跳转至

KV缓存淘汰的概率解释

文章背景与核心概要

在大语言模型（LLM）的推理过程中，KV（键-值）缓存占据了大量的显存并成为限制吞吐量的主要瓶颈之一。KV缓存淘汰技术通过在保持模型质量损失最小的前提下丢弃部分缓存条目，从而有效提升了系统的吞吐性能。然而，现有的缓存淘汰方法大多依赖于各种启发式规则，缺乏统一的理论形式化。

本文首次通过概率推理的视角对KV缓存淘汰问题进行了严格的形式化建模，证明了该问题在计算上的困难性，并揭示了它本质上可归约为主通过采样的期望估计问题。这一理论突破不仅使解码时修正（decode-time correction）成为可能，还证明了现有的文献方法实际上是零方差的有偏估计量，可以进行针对性改进。实验表明，这种基于概率视角的KV缓存淘汰方法在保持同等压缩预算下竞争力的同时，显著提升了在多任务上的鲁棒性。

Executive Summary

This paper formalizes the problem of KV (Key-Value) Cache Eviction—a technique used to improve LLM throughput by dropping cache entries with minimal quality loss—through the lens of probabilistic reasoning.

While existing methods rely heavily on creative heuristics, this work proves that the problem is computationally hard and demonstrates that it fundamentally reduces to expectation estimation via sampling. Furthermore, this probabilistic perspective makes decode-time correction feasible, revealing that current literature methods are zero-variance biased estimators that can be easily adapted. Practical evaluations show that this approach significantly improves robustness across different tasks while maintaining competitive performance at equivalent compression budgets.

本文从概率推理的角度，对KV（键-值）缓存淘汰问题进行了形式化研究。KV缓存淘汰是一种通过丢弃部分缓存条目来提升大模型吞吐量、同时将质量损失降至最低的技术。

尽管现有方法在很大程度上依赖于各种创造性的启发式规则，但本研究证明了该问题在计算上是困难的，并论证了它本质上可归约为通过采样的期望估计（expectation estimation）。此外，这种概率视角使得解码时修正（decode-time correction）成为可能，并揭示了现有文献中的方法实际上是零方差的有偏估计量，能够被轻松改造。实际评估表明，这种方法在维持同等压缩预算下的竞争性能的同时，显著提升了跨任务的鲁棒性。

Paper Metadata

  • arXiv ID: 2608.28293
  • Primary Subject: Computation and Language (cs.CL)
  • Secondary Subjects: Artificial Intelligence (cs.AI)
  • Publication Date: August 28, 2026
  • Authors: Renato Geh, Alex Chen, Daniel Israel, Aditya Grover, Guy Van den Broeck
  • License: Creative Commons Attribution 4.0 International license icon

论文元数据

  • arXiv ID: 2608.28293
  • 主要学科: 计算与语言 (cs.CL)
  • 次要学科: 人工智能 (cs.AI)
  • 发布日期: 2026年8月28日
  • 作者: Renato Geh, Alex Chen, Daniel Israel, Aditya Grover, Guy Van den Broeck
  • 许可协议: 知识共享署名 4.0 国际 license icon

Abstract

The premise and promise of KV cache eviction is simple: higher throughput can be achieved by evicting some entries from the KV cache, at a negligible cost to quality. This holds empirically for many existing methods, though most rely on creative heuristics for selecting which entries to drop.

Despite recent advances, the problem of KV eviction has remained informal in the literature. This paper aims to properly formalize this problem through the lens of probabilistic reasoning and reveal what can be learned from this perspective. Concretely, the authors: 1. Formalize the problem of KV eviction and prove that it is computationally hard. 2. Show that it reduces to expectation estimation, which can be approximated through sampling by framing it probabilistically. 3. Enable decode-time correction, solving a previously ignored problem of correcting for evicted entries during decoding. 4. Reveal that existing methods are zero-variance biased estimators that can be easily adapted to enable decode-time correction.

In practice, this probabilistic version of KV eviction coupled with decode-time correction proves more robust across diverse tasks compared to existing heuristics while achieving competitive performance at the same compression budget.

摘要

KV缓存淘汰的前提和愿景很简单：通过从KV缓存中淘汰部分条目，可以在付出微不足道的质量代价下实现更高的吞吐量。对于许多现有方法而言，这一点在经验上已经得到了证实，尽管大多数方法在选择要丢弃的条目时依赖于创造性的启发式规则。

尽管近期取得了进展，但在现有文献中，KV缓存淘汰问题一直缺乏正式的理论定义。本文旨在通过概率推理的视角对该问题进行适当的形式化，并揭示从这一视角中能够获得哪些深刻见解。具体而言，作者完成了以下工作： 1. 形式化了KV淘汰问题，并证明了其计算复杂性。 2. 证明了该问题可归约为期望估计，通过将其构架为概率问题，可以通过采样进行近似。 3. 实现了解码时修正，解决了以往被忽视的在解码过程中对被淘汰条目进行修正的问题。 4. 揭示了现有方法本质上是零方差的有偏估计量，并且可以轻松调整以支持解码时修正。

在实践中，与现有的启发式方法相比，这种结合了解码时修正的概率版KV缓存淘汰方法在处理多样化任务时表现出更强的鲁棒性，同时在相同的压缩预算下达到了具有竞争力的性能。

Access & Resources

访问与资源