Value-Aware Stochastic KV Cache Eviction for Reasoning Models
Ting-Yun Chang Harvey Yiyun Fu Deqing Fu Chenghao Yang, Jesse Thomason Robin Jia · 2026
Read Value-Aware Stochastic KV Cache Eviction for Reasoning Models by Ting-Yun Chang Harvey Yiyun Fu Deqing Fu Chenghao Yang, Jesse Thomason Robin Jia (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03928.txt.
Introduction
Chang and co-authors tackle the memory cost of long reasoning traces. Models that think step by step store key and value pairs for each token. Dropping weak pairs saves space but can hurt accuracy. Keeping all pairs, as sparse attention does, costs more. They look for what makes eviction fail or succeed.
They find a few value states have huge size. Dropping those states can trap a model in repeat loops. Random choice in what to drop also helps, they note. Their VaSE method guards the large states and adds that randomness. It needs no new training. On six tasks with Qwen3 models, VaSE beat prior eviction by over four points. It also topped a leading selection method at the same sparsity.
Catalog record
| CREATOR | Ting-Yun Chang Harvey Yiyun Fu Deqing Fu Chenghao Yang, Jesse Thomason Robin Jia |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.03928
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Value-Aware Stochastic KV Cache Eviction for Reasoning Models Ting-Yun Chang Harvey Yiyun Fu Deqing Fu Chenghao Yang, Jesse Thomason Robin Jia Abstract Reasoning models improve accuracy through extended chains of thought, but their long outputs create a memory and compute bottleneck. KV cache eviction methods reduce this cost by evicting unimportant key-value pairs from the cache, yet they often yield worse accuracy than selection-based sparse attention alternatives, which keep the full KV cache. We identify key factors crucial to KV cache eviction accuracy. First, a small fraction of value states have abnormally large magnitudes, and evicting them causes catastrophic failure where models enter repetitive reasoning loops. Second, introducing stochasticity during eviction improves accuracy by increasing cache diversity. Based on these findings, we propose V alue- a ware S tochastic KV Cache E viction ( VaSE ), a training-free recipe that protects large-magnitude value states and promotes diverse eviction decisions. Across six reasoning tasks, Qwen3 models using VaSE with 4 × 4\times KV cache compression yield higher average accuracies than SOTA selection method at the same sparsity, while outperforming the strongest eviction method by more than 4%. Overall, VaSE bridges the gap between efficiency and accuracy, supporting FlashAttention2 and enabling a static memory footprint for reasoning models. Figure 1: Top : VaSE is a KV Cache eviction method that combines stochastic sampling with value-state magnitude scoring to retain diverse and important KV pairs under a fixed KV cache budget. Bottom : By integrating both stochasticity and value awareness, VaSE outperforms baseline methods that use either signal alone, improving average pass@1 accuracy across various reasoning tasks. 1 Introduction Reasoning models ( 32 ; 34 ; 16 ) leverage test-time compute ( 40 ) to improve accuracy by generating extended chains of thought before producing a final answer. While this approach yields high accuracy on complex tasks, it introduces an efficiency bottleneck at test time because the reasoning models tend to generate unnecessary long outputs. For example, 7 show that models may overthink a simple arithmetic question, using more than 900 tokens to answer “2 + 3 = ?”. As a consequence, an auto-regressive large language model that stores the key-value representations of every past token incurs substantial memory and computational overhead as the sequence length grows. Sparse attention ( 52 ; 3 ; 49 ; 26 ) addresses this bottleneck by attending to only a subset of previous tokens; such approaches fall into two broad categories. KV cache selection methods ( 36 ; 44 ; 48 ; 14 ) keep the full KV cache in memory but activate only a sparse subset of KV pairs at each decode step. These methods reduce compute and memory movement, but their memory footprints scale linearly with sequence length. In contrast, KV cache eviction methods ( 51 ; 15 ; 12 ; 33 ) permanently discard low-importance KV pairs once the cache reaches a predefined budget. While eviction methods ( 28 ; 4 ) suffer larger accuracy degradation on reasoning tasks compared to their selection-based counterparts, they can yield a static memory footprint and better throughput. In this paper, we reveal two key findings to improve KV cache eviction methods on reasoning models. First, the magnitudes of value states show strongly skewed distributions, with a small fraction of tokens having abnormally large vector magnitudes (see Figure 2 ). Those large-magnitude value states are crucial for maintaining task accuracies: evicting them causes the models to enter repetitive loops, where they endlessly re-examine the context or generate nonsensical outputs without reaching a final answer (see Figure 9 for the examples). Second, we find that introducing stochasticity during KV cache eviction effectively improves reasoning task accuracies. We attribute this to improved diversity of the retained KV pairs, which together yield a more representative coverage of the full context. Our case study on GSM8K demonstrates that incorporating value scoring boosts Qwen3-4B’s accuracy by as much as 16.2%, while introducing stochasticity yields an additional 4.7% improvement. Building on these findings, we propose V alue- a ware S tochastic KV Cache E viction ( VaSE ), a training-free KV cache eviction recipe that prioritizes large-magnitude value states and introduces stochasticity during eviction. We target the decoding step of reasoning models, by applying VaSE to Qwen3 models ( 47 ) and evaluating on six tasks spanning math, code generation, and science question answering. On average, VaSE outperforms the previously SOTA eviction method R-KV ( 4 ) by 4.4% on Qwen3-4B and 4.9% on Qwen3-14B. When combined with CurDKV ( 38 ) , stochastic sampling further boosts its average accuracy by 7.7% and 9.2% on the two models, respectively. VaSE even slightly surpasses the average accuracy of SeerAttention-R ( 14 ) , a strong selection method whose KV cache memory grows linearly with the sequence length, on both models while using static memory. In addition, we benchmark the actual throughput and peak memory of different methods, showing that VaSE achieves higher throughput and a lower memory footprint than the R-KV eviction baseline across token budgets. Our results match closely with the theoretical memory compression ratio. Furthermore, our insights generalize to other efficiency methods like KV cache quantization; we show that large-magnitude value states also lead to disproportionately large reconstruction errors under per-token quantization ( 31 ) . Together, we demonstrate that value-state magnitude and stochasticity are fundamental axes of KV cache management, with our VaSE recipe bridging the efficiency-accuracy gap left by prior sparse attention methods. 1 1 1 Our code is available at https://github.com/terarachang/VaSE . 2 Problem Setup We formalize the decode-phase KV cache eviction setting by drawing the distinction between selection-based and eviction-based methods, and introduce several representative eviction baselines. Selection-based method. Selection-based sparse attention methods retain the full KV cache but activate only a sparse subset of KV pairs at each decoding step. A representative example is SeerAttention-R ( 14 ) , which uses a trained attention gate to predict attention sparsity patterns and selectively activates different KV cache blocks during inference, thereby reducing computational complexity and memory movement. Compared to eviction-based methods, SeerAttention-R retains all KV pairs and the memory footprint scales linearly as \mathcal{O}(T) with sequence length T . Eviction-based method. KV cache eviction methods permanently discard low-importance key-value pairs once the cache size reaches a predefined budget, reducing memory cost at the risk of irrecoverable information loss. We specifically focus on eviction methods for the decoding step of autoregressive reasoning models, as these models can generate over 10{,}000 tokens for a math question that has fewer than 200 prompt tokens (see Table 4 for statistics). Formally, let N be the total KV cache budget, and d be the dimension of keys and values. As the KV cache budget fills up at the token index t , we have N KV pairs ({\bm{k}}_{i},{\bm{v}}_{i}) for i=1,\ldots,N , where {\bm{k}}_{i}\in\mathbb{R}^{d},{\bm{v}}_{i}\in\mathbb{R}^{d} . Given the current query {\bm{q}}_{t}\in\mathbb{R}^{d} , the attention head computes its output as a weighted sum over the N cached values, {\bm{o}}_{t}\;=\;\sum_{i\leq N}\alpha_{i}^{(t)}\,{\bm{v}}_{i},\qquad\alpha_{i}^{(t)}\;=\;\frac{\exp\!\left({\bm{q}}_{t}^{\top}{\bm{k}}_{i}/\sqrt{d}\right)}{\sum_{j\leq N}\exp\!\left({\bm{q}}_{t}^{\top}{\bm{k}}_{j}/\sqrt{d}\right)}, (1) where \alpha_{i}^{(t)} is the attention weight assigned to token i , obtained by applying softmax to the scaled dot products between the current query and all cached keys ( 45 ) . Periodic eviction with budget K and buffer B . We adopt the periodic-eviction