Attention never needed its keys and values to be contiguous, and that single observation turned 60 to 80 percent wasted cache memory into two to four times more concurrent users.
Why you'd careThe thing you have already noticed
You raised max_model_len from 8k to 32k because a handful of users needed it, and your server's concurrency dropped by a factor of four — for everyone, including the people sending 200-token questions. Or you watched a GPU sit at 30 percent utilisation while queueing requests it plainly had memory for. That is the failure paged allocation fixed. The older design reserved one contiguous slab per sequence, sized for the worst case the request might grow to, so memory was booked against generations that never happened and the leftovers fragmented into holes nothing could fit. Paging hands the cache out in small fixed-size blocks tracked through a per-sequence block table, so a sequence holds only the blocks it has actually filled.
In and outWhat goes in, what comes out
| In | A sequence's current token count, the number of new tokens about to be written, and the free-block pool — a stack of physical indices into one large pre-allocated tensor per layer, sized at startup from whatever VRAM the weights and peak activations did not claim. |
|---|---|
| Process | Allocate blocks on demand, one per block_size tokens, appending each physical index to the sequence's block table. Increment a reference count when a block is shared with a fork or a matching prefix. Hand the table to the attention kernel, which gathers keys and values through that indirection. |
| Out | A small integer block table per sequence mapping logical to physical blocks, a shared physical pool whose fragmentation is bounded by one partly-filled block per sequence, and shared blocks serving many concurrent requests from a single stored copy. |
The values are untouched — relocation is not transformation, and attention output is identical given the same reduction order. What is given up is contiguity, and with it the ability to run a stock attention kernel: every read now costs an indirection through the block table. That is why paged attention requires bespoke kernels, and why which block sizes you may choose depends on the attention backend you compiled against.
ConceptThe idea underneath
There is no machine learning in this stage. It is virtual memory applied to activations, and the one model-side fact that makes it legal is that attention needs its keys and values logically ordered, not physically adjacent. The kernel computes a weighted sum over positions; as long as it knows which position each stored vector belongs to, it does not care whether position 300 sits next to position 301 in DRAM.
Given that, the design follows operating-systems practice exactly. Physical memory is one large pre-allocated pool carved into fixed-size blocks holding block_size tokens each. Every sequence gets a block table: an array mapping its logical block index to a physical block index — a page table by another name. Blocks are allocated on demand as the sequence grows, so a request that generates 40 tokens holds three blocks rather than the 500 its max_tokens would once have reserved.
Two consequences follow. Internal fragmentation becomes bounded by block_size - 1 tokens per sequence instead of by the gap between reservation and reality: the PagedAttention paper measured 60 to 80 percent of KV memory wasted in the systems that came before it, and under 4 percent with paging. And blocks become shareable. Attach a reference count, point two sequences' block tables at the same physical block, and a system prompt shared by a thousand requests is stored once. Forking a sequence for parallel samples or beam search copies the table rather than the memory, and copies a block only when one branch writes into it — copy-on-write, borrowed intact from the operating system it came from.
At a glanceSee it
A sequence's block table maps logical positions onto scattered physical blocks other sequences can share.
The knobsHyperparameters and nuance
- block_size(vLLM, default 16; accepted values are backend-dependent) — tokens per block. Larger blocks mean fewer table entries and less indirection but up to
block_size - 1wasted slots per sequence, and by default coarser prefix sharing, since prefix hashes are computed per block. Smaller blocks reuse more finely and cost more bookkeeping per access. Recent vLLM decouples the two withprefix_match_unit, which sets prefix-match granularity independently of the physical block size. - gpu_memory_utilization(vLLM, default 0.92) — sets the total block count. The engine profiles one forward pass at startup and converts the remainder into blocks, so this single number decides your concurrency ceiling.
- num_gpu_blocks_override(vLLM) — pins the block count directly instead of trusting profiling. Useful when another process shares the card, dangerous because it bypasses the headroom check that keeps peak activations from causing an OOM under load.
- enable_prefix_caching(vLLM, on by default) — hashes each filled block so unrelated requests share physical blocks, not just forks of one sequence. This is what converts paging from a memory-efficiency win into a latency win.
- preemption(engine behaviour, not a parameter you set) — when the pool cannot satisfy a running sequence, vLLM V1 preempts it, drops its blocks and re-prefills it later. There is no mode switch:
--preemption-modeand itsswapoption belonged to the removed V0 engine and no longer exist. Your levers on preemption pressure aregpu_memory_utilizationandmax_num_seqs; under heavy fan-out, recompute can thrash.
EffectHow this stage moves the answer
Paging is value-preserving: the same keys and values at different addresses. What it enables is not perfectly output-stable. Cross-request prefix sharing means part of your prompt is not recomputed at all, and the boundary between reused blocks and freshly prefilled ones changes how the attention reduction is tiled — vLLM's own documentation has long carried the caveat that enabling prefix caching can change results in their lowest-order bits. At a near-tie between two candidate tokens that is enough to diverge. The more visible effect is scheduling. When the free-block pool runs dry, the scheduler preempts running sequences rather than failing them, and under sustained pressure a request can be preempted and restarted several times. From outside you see a stream that stalls for seconds mid-answer, or a client timeout that turns into a truncated response and a retry the user reads as the model changing its mind.
EvalsWhat it does to your measurements
Nothing here moves an accuracy score, so the metrics are throughput-side: achieved concurrency at a fixed p95 latency, output tokens per second at your SLO, preemption count, and the fraction of VRAM actually holding live KV rather than sitting reserved and empty. The classic silent invalidation is a load generator that sends the same prompt template to every synthetic user. With prefix caching on, every request after the first gets its prefill free, and the tokens-per-second figure you publish can be several times what diverse production traffic delivers. Randomise the prefixes, or run the sweep with prefix caching disabled to establish an honest baseline and then measure the caching win separately. The second trap is short runs: a benchmark that finishes before the block pool fills never triggers a single preemption, so it measures a regime your server leaves within minutes of going live.
Failure modesWhen it goes wrong
- Concurrency drops sharply the moment you raise the context limitsomething is still reserving per-sequence worst case, or
max_num_seqsrather than free blocks is what is bounding you. - Prefix hit rate is far below what your prompt lengths predictsharing is block-granular, so with
block_size32 a shared 1,000-token prefix reuses at most 992 tokens, and any divergence inside a block loses that whole block. - Requests are preempted and restarted repeatedly under steady loadthe free-block watermark is being hit constantly; the pool is too small for
max_num_seqstimes your average sequence length. - The server OOMs at startup after a config change
gpu_memory_utilizationleft no room for peak activation memory, ornum_gpu_blocks_overridewas set past what actually fits. - Throughput regressed after switching attention backendsthe new backend forces a different supported
block_size, which changes both fragmentation and sharing granularity.
PapersWhere this comes from
- Efficient Memory Management for Large Language Model Serving with PagedAttentionKwon et al., 2023 (arXiv 2309.06180). Established the OS-paging analogy for KV memory, measured 60 to 80 percent waste in prior serving systems against under 4 percent with paging, and reported 2 to 4 times the throughput at equal latency. This is the paper vLLM is built on.
- SGLang: Efficient Execution of Structured Language Model ProgramsZheng et al., 2024 (arXiv 2312.07104). RadixAttention extends block sharing from forks of a single request to a radix tree spanning all requests, which is what makes cross-request prefix reuse automatic rather than something you arrange.
- vAttention: Dynamic Memory Management for Serving LLMs without PagedAttentionPrabhu et al., 2024. Argues the same fragmentation win is available through CUDA virtual-memory APIs while keeping a contiguous virtual address space, so unmodified attention kernels still work — useful evidence that paging is one solution to fragmentation rather than the only one.