AvoKV-E: Payload-Aware KV Cache Eviction for Long Reasoning

Han Yu; Wenhui Zhu; Xiwen Chen; Zhipeng Wang; Hejian Sang; Han Shi; Menglin Zhou; Xuanzhao Dong

cs.LGOct 2, 2026

AvoKV-E: Payload-Aware KV Cache Eviction for Long Reasoning

Authors: Han Yu, Wenhui Zhu, Xiwen Chen, Zhipeng Wang, Hejian Sang, Han Shi, Menglin Zhou, Xuanzhao Dong,

Organizations: LinkedIn Corporation · Clemson University · Rice University · Arizona State University

Abstract

Long-output reasoning shifts the KV-cache bottleneck from the fixed prompt to the generated trace. Existing reasoning-cache eviction methods largely treat cached entries as routing objects, estimating whether an old key will still be read, will recur, or can be replaced. This routing-only view overlooks two effects: low-attention entries can carry large value payloads whose removal changes future predictions, and newly generated states can appear stale before later queries have had a chance to read them. We introduce AvoKV-E, a training-free eviction policy that first delays eligibility for recent states and then ranks eligible entries using candidate-normalized read pressure, key redundancy, and value-payload potential. According to empirical evaluation across different models and datasets, AvoKV-E matches or exceeds redundancy-aware, recurrence-based, and thought-adaptive eviction baselines at matched active-KV budgets, with its largest gains in the tightest-cache regime. Component and counterfactual analyses further connect these gains to delayed observation, payload-aware scoring, redundancy, and scale-robust normalization. Together, the results show that long-reasoning KV eviction should preserve not only keys that are likely to be read, but also the value payloads that sustain the reasoning trajectory.

Figures & tables

Figure 1: Diagnostic evidence for two failure modes of routing-only eviction. (a) Some low-attention entries with large value payloads are nevertheless high-damage to remove, revealing an attention-only blindspot . (b) Some low-attention entries receive strong reads only after the initial observation window, so early eviction can confuse “not yet read” with “not useful.” Detailed construction, counts, and statistical tests are given in Appendix D .

Symbol	Description
$t$	current decode step / compression checkpoint
$\mathcal{I}_{t}$	active cache entries before compression
$L,H$	number of layers and attention heads
$k_{i}^{\ell,h},v_{i}^{\ell,h}$	key/value of entry $i$ at layer $\ell$ , head $h$
$a_{\tau,i}^{\ell,h}$	attention from query $\tau$ to entry $i$
$W_{\mathrm{obs}}$	observation-window length

Table 1: Notation used in the problem formulation, method, and analysis.

Figure 2: Overview of AvoKV-E. Recent entries in the delay buffer

P_{t}

are temporarily protected. Older eligible candidates in

C_{t}

are ranked by a scale-robust score

S_{i}(t)

that combines read pressure

p_{i}

, key redundancy

r_{i}

, and value-payload potential

b_{i}

. The top-scoring entries are retained under active budget

B

Figure 3: Accuracy versus active KV budget for DeepSeek-R1-Distill-Llama-8B (top row) and Qwen3-14B (bottom row) on MATH-500 (left column) and AIME-25 (right column); AIME-25 reports mean accuracy over

16

samples per problem. FullKV is the dotted uncompressed reference. At matched budgets, AvoKV-E matches or exceeds the redundancy-aware R-KV, recurrence-based LazyEviction, and thought-adaptive ThinKV (impl.) baselines, with the largest gaps at the smallest budgets.

Headline accuracy on MATH-500 / R1-8B (%)
Method	256	512	1024
FullKV	–	–	–
R-KV	105	78	60
LazyEviction	112	85	65
ThinKV (impl.)	119	92	70
AvoKV-E	102	55	50

Table 2: Max-length hit counts at the

32

K cap (out of

500

MATH-500 problems) and headline accuracy at three representative KV budgets on DeepSeek-R1-Distill-Llama-8B. FullKV terminates well within

32

K on essentially every problem. Among compressed methods, AvoKV-E achieves both the fewest max-length hits and the highest accuracy at each budget.

Score	AUROC	AP	Top- $k$ recall	False-safe rate	Spearman
attention only	0.891	0.369	0.621	0.033	0.322
R-KV-style proxy	0.894	0.372	0.629	0.026	0.303
ThinKV-style proxy	0.892	0.350	0.610	0.022	0.303
attention $\times$ age	0.891	0.362	0.621	0.022	0.268
AvoKV-E (full score)	0.901	0.388	0.658	0.020	0.331

Table 3: Oracle ranking quality against the single-token eviction-KL label on

5{,}440

candidates. AvoKV-E’s composite score has the strongest ranking metrics across the board while remaining within the same runtime budget as the proxy scores.

Variant	256	512	1024
AvoKV-E	68.4	81.4	82.6
$-$ payload ( $\lambda_{b}{=}0$ )	66.8	78.8	80.0
$-$ delay ( $W_{\mathrm{delay}}{=}W_{\mathrm{obs}}$ )	66.4	79.6	81.0
$-$ rank norm. (raw)	64.2	76.8	78.7
$-$ redundancy ( $\lambda_{r}{=}0$ )	60.5	73.4	76.4
R-KV-style anchor (in-runner)	66.6	76.4	80.2

Table 4: Component decomposition of AvoKV-E on MATH-500 with DeepSeek-R1-Distill-Llama-8B. Accuracy is reported at matched active-KV budgets. The in-runner R-KV-style anchor uses the same HuggingFace harness with the R-KV score and tracks the official R-KV row to within

\leq 1

point at every budget.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Raw features
$i$	1	2	3	4
	I	cook	dinner	myself
$p_{i}$ (read pressure)	0.04	0.81	0.02	0.05
$r_{i}$ (key redundancy)	0.55	0.41	0.55	0.92
$b_{i}$ (value payload)	0.55	0.62	2.10	1.20
Percentile-rank normalized

Appendix

Table 5: Worked example at one compression checkpoint. The score is

S_{i}=\lambda_{p}\,\hat{p}_{i}-\lambda_{r}\,\hat{r}_{i}+\lambda_{b}\,\hat{b}_{i}

. Scores are rounded to two decimals. The tied redundancy values for entries 1 and 3 are assigned the averaged percentile rank, following the definition of

N_{t}

Family	Representative work	Main cache signal	Relation to AvoKV-E
Attention retention	H2O ( Zhang et al., 2023 ) , StreamingLLM ( Xiao et al., 2023 ) , Scissorhands ( Liu et al., 2023 ) , TOVA ( Oren et al., 2024 )	Recent attention, heavy hitters, sinks, or persistence	Also uses attention, but delays eligibility (delayed-read effect) and adds value-payload potential (attention-only blindspot).
Observation-window eviction	SnapKV ( Li et al., 2024 ) , NACL ( Chen et al., 2024 )	Attention statistics over a short observation window	Causal observation window applied during generated reasoning rather than only prompt-side selection.
Budget allocation	FastGen ( Ge et al., 2024 ) , PyramidKV ( Cai et al., 2024 ) , Ada-KV ( Feng et al., 2024 ) , HeadKV ( Fu et al., 2024 ) , Quest ( Tang et al., 2024 ) , DuoAttention ( Xiao et al., 2024 )	Layer/head/query-aware allocation of limited cache capacity	Allocation is held fixed; we study the token-level eviction score, so this axis is orthogonal.
Reasoning-cache compression	RaaS ( Hu et al., 2025 ) , R-KV ( Cai et al., 2025 ) , LazyEviction ( Zhang et al., 2025 ) , ThinKV ( Ramachandran et al., 2025 ) , LongFlow ( Su et al., 2026 )	Reasoning milestones, redundancy, lagged recurrence, thought regimes, or current-query importance	Closest baselines. Unlike LazyEviction, delay only defines eligibility while payload-aware scoring drives the keep decision; unlike ThinKV, no thought classifier or quantization.
Quantization & serving	KIVI ( Liu et al., 2024 ) , KVQuant ( Hooper et al., 2024 ) , PM-KVQ ( Liu et al., 2025 ) , TurboQuant ( Zandieh et al., 2025 ) , PagedAttention ( Kwon et al., 2023 )	Lower precision or more efficient cache storage	Complementary; we disable quantization in our experiments to isolate the eviction decision.

Appendix

Table 6: Positioning of AvoKV-E among related KV-cache methods. Each row groups methods by their primary cache signal; the right-most column states what AvoKV-E adds or holds fixed relative to that family.

KV-Cache Eviction

Key-value (KV) cache eviction reduces language-model memory use by removing or compressing cached tokens while preserving useful context.

See all 97 papers

Value-Aware Stochastic KV Cache Eviction for Reasoning Models
Jun 2, 2026Ting-Yun Chang, Harvey Yiyun Fu, Deqing Fu +3LLM Inference Efficiency KV Caching
University of Southern California · University of Chicago
Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction
May 10, 2026Ngoc Bui, Hieu Trung Nguyen, Arman Cohan +1Self-Attention KV Caching
Department of Computer Science, Yale University · The Chinese University of Hong Kong
Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning
Sep 3, 2026Heng Wang, Jielin Qiu, Wenting Zhao +8KV Caching Memory-Efficient Optimization
Salesforce AI Research · University of Illinois Urbana-Champaign

Jun 2, 2026J/K move · Enter open · S save

Value-Aware Stochastic KV Cache Eviction for Reasoning Models

Ting-Yun Chang, Harvey Yiyun Fu, Deqing Fu, Chenghao Yang+2

University of Southern California · University of Chicago

LLM Inference Efficiency KV Caching Memory-Efficient Optimization KV-Cache Eviction KV-Cache Compression Large Reasoning Models

Open paper AskPDF arXiv

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 Value-aware Stochastic KV Cache Eviction (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 4x 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.

Abstract

KV-Cache Eviction

Explore similar work

Value-Aware Stochastic KV Cache Eviction for Reasoning Models

Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction

Random Attention: Rethinking KV Cache Eviction for Efficient Reasoning