Predicting Future KV Utility: Global Combinatorial Optimization for Task-Agnostic KV Cache Eviction
Ziyao Tang, Pengkun Jiao, Xinhang Chen, LiuWei Liu, Shiyong Li, Jingjing Chen
Abstract
Given the quadratic complexity of attention, KV cache eviction is vital to accelerate model inference. Current KV cache eviction methods typically rely on instantaneous heuristic metrics, implicitly assuming that score magnitudes are consistent proxies for importance across all heads. However, this overlooks the heterogeneity in predictive fidelity across attention heads. While certain heads prioritize the \textit{instantaneous contribution} of tokens, others are dedicated to capturinglong-horizon utility. In this paper, we propose that optimal budget allocation should be governed by the marginal utility in preserving long-term semantic information. Based on this insight, we propose LU-KV, a novel framework that optimizes head-level budget allocation through a convex-hull relaxation and a marginal-utility-based greedy solver to achieve near-optimal precision. Furthermore, we implement a data-driven offline profiling protocol to facilitate the practical deployment of LU-KV.
BibTeX
@inproceedings{
tang2026predicting,
title={Predicting Future Utility: Global Combinatorial Optimization for Task-Agnostic {KV} Cache Eviction},
author={Ziyao Tang and Pengkun Jiao and Xinhang Chen and Wei Liu and Shiyong Li and Jingjing Chen},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=FQLxcBsKIb}
}