Technical Summary: QEvict

Problem Statement

Autoregressive inference in large language models (LLMs) is increasingly constrained by the memory footprint of the Key-Value (KV) cache, which grows linearly with sequence length and batch size. While existing solutions address this through eviction (permanently removing tokens deemed unimportant) or quantization (storing states at lower precision), both approaches suffer from fundamental limitations:

1. Irreversibility of Eviction: Standard eviction policies make binary, irreversible decisions. They assume token importance is static; however, the paper demonstrates that token and window importance "drift" during decoding. A state discarded as unimportant under a current query may become critical later for resolving references or advancing reasoning trajectories. Once evicted, this information is permanently lost.
2. Fragmentation of Context: Token-level eviction can fragment locally coherent evidence by retaining isolated high-scoring tokens while discarding neighboring tokens essential for their interpretation.
3. Static Precision: Existing quantization methods generally do not jointly manage cache residency and numerical precision. They lack a mechanism to dynamically move historical states between full-precision execution, compact recoverable storage, and permanent removal.

The core challenge addressed is how to aggressively compress the KV cache while preserving coherent historical regions whose relevance may only emerge later in the generation process.

Methodology: QEvict

The authors propose QEvict, a three-tier, recoverable KV-cache management scheme that operates over contiguous windows rather than individual tokens. The system dynamically routes windows among three states under a fixed memory budget:

1. Full-Precision Tier: High-confidence windows are retained in full precision.
2. Recoverable Quantized Tier: Intermediate windows are stored in a compact, low-bit format (specifically INT2 in the experiments). These windows remain accessible to the attention mechanism and can be "promoted" back to full precision if their importance increases.
3. Evicted Tier: Only the lowest-confidence windows are permanently removed.

Key Mechanisms

• Window-Level Routing: Instead of token-level decisions, QEvict partitions the historical cache into contiguous windows. This stabilizes selection decisions and preserves local context.
• Cumulative Scoring: Window importance is determined by accumulating attention scores over time. This allows the system to track the "future missed mass" (attention that would have been assigned to discarded states) and identify windows that regain relevance.
• Recoverable Hierarchy:
  • Demotion: When a full-precision window's importance drops, it is moved to the quantized tier.
  • Promotion: If a quantized window's cumulative score rises, it is dequantized and promoted back to the full-precision tier.
  • Write-Once Quantization Ledger: To prevent error accumulation during repeated tier transitions, QEvict quantizes a window only once upon its first demotion. The resulting low-bit representation is stored in a persistent ledger and reused for all subsequent promotions and demotions, avoiding the compounding of approximation errors.
• Implementation: The system supports Grouped Query Attention (GQA) and FlashAttention-2. It selectively materializes SDPA attention during routing events to compute cumulative scores while using standard decoding paths otherwise.

Key Contributions

1. Systematic Analysis of Cache Dynamics: The authors introduce two new diagnostics to characterize decoding-time behavior:

   • Future Missed Mass (FMM): Measures the fraction of future attention assigned to states already discarded by a policy.
   • Global LIR (Latent Importance Reactivation): Measures how often historically inactive windows re-enter the active set.
   • Selection Churn: Quantifies the instability of cache assignments between consecutive routing steps.
   • Findings: These diagnostics reveal that while importance is concentrated, it is temporally unstable; a non-negligible subset of windows leaves the active set and later re-enters, justifying a recoverable tier.

2. QEvict Framework: A novel, byte-constrained hierarchy that replaces binary eviction with a dynamic process of demotion, recovery, and promotion. It combines the selective retention of eviction methods with the broad coverage of quantization methods.

3. Extensive Evaluation: The method is evaluated across three benchmarks (LongBench, RULER, GSM8K) and three instruction-tuned LLM families (Llama-3.1-8B, Mistral-7B, Qwen2.5-7B) under stringent memory budgets (5% to 20% of full KV cache).

Results

QEvict consistently improves the quality–memory trade-off compared to representative eviction and quantization baselines:

• Long-Context Understanding (LongBench): Across 12 tasks and multiple memory budgets, QEvict achieves the highest macro-average scores. At a 20% memory budget, it outperforms the strongest eviction baseline by a significant margin. At tight 5% budgets, the gains are even more pronounced, highlighting the value of recoverable low-bit retention.
• Long-Range Retrieval (RULER): On 32K context length tasks, QEvict achieves a macro-average of 87.6, exceeding the strongest matched-memory eviction baseline (Layer-DefensiveKV) by 1.2 points and outperforming comparable quantization baselines by 8.6 points. It remains within 2.4 points of the uncompressed Full-KV reference.
• Reasoning (GSM8K): QEvict preserves multi-step generation quality better than baselines as the cache budget decreases, maintaining higher accuracy across Llama, Qwen, and Mistral models.
• Efficiency:
  • With Eager/SDPA backends, QEvict reduces Time Per Output Token (TPOT) by 9.3% and improves throughput by 9.8% compared to Full-KV, as the reduced full-precision cache size offsets management overhead.
  • With FlashAttention-2, QEvict reduces peak GPU memory by 29.7% (from 29.54 GB to 20.78 GB), though current throughput is limited by the need to dequantize and reconstruct caches before attention.

Significance and Claims

The paper claims that recoverable low-bit retention is a practical and superior alternative to permanent eviction for long-context LLM inference. By treating cache management as a dynamic hierarchy rather than a one-shot decision, QEvict addresses the brittleness of assuming static token importance.

The authors emphasize that their approach:

• Preserves broader historical context without allocating full-precision memory to all states.
• Stabilizes cache selection through window-level aggregation, reducing sensitivity to transient token-level fluctuations.
• Supports the "reactivation" of historically inactive regions, a phenomenon observed to occur frequently during decoding but ignored by current state-of-the-art methods.

The work suggests that future systems should move beyond binary retain-or-delete policies toward dynamic, recoverable storage hierarchies to handle the evolving nature of attention in long-context generation.