Continuous Batching and PagedAttention: How vLLM Keeps a GPU Busy

A GPU serving one LLM request is mostly idle. Not slightly idle. Most of the silicon does nothing for most of the wall clock, because every decode step drags the entire model out of HBM to produce a single token. Part 9 showed why decode is memory-bound and why batch size is the only lever that moves it. Continuous batching and PagedAttention are the two engineering ideas that let you actually pull that lever.

They fix different things. Continuous batching fixes scheduling: who is in the batch, and when they may join or leave. PagedAttention fixes memory: how the KV cache is allocated, and how much of it you waste. Iteration-level scheduling came from Orca in 2022, PagedAttention from vLLM in 2023. Together they are why a naive Hugging Face generate() loop leaves most of a rented H100 doing nothing.

PagedAttention only makes sense as a fix for a problem that continuous batching creates, so the order here is scheduling first and memory second. By the end you will be able to work out how many concurrent sequences your KV cache holds, explain why PagedAttention has nothing to do with attention, and read the five vLLM flags that control both.

Where the idle GPU time goes

One request, alone on the machine

A single request has two phases: one wide parallel pass over the prompt, called prefill, then a long serial run of one-token steps, called decode. Prefill is short in wall-clock time and dense in work. Decode ticks are individually cheap and there are hundreds of them.

The ticks are the problem. Each one reads all 140 GB of a 70B-class model’s weights to emit one token. The arithmetic units barely warm up, and the slice of the card you are using does not get bigger by trying harder.

Static batching gets the roofline win, then throws half of it away

Group four requests, run them as one batch, and the weights are read once per step and shared by all four. That is nearly free throughput, and it is exactly the win from Part 9: arithmetic intensity rises with batch size, so you slide rightward off the memory slope.

Then the output lengths ruin it. R4 stops generating at step 7. R2 stops at step 10. But the batch formed as a unit and it dissolves as a unit, so nothing is released until R1 finishes at step 26. Those slots sit dead for the whole interval, still holding cache, still counted against capacity, producing nothing.

The precise version of the cause tells you the fix. The batch is the unit of scheduling. Membership is decided once, at admission, at the exact moment when the one fact that matters is unknowable: how many tokens each sequence will generate. Nobody chose it and nobody can predict it. The model decides when it emits a stop token, several hundred forward passes into the future.

A second failure sits on top of the first. Requests arriving at step 3 can see empty slots from step 7 onward and cannot touch them. They wait for the batch to drain. This is textbook head-of-line blocking, and it is unpleasant to explain to a customer: R1’s generation length sets the time to first token for everyone queued behind it.

Continuous batching: make the step the unit of scheduling

A decode step needs one thing from each sequence: a KV cache to attend over. It does not care what the previous step’s membership was, and nothing else survives a step boundary. The batch dimension carries no state, so it is free to change between steps.

So recompute membership every iteration. Finished sequences are evicted the moment they emit a stop token and their cache is freed at once. Waiting requests are admitted into the vacancy at that same boundary. In the diagram the rows stop being requests and become slots, which is the entire change. R4 ends at step 7 and R5 starts at step 7. R2 ends at 10 and R6 starts at 10. The slots never go grey, and the scheduler now runs once per token rather than once per request, which is why the second name for it, iteration-level scheduling, is the more accurate one.

The scheduler loop, written out

Stripped of accounting, the loop that produces that diagram is about twenty lines, and all of it is bookkeeping wrapped around one forward pass.

while True:
    # 1. retire anything that hit EOS or its length limit last step
    for seq in list(running):
        if seq.finished:
            running.remove(seq)
            free_blocks(seq)

    # 2. fill the vacancy from the waiting queue, memory permitting
    while waiting and can_allocate(waiting[0]):
        seq = waiting.popleft()
        allocate_blocks(seq)
        running.append(seq)

    # 3. if a running sequence cannot grow, something has to give
    while not can_grow(running):
        victim = running.pop()        # newest first, usually
        free_blocks(victim)           # its tokens get recomputed later
        waiting.appendleft(victim)

    # 4. one forward pass, one token for every sequence in running
    logits = model.step(running)
    for seq, token in zip(running, sample(logits)):
        seq.append(token)

Steps 1 and 4 are bookkeeping. Steps 2 and 3 are both memory questions: can this new sequence’s cache fit, and if a running sequence needs another block and there is none, who gets thrown out. Every interesting decision in continuous batching is an allocation decision.

The honest complication: admitting someone costs the incumbents

Admitting a request means running its prefill, and prefill is a different shape of work from decode. A 2,000-token prompt does not slot cleanly into a decode step. Run it as its own step and every active stream freezes for the duration. Users see a stutter, and your metrics show a spike in time per output token. If you are streaming responses, that stutter is the most visible thing your service does.

The roofline reading of that is neat: the decode portion of the step leaves the arithmetic units idle, and the prefill chunk fills exactly that gap. Nobody stalls.

The tradeoff is real. Existing users get a smoother time per output token. The arriving user gets a slightly worse time to first token, since their prompt is now spread over several steps. That is usually the trade you want, because one person waiting an extra 80 milliseconds beats forty people seeing a visible hitch.

Memory is the ceiling, and contiguous allocation wastes most of it

Roofline says batch until you approach the ridge. In practice you stop well short, and continuous batching is what makes the limit bite. Weights amortize across the batch, which is the whole point. KV cache does not. Each sequence holds a private cache, and that cache grows with every token it generates.

So the HBM budget has two very different tenants. Weights are a fixed toll, paid once, shared by everyone. Everything left over is divided among concurrent sequences. The gap between them is your batch size, and at long context it closes early. A batch that fit at step 0 can stop fitting at step 200, which is when the scheduler must preempt a sequence that is already running rather than simply decline an arriving one.

The bind: reserve before you can know

Before vLLM, a sequence’s KV cache was one contiguous slab. A contiguous allocation cannot grow, because the bytes after it belong to someone else. So at admission you reserve for the largest the sequence could ever become. Reserve for the expected size instead, and when the model generates past it there is nowhere to put the overflow.

Combine that with the scheduling half: the length is unknowable at admission. The reservation is therefore always worst case, and worst case is almost never what happens. A request declares max_tokens of 2,048 and generates 300. That is the normal outcome, not the pathological one. The other 1,748 slots are held for the entire life of the request and unavailable to anyone else.

Then churn turns the cache into Swiss cheese

Continuous batching means constant arrivals and departures. Sequences of different sizes free their slabs at different moments, leaving gaps between live neighbours. After a couple of minutes of real traffic the cache reads: live sequence, 600-slot gap, live sequence, 550-slot gap, and so on.

Now a request arrives needing 1,200 contiguous slots. There are 1,700 free in total, and it cannot be served, because no single gap is big enough. This is external fragmentation, and anyone who has read about page allocation inside a storage engine will recognise it. It also worsens the longer the server runs, so throughput degrades quietly over a shift and recovers when someone restarts the process.

Cache capacity caps batch size, and batch size is your position on the memory slope. Two thirds of the cache lost to over-reservation and fragmentation pins you far to the left of the ridge with the arithmetic units idle, for no reason except allocation policy. That is a bookkeeping limit wearing a hardware limit’s clothes.

PagedAttention: a memory allocator borrowed from virtual memory

The name misleads nearly everyone. PagedAttention is a memory allocator for the KV cache, lifted almost unchanged from operating system virtual memory. It changes nothing about how attention scores are computed and does not alter the math from Part 4 on multi-head attention. It needed a custom kernel only because the kernel must now look up where the data lives before it reads it.

Fixed-size blocks make every free block usable

The attention kernel needs to find the K and V for position 7. It does not need position 7 to sit physically beside position 6. If something else can say where position 7 lives, the physical layout is free. So chop the cache into fixed-size blocks, 16 tokens each by default in vLLM, and let them land anywhere. Every block is identical, so any free block satisfies any request, and external fragmentation stops existing by construction.

The block table is a page table

Each sequence keeps a small array mapping logical block indices to the physical blocks holding them. The sequence believes it has contiguous memory. Physically its blocks are scattered across HBM in whatever order they were handed out.

The correspondence with virtual memory is exact and deliberate. Block is page, block table is page table, token positions are the virtual address space, HBM is physical memory. The price is paid in the kernel, which must gather through the table instead of striding, and that costs a few percent.

Growth on demand, so the unknowable length stops mattering

A sequence gets the blocks its prompt needs, then one more only when the current one fills. There is no reservation, so there is no guess to get wrong. The problem from the scheduling half, that you must commit to a length before you can know it, simply stops existing.

What remains is internal fragmentation, bounded at 15 unused slots in the final partial block, once per sequence. For the 300-token request above that is 4 wasted slots out of 304 allocated, about 1.3 percent, against 85 percent under contiguous allocation.

Sharing, the part that goes beyond fixing what broke

Because every access runs through a table, two sequences can point at the same physical block. Requests sharing a system prompt have bit-identical K and V for that prefix, so store it once and let both tables reference it, with a reference count tracking how many. When one diverges and needs to write, it gets a private copy first.

This is the mechanism underneath prefix caching, and it is a real cost lever. A 1,200-token system prompt shared across thousands of requests is stored once and, with prefix caching on, prefilled once. Anyone who has measured what prompt caching does to a bill on a hosted API is seeing the same idea from outside. The same indirection makes parallel sampling cheap, since four completions from one prompt share the prompt’s blocks.

The honest scoreboard

PagedAttention makes nothing faster per token. The gather costs a few percent on the attention kernel. What it does is let three to four times as many sequences fit in the same cache, which raises batch size, which slides you rightward on the roofline slope.

The vLLM paper reports that serving systems before it wasted 60 to 80 percent of KV cache memory to fragmentation and over-reservation, and that vLLM holds waste under 4 percent. It reports 2 to 4 times higher throughput at comparable latency against FasterTransformer and Orca, with the gain largest for long sequences, large models and complex decoding schemes. Those are the authors’ measurements on their hardware and workloads, so treat them as the right order of magnitude rather than a number to expect exactly.

The sentence worth keeping: PagedAttention does not make attention faster, it makes the server bigger.

Sizing the KV cache for the running 70B model

The running example is a Llama-3-70B class model: 80 layers, 8 KV heads, head_dim 128, bf16 throughout. Per token, per layer, you store one K vector and one V vector for each KV head. That is 2 tensors times 8 heads times 128 dimensions, which is 2,048 values. At 2 bytes each in bf16 that is 4,096 bytes, or 4 KiB per token per layer. Multiply by 80 layers for 327,680 bytes per token, which is 320 KiB. A 4,096-token sequence therefore holds 1.25 GiB of KV cache, per user, on top of the 140 GB of weights.

Now the payoff for grouped-query attention from Part 4. Plain multi-head attention gives this model 64 KV heads instead of 8, an eight-fold increase in every line.

That 140 GiB is roughly what four 80 GB cards leave after 140 GB of bf16 weights, workspace and activations. So the deployment holds 112 concurrent full-context sequences. Recall from Part 9 that decode’s arithmetic intensity is roughly the batch size, since a bf16 weight byte earns about one FLOP per sequence in the batch. An A100 offers about 312 TFLOP/s against 2.0 TB/s, so its ridge sits near batch 150. At 112 you are close. At 14 you are nowhere near it, and the cards spend their lives on the memory slope. That is what eight KV heads bought.

The vLLM flags that actually matter here

Five flags control everything above. The defaults are sensible, and the failure modes are specific enough to diagnose from a log.

What your stack actually does under this load is a measurement, not an argument, which is where Part 11 on benchmarking your own serving stackcoming 19 Aug picks up.

Key takeaways

• Static batching wastes slots because the batch is the unit of scheduling, and membership is fixed at the one moment when generation length is unknowable.
• Continuous batching rebuilds membership every forward pass, so finished sequences leave and queued ones join at the same step boundary. Nothing survives a step except each sequence’s KV cache, which is what makes it legal.
• Admitting a request runs its prefill and stalls every active stream. Chunked prefill trades a little time to first token for the newcomer against smooth pacing for everyone already running.
• PagedAttention is a memory allocator, not an attention technique. Block is page, block table is page table, and copy-on-write comes along unchanged.
• Contiguous allocation forces worst-case reservation and then fragments, which the vLLM paper measured at 60 to 80 percent waste. Paging cuts that to a few percent.
• The running 70B model costs 320 KiB of cache per token, or 1.25 GiB for a full 4,096-token sequence. Grouped-query attention is why that is 1.25 GiB instead of 10 GiB.
• Preemption warnings mean you ran out of KV cache and are recomputing work you already paid for. Watch reported cache usage before it gets there.

Frequently asked questions

What is the difference between continuous batching and static batching?

Static batching fixes the set of requests when the batch forms and runs it to completion, so a slot freed by a short request stays idle until the longest request in the batch finishes. Continuous batching recomputes membership at every forward pass, so finished sequences are evicted and queued ones admitted at the same step boundary. The change is that the scheduling unit becomes the iteration rather than the batch.

Is PagedAttention an attention algorithm?

No. It is a memory allocator for the KV cache, borrowed from operating system virtual memory, and it does not change how attention scores are computed. It needed a custom kernel only because the kernel must now gather K and V through a block table instead of striding through contiguous memory.

How much KV cache does a 70B model need per token?

For a Llama-3-70B class model with 80 layers, 8 KV heads and head_dim 128 in bf16, one token costs 2 x 8 x 128 x 2 bytes per layer, which is 4 KiB, and 320 KiB across all 80 layers. A full 4,096-token sequence therefore holds 1.25 GiB of cache, so 140 GiB of spare HBM holds about 112 concurrent sequences.

Why does vLLM log preemption warnings?

Preemption means the scheduler ran out of free KV cache blocks and had to evict a sequence that was already running, so its tokens get recomputed later. It is the clearest symptom of an undersized cache, and the usual responses are more GPU memory, more tensor parallelism, a higher gpu_memory_utilization value, or a lower max_num_seqs.

Should I enable chunked prefill?

Enable it when long prompts are causing visible stutters in active token streams, which is most interactive workloads. It costs the arriving request a little time to first token because its prompt is spread across several steps. Recent vLLM versions enable it by default, so confirm your version’s behaviour before changing the flag.

Does PagedAttention make inference faster?

Not per token. The block table gather costs a few percent on the attention kernel. It raises throughput by letting far more sequences fit in the same cache, which increases batch size and moves decode rightward on the roofline toward the compute ceiling.

Sources and further reading

• Efficient Memory Management for Large Language Model Serving with PagedAttention, Kwon et al. The vLLM paper, source of the waste measurement and the throughput comparisons.
• Orca: A Distributed Serving System for Transformer-Based Generative Models, Yu et al., OSDI 2022. The origin of iteration-level scheduling.
• vLLM documentation, for current flag names, defaults and engine behaviour, which move between releases.
• GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints, Ainslie et al. Why the model has 8 KV heads instead of 64.
• Roofline: An Insightful Visual Performance Model for Multicore Architectures, Williams, Waterman and Patterson.