kv cache optimization

**KV Cache Optimization** is **the set of techniques for reducing memory footprint and bandwidth requirements of cached key-value pairs in autoregressive transformer inference** — including quantization (INT8/INT4), eviction policies, compression, and architectural changes that collectively enable 2-10× memory reduction, allowing larger batch sizes, longer contexts, or deployment on smaller GPUs while maintaining generation quality. **KV Cache Fundamentals:** - **Cache Purpose**: in autoregressive generation, each token attends to all previous tokens; recomputing K and V for all previous tokens at each step costs O(L²) FLOPs; caching K and V reduces to O(L) per token; trades memory for compute - **Memory Scaling**: for model with L layers, H heads, sequence length N, head dimension d, batch size B: cache size = B×L×2×N×H×d×sizeof(dtype); Llama 2 70B at N=4096, B=32, FP16: 70×2×4096×8×128×2 = 58GB just for KV cache - **Bandwidth Bottleneck**: each generated token loads entire KV cache from HBM; at 4K context, loads 1.8GB per token; A100 HBM bandwidth 1.5TB/s limits to ~800 tokens/sec; memory bandwidth, not compute, determines throughput - **Growth During Generation**: cache grows by B×L×2×H×d×sizeof(dtype) per token; for Llama 2 70B, adds 14MB per token; 1000-token generation requires 14GB additional memory; limits maximum batch size or context length **Quantization Techniques:** - **INT8 KV Cache**: quantize cached K and V from FP16 to INT8; 2× memory reduction; per-tensor or per-channel quantization; dequantize before attention computation; quality loss <0.1 perplexity for most models; supported in TensorRT-LLM, vLLM, HuggingFace TGI - **INT4 KV Cache**: aggressive 4× reduction; requires careful calibration; group-wise quantization (groups of 32-128 elements) maintains quality; perplexity increase 0.1-0.3; enables 4× larger batches or contexts; used in GPTQ-for-LLMs, AWQ - **Mixed Precision**: quantize V cache more aggressively than K; V contributes to output values (less sensitive), K affects attention scores (more sensitive); K in INT8, V in INT4 provides 3× reduction with minimal quality loss - **Dynamic Quantization**: quantize during generation, not ahead of time; adapts to actual value distributions; slightly higher latency (quantization overhead) but better quality; used in production systems with strict quality requirements **Eviction and Compression:** - **H2O (Heavy Hitter Oracle)**: evicts KV pairs with lowest attention scores; keeps "heavy hitter" tokens that receive most attention; maintains 20-30% of cache with <1% quality loss; requires tracking attention scores (overhead); effective for long contexts where most tokens rarely attended - **StreamingLLM**: keeps first few tokens (system prompt) and recent window; evicts middle tokens; exploits observation that attention focuses on recent context and initial tokens; enables infinite context with fixed memory; quality depends on task (good for chat, poor for long-document QA) - **Scissorhands**: learns to predict which KV pairs can be evicted; trains small predictor network on attention patterns; achieves 50-70% cache reduction with <0.5% quality loss; requires model-specific training - **Sparse Attention Patterns**: for models with structured sparsity (sliding window, block-sparse), only cache tokens within attention pattern; Mistral 7B with 4K sliding window caches only 4K tokens regardless of total length; enables unbounded generation **Architectural Optimizations:** - **Multi-Query Attention (MQA)**: shares K and V across all query heads; reduces cache by number of heads (typically 32-64×); used in PaLM, Falcon; 1-2% quality trade-off for massive memory savings - **Grouped Query Attention (GQA)**: shares K and V across groups of heads; 4-8× cache reduction with <0.5% quality loss; used in Llama 2, Mistral; sweet spot between MHA and MQA - **Cross-Layer KV Sharing**: shares KV cache across multiple layers; reduces cache by factor of layers sharing; experimental technique; 2-4 layers can share with acceptable quality loss; total reduction 2-4× - **Low-Rank KV Projection**: projects K and V to lower dimension before caching; cache stores low-rank version; reconstruct full dimension during attention; 2-4× reduction; requires architecture modification and retraining **PagedAttention and Memory Management:** - **PagedAttention (vLLM)**: treats KV cache like virtual memory with paging; divides cache into fixed-size blocks (pages); non-contiguous storage eliminates fragmentation; enables near-optimal memory utilization (90-95% vs 20-40% for naive allocation) - **Block Size**: typical block size 16-64 tokens; smaller blocks reduce internal fragmentation but increase metadata overhead; 32 tokens balances trade-offs for most workloads - **Copy-on-Write**: multiple sequences can share cache blocks (e.g., common prompt); only copy when sequences diverge; critical for beam search and parallel sampling where sequences share prefix - **Memory Pool**: pre-allocates memory pool for cache blocks; eliminates allocation overhead during generation; enables predictable latency; pool size determines maximum concurrent requests **Production Deployment Impact:** - **Throughput**: INT8 quantization + PagedAttention enables 2-3× higher throughput vs naive FP16 caching; serves 100-200 requests/sec vs 30-50 for Llama 2 70B on 8×A100 - **Latency**: reduced memory bandwidth improves time-to-first-token by 20-40%; subsequent tokens 10-20% faster; critical for interactive applications where latency matters - **Cost**: 2-4× memory reduction enables deployment on smaller/fewer GPUs; Llama 2 70B with optimizations fits on 4×A100 vs 8×A100; halves infrastructure cost - **Context Length**: memory savings enable 2-4× longer contexts at same batch size; or maintain context while increasing batch size 2-4×; flexibility to optimize for throughput or capability KV Cache Optimization is **the critical enabler of practical LLM deployment** — by addressing the memory bottleneck that dominates inference costs, these techniques transform LLMs from research artifacts requiring massive GPU clusters into production systems that serve millions of users on reasonable hardware budgets.