KV-Cache

Without a cache, each new token forces a full recalculation of attention over the entire growing sequence, resulting in O(n²) time complexity. The KV-Cache stores the Key and Value projections from all prior tokens. When generating token t+1, the model only computes the Query, Key, and Value for the single new token and appends them to the cache. This reduces the computational cost of each step to O(n) linear time, making long-form generation feasible.

The cache size scales linearly with four factors:

• Batch Size (B): Number of concurrent sequences
• Sequence Length (L): Total tokens generated
• Number of Layers (H): Transformer depth
• Hidden Dimension (D): Model width

Total memory = 2 * B * L * H * D * sizeof(dtype) bytes. For a 7B model generating 2048 tokens with a batch of 32 in FP16, the cache alone consumes over 2 GB of VRAM. This often exceeds the model weights themselves, making it the primary bottleneck for high-throughput serving.

The KV-Cache creates a distinct performance profile with two phases:

• Prefill Phase: The initial prompt is processed in parallel. This is compute-bound, saturating the GPU's matrix multiplication units as it computes the full cache for all input tokens simultaneously.
• Decode Phase: Each subsequent token is generated sequentially. This is memory-bound, as the entire cache must be loaded from VRAM to compute attention for a single new token. Optimization strategies must target these two bottlenecks differently.

Standard Multi-Head Attention (MHA) stores separate Key and Value tensors for each head, multiplying memory usage. Optimization variants reduce this:

• Multi-Query Attention (MQA): All heads share a single Key and Value tensor, drastically cutting cache size but potentially degrading quality.
• Grouped-Query Attention (GQA): A middle ground where heads are divided into groups sharing a single K and V. Models like Llama 2 70B use GQA to achieve near-MHA quality with a significantly smaller memory footprint, directly lowering the cost of the KV-Cache.

For extremely long contexts, the cache can exceed available memory. Mitigation strategies include:

• Sliding Window Attention: Only the most recent W tokens' cache entries are retained, enforcing a fixed memory bound.
• KV-Cache Quantization: Storing Keys and Values in lower precision (e.g., INT8 or FP8 instead of FP16) reduces memory pressure by 2-4x with minimal accuracy loss.
• Token Dropping: Heuristics like StreamingLLM evict the cache entries for middle tokens while preserving initial 'attention sinks' and recent tokens to maintain coherence.

The elapsed time between a user submitting a query and the model generating the first output token. A populated KV-Cache eliminates the need to recompute the prompt's attention state, directly minimizing TTFT. In scenarios with long system prompts, a pre-computed KV-Cache can reduce TTFT from seconds to milliseconds by serving as a pre-filled prompt state.

The algorithm determining which key-value pairs to discard when the KV-Cache exceeds its memory budget. Common strategies include:

• LRU (Least Recently Used): Evicts the least recently accessed sequences, ideal for stateless API serving.
• FIFO (First-In, First-Out): Simple queue-based eviction.
• TTL (Time-to-Live): Expires entries after a fixed duration. Poor eviction policies cause cache thrashing, where frequently reused prompts are repeatedly evicted and recomputed.

A cascading failure mode where a popular, shared KV-Cache entry (e.g., a long system prompt) expires or is evicted. This triggers a flood of concurrent requests to simultaneously recompute the attention state, overwhelming GPU compute and memory bandwidth. Mitigation strategies include probabilistic early recomputation (stochastically refreshing the cache before expiry) and locking to ensure only one process regenerates the entry.

An attention variant where all attention heads share a single set of key and value projections while retaining distinct query projections. This drastically reduces the KV-Cache size by a factor equal to the number of heads. Grouped-Query Attention (GQA) is a compromise, using a small number of key-value groups. Models like Llama 2 70B and Mistral use GQA to balance memory savings with model quality.