# Every Cache Entry Earns Its Place: Global Allocation of Resolution and Coverage for KV Cache Compression

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

## Key facts

- Cited by 2 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 17 of its 28 references that are in the map.
- First posted on arXiv 7 Aug 2026.

## Placed in

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

## Builds on (most cited first, 17 of 17)

- [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)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (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)
- [∞Bench: Extending Long Context Evaluation Beyond 100K Tokens](https://mlsanity.com/paper/2402.13718/) (2024)
- [Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference](https://mlsanity.com/paper/2407.11550/) (2024)
- [Keyformer: KV Cache Reduction through Key Tokens Selection for Efficient Generative Inference](https://mlsanity.com/paper/2403.09054/) (2024)
- [Not All Heads Matter: A Head-Level KV Cache Compression Method with Integrated Retrieval and Reasoning](https://mlsanity.com/paper/2410.19258/) (2024)
- [Model Tells You Where to Merge: Adaptive KV Cache Merging for LLMs on Long-Context Tasks](https://mlsanity.com/paper/2407.08454/) (2024)
- [ChunkKV: Semantic-Preserving KV Cache Compression for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2502.00299/) (2025)
- [SpeCache: Speculative Key-Value Caching for Efficient Generation of LLMs](https://mlsanity.com/paper/2503.16163/) (2025)
- [ZSMerge: Zero-Shot KV Cache Compression for Memory-Efficient Long-Context LLMs](https://mlsanity.com/paper/2503.10714/) (2025)
- [Homogeneous Keys, Heterogeneous Values: Exploiting Local KV Cache Asymmetry for Long-Context LLMs](https://mlsanity.com/paper/2506.05410/) (2025)
- [SemantiCache: Efficient KV Cache Compression via Semantic Chunking and Clustered Merging](https://mlsanity.com/paper/2603.14303/) (2026)

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

- [CORE: COverage CAlibration and Evicted-Mass REdistribution for KV Cache](https://mlsanity.com/paper/2610.02235/) (2026)
- [Compile the Table: Query-Calibrated Operator Compression for Tabular In-Context Learning](https://mlsanity.com/paper/2610.11784/) (2026)

## Abstract (arXiv)

As large language models (LLMs) process increasingly long contexts, KV cache storage and repeated access have become a major bottleneck. Existing KV cache compression methods rely on predefined, fixed compression rules and are typically developed around either token eviction or merging. As a result, cache resources can neither flow freely across layers, heads, and context slots, nor be jointly allocated to balance local resolution and information coverage. Therefore, we propose GraceKV, a global approach for the allocation of resolution and coverage in KV cache compression, and formulate the compression process as a global resource allocation problem under a fixed cache budget. GraceKV treats each layer-KV-head-slot combination as an atomic unit and builds a prototype tree. Leaf nodes correspond to token-level KV entries, while each internal node uses a single prototype to compress the KV space covered by its children. A set of non-overlapping nodes in the tree forms the representation of an atomic unit. Adding the root of a new tree expands information coverage, whereas splitting a selected node improves local resolution. All candidate actions compete globally for a shared cache budget. Finally, the nodes retained across all trees form the compressed KV cache. This process adaptively determines the allocation of cache resources among atomic units globally and the balance between resolution and coverage. GraceKV requires no additional training, and the entire compression and inference process is performed on the GPU. Systematic experiments across diverse long-context tasks and compression ratios show that GraceKV ranks first in 25 of 32 settings and remains robust up to 128-fold compression. These results validate the effectiveness of global budget allocation in coordinating information coverage and local resolution.