KV Cache › Summary

The KV cache is a basic optimization that makes autoregressive generation practical. By storing and reusing the key and value projections from attention, we avoid recomputing the same values at every generation step. This reduces the computational overhead from quadratic to linear in the number of generated tokens, and the reduction is not an approximation but an algebraically exact reformulation of the same computation.

The key concepts covered in this chapter are:

• Redundancy problem: Without caching, each generation step recomputes $K$ and $V$ for all previous tokens, yielding $O(T^2)$ total projection operations for a $T$-token generation
• Cache structure: Separate $K$ and $V$ tensors per layer per head, growing with sequence length, storing projections for all processed tokens
• Prefill vs decode: The initial prompt processing (prefill) populates the cache in a single parallel pass, while subsequent generation steps (decode) each process only one token at a time
• Memory requirements: Cache size scales as $2 \times L \times d_{\text{model}} \times T \times \text{bytes}$, easily reaching multiple gigabytes for long sequences with modern models
• Cache management: Decisions about static vs dynamic allocation, batching strategies, and context length limits materially impact deployment efficiency
• Limitations: Memory pressure, fragmentation, bandwidth bottlenecks, and the memory-bandwidth-bound decode phase motivate a detailed ecosystem of follow-on optimizations

Understanding KV cache mechanics is needed for working with modern LLMs, as cache memory often becomes the primary constraint on throughput and context length. The next chapter examines KV cache memory arithmetic in greater detail, including how grouped-query attention changes the calculation. Following that, Paged Attention introduces an operating-system-inspired approach to cache memory management that lets the vLLM serving system's large throughput improvements. After that, we explore techniques for compressing the cache through quantization and eviction to extend context lengths further, all building directly on the foundation established here.