# Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference

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

## Key facts

- Cited by 235 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 46 of its 71 references that are in the map.
- First posted on arXiv 16 Jul 2024.

## Placed in

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

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [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)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (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)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [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)
- [Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned](https://mlsanity.com/paper/1905.09418/) (2019)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Are Sixteen Heads Really Better than One?](https://mlsanity.com/paper/1905.10650/) (2019)
- [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)
- [SAMSum Corpus: A Human-annotated Dialogue Dataset for Abstractive Summarization](https://mlsanity.com/paper/1911.12237/) (2019)
- [ZeroQuant: Efficient and Affordable Post-Training Quantization for Large-Scale Transformers](https://mlsanity.com/paper/2206.01861/) (2022)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [A Dataset of Information-Seeking Questions and Answers Anchored in Research Papers](https://mlsanity.com/paper/2105.03011/) (2021)
- [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)

## Built on by (most cited first, 30 of 235)

- [A Survey on Large Language Model Acceleration based on KV Cache Management](https://mlsanity.com/paper/2412.19442/) (2024)
- [Not All Heads Matter: A Head-Level KV Cache Compression Method with Integrated Retrieval and Reasoning](https://mlsanity.com/paper/2410.19258/) (2024)
- [KVzip: Query-Agnostic KV Cache Compression with Context Reconstruction](https://mlsanity.com/paper/2505.23416/) (2025)
- [Expected Attention: KV Cache Compression by Estimating Attention from Future Queries Distribution](https://mlsanity.com/paper/2510.00636/) (2025)
- [R-KV: Redundancy-aware KV Cache Compression for Reasoning Models](https://mlsanity.com/paper/2505.24133/) (2025)
- [Twilight: Adaptive Attention Sparsity with Hierarchical Top-p Pruning](https://mlsanity.com/paper/2502.02770/) (2025)
- [AdaReTaKe: Adaptive Redundancy Reduction to Perceive Longer for Video-language Understanding](https://mlsanity.com/paper/2503.12559/) (2025)
- [RocketKV: Accelerating Long-Context LLM Inference via Two-Stage KV Cache Compression](https://mlsanity.com/paper/2502.14051/) (2025)
- [Accelerating Streaming Video Large Language Models via Hierarchical Token Compression](https://mlsanity.com/paper/2512.00891/) (2025)
- [The Sparse Frontier: Sparse Attention Trade-offs in Transformer LLMs](https://mlsanity.com/paper/2504.17768/) (2025)
- [CriticalKV: Optimizing KV Cache Eviction from an Output Perturbation Perspective](https://mlsanity.com/paper/2502.03805/) (2025)
- [d2Cache: Accelerating Diffusion-Based LLMs via Dual Adaptive Caching](https://mlsanity.com/paper/2509.23094/) (2025)
- [Tactic: Adaptive Sparse Attention with Clustering and Distribution Fitting for Long-Context LLMs](https://mlsanity.com/paper/2502.12216/) (2025)
- [Memory-Efficient Visual Autoregressive Modeling with Scale-Aware KV Cache Compression](https://mlsanity.com/paper/2505.19602/) (2025)
- [ThinKV: Thought-Adaptive KV Cache Compression for Efficient Reasoning Models](https://mlsanity.com/paper/2510.01290/) (2025)
- [TriAttention: Efficient Long Reasoning with Trigonometric KV Compression](https://mlsanity.com/paper/2604.04921/) (2026)
- [SCOPE: Optimizing Key-Value Cache Compression in Long-context Generation](https://mlsanity.com/paper/2412.13649/) (2024)
- [Dialogue Without Limits: Constant-Sized KV Caches for Extended Responses in LLMs](https://mlsanity.com/paper/2503.00979/) (2025)
- [SparseMM: Head Sparsity Emerges from Visual Concept Responses in MLLMs](https://mlsanity.com/paper/2506.05344/) (2025)
- [SpecVLM: Enhancing Speculative Decoding of Video LLMs via Verifier-Guided Token Pruning](https://mlsanity.com/paper/2508.16201/) (2025)
- [A Silver Bullet or a Compromise for Full Attention? A Comprehensive Study of Gist Token-based Context Compression](https://mlsanity.com/paper/2412.17483/) (2024)
- [Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores](https://mlsanity.com/paper/2507.08143/) (2025)
- [Semantic Integrity Matters: Benchmarking and Preserving High-Density Reasoning in KV Cache Compression](https://mlsanity.com/paper/2502.01941/) (2025)
- [LazyEviction: Lagged KV Eviction with Attention Pattern Observation for Efficient Long Reasoning](https://mlsanity.com/paper/2506.15969/) (2025)
- [LAVa: Layer-wise KV Cache Eviction with Dynamic Budget Allocation](https://mlsanity.com/paper/2509.09754/) (2025)
- [Fast KVzip: Efficient and Accurate LLM Inference with Gated KV Eviction](https://mlsanity.com/paper/2601.17668/) (2026)
- [Past- and Future-Informed KV Cache Policy with Salience Estimation in Autoregressive Video Diffusion](https://mlsanity.com/paper/2601.21896/) (2026)
- [Head-Aware KV Cache Compression for Efficient Visual Autoregressive Modeling](https://mlsanity.com/paper/2504.09261/) (2025)
- [KVzap: Fast, Adaptive, and Faithful KV Cache Pruning](https://mlsanity.com/paper/2601.07891/) (2026)
- [FastKV: Decoupling of Context Reduction and KV Cache Compression for Prefill-Decoding Acceleration](https://mlsanity.com/paper/2502.01068/) (2025)

## Abstract (arXiv)

Large Language Models have excelled in various domains but face efficiency challenges due to the growing Key-Value (KV) cache required for long-sequence inference. Recent efforts aim to reduce KV cache size by evicting vast non-critical cache elements during runtime while preserving generation quality. However, these methods typically allocate compression budgets uniformly across all attention heads, ignoring the unique attention patterns of each head. In this paper, we establish a theoretical loss upper bound between pre- and post-eviction attention output, explaining the optimization target of prior cache eviction methods, while guiding the optimization of adaptive budget allocation. Base on this, we propose it Ada-KV, the first head-wise adaptive budget allocation strategy. It offers plug-and-play benefits, enabling seamless integration with prior cache eviction methods. Extensive evaluations on 13 datasets from Ruler and 16 datasets from LongBench, all conducted under both question-aware and question-agnostic scenarios, demonstrate substantial quality improvements over existing methods. Our code is available at https://github.com/FFY0/AdaKV.