← All papers

Efficient Memory Management for Large Language Model Serving with PagedAttention

Kwon, Li, Zhuang, Sheng, Zheng, Yu, Gonzalez, Zhang, Stoica · 2023 · SOSP 2023

EfficiencyRead on arXiv

Introduces PagedAttention, which applies OS-style virtual memory paging to KV cache management in LLM serving. Achieves near-zero memory waste and 2-4× throughput improvement. Powers vLLM, the most widely used open-source LLM serving framework.

Key Idea

LLM serving is bottlenecked by KV cache memory, not compute. Existing systems pre-allocate contiguous memory for each request's KV cache based on maximum sequence length, leading to massive internal fragmentation (allocated but unused memory) and external fragmentation (unusable gaps between allocations). PagedAttention borrows the virtual memory paging concept from operating systems: store KV cache in non-contiguous fixed-size blocks (pages) and map them through a page table.

How It Works

  • KV cache pages: Each page holds KV vectors for a fixed number of tokens (e.g., 16). Pages are allocated on demand as tokens are generated
  • Block table: Maps logical KV cache positions to physical memory blocks, just like an OS page table maps virtual to physical addresses
  • On-demand allocation: Pages are allocated only when needed, not pre-allocated for max sequence length
  • Copy-on-write sharing: For parallel sampling (beam search, multiple completions), sequences that share a common prefix share the same physical KV cache pages. Pages are only copied when one sequence diverges
  • Preemption and swapping: When GPU memory is full, lower-priority requests' KV cache can be swapped to CPU memory and brought back later

Why It Matters

  • Near-zero KV cache waste: Fragmentation drops from 60-80% in existing systems to <4%
  • 2-4× throughput improvement over FasterTransformer and Orca at equivalent latency
  • Powers vLLM: The most widely deployed open-source LLM serving engine, used in production by hundreds of companies
  • Enables larger batch sizes under the same GPU memory, directly improving cost-efficiency
  • The memory sharing mechanism makes beam search and parallel sampling nearly free in memory cost

Key Takeaways for Interviews

  • PagedAttention = OS virtual memory paging applied to KV cache, non-contiguous blocks + page table
  • Key insight: KV cache grows dynamically and varies per request, so pre-allocation wastes 60-80% of memory
  • Copy-on-write enables efficient beam search: shared prefixes share physical KV pages
  • In system design: PagedAttention is the serving-side complement to model-side efficiency (GQA, MLA reduce cache per token; PagedAttention manages whatever cache exists more efficiently)
  • vLLM stack: PagedAttention (memory) + continuous batching (scheduling) + CUDA graphs (compute) = production LLM serving