PagedAttention: The vLLM Paper

Paper: Efficient Memory Management for Large Language Model Serving with PagedAttention (Woosuk Kwon, Zhuohan Li et al., SOSP 2023, UC Berkeley et al.)

vLLM is a must-read systems paper in model deployment: it ports the virtual-memory paging idea from operating systems into GPU memory management, solving the most painful problem in LLM inference — wasted KV cache memory — and, combined with continuous batching, lifts throughput by 2–4×. Nearly every LLM inference framework today (TGI, TensorRT-LLM, SGLang, and in-house engines) absorbs its design.

Before reading this, it helps to know LLM Inference Optimization (KV cache, the prefill/decode phases) and Model Serving (batching concepts); this walkthrough answers "why does vLLM look the way it does," and the hands-on companion is the vLLM case study.

Background and Motivation: The KV Cache Is LLM Inference's Hidden Bottleneck

When an LLM generates autoregressively, every new token must attend over all previous tokens. To avoid recomputing, the system caches each generated token's Key/Value vectors in GPU memory — the KV cache. The problems:

• It grows dynamically with the sequence: every generated token adds KV vectors, and the final length is unknown in advance;
• It dominates per-request memory: for a 13B model on an A100 (40GB), weights take about 65%, the KV cache about 30%, and activations only a slice (paper Figure 1);
• Requests compete for it: each request in a batch holds its own KV cache — the bigger the batch and the longer the sequences, the tighter memory gets.

Traditional systems (FasterTransformer, Orca) respond by pre-allocating one contiguous block of memory per request based on its max_length. The paper's measurements are grim: under this static allocation, only 20.4%–38.2% of KV cache memory actually stores token state — the rest is wasted.

Existing systems: contiguous pre-allocation per request's max length (three kinds of waste)
┌───────────────────────────────────────────────────────┐
│ Request A (pre-allocated 2048 tokens, generated 512)  │
│ ████████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░  ← internal  │
│                                              frag.    │
│ Request B (pre-allocated 2048, generation not begun)  │
│ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░  ← reserved │
│ Request C (length differs from A/B)                   │
│ ██░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░  ← external  │
│                                              frag.    │
└───────────────────────────────────────────────────────┘
Measured memory utilization: only 20.4%–38.2%

These three kinds of waste (reserved / internal fragmentation / external fragmentation) directly cap batch size — and batch size is the throughput ceiling of an LLM service. Getting the KV cache right is far cheaper than buying more GPUs.

The Core Idea: PagedAttention — Virtual Memory, Reborn for LLMs

The paper's insight is plain but deep: a KV cache that "grows dynamically, has unknown length, fragments, and needs sharing" is exactly the same problem as process memory in an OS — and operating systems solved it 60 years ago with paging. Hence PagedAttention: chop the KV cache into fixed-size blocks, allocate on demand, and record each request's block mapping in a block table.

PagedAttention: KV cache split into fixed-size blocks, stored non-contiguously

 GPU block pool
 ┌────┬────┬────┬────┬────┬────┬────┬────┐
 │B0  │B1  │B2  │B3  │B4  │B5  │B6  │B7  │  each block = KV for 16 tokens
 ├────┼────┼────┼────┼────┼────┼────┼────┤
 │A-1 │B-1 │A-2 │    │B-2 │    │A-3 │B-3 │
 └────┴────┴────┴────┴────┴────┴────┴────┘
         ↑ claimed on demand, returned when done, reusable by any request

 Request A's block table (logical → physical): [0, 2, 6]
 Request B's block table (logical → physical): [1, 4, 7]

Note that A's blocks go 0 → 2 → 6, physically non-contiguous — attention computes through block-table indirection (the PagedAttention kernel reads KV non-contiguously). This is the same principle as an MMU letting a user program believe its memory is contiguous while it actually sits scattered across physical frames.

The OS paging analogy

OS virtual memory	PagedAttention / vLLM
Page	Block (fixed KV for 16 tokens)
Physical memory frame	GPU memory block
Page table	Block table
Demand paging	Blocks allocated on demand, growing with generation
Process address space	A request's KV cache sequence
Defragmentation / compaction	Unneeded — uniform block size, no external fragmentation
Page sharing (fork, copy-on-write)	Block sharing (parallel sampling, beam search, prefix caching)
Swapping	KV blocks swapped to CPU memory (or dropped and recomputed)

The design yields three immediate wins:

1. Near-zero waste: blocks are allocated on demand and only the last one may be partially filled — waste shrinks to block granularity;
2. No external fragmentation: all blocks are the same size, so no "holes";
3. Block-level sharing: a shared prompt prefix, or the multiple sampled sequences of one request, can reference the same KV blocks — memory reuse pushes peak usage down further.

Continuous Batching: Request-Level vs. Iteration-Level Scheduling

Memory alone isn't enough — throughput also depends on "when the batch turns over." Autoregressive generation runs a full forward pass per token, so one request means dozens to hundreds of forward passes. Traditional serving schedules at request granularity: the whole batch must finish generating before the next batch starts — the slowest request drags everyone, and new requests just wait (Orca's paper nailed this problem precisely).

Continuous batching (iteration-level scheduling) drops the scheduling granularity to "one iteration":

• Iteration-level scheduling: after each token, finished requests immediately dequeue and return, and new requests immediately join the next iteration's batch;
• The batch stays full: the GPU no longer idles waiting for the slowest request — throughput jumps accordingly.

Request-level scheduling (pre-Orca):      Iteration-level (continuous batching):
batch = {A,B,C} fixed                     batch updated every iteration
A finishes → whole batch waits on B, C    A finishes → A dequeues, D enqueues
New request D queues until batch ends     batch = {B,C,D}
→ GPU idles, high latency                 → GPU saturated, high throughput

Orca (OSDI 2022) introduced this mechanism; vLLM inherited it as standard equipment.

Implementation Essentials

• Block Manager: a pre-allocated memory pool, block allocation/reclamation, and refcounts enabling cross-sequence sharing; when memory runs short, preemption kicks in — swapping a low-priority request's blocks to CPU or dropping them wholesale for later recomputation (like OS swap).
• Pre-allocated memory pool: the KV cache pool is allocated once at startup; no dynamic cudaMalloc during inference (dynamic allocation is slow and worsens fragmentation).
• Prefix sharing: the multiple sequences of parallel sampling share the prompt's KV blocks, avoiding recomputing the prompt.
• Room for speculative decoding: blocks are reserved for draft tokens, avoiding extra allocation overhead during speculative decoding.

Key Results

Metric	Number
Throughput (vs. FasterTransformer / Orca)	2–4×, with no latency regression (the abstract's own claim)
Throughput (vs. Orca, ShareGPT long sequences / OPT-13B config)	Up to 8.5× (per Figure 10 and the specific experimental setups)
KV cache waste	From 60%–80% down to near zero (block granularity)
Pattern	The longer the sequences, the larger the model, the more complex the decoding (parallel sampling/beam search), the bigger the gains
Distributed	Supports models larger than one GPU (with tensor parallelism, each card manages its own KV cache)

Reading the 8.5× claim correctly

2–4× is the across-the-board throughput gain over SOTA systems at equal latency. 8.5× is a specific configuration (long-sequence workloads like ShareGPT, OPT-13B). Quoting "8.5×" in an engineering report without the workload characteristics misleads capacity planning. Always re-measure with your own traffic distribution — see Performance Optimization and Capacity Planning.

Impact and Follow-Ups: The KV Cache Becomes the New Battleground

After vLLM, the KV cache went from "an unmanaged cache" to core inference infrastructure, spawning three directions:

1. Prefix caching: cache the KV of shared prompt prefixes (system prompts, few-shot templates) and reuse them across requests — on a hit, prefill is nearly free. vLLM supports this natively, and a hit saves a large chunk of latency.
2. Chunked prefill: long prompts make prefill compute-heavy and "clog" decoding; splitting prefill into chunks interleaved with decode lowers time-to-first-token (TTFT) and raises GPU utilization.
3. Even more aggressive KV optimization: SGLang's RadixAttention (a shareable prefix tree of KV caches), KV cache quantization, GQA/MQA to shrink KV size, and prefill/decode disaggregated deployment (PD separation).

Where vLLM sits on this site

• Mechanisms (KV cache, scheduling, prefill/decode): LLM Inference Optimization
• Hands-on configuration (--max-model-len, --gpu-memory-utilization, prefix caching flags): the vLLM case study
• Its scheduling descends from Orca and its memory management from OS design — the full lineage in Serving Systems

Limitations

• However well you tame the KV cache, weights and long contexts can still blow past memory: block management optimizes "waste," not "total volume"; very long contexts still need quantization (Quantization Classics) and parallelism (Parallel and Distributed Inference).
• Preemption costs: swapping/recomputing requests under memory pressure produces latency spikes; scheduling policies need careful tuning.
• Non-contiguous kernel complexity: the PagedAttention kernel is costly to implement and tune — and remains one of the main axes on which engines differentiate.

Further Reading

• LLM Inference Optimization — the foundations: KV cache, continuous batching, speculative decoding
• The vLLM case study — the paper's design turned into real deployment parameters and tuning
• Serving Systems: Clipper / Orca / Nexus — where continuous batching came from (Orca) and the earlier serving systems
• Parallel and Distributed Inference — how tensor/pipeline parallelism stacks with vLLM
• Quantization Classics: LLM.int8 / GPTQ / AWQ — weight and KV quantization to cut total memory
• Performance Optimization and Capacity Planning — measuring and load-testing throughput/latency

References

• Efficient Memory Management for Large Language Model Serving with PagedAttention (arXiv 2309.06180, SOSP 2023)
• vLLM official GitHub repository
• Orca: A Distributed Serving System for Transformer-Based Generative Models (OSDI 2022)
• SGLang: Efficient Execution of Structured Language Model Programs (arXiv 2312.07104)