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

1 Introduction

• Under tight active-cache budgets, eviction mistakes can disrupt reasoning, leading models to revisit completed work, loop, or fail to produce a final answer.Each generated token appends a key and value at every layer, making the reasoning trace a growing memory object.Source: §1 · p. 1
• Routing-oriented policies primarily assess whether keys will be read again or have nearby substitutes, but overlook value content and states not yet observed by later queries.Eviction removes both the retrieval address and its value, while a recent state may appear unimportant before later queries can use it.Source: §1 · p. 1
• A leave-one-out replay diagnostic finds the low-attention/high-payload region is enriched 2.4× in entries whose removal substantially changes future predictions.Figure 1 also illustrates low-attention states that receive strong reads only after the initial observation window, showing why early attention alone may be incomplete evidence for eviction.Source: §1 · p. 2, Figure 1 · p. 2
• AvoKV-E delays eligibility for recent states, then ranks eligible entries by read pressure, key redundancy, and value-payload potential using candidate-relative normalization.The training-free policy separates when an entry may be judged from how it is scored.Source: §1 · p. 2
• At matched active-KV budgets, AvoKV-E matches or outperforms redundancy-aware, recurrence-based, and thought-adaptive baselines, with its largest gains in the tightest-cache regime.Evaluations use DeepSeek-R1-Distill-Llama-8B and Qwen3-14B on MATH-500 and AIME-25; component ablations and counterfactual oracle analysis connect improvements to the method's components.Source: §1 · p. 2

2 Related Work

• Reasoning-cache methods use milestones or current-query importance, key redundancy, lagged recurrence, or thought-adaptive compression; AvoKV-E is closest to R-KV and LazyEviction but differs in using delay to set eligibility, not importance.Once eligible, AvoKV-E evaluates the risk of discarding both routing address and value content, without requiring a milestone detector or thought-regime classifier.Source: §2 · p. 3
• Attention-based methods infer future utility from attention history or short observation windows, while CAOTE estimates attention-output error; AvoKV-E uses an online value-norm proxy and delays scoring recent states.The cited attention-based methods include Scissorhands, H2O, StreamingLLM, TOVA, SnapKV, and NACL.Source: §2 · p. 3
• Budget-allocation methods change capacity across layers, heads, or queries, whereas this study holds allocation uniform to isolate token-level eviction under a fixed budget.AvoKV-E asks which generated reasoning states should remain once capacity has been specified.Source: §2 · p. 3
• Quantization reduces storage precision and PagedAttention changes memory organization; both are complementary to the studied eviction policy, which retains full-precision entries in a shared decoding harness.Source: §2 · p. 3

3 Problem Formulation

• At each compression checkpoint, a policy selects a keep set from the currently stored KV entries under an active KV budget.The supplied formulation identifies the cache entries and budget but does not specify further selection details in these passages.Source: §3 · p. 3
• Compression is causal: selection may use cached keys and values and attention observed up to the checkpoint, but not future queries or their attention patterns.Source: §3 · p. 3
• Future utility is incomplete at decision time: a recent low-attention entry may be expendable or merely too new to have been used, and eviction removes both its routing key and value.The policy must separately determine when an entry has enough causal evidence to be judged and how eligible entries should be ranked under the budget.Source: §3 · pp. 3–4

4 Method

• AvoKV-E separates eviction eligibility from ranking: it protects recent entries, then scores older candidates using read pressure, key redundancy, and value-payload potential.The score places the three signals on a candidate-relative scale.Source: Figure 2 · p. 4, §4 · p. 5

4.1 Delayed Causal Observation

• A new state stays protected until later queries have had a causal opportunity to reveal its utility; the delay controls eligibility rather than predicting importance.The observation window is used to measure read pressure, and the delay period is at least as long as that window.Source: §4.1 · p. 5

4.2 Payload-Aware Eviction Risk

• Eligible entries are ranked by candidate-percentile read pressure and payload potential minus key redundancy, with payload scored independently so large values can rescue low-read states.High read pressure and payload potential increase eviction risk, while high redundancy decreases it.Source: §4.2 · p. 6

4.3 Online Compression

• At a checkpoint, AvoKV-E reserves the protected set and fills the remaining active-budget slots with the highest-scoring eligible candidates.If the active cache is already within budget, it is returned unchanged.Source: §4.2 · p. 6, §4.3 · p. 6

• Observation determines which entries may be compared, while payload-aware ranking determines which eligible entries are safest to evict.Source: §14 · p. 7
• At each checkpoint, the method uses decoded-prefix attention rows, stored RoPE-transformed keys, and stored value norms to compute its signals.Source: §14 · p. 7
• Compression runs every 128 generated tokens, with W_delay set to 8 for budgets at or above 768 entries and 32 for budgets at or below 512.This configuration was selected on small MATH-100/MATH-200 pilots and reused across models, benchmarks, and budgets.Source: §14 · p. 7

5.1 Experimental Setup

• The evaluation uses two reasoning models and two mathematical benchmarks, with shared decoding controls and matched measured active-KV budgets.AvoKV-E’s configuration was selected on small MATH pilots and reused unchanged across both models, benchmarks, and reported budgets.Source: §5.1 · pp. 7–8

5.2 Accuracy and Termination under Matched Budgets

• AvoKV-E is best or tied-best across the shared budgets in all four model-task panels, with its largest advantages at the tightest budgets.As budgets grow, compressed policies converge toward FullKV.Source: Figure 3 · p. 8, §5.2 · pp. 8–9

5.3 Why Does AvoKV-E Work?

• AvoKV-E’s composite score has the strongest oracle-ranking metrics, including top-k recall, while using the same runtime budget as proxy scores.The ranking comparison uses single-token eviction-KL labels for 5,440 candidates; the five metrics improve simultaneously.Source: Table 3 · p. 9, §5.3 · pp. 9–10

5.2 Accuracy and Termination under Matched Budgets

• At budgets 256, 512, and 1024, AvoKV-E has the highest accuracy and fewest 32K-cap hits; at 512, it records 55 hits versus 78 for the next-best baseline.FullKV terminates on essentially every prompt, so remaining cap hits primarily reflect failures introduced by eviction.Source: §5.2 · p. 9, Table 2 · p. 9

5.3 Why Does AvoKV-E Work?

• Removing key redundancy causes the largest ablation loss at every tested budget, while removing payload scoring or delayed eligibility also consistently lowers accuracy.The payload and delay components address different routing-only limitations: which evidence is considered and when it becomes trustworthy.Source: §5.3 · p. 10
• Raw-score ablations degrade across all three budgets because read pressure, redundancy, and payload potential occupy different numerical ranges; the in-runner R-KV anchor tracks the official row within ≤1 point.These results support candidate-relative normalization and make a harness mismatch an unlikely explanation for AvoKV-E’s improvement.Source: §5.3 · p. 10, Table 4 · p. 10

6 Conclusion

• AvoKV-E is a training-free policy that separates delayed eligibility from payload-aware eviction risk.Its scoring combines candidate-normalized read pressure, key redundancy, and value-payload potential.Source: §6 · p. 10
• Across two reasoning models and two mathematical reasoning benchmarks, AvoKV-E matches or exceeds tested baselines at matched active-KV budgets, with its largest gains under tight budgets.Oracle ranking and component analyses connect the gains to preserving high-damage payloads, allowing late reads, and normalizing signals within the candidate set.Source: §6 · p. 10
• The results suggest reasoning-cache eviction should preserve both retrievable keys and the value payloads that sustain the reasoning trajectory.Source: §6 · p. 10

Limitations

• Evaluation covers DeepSeek-R1-Distill-Llama-8B and Qwen3-14B on MATH-500 and AIME-25; code and multimodal reasoning were not tested.Source: Limitations · p. 11
• The HuggingFace-generation prototype reports active-KV budgets and decoding behavior, not packed-memory savings or end-to-end throughput.Source: Limitations · p. 11
• AvoKV-E is an eviction policy; evaluation alongside low-bit KV quantization and hybrid eviction–quantization allocation is left as a next step.Source: Limitations · p. 11

A Worked Example

• Table 5 lists raw read-pressure, redundancy, and payload features, their within-candidate percentile ranks, and the resulting eviction-risk score.Its score is S_i = λ_p p̂_i − λ_r r̂_i + λ_b b̂_i; tied redundancy values for entries 1 and 3 receive averaged percentile ranks.Source: A Worked Example · p. 13, Table 5 · p. 13
• Among the informative pair, entry 1 has slightly higher read pressure, while entry 3 is barely read yet carries the largest value payload; entry 2 is read often and is not redundant.Entry 4 has the most replaceable key, so its high redundancy lowers its eviction-risk score despite moderate read pressure and payload.Source: A Worked Example · p. 13
• Removing the payload term changes the top-2 set from preserving entry 3 to selecting entries 2 and 1, evicting entry 3.The example illustrates how a low-read candidate’s payload can affect the eviction decision.Source: A Worked Example · p. 13

B Extended Positioning

• AvoKV-E isolates eviction and changes the score for deciding which active KV entries remain, without allocating precision, classifying thought regimes, or modifying the serving kernel.Table 6 groups related methods by primary cache signal and states what AvoKV-E adds or holds fixed relative to each family.Source: B Extended Positioning · p. 13, Table 6 · p. 14

Causal scoring

• All three scoring signals use information already in the prefix: attention rows for read pressure, RoPE-transformed candidate keys for redundancy, and stored value norms for payload.The method uses no future tokens, oracle labels, or auxiliary networks, allowing scoring during ordinary autoregressive decoding.Source: C Additional Reproducibility Details · p. 14

Configuration-selection rationale

• The pilot selected W_delay=8 at budget 1024 and W_delay=32 at budget 512; setting λ_b=0 costs several points, while λ_b much above ∼0.05 degrades behavior.The payload term is intended to rescue high-payload states and break ties among similarly routed candidates, while λ_r=0.9 keeps the score close to the R-KV family.Source: C Additional Reproducibility Details · pp. 14–15
• Scale-sensitive normalizers forfeited 3–11 points depending on budget, while percentile-rank and age-bucket-rank normalization were interchangeable in the pilots.Under the same pilot harness, the composite score was consistently best at both pilot budgets against R-KV+payload, a recency-weighted variant, and an R-KV-style anchor.Source: C Additional Reproducibility Details · p. 15

Artifacts and terms

• The evaluation uses publicly available pretrained models and math benchmarks for research, and does not redistribute model weights or benchmark contents.The passage lists licenses or credits for DeepSeek-R1-Distill-Llama-8B, Qwen3-14B, the Hugging Face Hendrycks MATH dataset, and AIME-25 sources.Source: C Additional Reproducibility Details · p. 15

Candidate pool and oracle damage

• The analysis pooled 892 candidate KV entries from five DeepSeek-R1-Distill-Llama-8B MATH/AIME traces; candidates were trace-position pairs with sufficient remaining horizon.Oracle damage was measured by replaying eight future decode steps with and without a candidate entry; high damage meant top-decile damage within its trace.Source: D Empirical foundations of Figure 1 · p. 15

Oracle damage and the attention-only blindspot

• 10/43=23% of low-attention, high-value-norm candidates were high-damage, versus 81/844=9.6% in the remaining cells, a 2.4× enrichment (p=0.009).The blindspot cell was the only significantly elevated cell outside the high-attention column; neither attention nor value-norm alone discriminated damaging from safe candidates.Source: D Empirical foundations of Figure 1 · pp. 15–16

Delayed first reads and the case for delayed observation

• F(4) was 51% versus 62% and F(16) was 56% versus 72% for low- versus high-attention candidates; 15% of low-attention candidates were never strongly read within 32 steps.The high-attention curve dominated throughout (one-sided Kolmogorov–Smirnov p=0.010), showing that short observation windows can precede later reads.Source: D Empirical foundations of Figure 1 · p. 16

Figure 1 takeaway

• Together, the panels indicate that snapshot attention misses a high-damage subpopulation and is unreliable at short lags; AvoKV-E addresses both with payload-aware scoring and delayed observation.The first-strong-read analysis includes 542 candidates with a 32-step horizon and right-censors lags at that cap.Source: D Empirical foundations of Figure 1 · p. 16