What KV cache problem does paged attention in vLLM solve, and which operating system idea does it use?
PagedAttention (vLLM) applies OS virtual memory to the KV cache: fixed-size pages, allocated on demand through per-request page tables. It removes fragmentation, so one GPU serves 2-4x more concurrent requests.
Picture a coffee shop where every customer used to reserve a whole long table on arrival, in case their group might grow big. Most groups stay tiny, so the shop sits half empty while people line up at the door. PagedAttention changes the rule. Each customer gets one small chair at a time and asks for another chair when a friend arrives. They return chairs as friends leave. The shop is the same, but many more groups fit. Two groups that share the same conversation can even share the same chairs at the start.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
PagedAttention is one of the most important systems contributions to LLM serving. Its central idea comes from OS virtual memory: do not reserve a contiguous max-size buffer for each request. Allocate fixed-size pages on demand, and use page tables to map logical positions to them.
With this design, the same GPU serves 2-4x more concurrent requests under realistic mixed-length workloads. Prefix sharing, copy on write for beam search and easy preemption come from the same abstraction at almost no extra engineering cost. The original Kwon et al. 2023 paper (arXiv 2309.06180) is one of the most cited LLM systems papers of the post-ChatGPT era. High-throughput serving now depends on paged KV cache.
The fragmentation problem
Naive serving allocates contiguous max_context KV cache buffers per request to avoid expensive resizing during generation. The tradeoff looks reasonable at first: simple allocation, fast kernels, no mid generation copies that would require synchronizing with running attention kernels.
The problem is that most requests don't fill the reservation. Average chats finish around 500 tokens; max_context is often 4096 or more. The 80-95% unused but reserved memory accumulates across concurrent requests until the GPU is mostly idle memory.
Llama-3 70B GQA with max_context = 8192 reserves ~2.7 GB per request. A serving fleet running 16 concurrent requests with average length 500 tokens uses only ~2.6 GB of real cache data but reserves ~43 GB. Of that, ~40 GB sits idle, blocked from any other workload by the contiguous buffer assumption.
Throughput per GPU ends up capped not by compute or even by total KV bytes actually used, but by reservation waste. The fix has to remove the waste without breaking kernel assumptions about contiguous K, V access patterns. That is the challenge OS virtual memory solved in the 1960s for CPU programs.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
# Conceptual: PagedAttention block lookup
# block_size = 16 (tokens per physical block)
# block_table[req_id]: List[int] (physical block indices in allocation order)
# kv_pool: a flat array of physical blocks shape [num_blocks, 2, num_layers, num_kv_heads, block_size, d_head]
def attention_paged(query, req_id, block_table, kv_pool, seq_len, block_size=16):
# For each logical position in [0, seq_len), fetch K, V via block table
keys, values = [], []
for pos in range(seq_len):
phys_block = block_table[req_id][pos // block_size]
offset = pos % block_size
keys.append(kv_pool[phys_block, 0, :, :, offset, :]) # K
values.append(kv_pool[phys_block, 1, :, :, offset, :]) # V
# ... standard scaled dot product attention with the gathered K, V
# Real kernels integrate the gather into the inner tiling loop
return attention(query, stack(keys), stack(values))| Aspect | Naive contiguous allocation | PagedAttention |
|---|---|---|
| Reservation per request | max_context sized buffer | On-demand pages |
| Wasted memory | 60-80% (typical) | <5% (intra page fragmentation only) |
| Concurrent requests on same GPU | Limited by max_context | 2-4x more |
| Prefix sharing across requests | Not supported | Native, share physical pages |
| Beam search / best of N | Duplicates cache | Copy on write blocks |
| Kernel overhead | None | Small (<5%) for page table lookup |
Real products, models, and research that use this idea.
- vLLM is the canonical PagedAttention implementation and underpins many production LLM API stacks.
- TensorRT-LLM ships a paged KV cache implementation with custom Hopper and Blackwell kernels.
What an interviewer would ask next. Try answering before peeking at the approach.
QHow does PagedAttention interact with beam search or best of N sampling?
Multiple beams share their common prefix's physical blocks via copy on write. When a beam diverges (new token), a fresh block is allocated and the divergent block's content is copied. Cache footprint of N beams is closer to common prefix blocks + (N × divergent length) blocks rather than N × full length.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Treating PagedAttention as a matmul speedup. It is a memory management optimization that raises concurrent capacity. The kernel does slightly MORE work because of page table lookups; the gain is system throughput, not per-request latency.
60 second bullets to scan on the way to the call.
The fragmentation problem under naive max context allocation
OS virtual memory as the source analogy
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.