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?
Free · 2 AI evals / day
**PagedAttention** is the LLM-serving version of OS virtual memory. Four steps.
**Page structure.** GPU KV cache is one pool of fixed size physical blocks. A typical block holds 16 tokens of K and V at every layer and KV head. For Llama-3 70B GQA-8 fp16, ~5.2 MB per block.
**Per-request block table.** Each request owns a small int array mapping logical positions to physical block indices. Position p lives at `block_table[p // block_size]` at offset `p % block_size`.
**On-demand allocation.** As tokens generate, if the last block has room, write there. If full, fetch a new block from the free pool, append its index. A 200-token request uses 13 blocks. The old contiguous approach reserved 256, 95% waste.
**Attention at compute.** The kernel takes the block table as input and dereferences for each position. vLLM's kernel and FlashAttention-Paged fuse this into the tiling loop with <5% overhead.
Pay-off: 2-4x system throughput. Bonus capabilities (prefix sharing, copy on write beam search, easy preemption) fall out naturally. By 2026, paged KV is mandatory across vLLM, TensorRT-LLM, SGLang, LMDeploy.
Four mechanics, then the pay-off.
**PagedAttention** partitions GPU KV cache into fixed size physical blocks (typically 16 tokens). Each request has a block table mapping logical positions to physical block indices. Blocks are allocated on demand as the request grows and returned to a global pool when it completes.
The attention kernel takes the block table as input and dereferences for each attended position:
$$\text{phys\_block} = \text{block\_table}[p \,\text{div}\, \text{block\_size}], \quad \text{offset} = p \bmod \text{block\_size}$$
Modern kernels (vLLM's PagedAttention v2, FlashAttention-Paged) fuse this dereference into the inner tiling loop with ~5% overhead.
The result is 2-4x more concurrent requests on the same GPU because reservation waste is eliminated. Three bonus capabilities: prefix sharing across requests with common system prompts, copy on write beam search, and easy preemption via block table freeing.
Quick reference
TL;DR
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.
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.
Edge or on-device inference with batch one and a fixed-length context Single request and a known sequence length means no fragmentation gain; the block table overhead is pure cost.
Research prototyping with vanilla PyTorch attention No paged attention kernel path means a forced gather copy each step, defeating the purpose.
Workloads where every request truly uses the full max context Reservation waste is already minimal, so paging recovers little while paying full kernel side overhead.
MLA-based serving such as DeepSeek V4 deployments The cache is a small per-token latent; paging matters less and the latent layout may not slot cleanly into a block table.
Ultra-low-latency streaming with very small batches The 3-5% kernel overhead from page table dereferences can dominate when throughput is not the limiter.
Quick scan · 2–4 min
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.
Code example
python
# 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)
Side-by-side
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-world examples
Real products, models, and research that use this idea.
1vLLM with block_size=16 is the canonical PagedAttention deployment and runs many 2026 production LLM API stacks.
2SGLang adds a RadixAttention prefix tree on top of paged KV to maximize cross request prefix reuse, especially for agent workloads on Llama 4.
3TensorRT-LLM has a paged KV cache implementation with custom CUDA kernels for Hopper and Blackwell.
4FlashAttention 3 and the xformers paged path both expose paged attention forward kernels callable from vLLM and downstream frameworks.
5DeepSeek V4 deployments combine MLA's compact latent with paged allocation to push concurrent capacity per GPU higher than GQA-plus-paged stacks.
Interviewer follow-ups
What an interviewer would ask next. Try answering before peeking at the approach.
QHow does PagedAttention support beam search efficiently?
Sign in or go Pro to see the approach for this follow-up.
QWhy does FlashAttention need to be modified for paged inputs?
Sign in or go Pro to see the approach for this follow-up.
QWhat can go wrong with very small or very large block_size?
Sign in or go Pro to see the approach for this follow-up.
Don't say this
Red flags and common mistakes that signal junior thinking. Click to expand.
Most common mistake
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.