Walk through paged attention end to end, page table, block lookup, and how it enables higher throughput.
Walk through paged attention end to end: how is the KV cache structured, what's a 'page', what's the page table, and how does the attention kernel handle the non-contiguous memory at compute time?
PagedAttention is OS virtual memory for the KV cache: fixed size blocks, per-request page tables, on demand allocation, and kernel dereferences at compute. It yields 2-4x more concurrent requests.
Imagine a library where every visitor used to reserve a whole reading wing in case they ended up reading a lot. Most visitors only used one table. The library mostly sat empty while readers lined up at the door. PagedAttention hands each visitor a folder of receipts pointing to specific shelves. Visitors get shelves only as they need them and return shelves when they leave. Two visitors reading the same introduction can share the same opening shelves. The library is the same, but far more visitors fit. The librarian only does a tiny extra lookup each time someone wants a page.
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 mechanic is straightforward: OS virtual memory ported into KV cache management. Its impact is large: 2-4x more concurrent requests per GPU under realistic mixed length workloads.
Its parts are the page structure, the block table, on demand allocation, and the kernel-level dereference. Each part adopts an OS paging concept and translates it into a GPU-friendly form. The entire downstream cascade (prefix sharing, copy on write beam search, easy preemption, cleaner mixed batch serving) follows naturally from the same abstraction with almost no additional engineering cost.
Physical page structure
The GPU's KV cache memory is one flat pool of fixed size physical blocks. Each block holds block_size tokens of K and V at all layers, heads, and d_head. block_size is typically 16 (vLLM default). The vLLM paper found 16 large enough to use the GPU efficiently while keeping tail waste small.
Concrete sizing. For Llama-3 70B with GQA-8 in fp16 and block_size = 16, one block holds:
16 (tokens) × 80 (layers) × 8 (KV heads) × 128 (d_head) × 2 (K + V) × 2 (bytes/value) = 5.24 MB
Pool organization. The pool is allocated once at server startup as a contiguous CUDA tensor of shape [num_blocks, 2 (K/V), num_layers, num_kv_heads, block_size, d_head]. Free blocks are tracked in a simple free list managed by the host scheduler. Total pool size is usually all the HBM left after model weights and activation buffers. It is capped at a set limit (vLLM's gpu_memory_utilization, default 0.9 of the GPU).
Blocks aren't required to be contiguous in physical memory beyond their internal layout, and they aren't aligned to anything beyond GPU memory transaction granularity. This freedom is what makes the rest of the design work. Any request can claim any free block from the pool, and reclamation is just a free list append. The OS analogy is exact: blocks are physical pages in a flat physical memory.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
# Conceptual: paged attention for a single decode step
# Block table: List[int] of physical block indices for this request
# kv_pool: physical block storage,
# shape [num_blocks, 2 (K/V), num_layers, num_kv_heads, block_size, d_head]
def paged_attention_decode(q_new, k_new, v_new, block_table, kv_pool, seq_len,
block_size=16):
# Append new K, V to the cache: figure out which physical block
next_pos = seq_len
if next_pos % block_size == 0:
# Need a new physical block
new_block = allocate_block_from_pool()
block_table.append(new_block)
last_block = block_table[-1]
offset = next_pos % block_size
write_kv_to_pool(kv_pool, last_block, offset, k_new, v_new)
# Attention: dereference block table for every attended position
# Real kernels fuse this with FlashAttention tiling.
keys, values = [], []
for p in range(seq_len + 1):
phys = block_table[p // block_size]
off = p % block_size
keys.append(kv_pool[phys, 0, :, :, off, :])
values.append(kv_pool[phys, 1, :, :, off, :])
# standard scaled dot product attention over the gathered K, V
return attention(q_new, stack(keys), stack(values))| Step | Contiguous KV cache (naive) | PagedAttention |
|---|---|---|
| Request arrival | Reserve max_context buffer | Allocate empty block table |
| Token generation | Write into reserved buffer | Write into current block; allocate next on overflow |
| Memory waste | 60-80% (typical) | <5% intra-page only |
| Attention kernel | Standard FlashAttention | FlashAttention with block table dereference |
| Multiple requests | Each gets max_context buffer | Share a global block pool |
| Prefix sharing | Impossible (separate buffers) | Native (share physical blocks) |
| Throughput on same GPU | Baseline | 2-4x |
Real products, models, and research that use this idea.
- vLLM with block_size=16 is the canonical PagedAttention deployment and runs many production LLM API stacks.
- SGLang adds a RadixAttention prefix tree on top of paged KV to maximize cross request prefix reuse, especially for agent workloads on Llama 4.
What an interviewer would ask next. Try answering before peeking at the approach.
QHow does PagedAttention support beam search efficiently?
Beams share their common prefix's physical blocks via reference counting. When a beam diverges (a new token differs across beams), the diverging block is copied (copy on write) and the divergent suffix uses unique blocks. Memory footprint for N beams is roughly common_prefix_blocks + N × divergent_suffix_blocks, much smaller 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.
Believing paging changes the attention math; it does not. PagedAttention is purely a memory layout abstraction; the math is identical to standard attention. The pay-off is throughput per GPU, not per-request latency.
60 second bullets to scan on the way to the call.
Physical block structure, fixed size holding block_size tokens of K and V
Per-request block table mapping logical positions to physical blocks
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.