Why contiguous KV allocation bleeds memory
During autoregressive decoding, every token a model has already seen contributes a key and a value vector per layer per head that must be kept around — the KV cache. Its size grows with the sequence length, and the naive way to store it is one contiguous buffer per sequence. But you do not know in advance how long a sequence will be, so a request that could reach the 4096-token context limit forces you to reserve room for 4096 tokens up front.
Most requests never get close. A chat reply might be 200 tokens; you reserved 4096. The other 3896 slots sit allocated but empty, unusable by any other sequence because they belong to a contiguous reservation. Across a batch this compounds: the GPU reports its KV memory as full while useful occupancy is a fraction of that. The vLLM authors measured real systems wasting 60–80% of KV memory this way — and that wasted memory is the hard cap on how many sequences you can serve at once, and therefore on throughput.
The operating-system analogy
This is exactly the problem virtual memory solved for processes fifty years ago. A program wants to believe it has one long contiguous address space; physical RAM is finite and shared. The OS reconciles the two with paging: it splits memory into fixed-size pages, lets a process’s logically contiguous addresses map to physically scattered page frames, and keeps a page table to record the mapping.
PagedAttention lifts this design directly. A sequence’s KV cache is the ‘address space’ it wants to see as contiguous. A KV block is the page — a fixed-size chunk holding keys and values for a small number of tokens (commonly 16). The block table is the page table, mapping each logical block to a physical block in the GPU’s KV pool. Because the mapping is indirected through the table, physical blocks need not be adjacent, and memory is handed out one block at a time, on demand, as tokens are generated.
Anatomy of a KV block
A block is the unit of allocation. If the block size is B tokens, one block for one layer holds a tensor of keys shaped [B, n_kv_heads, d_head] and an identically shaped tensor of values. The full KV memory is a large pool of these fixed-size slots, allocated once at startup and never fragmented afterward because every block is the same size. A sequence acquires blocks lazily: it starts with none, and each time it fills its current last block it requests one more. Block size B is the one tuning knob — small blocks minimize wasted tail and sharpen prefix sharing but inflate the block table and shrink each memory read; values around 16 balance the two for typical GPUs. A 200-token reply thus holds ⌈200 / 16⌉ = 13 blocks — not the 256 a 4096-token reservation would have pinned.
The block table: logical to physical mapping
Each running sequence owns a small block table: an array indexed by logical block number whose entries are physical block numbers into the shared pool. Logical block 0 is the sequence’s first B tokens, logical block 1 the next B, and so on; the table says where each one physically lives.
To locate the KV for token position t, the runtime computes logical_block = t // B and offset = t % B, looks up physical = block_table[logical_block], and indexes into that block at offset. The logical view is perfectly contiguous while the physical blocks are scattered arbitrarily across the pool. This indirection is the whole trick: it decouples the sequence’s apparent layout from where bytes sit, so the allocator can reuse any freed block for any sequence without ever needing a contiguous run.
Both fragmentation modes disappear
Internal fragmentation is space reserved for a sequence but not yet used. Under contiguous allocation it was catastrophic: reserve 4096 slots, use 200, waste 3896. Under paging it is bounded by the block size, because a sequence only holds blocks it has begun to fill and the sole waste is the unfilled tail of its last block. With B = 16 that is at most 15 token-slots — for a 200-token sequence, 8 wasted slots out of 208, under 4% versus over 95% before. The waste no longer scales with the context-length limit; it is a small constant per sequence.
External fragmentation is the other classic failure: free memory exists but is broken into pieces too small or scattered to satisfy a request needing a contiguous run — and contiguous KV allocation suffers badly, as sequences of different sizes start and finish at different times, carving the pool into a patchwork of holes. Paging eliminates it by construction: every block is the same size, so any free block satisfies any request and no free space can ever become unusable. Removing both modes, leaving only the bounded last-block remainder, is the deeper reason PagedAttention reaches near-zero waste.
Copy-on-write for shared prefixes
Because blocks are addressed indirectly, two sequences can point their block tables at the same physical block. That makes prefix sharing almost free. When you sample several completions from one prompt, or many requests reuse a long shared system prompt, the identical prefix tokens produce identical KV, so all those sequences can share the physical blocks holding the prefix — storing it once instead of N times.
The sharing is made safe with copy-on-write, again straight from OS paging. Each physical block carries a reference count, and reads by any number of sharers are fine. The moment one sequence needs to write into a shared block — because its generated tokens now diverge from the siblings — the runtime copies that single block, gives the writer a private copy, and decrements the original’s reference count. Only the one block at the point of divergence is copied; everything before it stays shared. For parallel sampling and shared-prompt workloads this cuts KV memory dramatically.