If you’ve run a large language model at scale, you’ve hit the KV cache wall. What is PagedAttention? It’s the memory management technique introduced in vLLM that treats key-value cache like operating system virtual memory — dividing it into fixed-size blocks that can be allocated non-contiguously, shared across requests, and swapped to CPU or disk when GPU memory fills up. This single abstraction solves the fragmentation and pre-allocation problems that made high-throughput LLM serving impractical.
How PagedAttention works
Traditional KV cache allocation reserves a contiguous tensor for each request: batch_size × num_layers × 2 × num_heads × max_seq_len × head_dim. If you set max_seq_len = 4096 but most requests only use 512 tokens, you waste 87% of that memory. Worse, you can’t add a new request mid-batch if the contiguous space isn’t available, even if total free memory is sufficient.
PagedAttention replaces this with a block table per request. Each block holds a fixed number of tokens (typically 16 or 32) for all layers and heads. The GPU memory allocator hands out blocks from a global pool. A request’s logical sequence maps to physical blocks via a lookup table — exactly like page tables in virtual memory.
# Simplified block table structure
class BlockTable:
def __init__(self, num_blocks: int, block_size: int):
# Physical block IDs for each logical position
self.block_ids: list[int] = [-1] * num_blocks
self.block_size = block_size
def append_token(self, block_allocator) -> int:
logical_idx = self.num_tokens // self.block_size
if logical_idx >= len(self.block_ids):
self.block_ids.append(block_allocator.allocate())
elif self.block_ids[logical_idx] == -1:
self.block_ids[logical_idx] = block_allocator.allocate()
self.num_tokens += 1
return self.block_ids[logical_idx]During attention computation, kernels gather from these scattered blocks. The vLLM kernel uses a two-level indirection: the block table gives the physical block ID, and within each block, tokens are laid out contiguously. This preserves memory coalescing while enabling flexible allocation.
Why it matters for KV cache
The KV cache grows linearly with sequence length and batch size. For a 7B model with 32 layers, 32 heads, 128-dim heads, and 4096 context: each token consumes ~1 MB per request. At batch 256, that’s 256 GB — far beyond any single GPU.
PagedAttention delivers three concrete wins:
Memory efficiency. No more reserving for max_seq_len. Blocks are allocated on-demand as tokens are generated. A request using 200 tokens consumes 200 tokens worth of blocks, not 4096.
Prefix sharing. Multiple requests with the same system prompt or few-shot examples can point their block tables at the same physical blocks. This is copy-on-write at the block level — when a request diverges, new blocks are allocated for the suffix.
# Prefix sharing in block allocation
def fork_block_table(parent: BlockTable, divergence_idx: int) -> BlockTable:
child = BlockTable(0, parent.block_size)
# Share blocks up to divergence point
shared_blocks = divergence_idx // parent.block_size
child.block_ids[:shared_blocks] = parent.block_ids[:shared_blocks]
child.num_tokens = divergence_idx
# Remaining blocks allocated on demand
return childSwapping and preemption. Blocks can be evicted to CPU memory or NVMe when GPU pressure spikes, then fetched back when the request resumes. This enables fair scheduling across long and short requests without OOM kills.
Concrete example: serving a chat workload
Consider a chat endpoint with 4K context, serving 128 concurrent users. Requests arrive with varying prompt lengths (100–2000 tokens) and generate 50–500 tokens each.
Without PagedAttention: You statically allocate 128 × 4096 tokens of KV cache. At 1 MB/token, that’s 512 GB — impossible on 8×H100 (640 GB total, minus model weights). You’d cap batch size at ~16, leaving GPUs underutilized.
With PagedAttention (block_size=16):
- Average prompt: 800 tokens → 50 blocks
- Average generation: 200 tokens → 13 blocks
- Peak concurrent: 128 requests × 63 blocks = 8,064 blocks
- At 16 tokens/block × 1 MB/token = 16 MB/block → ~129 GB KV cache
- Fits comfortably with headroom for model weights and activation memory
The block allocator satisfies requests from a shared pool. When a request finishes, its blocks return to the pool instantly — no compaction needed. New requests grab whatever blocks are free.
Prefix sharing amplifies this. If all 128 requests share a 500-token system prompt (32 blocks), those 32 blocks are allocated once, not 128 times. Savings: 32 × 127 × 16 MB ≈ 65 GB.
Common misconceptions
Misconception: PagedAttention is just “chunked KV cache.”
Chunking splits the sequence into fixed segments but still requires contiguous allocation per chunk. PagedAttention’s block table enables non-contiguous allocation at the token-group level. This distinction matters for prefix sharing and fine-grained swapping.
Misconception: It only helps with long contexts.
Even at 2K context, fragmentation kills throughput when request lengths vary. A 100-token request followed by a 1500-token request leaves a 100-token hole that can’t fit the next 500-token request — unless you use paging.
Misconception: The attention kernel becomes much slower.
The gather overhead is real but small. vLLM’s PagedAttention kernel fuses the block table lookup into the attention computation. Benchmarks show <5% latency overhead vs. contiguous KV cache at same batch size — and the memory savings enable much larger batches, which improves throughput dramatically.
Misconception: You need vLLM to use it.
The concept is portable. TensorRT-LLM, SGLang, and other engines have adopted block-based KV cache management. The core idea — indirection via block tables — works anywhere you control the attention kernel and memory allocator.
Misconception: Block size doesn’t matter.
Block size trades off internal fragmentation against block table overhead. Smaller blocks (8–16 tokens) reduce waste for short sequences but increase table size and kernel launch overhead. Larger blocks (64–128) reduce metadata but waste more on partial blocks. 16–32 is the sweet spot for most workloads; profile your token distribution.
When to care (and when not to)
You need PagedAttention when:
- Serving multiple concurrent requests with variable lengths
- Running models where KV cache exceeds 20% of GPU memory
- Supporting prefix caching for system prompts or RAG contexts
- Implementing preemption, swapping, or priority scheduling
You can skip it when:
- Batch size = 1 (single-user, offline inference)
- All requests use identical, fixed sequence lengths
- Running on CPU-only where memory pressure is different
- Prototyping — contiguous allocation is simpler to debug
The n4n.ai gateway handles model routing across providers, but the KV cache strategy lives in the inference engine itself. If you’re self-hosting vLLM, SGLang, or TensorRT-LLM, PagedAttention (or its equivalents) is what lets you serve 10× more requests per GPU than naive allocation.
TL;DR: PagedAttention applies OS-style paging to KV cache. Fixed-size blocks + per-request block tables eliminate fragmentation, enable prefix sharing, and make swapping feasible. It’s the reason vLLM achieves high throughput on commodity GPUs — and why every production inference engine now copies the pattern.