KV Cache

During text generation, each new token requires attention over all previous tokens. Without caching, the model would recompute Keys and Values for the entire sequence at every step, resulting in O(n²) computational complexity. The KV Cache stores these tensors in GPU memory, reducing per-step computation to O(n) by only calculating attention for the newest token against the cached history. This transforms generation from quadratic to linear time complexity relative to sequence length.

The cache grows linearly with batch size, sequence length, number of layers, and hidden dimensions. For a 70B parameter model serving 64 concurrent requests at 4096 tokens each, the KV Cache can consume hundreds of gigabytes of GPU memory. This memory pressure often becomes the primary constraint on serving throughput, not compute. Techniques like PagedAttention and multi-query attention directly target this bottleneck by reducing per-token memory footprint and enabling efficient memory sharing across sequences.

Traditional KV Cache implementations allocate contiguous memory blocks per sequence, leading to fragmentation and underutilization. PagedAttention, introduced by the vLLM project, treats the cache like virtual memory in operating systems:

• Partitions cache into fixed-size blocks that can be mapped non-contiguously
• Enables memory sharing across sequences for identical prompt prefixes
• Reduces waste from overallocation by up to 80%
• Allows near-optimal GPU memory utilization under dynamic batching workloads

When multiple requests share a common system prompt or few-shot examples, the KV tensors for that prefix are identical. Prefix-aware caching computes and stores these once, then reuses them across all requests. This technique:

• Eliminates redundant computation for shared prefixes
• Reduces time-to-first-token for common prompt templates
• Is especially impactful for chat applications with long system instructions
• Requires careful cache keying based on token-level prefix matching

To further reduce memory pressure, the cached Key and Value tensors can be stored at lower precision than the model weights. KV Cache quantization typically uses:

• INT8 or FP8 formats instead of FP16/BF16
• Per-channel or per-token quantization granularity
• Calibration-based scaling factor determination This can reduce cache memory by 50% with negligible accuracy degradation, enabling larger batch sizes or longer context windows on the same hardware. Libraries like TensorRT-LLM and llama.cpp implement this natively.

For extremely long sequences exceeding available memory, sliding window attention restricts the cache to only the most recent tokens. Key strategies include:

• Fixed window: Retain only the last W tokens, discarding older context
• Sink token preservation: Keep initial tokens as attention sinks while sliding the window
• StreamingLLM: Maintains stable perplexity by preserving a small set of initial tokens alongside the sliding window These policies trade full-context recall for bounded memory usage, enabling theoretically infinite-length generation.