You don't know how long a reply will be, so the naive cache reserves each request's maximum slot — and short replies leave most of it empty. Fixed-size pages hand back the slack, so far more requests fit the same VRAM.
Last lesson the KV cache grew per token and per request. But there's a second, sneakier cost: the cache is variable-length — you don't know a reply's length up front. The naive fix reserves each request's maximum contiguous slot. A 4-token reply parked in a 2048-token slot leaves 2044 slots empty as padding — and the free pool fragments.
Paged attention (the idea behind vLLM) chops the cache into fixed-size pages — say 16 tokens — placed wherever there's room, exactly like an operating system's virtual memory. A sequence uses only as many whole pages as it actually fills.
Waste drops from "up to the max length per request" to "under one page per request." Same K/V, same output — only the layout changed.
TRY → Start on reserve max — every row is mostly hatched padding and waste reads ~75%. Flip to paged: the rows collapse to a short colored block plus a tiny page-tail, the rest of each row goes free, and waste drops to ~1% with ~4× more requests served. Now drag the page size slider up — bigger pages round each request up further, so waste creeps back.
Five requests, used = 512 + 37 + 1900 + 128 + 4 = 2581 tokens of real K/V.
Reserve-max gives each request the full 2048-token slot no matter how short it is: alloc = 5 × 2048 = 10,240. Waste = 1 − 2581 / 10,240 = 74.8% — three-quarters of the pool is padding.
Paged (page = 16) rounds each length up to whole pages with pagesFor(len, 16):
| request | len | ⌈len/16⌉ pages | alloc | tail waste |
|---|---|---|---|---|
| r1 | 512 | 32 | 512 | 0 |
| r2 | 37 | 3 | 48 | 11 |
| r3 | 1900 | 119 | 1904 | 4 |
| r4 | 128 | 8 | 128 | 0 |
| r5 | 4 | 1 | 16 | 12 |
alloc = 512 + 48 + 1904 + 128 + 16 = 2608. Waste = 1 − 2581 / 2608 = 1.0% — under one page per request. In a fixed 40,960-slot pool that lifts capacity from ⌊40960 / (10240/5)⌋ = 20 requests to ⌊40960 / (2608/5)⌋ = 78 — about 3.9× more.
Paging trades a tiny per-page rounding waste (at most page − 1 tokens per request) for the freedom to place pages anywhere, which also kills fragmentation. Smaller pages waste less but add bookkeeping; 16 is a common middle ground. The stored K/V and the model's output are identical either way — only the memory layout changed.
Reserving each request's maximum slot wastes most of it on padding. Paged attention allocates fixed pages on demand — a request uses only what it fills, so waste falls to under one page and the pool serves ~4× more requests, with zero change to the answer.