Batching and PagedAttention: How vLLM Serves Thousands at Once
Continuous batching and paged memory: the two ideas behind modern serving throughput.
After understanding why the KV (key-value) cache is both essential and expensive, vLLM’s answer is to virtualize it. PagedAttention turns the KV cache into a block-based memory pool, and continuous batching schedules at the token level to keep the GPU (graphics processing unit) saturated. Together they let a single GPU serve thousands of concurrent requests without the fragmentation and head-of-line blocking that cripple static batching.
The surprising result is that memory waste drops from 60 to 80 percent in naive frameworks to under 4 percent in vLLM. That means the same GPU can run 2 to 4 times more requests at similar latency. The trick is not a new math formula. It is a memory layout and a scheduler that treat tokens the way an operating system treats virtual memory pages.
The problem: static batching and contiguous KV allocation
A naive inference server forms a batch, pads all sequences to the same length, runs a forward pass, and waits until every sequence finishes before forming a new batch. This static batching wastes compute because short sequences sit idle while long ones continue. It also wastes memory because each sequence gets a contiguous KV cache sized for the maximum possible length, regardless of how many tokens it actually uses.
When sequences finish at different times, the freed memory leaves holes. Those holes are often too small to fit a new full-length KV tensor, even if total free memory is enough. This is external fragmentation. Meanwhile, the unused slots inside each over-allocated tensor are internal fragmentation. Together they can strand 60 to 80 percent of the KV cache memory vLLM paper. The GPU starves for memory, so batch sizes stay small and throughput collapses.
Static batching also forces a coarse scheduling loop. New requests queue up until the current batch finishes. If a single long prompt arrives, it blocks everything behind it. The GPU sits underutilized while waiting for that one sequence to complete. This is the head-of-line blocking problem that continuous batching solves.
How PagedAttention virtualizes the KV cache
PagedAttention borrows the idea of virtual memory from operating systems. Instead of a contiguous KV tensor per request, it preallocates a large global pool of fixed-size KV blocks. Each block holds the keys and values for a small number of tokens (typically 16 or 32) across all layers and heads. The block size in bytes is block_size × num_hidden_layers × kv_hidden_size, where kv_hidden_size captures both key and value dimensions vLLM docs.
A sequence never sees physical blocks directly. It sees a logical address space divided into logical blocks. A per-sequence block table maps each logical block index to a physical block ID in the global pool. The blocks for a single sequence can be scattered anywhere in GPU memory. The block table keeps them in order.
This indirection is the heart of the design. Allocating KV space for a new token means, if the current block is full, grabbing a free physical block from the pool and appending its ID to the block table. Deallocation returns the block to the free list. No compaction, no splitting, no external fragmentation. Internal fragmentation is at most one partially filled block per sequence, which is negligible for realistic lengths vLLM paper.
How the attention kernel reads non-contiguous pages
Standard attention kernels assume keys and values are contiguous in memory. PagedAttention replaces that assumption with a block table lookup inside the kernel. For each query token, the kernel iterates over the logical blocks that cover the context window. For each logical block, it reads the physical block ID from the sequence’s block table, computes the base address, and loads the key and value slices for the tokens in that block.
Because the block size is fixed and known at compile time, the kernel can still issue coalesced memory accesses within each block. The extra indirection adds a small constant overhead, but it is hidden by the heavy arithmetic of attention. The vLLM team implemented this as a custom CUDA kernel that matches or beats contiguous-kernel throughput at large batch sizes.
The block table entries are small integers. They can be cached in registers or shared memory, so the lookup cost is minimal. The result is that attention runs at full speed even though the underlying memory layout is fragmented. This is what makes the virtual memory analogy practical on a GPU.
How on-demand allocation eliminates waste
Because blocks are independent, vLLM allocates them only when a sequence actually needs them. During prefill, it allocates exactly enough blocks to cover the prompt tokens. During decode, it allocates a new block only when the sequence crosses a block boundary. When a sequence finishes, all its blocks (except shared prefixes) return to the free pool immediately.
The only waste is the unused slots in the last block of each sequence. With a block size of 16 tokens and a typical sequence of 512 tokens, that is at most 15 wasted slots, or under 3 percent overhead. Across a whole workload, the measured waste drops to under 4 percent, compared to 60 to 80 percent in systems that preallocate contiguous tensors vLLM paper.
This near-zero waste directly translates into larger effective batch sizes. More KV cache memory means more concurrent sequences can fit on the GPU. The scheduler can keep the compute units busy instead of waiting for memory to free up.
- Sequences padded to max length
- KV tensors allocated contiguously
- Memory waste 60-80%
- Batch size limited by memory holes
- No padding, blocks allocated on demand
- Non-contiguous blocks with block table
- Memory waste under 4%
- Batch size limited only by total KV pool
How prefix sharing works with copy-on-write
When multiple sequences share a common prefix, vLLM can map the same physical blocks into their block tables. This happens automatically in parallel sampling from a single prompt, in beam search, and when caching system prompts across requests. The shared blocks are reference-counted. As long as all sequences only read from a block, they can share it without duplication.
When a sequence generates a new token beyond the shared prefix, it needs its own copy of the last block if that block is not yet full. vLLM implements a copy-on-write mechanism: the first writer to a shared block triggers a copy of that block’s data into a new physical block, and the writer’s block table is updated to point to the private copy. Other readers continue using the original shared block vLLM paper. When the last reader drops its reference, the block returns to the free pool.
This sharing dramatically reduces memory for workloads with long system prompts or repeated prefixes. It also makes beam search practical at scale, because thousands of candidates can share the same prompt KV cache and only pay for the divergent tokens.
How continuous batching keeps the GPU saturated
Continuous batching abandons the idea of a fixed batch that lives for many steps. Instead, the scheduler runs one decoding iteration at a time. At each step, it builds a batch from every active sequence. When a sequence finishes, its slot is freed immediately. When new requests arrive, they are added to the batch at the next iteration, without waiting for a batch boundary.
This token-level scheduling eliminates head-of-line blocking. A long prompt does not hold up short ones. The GPU stays busy because every iteration uses all available sequences. The scheduler can also interleave prefill and decode. A pure decode batch is memory-bound, while a prefill batch is compute-bound. By mixing them, vLLM balances the two and avoids stalling either.
Chunked prefill further refines this. A long prompt is split into chunks and processed over multiple iterations, interleaved with decode steps from other sequences. This prevents a single large prefill from monopolizing the GPU and causing latency spikes for ongoing generations.
How PagedAttention and continuous batching reinforce each other
These two ideas are not independent optimizations. They form a cycle. PagedAttention provides a flexible memory pool that can absorb the constant churn of sequences starting and stopping. Without it, continuous batching would quickly fragment memory and fail to allocate KV space for new requests. Continuous batching, in turn, exploits the freed blocks immediately, converting memory efficiency into higher throughput.
The vLLM paper reports that this combination delivers 2 to 4 times the throughput of state-of-the-art systems like FasterTransformer and Orca at the same latency, and up to 10 times over naive static-batching loops on modern GPUs like the H100 vLLM paper. The key metric is not just raw tokens per second, but the number of concurrent requests a single GPU can handle without latency degradation.
Quick Reference
| Property | Value |
|---|---|
| Default block size | 16 tokens |
| KV cache waste (naive) | 60-80% |
| KV cache waste (vLLM) | <4% |
| Throughput gain vs. Orca/FasterTransformer | 2-4× |
| Throughput gain vs. naive static batching | up to 10× |
| Page size formula | block_size × num_hidden_layers × kv_hidden_size |
| Scheduler granularity | Token step (decode iteration) |
| Prefix sharing mechanism | Copy-on-write with reference counting |
Frequently Asked Questions
Q: Does PagedAttention add latency overhead compared to contiguous KV caches?
No measurable overhead at serving batch sizes. The custom CUDA kernel hides the block table indirection behind the arithmetic intensity of attention. For very small batches the overhead might be visible, but those are not the regime where vLLM is designed to win vLLM paper.
Q: What happens when the KV pool runs out of blocks?
vLLM can evict blocks to CPU (central processing unit) memory and reload them when needed, or it can preempt the lowest-priority sequences and free their blocks. The exact policy is configurable. This is analogous to swapping in an OS.
Q: Can I use PagedAttention with any model architecture?
PagedAttention requires a model that uses a standard multi-head attention mechanism where keys and values can be split into per-token slices. Most transformer-based LLMs (LLaMA, Mistral, Falcon, etc.) work. Architectures with fused or non-standard attention may need custom kernel support vLLM docs.
Q: How does chunked prefill interact with PagedAttention?
Chunked prefill processes a long prompt in multiple forward passes, each filling a few blocks. PagedAttention allows those blocks to be allocated incrementally and scattered in memory. The scheduler interleaves these prefill chunks with decode steps, keeping latency low while still saturating compute.
Q: Does vLLM support multi-GPU serving with PagedAttention?
Yes. vLLM combines tensor parallelism and pipeline parallelism with PagedAttention. The KV cache blocks are sharded across GPUs, and the block table is replicated or partitioned depending on the parallelism strategy. This scales both model size and request throughput.
Test yourself
You are running a vLLM server with a block size of 16 and a KV pool of 10,000 blocks. A burst of 100 requests arrives, each with a 256-token prompt and expected to generate about 100 tokens. A few minutes later, 5 long requests arrive with 8,000-token prompts. How does vLLM handle this mix without preemption, and why does static batching fail in the same scenario?
Answer: vLLM allocates blocks on demand. The 100 short requests each need ceil(256/16) = 16 blocks for the prompt and eventually ceil(100/16) = 7 more for generation, totaling 23 blocks per request. 100 requests consume 2,300 blocks, well within the pool. As they finish, blocks are freed immediately and reused. When the 5 long requests arrive, each needs ceil(8000/16) = 500 blocks for the prompt alone, totaling 2,500 blocks. By that time many short requests have finished, freeing blocks, so the pool can likely accommodate them. If not, vLLM can queue or preempt. Static batching would preallocate contiguous tensors sized for the maximum context length (say 8,192 tokens). Each of the 100 short requests would waste memory for 8,192 - 356 = 7,836 unused slots, quickly exhausting GPU memory and forcing a tiny batch size. The long requests would then cause head-of-line blocking, leaving the GPU idle while they complete.
If you want this kind of breakdown every week, how real systems actually work under the hood, subscribe to Internals Decoded at internalsdecoded.com.
Sources
- vLLM paper: Efficient Memory Management for Large Language Model Serving with PagedAttention
- vLLM architecture overview
- vLLM supported models