Paged Attention

A KV cache has to be contiguous, and nobody knows how long a sequence will get, so servers reserve the maximum up front. Most of that is never used. Paged attention borrows virtual memory: the cache lives in fixed-size blocks that need not be adjacent, allocated as the sequence actually grows.

Split the KV cache into blocks of a fixed number of tokens and keep a per-sequence block table, the way an operating system keeps page tables. Internal fragmentation falls to at most one block per sequence, and blocks can be shared outright — two requests with the same prompt prefix point at the same physical blocks rather than each holding a copy.

Reserving for a maximum length L wastes L − n per sequence at length n. With block size B the waste is bounded by B − 1 tokens regardless of L, so utilisation stops depending on how badly the maximum was guessed. Copy-on-write on shared blocks makes prefix reuse cost one block rather than the whole prefix.