Training a large language model is an overwhelmingly compute-bound process dominated by massive matrix multiplications running on parallel Tensor Cores. Serving that same model during autoregressive inference, however, undergoes a complete thermodynamic inversion: token generation is severely Memory-Bandwidth Bound. For every single generated token, the model must read all billions of static model parameters plus gigabytes of dynamic history from GPU memory. The primary battleground of modern inference systems is the Key-Value (KV) Cache and memory management architectures like PagedAttention (vLLM).
1. The Autoregressive Generation Bottleneck: Prefill vs Decode
Inference proceeds in two fundamentally distinct operational regimes:
- The Prefill (Prompt) Phase: Ingests prompt tokens $(x_1, dots, x_P)$ simultaneously in parallel. The entire $P times P$ causal attention matrix is evaluated in a single forward pass, completely saturating GPU arithmetic units (Compute-Bound, High Arithmetic Intensity).
- The Decode (Generation) Phase: Generates tokens autoregressively one by one ($x_{P+1}, x_{P+2}, dots$). At step $t$, the query vector is a single token vector $q_t in mathbb{R}^{1 times d}$. Evaluating attention against past context requires accessing keys and values for all preceding positions $1 dots t-1$.
Without caching, past hidden states would have to be recomputed from scratch at every step, scaling generation cost as $O(T^2)$. Storing past keys and values in GPU VRAM avoids recomputation: this is the KV Cache.
2. Anatomy of the KV Cache Footprint
For a model with $n_{text{layers}}$ layers, $n_{text{heads}}$ key/value heads, and head dimension $d_{text{head}}$, storing 16-bit floating-point (FP16/BF16, 2 bytes) representations across batch size $b$ and sequence length $s$ requires:
$$text{Memory}_{text{KV}} = 2 times 2 times n_{text{layers}} times n_{text{heads}} times d_{text{head}} times b times s quad text{Bytes}$$
For a standard LLaMA-2 70B model ($n_{text{layers}} = 80, n_{text{heads}} = 64, d_{text{head}} = 128$) running batch size $b = 32$ with context length $s = 4096$:
$$text{Memory}_{text{KV}} = 4 times 80 times 64 times 128 times 32 times 4096 = 343.6 times 10^9 text{ Bytes} approx 344 text{ GB}$$
The KV cache alone exceeds the memory capacity of four 80GB NVIDIA A100 GPUs, surpassing the static parameter weights ($140text{ GB}$) of the model itself!
3. Memory Fragmentation in Traditional Serving
Prior to 2023, serving frameworks (HuggingFace TGI, FasterTransformer) allocated contiguous chunks of virtual memory based on the maximum possible request length (e.g., reserving 2048 tokens). Because actual user queries are unpredictable in length, this design caused catastrophic memory fragmentation:
- Internal Fragmentation: Unused pre-allocated slots reserved for tokens that were never generated.
- External Fragmentation: Scattered non-contiguous memory chunks too small to accommodate new requests.
Empirical audits revealed that $60%$ to $80%$ of GPU VRAM was wasted on empty reserved memory, forcing batch sizes down and crippling throughput.
4. PagedAttention and vLLM: Virtual Memory for LLMs
In 2023, Woosuk Kwon et al. at UC Berkeley resolved this crisis with PagedAttention, drawing inspiration from classical operating system virtual memory and paging.
PagedAttention partitions the KV cache into fixed-size physical memory blocks (typically 16 or 32 tokens). Instead of storing tokens contiguously, blocks are allocated dynamically on-demand from a centralized block table: logical token positions map to arbitrary physical GPU memory locations.
Key algorithmic innovations of PagedAttention include:
- Near-Zero Memory Waste: Memory waste drops below $4%$, occurring only in the final block of a sequence. GPU serving concurrency and batch size increase by $2times$ to $4times$.
- Zero-Copy Branching: Parallel sampling (e.g., beam search, multiple candidate completions) shares physical blocks using Copy-on-Write (CoW), consuming zero additional memory until branches diverge.
- Prefix Caching: Frequently recurring system prompts, multi-turn chat histories, or document contexts reside persistently in cache blocks, eliminating redundant prefill computation entirely.
