How Paged Attention and Continuous Batching Actually Work

Every serious inference engine built since 2023, vLLM, SGLang, TensorRT-LLM, and our own runtime included, rests on the same two ideas: paged attention and continuous batching. They are usually name-dropped and rarely explained mechanically, which is a shame, because neither is hard once you see what problem it solves, and both are the reason one GPU today serves traffic that used to take three.

This article explains how they actually work: the block tables and the indexing formula behind paged attention, and the scheduling loop behind continuous batching. It draws on the vLLM V1 architecture, following Aleksa Gordić's excellent code-level breakdown and the original papers, with the memory arithmetic worked out on a concrete model

TL;DR

• The KV cache is dynamic memory: it grows one token at a time to an unknown final length. Contiguous allocators handled that by reserving the maximum, wasting most of it.
• Paged attention is virtual memory for the KV cache: fixed 16-token blocks, a per-request block table, and one indexing formula. Worst-case waste drops from most of the reservation to 15 tokens per sequence.
• Continuous batching schedules per step, not per batch: when a request finishes, its slot is refilled at the very next iteration instead of waiting for the longest request in the batch.
• The two are one system: batching keeps the GPU busy only if memory can be granted and reclaimed at token granularity, which is exactly what paging provides.
• The reason it all matters is the roofline: below roughly 200 concurrent sequences, an 8B decode step on an H200 costs the same 3.3 ms whether it serves 1 token or 200. Empty batch slots are pure waste.

The problem: KV cache is dynamic memory

During generation the model caches a key and a value vector for every token it has seen, per layer (the mechanics are in our KV cache explainer, and the sizing maths in the VRAM guide). For a Llama-3.1-8B-class model, 32 layers, 8 KV heads, head dimension 128, bf16, that costs:

The awkward part is not the size, it is the shape of the demand. The cache grows by one token per step, to a final length nobody knows in advance, and it must be freed the instant the request finishes. That is heap allocation, happening thousands of times per second, inside GPU memory.

Pre-2023 engines dodged the problem by reserving one contiguous slab per request, sized for the maximum the request might reach. The PagedAttention authors measured what that costs: in existing systems, only 20 to 40% of KV memory held actual token state. The rest was reservation, padding, and fragmentation. Here is that failure on our 8B model, for a request that ends up 200 tokens long against a 4,096-token maximum:

Wasted KV memory is not a rounding error. It is lost concurrency: every wasted gigabyte is a batch slot some other user could have occupied.

Paged attention: virtual memory for the KV cache

The fix is the one operating systems shipped in the 1960s: stop requiring contiguity. Chop KV memory into fixed-size blocks of 16 tokens, keep a pool of free blocks, and give each request a block table, a small array mapping its logical positions to whichever physical blocks it happened to be granted. Blocks of one sequence can be scattered anywhere in VRAM.

At startup the engine profiles a forward pass, sees what VRAM remains after weights and activations, and carves all of it into this pool, often hundreds of thousands of blocks held in a free list. Allocation is popping from that list; freeing is pushing back onto it. Both are O(1), which is what lets the scheduler do them every single step.

The entire trick then compresses into one line of indexing. When the attention kernel needs the KV entry for token position $p$ of a request, it computes:

Divide to find which logical block the token lives in, look up the physical block the table assigned, multiply out, add the offset. The kernel gathers KV entries through this mapping instead of assuming they sit side by side. That gather is the only price of paging, and fused kernels hide it well.

Allocation now tracks actual length instead of feared length. A request that has produced $t$ tokens holds $\lceil t/16\rceil$ blocks, so the waste is bounded by what fits in one partial block:

per sequence, versus hundreds of megabytes under reservation. That is the whole mechanism. Two consequences fall out of it almost for free. First, sharing: because the table is indirection, two requests with the same prefix can point at the same physical blocks with a reference count, which is what prefix caching is (block hashes decide when it is safe, as covered in the token cost guide's caching section). Second, preemption: under memory pressure the engine can evict a low-priority request by returning its blocks to the pool and recomputing later, because giving memory back is just as O(1) as taking it.

Continuous batching: schedule steps, not batches

Now the second idea. Batching exists because of the decode roofline: a decode step must stream all 16 GB of the model's weights from HBM regardless of how many sequences it serves, so the step costs about the same until there is enough arithmetic to hide the streaming:

So throughput lives and dies by how full the batch is. The old approach, static batching, formed a batch, ran it to completion, then formed the next one. But generation lengths are wildly uneven, so the batch runs at the pace of its longest member while finished slots sit idle:

Continuous batching, introduced by Orca and at the heart of vLLM's engine loop, moves the scheduling decision from the batch to the iteration. Every step, the scheduler rebuilds the working set: it walks the running queue granting each decode its next token's worth of blocks, then admits prefills from the waiting queue until a per-step token budget is spent. A request that finishes this step returns its blocks to the pool this step; a request that arrived a millisecond ago can be computing in the very next one.

The part that makes this cheap is how the forward pass is shaped. The batch is not a padded matrix of sequences. Every scheduled token, from every request, prefill and decode alike, is flattened into one long sequence, and attention metadata tells the kernel where each request's tokens begin, end, and are allowed to look. No right-padding, no wasted lanes, and mixed prefill/decode steps come free. Chunked prefill is the same budget logic applied once more: a very long prompt is fed in slices so it cannot monopolise a step while everyone else's latency spikes.

And here is why the two ideas are really one system: iteration-level scheduling only works if memory can be granted and reclaimed at iteration granularity. A contiguous allocator cannot admit a request whose reservation does not fit, even when plenty of scattered free memory exists. The block pool can. Paging is what makes continuous batching's promise, "any free slot refills immediately", actually true.

One step, end to end

Putting it together, here is what one iteration of the engine loop does:

• Schedule: for each running request, compute tokens needed this step and call allocate_slots, popping $\lceil \text{new}/16\rceil$ blocks from the pool. Admit waiting prefills while the token budget lasts. If the pool runs dry, preempt the lowest-priority request and return its blocks.
• Forward pass: flatten every scheduled token into the super-sequence, gather and write KV through the slot-mapping formula, sample one token per sequence at its final position.
• Postprocess: append sampled tokens, check stop conditions, and for every finished request push its blocks straight back onto the free list, where the next step's scheduling can hand them to someone else.

That loop, run thousands of times a second, is the entire runtime behaviour of a modern engine. Everything else, prefix caching, speculative decoding, guided decoding, disaggregated prefill, plugs into one of those three stages.

What this means when you serve a model

Three practical consequences follow directly from the mechanics.

Your capacity is the block pool. After weights and overhead, whatever VRAM remains becomes KV blocks, and concurrency times context length must fit inside it. That is the token-capacity arithmetic we derived in the VRAM guide, and the LLM VRAM Calculator computes it per model.

Latency spikes usually mean pool pressure, not compute. When the free list empties, the engine preempts and recomputes, which shows up as sudden inter-token stalls. The fix is a smaller advertised context, a quantized KV cache, or fewer wasted prompt tokens, which is why trimming inputs with Token Counter or Web to Markdown translates directly into steadier latency.

Engines differ above this layer, not below it. Paging and continuous batching are table stakes; the differences that show up in benchmarks come from scheduling policy, kernel quality, and speculative execution. That is the layer Netra competes at: our runtime serves up to 4x more output per second than vLLM on the same GPU and the same weights, and we deploy it on infrastructure you own.

FAQ

Why 16 tokens per block? It is a fragmentation-versus-overhead dial. Smaller blocks waste less in the final partial block but mean longer block tables and more gather indirection; larger blocks reverse the trade. 16 is vLLM's default, and other engines pick nearby powers of two.

Does paging make attention slower? The kernel pays one extra indirection per block through the table. In fused implementations the cost is small, and it buys back far more in concurrency than it spends in gather latency.

Is continuous batching why my per-request latency varies? Partly. Your tokens share each step with everyone else's, so inter-token latency rises with load. Engines bound this with the per-step token budget and chunked prefill so one long prompt cannot starve the rest.

Do these ideas apply to linear-attention models? The batching logic does; the paging story changes, because models like Qwen's GDN layers keep a fixed-size state instead of a growing cache. We covered what replaces the problem in the GDN kernel deep dive.

Where does prefix caching fit? It is a consequence of paging: blocks are content-hashed, and a new request whose prompt hashes to already-resident blocks simply points at them instead of recomputing. Shared system prompts are the big winner.

Free tools from Netra

All of these run in your browser. No signup, and your data is not uploaded to us.

• LLM VRAM Calculator: how much of your card the weights and KV block pool will take.
• Token Counter: measure the prompts that fill those KV blocks.
• Fine-Tuning Memory Calculator: the training-time memory budget.
• Web to Markdown: strip pages to clean Markdown before they reach a prompt.
• Free OCR: turn scans and PDFs into LLM-ready text.
• Limbus: local-first image segmentation.
• sam3.c: SAM3 inference in pure C.

References

• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, the vLLM paper.
• Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models, where iteration-level (continuous) batching was introduced.
• Aleksa Gordić, Inside vLLM: Anatomy of a High-Throughput LLM Inference System, the code-level walkthrough of vLLM V1 this article draws on.
• vLLM V1 engine documentation.