PaperlayerView exact revision on arXiv

Source-linked AI summary

QEvict: Recoverable Quantized KV Eviction for Attention-Drift-Robust Long-Context Decoding

Ayushman Garg, Akshita Gupta, Shaswata Bhattacharya, Abhishek Gupta, Sandeep Kumar, Manoj Kumar

arXiv:2608.05326v1cs.LGcs.CL

TL;DR

Long-context inference is constrained by growing KV-cache memory, and irreversible eviction can remove states whose importance emerges later. QEvict routes contiguous windows through full-precision, recoverable low-bit, and evicted tiers; it improves performance–memory trade-offs across the evaluated benchmarks and models.

  • Problem

    KV-cache memory constrains long-context inference, while query-dependent importance can make irreversibly evicted states relevant later.

    Source: §1 · p. 1

  • Method

    QEvict dynamically routes contiguous historical windows among full-precision, recoverable low-bit, and evicted tiers using cumulative attention scores.

    Source: §1 · p. 2, §4.2 · p. 5

  • Results

    QEvict improves performance–memory trade-offs over eviction and quantization baselines across LongBench, RULER, and GSM8K, while reducing peak GPU memory and improving eager decoding throughput.

    Source: §1 · p. 2, §6 · p. 7

  • Takeaways & Limitations

    Recoverable low-bit retention is a practical alternative to permanent eviction within the evaluated settings.

    Source: §6 · p. 7

    The current implementation limits FlashAttention-2 throughput, and evaluation focuses on decoder-only models and fixed-size contiguous windows.

    Source: §5.1 · p. 7

Abstract

from arXiv · show

Autoregressive large language model inference is increasingly constrained by the memory footprint of the Key-Value (KV) cache. A dominant line of work reduces this footprint by evicting tokens that appear unimportant under attention-derived scores. However, such policies make an implicit irreversible decision: once a token is evicted, it cannot become useful again. We show that this assumption is brittle during decoding. Token and window importance drift as generated queries evolve, causing standard eviction policies to permanently discard states that later receive substantial attention under the full-cache model. To characterize this behaviour, we introduce Future Missed Mass and Global LIR, two diagnostics that measure future attention assigned to discarded states and the reactivation of historically inactive regions. We propose QEvict, a three-tier KV-cache management scheme that replaces binary retain-or-delete eviction with recoverable eviction. QEvict maintains high-confidence windows in full precision, stores intermediate windows in a quantized recoverable tier, and deletes only the lowest-confidence windows. During decoding, cumulative attention scores update window importance and when a quantized window becomes important again, it is dequantized and promoted to the full-precision. Under a fixed memory budget, this design preserves broader historical context while retaining exact full precision for the most important regions. Across long-context understanding, retrieval, and reasoning benchmarks, QEvict consistently improves over representative eviction and quantization baselines, reducing missed attention and improving information retention

1 Introduction

Long-context inference strains memory as KV caches grow, while existing compression can irreversibly discard coherent or later-relevant context. QEvict instead routes contiguous windows among full-precision, recoverable low-bit, and evicted states, motivated by decoding-time importance drift.

1 Introduction

  • The KV cache grows with sequence length and batch size, potentially rivaling or exceeding model-parameter memory at long contexts.This constrains batch capacity, increases inference latency, and raises serving costs.Source: §1 · p. 1
  • Token-level eviction can fragment coherent neighboring evidence, while query-dependent importance shifts can make irreversibly discarded states useful later.Related linguistic dependencies span neighboring tokens and sentences, and a state's relevance can re-emerge as decoding proceeds.Source: §1 · pp. 1–2
  • QEvict ranks contiguous historical windows by cumulative attention, keeping high-importance windows full precision, intermediate windows recoverable at low bitwidth, and the rest evicted.Quantized windows remain available for attention and can be promoted when importance re-emerges.Source: §1 · p. 2
  • A persistent quantized backing store reuses each window's first-demotion representation across later recoveries and promotions, preventing error accumulation across transitions.The implementation supports GQA and FlashAttention-2 and selectively materializes SDPA attention at routing steps.Source: §1 · p. 2
  • Future Missed Mass, Global LIR, and Selection Churn characterize discarded-state attention, revival of inactive windows, and routing instability.These diagnostics accompany observations that attention is concentrated but temporally unstable, motivating preservation of uncertain historical states without keeping them all full precision.Source: §1 · p. 2
  • QEvict consistently improves quality–memory trade-offs over representative eviction and quantization baselines across three benchmarks and three model families.The evaluation covers LongBench, RULER, and GSM8K; QEvict also supports broader historical coverage under a fixed budget.Source: §1 · p. 2

2 Related Work

Prior work compresses KV caches through eviction or quantization, but these approaches leave gaps in recoverability and coherent context retention. QEvict combines window-level routing with a recoverable low-bit tier.

2 Related Work

  • QEvict complements query-dependent cache-access methods by retaining historical states whose future relevance has not yet emerged.Its low-bit intermediate state combines broader coverage with dynamic recovery under a fixed memory budget.Source: §2 · p. 2
  • Eviction methods retain sinks and recent tokens, accumulated heavy hitters, prompt-observed importance, adaptive head budgets, or value-aware states [Xiao et al. 2024; Zhang et al. 2023; Li et al. 2024; Feng et al. 2024; Feng et al. 2025].DefensiveKV and Layer-DefensiveKV also account for uncertainty in future attention [Feng et al. 2026].Source: §2 · p. 2
  • Prior methods retain binary cache states, so low-importance discarded states cannot return, and token-level selection can fragment related context.QEvict routes contiguous windows among full-precision, recoverable low-bit, and evicted states, supporting promotion and demotion as importance changes.Source: §2 · p. 3
  • KV quantization methods broaden historical coverage using asymmetric 2-bit quantization, sub-4-bit representations, or token-level saliency-dependent precision [Liu et al. 2024; Hooper et al. 2024; He et al. 2024].These examples are KIVI, KVQuant, and ZipCache, respectively.Source: §2 · p. 3

3 Observations and Motivation for QEvict

The observations show that window aggregation stabilizes cache selection, while some historically inactive windows regain importance. At matched budget and window size, a recoverable INT2 tier preserves attention mass that binary eviction discards.

3 Observations and Motivation for QEvict

  • The diagnostic compares R1 token-level eviction, R2 two-tier window eviction, and R3/R4 three-tier policies using window sizes 1, 8, 8, and 32, respectively.R2 and R3 provide the controlled comparison: they share window size and measured cache budget but differ in binary versus recoverable retention.Source: §3 · p. 3
  • Window-based policies incur substantially lower Future Missed Mass than token-level eviction, and window aggregation suppresses short-lived selection changes at the cost of coarser allocation for larger windows.The diagnostic uses Llama-3.1-8B-Instruct, a 512-token prefill, 256 generated tokens, and a 20% cache budget.Source: §3 · p. 3
  • R3 retains 19.7% of FullKV attention mass in full precision and another 42.6% in INT2, reducing eviction to 35.7%; matched R2 retains 33.3% in full precision and evicts 64.8%.The R2–R3 comparison uses the same window size and measured cache budget; INT2 scores have 0.9824 cosine agreement with FullKV scores.Source: §3 · p. 3
  • For R3, oracle top-ranked windows have a 0.98% revival rate, while the deployed full-precision policy has a 6.18% revival rate.Most important windows remain stable, but a non-negligible subset leaves and later re-enters the active set; demotion is substantially more frequent than promotion.Source: §3 · p. 4
  • The findings motivate contiguous windows, a recoverable low-bit tier between full precision and eviction, and bidirectional migration as importance evolves.The ranked cache therefore supports retaining in full precision, preserving compactly, or evicting.Source: §3 · p. 4

4 Methodology

QEvict manages historical KV context as contiguous windows whose precision and residency change with cumulative attention importance. Its recoverable low-bit tier lets windows return to full precision rather than making every eviction permanent.

4.3 QEvict: Recoverable Cache Hierarchy

  • QEvict routes historical windows among full-precision, recoverable low-bit, and evicted states under a fixed budget.Quantized windows remain available to attention and can be promoted or demoted as importance changes; only windows outside the combined tier capacities are permanently removed.Source: §4 · p. 4, §4.3 · p. 6

4.1 Preliminaries and Problem Formulation

  • After reserving protected sink and recent regions, QEvict partitions the remaining cache into contiguous windows and assigns each a state subject to storage costs.The assignment jointly determines residency and representation precision rather than selecting only a retained subset.Source: §4.1 · p. 4

4.2 Cumulative Window Scoring

  • Cumulative attention scores rank historical windows, with prompt attention initializing scores and routing repeated every Ω generated tokens during decoding.The hierarchy needs only an importance ordering, so alternative ranking functions are compatible.Source: §4.2 · pp. 4–5

4.3 QEvict: Recoverable Cache Hierarchy

  • The hierarchy allocates historical bytes between full-precision and quantized tiers; first-demotion quantization is reused across later migrations to prevent error accumulation.Active low-bit windows are dequantized before attention, and their keys are re-rotated at original positions; the persistent codes and parameters are reused on subsequent transitions.Source: §4.3 · pp. 5–6

5 Experiments

Across long-context understanding and retrieval evaluations, QEvict improves quality–memory trade-offs over representative eviction and quantization baselines. Efficiency varies by attention backend, and the current implementation has throughput and scope limitations.

5 Experiments

  • At 20% memory, LongBench scores are 46.4 on Llama and 37.8 on Mistral, versus 44.0 and 37.4 for the strongest matched-memory eviction baseline.At 5% memory, the gains increase to 9.7 and 4.7 points, respectively; at 10% memory, QEvict is within 1.2 points on Llama and 1.8 on Mistral of the strongest quantization baseline using roughly half the KV memory.Source: §5 · p. 7
  • LongBench macro-average leads across six model–budget settings; on RULER, QEvict scores 87.6, beating matched-memory eviction by 1.2 points and comparable-memory quantization by 8.6.On RULER, it remains within 2.4 points of Full-KV.Source: §5 · p. 7
  • GSM8K evaluation reports accuracy–memory curves for Llama, Qwen, and Mistral across a complete memory sweep, with numerical model-specific comparisons deferred to Appendix F.The supplied results passage does not state curve outcomes.Source: §5 · p. 7
  • Ablations favor routing interval Ω=8 and quantized-tier fraction q=0.70 across benchmarks; INT2 broadens historical coverage, while INT4 trades coverage for lower quantization error.The passage does not give the detailed ablation values.Source: §5 · p. 7

5.1 Efficiency, Limitations, and Future Work

  • With eager SDPA, QEvict adds 0.5% TTFT overhead, reduces TPOT by 9.3%, and improves decoding throughput by 9.8% over Full-KV; with FlashAttention-2, peak GPU memory falls 29.7%.The FlashAttention-2 memory change is from 29.54 to 20.78 GB; throughput is lower because the current path materializes attention scores and reconstructs the cache.Source: §5.1 · p. 7
  • The evaluation is limited to decoder-only models and fixed-size contiguous windows, leaving adaptive window boundaries and broader model architectures for future study.Current reconstruction and selective SDPA attention-score materialization also limit FlashAttention-2 throughput and add temporary workspace overhead.Source: §5.1 · p. 7

6 Conclusion

QEvict routes historical windows across full-precision, recoverable INT2, and evicted tiers under a byte constraint. Across LongBench, RULER, and GSM8K, it improves performance–memory trade-offs over eviction and quantization baselines while reducing peak GPU memory and improving eager decoding throughput.

6 Conclusion

  • Across LongBench, RULER, and GSM8K, QEvict improves performance–memory trade-offs over eviction and quantization baselines while reducing peak GPU memory and improving eager decoding throughput.The conclusion describes recoverable low-bit retention as a practical alternative to permanent eviction.Source: §6 · p. 7

A Algorithm

  • QEvict ranks candidate historical windows by cumulative attention, assigning them to full-precision, quantized, or evicted tiers and promoting important quantized windows through ledger-based recovery.The routing algorithm dequantizes promoted windows, quantizes windows entering the recoverable tier once, and deletes ledger entries for evicted windows.Source: A Algorithm · p. 10

B.1 Models and Inference Protocol

  • Evaluation uses three instruction-tuned models across long-context understanding, controlled retrieval and aggregation, and multi-step mathematical reasoning.All methods use the same checkpoint, tokenizer, prompts, input and generation limits, and answer post-processing within each benchmark; decoding is greedy unless stated otherwise.Source: §B.1 · p. 10

B.2 Baselines

  • Comparisons include eviction methods, reduced-precision quantization methods, and Full-KV as the uncompressed reference.The eviction baselines cover sink- and recency-based retention, attention scoring, prompt observation, head-adaptive allocation, value-aware importance, and drift-aware eviction.Source: §B.2 · p. 10

B.3 Comparison Regimes

  • Eviction baselines are compared at measured memory ratios, while quantization baselines are compared at their measured performance–memory operating points.Eviction ratios vary by benchmark: LongBench uses 0.05, 0.10, and 0.20; RULER uses 0.20; GSM8K uses 0.10 through 1.0.Source: §B.3 · p. 11

B.4 Memory Accounting

  • QEvict’s measured cache budget includes retained tensors, packed codes, quantization metadata, residual regions, outliers, indexing metadata, and persistent migration records.Temporary workspaces are excluded from the KV-cache budget and captured separately by peak GPU memory.Source: §B.4 · p. 11

B.5 QEvict Configuration

  • Unless varied, QEvict uses routing interval Ω=8, five sink tokens, an INT2 recoverable tier, and assigns 70% of the remaining historical budget to quantization.The remaining 30% goes to the full-precision historical tier; sensitivity to routing interval, allocation, and precision is reported in Appendix G.Source: §B.5 · p. 11

C.1 Task Families and Metrics

The evaluation covers 12 LongBench tasks spanning four task families, uses each dataset’s official metric, and reports task-level scores.

C.1 Task Families and Metrics

  • The evaluation covers 12 LongBench tasks across single-document QA, multi-document QA, summarization, and few-shot learning, storing 128 recent tokens for this task.Table 5 summarizes the task families used in the evaluation.Source: §C.1 · p. 11, Table 5 · p. 11

C.2 Complete Results

  • LongBench results use each dataset’s official metric and are reported at the task level.Table 3 reports Llama and Mistral results, while Table 6 reports Qwen results.Source: §C.1 · p. 11, §C.2 · p. 11

D LongBench Performance–Memory Pareto Analysis

The section analyzes LongBench performance–memory Pareto frontiers across task families, models, and baseline classes, complementing fixed-budget comparisons with multiple memory regimes.

D LongBench Performance–Memory Pareto Analysis

  • Pareto analysis shows whether an advantage persists across memory regimes and distinguishes higher performance at matched memory from lower memory at comparable performance.The analysis is intended to complement fixed-budget results that cover only a small number of operating points.Source: D LongBench Performance–Memory Pareto… · pp. 11–12
  • An operating point pairs measured KV-memory ratio with task-family score; one point dominates another when it is no worse on either axis and strictly better on at least one.Non-dominated points form the Pareto frontier, where upper-left positions are preferable.Source: D LongBench Performance–Memory Pareto… · pp. 11–12
  • Table 6 reports Qwen2.5-7B-Instruct LongBench performance against eviction methods at matched 20%, 10%, and 5% budgets and quantization baselines at comparable memory footprints.Its caption identifies the best and second-best distinct results within each comparison group, excluding Full-KV.Source: Table 6 · p. 12
  • Figures 4–6 compare QEvict with eviction and quantization baselines across four LongBench task families and three models, with FullKV performance marked by dashed lines.Each model has eight panels: separate comparisons for the four task families against each baseline class.Source: D LongBench Performance–Memory Pareto… · p. 12, Figure 4 · p. 13, Figure 5 · p. 14

E.1 Dataset and Evaluation Protocol

  • RULER evaluates retrieval, aggregation, and reasoning at 32K context and a 20% KV-cache budget; its tasks test sparse evidence access, distributed information, dependent intermediate states, and long-range evidence use.The section evaluates Llama-3.1-8B-Instruct with a 64-token protected recent region.Source: §E.1 · pp. 12, 16, Table 7 · p. 16

F.1 Evaluation Protocol

GSM8K evaluates cache compression during autoregressive multi-step reasoning, where intermediate generated states may matter again in later calculations or final-answer construction.

F.1 Evaluation Protocol

  • GSM8K tests whether cache compression preserves intermediate decoding states that may become relevant during later calculations or final-answer construction.This complements long-context benchmarks that primarily test retrieval from the input sequence.Source: §F.1 · p. 16
  • Evaluation covers three instruction-tuned models and multiple measured KV-memory budgets, reporting exact-match accuracy relative to the FullKV cache.Eviction methods are compared at matched budgets, quantization methods at measured operating points, and 25% of persistent cache is reserved for recent tokens.Source: §F.1 · p. 16
  • Figure 3 presents accuracy–memory curves for all three models, while Tables 8–10 report numerical results for every evaluated operating point.Table 8 compares KV-cache eviction methods at different KV-cache budgets and quantization methods at approximately matched memory for Llama-3.1-8B-Instruct on GSM8K.Source: §F.1 · p. 16, Table 8 · p. 16

G Ablation Studies

The appendix tests routing granularity, recoverable-tier allocation, and quantization precision, then details diagnostic protocols and supporting findings on missed attention, cache churn, and quantized-score agreement.

G.1 Window Granularity

G.2 Quantized-Tier Allocation

  • The quantized-tier allocation sweep examines the trade-off between broader low-bit historical coverage and reduced full-precision historical capacity.It fixes Ω=8 and uses INT2 quantization.Source: §G.2 · p. 17, Table 12 · p. 18

G.3 Quantization Precision

  • The precision comparison contrasts INT2’s broader historical-window coverage with INT4’s lower quantization error under the same total cache budget.The comparison fixes Ω=8 and q=0.70.Source: §G.3 · p. 18, Table 13 · p. 18

H.1 Measurement Protocol; H.2 Runtime Components; H.3 Hardware Settings

  • Measurements report TTFT, TPOT, aggregate decoding throughput, and peak GPU memory; runtime components include routing and migration, while the current FlashAttention-2 path adds dequantization and reconstruction overhead.Runs control hardware, model precision, batch size, sequence lengths, and backend; experiments used A100 GPUs, with some runs on a GB10.Source: §H.1 · p. 18, §H.2 · p. 19, §H.3 · p. 19

I.1 Diagnostic Protocol

  • Diagnostic traces use an uncompressed FullKV reference and compare token-level eviction, two-tier window eviction, and three-tier routing at matched measured byte budgets where specified.The protocol uses Llama-3.1-8B-Instruct, two articles, 256 generated tokens, and a 20% cache budget; FMM uses H=32.Source: §I.1 · p. 19, §I.2 · p. 19

I.2 Observation I: Future Missed Mass and Selection Churn

  • R3 reduced average FMM versus token-level R1 and lowered historical-set churn by more than an order of magnitude; R4 lowered FMM but did not improve churn.The authors caution that excessively large windows can sacrifice allocation granularity without improving assignment stability.Source: Table 14 · p. 20, §I.2 · p. 20

I.3 Observation II: Tier-Mass Distribution and Quantized-Score Agreement

  • 29.1 percentage points less reference attention mass went to permanent eviction with recoverable R3 than byte-matched R2.R2 assigned 64.8% to evicted windows; R3 assigned 35.7%, preserving 42.6% in INT2.Source: §I.3 · p. 20
  • INT2 largely preserved quantized-window score ordering, although attention-mass attenuation means its execution was not numerically identical to FullKV.The ranking signal remained sufficiently stable for continued scoring and later promotion.Source: §I.3 · p. 20, Table 15 · p. 21

I.4 Observation III: Global LIR

Global LIR tracks inactive-window episodes that later return to the selected full-precision set, while transition probabilities describe changes in selection over routing intervals. The section reports re-entry under deployed routing and evaluates QEvict with alternative window-ranking functions.

I.4 Observation III: Global LIR

  • Global LIR counts eligible inactive episodes that later re-enter the selected set; episodes that never return before generation ends remain unrescued in the denominator.The default eligibility threshold is three consecutive inactive routing events, with the same trend checked for thresholds of 1, 2, 4, and 8.Source: §I.4 · p. 21
  • Under R3, the deployed full-precision tier had a 6.18% return rate, approximately 6.3× the oracle rate.The authors attribute the greater re-entry pressure to approximate scoring and constrained allocation compared with oracle ranking.Source: Table 16 · p. 21, §I.4 · p. 21
  • Median policy return times were eight routing events for R3 and two for R4, each corresponding to approximately 64 decoding steps.This indicates that relevance revival can occur beyond the next routing event.Source: §I.4 · p. 21
  • At an eight-event lag, transitions from inactive to active rose from 0.31% at ∆=1 to 2.39%, while departures were approximately 9.3× more frequent than returns.The reported active-to-inactive transition increased from 3.05% to 22.12%.Source: §I.4 · p. 21

J Compatibility with Alternative Ranking Functions

  • QEvict’s hierarchy requires only an ordering over candidate windows, so the study changes the ranking function while holding the hierarchy, byte allocation, and migration policy fixed.Compared estimators include cumulative attention, exponentially decayed attention, attention p-norm with p=3, and key-vector norm.Source: J Compatibility with Alternative… · pp. 21–22
  • The alternative-ranking evaluation uses Llama-3.1-8B-Instruct on LongBench with a 5% KV-cache budget, Ω=8, q=0.70, and INT2.It covers the 12 main-study tasks plus PassageCount and PassageRetrieval-en; the table average spans 14 tasks.Source: J Compatibility with Alternative… · p. 21, Table 17 · p. 22

K Effect of Q→F Residency Promotion

In the R3 three-tier policy, enabling Q→F promotion is associated with lower future missed mass, stronger Q-tier agreement and attention preservation, and observed re-entry. The pilot comparison is directional because its variants use different source articles.

K Effect of Q→F Residency Promotion

  • Promoted windows are reconstructed from persistent INT2 representations, restoring full-tier residency and execution handling rather than their original pre-quantization KV values.This bounds what promotion restores: residency, not the original KV values.Source: K Effect of Q→F Residency Promotion · p. 22
  • 16.8% to 16.1%: R3 FMM decreases with Q→F promotion enabled, indicating less future attention assigned to inaccessible historical states.Table 18 reports FMM for the R3 policy; lower is better.Source: Table 18 · p. 23, K Effect of Q→F Residency Promotion · p. 23
  • 0.947 to 0.985: QSA increases under promotion, indicating closer score agreement for windows currently in the quantized tier with their FullKV reference scores.The comparison concerns the current Q-tier population, not fixed-window quantization error.Source: Table 18 · p. 23, K Effect of Q→F Residency Promotion · p. 23
  • 88.7% to 95.5%: RQ rises by 6.8 percentage points with promotion, preserving more FullKV reference attention mass over the current Q-tier windows.Table 18 defines higher RQ as better.Source: Table 18 · p. 23, K Effect of Q→F Residency Promotion · p. 23
  • Global LIR rises from 0% to 6.6%, and promotion records 639 Q→F transitions versus none under one-way demotion.The zero Global LIR value without promotion holds by construction; the nonzero value marks re-entry into the full tier.Source: Table 18 · p. 23, K Effect of Q→F Residency Promotion · pp. 23–24
  • The variants share tier capacities, scoring, routing schedule, quantization, and memory budget; only promotion eligibility differs.Without promotion, quantized windows can be evicted but cannot return to the full tier.Source: K Effect of Q→F Residency Promotion · p. 23
  • Because the pilot variants use different source articles, the comparison is directional evidence, not a paired estimate of promotion’s exact causal effect.The paper explicitly cautions against interpreting this pilot as an exact causal estimate.Source: K Effect of Q→F Residency Promotion · p. 23
Loading 2608.05326v1…