Trust the Mass: Forced Weights in KV-Cache Eviction
cs.LG, cs.CL
Submitted: 2026-08-25
Updated: 2026-08-28
Comments: 18 pages; revised wording in 2.3 for increased accuracy (main results unchanged)
Code: https://github.com/NVIDIA/kvpress
License: http://creativecommons.org/licenses/by/4.0/
The gist: Every deployed sparse-attention or KV-cache-eviction rule keeps a subset of the keys, discards the rest, and renormalizes the attention weights over the kept set.
Terminology
Abstract
Every deployed sparse-attention or KV-cache-eviction rule keeps a subset of the keys, discards the rest, and renormalizes the attention weights over the kept set. Enumerating the exact best subset under that constraint on 168, 192 attention rows from five models shows that keeping the largest weights is already near-optimal, since the best subset closes only a median 2 to 5% of the remaining gap to full attention. If selection closes this little, published margins between eviction methods must come from elsewhere, so we measure the bytes each method holds. In the shared evaluation pipeline, the strongest query-agnostic methods hold the full cache because their per-head selections are stored as masks, and only ragged per-head storage frees that memory. Enforcing a nominal budget on one fixed selection costs 14 to 62 benchmark points. We trace an 87.6-point retrieval margin to rankings computed while the question is visible. ContourKV, a training-free allocator built from the dropped-mass statistic, wins 93 of 160 paired comparisons against that state of the art and loses 22 at the byte count of the budget-enforcing baselines, and it ties the strongest of them.
Sources
- LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding
- Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carath'{e}odory's Theorem
- Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction
- PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling
- Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores
- Stream sampling for variance-optimal estimation of subset sums
- Expected Attention: KV Cache Compression by Estimating Attention from Future Queries Distribution
- Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference
- CriticalKV: Optimizing KV Cache Eviction from an Output Perturbation Perspective
- CAOTE: KV Cache Selection for LLMs via Attention Output Error-Based Token Eviction
- Attention Score is not All You Need for Token Importance Indicator in KV Cache Reduction: Value Also Matters
- RULER: What's the Real Context Size of Your Long-Context Language Models?
- LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
- Tangram: Unlocking Non-Uniform KV Cache Compression for Efficient Multi-turn LLM Serving
- KVzip: Query-Agnostic KV Cache Compression with Context Reconstruction
- Streaming Attention Approximation via Discrepancy Theory
- SnapKV: LLM Knows What You are Looking for Before Generation
- Nearly Optimal Attention Coresets
- Twilight: Adaptive Attention Sparsity with Hierarchical Top-$p$ Pruning
- CompressKV: Semantic Retrieval Heads Know What Tokens are Not Important Before Generation
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks