通过全局优化提升长程语义保留，实现高效无任务依赖的缓存淘汰
Predicting Future Utility: Global Combinatorial Optimization for Task-Agnostic KV Cache Eviction
- 将注意力头的缓存预算分配建模为全局组合优化问题
- 在LongBench和RULER上减少80%缓存大小，性能损失极小
- 适合追求推理效率与内存优化的模型部署场景
由于注意力机制具有二次复杂度，KV缓存淘汰对加速模型推理至关重要。现有方法通常依赖瞬时启发式指标，隐含假设得分大小可统一代表各注意力头的重要性。然而，这忽略了不同注意力头在预测能力上的异质性：某些头关注当前词元贡献，另一些则专注长期语义信息。本文提出，最优缓存预算应基于保留词元对长期语义的边际效用。据此，我们提出LU-KV框架，将头级预算分配建模为最大化长期边际贡献的全局组合优化问题。针对该非凸问题，采用凸包松弛与基于边际效用的贪心求解器，逼近近似最优解。此外，设计数据驱动的离线预分析流程以支持实际部署。在LongBench与RULER基准上的评估表明，LU-KV在仅轻微性能下降下，将缓存大小降低80%，同时降低推理延迟与GPU显存占用。
原文摘要 · Abstract (English)
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 instantaneous contribution of tokens, others are dedicated to capturing long-horizon utility. In this paper, we propose that optimal budget allocation should be governed by the marginal utility in preserving long-term semantic information. Building on this insight, we propose LU-KV, a novel framework that formulates head-level budget allocation as a global combinatorial optimization problem to maximize the long-horizon marginal contribution of reserved tokens. To solve this non-convex problem, we employ a convex-hull relaxation and a marginal-utility-based greedy solver, achieving near-optimal solutions. Furthermore, we implement a data-driven offline profiling protocol to facilitate the practical deployment of LU-KV. Evaluations on LongBench and RULER benchmarks demonstrate that LU-KV reduces KV cache size by 80% with minimal performance degradation, while also decreasing inference latency and GPU memory footprint.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。