Batching and PagedAttention: How vLLM Serves Hundreds 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 manage it the way an operating system manages memory. PagedAttention turns the KV cache into a pool of small fixed-size blocks, and continuous batching schedules one model step at a time to keep the GPU (graphics processing unit) busy. Together they let one GPU serve hundreds of concurrent requests without the fragmentation and head-of-line blocking that cripple static batching.
The result is large. The team's vLLM launch post reports that existing systems wasted 60 to 80 percent of KV cache memory and vLLM wastes under 4 percent, and their paper, Efficient Memory Management for Large Language Model Serving with PagedAttention, measured 2 to 4 times the throughput of the best earlier systems at the same 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. The vLLM paper measured that in existing systems only 20.4 to 38.2 percent of the KV cache memory held actual token states, so 60 to 80 percent was stranded. 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; the paper chose 16 as the default, large enough to use the GPU efficiently and small enough to keep waste low, and 16 is still vLLM's default. Counting every layer, one block takes block_size × num_layers × 2 × num_kv_heads × head_dim × bytes_per_number bytes. For Llama 3.1 8B in BF16 that is 16 tokens × 128 KiB = 2 MiB (Part 2 worked out the 128 KiB per token).
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 small for realistic lengths.
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, the kernel can still issue coalesced memory accesses within each block. The indirection does cost something. In the paper's microbenchmark, the PagedAttention kernel had 20 to 26 percent higher attention latency than FasterTransformer's highly optimized contiguous kernel, because of the block table lookups, extra branches and variable sequence lengths. Decode attention is limited by memory reads, so there is no heavy arithmetic to hide this behind.
The whole system still wins by a wide margin, because far more sequences fit in each batch. A slightly slower kernel running a batch several times larger produces many more tokens per second. That trade 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 launch post puts the waste under 4 percent, compared to 60 to 80 percent in systems that preallocate contiguous tensors.
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. The chart below uses the same two sources as the opening: the vLLM paper and the vLLM launch post.
- 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. The paper describes a copy-on-write mechanism at block granularity: 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. When the last reader drops its reference, the block returns to the free pool.
This sharing saves a lot of memory for workloads with long system prompts or repeated prefixes. On the paper's two test datasets it saved 6 to 30 percent of memory for parallel sampling and 38 to 66 percent for beam search, because every candidate shares the same prompt KV cache and only pays for the tokens where it differs.
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 model 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 idea, called iteration-level scheduling, comes from the Orca system (Orca: A Distributed Serving System for Transformer-Based Generative Models, OSDI 2022); vLLM pairs it with paged memory.
This step-by-step scheduling removes 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. In current vLLM, chunked prefill is on by default and the scheduler places every waiting decode in the batch before it fills the rest of the step's token budget with prefill chunks (vLLM's tuning guide).
How big does a batch get? Current vLLM caps it at 256 sequences by default, or 1,024 on the largest GPUs such as the H100, H200 and B200 (vLLM's engine defaults), and the KV pool usually runs out before that cap for long requests. Thousands of users are served by many GPUs together.
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 FasterTransformer and Orca at the same latency, measured on NVIDIA A100 GPUs. The launch post, comparing against plain Hugging Face Transformers generation, reported up to 24 times the throughput, and up to 3.5 times that of Hugging Face's Text Generation Inference. 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 (earlier systems) | 60-80% |
| KV cache waste (vLLM) | under 4% |
| Throughput vs. Orca and FasterTransformer | 2-4× at the same latency (A100 GPUs) |
| Throughput vs. Hugging Face Transformers | up to 24× (vLLM launch post) |
| Bytes per block | block_size × num_layers × 2 × num_kv_heads × head_dim × bytes_per_number |
| Attention kernel cost | 20-26% slower than a contiguous kernel, outweighed by bigger batches |
| Scheduler granularity | One model iteration (iteration-level scheduling, from Orca) |
| Prefix sharing mechanism | Copy-on-write with reference counting |
| Batch cap in current vLLM | 256 sequences by default, 1,024 on the largest GPUs |
Frequently Asked Questions
Q: Does PagedAttention add latency overhead compared to contiguous KV caches?
Yes, a little, inside the attention kernel. The vLLM paper measured 20 to 26 percent higher attention kernel latency than FasterTransformer's contiguous kernel. Attention is only part of each step, and the paged layout fits far more sequences into each batch, so end to end the system delivers 2 to 4 times the throughput at the same latency.
Q: What happens when the KV pool runs out of blocks?
vLLM preempts requests: it picks whole sequences (the most recently admitted first, or the lowest priority under the priority policy) and frees all their blocks. When memory frees up, current vLLM recomputes their cache by re-running prefill over everything they had so far. The original paper also describes copying the blocks to CPU (central processing unit) memory and back, which is the closer analogy to swapping in an OS; current vLLM's default is to recompute rather than swap.
Q: Can I use PagedAttention with any model architecture?
Most popular models work. vLLM's supported models list covers the common open families, such as Llama, Mistral, Qwen, DeepSeek, Gemma and gpt-oss, including attention variants like grouped-query attention, and it even runs state-space and hybrid models such as Mamba and Jamba, which keep a different kind of cache. A brand-new attention design may need its own kernel before it can use paged blocks.
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. With tensor parallelism, attention is split by heads: each GPU stores the KV cache only for its own heads, while one KV cache manager in the central scheduler keeps a single block table that every GPU follows, so all of them use the same physical block IDs. 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. Each short request holds 256 + 100 = 356 tokens, which is ceil(356/16) = 23 blocks, so all 100 together need 2,300 blocks. Each long request needs ceil(8000/16) = 500 blocks for its prompt, 2,500 for all five. Even if every short request were still running, 2,300 + 2,500 = 4,800 blocks (about 4,835 once the long requests generate 100 tokens each) is under half of the 10,000-block pool, so nothing is preempted. Chunked prefill splits each 8,000-token prompt across several steps, so the short requests keep decoding instead of stalling behind a giant prefill. Static batching would reserve a contiguous buffer for the maximum length, say 8,192 tokens, for every request. Each short request would leave 8,192 minus 356, or 7,836, slots unused, memory would run out after a small batch, and the long prompts would block the queue while the GPU sat partly idle.
Next: Quantization: Smaller Weights, Same Answers (Mostly). It shrinks the weights themselves, so every decode step has fewer bytes to read.
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
- Efficient Memory Management for Large Language Model Serving with PagedAttention (Kwon et al. 2023)
- vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention (vLLM launch post, June 2023)
- Orca: A Distributed Serving System for Transformer-Based Generative Models (Yu et al., OSDI 2022)
- Optimization and Tuning (vLLM documentation)
- vLLM engine argument defaults (source code)
- vLLM supported models
