Every sequence a language model is generating needs its own KV-cache (the running memory of every token's key and value vectors) — and nobody knows in advance how long a sequence will run. Reserve a block big enough for the worst case, for every sequence, and most of what you reserved sits empty the whole time.
Sequences of lengths [1, 4, 2] use 7 tokens total, allocated 12 slots.
Wasted: 5 of 12 — fragmentation 0.417
Three sequences, three very different lengths, sharing one small cache. Toggle between reserving a fixed block per sequence and allocating page by page, and watch how much of the cache is actually doing something.
The naive scheme reserves the same fixed block for every sequence, sized for the longest one it might ever need to hold — so the reservation never depends on how long the sequence actually turns out to be:
PagedAttention instead manages the cache the way an OS manages memory: fixed-size pages, allocated to a sequence only as it actually grows, one whole page at a time:
- — a sequence's actual length so far, in tokens.
- — the naive scheme's fixed per-sequence reservation.
- — the page size (tokens per page).
Whatever's allocated but not holding a real token is wasted, and that fraction of the whole cache is its fragmentation:
- Naive waste is unbounded by how the sequence actually turns out
A sequence that stops after 1 token still holds its entire reservation — the gap between what's reserved and what's used can be almost the whole block.
- Paged waste is capped at less than one page
The only place a paged sequence can waste anything is inside its own last, partially-filled page — at most tokens' worth, no matter how long the sequence ran before that.
The exact same three sequences, laid out both ways at once. The naive grid reserves a full, fixed block per sequence regardless of how much of it is ever touched; the paged grid only ever wastes inside each sequence's own last page — everything else is either in use or still free for someone else.
- Three sequences, lengths 1, 4, and 2 — 7 tokens total
Naive: each reserves 4 slots regardless of length, so slots allocated for 7 used — 5 wasted, fragmentation .
- The same three sequences, paged (page size 2)
- Length :
- Length :
- Length :
Total slots for the same 7 used tokens.
- Only 1 slot wasted
, fragmentation — the length-1 sequence's single half-empty page is the only waste left in the entire cache.
Two new sequences, lengths 3 and 1, arrive under the paged scheme (page size 2). How many slots end up wasted — allocated but unused?
This is exactly the trick vLLM's PagedAttention is named for: treat KV-cache slots the way an operating system treats physical memory pages, and let any sequence's logical cache be scattered across whatever physical pages happen to be free. What used to be wasted reservation becomes cache available for more concurrent sequences — which is where vLLM's throughput gains actually come from, not from a faster attention kernel. The next chapter asks a different question about that same serving loop: instead of generating one token per big-model call, can a cheap draft process guess several ahead and let the big model verify them all in one pass?