Abstract:Key-value (KV) caching is essential for large language model inference, yet its memory overhead poses a critical bottleneck for long-context generation. Existing eviction policies predominantly rely on empirical heuristics, lacking a rigorous theoretical foundation. This work rethinks KV cache eviction through the lens of the Information Bottleneck principle. Under a linear-Gaussian surrogate of attention, we derive a closed-form mutual information objective that characterizes the effective information capacity of a retained KV cache subset. This formulation reveals that a wide range of existing eviction strategies can be interpreted as different approximations of the same capacity-maximization principle. Guided by this insight, we introduce CapKV, a capacity-aware eviction method that directly targets information preservation via a log-determinant approximation using statistical leverage scores. This approach replaces heuristic selection with a theoretically grounded mechanism that preserves the maximum predictive signal. Extensive experiments across multiple models and long-context benchmarks show that CapKV consistently outperforms prior methods, achieving a better trade-off between memory efficiency and generational fidelity.
| Comments: | 19 pages, 6 figures |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Information Theory (cs.IT) |
| Cite as: | arXiv:2604.25975 [cs.LG] |
| (or arXiv:2604.25975v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2604.25975 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Chenwei Tang Dr. [view email]
[v1]
Tue, 28 Apr 2026 12:28:04 UTC (2,320 KB)