ML//inference//KV cache//PagedAttention

2026-10-28

PagedAttention is a way of storing the KV cache of a serving engine in small fixed-size blocks scattered through GPU memory, with a table per request that lists which blocks hold its tokens, and it is used by vLLM and most servers since to fit many more conversations on one GPU. It borrows the idea of pages from an operating system's virtual memory: a request sees one continuous cache, and the engine hands it a new block (16 tokens by default in vLLM) only when the previous one is full.

The problem it removes is reservation. Before it, an engine reserved for each request a contiguous region large enough for the longest answer it might produce, because it could not know in advance where generation would stop. Most of that reserved space was never written, and the gaps between regions could not be reused, so a GPU with free memory refused new requests.

Memory is spent on tokens that exist, not on tokens that might. Less waste means a larger batch, and in the decoding phase a larger batch is nearly free throughput, because every request in it shares the same pass over the weights.

The attention kernel has to read keys and values from non-contiguous blocks, which costs a little indirection; the paper that introduced it measured two to four times the throughput of earlier servers at the same latency, almost all of it from the larger batches.

Blocks can be shared. Two requests with the same beginning point to the same blocks, which is how prefix caching and parallel sampling of several answers avoid storing the shared part twice; a block is copied only when one of them writes into it.

It works together with continuous inference batching: requests join and leave the batch at every step, and their blocks are allocated and freed as they go.