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.
Detailed answer & concept explanation~7 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 page structure, block table mechanics, on demand allocation, FlashAttention-fused dereference, throughput gains, and the cascade of capabilities (prefix sharing, copy on write beam search, easy preemption). Tune block_size deliberately. Compose with GQA, FlashAttention, and KV quantization for stacked gains.
# 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.
- TensorRT-LLM has a paged KV cache implementation with custom CUDA kernels for Hopper and Blackwell.
- FlashAttention 3 and the xformers paged path both expose paged attention forward kernels callable from vLLM and downstream frameworks.
- DeepSeek V4 deployments combine MLA's compact latent with paged allocation to push concurrent capacity per GPU higher than GQA-plus-paged stacks.
What an interviewer would ask next. Try answering before peeking at the approach.
QHow does PagedAttention support beam search efficiently?
QWhy does FlashAttention need to be modified for paged inputs?
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.
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.
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.