Technical Summary: Value-Aware Stochastic KV Cache Eviction for Reasoning Models

1. Problem Statement

Reasoning models (e.g., Qwen3, OpenAI's o1) achieve high accuracy by generating extended chains of thought before producing a final answer. However, this capability creates a significant memory and computational bottleneck during the decoding phase. As the sequence length grows, the Key-Value (KV) cache required to store representations of every past token incurs substantial overhead.

Existing solutions fall into two categories:

• Selection-based methods: These retain the full KV cache but activate only a sparse subset of tokens during attention computation. While accurate, their memory footprint scales linearly with sequence length ($O(T)$), failing to solve the memory bottleneck.
• Eviction-based methods: These permanently discard low-importance KV pairs once a predefined budget is reached, offering a static memory footprint and better throughput. However, current eviction methods suffer from significant accuracy degradation on reasoning tasks compared to selection-based alternatives, often causing models to enter repetitive reasoning loops or generate nonsensical outputs.

The paper identifies that current eviction strategies fail to account for two critical factors: the disproportionate influence of large-magnitude value states and the need for stochastic diversity in retained tokens.

2. Methodology: VASE

The authors propose Value-Aware Stochastic KV Cache Eviction (VASE), a training-free eviction framework designed to bridge the gap between efficiency and accuracy. VASE operates within a periodic eviction framework (using a persistent budget $K$ and a recent buffer $B$) and introduces two core mechanisms:

A. Protection of Large-Magnitude Value States

The authors observe that value states in reasoning models exhibit a strongly skewed distribution, where a small fraction of tokens possess abnormally large vector magnitudes (measured by the range $Range(v) = \max(v) - \min(v)$).

• Finding: Evicting these high-magnitude values causes catastrophic accuracy collapse (e.g., dropping from ~88% to 14% on GSM8K) and induces repetitive loops where the model endlessly re-examines context without reaching a conclusion.
• Mechanism: VASE reserves a specific portion of the token budget ($N_v$) to unconditionally retain the $N_v$ tokens with the largest value magnitudes. This ensures that the most influential value vectors are never discarded.

B. Introduction of Stochasticity

Current eviction methods often use deterministic top-$k$ selection, which can lead to a lack of diversity in the retained cache.

• Finding: Introducing stochasticity improves accuracy by ensuring a more representative coverage of the full context.
• Mechanism: Instead of deterministically selecting the top-scoring tokens, VASE employs weighted stochastic sampling.
  • VASE-AttnV: Combines the value-aware reservation with stochastic sampling based on attention scores (derived from SnapKV).
  • VASE-DKV: Adapts the CurDKV method (which uses leverage scores from CUR matrix decomposition) by resampling the Gaussian projection matrix $G$ at every eviction step. This prevents tokens with specific representations from being consistently assigned low scores and permanently evicted.

3. Key Contributions

1. Identification of Critical Factors: The paper establishes that (1) large-magnitude value states are crucial for maintaining reasoning progression and preventing repetitive loops, and (2) stochasticity in eviction decisions significantly boosts accuracy by increasing cache diversity.
2. VASE Framework: A novel, training-free eviction recipe that integrates value-state magnitude protection and stochastic sampling. It is the first eviction method to combine key-based scoring, value-based scoring, and diversity promotion.
3. Connection to Quantization: The authors demonstrate that large-range value states are also the primary source of reconstruction error in per-token KV cache quantization, suggesting that VASE's insights generalize to other compression techniques.

4. Experimental Results

The authors evaluated VASE on Qwen3-4B and Qwen3-14B across six reasoning tasks (AIME25/26, HMMT25, GPQA-Diamond, MATH, LiveCodeBench-v6) with a 4× KV cache compression ratio.

• Accuracy vs. Selection Methods: VASE-AttnV achieved higher average accuracy than the strongest selection-based method (SeerAttention-R) on both model sizes while maintaining a static memory footprint.
  • Qwen3-4B: VASE-AttnV (59.09%) outperformed SeerAttention-R (58.81%) and the strongest eviction baseline R-KV (54.69%) by 4.4%.
  • Qwen3-14B: VASE-AttnV (65.81%) matched SeerAttention-R (65.37%) and outperformed R-KV (60.90%) by 4.9%.
• Ablation Studies:
  • Value Awareness: Reserving slots for large-magnitude values improved GSM8K accuracy by up to 16.2% over baselines.
  • Stochasticity: Adding stochastic sampling to CurDKV improved accuracy by 9.2% on Qwen3-14B.
• Efficiency: VASE-DKV achieved the highest throughput (3.1× faster than the full model baseline at 16K tokens) and the lowest peak memory usage among all tested methods.
• Code Generation: On LiveCodeBench, VASE methods significantly outperformed the selection-based SeerAttention-R, which struggled with domain shifts.

5. Significance and Claims

The paper claims that VASE successfully bridges the efficiency-accuracy gap that has historically plagued KV cache eviction methods. By prioritizing large-magnitude value states and introducing stochasticity, VASE enables reasoning models to operate with a static memory footprint without sacrificing the accuracy typically associated with full-cache or selection-based approaches.

The authors emphasize that their findings regarding the importance of value-state magnitude have broader implications beyond eviction, specifically for KV cache quantization, where large-range values are identified as a primary source of error. They suggest that future memory-efficient inference methods should consider mixed-precision approaches that protect these critical high-magnitude states.

Ultimately, VASE provides a simple, effective, and training-free recipe to support FlashAttention2 and enable scalable inference for long-chain reasoning models.