Source
Kwon et al. (2023), LIT-112 — ARXIV-2309.06180.
The fragmentation problem, and the borrowed idea
Serving batches many requests whose KV caches grow at different rates and finish at different times. Allocating each a contiguous block sized for the maximum length wastes most of it — the request that stops after 200 tokens still holds an allocation for 4,096 — and the free space left behind is scattered in pieces too small to reuse.
PagedAttention borrows the operating system’s answer: the cache is stored in fixed-size blocks, and a request’s blocks need not be contiguous, with an indirection table mapping logical positions to physical blocks. Internal fragmentation is bounded by one block, external fragmentation disappears, and the memory that is freed is immediately usable by anyone.
What the recovered memory is spent on
More concurrent requests, which is the whole point: throughput at a given latency is set by how many sequences fit in memory at once, so recovering the waste converts almost directly into batch size (SOTA-113).
The technique and the recommendation both come from LIT-112, which introduced PagedAttention as the memory manager of vLLM. Against FasterTransformer and Orca it measured 2–4× throughput at the same latency, and the gain grew with longer sequences, larger models and more complex decoding — the cases where the cache is a larger share of memory or more duplicated.
Two capabilities fall out of the indirection rather than being added: blocks can be shared between requests with a common prefix — a system prompt materialised once, not once per request — and copy-on-write makes parallel sampling from one prompt nearly free.
Condition
This is an inference practice, and the record should be explicit that it does not transfer to training: there is no KV cache to fragment in a training step, and the memory pressure there is activations and optimizer state, which the practices around SOTA-028 address instead.