kv cache optimization
**KV Cache Optimization** is the **set of techniques for reducing the massive memory consumption of key-value caches in autoregressive Transformer inference** — where each generated token requires storing key and value tensors for all previous tokens across all layers, creating a memory bottleneck that grows linearly with sequence length and batch size, addressed by methods like PagedAttention (vLLM), KV cache compression, quantization, and eviction policies that enable serving longer contexts and more concurrent users.
**The KV Cache Problem**
```
Autoregressive generation:
Token t needs attention over all tokens 0..t-1
→ Must store K and V for all past tokens in all layers
Memory per token per layer: 2 × d_model × sizeof(dtype)
Total KV cache: 2 × n_layers × n_tokens × d_model × sizeof(dtype)
Llama-2-70B (80 layers, d=8192, FP16):
Per token: 2 × 80 × 8192 × 2 bytes = 2.6 MB per token
4K context: 2.6MB × 4096 = 10.5 GB
128K context: 2.6MB × 131072 = 335 GB (!)
```
**KV Cache vs. Model Weights Memory**
| Model | Weights (FP16) | KV Cache (4K) | KV Cache (128K) |
|-------|---------------|-------------|----------------|
| Llama-2-7B | 14 GB | 1.3 GB | 43 GB |
| Llama-2-70B | 140 GB | 10.5 GB | 335 GB |
| Mixtral 8x7B | 94 GB | 3.5 GB | 112 GB |
**PagedAttention (vLLM)**
```
Problem: Traditional KV cache pre-allocates max_seq_len per request
→ 90%+ of allocated memory is wasted (internal fragmentation)
PagedAttention solution: OS-style virtual memory for KV cache
- Divide KV cache into fixed-size pages (blocks of 16-64 tokens)
- Allocate pages on demand as sequence grows
- Pages can be non-contiguous in GPU memory
- Free pages immediately when sequence completes
Result: Near-zero memory waste → 2-4× more concurrent requests
```
**KV Cache Compression Techniques**
| Technique | Method | Compression | Quality Impact |
|-----------|--------|------------|---------------|
| KV cache quantization | INT8/INT4 cache | 2-4× | Minimal |
| GQA (Grouped Query Attention) | Share K,V across head groups | 4-8× | Negligible |
| MQA (Multi-Query Attention) | All heads share one K,V | 8-32× | Small |
| KV cache eviction (H2O) | Drop least important tokens | 5-10× | Moderate |
| StreamingLLM | Keep attention sinks + recent | Constant memory | Good for streaming |
| Scissorhands | Prune based on attention pattern | 5× | Moderate |
**Grouped Query Attention (GQA)**
```
MHA (Multi-Head Attention): 32 Q heads, 32 K heads, 32 V heads
KV cache: 2 × 32 × d_head × seq_len
GQA (8 KV groups): 32 Q heads, 8 K heads, 8 V heads
Each KV head shared by 4 Q heads
KV cache: 2 × 8 × d_head × seq_len → 4× smaller!
MQA (1 KV head): 32 Q heads, 1 K head, 1 V head
KV cache: 2 × 1 × d_head × seq_len → 32× smaller!
```
**KV Cache Quantization**
- Quantize cached K and V to INT8 or INT4 after computation.
- Attention still computed in FP16/BF16 (dequantize on the fly).
- INT8 KV: 2× memory reduction, <0.1% quality loss.
- INT4 KV: 4× reduction, 0.5-1% quality loss.
- Per-token or per-channel quantization for best accuracy.
**Eviction Policies**
```
H2O (Heavy Hitter Oracle):
Observation: Some tokens get high attention consistently ("heavy hitters")
Strategy: Keep heavy hitters + recent tokens, evict the rest
Budget: Keep top-k heavy hitters + sliding window of recent tokens
StreamingLLM:
Observation: First few tokens ("attention sinks") always get high attention
Strategy: Keep first 4 tokens + sliding window of last N tokens
Enables: Infinite generation with fixed memory
```
**Practical Deployment**
| System | KV Optimization | Benefit |
|--------|----------------|--------|
| vLLM | PagedAttention | 2-4× throughput |
| TensorRT-LLM | Paged KV + INT8 quant | 3-6× throughput |
| SGLang | RadixAttention (prefix caching) | Share KV across requests |
| Llama 3.1 | GQA (8 KV heads) | 4× smaller KV cache |
KV cache optimization is **the critical bottleneck for scalable LLM serving** — as models process longer contexts and serve more users simultaneously, the KV cache becomes the dominant memory consumer, and techniques like PagedAttention, GQA, and cache quantization directly translate into serving more requests per GPU, reducing inference costs, and enabling the long-context applications that modern AI demands.