用随机采样让缓存淘汰误差可追踪,提升长对话召回率。
Error Certificates for KV-Cache Eviction via Randomized Design

- 用泊松采样替代确定性淘汰,使每个保留项带误差证书。
- 在30轮对话中,召回率从9%提升至97%,26-30轮前信息召回率达97%。
- 适合关注推理可靠性与资源优化的系统设计者,尤其长对话场景。
确定性键值缓存淘汰仅保留重要性得分前k项,删除其余内容,但系统无法知晓淘汰代价。本文改用已知包含概率的泊松采样,使淘汰误差可识别,并将保留集上的抽样方差估计器转化为每步一个标量形式的误差证书。在压缩至10%缓存预算的30轮助手对话中,证书门控系统对回忆类问题的召回率为0.97,而传统top-k仅为0.09;对26至30轮前提及的事实,召回率97%对比2%。证明了任何基于确定性方案保留信息的误差估计器均不一致:被删内容可被修改,而保留内容不变,真实注意力输出误差却可无限增长。在泊松设计下,证书覆盖实际注意力误差比例达96.9–97.7%(12,096次重播单元),在12种额外架构上为98.1–99.7%。随机化带来归因而非预测:在LongBench上预注册研究显示,25–50%预算下,基于问题感知的淘汰近乎无成本,输出对数似然为更优失败预测因子,证书能区分淘汰引入与固有失败,AUC达0.65–0.75(对比随机门控的0.47–0.54),并以1.7–1.8倍增益触发重计算。真实长期对话中,该系统在高损伤区间仍可返回全缓存性能,且触发规则在五个模型家族间保持一致。
原文摘要 · Abstract (English)
Deterministic KV-cache eviction keeps the top-$k$ tokens under an importance score and deletes the rest, and after the deletion the serving system cannot know what the eviction cost it on the current query. We replace the deterministic tail with Poisson sampling at known inclusion probabilities, which makes the eviction error identifiable and turns a survey-sampling variance estimator over the retained set into a per-step error certificate at one extra scalar per retained token. On a thirty-turn assistant compressed to a 10\% cache budget, the certificate-gated system answers 0.97 of recall questions against 0.09 for top-$k$, and for facts stated 26 to 30 turns earlier it recalls 97\% against 2\%. We prove that no estimator computable from the information a deterministic scheme retains is consistent for its own eviction error: evicted values can be altered so that everything retained is unchanged while the true attention-output error grows without bound. Under the Poisson design the certificate covers the realized attention error in 96.9--97.7\% of 12{,}096 replay cells and in 98.1--99.7\% on twelve further architectures. Randomization buys attribution, not prediction: a pre-registered study on LongBench at 6k and 16k tokens (about 74{,}000 generations) finds question-aware eviction at 25--50\% budgets nearly free and output log-probability the better failure predictor, while the certificate answers the question confidence cannot, separating eviction-induced from inherent failures at AUC 0.65--0.75 against 0.47--0.54, and schedules recomputation at 1.7--1.8 times the gain of random gating. On real long-term conversations the gated system returns the full-cache score inside the heavy-damage regime, and the rule that triggers it is the same across five model families.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。