When an LLM serves a 2,000-token response to a prompt of 10,000 tokens, it does something that looks absurd from a memory-management perspective: it keeps every intermediate attention state for every token it has processed, for every request in flight, in GPU memory. This KV cache is not optional — without it, every generated token would require recomputing attention over the entire context. But it is enormous, it grows one token at a time, and nobody knows at request time how big any single request will get.
How a serving system answers that memory-management question determines its throughput more than almost anything else. The technique that settled the question for a generation of serving engines — PagedAttention, introduced in the vLLM paper — is a direct transplant from operating systems: virtual memory and paging, applied to GPU tensors. If you know how an OS manages pages, you already understand the core of modern LLM inference serving.
Why the KV cache is the bottleneck
Autoregressive decoding works one token at a time. To generate token N+1, the model needs the attention keys and values for all tokens 1 through N. Computing them fresh at every step would be quadratic; instead they’re cached. The cache size per token scales with model depth and width: for the 13B-parameter OPT model the paper’s authors computed roughly 800 KB per token (2 tensors × 5,120 hidden size × 40 layers × 2 bytes in FP16). A single 2,048-token request could therefore demand up to 1.6 GB — before batching.
The structural problem is that output length is unknown in advance. Earlier serving systems stored each request’s KV cache as one contiguous tensor, so they had to pre-allocate for the maximum possible sequence length. Profile the result and the waste is brutal: the paper measured that only 20.4%–38.2% of reserved KV cache memory actually held token states. The other 60–80% was internal fragmentation (reserved slots never used) and external fragmentation (free holes too small to reuse). Since batch size is capped by KV cache capacity, wasted memory directly means fewer concurrent requests and lower throughput.
Contiguous allocation also forecloses sharing: multiple samples of one prompt, beam search candidates, and conversations sharing a system prompt all hold identical KV data that separate allocations can’t reference.
PagedAttention: the OS metaphor, made literal
The PagedAttention paper applies the same fix operating systems have used since the 1960s: break the allocation into fixed-size blocks and maintain a page table. Each KV block holds the keys and values for a fixed number of tokens (16 in vLLM’s default configuration), and blocks for one request need not be contiguous in GPU memory.
The mapping is explicit: blocks are pages, tokens are bytes, requests are processes. Each request carries a block table — which physical blocks its logical blocks map to, plus a filled-count for the last block. Blocks are allocated only as tokens actually arrive, so worst-case waste per request is one partially filled block instead of a pre-reserved max-length buffer. The attention kernel takes the block table as an argument and gathers from non-contiguous memory directly — no compaction pass, which would be prohibitively expensive at this data scale.
There is a real cost: the paper’s microbenchmarks showed 20–26% higher attention kernel latency versus a tightly optimized contiguous-memory implementation, because of the extra indirection. End-to-end, it’s a massive net win — vLLM measured 2–4× higher serving throughput than the contemporaneous state of the art at equal latency — but it’s worth knowing the trade exists. Bigger blocks amortize the indirection better but increase per-request fragmentation; 16 is the empirical sweet spot.
Copy-on-write and shared prefixes
Once memory is paged, the rest of the OS toolkit follows naturally. When one request produces multiple output samples (parallel sampling), the prompt’s KV blocks are identical across the sequences — so they’re shared, with a reference count on each physical block. The moment two sequences need to write to the same shared block (each generating different tokens into the same partially-filled block), the classic copy-on-write dance triggers: allocate a new physical block, copy the data, decrement the reference count. Beam search works the same way — candidates share blocks and fork only when they diverge.
The same machinery extends across requests as prefix caching. If many requests begin with the same system prompt, the KV cache for that prefix can be computed once and reused by every subsequent request that matches it. What was a per-request prefill cost becomes a hash lookup.
In vLLM this is Automatic Prefix Caching (APC). Hash each block of tokens; if a block’s hash chain matches an already-cached prefix, skip recomputation and reuse the stored KV blocks. Two workloads benefit enormously: querying a long document repeatedly (the document is prefilled exactly once) and multi-turn conversation (each round reuses the entire prior history’s cache). Recent vLLM versions enable it by default; you can control it with enable_prefix_caching in the engine arguments:
from vllm import LLM
llm = LLM(
model="meta-llama/Llama-3.1-8B-Instruct",
enable_prefix_caching=True,
)One design detail worth respecting: eviction is prefix-aware, not LRU-per-block in the naive sense. Cached blocks are evicted in an order consistent with prefix structure — a prefix block is never evicted while a block derived from it remains cached — and eviction is recycling rather than copying, since a recomputation is always available as a fallback.
APC also has a real limitation to plan around: it only accelerates prefill. If your workload is dominated by long generation phases (long outputs, short prompts), prefix caching does little, and if incoming prompts share no prefixes, it does nothing. A retrieval workload with a giant shared document prefix is the ideal case; a traffic mix of unrelated short queries is the null case.
What happens when memory runs out
Every serving system eventually hits the wall: more active requests than the KV cache can hold. The two classical responses, both inherited from OS design, are swapping and preemption-recomputation.
Swapping evicts a request’s blocks to CPU RAM and copies them back when the request is rescheduled — direct virtual memory paging, with swap space bounded so it never exceeds GPU KV cache capacity. Recomputation is the alternative: drop the evicted KV cache entirely and re-run prefill over the full sequence when the request returns. This sounds wasteful, but modern GPUs recompute prefill fast enough that for moderate sequences it competes with swap latency — and avoids the PCIe copy traffic entirely. vLLM’s benchmarks show the two as comparable in the 16–64 block size range, and both are supported.
The scheduling policy that decides which request to evict matters as much as the mechanism. vLLM preempts the latest arrived requests first, on the theory that a request that just started has wasted little compute, whereas evicting a request deep into generation discards a large investment. Both swap and recompute are per-request all-or-nothing in vLLM — the paper notes this “all-or-nothing” policy is simpler and, in practice, sufficient.
Practical knobs that actually matter
- gpu_memory_utilization — the fraction of GPU memory vLLM may use for model + KV cache (0.92 in recent releases). Raising it buys more KV cache; too high and you OOM during CUDA graph capture or activation spikes. The remaining headroom must cover activations and framework overhead.
- max_model_len — the maximum sequence length the engine will accept. Lowering it from a model’s 128K ceiling to something your traffic actually uses frees KV cache for concurrency. This is frequently the single highest-leverage setting for throughput.
- Chunked prefill — in vLLM V1 engines this is enabled by default whenever possible. Long prompts are processed in chunks interleaved with ongoing decode work, which prevents a single 30K-token prompt from stalling every other request in the batch. Tune via
max_num_batched_tokens. - Block size — 16 is the default and rarely worth changing; smaller blocks waste more on fragmentation, larger ones underutilize attention kernels.
# Serve with the two settings that most affect KV cache economics
vllm serve meta-llama/Llama-3.1-8B-Instruct \
--max-model-len 16384 \
--gpu-memory-utilization 0.92 \
--enable-prefix-cachingThe deeper lesson
PagedAttention worked not because anyone invented a new data structure, but because someone noticed the problem was sixty years old. Dynamic allocation with unknown final size, heavy sharing potential, a hard physical capacity, and a need for graceful degradation under pressure — that’s textbook virtual memory. The serving layer’s job was recognizing the mapping and adapting the attention kernel to indirection.
That pattern keeps repeating as inference infrastructure matures. Scheduler-level batching (Orca’s iteration-level scheduling) and paged memory proved complementary, and most current engines — vLLM, SGLang, TensorRT-LLM — converge on some form of paged KV cache with prefix reuse. When you evaluate a serving stack, the questions that matter are the memory-management questions: how much of the KV pool is actually usable, can prefixes be shared across requests, and what happens to in-flight requests when the pool runs dry. If the answer to the first is “pre-allocated contiguous buffers,” you already know the throughput story.