Before vLLM, LLM serving systems threw away most of the GPU memory they reserved for attention state. The measured number in the PagedAttention paper is stark: in existing systems, only 20.4%–38.2% of KV cache memory actually held token states. The rest was reservation, padding, and fragmentation. The fix was not a smarter model or a faster kernel — it was a memory allocator, lifted almost directly from your operating system's virtual memory design.
Why the KV cache is an allocator problem
During autoregressive decoding, a transformer caches the key and value vectors of every token it has seen, per layer, per attention head, so it doesn't recompute them on each step. This KV cache is big and it grows token by token.
The paper's worked example uses OPT-13B: a single token's KV cache takes 2 (one key vector, one value vector) × 5120 (hidden size) × 40 (layers) × 2 (bytes per FP16 value) = 800 KB. Not per sequence — per token. A sequence generating 2,000 tokens carries roughly 1.6 GB of cache. The vLLM team quoted a similar figure for LLaMA-13B: up to 1.7 GB for one sequence.
On a 13B-parameter model running on an NVIDIA A100 with 40 GB, the paper's breakdown puts about 65% of GPU memory into model weights and close to 30% into the KV cache, with activations taking the small remainder. Weights are static; you can't do anything about them. The KV cache is the only large, dynamic allocation on the GPU — so it determines your batch size, and batch size determines your throughput.
Here's the allocator problem: the cache grows and shrinks unpredictably (you don't know output lengths in advance), yet attention kernels historically required each sequence's cache to be one contiguous tensor. Contiguous plus dynamic plus unknown-length is exactly the combination that breaks naive allocators. Systems like FasterTransformer and Orca handled it the only way a contiguous layout allows: pre-allocate a slab sized to the maximum possible sequence length (say, 2,048 tokens) for every request.
The paper categorizes what gets wasted in that scheme:
- Reserved slots — memory held for tokens the sequence will eventually generate. Not usable by anyone else in the meantime, even though it's empty right now.
- Internal fragmentation — the gap between the max-length slab and the actual output. A request that generates 50 tokens against a 2,048-token reservation wastes ~97% of its slab, and you only find out at the end.
- External fragmentation — allocator-level waste (from a buddy-allocator-style scheme) because slabs come in different sizes.
Add it up and you get the 60–80% waste figure the vLLM authors reported for existing systems. Your "out of memory" errors at batch size 8 were mostly memory that held nothing.
The OS already solved this in the 1960s
Operating systems faced the same shape of problem with process memory: processes want contiguous address spaces, grow unpredictably, and can't each reserve their theoretical maximum. The solution was paging — divide memory into fixed-size pages, let a page table map contiguous virtual addresses onto scattered physical frames, and allocate frames on demand.
PagedAttention is that idea applied to attention. The KV cache of each sequence is partitioned into fixed-size blocks — vLLM's default holds 16 tokens per block, which the authors found "large enough to efficiently utilize the GPU and small enough to avoid significant internal fragmentation in most workloads." A per-sequence block table maps logical block numbers to physical block locations, and physical blocks are allocated only when the sequence actually grows into them. The attention kernel is rewritten to follow the block table instead of assuming contiguity.
The waste analysis becomes trivial: a sequence can waste memory only in its final, partially filled block — at most 15 token slots. The measured result is under 4% waste, versus 60–80%. Nothing about the model changed. The same weights, the same math — just far more sequences resident in memory at once, which means bigger batches, which means better GPU utilization.
The throughput numbers from the original vLLM release (mid-2023, LLaMA models): 14–24× higher throughput than HuggingFace Transformers, and 2.2–2.5× higher than HuggingFace TGI for single-output requests. Against the stronger research baselines (FasterTransformer, Orca), the SOSP paper reports 2–4× at the same latency, with the gap widening for longer sequences and larger models.
Paging's second gift: copy-on-write
Once cache lives in shared physical blocks behind a translation table, you inherit the other classic OS trick for free: sharing pages between processes until one of them writes.
Two serving patterns benefit directly:
- Parallel sampling — generating N samples from one prompt (common in coding assistants offering multiple completions). All N sequences share the prompt's KV blocks; each block carries a reference count, and only when a sequence writes into a shared block does vLLM copy it — block-level copy-on-write, exactly like
fork(). - Beam search — beams share not just the prompt but long common prefixes that diverge and die off continuously. With contiguous allocation this meant repeatedly copying large cache regions; with block tables it's reference-count bookkeeping.
The paper measures the savings: parallel sampling shares 6.1%–9.8% of KV memory on Alpaca-style short prompts and 16.2%–30.5% on ShareGPT's longer conversations, while beam search shares 37.6%–55.2% and 44.3%–66.3% respectively. The blog summarizes the effect as cutting memory usage of these decoding algorithms by up to 55%, translating into up to 2.2× more throughput.
The tradeoff: you just wrote a virtual memory subsystem in userspace
PagedAttention is not free, and it's worth being precise about the cost, because a follow-up line of research attacks exactly this point.
The vAttention paper (Microsoft Research, 2024) observes that PagedAttention "ends up changing the virtual memory layout of the KV cache from contiguous to non-contiguous," which has two consequences:
- Every attention kernel must be paging-aware. You can't drop in a stock kernel that assumes contiguous tensors; FlashAttention and FlashInfer needed dedicated paged variants. The serving framework takes on responsibility for address translation — bookkeeping the OS normally does for you.
- Translation has runtime cost. Dereferencing block tables inside the kernel adds overhead relative to contiguous access. vAttention reports up to 1.23× higher serving throughput by keeping the KV cache virtually contiguous and instead using CUDA's virtual memory management APIs to back it with on-demand physical pages — pushing the paging back down to where paging hardware already exists.
That's the honest framing of the design space: PagedAttention proved the waste was in the allocator, and its block-table approach became the industry default. Whether the translation layer belongs in the attention kernel (vLLM), in CUDA's VMM (vAttention), or somewhere else is still open. But the direction of travel is settled — nobody is going back to max-length contiguous slabs.
What this means when you operate an inference server
- Throughput problems are often memory problems. If your GPU sits at low utilization while requests queue, check whether the KV cache is capping your batch size before reaching for a faster kernel.
- Block size is a real tuning knob. Small blocks minimize internal fragmentation but fragment kernel memory access; large blocks waste tail space. vLLM's default of 16 tokens is a measured compromise, not a magic number.
- Decoding strategy changes memory economics. Parallel sampling and beam search went from memory-hungry to cheap because of block-level sharing — if you rejected N-sample generation for cost reasons pre-2023, the math has changed.
- The 2–4× headline number is workload-dependent. The gains come from fitting more sequences per batch, so short-output, small-model, latency-dominated workloads see less benefit than long-context, high-concurrency ones.