# CriticalKV: Optimizing KV Cache Eviction from an Output Perturbation Perspective

arXiv: https://arxiv.org/abs/2502.03805 · HTML: https://mlsanity.com/paper/2502.03805/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 41 of its 56 references that are in the map.
- First posted on arXiv 6 Feb 2025.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 30 of 41)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot](https://mlsanity.com/paper/2301.00774/) (2023)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [A Simple and Effective Pruning Approach for Large Language Models](https://mlsanity.com/paper/2306.11695/) (2023)
- [KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache](https://mlsanity.com/paper/2402.02750/) (2024)
- [The NarrativeQA Reading Comprehension Challenge](https://mlsanity.com/paper/1712.07040/) (2017)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [SAMSum Corpus: A Human-annotated Dialogue Dataset for Abstractive Summarization](https://mlsanity.com/paper/1911.12237/) (2019)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling](https://mlsanity.com/paper/2406.02069/) (2024)
- [Multi-News: a Large-Scale Multi-Document Summarization Dataset and Abstractive Hierarchical Model](https://mlsanity.com/paper/1906.01749/) (2019)
- [QMSum: A New Benchmark for Query-based Multi-domain Meeting Summarization](https://mlsanity.com/paper/2104.05938/) (2021)
- [Efficient Attentions for Long Document Summarization](https://mlsanity.com/paper/2104.02112/) (2021)
- [DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads](https://mlsanity.com/paper/2410.10819/) (2024)
- [Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference](https://mlsanity.com/paper/2407.11550/) (2024)
- [Understanding the Difficulty of Training Transformers](https://mlsanity.com/paper/2004.08249/) (2020)

## Built on by (most cited first, 26 of 26)

- [A Survey of Agent Memory in the Second Half: Towards Self-Evolving and Long-Horizon Agents](https://mlsanity.com/paper/2602.06052/) (2026)
- [SpecVLM: Enhancing Speculative Decoding of Video LLMs via Verifier-Guided Token Pruning](https://mlsanity.com/paper/2508.16201/) (2025)
- [LAVa: Layer-wise KV Cache Eviction with Dynamic Budget Allocation](https://mlsanity.com/paper/2509.09754/) (2025)
- [Taming the Fragility of KV Cache Eviction in LLM Inference](https://mlsanity.com/paper/2510.13334/) (2025)
- [MixKVQ: Query-Aware Mixed-Precision KV Cache Quantization for Long-Context Reasoning](https://mlsanity.com/paper/2512.19206/) (2025)
- [LCGuard: Latent Communication Guard for Safe KV Sharing in Multi-Agent Systems](https://mlsanity.com/paper/2605.22786/) (2026)
- [From Prefix Cache to Fusion RAG Cache: Accelerating LLM Inference in Retrieval-Augmented Generation](https://mlsanity.com/paper/2601.12904/) (2026)
- [Rethinking KV Cache Eviction via a Unified Information-Theoretic Objective](https://mlsanity.com/paper/2604.25975/) (2026)
- [When Does Value-Aware KV Eviction Help? A Fixed-Contract Diagnostic for Non-Monotone Cache Compression](https://mlsanity.com/paper/2605.08234/) (2026)
- [Beyond RAG: Task-Aware KV Cache Compression for Comprehensive Knowledge Reasoning](https://mlsanity.com/paper/2503.04973/) (2025)
- [LKV: End-to-End Learning of Head-wise Budgets and Token Selection for LLM KV Cache Eviction](https://mlsanity.com/paper/2605.06676/) (2026)
- [RDKV: Rate-Distortion Bit Allocation for Joint Eviction and Quantization of the KV Cache](https://mlsanity.com/paper/2605.08317/) (2026)
- [ManifoldKV: Training-Free KV Cache Compression via Euclidean Outlier Detection](https://mlsanity.com/paper/2602.08343/) (2026)
- [T-LoopFormer: Token-Level Elastic-Depth Looped Transformers for Latent Reasoning with Dynamic Routing](https://mlsanity.com/paper/2609.15160/) (2026)
- [Neural Attention Search](https://mlsanity.com/paper/2502.13251/) (2025)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [Reformulating KV Cache Eviction Problem for Long-Context LLM Inference](https://mlsanity.com/paper/2605.07234/) (2026)
- [AnchorKV: Anchor-Residual KV Cache Compression](https://mlsanity.com/paper/2608.02901/) (2026)
- [KV Cache Compression Through the Lens of Transform Coding](https://mlsanity.com/paper/2608.14191/) (2026)
- [Trust the Mass: Forced Weights in KV-Cache Eviction](https://mlsanity.com/paper/2608.25230/) (2026)
- [Monte Carlo Estimation for KV Cache Eviction](https://mlsanity.com/paper/2610.07643/) (2026)
- [Head-Aware Key-Value Compression for Efficient Autoregressive Image Generation](https://mlsanity.com/paper/2605.20600/) (2026)
- [Parser Transitions Already Reveal Structural Responsibility: KV Persistence for Structured Generation](https://mlsanity.com/paper/2608.28276/) (2026)
- [From Token Importance to Conditional Removability: Rethinking Visual Token Pruning in Multimodal Large Language Models](https://mlsanity.com/paper/2609.26484/) (2026)
- [When to Evict, Not What to Keep: Draft-Guided Eviction for Training-Free KV-Cache Compression](https://mlsanity.com/paper/2609.33334/) (2026)
- [ReSS: Residual-Restoring Sparse Attention for 3D Vision Transformers](https://mlsanity.com/paper/2609.35593/) (2026)

## Abstract (arXiv)

Large language models have revolutionized natural language processing but face significant challenges of high storage and runtime costs, due to the transformer architecture's reliance on self-attention, particularly the large KV cache for long-sequence inference. Recent efforts to reduce KV cache size by pruning less critical entries based on attention weights remain empirical and lack formal grounding. This paper presents a formal study on identifying critical KV cache entries by analyzing attention output perturbation. Our analysis reveals that, beyond attention weights, the value states within KV entries and pretrained parameter matrices are also crucial. Based on this, we propose a perturbation-constrained selection algorithm that optimizes the worst-case output perturbation to identify critical entries. We demonstrate that our algorithm is a universal, plug-and-play enhancement that incurs negligible computational overhead. When integrated with three state-of-the-art cache eviction methods on three distinct LLMs, our algorithm significantly reduces the compression loss by more than textithalf on average across 29 datasets from the Ruler and LongBench benchmarks. Further perturbation analysis, at both the head and layer levels, confirms the principles underlying our effectiveness. This work offers a new, formally grounded perspective to cache eviction , opening promising avenues for future research. The code is publicly available at https://github.com/FFY0/DefensiveKV.