CriticalKV: Optimizing KV Cache Eviction from an Output Perturbation Perspective

Large language models have revolutionized natural language processing but face significant challenges of high storage and runtime costs, due to the transformer architecture's reliance on self-attention, particularly the large KV cache for long-sequence inference. Recent efforts to reduce KV cache size by pruning less critical entries based on attention weights remain empirical and lack formal grounding. This paper presents a formal study on identifying critical KV cache entries by analyzing attention output perturbation. Our analysis reveals that, beyond attention weights, the value states within KV entries and pretrained parameter matrices are also crucial. Based on this, we propose a perturbation-constrained selection algorithm that optimizes the worst-case output perturbation to identify critical entries. We demonstrate that our algorithm is a universal, plug-and-play enhancement that incurs negligible computational overhead. When integrated with three state-of-the-art cache eviction methods on three distinct LLMs, our algorithm significantly reduces the compression loss by more than \textit{half} on average across 29 datasets from the Ruler and LongBench benchmarks. Further perturbation analysis, at both the head and layer levels, confirms the principles underlying our effectiveness. This work offers a new, formally grounded perspective to cache eviction , opening promising avenues for future research. The code is publicly available at \url{https://github.com/FFY0/DefensiveKV}.

Large language models (LLMs) struggle with long texts due to the massive memory footprint of their context storage, the KV cache. Current methods compress this cache using ungrounded heuristics, which can accidentally delete critical information and degrade model accuracy. We introduce a rigorous framework to identify essential memory entries by analyzing "output perturbation"—measuring how deleting an entry distorts the model's final output. Proving that the cached data itself is as vital as attention weights, we developed a plug-and-play algorithm that mathematically minimizes errors during compression. When added to existing compression techniques, our algorithm cuts performance loss by over 50% across diverse benchmarks. It provides a formally grounded, highly effective solution for building faster and more memory-efficient LLMs.