Navigation
⚡ Inference Systems· 12 min read

PagedAttention — The KV Cache Problem

Virtual memory for KV cache, fragmentation, and why GPU memory management mirrors OS page tables.

📄 PagedAttention / vLLM (Kwon et al., 2023)

paged-attentionkv-cachevllminference

TL;DR

PagedAttention brought OS-style virtual memory to GPU KV cache management. Instead of pre-allocating contiguous memory per sequence, it pages KV cache into fixed-size blocks — eliminating fragmentation and enabling near-perfect memory utilization. This single innovation unlocked 2-4× higher throughput for LLM serving.

The Paper

PagedAttention: Efficient Memory Management for Large Language Model Serving with PagedAttention (Kwon et al., 2023) — the paper behind vLLM, now the most widely deployed open-source LLM serving engine.

The key insight: GPU memory management for KV cache has the same fragmentation problem that OS memory management solved decades ago with virtual memory and paging.

How It Works

Traditional serving pre-allocates a contiguous chunk of GPU memory for each sequence’s KV cache based on the maximum possible sequence length. This wastes memory on three levels:

  1. Internal fragmentation — most sequences are shorter than the max length
  2. External fragmentation — freed memory blocks create gaps that can’t be reused
  3. Reservation waste — memory reserved for potential future tokens that may never be generated

PagedAttention fixes this with a simple idea: don’t allocate contiguous memory. Instead:

  • Divide KV cache into fixed-size blocks (e.g., 16 tokens per block)
  • Maintain a block table per sequence (like a page table in an OS)
  • Allocate blocks on demand as tokens are generated
  • Free blocks immediately when sequences finish

The attention kernel reads the block table to gather KV cache from non-contiguous memory locations — exactly like how a CPU reads virtual memory through page tables.

Why This Matters for Production

  • 2-4× throughput increase over naive pre-allocation
  • Near-zero memory waste — utilization goes from ~50% to ~98%
  • Enables larger batches — more concurrent requests on the same GPU
  • Copy-on-write — parallel sampling and beam search share KV cache blocks

What’s Still Unsolved

  • Page size tradeoff: 16-token pages create internal fragmentation; 1-token pages destroy GPU L2 cache hit rates due to pointer-chasing
  • Cross-layer compression: can we share or compress KV cache across layers?
  • FP4/FP8 quantized KV cache: reducing precision saves memory but may hurt quality
  • Distributed KV cache: when sequences span multiple GPUs, paging becomes a network problem

References