Explainer
Reserve for the worst case, or page
A request’s cache grows one token at a time and nobody knows when it will stop. Every allocator has to answer that with a guess. Below, the same forty requests run against the same memory under the two answers serving has given, and you can watch what each guess costs.
The KV cache page charged every request a full context window, and said that was pessimistic. This is where the pessimism comes from. Before 2023 that is what engines actually did: on arrival, reserve prompt plus the longest possible answer, in one contiguous run, because the attention kernel wanted its keys and values laid out end to end. A request that answered in twenty tokens held its two thousand slots until it finished.
Orange is memory that is allocated and holding nothing. On the left it is the unreached tail of every reservation, and the free rows around it are holes too small for the next reservation to land in. On the right it is at most the unfilled end of one block per request.
Reservation wastes memory twice. The tail of every reservation that is never reached is internal fragmentation: allocated, empty, and unusable by anyone else until the request ends. The holes between reservations, each too small to fit the next request’s worst case, are external fragmentation: free, and still unusable. Kwon et al. measured existing systems at 20 to 40% of cache memory actually holding tokens. The left-hand run above lands in that range by itself.
Paging separates where a token lives from where its neighbours live. Memory is cut into fixed blocks of a few tokens each. A request gets blocks as it grows, from wherever they are free, and a small block table maps its logical positions to physical blocks, exactly as an operating system maps virtual to physical pages. Nothing has to be contiguous and nothing has to be guessed. The only waste is the unfilled end of each request’s last block, which is why the right-hand run sits above 90%, and why raising the block size pulls it back down.
The freed memory is where the batch comes from. Continuous batching keeps slots full but cannot create them; the cache page said batch size is capped by how many caches fit beside the weights. Paging is what changed how many fit. The same 2048 slots that held three reservations hold thirty paged requests, and the tokens-per-step figure follows. There is a second gift too: once cache is addressed by block, two requests can point at the same block, so a shared prefix is stored once, which is the mechanism the prefix cache page leans on.
What this model leaves out
All forty requests arrive at once, which flatters neither allocator in particular but does make the queue visible. With trickling arrivals the contiguous run would find its holes at different moments; the utilisation figure would not change much.
Paging is not free. The kernel gathers keys and values from scattered blocks instead of one run, and very small blocks cost more of that indirection; that is the real reason engines settle on sixteen rather than eight, and it is not in the utilisation number. Preemption is also modelled as a plain evict-and-recompute; engines can swap the blocks out to host memory instead, which the prefix cache page prices.
Slots are abstract. At Llama 3 70B rates each one is 320 KiB, so the 2048 here are 640 MB and a real deployment has hundreds of thousands of them. The proportions are what carry over, not the counts.