Paged Attention and vLLM

Paged Attention is a memory management algorithm for large language model inference that partitions the KV cache into fixed-size, non-contiguous physical memory blocks—analogous to virtual memory paging in operating systems—enabling near-zero KV cache fragmentation and dynamic memory allocation across concurrent requests. vLLM is the open-source serving system built atop this primitive, achieving throughput improvements of 2–4× over prior systems such as FasterTransformer and Orca by eliminating the static, pre-allocated memory waste that plagued earlier LLM serving stacks. The counterintuitive fact: the dominant bottleneck in LLM serving is not compute (GPU FLOPs) but memory bandwidth and fragmentation of the KV cache, meaning that an OS-level insight—virtual memory—unlocks more practical throughput than most architectural innovations.

The core insight

Every autoregressive generation step requires reading the full KV cache for all active tokens, so the memory layout of that cache determines serving throughput more than almost any other factor. Prior systems over-provision contiguous GPU memory per sequence—wasting 60–80% of KV cache capacity to internal and external fragmentation—because they had no mechanism to share or reuse non-contiguous blocks. Paged Attention decouples the logical KV cache (contiguous from the model's perspective) from the physical KV cache (arbitrary block addresses on device), exactly as virtual memory decouples process address spaces from DRAM pages. The "aha moment": the GPU memory manager can now handle a dynamic, unpredictable workload of variable-length sequences without any static worst-case reservation.

Common trapCommon Misconception

Practitioners frequently assume vLLM's throughput gain comes primarily from kernel-level attention optimizations such as FlashAttention or from better batching heuristics, and consequently expect that combining FlashAttention with a naive serving loop will approach vLLM performance. This is wrong for a precise reason: FlashAttention reduces the per-step compute cost of attention, but it does nothing about the memory capacity available for concurrent sequences. The true bottleneck is that naive systems must allocate a contiguous chunk of KV cache large enough for the maximum possible output length of each sequence at the moment the request arrives—a gross over-reservation that evicts other requests from GPU memory. The correct mental model distinguishes two orthogonal axes: (1) per-step memory bandwidth (improved by FlashAttention/IO-aware kernels) and (2) total concurrent sequence capacity (improved by Paged Attention's block allocator); vLLM primarily attacks axis (2), though it also integrates axis (1) optimizations.

How It Works

KV Cache Fundamentals

During autoregressive decoding of a transformer, each layer $\ell$ maintains key and value projections for all previously generated tokens. For a sequence of current length $t$ , layer $\ell$ , head $h$ , the key cache is:

\quad K^{(\ell,h)} = \bigl[k^{(\ell,h)}_1,\, k^{(\ell,h)}_2,\, \ldots,\, k^{(\ell,h)}_t\bigr] \in \mathbb{R}^{t \times d_k}

Explanation: the key cache for one head at one layer is simply the concatenation of per-token key vectors, growing by one row at every generation step. Here $d_k = d_{\text{model}} / H$ where $H$ is the number of attention heads. The memory footprint per token across all layers and heads is:

\quad M_{\text{token}} = 2 \cdot L \cdot H \cdot d_k \cdot \text{sizeof}(\text{dtype}) \;\text{bytes}

Explanation: factor of 2 accounts for both keys and values, $L$ layers and $H$ heads each contribute $d_k$ elements per token. For LLaMA-2 70B in FP16: $L=80$ , $H=64$ , $d_k=128$ , giving $M_{\text{token}} = 2 \times 80 \times 64 \times 128 \times 2 = 2{,}621{,}440$ bytes $\approx 2.5$ MB per token. A batch of 256 sequences each generating 512 tokens consumes $\approx 327$ GB—exceeding a single A100 node.

Block Table and Logical-to-Physical Mapping

Paged Attention partitions the physical KV cache into blocks of fixed size $B$ tokens (typically $B = 16$ ). Let $\mathcal{P}$ denote the pool of physical blocks. Each sequence $s$ maintains a block table $\tau_s : \mathbb{Z}_{\geq 0} \to \mathcal{P}$ mapping logical block index $j$ to a physical block:

\quad \tau_s(j) = p \;\Longleftrightarrow\; \text{tokens } [jB,\, (j+1)B) \text{ of sequence } s \text{ are stored in physical block } p

Explanation: the block table is a level of indirection—the attention kernel uses $\tau_s$ to fetch the right physical memory addresses regardless of where they reside. The attention computation for query $q_t$ at decode step $t$ with Paged Attention becomes:

\quad a_t = \text{softmax}\!\left(\frac{q_t \cdot \left[\,K_{\tau_s(0)}\,\|\,K_{\tau_s(1)}\,\|\,\cdots\,\|\,K_{\tau_s(\lfloor t/B\rfloor)}\,\right]^{\top}}{\sqrt{d_k}}\right)

Explanation: the query attends over keys gathered from non-contiguous physical blocks via the block table, with the gather operation fused into the attention kernel to avoid materializing a contiguous buffer.

Memory Efficiency: Fragmentation Analysis

Define memory utilization as the fraction of allocated KV cache memory actually storing useful token data. For a system with $N$ sequences and per-sequence max-length reservation $L_{\max}$ , actual mean length $\bar{L}$ :

\quad \eta_{\text{naive}} = \frac{\bar{L}}{L_{\max}} \approx 0.2\text{–}0.4 \quad \text{(empirically, Kwon et al. 2023)}

\quad \eta_{\text{paged}} = \frac{\bar{L}}{B \cdot \lceil \bar{L}/B \rceil} \geq 1 - \frac{B-1}{\bar{L}} \xrightarrow{\bar{L} \gg B} 1

Explanation: paged allocation wastes at most $B-1$ slots in the final block per sequence, so for long sequences and small $B$ , fragmentation vanishes to near zero. This gap— $\eta_{\text{paged}}/\eta_{\text{naive}} \approx 2.5\text{–}5\times$ —directly multiplies the number of concurrent sequences that fit in GPU VRAM, explaining the throughput gains.

Continuous Batching and Scheduler

vLLM implements continuous batching (also called iteration-level scheduling, Orca 2022), where the scheduler makes a new batching decision at every forward pass iteration rather than at request granularity. Combined with Paged Attention, the scheduler can: 1. Preempt a low-priority sequence by evicting its physical blocks to CPU (block-granularity swap). 2. Resume it later by swapping blocks back, incurring only the cost of the evicted blocks rather than the full sequence. 3. Share blocks across sequences with a common prefix (copy-on-write semantics for prefix caching). The copy-on-write rule: physical block $p$ is shared by sequences $\mathcal{S}_p \subseteq \mathcal{S}$ ; a write (new token appended) to $p$ by sequence $s$ triggers allocation of fresh block $p'$ , copy of $p \to p'$ , and update $\tau_s(j) \leftarrow p'$ .

Paged Attention CUDA Kernel

The paged attention kernel (v1/v2, Kwon et al. 2023) partitions each sequence's key-value blocks across thread blocks. For each query token $q$ , a thread block processes one physical KV block, accumulating a partial softmax via the log-sum-exp trick (identical in spirit to FlashAttention's tiling). Thread block $b$ computes:

\quad m_b = \max_{i \in \text{block}_b} \frac{q \cdot k_i}{\sqrt{d_k}}, \qquad \ell_b = \sum_{i \in \text{block}_b} e^{q^\top k_i / \sqrt{d_k} - m_b}, \qquad v_b^{\text{acc}} = \sum_{i \in \text{block}_b} e^{q^\top k_i/\sqrt{d_k} - m_b} v_i

Explanation: each thread block independently computes a numerically stable partial attention output; a reduction pass then combines $(m_b, \ell_b, v_b^{\text{acc}})$ tuples across blocks using the online softmax merge formula. The global output merges partial results from $\lceil t/B \rceil$ blocks:

\quad o = \frac{\sum_b e^{m_b - m^*} v_b^{\text{acc}}}{\sum_b e^{m_b - m^*} \ell_b}, \quad m^* = \max_b m_b

Explanation: this is the standard parallel prefix-softmax reduction—exponentially re-weighted partial sums yield the exact same result as a sequential softmax over the full sequence.

researcher · Woosuk Kwon | b. 1994 | Lead author of the Paged Attention paper and vLLM system

Woosuk Kwon is a PhD student at UC Berkeley (RISE Lab) whose 2023 SOSP paper "Efficient Memory Management for Large Language Model Serving with PagedAttention" introduced the paged attention algorithm and the vLLM system. His key insight was drawing a direct formal analogy between OS virtual memory management and LLM KV cache management, borrowing both the block table abstraction and copy-on-write semantics wholesale. A surprising fact: the paper was submitted and accepted at SOSP—the premier systems conference—rather than a machine learning venue, reflecting vLLM's identity as a systems contribution first and an ML one second.

researcher · Zhuohan Li | b. 1996 | Co-creator of vLLM and Alpa distributed training system

Zhuohan Li is a PhD student at UC Berkeley who co-authored vLLM and previously built Alpa (2022), a system for automated inter/intra-operator parallelism for large model training. His contribution to vLLM included the continuous batching scheduler design and the multi-GPU tensor-parallel execution runtime. Remarkably, the vLLM GitHub repository accumulated over 20,000 stars within three months of its June 2023 release, driven almost entirely by organic practitioner adoption before any major corporate endorsement.

Figure

Paged Attention Memory Layout

Figure

vLLM System Architecture and Request Lifecycle

Intuition

The Mental Model

Think of GPU memory as a hotel, and each LLM request