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.
Detailed answer & concept explanation~6 min readEverything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Everything important, quickly.
Walk the fragmentation problem, the OS-paging analogy, the block_size/block_table mechanics, the kernel side dereference, the production gains, and the cascade of capabilities (prefix sharing, copy on write for beam search, easy preemption).
# 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.
- SGLang layers a RadixAttention prefix tree on top of paging for aggressive cross request reuse on Llama 4 and Mistral Large 3 workloads.
- LMDeploy and Triton Inference Server with the TRT-LLM backend both support paged KV cache.
- xformers ships a paged attention forward path interoperable with vLLM block tables.
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?
QWhy is 16 tokens a common block_size choice?
Don't say thisRed flags and common mistakes that signal junior thinking. Click to expand.
Red flags and common mistakes 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.
The night-before-the-interview bullets. Scan these on the way to the call.
Primary sources. Skim if you want the original framing.
Same topic, related formats. Practice these next.