kv cache
**KV Cache (Key-Value Cache)** is the **inference optimization technique that stores the previously computed Key and Value projection matrices from the transformer attention mechanism** — avoiding redundant recomputation during autoregressive text generation, where each new token only needs to attend to all previous tokens without recalculating their K and V representations, reducing the computational complexity of generating N tokens from O(N³) to O(N²).
**Why KV Cache Is Necessary**
Autoregressive generation produces tokens one at a time:
- Token 1: Compute K₁, V₁, Q₁ → attention → output token 2.
- Token 2: Need K₁, K₂, V₁, V₂, Q₂ → without cache, recompute K₁, V₁.
- Token N: Need all K₁..Kₙ, V₁..Vₙ → without cache, recompute everything.
- **With KV cache**: Store K₁..Kₙ₋₁, V₁..Kₙ₋₁ → only compute Kₙ, Vₙ, Qₙ → append to cache.
**Memory Cost**
- Per token per layer: 2 × d_model × sizeof(dtype) (one K vector + one V vector).
- For a 70B model (80 layers, d=8192, FP16): 2 × 80 × 8192 × 2 bytes = 2.5 MB per token.
- Sequence length 4096: 2.5 MB × 4096 = **10 GB** of KV cache per sequence.
- Batch of 32 sequences: **320 GB** — often exceeds GPU memory!
**KV Cache Optimization Techniques**
| Technique | Memory Savings | Approach |
|-----------|---------------|----------|
| Multi-Query Attention (MQA) | ~8-16x | Share K,V heads across all query heads |
| Grouped-Query Attention (GQA) | ~4-8x | Share K,V among groups of query heads |
| KV Cache Quantization | 2-4x | Quantize cached K,V to INT8/INT4 |
| Sliding Window | Bounded | Only cache last W tokens (Mistral) |
| PagedAttention (vLLM) | ~2-4x throughput | OS-style paged memory management for KV |
| Token Pruning/Eviction | Variable | Evict less important cached tokens |
**PagedAttention (vLLM)**
- Problem: KV cache allocated as contiguous memory per sequence → fragmentation, wasted memory.
- Solution: Divide KV cache into pages (blocks) → allocate on demand like virtual memory.
- Cache entries stored in non-contiguous physical blocks, mapped via page table.
- Result: Near-zero memory waste → 2-4x more concurrent sequences → higher throughput.
**Prefill vs. Decode Phases**
| Phase | Compute | Memory | Bottleneck |
|-------|---------|--------|------------|
| Prefill | Process all prompt tokens at once | Build initial KV cache | Compute-bound |
| Decode | Generate one token at a time | Append to KV cache | Memory-bandwidth-bound |
- Prefill: Matrix multiply (batched) → high compute utilization.
- Decode: Each step reads entire KV cache for attention → dominated by memory bandwidth.
KV cache optimization is **the central challenge in LLM serving** — as context lengths grow to 100K+ tokens, the KV cache memory footprint dominates GPU memory usage, making techniques like GQA, quantization, and PagedAttention essential for practical deployment of large language models at scale.