PagedAttention: virtual memory for attention
Pre-allocation reserves worst-case contiguous slabs per request; most sit empty, and fragmentation strands the rest. PagedAttention borrows the OS answer: fixed-size blocks allocated on demand, a block table mapping logical positions to scattered physical pages, and copy-on-write for shared prefixes.
Fragmentation Kill
Reserved-but-unused KV (internal fragmentation) plus unallocatable gaps (external) historically wasted 60-80% of KV memory. Paging cuts waste to under 4%.
Block Tables
Each request carries a table: logical block i → physical block. Attention kernels gather K/V through indirection instead of assuming contiguity.
Copy-on-Write Forks
Two requests sharing a prefix share physical blocks; divergence triggers copy. Beam search and n-best sampling become nearly free in memory terms.
With 16-token blocks, internal waste is <15 tokens per request regardless of context length. vLLM's paper reports 2-4× throughput over naive allocation purely from this.
- Block size is a tuning knob: 16 tokens (vLLM default) balances kernel overhead against fragmentation.
- PagedAttention made beam search economically viable again — pre-paging, it was a memory multiplier.