What problem does PagedAttention solve and why does block-based allocation enable larger batches?

During generation, a transformer keeps a **KV cache**: the keys and values for every token seen so far, read back on each decode step. The cache grows as the answer gets longer, and nobody knows in advance how long an answer will be. The naive fix is to reserve, up front, enough contiguous memory for the longest answer the model could ever produce. If a request only generates 50 tokens but you reserved space for 4000, the other 3950 slots sit allocated but untouched. That waste is called internal fragmentation, and across many requests it can swallow most of the GPU. PagedAttention borrows the operating-system idea of virtual memory. It chops the cache into small fixed-size blocks, typically 16 tokens each, and keeps a per-request block table that maps logical token positions to physical blocks. Blocks are handed out only when a token actually arrives, and returned when the request finishes. Because almost no memory sits reserved but empty anymore, the freed space holds more concurrent requests. A bigger batch means each expensive read of the model weights from memory is shared across more tokens, so throughput climbs sharply on the very same GPU.

**PagedAttention** is a KV-cache memory manager, introduced in vLLM, that stores the cache in fixed-size blocks instead of one contiguous slab per request. The pathology it kills is internal fragmentation. Naive serving reserves contiguous memory sized for the maximum possible completion length, per request. Most requests finish far shorter. So the reserved but untouched tail is dead weight. In practice this wastes 60 to 80 percent of KV memory, so the GPU looks full while most cells are empty. The fix is exactly OS virtual memory. The cache is sliced into fixed blocks, often 16 tokens each. A per-request block table maps logical token positions to physical block addresses. Blocks are allocated on demand as tokens are generated, and freed when a request completes. Physical blocks need not be contiguous, so external fragmentation disappears too. Reclaimed memory becomes spendable on more concurrent sequences. Achievable batch size rises roughly 2 to 4 times on the same hardware. Decode is memory bandwidth bound, dominated by streaming the model weights from HBM each step. A larger batch amortizes that one weight read across more tokens. Higher utilization turns directly into higher throughput.