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

TL;DR - GraceKV reformulates KV cache compression as a global resource-allocation problem under a fixed budget, rather than applying fixed token-eviction or merging rules, so cache capacity can flow across layers, heads, and context slots. It matters because KV cache storage and access are a primary bottleneck for long-context LLM inference.

• Each layer–KV-head–slot combination is treated as an atomic unit represented by a prototype tree: leaves are token-level KV entries, and internal nodes compress their children into a single prototype; a set of non-overlapping nodes forms the unit's representation.
• Two competing actions trade off globally for the shared budget — adding a new tree root expands information coverage, while splitting a node improves local resolution — letting the method jointly balance coverage and resolution instead of fixing one policy.
• Training-free, with compression and inference running entirely on GPU.
• Reported to rank first in 24 of 32 evaluated settings across long-context tasks and compression ratios, remaining robust up to 128× compression.