PaperlayerView exact revision on arXiv

Source-linked AI summary

What Matters for Aggressive Decoding-Time KV Eviction? Temporal Aggregation and Ranking Preservation

Bo Zeng, Yu Zhao, Yefeng Liu, Zhihong Lu, Xuanfan Ni, Xintong Wang

arXiv:2609.03515v1cs.AI

TL;DR

The paper asks whether aggressive decoding-time KV eviction quality is governed mainly by token scoring or by how scores are aggregated over layers and decode steps. It isolates temporal aggregation with EMA, then evaluates lazy and score-free operating points across models and long-context benchmarks. The results show that ranking-preserving scorer changes often leave eviction sets unchanged, while periodic refresh reaches 1.34–1.46× throughput and Score-Free changes average quality by +0.03.

  • Problem

    Prior work rarely isolates scoring from temporal aggregation, leaving open which axis governs quality under aggressive KV budgets.

  • Method

    The paper evaluates sequential layer–temporal EMA aggregation, introduces InertiaKV and periodic-refresh InertiaKV-Lazy, and separately freezes the first-step ranking for Score-Free decoding.

  • Results

    Across the evaluated models and benchmarks, approximately order-preserving scorer changes produce similar retention sets, InertiaKV-Lazy provides 1.34–1.46× decode throughput, and Score-Free changes average quality by +0.03.

  • Takeaways & Limitations

    Temporal aggregation and ranking preservation are consequential design factors under aggressive compression, without implying that scoring quality is generally irrelevant.

  • Takeaways & Limitations

    Score-Free may fail when relevance shifts later in generation, and InertiaKV methods do not reduce prefill peak memory.

Abstract

from arXiv · show

Decoding-time KV cache compression research focuses heavily on designing better token scoring functions, while the temporal rule that aggregates scores across decode steps is often treated as an implementation detail. Under aggressive KV compression, we find that exponential-moving-average (EMA) aggregation makes approximately order-preserving scorer modifications largely indistinguishable at the eviction-set level. Value-norm and entropy variants remain highly correlated with attention and produce nearly unchanged retention sets, whereas KeyDiff, key norm, recency, and a learned scorer alter the ranking and degrade substantially. We associate this stability with the evaluated aggregation, which couples layer weighting and temporal retention. Building on this observation, we introduce InertiaKV, an EMA-based decoding-time eviction method, and InertiaKV-Lazy, its periodic-refresh variant, which yields 1.34-1.46x decode throughput relative to full refresh InertiaKV. We also study Score-Free decoding as a separate empirical operating point: it scores the full context once at the first decode step, freezes that ranking, and incurs an average quality change of +0.03 while removing all subsequent scoring. Across six open-weight backbones and the LongBench, LongBench-v2, and RULER benchmarks, the results identify temporal aggregation and ranking preservation as distinct, consequential design factors; they do not imply that scoring quality is irrelevant in general.

1 Introduction

The paper shifts attention from token scoring functions to temporal aggregation under aggressive KV compression, where approximately rank-preserving changes can leave eviction sets unchanged. It introduces EMA-based operating points that trade adaptation for stability and efficiency.

  • Motivation: Decoding-time KV compression jointly involves per-step scoring and aggregation across layers and decode steps, but prior work emphasizes scoring.The aggregation rule determines the running utility estimate that drives irreversible eviction.
  • Motivation: At aggressive compression, TOVA, SnapKV, and AdaKV all degrade substantially as the RULER KV budget shrinks from 50% to 10%.Their different scoring functions nevertheless show shared degradation, motivating isolation of scoring from temporal aggregation.
  • Main finding: EMA makes approximately order-preserving scorer modifications largely indistinguishable at the eviction-set level under the evaluated sequential aggregation.This pattern holds across Qwen2.5-7B, Llama-3.1-8B, and Llama-3.3-70B on LongBench, LongBench-v2, and RULER.
  • Operating points: 1.34–1.46× decode speedup is achieved by InertiaKV-Lazy relative to full-refresh InertiaKV through periodic score refreshes.The paper treats refresh frequency as an explicit quality–efficiency control.
  • Operating points: Score-Free freezes the first decode-step ranking, eliminates later score updates, and shows an average quality change of +0.03 points.This is presented as a separate empirical operating point rather than evidence that scoring quality is generally irrelevant.
  • Tradeoff: Stronger temporal smoothing stabilizes eviction decisions but can delay adaptation to relevance shifts, creating a boundary-error versus lag-error tradeoff.The paper also reports that local noise and drift alone cannot reliably guide adaptive smoothing.

2 Related Work

Prior KV eviction work mainly develops better scoring signals, while temporal aggregation has usually remained an implementation choice. The paper positions aggregation as a distinct design axis and illustrates EMA’s retention-set stability for correlated scorers.

  • Decode-time eviction methods: H2O, ScissorHands, TOVA, and later methods progressively refine attention-based, persistence-based, single-step, or adaptive scoring signals.The related work frames this progression around score-and-evict methods under fixed budgets.
  • EMA stability: EMA yields near-identical retention sets for Attention, Value Norm, and Entropy, with mean pairwise Jaccard 0.97 over top-B token sets.The figure compares per-step and EMA-smoothed scoring across decode steps and layers.
  • Temporal perspectives: Temporal aggregation has generally remained a background implementation choice rather than an object of study in its own right.Prior systems use cumulative sums, sliding windows, or implicit single-step aggregation.
  • Temporal perspectives: FAEDKV treats temporal dynamics explicitly through frequency-domain debiasing, but improves the scoring signal rather than decoupling scoring from aggregation.This distinguishes its contribution from the paper’s focus on the aggregation mechanism.
  • Adjacent regimes: Prefill-time selection and sparse-attention systems operate outside the irreversible decode-time eviction regime.SnapKV selects tokens during prefill, while sparse attention loads subsets without permanently removing KV pairs.
  • Orthogonal dimensions: Quantization, cross-layer sharing, layer-wise budget shaping, reconstruction, and hardware-efficient attention are orthogonal or composable dimensions rather than substitutes for the studied aggregation question.These methods reduce cache size or per-step cost through mechanisms distinct from temporal eviction.

3 Method

The method uses decode-time EMA utilities to make irreversible eviction decisions, then exploits ranking persistence through periodic refresh or one-time scoring. Its design explicitly balances stability against adaptation to relevance shifts.

  • Compression setting: Under compression ratio ρ, the decode-side budget is B = ⌊(1−ρ)L0⌋, and evicted KV pairs cannot be recovered.This defines the aggressive decode-time setting.
  • Utility and eviction: Per-token importance is mean-pooled across attention heads into a utility vector, and tokens with the lowest utility are evicted when the cache exceeds B.The utility vector estimates aggregated token importance through the current decode step.
  • Temporal aggregation: EMA interpolates between noisy single-step scoring and slow-to-adapt cumulative scoring with bounded memory.Its coefficient α also controls persistence across decode steps and the relative influence of successive transformer layers.
  • Stability–adaptivity tradeoff: Aggressive compression exposes boundary errors from noisy fluctuations and lag errors from stale utilities after relevance shifts.The paper uses this decomposition as a qualitative design lens rather than a formal objective.
  • InertiaKV: InertiaKV applies decode-side EMA with α=0.8 and a proportional budget, using ranking inertia to absorb per-step scoring perturbations.Compression occurs during decoding, making the method query-aware but not a prefill memory reduction.
  • Lazy refresh: InertiaKV-Lazy refreshes scores at the first decode step and every r steps thereafter while continuing eviction whenever the cache exceeds B.Skipping score observations on non-refresh steps creates a quality–speed tradeoff evaluated empirically.
  • Score-Free: Score-Free computes full-context scores at the first decode step, freezes the resulting ranking, and performs no later score computation while eviction continues.Its effectiveness is an empirical observation about evaluated workloads, not a universal claim about first-step rankings.

4 Experimental Setup

The evaluation spans open-weight models with different GQA configurations, aggressive 90% compression, and benchmarks covering long-context understanding, retrieval, and synthetic stress cases. Baselines represent diverse decode-time, prefill-time, adaptive, geometric, and reconstruction-based methods.

  • Benchmarks: LongBench covers extractive QA and generation, while RULER includes 13 synthetic subtasks spanning retrieval, variable tracking, and word extraction.Multi-evidence retrieval subtasks are especially challenging because they require retaining dispersed tokens simultaneously.
  • Models: The main evaluation uses Llama-3.1-8B-Instruct and Qwen2.5-7B-Instruct, with Llama-3.3-70B-Instruct included for scale testing.The main models use distinct grouped-query attention configurations.
  • Baselines: Baselines include TOVA, SnapKV, AdaKV with Expected Attention, KeyDiff, and KVzip, alongside full-refresh InertiaKV and InertiaKV-Lazy variants.The comparisons use 90% compression, where temporal effects are most pronounced in the experiments.

5 Results

Under aggressive compression, EMA absorbs approximately order-preserving scorer changes but is sensitive to ranking-altering changes; reducing refresh frequency can preserve quality while improving efficiency.

  • Aggregation baseline: EMA substantially outperforms single-step aggregation on retrieval-heavy settings, improving LongBench by +1.8 and RULER by +21.6 on Llama.Cumulative aggregation is competitive but mixed across models and benchmarks.
  • Order-preserving perturbations: On Llama-3.3-70B, VNorm deviates from EMA by at most 0.67 points, whereas α=0 drops by 7.37 points on average.The contrast changes both layer weighting and temporal retention, rather than momentum alone.
  • Ranking preservation: VNorm and entropy preserve ranking with ρ ≈0.97, whereas KeyDiff has ρ=0.49 and Jaccard = 0.38, and key norm and recency collapse on retrieval.The learned scorer is far from attention, with ρ≈0.05 and Jaccard ≈0.08; it loses 1.94 LongBench points and 45.06 RULER points.
  • Refresh frequency: Lazy4 reduces layer-scoring operations by 4× and yields 1.34× and 1.46× decode speedups on Llama and Qwen at 64k context.Benchmark deltas are below 0.05 except for a Llama RULER regression of ∆=−0.151.
  • Refresh frequency: Score-Free freezes the first-step ranking, producing an average deviation of +0.03 while removing subsequent score updates.Seven of eight LongBench tasks are statistically indistinguishable from full refresh; MultiNews regresses by ∆=−0.61.
  • Comparison with existing methods: InertiaKV is 6.5× faster in prefill and 3.6× faster in decode than evaluated KVzip, while retaining approximately 10× fewer decode-side KV tokens.KVzip provides higher Llama RULER quality: 86.44 versus 75.60 for InertiaKV.
  • Adaptation limits: Online adaptation almost always selects α=0.8 or 0.95 because warmup noise-to-drift ratios are large, while useful relevance shifts arrive later.A reactive rank-disagreement trigger is also insufficient, suggesting adaptation requires directional detection of relevance shifts.

6 Conclusion

Under aggressive compression, EMA preserves eviction sets only when scorer changes approximately preserve utility rankings; ranking-altering scorers remain outside this stability result. The findings motivate lazy refresh and separate Score-Free operation while preserving the limited claim that scoring quality is not generally irrelevant.

  • EMA makes approximately order-preserving scorer modifications largely indistinguishable at the eviction-set level under tested aggressive-compression settings.
  • This conclusion does not extend to scorers that substantially alter utility ranking.
  • InertiaKV-Lazy4 delivers 1.34–1.46× decode throughput relative to full-refresh InertiaKV with little quality change.
  • Score-Free scores once at the first decode step and freezes the ranking, yielding an average ∆=+0.03 with one significant small MultiNews regression.
  • The results redirect attention toward temporal aggregation without claiming that scoring quality is generally irrelevant.

Limitations

The method is constrained by decode-only operation, scorer–task interactions, architecture transfer, and the coupling of layer weighting with temporal retention. Score-Free additionally depends on relevance remaining stable after its first-step ranking.

  • InertiaKV and InertiaKV-Lazy do not reduce prefill peak memory, so prefill-bound workloads require composition with a prefill-time compressor.
  • Score-Free may fail when token relevance shifts later in generation, and its needle-in-a-haystack stability does not establish robustness for multi-turn or short-prompt, long-generation workloads.
  • At 90% compression, Mistral-7B and Qwen2.5-14B lose 17–27 RULER points mainly on multi-needle and distant-token retrieval.
  • Because InertiaKV-Lazy4 tracks full-refresh InertiaKV on these models, the degradation is attributed to underlying scorer–task interaction rather than lazy temporal aggregation.
  • Per-eligible-layer EMA updates couple layer weighting with temporal retention, limiting purely temporal interpretation and potentially architecture transfer.
  • The evaluation is English-only and does not rule out a competitive non-attention scorer.

A Proof of Proposition 1

The supplied proof material presents an EMA recurrence and variance bound, alongside a controlled comparison of InertiaKV with an auxiliary variant. The available passages do not state a complete proposition proof in readable form.

  • The displayed recurrence represents the EMA state as a weighted combination of sequential scores and an initialized state.
  • The expectation expression states convergence toward the mean score as the EMA horizon grows.
  • The auxiliary variant combines the same temporal accumulation rule with static reserve and first-eviction rescue mechanisms.
  • The variance passages bound temporal fluctuation using the EMA coefficient and score variance under temporal independence.

B Controlled Auxiliary Ablations

Controlled ablations compare InertiaKV with auxiliary safeguards, stress-test compression across tasks and models, and examine transfer beyond the core scorer. The results favor the no-reserve EMA operating point in several settings but expose scorer and transfer limitations.

  • Controlled auxiliary mechanisms: The auxiliary variant adds static reserve and first-eviction rescue to InertiaKV’s temporal accumulation rule.
  • Compression sweep: As compression becomes more aggressive, InertiaKV increasingly outperforms the auxiliary variant on LongBench and RULER, while LongBench-v2 remains mixed.
  • Operating-point variants: At 90% compression, the no-reserve InertiaKV scorer is strongest among controlled variants on LongBench and RULER, whereas removing momentum is especially harmful on RULER.
  • Retrieval stress tests: The needle-in-a-haystack grid is an auxiliary fixed-setting stress test using ROUGE-L-F over 12 context lengths and 9 depths at 90% compression.
  • Retrieval stress tests: InertiaKV and InertiaKV-Lazy4 closely track the full-cache pattern in the needle-in-a-haystack heatmap, while comparison baselines degrade.
  • Architecture and scale checks: Across additional architecture and scale checks, Lazy4 remains close to full-refresh InertiaKV, but the underlying scorer degrades on RULER multi-evidence retrieval.
  • Architecture and scale checks: On failed subtasks, full refresh differs from Lazy4 by at most 0.65 points, indicating lazy refresh is not the primary degradation source.
  • Transfer beyond InertiaKV: EMA produces only small changes for TOVA, KeyDiff, and KNorm under fixed budgets, so it is not a universal wrapper for every scoring rule.

F Benchmark-Level Interpretation Guide

The benchmark suite separates stability and adaptivity across temporal aggregation choices, with LongBench-v2 serving as a boundary case for lag. Supplementary stress tests also distinguish temporal-aggregation behavior from scorer and architecture limitations.

  • LongBench-v2: LongBench-v2 is a boundary case where lower smoothing helps a small but meaningful subset, while most examples remain invariant across temporal scoring choices.The section treats this pattern as exposing the lag side of the stability–adaptivity tradeoff rather than showing that EMA is broadly harmful.
  • Needle-in-a-haystack: Needle-in-a-haystack evaluation is used as a qualitative retrieval stress check because ROUGE-L-F is informative while exact match and hit rate are not discriminative.
  • MoE: The MoE experiment is a minimal stress check for whether the auxiliary-mechanism pattern extends beyond dense backbones.
  • Architecture and scale stress tests: Architecture and scale tests indicate that Lazy4 remains faithful to the full-refresh estimator, while degradation concentrates in RULER multi-evidence retrieval and scorer–task interaction.On Mistral, increasing α from 0.8 to 0.9 improves RULER from 72.76 to 76.79 but does not solve the issue.
  • Scope: The appendix frames its analysis around how much temporal memory a decode-time compressor should retain, linking benchmark interpretation to the stability–adaptivity tradeoff.

G.1 Alpha Sensitivity

The alpha studies characterize EMA as a bounded-memory stability–adaptivity tradeoff: α=0.8 is retained as a pragmatic default, while lower smoothing can help boundary cases such as LongBench-v2. Cumulative accumulation and automatic selection do not uniformly improve on this operating point.

  • Cross-model validation: α=0.80 remains the default because α=0.90 is tied on Qwen LongBench but worse on LongBench-v2 and RULER.The reported Qwen values are 46.05 vs. 46.01 on LongBench, 0.247 vs. 0.254 on LongBench-v2, and 78.28 vs. 79.43 on RULER.
  • Alpha sensitivity: LongBench-v2 exposes the lag side of smoothing: on Qwen, α=0.80 loses 13 previously correct examples and recovers 7 relative to α=0.30, while α=0.90 loses 17 and recovers 7.Declines span several long-context understanding domains in the evaluated Qwen setting.
  • Cumulative vs. EMA: Cumulative attention is competitive but not dominant: it can outperform EMA when evidence persists, yet stale retention hurts when relevance changes.On Qwen2.5-7B, cumulative attention drops substantially on RULER by −7.66.
  • Adaptive selection: The adaptive selector fails to exploit low-α cases because warmup estimates observe stable cross-layer disagreement but extremely small early temporal drift.It almost always selects α=0.8 or α=0.95 and cannot adapt when relevance shifts occur after warmup.
  • Adaptive selection: A reactive rank-disagreement signal identifies alpha sensitivity better than its direction, so it cannot reliably choose whether to increase or decrease smoothing.The reported disagreement correlations are 0.14–0.15, while both low-α-wins and high-α-wins occur in elevated-disagreement bins.
  • Mechanism-level diagnostics: EMA reduces top-k churn, but stronger smoothing has benchmark-dependent effects: it lowers raw/EMA agreement without improving traced accuracy on LongBench-v2 and improves traced accuracy on RULER.Churn is used as a proxy for boundary variance, while raw/EMA divergence proxies lag.
  • Failure anatomy: Across LongBench-v2, 97.6% of Llama examples and 95.0% of Qwen examples are invariant across temporal rules, leaving a small sensitive subset.The sensitive Qwen subset contains 17 adaptation-lag candidates versus 7 stability-help cases; Llama contains 3 versus 1.

J Supplementary Result Details

Supplementary results show that learned-scorer failures worsen with sequence length, while Lazy4 preserves full-refresh quality and provides stable throughput gains across context lengths. Profiling attributes the targeted efficiency opportunity to per-layer score reconstruction.

  • Learned scorer: ∆=−38.0 at 4k and ∆=−52.2 at 16k quantify the learned bilinear scorer’s worsening Llama RULER deviation with sequence length.At 16k, niah_multiquery falls from 99.2 to 3.4, showing severe degradation in a needle-in-a-haystack retrieval task.
  • Rank-trace diagnostics: EMA top-k churn is consistently lower than raw churn, while stronger smoothing diverges from raw attention without improving LongBench-v2 accuracy and improves RULER accuracy.
  • Lazy refresh: 1.34× for Llama and 1.46× for Qwen are the InertiaKV-Lazy4 wall-clock speedups over full-refresh InertiaKV at 90% compression and 64k context.Lazy4 benchmark deltas are below 0.05 except for the small Llama RULER regression of ∆=−0.151.
  • Throughput scaling: 1.36–1.44× is the InertiaKV-Lazy4 speedup over full refresh across 16k, 32k, and 64k contexts, indicating the gain is not confined to one context length.
  • Hook-level profiling: Per-layer query-aware score reconstruction is the largest measured per-step cost, motivating lazy refresh without changing the retention budget or utility estimator.The profiled bottleneck is specifically attention fallback computation.
  • Reanalysis: Clean-root reruns reproduce the reported Lazy4 task-level values across both main backbones and the listed LongBench, LongBench-v2, and RULER evaluations.
Loading 2609.03515v1…