Paged Attention and the KV Memory Manager

You know the KV cache is the memory bottleneck in LLM serving. What is less obvious is that, before 2023, most of that memory was never used. Kwon et al. measured production serving stacks (Orca-style systems built on FasterTransformer) wasting 60-80% of KV cache memory not to the cache itself but to how it was allocated: contiguous slabs, sized for the worst case, that sat mostly empty. PagedAttention is the fix, and the framing is the whole trick. Stop treating the KV cache as an array; treat it as virtual memory, with pages, a page table, and on-demand allocation. That single reframe is what let vLLM pack 2-4x more concurrent requests onto the same GPU.

This concept assumes you already know what a KV cache holds and why it grows linearly with sequence length. The question here is narrower and more interesting: given a fixed pool of HBM, how do you hand it out to hundreds of concurrent, variable-length sequences without wasting most of it?

Where a contiguous allocator bleeds memory

The pre-PagedAttention design gave each sequence one contiguous chunk of KV cache, sized to the maximum sequence length the server supports. If your server advertises 2,048-token contexts, every request reserves 2,048 tokens of cache the moment it is admitted, whether it ends up generating 20 tokens or 2,000. Three distinct wastes stack on top of each other, and they are worth separating because each has a different cause.

• Reservation waste. The slab is sized for the maximum, but the sequence is still being generated. A request that will eventually reach 2,000 tokens but is currently at token 50 has reserved 2,048 slots and filled 50. Those 1,998 slots are spoken for; no other request can touch them, even though this sequence may not need them for minutes, if ever.
• Internal fragmentation. The sequence finishes short of the maximum. It generated 512 tokens against a 2,048-slot reservation, so 1,536 slots were held for its entire lifetime and never written. This is unrecoverable within the request; you sized for a length that never arrived.
• External fragmentation. Because different requests reserve different max lengths (or the allocator rounds to fixed buckets), the free pool breaks into odd-sized holes. You may have 4 GB free in aggregate and still be unable to admit a request that needs 3 GB contiguous, because no single hole is large enough.

The measured result across real workloads: 60-80% of the KV cache pool is wasted, with only 20-40% holding live token state (Kwon et al., SOSP 2023). On a GPU where KV cache directly caps how many users you can serve concurrently, that is throughput thrown in the bin.

Fixed blocks and a per-sequence page table

PagedAttention borrows the operating system's answer to exactly this problem. An OS does not give a process one contiguous slab of physical RAM; it hands out fixed-size pages and keeps a page table mapping the process's contiguous virtual addresses to scattered physical frames. PagedAttention does the same for the KV cache.

The cache is carved into fixed-size KV blocks, each holding a small fixed number of tokens (vLLM's default is 16). A block is the unit of allocation: it is either free or assigned to exactly one logical position range of one sequence. Each sequence gets a block table, an array mapping its logical token positions to physical block numbers.

Sequence A, logical tokens 0..40, block_size = 16

logical positions   physical block
   0 - 15      ->      block 7
  16 - 31      ->      block 2
  32 - 40      ->      block 9   (partially filled: 9 of 16 slots used)

block table for A: [7, 2, 9]

Blocks are allocated on demand. When sequence A crosses from token 31 to token 32, the manager grabs one free block (block 9 here) and appends it to A's table. Nothing is reserved up front. A sequence at token 50 owns exactly four blocks (64 slots), not 128 blocks sized for some maximum. The only waste left is inside the last, partially filled block: at most block_size - 1 slots per sequence. With a 16-token block that is at most 15 wasted slots regardless of how long the sequence runs, which is why the paper reports total waste dropping to under 4%. Internal and external fragmentation vanish because every allocation is the same size; reservation waste vanishes because you allocate only as you fill.

Copy-on-write for shared prefixes

The page-table design pays a second dividend that a contiguous allocator cannot easily match: sharing. Two logical sequences can point their block tables at the same physical block. This matters for any decoding scheme that forks a common prefix.

Consider parallel sampling: one prompt, n independent completions (the "generate 4 candidates" pattern). Every candidate shares the identical prompt KV. Under contiguous allocation you either recompute or copy the prompt cache n times. Under PagedAttention, all n sequences' block tables point at the same physical prompt blocks. One copy of the prompt KV, referenced n ways.

The sharing is safe because of copy-on-write, again lifted straight from OS memory management. Each physical block carries a reference count. As long as a shared block is only read (the prompt is fixed), everyone reads the same block. The moment one sequence needs to write into a shared, partially filled block (the candidates start diverging at generation time), the manager copies that single block, points the writer's table at the private copy, and decrements the shared block's count. Only the one block at the point of divergence is duplicated; every block before it stays shared.

Beam search is the extreme case. Beams share not just the prompt but long stretches of generated tokens, and the shared structure changes every step as beams are pruned and forked. Block-level reference counting with copy-on-write expresses this naturally: forking a beam is copying a block table (cheap, it is a small array of integers), and physical blocks are freed automatically when the last beam referencing them dies. vLLM reports memory savings of up to 55% for these parallel and beam-search workloads from block sharing alone.

A worked estimate

Take a serving box that can hold 1,000 KV blocks after weights and activations. Requests average 300 generated tokens but the server supports 2,048-token contexts, and block size is 16.

Contiguous allocation reserves the full 2,048 tokens per sequence, which is 2048 / 16 = 128 blocks each. You fit 1000 / 128 = 7 concurrent sequences. Actual live state averages 300 / 16 ceil = 19 blocks per sequence, so 7 * 19 = 133 blocks hold real data and 867 are reserved-but-empty: about 87% idle at this operating point.

PagedAttention allocates on demand, so a sequence averaging 300 tokens holds about 19 blocks. You fit roughly 1000 / 19 = 52 concurrent sequences against the same pool. That is more than 7x the concurrency in this illustrative regime, though the paper's end-to-end figure lands at a more conservative 2-4x once you account for compute limits, prefill cost, and traffic that includes some genuinely long sequences. The launch benchmarks report up to 24x throughput versus a naive HuggingFace Transformers baseline, and 8.5-15x on parallel-completion workloads where block sharing compounds the packing win.

When it falls down

• Block size is a real tradeoff. Small blocks (say 8 tokens) minimise the wasted tail per sequence but multiply block-table length and per-block bookkeeping, and they hurt the attention kernel's memory-coalescing (more, smaller reads). Large blocks (say 64) coalesce better and shrink tables but bring back internal fragmentation inside that last block. 16 is a tuned compromise, not a law; the right value shifts with model and workload.
• The attention kernel must gather non-contiguous blocks. A textbook kernel assumes K and V are one contiguous tensor. PagedAttention breaks that assumption, so it needs a custom kernel that walks the block table and gathers scattered blocks, doing the QK dot products and value aggregation across block boundaries with careful shared-memory and warp-level reductions. That kernel is real engineering cost, and it is why you cannot bolt PagedAttention onto an arbitrary attention implementation for free.
• Bookkeeping overhead is not zero. Reference counts, the free-block pool, block-table updates every time a sequence crosses a block boundary, and copy-on-write triggers all cost CPU cycles on the scheduling path. On very short sequences the management overhead can outweigh the packing benefit, which is exactly where the gains are smallest.
• Interaction with prefix caching. Block-level sharing is the substrate that automatic prefix caching builds on: hash a block's contents plus its prefix, and an incoming request reusing the same system prompt can point at already-resident blocks. But the block boundary and hashing scheme constrain what can be shared (a shared prefix that does not align to a block boundary shares fewer blocks), and eviction has to respect reference counts so a hot shared prefix is not dropped out from under live sequences. The manager that made packing efficient becomes the manager you now have to make eviction-aware.

Further reading

• Efficient Memory Management for Large Language Model Serving with PagedAttention - Kwon et al., SOSP 2023; the original paper with the fragmentation taxonomy, block-table design, copy-on-write, and the 2-4x throughput measurements.
• vLLM PagedAttention design doc - a kernel-level walk-through of how the attention computation gathers non-contiguous blocks (marked as a historical document matching the original paper, ideal for understanding the mechanism).
• vLLM launch blog post - the practitioner introduction with the 60-80% waste figure, the under-4% result, the copy-on-write sharing explanation, and throughput plots versus HuggingFace.