Every serving framework before vLLM made the same quiet decision: a request's KV cache lives in one contiguous tensor. Deep learning frameworks want contiguous memory, so you allocate one chunk per request and move on. The vLLM paper (SOSP 2023) measured what that decision costs: in the systems they profiled, only 20.4%–38.2% of KV cache memory actually held token states. The rest was reservation and fragmentation. Their fix — PagedAttention — is a direct port of a 60-year-old operating systems idea, and it raised effective utilization to 96.3%.
Why the KV cache is the thing that limits your batch
Autoregressive decoding generates one token at a time, and each step is a matrix-vector multiply per request — memory-bound work that leaves GPU compute idle. The standard remedy is batching more requests together, which means the binding constraint is whatever limits how many requests fit in memory.
Weights aren't it: they're static. For a 13B model on an A100-40GB, the paper's breakdown is roughly 65% of memory for weights, close to 30% for KV cache, and a small remainder for activations. The weights never move; the KV cache grows token by token, per request, with a lifetime and final length nobody knows in advance. How you manage that ~30% decides your batch size, and your batch size decides your throughput.
And it's big. For OPT-13B, one token's KV cache is:
2 (key + value) × 5120 (hidden size) × 40 (layers) × 2 (bytes, fp16)
= 800 KB per tokenAt OPT's 2048-token maximum, a single request can need up to 1.6 GB. On a 40 GB card that's already shared with 26 GB of weights, a few tens of requests exhaust everything — and that's before any waste. The authors also note the trend making this worse: from A100 to H100, FLOPS more than doubled while maximum GPU memory stayed at 80 GB. Compute keeps outrunning capacity, so the memory side keeps getting more decisive.
Where 60–80% of the cache went
Because output length is unknown, pre-vLLM systems allocated each request's chunk at the maximum possible sequence length — 2048 slots whether the request would use 30 or 2000. The paper identifies three distinct wastes in this scheme:
- Reserved slots: space for tokens the request will eventually generate. Not pure waste — it gets used — but it's held for the request's entire lifetime, blocking other requests from it the whole time.
- Internal fragmentation: the gap between the maximum length you allocated and the length the request actually reached. You only discover this waste when the request finishes.
- External fragmentation: the gaps a buddy-style allocator leaves between differently-sized chunks. This memory is never usable for any request's tokens, and you know it up front.
Add it up and you get the profiling result above: token states occupied as little as 20.4% of KV cache memory. The vLLM announcement post states it bluntly — existing systems waste 60%–80% of this memory through fragmentation and over-reservation. Fine-grained batching schedulers (Orca-style continuous batching) fixed the compute waste of static batching, but they sat on top of the same allocator, so the memory waste survived.
The page table, relocated into attention
The OS solved exactly this problem decades ago: processes want contiguous address spaces, physical memory is fragmented, so you insert a translation layer. Virtual pages map to arbitrary physical frames through a page table.
PagedAttention is that, for KV cache:
- The KV cache is carved into fixed-size blocks, each holding the keys and values for a fixed number of token positions (16 by default).
- A request sees logical blocks, filled left to right as it generates.
- A per-request block table maps each logical block to a physical block anywhere in GPU memory, along with how many positions are filled.
- A new physical block is allocated only when all previous blocks are full.
The attention kernel then follows the block table during computation, gathering keys and values from non-contiguous physical blocks instead of assuming one flat tensor.
Each waste category falls out directly. Reservation disappears: a 7-token prompt gets two 16-slot blocks, not 2048 slots, and the request grows on demand. Internal fragmentation is capped at less than one block per sequence — at most 15 unused slots with the default size. External fragmentation is structurally zero, because every block is the same size; there are no odd-shaped gaps for an allocator to strand. That's the whole gap between 20.4% and 96.3%.
The block size tradeoff
Block size is a genuine knob, not a free parameter. Too small, and the kernel can't process enough positions in parallel to use the GPU well. Too large, and you've reinvented internal fragmentation — plus sharing (below) becomes less likely, since sequences diverge mid-block. In the paper's experiments, ShareGPT traces performed best anywhere from block size 16 to 128, but on Alpaca (short sequences), sizes beyond 32 degraded sharply because sequences were shorter than a single block. vLLM shipped 16 as the default: large enough for GPU efficiency, small enough that fragmentation stays trivial on most workloads.
What the indirection costs
Nothing is free: the PagedAttention kernel reads block tables, takes extra branches, and handles variable lengths. The paper measures 20–26% higher attention-kernel latency than FasterTransformer's highly optimized implementation. It doesn't matter end to end, because the overhead touches only the attention operator — not the linear layers that dominate — and the memory it recovers buys a much larger batch. vLLM still beats FasterTransformer and Orca by 2–4x throughput at the same latency, with bigger wins at longer sequences and larger models.
The part everyone forgets: pages enable sharing, not just packing
Page tables don't just defragment — they let two address spaces point at the same frame. Same here, and it's where the design gets its second payoff.
In parallel sampling (n candidate completions from one prompt), every sample's logical prompt blocks map to the same physical blocks. Each physical block carries a reference count; when a sample needs to write into a shared block — appending its first distinct token into the prompt's final, partially-filled block — vLLM does copy-on-write at block granularity: allocate a fresh block, copy one block's worth of data, decrement the refcount. Exactly the fork trick, applied to attention state. In the paper's experiments the prompt accounted for 12% of total KV memory, and sharing saved 6.1%–9.8% of memory on the Alpaca trace (16.2%–30.5% on ShareGPT).
Beam search shares far more aggressively, because beams share not just the prompt but every block up to their divergence point, and the sharing pattern mutates every step as beams are kept or killed — the paper compares it to an OS process tree under compound forks. Dead beams just decrement refcounts; blocks hit zero and return to the pool. Earlier systems had to physically copy a surviving beam's KV cache when candidates forked; vLLM copies at most one block. Measured savings: 37.6%–55.2% of memory on Alpaca, 44.3%–66.3% on ShareGPT. And when many requests share a common prefix — few-shot prompts — mapping the prefix once gave 1.67x throughput over Orca with a one-shot prefix and 3.58x with five shots.
Why this generalized
The production numbers matched the paper's: LMSYS swapped vLLM into FastChat for Vicuna and Chatbot Arena, saw up to 30x the throughput of their initial HuggingFace backend in internal benchmarks, and halved their GPU count while peak traffic grew 5x, serving 30K requests on an average day and 60K at peak.
The durable lesson isn't "use vLLM." It's that the KV cache was never a tensor — it's a dynamically growing, unpredictably sized, shareable allocation, which is to say it's process memory, and it wants the machinery process memory got in the 1960s: fixed-size pages, a translation table, demand allocation, refcounts, copy-on-write. Every major serving stack has since adopted paged or block-based KV management. When a resource's size is unknown at allocation time, contiguity is a tax; indirection is how you stop paying it.