KVgrad: Query-Agnostic KV Cache Eviction via Gradient-based Global Importance Scoring

Transformer-based Large Language Models (LLMs) suffer from substantial memory overhead and latency bottlenecks due to the linear scaling of the Key-Value (KV) cache. Existing KV cache eviction methods typically rely on local heuristics, scoring cached entries by their immediate contribution to the attention output while ignoring the downstream propagation of information to the final representation. To that end, we propose KVgrad, which carries out the eviction by using a query-agnostic importance score that quantifies a cache entry's global impact on the final representation. Based on a simple analysis using Taylor approximation and chain-rule, KVgrad factorizes the impact of a cached value into a linear local component and a gradient-based downstream sensitivity term. Then, we apply a magnitude-aware scoring scheme to stabilize the importance score. Evaluations on RULER and LongBench demonstrate that KVgrad achieves an average maximum compression ratio of 6.42x with negligible performance loss (<2%), significantly outperforming strong local-only state-of-the-art baselines. Furthermore, we demonstrate that our signal is highly amenable to distillation; by training a lightweight MLP to predict KVgrad scores from local hidden-state features, we enable high-fidelity, on-the-fly compression at negligible computational cost.