Key-Value Cache (KV Cache)
The Key-Value Cache (KV Cache) is an indispensable memory-centric acceleration mechanism in Transformer-based large language models during autoregressive token generation. By persisting the Key ($K$) and Value ($V$) projection tensors of prior tokens in GPU memory, it eliminates the need to recompute self-attention representations across the entire prompt history at every decoding step, reducing single-step attention complexity from $O(N^2)$ to $O(N)$.
Two-Phase Autoregressive Decoding Paradigm
Large language model inference comprises two distinct operating phases with divergent hardware bottlenecks:
- Prefill Phase (Prompt Ingestion):
- Processes the prompt tokens concurrently in parallel;
- Strongly compute-bound, saturating Tensor Core matrix-multiply (GEMM) units;
- Computes Key and Value tensors for all input positions simultaneously and initializes the KV Cache.
- Decode Phase (Autoregressive Generation):
- Generates tokens sequentially, one at a time;
- Computes Query, Key, and Value projections solely for the newest incoming token;
- Calculates attention weights against all cached past Keys and computes a weighted average of cached Values;
- Extremely memory-bandwidth-bound: the arithmetic intensity is minimal, meaning the hardware must stream gigabytes of historical KV Cache from High Bandwidth Memory (HBM) to on-chip SRAM for each single token generated. Output throughput is strictly gated by memory bandwidth rather than compute FLOPS.
Quantitative Memory Modeling & Formula
For standard, unquantized half-precision (FP16/BF16) deployments, the aggregate memory occupied by the KV Cache is governed by:
$$\text{Memory}{\text{KV}} = 2 \times L \times n{\text{kv}} \times d_{\text{head}} \times S \times B \times P \quad (\text{Bytes})$$
where:
- $2$: Accounts for the twin Key and Value projection tensors;
- $L$: Total number of Transformer hidden layers;
- $n_{\text{kv}}$: Number of Key-Value attention heads per layer;
- $d_{\text{head}}$: Dimension per individual attention head;
- $S$: Context sequence length (number of prompt and generated tokens);
- $B$: Batch size (concurrent request streams);
- $P$: Precision byte size ($2$ for FP16/BF16, $1$ for FP8, $0.5$ for INT4).
Concrete Numerical Walkthrough: LLaMA-3-70B
For LLaMA-3-70B ($L = 80$, $n_{\text{kv}} = 8$, $d_{\text{head}} = 128$, BF16 $P = 2$ bytes):
-
A single token consumes: $2 \times 80 \times 8 \times 128 \times 2 = 327,680 \text{ bytes} \approx 320 \text{ KB/Token}$;
-
Under an active context window of $S = 8,192$ across a batch of $B = 16$:
$$\text{Total KV Cache} = 320 \text{ KB} \times 8,192 \times 16 \approx 41.9 \text{ GB}$$
The KV Cache demand alone exceeds half the total VRAM of an 80GB A100/H100 GPU, demonstrating that serving capacity is fundamentally constrained by available memory.
Architectural Evolution of Key-Value Attention
To counteract memory expansion, modern attention topologies feature distinct compression trade-offs:
| Architecture | Representative Models | KV Head Ratio | Relative Memory | Core Mechanism |
|---|---|---|---|---|
| MHA (Multi-Head Attention) | GPT-3, LLaMA-1 | $n_{\text{kv}} = n_q$ (1:1) | 100% | Distinct KV projection per Query head; highest capacity and highest footprint |
| MQA (Multi-Query Attention) | Falcon, StarCoder | $n_{\text{kv}} = 1$ | $1/n_q$ (~1.5%) | All Query heads share a single KV head; minimal footprint but potential quality regression |
| GQA (Grouped-Query Attention) | Llama-2/3, Qwen-2 | $n_{\text{kv}} = n_q / 8$ | 12.5% | Query heads grouped into subsets sharing KV heads; current industry standard |
| MLA (Multi-Head Latent Attention) | DeepSeek-V2/V3 | Latent Compression | ~16% (outperforms GQA) | Joint low-rank compression of KV projections into a unified latent vector |
Systems-Level Optimization Techniques
- PagedAttention (Virtual Memory Paging):
- Traditional serving runtimes statically allocate contiguous memory based on maximum sequence length, suffering severe internal fragmentation (unused reserved slots) and external fragmentation, dropping memory utilization below 30%;
- vLLM mirrors operating system virtual memory by chunking the KV Cache into fixed-sized blocks dynamically mapped via a page table, driving memory waste down under 4%.
- Prefix Caching & Radix Trees:
- For multi-turn chats, standard system prompts, or shared retrieval contexts, runtimes employ Radix Trees to cache and share common prefix KV tensors across sessions, substantially lowering Time-To-First-Token (TTFT).
- KV Cache Quantization (FP8 / INT8 / INT4):
- Converting Key and Value representations into lower precision formats (such as FP8) halves memory consumption and doubles concurrent request throughput with negligible perplexity degradation.