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, kernel dereferences at compute, yielding 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, even if 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, return shelves when they leave, and two visitors reading the same introduction can share the same opening shelves. Same library, far more visitors fit, and 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 the most important systems contribution to LLM serving since the transformer itself. Its mechanic is straightforward (OS virtual memory ported into KV cache management) and its impact is dramatic: 2-4x more concurrent requests per GPU under realistic mixed length workloads.
Understanding it requires walking through the page structure, the block table, on demand allocation, and the kernel-level dereference. Each step adopts an OS-paging concept and translates it into a GPU-friendly form. Once you've seen it, the entire downstream cascade (prefix sharing, copy on write beam search, easy preemption, cleaner mixed batch serving) falls out naturally from the same abstraction with essentially zero additional engineering cost.
This deep dive walks all four mechanical pieces in order with concrete byte counts for a realistic Llama-3 70B workload, then closes with the gains, the tuning knobs, the tradeoffs that bind, and how PagedAttention composes with GQA, FlashAttention, and KV quantization in the 2026 production stack. By the end you should be able to reason about paged KV layout precisely enough to debug a kernel mismatch or tune block_size for a specific workload.
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), chosen to match GPU memory transaction granularity and typical decoding bursts.
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 set to fit the target concurrency at expected workload mix, typically 40-80% of remaining HBM after model weights and activation buffers.
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, 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.
scores = []
for p in range(seq_len + 1):
phys = block_table[p // block_size]
off = p % block_size
scores.append(q_new @ kv_pool[phys, 0, :, :, off, :].T)
# softmax + weighted sum over kv_pool[phys, 1, ...] similarly
return attention(q_new, gather_keys, gather_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 2026 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 the attention math is changed by paging, it isn't. 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.