What problem does paged attention (vLLM) solve, and what OS concept does it borrow from?
PagedAttention (vLLM) ports OS virtual memory to the KV cache, fixed size pages allocated on demand via per-request page tables, eliminating fragmentation and letting the same GPU serve 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 just one small chair at a time, asks for another chair when a friend arrives, and returns chairs as friends leave. Same shop, many more groups fit. Two groups even sharing the same conversation can 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 the most important systems contribution to LLM serving since transformers themselves. Its central idea is borrowed wholesale from OS virtual memory: stop reserving contiguous max size buffers; instead allocate fixed size pages on demand and use page tables to resolve logical positions.
The same GPU then serves 2-4x more concurrent requests under realistic mixed length workloads. Bonus capabilities (prefix sharing, copy on write for beam search, easy preemption) fall out of the same abstraction at essentially zero additional engineering cost. The original Kwon 2023 paper (arxiv 2309.06180) is one of the most cited LLM systems papers of the post-ChatGPT era, and by 2026 paged KV cache is essentially mandatory for high throughput serving.
This deep dive walks the fragmentation problem at the level of concrete byte counts, the OS analogy that motivates the design, the kernel side mechanics that make paged access cheap (under 5% overhead), the cascade of production capabilities that the abstraction enables, the tuning knobs that actually matter, and the 2026 adoption story across vLLM, TensorRT-LLM, SGLang, and LMDeploy.
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.
Walk a concrete number. Llama-3 70B GQA with max_context = 8192 reserves ~2.6 GB per request. A serving fleet running 16 concurrent requests with average length 500 tokens uses only ~2.5 GB of real cache data but reserves ~42 GB. Of that, ~39 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, which is exactly the challenge OS virtual memory solved fifty years ago 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 in 2026.
- 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 1 + (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 speed optimization for the matmul, it's a memory management optimization that increases concurrent capacity. The kernel actually does slightly MORE work due to page table lookups; the win 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.