History Problem Core Idea Paging Sharing vLLM Results Impact Deep Dive Quiz
Interactive Paper Explainer

Virtual Memory for the KV Cache
PagedAttention

A visual, step-by-step guide to the serving breakthrough that borrowed 60 years of operating-system wisdom — paging the KV cache like RAM — and built vLLM, the inference engine that made GPU serving cheap.

Start Learning Read the Paper ↗
2–4×
Throughput Gain
<4%
KV Cache Waste
SOSP
First LLM Paper There
2023
Year Published
History

Serving Meets 1961

The ideas are older than deep learning: virtual memory, paging, and copy-on-write — applied to the KV cache.

1961–present
Virtual memory (Atlas → Linux)
Operating systems solved "programs of unpredictable size, limited RAM" with pages, page tables, and copy-on-write decades ago.
2022
KV cache becomes the bottleneck
Attention serving stores per-token K/V states; the cache grows with traffic and sequence length, fragmenting GPU memory.
2023 · Sep
🚀 PagedAttention + vLLM (Kwon et al., UC Berkeley)
KV cache in fixed-size blocks with a block table — near-zero waste, flexible sharing, 2-4x throughput. First LLM paper at SOSP, a systems venue.
2023 →
The open serving era
vLLM becomes the default open inference engine; paged KV management spreads to TensorRT-LLM, SGLang, and beyond.
The One-Sentence Idea

Treat the KV cache like RAM: fixed-size physical blocks + a per-request page table + logical-to-physical mapping. Requests never need contiguous memory, fragmentation drops from catastrophic to <4%, and identical prefixes (a system prompt seen by a thousand users) become shared physical blocks.

🧭 Pairing
FlashAttention fixed attention compute; this fixes attention memory at serving time.
Chapter 01

The Fragmentation Tax

Before PagedAttention, serving systems reserved contiguous KV memory per request — and paid for it three ways.

🧩
Contiguous Reservation Fails
  • Reserve by maximum possible length: 80%+ of the cache sits idle for short generations — massive internal fragmentation
  • Reserve small and grow: external fragmentation — GPU memory shatters into unusable gaps between live requests
  • Same shared prefix (long system prompt) stored again per request — redundant duplication
  • Result: tiny effective batch sizes, because memory — not compute — gates how many requests fit
📘
Paged Blocks Fit Anywhere
  • KV states stored in fixed-size blocks (like 4KB pages), allocated on demand
  • Each request keeps a block table: logical block → physical block (like a page table)
  • Attention kernels gather K/V across non-contiguous blocks
  • Near-zero waste: fragmentation <4% versus 60-80% in prior systems
Analogy — Hotel Rooms vs Bunk Beds

Contiguous reservation books every guest a 12-room suite in case their family shows up — most rooms stay dark. Paged allocation gives each guest bunk beds as needed, wherever they exist: a guest's party may sleep on three floors, tracked by a ledger. Occupancy soars; nobody cares about floors.

Chapter 02

The Block Table

How one request's KV cache becomes a list of pointers — and why that's enough.

logical blocks [0, 1, 2, …] → block table → physical blocks (anywhere in GPU memory)
block size
Fixed, small
e.g., 16 tokens' KV states per block — the "page size" of the cache.
block table
Per request
Maps the request's logical sequence to its physical blocks — indirection, the OS's classic move.
on demand
Allocation
A new block is allocated only when the generation crosses a block boundary.
gather kernel
Attention
PagedAttention computes attention by walking the block table — correctness independent of layout.
Interactive Demo — Fragmentation Visualizer
Chapter 03

Growing a Sequence

Follow one request generating tokens: new blocks appear anywhere, the table extends, memory never fragments.

Interactive Demo — Generation with a Block Table
Chapter 04

Prefixes Shared, Copies Lazy

The bonus that only indirection enables: many requests pointing at the same physical blocks.

Shared Prefixes
  • Beam search & parallel sampling: candidates share the whole prompt's KV — one physical copy, multiple block-table entries
  • A long system prompt under a thousand requests: shared blocks instead of a thousand duplicates
  • Copy-on-write semantics: shared blocks are read-only until one request diverges — then, and only then, a private block is allocated
Memory Savings Multiply
  • Prefix sharing cuts memory up to 55% in beam-search-style workloads (parallel decoding)
  • Shared-prefix workloads cut up to ~3x in the paper's evaluations
  • Freed memory converts directly into bigger batches — throughput, not just efficiency
Interactive Demo — Copy-on-Write Divergence

Two requests share a prompt, then one branches. Watch which blocks fork.

Chapter 05

vLLM — The Engine

PagedAttention is the kernel; vLLM is the serving system built around it.

🧮 KV cache manager
Block allocator + per-request tables; near-zero waste and on-demand growth.
🔀 Continuous batching
Requests join/leave the batch at token boundaries — no waiting for a generation group to finish.
⚡ Paged kernels
Attention and copy kernels natively traverse block tables (CUDA + custom ops).
🚫 Preemption & swapping
Under memory pressure, requests can be recomputed or swapped out — OS eviction logic, again.
Chapter 06

Throughput Proof

Same GPUs, same latency budgets, more requests served — measured against the state-of-the-art systems of the day.

THROUGHPUT
2–4×
vs FasterTransformer and Orca at same latency (LLaMA-13B & 13B-class workloads)
WASTE
<4%
KV cache memory wasted vs 60-80% in contiguous-reservation systems
PREFIX SHARING
−55%
memory in parallel-sampling workloads; up to ~3x with long shared system prompts
VENUE
SOSP
first LLM-inference paper at a premier *systems* conference — a field-crossing event
Interactive Demo — Batch Size Machine

Memory freed by paging converts to concurrent requests. Toggle memory mode; watch throughput follow.

Legacy

Impact — Serving Becomes Systems

PagedAttention pulled LLM inference into the operating-systems tradition — and never left it.

🌍 vLLM everywhere
The default open serving engine for years; the codebase became a shared industry foundation.
🧠 Paged KV as a pattern
TensorRT-LLM, SGLang and successors adopted paged cache management — the idea is now table stakes.
💰 The cost curve
2-4x throughput translates directly into per-token price — part of why inference got cheap.
🔬 Systems-ML convergence
SOSP acceptance signaled the field: inference problems ARE OS problems — scheduling, allocation, eviction.
⚠️ What it did NOT solve
Compute per token (FlashAttention/quantization's lane), multi-GPU tensor parallelism details, and request-level scheduling fairness.
🧭 Study path
Attention compute: FlashAttention → this page → token-level speedups: Speculative Decoding.
Deep Dive

Indirection Is the Universal Unlock

The paper's technique is 60 years old. The lesson is why nobody applied it sooner — and what else it unlocks.

🔗
The Contiguity Habit
  • ML systems assumed tensors must be contiguous for kernel efficiency
  • So memory managers pre-reserved big contiguous slabs — and inherited 1960-style fragmentation
  • Gather-based kernels looked "inefficient" — until measured against the waste they replace
  • Domain pressure ("this is an ML problem") hid the isomorphism to paging
🔓
What Indirection Buys
  • Any-layout allocation: fragmentation → near zero
  • Sharing + copy-on-write: dedup at no correctness cost
  • Eviction/swapping become possible (requests as pages)
  • Each capability composes: sharing + preemption + batching interact multiplicatively in vLLM
Interactive Demo — The Isomorphism Mapper

OS concept → KV-cache counterpart. Click through four pairs.

Verdict

PagedAttention's meta-lesson: when a new field hits an old constraint, inventory the old solutions before inventing new ones. The KV cache's unpredictable growth, scarcity, and sharing needs are a re-run of 1961's virtual-memory problem — and the transfer cost was nearly zero once someone looked. The 2-4x that followed wasn't a cleverer model; it was a correct classification of the problem.

Test Yourself

Quick Quiz

Check your understanding of the key concepts from the PagedAttention paper.

Reference

Key Takeaways

Everything you need to remember about this paper.

✅ KV cache in fixed-size blocks + per-request block tables = virtual memory for inference.
✅ Fragmentation falls from 60-80% (contiguous reservation) to under 4%.
✅ Prefix sharing via block-table aliasing: up to 55% memory savings in parallel decoding; copy-on-write on divergence.
✅ vLLM: 2-4x throughput vs prior SOTA serving systems (FasterTransformer, Orca) at equal latency.
✅ Freed memory becomes bigger batches — paging converts efficiency into throughput.
✅ First LLM paper at SOSP: inference problems are operating-systems problems.