KV 缓存驱逐的概率解释

KV（缓存）驱逐的前提和承诺很简单：通过从 KV 缓存中驱逐一些条目可以实现更高的吞吐量，而质量成本可以忽略不计。这对于许多现有方法来说在经验上是成立的，尽管大多数方法都依赖于创造性启发法来选择要删除的条目。尽管最近取得了进展，KV 驱逐问题在文献中仍然是非正式的。本文旨在通过概率推理的视角正确地形式化这个问题，并揭示从这个角度可以学到什么。具体来说，我们（1）形式化了 KV 驱逐问题，不幸的是，证明它在计算上是困难的，（2）表明通过概率性地构建它，KV 驱逐减少到期望估计问题，这可以通过采样来近似，（3）表明通过这种概率解释，在解码过程中纠正被驱逐条目（以前被忽视的问题）变得可行，（4）揭示文献中的现有方法是零方差可以轻松调整偏置估计器以实现解码时间校正。在实践中，我们表明，与现有的驱逐方法相比，这种结合解码时间校正的 KV 驱逐的概率版本对于不同的任务更加稳健，并且在相同的压缩预算下实现了有竞争力的性能。