PagedAttention & KV-Cache Management
The KV-cache (not the model weights), usually decides how many requests a GPU can serve concurrently. A naive allocator reserves one contiguous slab of max_seq_len cache per request the moment it arrives; since real responses are far shorter than the maximum and lengths are unknowable in advance, 60–80% of that memory sits reserved-but-unused. PagedAttention (the algorithm at the core of vLLM) applies the oldest trick in operating systems: break the cache into small fixed-size blocks, map logical positions to physical blocks through a per-sequence block table, and allocate blocks only when tokens actually exist.
Why contiguous allocation fails
Three kinds of waste, mirroring classic memory management:
- Internal fragmentation: a request allocated 4096 slots that generates 350 tokens wastes 3746 slots for its entire lifetime.
- External fragmentation: variable-size contiguous slabs leave unusable gaps between allocations; free memory exists but no hole is big enough.
- No sharing: two requests with an identical 5k-token system prompt each store a full private copy of the same K/V tensors.
The cache is also append-only and per-token — a perfect match for paging, because a sequence only ever grows one token at a time at its tail.
The paged design
Physical HBM is carved into blocks of tokens each ( in vLLM). Each sequence holds a block table:
Allocation procedure:
- On admission, allocate blocks from the free list and prefill into them.
- Each decode step appends one token to the last block; only when it fills is one new block popped from the free list.
- On completion, all of the sequence's blocks return to the free list (subject to refcounts, below).
Blocks need not be contiguous — the attention kernel gathers K/V through the block table (one extra indirection, a few percent kernel overhead). Waste collapses to at most slots per sequence (the unfilled tail of the last block): for against a 4096-token reservation, worst-case waste drops from ~90% to under 0.4%.
Watch it run
The allocator on the trace below, block by block — admission, on-demand growth, a shared prefix, and the copy-on-write that keeps it safe:
PagedAttention — block tables, prefix sharing, copy-on-write
Physical HBM carved into 10 blocks of 4 tokens each, all free. Nothing is reserved in advance — this is the entire departure from the naive allocator, which hands each arriving request one contiguous slab of max_seq_len and hopes.
The KV-cache is append-only and grows one token at a time at the tail — which is exactly the access pattern paging was invented for.
KV-cache allocation the way an OS allocates RAM, on the worked trace above: blocks handed out on demand, a prefix shared between two requests by refcount rather than by copying, and a single block duplicated when one of them finally writes. The last step measures the claim that motivates the whole design — 256 realistic requests allocated both ways, contiguous against paged.
What to notice as you step:
- Growth is one block, on demand. A decode step that lands in an existing block's spare slot allocates nothing at all; only a full tail block triggers a single pop from the free list. There is never a re-reservation or a copy of the sequence.
- Only full blocks can be shared. A partially-filled block has no stable content hash (the next token would change it), so prefix sharing operates at block granularity, which is one reason is small.
- Copy-on-write copies exactly one block, not the prefix and not the sequence. That is what makes parallel sampling branches cheap.
- The final step measures the motivation: 256 requests with a realistic length mix, allocated both ways. Contiguous reservation leaves 72% of the cache reserved-and-untouched; paged allocation reaches 99.4% utilization and 3.5× the concurrent capacity on the same GPU.
Prefix sharing and copy-on-write
Because blocks are content-addressable units, identical prefixes can share physical blocks:
- Each full block is hashed by (prefix so far → block contents). A new request whose prompt matches an existing hash chain simply points its block table at the existing physical blocks and increments their reference counts — those tokens are never prefilled again. This is prefix caching (the big TTFT lever for RAG workloads).
- Shared blocks are read-only. If a sequence must write into a block with refcount > 1 (e.g. parallel sampling branches diverging), the allocator performs copy-on-write: copy that one block, decrement the original's refcount, write to the private copy.
- Freeing decrements refcounts; a block returns to the free list only at refcount 0. Evicted-but-hashed blocks can linger as a cache and be revived on a later hash hit (LRU eviction).
Worked trace
Block size (small for readability). Request A arrives with a 10-token prompt, then generates; request B arrives sharing A's first 8 prompt tokens:
physical blocks: P0 P1 P2 P3 P4
[t0–t3] [t4–t7] [t8,t9,·,·]
A block table: P0 P1 P2 ← 3 blocks, 2 slots slack
(t8,t9 = A-specific tokens)
B arrives, prompt = A's first 8 tokens + 3 new tokens:
hash(t0–t3) hit → share P0 (refcount 2)
hash(t4–t7) hit → share P1 (refcount 2)
3 new tokens → allocate P3: [u0,u1,u2,·]
B block table: P0 P1 P3
B's prefill work: 3 tokens instead of 11 (73% saved).
A generates t10, t11 → P2 fills; next token pops P4. B never sees it.
A finishes → P2,P4 freed; P0,P1 drop to refcount 1 (B still holds them).
Preemption: when blocks run out
Under load the free list can empty while sequences still need to grow. The scheduler must preempt a victim (vLLM picks most-recently-arrived first, so oldest requests finish):
- Swap: copy the victim's blocks to CPU RAM, restore later. Cost = PCIe transfer both ways; sane for long sequences.
- Recompute: drop the blocks and re-prefill the victim from its tokens when rescheduled. Counter-intuitively often cheaper for short-to-medium sequences, because prefill is compute-bound and fast while PCIe is slow.
Preemption is why a paged server degrades gracefully under overload (tail latency rises) instead of OOM-crashing.
What it buys, measured
| Metric | Contiguous allocator | Paged (B = 16) |
|---|---|---|
| Reserved-but-unused cache | 60–80% | < 4% |
| Concurrent sequences on fixed HBM | 1× | typically 2–4× |
| Shared system prompt (k requests) | k full copies | 1 copy + refcounts |
| Throughput (chat traffic) | 1× | 2–4× (more batch slots to fill) |
Gotchas
- Block size trades waste against overhead: smaller → less tail slack but bigger block tables and more gather overhead; 16 is the sweet spot vLLM converged on.
- Sharing requires identical token prefixes — one differing token (a timestamp in the system prompt, a user ID early in the template) breaks the entire hash chain after it. Put volatile content at the end of the prompt.
- Watch
gpu_cache_usageand preemption counters: a high preemption rate silently converts throughput into recompute work; the fix is more replicas, KV quantization, or shorter contexts.
Related concepts
- Optimizing LLM Inference: where paged cache management and prefix caching sit in the metric→lever map
- Inference Optimization & Serving: the KV-cache size formula and why the cache is the concurrency ceiling
- Continuous Batching: the scheduler that decides which sequences occupy the blocks each step
- Memory & Performance in CUDA: the HBM bandwidth hierarchy underneath all of this