KV Cache

During autoregressive decoding, each new token must attend to all previous tokens. Without a cache, the Key and Value projections for the entire sequence would be recomputed at every step, resulting in quadratic complexity. The KV Cache stores these computed tensors in GPU memory.

• Write Phase: When a new token is generated, its Key and Value tensors are computed and appended to the cache.
• Read Phase: The attention mechanism reads all historical Keys and Values directly from the cache, computing only the single new Query vector.
• Result: Reduces the computational complexity of a single decoding step from quadratic to linear relative to the sequence length.

The cache size scales linearly with batch size, sequence length, number of layers, and hidden dimension. For large models, this creates a significant memory bottleneck.

• Calculation: cache_size = 2 * batch_size * seq_len * num_layers * hidden_dim * precision_bytes
• Example: A 70B parameter model serving a single 4096-token sequence can require over 2.5 GB of memory just for the KV Cache.
• Impact: Memory bandwidth, not compute, often becomes the primary limiter of throughput, a phenomenon known as memory-bound inference.

Traditional KV Caches allocate one large contiguous block of memory per sequence, leading to internal fragmentation and limiting total throughput. PagedAttention solves this by partitioning the cache into non-contiguous blocks.

• Block-Based Management: Memory is allocated in fixed-size blocks, similar to virtual memory paging in operating systems.
• Zero Waste: Blocks can be shared across sequences for parallel sampling or beam search, eliminating redundant storage.
• Result: This enables a serving system to handle a significantly higher number of concurrent requests by dynamically mapping logical KV caches to physical GPU memory blocks.

Many applications use a long, static system prompt or few-shot examples. Prefix Caching identifies and reuses the KV Cache for these shared prefixes across multiple distinct requests.

• Mechanism: The serving engine hashes the prompt prefix tokens. If a match is found in a persistent cache, the pre-computed Keys and Values are loaded instantly.
• Benefit: Eliminates the computationally expensive prefill phase for the shared portion, drastically reducing Time To First Token (TTFT) and freeing compute for unique suffixes.
• Use Case: Critical for chatbots with large system instructions or Retrieval-Augmented Generation (RAG) applications with a fixed retrieved context.

The KV Cache embodies a fundamental trade-off in inference serving. Saving compute by caching tensors consumes scarce high-bandwidth memory (HBM).

• Latency-Optimized: Keeping the entire cache in GPU HBM ensures the fastest possible token generation speed.
• Throughput-Optimized: Offloading less-frequently accessed cache blocks to CPU RAM or NVMe storage allows for serving extremely long contexts or more concurrent users, at the cost of higher per-token latency.
• Quantization: Applying KV Cache Quantization (e.g., FP8 or INT8) is a common strategy to compress the cache, increasing effective memory capacity with minimal accuracy loss.

Architectural changes to the attention mechanism directly reduce the size of the KV Cache. Multi-Query Attention (MQA) uses a single Key-Value head shared across all Query heads.

• MQA: Drastically shrinks the cache size, but can lead to quality degradation.
• Grouped-Query Attention (GQA): A compromise where a small number of Key-Value heads (e.g., 4) serve a larger number of Query heads (e.g., 32).
• Impact: GQA achieves near-MHA quality while significantly reducing the memory footprint of the KV Cache, enabling larger batch sizes and longer context windows on the same hardware.

An optimization that stores and reuses the computed KV cache for a shared prompt prefix across multiple generation requests, avoiding redundant computation of identical token sequences.

• System Prompt Reuse: Caches the KV tensors for static system instructions applied to every request
• Few-Shot Example Sharing: Reuses cached examples across different user queries
• Radix Tree Matching: Efficiently identifies the longest common prefix among incoming requests

Prefix caching can reduce Time To First Token (TTFT) by up to 90% when serving applications with long, shared system prompts or conversation histories.

An attention mechanism that uses a single set of key-value heads for multiple query heads, directly reducing the size of the KV cache. GQA balances the memory efficiency of multi-query attention with the quality of multi-head attention.

• Configuration: Typically 8 query heads share 1 KV head (e.g., Llama 2 70B)
• Cache Reduction: Reduces KV cache size proportionally to the query-to-KV head ratio
• Quality Retention: Maintains >99% of multi-head attention quality on standard benchmarks

GQA is the default attention mechanism in Llama 2, Llama 3, Mistral, and Gemma models, making it a foundational design choice for modern LLM inference.

An extreme variant of attention where all query heads share a single key-value head, minimizing the KV cache to its theoretical minimum. This trades some model quality for maximum memory efficiency during autoregressive decoding.

• Single KV Head: Regardless of the number of query heads (e.g., 96 query heads, 1 KV head)
• Memory Savings: Reduces KV cache size by the number of query heads compared to multi-head attention
• Quality Tradeoff: Small degradation on tasks requiring fine-grained attention differentiation

MQA was popularized by Google's PaLM and is used in models where inference speed and memory constraints outweigh marginal quality improvements.

An IO-aware exact attention algorithm that minimizes high-bandwidth memory (HBM) reads and writes by tiling the attention computation. While not a caching technique itself, FlashAttention dramatically accelerates the computation that populates the KV cache.

• Tiling: Decomposes the attention matrix into blocks that fit in SRAM, avoiding materializing the full N×N matrix in HBM
• Recomputation: Recomputes attention statistics in the backward pass rather than storing them, reducing memory overhead
• Speedup: Achieves 2-4x wall-clock speedup over standard attention implementations

FlashAttention-2 and FlashAttention-3 extend these principles to achieve up to 70% of theoretical peak FLOPs on H100 GPUs, making it the de facto standard attention kernel in modern inference stacks.

A serving technique that dynamically appends new sequences to a running batch instead of waiting for the entire batch to complete before starting new requests. This maximizes GPU utilization by keeping the batch full at all times.

• Iteration-Level Scheduling: New requests join the batch at the next token generation step
• KV Cache Coexistence: Multiple sequences at different generation stages share GPU memory simultaneously
• Throughput Gains: Achieves 5-10x higher throughput compared to static batching

Continuous batching is a core feature of modern inference engines like vLLM, TensorRT-LLM, and TGI, directly complementing PagedAttention's memory management for maximum serving efficiency.