PagedAttention

Definition

PagedAttention (Kwon et al., SOSP 2023; arXiv:2309.06180 — the algorithm behind vLLM) applies OS virtual-memory paging to the KV cache. Instead of one contiguous buffer per sequence sized to max context, the cache is split into fixed-size blocks (e.g. 16 tokens); a per-sequence block table maps logical tokens to physical blocks, which need not be contiguous and are allocated on demand. This near-eliminates fragmentation and enables cross-sequence sharing.

Key math / How it works

The waste it fixes. A contiguous per-request buffer sized to max context (say 8192) for a reply that turns out to be 200 tokens strands the other ~7992 slots (internal fragmentation) and chops free memory into holes too small for a new buffer (external fragmentation). Classic serving wasted 60–80% of KV memory this way.

Paging. Blocks are allocated as the sequence grows; waste is bounded to at most one partial block per sequence — < 4%. Any free block serves any sequence (no contiguity requirement → no external fragmentation).

Prefix sharing + copy-on-write. A shared prompt prefix (system prompt, few-shot examples) or the branches of beam/parallel sampling can point their block tables at the same physical blocks; on divergence a block is copied (copy-on-write), so only the differing suffix costs new memory. This slashes memory for high-fan-out sampling.

The attention kernel is modified to gather K/V from non-contiguous blocks rather than a flat buffer — the systems analogue of a gather-aware FlashAttention. Net effect: more sequences fit → larger decode batch → higher intensity → multi-fold throughput gains at equal latency vs. prior systems.

Why it matters

The KV cache is the serving bottleneck; PagedAttention is the allocation strategy that turned it from a 60–80%-wasted resource into a nearly fully-packed one, and it is the mechanism that makes continuous batching cheap (sequences can join/leave without contiguous reallocation). It is the core of vLLM and standard across modern serving stacks.

Taught in

• 12-llm-inference-systems — §4 the paging scheme, fragmentation modes, and prefix sharing.
• 13-gpu-engineer-roadmap — Project 5, a “toy vLLM” paged-KV decode loop.

See also

• kv-cache — the structure it manages
• continuous-batching — its package-deal partner
• flash-attention — the gather-aware kernel analogue
• prefill-decode · quantization-inference · gpu-memory-hierarchy
• gpu-systems-for-llms