KV Cache

During autoregressive generation, a transformer recomputes the Key (K) and Value (V) tensors for all previous tokens in the sequence for each new token. The KV Cache stores these tensors after their first computation. This changes the computational complexity of generating the n-th token from O(n²) to O(n), eliminating quadratically growing redundant calculations. For a 2048-token sequence, this can reduce FLOPs by over 99% for the final token.

By avoiding the recomputation of past K/V states, the model's forward pass for each new token is significantly faster. This directly reduces:

• Per-token latency: The time to generate each subsequent token.
• Time-to-first-byte (TTFB): For longer sequences, the initial computation is heavier, but the cache makes subsequent generation steps consistently fast. This is critical for real-time interactive applications like chatbots and copilots, where high latency degrades user experience.

The KV Cache enables effective continuous batching (also known as in-flight batching). In a batched inference setting, requests have different sequence lengths and generation states. The cache allows the system to:

• Maintain separate KV states for each sequence in the batch.
• Keep the GPU's compute cores saturated by adding new requests to a running batch as others finish, without recomputing from scratch. This maximizes GPU utilization and overall system Tokens Per Second (TPS), which is the primary throughput metric for LLM serving.

While the KV Cache consumes significant GPU memory, its growth is linear and predictable with sequence length. For a model with L layers, H attention heads, and a hidden size d, the cache size for one token is approximately 2 * L * H * d * dtype_size. This predictability allows serving systems to:

• Pre-allocate memory efficiently.
• Implement advanced memory management (e.g., PagedAttention in vLLM) to reduce fragmentation.
• Accurately plan instance sizing and scaling for target context windows.

The benefits above translate directly into lower cost per token. By reducing FLOPs, latency, and increasing throughput, the same hardware can serve more requests in less time. This optimization is a primary lever in FinOps for LLMs. For high-volume inference, enabling KV Cache can reduce compute costs by an order of magnitude compared to a naive implementation that recomputes all states.

Without a KV Cache, generating even a few hundred tokens would be computationally prohibitive due to the O(n²) complexity. The cache is what makes practical generation with long context windows (e.g., 128K tokens) feasible. While memory becomes the limiting constraint, techniques like paged caching and compression are actively developed to manage this, all building upon the foundational KV Cache mechanism.

This technique applies model quantization principles directly to the KV cache. Instead of storing keys and values in full precision (e.g., FP16/BF16), they are stored in lower precision (e.g., INT8, FP8).

Key benefits include:

• Reduced memory bandwidth: Loading lower-precision data is faster.
• Smaller memory footprint: Enables longer context windows or larger batches on the same hardware.
• Minimal accuracy impact: The attention mechanism is often robust to quantization noise in the cached states.

Dequantization back to higher precision typically occurs just before the attention computation. This is a critical technique for deploying models with long context windows (e.g., 128K+ tokens) without prohibitive memory costs.

These are architectural modifications that fundamentally reduce the size of the KV cache.

• Multi-Query Attention (MQA): All attention heads share a single key and value projection. This drastically shrinks the KV cache size by a factor equal to the number of heads.
• Grouped-Query Attention (GQA): A hybrid approach where heads are divided into groups that share a single key and value projection. It offers a tunable trade-off between the cache savings of MQA and the model quality of standard Multi-Head Attention.

By reducing the number of unique KV vectors that must be stored per layer, these techniques directly lower memory consumption and I/O costs during autoregressive decoding. Models like Llama 2 & 3 use GQA for this reason.

For extremely long sequences that exceed fixed memory budgets, intelligent cache management policies are required.

• Streaming: The cache is treated as a rolling window. As new tokens are generated, the oldest cached tokens are discarded. This is effective for tasks where only recent context is most relevant.
• Eviction Policies: More sophisticated than simple streaming, these algorithms decide which tokens to evict based on heuristics. Examples include:
  • Attention Score: Evict tokens with the lowest average attention score from recent steps.
  • Position-based: Prioritize keeping tokens from the beginning (system instructions) and the most recent tokens.

These methods enable bounded-memory inference for infinite-length contexts, a requirement for applications like long document analysis or perpetual chatbots.

Not all tokens are equally important for future generation. Selective caching avoids storing the KV states for tokens deemed less relevant, creating a sparse KV cache.

Implementation strategies include:

• Static Patterns: Only cache tokens at regular intervals (e.g., every 4th token).
• Content-Based: Use a lightweight scoring model to decide in real-time which tokens to cache, often based on linguistic importance or predicted future utility.
• Attention Sink: Explicitly preserve the KV states of the initial few tokens, which act as "sinks" that stabilize attention scores in streaming/eviction scenarios.

This technique directly trades off a configurable amount of potential model quality for significantly reduced memory and compute overhead.

This optimization focuses on how the KV cache is arranged in physical memory (DRAM/HBM) to maximize hardware efficiency.

Key considerations:

• Memory Access Patterns: Organizing cache tensors to enable coalesced memory accesses, where the GPU can read large, contiguous blocks of data in a single transaction.
• Cache Line Alignment: Ensuring data structures are aligned to hardware cache line boundaries (e.g., 128 bytes) to prevent wasteful partial reads.
• Kernel Fusion: Fusing the cache lookup/update operations with the attention computation kernel to minimize costly round-trips to global memory.

Optimizing the memory layout reduces latency hidden by memory bandwidth bottlenecks, making it a low-level but essential technique for peak GPU performance during inference.

PagedAttention is the memory management algorithm that makes efficient KV Cache usage possible in production. It treats the KV cache like virtual memory in an operating system:

• Manages cache in fixed-size, non-contiguous blocks.
• Dramatically reduces memory fragmentation caused by variable-length sequences.
• Enables memory sharing for identical prompts across multiple requests (e.g., in beam search). This is the foundational technology behind high-throughput serving engines like vLLM, allowing for much higher request concurrency.

Continuous Batching (or In-flight Batching) is an inference scheduling technique that maximizes GPU utilization, working in tandem with KV Cache optimization.

• New requests are dynamically added to a running batch as previous sequences finish generation.
• Eliminates the idle GPU time inherent in static batching.
• The efficiency gains are amplified when combined with a well-managed KV Cache, as both techniques aim to keep computational units saturated with productive work, driving down cost per token.

Tokens Per Second (TPS) is the primary throughput metric for LLM inference. KV Cache is a major determinant of this metric.

• By avoiding redundant computation of previous tokens' Keys and Values, KV cache directly increases TPS.
• The memory footprint of the KV cache can become a bottleneck; efficient management (e.g., via PagedAttention) prevents TPS from degrading as context length or concurrency increases.
• Engineering teams optimize KV cache to maximize TPS, which directly lowers inference cost for a given workload.

Speculative Decoding is an inference acceleration technique that uses a smaller, faster model to 'draft' token sequences which are then verified in parallel by the target LLM. It interacts with KV Cache in two key ways:

• The draft model's forward pass requires its own KV cache management.
• The verification step by the large model can efficiently reuse the KV cache for the accepted draft tokens, making the parallel validation extremely fast. This technique complements KV cache optimization to further reduce time-to-first-token and total generation latency.

Inference Cost is the total financial expenditure of running an LLM, with Cost Per Token as its key unit metric. KV Cache management is a central cost lever.

• Memory Cost: KV Cache consumes GPU VRAM. Inefficient caching forces the use of larger, more expensive instances.
• Compute Cost: By eliminating redundant computation, KV Cache reduces GPU kernel execution time, lowering the compute cost per generated token.
• Throughput Impact: Higher TPS enabled by KV cache means more tokens are processed per dollar of allocated hardware. Optimizing the KV cache is a direct action to reduce both cloud spend and latency.