PagedAttention
Every token a model has already seen has to keep its key and value vectors resident for the rest of the request. The KV cache is therefore the single resource that decides how many users one GPU can hold — and the naive way to hand it out wastes most of it. This part measures the waste, replaces reservation with blocks and block tables, and follows the consequences all the way down to copy-on-write sharing, watermarks, and what a preemption actually costs.
The three kinds of waste
Why 100 GB of HBM holds 40 GB of cache
The KV cache sizing formula is Part 4's; the interesting question is what an engine does with the bytes once it has them. The pre-PagedAttention design is the obvious one: when a request arrives, reserve one contiguous span large enough for the maximum sequence it might ever produce, and hand the attention kernel that single pointer. It is simple, it makes the kernel's addressing trivial, and it wastes memory in three independent ways at once.
Reserved-but-unused. A request that reserves 2,048 slots but generates 180 tokens holds 1,868 slots hostage for its whole lifetime. On chat-shaped traffic this dominates everything else. Internal fragmentation is the sliver left at the end of the reservation that rounding to a convenient size made unusable. External fragmentation is the Swiss cheese that is left after sequences of different lengths come and go: the free memory may be large in total and still be split into holes no new sequence fits. The PagedAttention paper measured production traces where existing systems used only 20–38% of their KV memory; this page's own simulation lands on the same order of magnitude.
Below, the same 24-request stream runs twice: once with a 560-slot contiguous reservation per request, once with 16-token blocks allocated as the tokens actually arrive. Play it, then read the two ending percentages.
Two allocators, one request stream. The animation grows each request's real tokens from zero to its final length.
Blocks and block tables
Virtual memory, for attention keys and values
PagedAttention borrows the operating system's answer: stop pretending the cache is one object per sequence. Cut the KV cache into fixed-size blocks — 16 tokens is the vLLM default, and every choice of block size is a trade between table overhead and internal fragmentation. A sequence's logical tokens are grouped into logical blocks; a per-sequence block table maps each logical block to whichever physical block currently holds it. Nothing requires those physical blocks to be adjacent, or to arrive in order.
The attention kernel gathers the physical blocks a sequence owns and computes over them; the block table is just an array of 32-bit indices, so for a 16-token block on a model that caches 1 KB per token the table costs about 2 bytes per 32 KB cached — well under 0.1%. Allocation becomes a free-list pop, freeing becomes a push, and allocating tokens to grow a sequence never has to move anything. The cost shows up as non-contiguous memory access in the kernel, which is the last section's subject.
Click any token in the logical strip to follow its block table entry to a physical block, and move the block-size slider to watch internal fragmentation change.
Click a logical token. The highlighted logical block is traced through the table to its physical block.
Copy-on-write across beams and parallel samples
One prefix, many futures
Beam search, best-of-n sampling and any parallel-decoding scheme produce several continuations from the same prompt. The prompt's KV blocks are bitwise identical across all of them, so the engine points every sequence's block table at the same physical blocks and keeps a reference count per block. Cost of the shared prefix: one copy, regardless of how many samples ride on it.
The instant two samples diverge, a write lands in a shared block. The engine copies that one block — the classic copy-on-write — gives the writer a private block, drops the old block's reference count, and leaves every other sample pointing at the shared original. Only the partial final block of the prefix is ever at risk: earlier blocks are full and immutable. So the copy is always exactly one block, which is why beam search in a paged engine costs a few blocks per beam rather than a full prompt-sized cache. Write a token below and watch the refcounts.
Shared prefix blocks carry a refcount. A write to a shared partial block forks it; later writes append to the private copy.
Watermarks and the block pool
When free blocks run out
A serving engine runs one global block pool, shared by every resident sequence, plus a free list. Decode consumes one new block every 16 tokens per sequence (and prefill consumes the prompt's blocks up front), so the pool drains steadily even when no new request arrives. The engine watches the free-block count against two thresholds. Crossing the low watermark makes it shed load: preempt a resident sequence to reclaim its blocks. Staying above the high watermark lets it resume admitting. The band between them is hysteresis — without it, an engine would admit and evict at the same boundary every step, which is exactly the thrashing pattern in section 6.
The thresholds are small by design: vLLM's default low watermark is 4% of the pool and the high watermark 8%. Cross the low line and the engine must find a victim; the only question is what to do with that victim's cache.
Fewer pool blocks, or more concurrent sequences, pushes the free list toward the low watermark.
Recompute vs swap
Two ways to evict a sequence
When a sequence is preempted, its blocks are reclaimed. Its KV values are not free to reconstruct, so the engine chooses between two losses. Recompute throws the cache away and re-prefills the sequence from scratch when it is rescheduled: it pays 2 × params FLOPs per token, at prefill's compute-bound rate. Swap copies the KV blocks to CPU DRAM and back: it pays 2 × bytes over PCIe per token, plus a fixed pinned-buffer setup, at PCIe's bandwidth.
Both are roughly linear in sequence length, so the comparison is decided by their slopes and a constant. Recompute's per-token cost depends on the model and the prefill efficiency; swap's depends on how many bytes a token occupies and how fast the host link is. That means there is always a crossover length: below it recompute is cheaper, above it swap is — and moving the PCIe bandwidth slider moves the crossover. The model here is Llama 3.1 8B geometry at 40% of H100 SXM dense BF16 peak, with a 20 ms fixed swap setup.
Cost to evict and later restore one sequence, as a function of how many cached tokens it holds.
Thrashing and the preemption rate
The failure mode that looks like a slowdown but is a loop
If the working set of live sequences is slightly larger than the block pool, every admission forces an eviction and every eviction is followed by a re-admission. The scheduler runs continuously and makes no forward progress: GPU util stays high, throughput collapses, and tail latency explodes. This is thrashing, and it is the paging analogue of a cache miss storm.
The honest metric is not preemptions per second — that rises with load on a healthy system too. It is the preemption rate per request: how many times the average request is evicted over its lifetime. Engine dashboards expose it as preemptions or num_preemptions_total, and the operating rule is boring but effective: keep the pool large enough that the rate stays near zero at your target concurrency, and shed load at the gateway instead of letting the scheduler thrash. The chart below runs the same workload against shrinking KV pools.
Same arrival stream, varying total KV block count. Below a knee, requests are evicted repeatedly instead of finishing.
What paging costs in the kernel
The bill comes due in memory access, not in bookkeeping
Block tables are almost free as data. They are expensive as an indirection. A contiguous KV cache is a handful of large, aligned, prefetch-friendly reads; a paged cache is a gather over 16-token pages whose physical addresses are scattered by allocation order. Attention over the prompt becomes a loop over blocks, and the decode kernel must fuse the block-table lookup into the same kernel that computes $QK^\top$ — the original PagedAttention work writes a custom CUDA kernel for exactly this, and engines since have fused it into FlashAttention-style tiling so the table is read once per block rather than once per token. The cost is real but second-order: it is memory-level parallelism lost to scattered access, not extra bytes moved. Block size is the tuning knob — larger blocks amortise the table and improve coalescing, at the price of more internal fragmentation and coarser sharing.
Two practical constraints follow. First, block sizes must be powers of two and small enough that the last partial block is not wasteful, which is why 16 dominates. Second, the kernel's grid is sized by the number of blocks in the batch, so a batch of sequences with wildly different lengths produces a ragged, imbalanced grid; chunked prefill (Part 6) exists partly to smooth it. The thing that made PagedAttention worth a custom kernel is not that paging is free — it is that the memory it saves buys concurrency that more than pays for the scattered reads.
Cheat sheet
| Concept | Rule of thumb | Where it bites |
|---|---|---|
| Contiguous reservation | Reserves max sequence length per request; production traces use 20–38% of KV memory | Throws away concurrency you paid for in HBM |
| Block size | 16 tokens is the default; power of two | Small blocks: table and kernel overhead. Large blocks: internal fragmentation and coarse sharing |
| Block table cost | ~2 bytes per block per sequence; <0.1% of cached bytes at 1 KB/token | Negligible, but must be read inside the attention kernel |
| Copy-on-write | Only the partial last prefix block is shared-and-writable; a fork copies exactly one block | Beam search without it duplicates the whole prompt per beam |
| Watermarks | Low ~4% free, high ~8% free | Too narrow a band admits and evicts at the same boundary (thrashing) |
| Preemption rate | Preemptions per request; keep near zero at target concurrency | Rising rate with flat throughput means the pool is too small |
| Recompute vs swap | Recompute: 2 × params FLOPs/token. Swap: 2 × bytes/token over PCIe | Crossover length moves with PCIe bandwidth and model size |
Further reading
- Kwon, Li, Zhuang, Sheng, Zheng, Yu, Gonzalez, Zhang, Stoica, Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023.
- vLLM documentation, Paged Attention and conserving memory (watermark behaviour).
- Yu, Jeong, Kim, Kim, Chun, Orca: A Distributed Serving System for Transformer-Based Generative Models, OSDI 2022 — iteration-level scheduling, the context this part's memory manager feeds.