Dynamic KV Cache Eviction in Production: Architecture, Sparsity Policies, and Serving Trade-Offs

In long-context large language model serving, the key-value (KV) cache is the primary hardware bottleneck limiting concurrency and throughput. While model weights remain static during inference, KV cache memory scales linearly with sequence length, batch size, and layer count. For modern 70B parameter models utilizing Grouped-Query Attention (GQA), serving a 128,000-token context across a modest batch size of 4 requires over 80 GB of VRAM solely for KV states in 16-bit precision, exceeding the memory footprint of the weights themselves.

To bypass this memory wall, inference runtimes are increasingly deploying dynamic KV cache eviction and sparsity techniques. Rather than retaining every historical key-value pair across all layers, algorithms such as Heavy Hitter Oracle (H2O), SnapKV, and PyramidKV selectively prune redundant tokens. By exploiting attention sparsity, these methods can drop 70% to 90% of the cache footprint with minimal impact on retrieval accuracy and generation quality.

The Mechanics of Attention Sparsity

Empirical analysis of transformer self-attention reveals that attention matrices are heavily sparse. During autoregressive generation, query tokens allocate significant attention mass to three primary categories of historical positions:

1. Initial Attention Sinks: The first 4 to 32 tokens in a sequence absorb disproportionately large attention scores regardless of semantic relevance, acting as numerical anchors for the softmax denominator. Dropping them causes immediate perplexity collapse, as documented in StreamingLLM research.
2. Local Sliding Windows: The most recent $W$ tokens (typically 32 to 128 tokens) preserve local syntactic and grammatical coherence.
3. Heavy Hitters (Semantic Anchors): A sparse subset of historical prompt tokens that carry high contextual relevance to the ongoing generation.

Dynamic KV cache eviction operates by preserving initial sinks and local sliding windows unconditionally, while running selection policies to evict the remaining non-critical tokens from GPU memory.

Core Eviction Architectures

Heavy Hitter Oracle (H2O)

Introduced by Zhang et al. (2023), Heavy Hitter Oracle (H2O) implements an online dynamic eviction policy during autoregressive decoding.

H2O tracks the cumulative attention scores assigned to each key-value pair across all preceding decoding steps:

$$s_j = \sum_{t=1}^{T} \alpha_{t, j}$$

When the KV cache reaches a predefined budget $K$, H2O evicts the token with the lowest cumulative score $s_j$, excluding attention sinks and recent window tokens. Because token importance can evolve dynamically as generation shifts topics, H2O continuously updates scores at each step.

However, running online cumulative score updates and top-$k$ sorting at every decoding step introduces memory tracking overhead and non-trivial kernel latency when deployed in high-throughput engines.

SnapKV: Prefill-Phase Compression

SnapKV shifts the compression workload entirely to the prefill phase. The core insight behind SnapKV is that attention patterns stabilize during prompt processing: an observation window placed at the end of the prompt (the instruction tokens) can reliably predict which prefix tokens will remain critical during generation.

During prompt processing, SnapKV computes cross-attention from the observation window queries to all prefix keys. It applies a 1D pooling kernel (kernel size 5 to 7) over the attention scores to identify clustered feature locations rather than isolated tokens. SnapKV retains these clustered positions alongside sinks and observation tokens, discarding the remaining prefix KV entries before autoregressive generation begins.

Because eviction occurs once per request during prefill, SnapKV incurs zero sorting overhead during subsequent decoding steps.

PyramidKV: Pyramidal Information Funneling

A major limitation of both H2O and baseline SnapKV is uniform budget allocation: every transformer layer receives an identical KV cache capacity.

PyramidKV demonstrates that attention dynamics differ fundamentally across model depth:

• Lower Layers (0 to 25%): Focus almost entirely on local linguistic patterns and immediate token interactions. They require minimal historical context (low KV budget).
• Middle Layers (25% to 75%): Begin aggregating semantic relationships across broader spans.
• Upper Layers (75% to 100%): Exhibit broad, diffuse attention distributions across the entire sequence, requiring substantial memory capacity to synthesize global context.

By allocating KV cache budgets pyramidally (e.g., retaining 16 tokens in Layer 1 and scaling up to 1,024 tokens in the final layers), PyramidKV achieves equivalent or superior LongBench and Needle-in-a-Haystack performance while cutting overall memory consumption by up to 88% compared to full KV caches.

Adaptive Budgeting and Block-Level Eviction

More recent frameworks, such as Ada-KV and Quest, refine eviction granularity:

• Head-Wise Adaptivity: Different attention heads within the same layer exhibit divergent sparsity profiles. Retrieval heads require high capacity, while streaming heads focus solely on local windows. Ada-KV dynamically allocates token budgets across individual heads based on observation score variance.
• Block-Level Paged Eviction: In production systems using PagedAttention (such as vLLM and SGLang), memory is allocated in fixed blocks of 16 or 32 tokens. Evicting individual tokens creates intra-block fragmentation that cannot be returned to the global memory pool. Modern production implementations aggregate token scores to the block level, evicting entire physical memory pages to free contiguous GPU VRAM.

Production Trade-Offs and Failure Modes

Deploying dynamic KV eviction in enterprise workloads introduces specific architectural trade-offs:

1. Multi-Turn Agent Degradation: In agentic loops where tool outputs and user instructions alternate across multiple turns, prefill observation windows from turn $N$ may evict prompt instructions from turn 1. Systems serving stateful multi-turn agents must pin system prompts and tool schemas to prevent catastrophic forgetting.
2. The Out-of-Distribution Needle Failure: When a prompt contains arbitrary IDs, UUIDs, or exact numerical values that lack semantic clustering, observation window queries may fail to allocate sufficient attention during prefill. While methods like PyramidKV achieve 100% accuracy on standard synthetic benchmarks, complex real-world multi-hop reasoning can experience subtle degradation under extreme compression ratios (<10% cache budget).
3. Kernel Support and Custom Triton Kernels: Standard dense FlashAttention implementations assume contiguous tensor layouts. Running sparse KV caches requires custom gather kernels or sparse block pointers in Triton, which must be tuned across GPU architectures (Hopper, Ada Lovelace, Ampere) to prevent memory bandwidth bottlenecks.

Sources

• H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models (arXiv:2306.14048)
• SnapKV: LLM Knows What You Are Looking for Before Generation (arXiv:2404.14469)
• PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling (arXiv:2406.02069)
• Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference (arXiv:2407.11550)
• Efficient Streaming Language Models with Attention Sinks (StreamingLLM, arXiv:2309.17453)
• KVCache-Factory: Unified KV Cache Compression Methods (GitHub)