信任质量：KV-Cache淘汰中的强制权重

# 相信大众：KV缓存淘汰中的强制权重
来源：https://arxiv.org/html/2608.25230

###### 摘要
所有已部署的稀疏注意力或KV缓存淘汰规则都会保留一个键子集，丢弃其余键，并在保留子集上对注意力权重进行重新归一化。对来自五个模型的168,192个注意力行进行枚举，在约束条件下找出精确的最佳子集，这表明保留权重最大的键已经接近最优，因为最佳子集仅能将剩余差距的中位数进一步缩小2%到5%（即填补到完整注意力差距的2%-5%）。如果选择只能闭合这么一点差距，那么已发表的淘汰方法之间的差距必然来自其他方面，因此我们测量了每种方法所占用的字节数。在共享评估管道中，最强的与查询无关的方法因为将其每头选择存储为掩码，从而保留了完整的缓存，只有不规则的按头存储才能释放这部分内存。对一个固定选择施加名义预算会带来14.1到62.2个基准点的性能损失。我们将一个87.6点的检索差距追溯到问题可见时计算的排名。ContourKV是一个无需训练的分配器，基于丢弃质量统计量构建，在160次两两比较中，有93次击败了上述最先进的方法，仅在强制执行基线方法的字节预算计数时输了2次，并且与其中最强的基线方法打平。

## 1 引言
KV缓存在每个注意力头的每个过去存储一个键和一个值向量，在长上下文服务中主导着内存使用，因此已部署的系统通过淘汰条目来缩减其大小。每个已部署的淘汰或稀疏注意力规则都保留一个键子集，并在该子集上重新归一化softmax权重，然后返回重新归一化的平均值作为密集注意力输出的替代，因此这些方法之间的区别仅在于如何选择子集[22, 41, 20, 5]。经典的子集近似方法会重新求解其保留点上的权重，并基于几何性质进行选择[6, 18, 9, 21]。淘汰则强制使用固定权重。我们量化了在权重被强制后，任何保留子集所能获得的最大收益，并识别出已发表的淘汰方法比较实际上衡量的是什么。
我们对五个模型的168,192个注意力行，在强制权重下枚举了精确的最佳子集，这揭示了保留权重最大的键已经接近最优。最佳子集将到密集输出的差距中位数进一步缩小了2%到5%，而一个廉价的交换规则就能完全恢复这个中位数差距。被选择丢弃的权重可以预测这些例外情况（§2）。
如果选择只能闭合这么一点差距，那么已发表的淘汰方法之间的差距必然来自其他方面。因此，我们在该领域自身的评估管道上运行这些方法，并读取每个方法占用的字节数。差距分解为内存、查询信息和计算。那些在未见问题情况下进行压缩的最强方法按注意力头进行选择，而管道将该选择存储为一个不会缩小的缓存上的掩码，因此它们已发表的质量是在完整内存下的选择质量（§4）。
因此，我们发现对一个固定选择施加名义预算会带来14.1到62.2个基准点的性能损失（§4），而87.6点的检索差距可追溯到在问题可见时计算的排名（§4）。
我们部署了我们的分配规则ContourKV。它在160次与KVzip[20]（该类别中的领先方法）的比较中，赢了93次，输了2次，其预算与KVzip的完整缓存进行强制执行（内存比率见附录D）。在匹配内存下，它与Compactor[5]（强制执行自身预算的最强基线）打平。这个平局证实了在部署规模上的测量结果（§2.2），因为当选择只能闭合剩余差距的几个百分点时，两个接近子集最优的规则无法区分开来。
ContourKV是免训练的，并借用了所比较方法自身的重要性得分，其预算在读取任何结果之前就在物理上强制执行了。我们的贡献是测量和核算（定位见§3），这并不依赖于ContourKV的获胜。我们的目标是到密集输出的差距——这是压缩器在查询前唯一可以优化的量。我们注意到，优化差距仅在缓存被重用时是理想的。这是多轮对话的情况，其中单个压缩缓存服务于所有后续查询，同时解码过程不断追加。允许每个头持有不同数量条目的存储就是为该缓存构建的[19]。下游损失是分开的（附录E）。

## 2 算子与冻结头测量
### 2.1 算子
完整细节和证明见附录A。
###### 定义2.1（术语）。
一个实例是一个在\[N\]=\{1,...,N\}上严格为正的概率向量$p$，具有点$v_1,\dots,v_N \in \mathbb{R}^d$和均值$\mu=\sum_j p_j v_j$。一个非空保留集合$A \subseteq [N]$有$p(A)=\sum_{j \in A} p_j$，其中$p_j$是键$j$的质量，它有丢弃质量$\bar{p}(A)=1-p(A)$，且$m_A=\sum_{j \in A} (p_j/p(A)) v_j$。最大质量集合$A_s^\star$是一个包含$s$个最大质量键的集合，且$D=\max_j \|v_j-\mu\|$。在一个注意力头，$p$是查询行的一行，$v_j$是值，$\mu$是密集输出，$m_A$是任何已部署稀疏算子返回的结果。我们称$\bar{m}_s=\bar{p}(A_s^\star)$为可达到的最小丢弃质量。对于$|A|=s$，令$\mathrm{ef}(A)=\mathrm{dist}(\mu,\mathrm{conv}\{v_j:j \in A\})$为权重被重新求解下的误差，$\mathrm{es}(A)=\|\mu-m_A\|$为权重被强制下的误差。它们在$|A|=s$上的最小值分别是$\mathrm{EF}(s)$和$\mathrm{ES}(s)$，且$\kappa(s)=\mathrm{es}(A_s^\star)/\mathrm{ES}(s) \geq 1$。

###### 引理2.1。
对于$0 < s \leq N$，$\mathrm{ES}(s) \leq \mathrm{es}(A_s^\star) \leq 2 D \bar{m}_s$。

**证据**。上界来自三角不等式和$\mu - m_{A_s^\star} = \sum_{j \notin A_s^\star} (p_j/p(A_s^\star)) (v_j - \mu)$，并利用范数可加性。下界来自对$A_s^\star$的定义。

###### 定理2.1。
在权重被强制的情况下，最大质量集合与均匀丢弃相比，在$1-\bar{m}_s/2$的分位数上，将到密集输出的差距减少了至多$2D\bar{m}_s$，在$\bar{m}_s=0$时减少0。

**证据**。均匀丢弃产生一个与$A_s^\star$质量相同但点不同的集合$A$，且$\mathrm{es}(A) \leq 2D$。$\mathrm{es}(A_s^\star)$的界来自引理2.1。

### 2.2 枚举
我们在146个族中的168,192个实例上枚举了$A_s^\star$，$s \in \{4, 8, 16, 32\}$，在$s=64, 128, 256$时对四个族进行了枚举（附录B.1）。我们验证了$\mathrm{ES}_{\mathrm{pool}}$在$s=4$时全局最优占解决实例的37%，在$s=4,8,16,32$时占$32.4\%$，并找到了在$4.9\%$实例上质量更好的子集（每个改进都收紧了$\mathrm{ES}$）。在$s=8$时，我们观察到$\hat{\kappa}=1.11$，从$s=32$时的$35.6\%$上升到$37.8\%$，然后到$s=8$时的$38.7\%$，增量递减。求解器确认在解决的实例中，有$37\%$的$\mathrm{ES}_{\mathrm{pool}}$全局最优，并在$4.9\%$的实例上找到了实质性更好的子集（每次改进都收紧了$\mathrm{ES}$）。

#### 惩罚。
我们发现强制权重的代价随预算增长。比率$\pi(s)=\mathrm{ES}(s)/\mathrm{EF}(s) \geq 1$分析了强制权重相对于自由权重最优的情况。在参考族上，中位数$\pi$从$1.07$上升到$1.79$，其第99百分位数从$2.2$上升到$6.8$，当$s$从$4$下降到$32$（附录B.3）。一旦权重被重新归一化，几何选择也比最大质量选择表现更差（表8）。

#### 选择上限。
我们发现，对于八个族和所有预算，中位数$\hat{c}$在$0.021$到$0.047$之间，每个预算的$95\%$区间在$[0.017, 0.051]$内，在$\hat{\kappa} > 1.11$的实例上上升到$0.200$到$0.254$。该份额是针对最大质量到密集的差距$\mathrm{es}(A_s^\star)$测量的，因为我们保留所有键时恢复了$\mu$，并且这个份额很小，因为大的差距不常见（在$s \in \{4, 8\}$时，$89\%$到$90\%$的实例上$\hat{\kappa} \leq 1.5$，$97\%$的实例上$\hat{\kappa} \leq 2$，附录B）。最大质量在$s=4$时$39\%$的实例上直接达到$\mathrm{ES}_{\mathrm{pool}}$，在$s=8$时为$21\%$。我们证明平衡选择器达到了这个界限，在每个族和预算中恢复了中位数$1.00$的可闭合差距（$[1.00, 1.00]$，图1）。在$\hat{\kappa} \leq 1.5$且$s=4$时，每个族的覆盖范围从$0.75$（OLMo-2）到$0.95$（Qwen3-0.6B），并且在$\hat{\kappa} \leq 2$时，每个族都超过$0.91$。在覆盖范围内，中位数$\hat{\kappa}$在$1.00$到$1.03$之间，第90百分位数在$1.14$到$1.28$之间；由于$\hat{\kappa}$被限制在候选集中，这些是上界估计。我们无法在已部署的$s=64$到$256$（命题2.1）上精确搜索，但没有任何选择器能获得超过$\mathrm{es}(A_s^\star) \leq 2D\bar{m}_s$（引理2.1）的收益，并且这个上限在$s=64$时降至其中位数值的$28\%$到$34\%$，在$s=256$时降至$8\%$到$12\%$。平衡子集在$s=64$到$256$的两个审计族上保持可行，并闭合了$0.04$到$0.13$的差距，达到或超过其$s=32$的水平，因此这个份额是$c$的下界（表1，附录B.4）。因此，$\mathrm{es}(A_s^\star)$随$s$减小而减小，而可闭合比例保持稳定。

表1：本然预算：在所有预算中，平衡子集闭合的最大质量到密集差距的中位数份额，这是$c$的下界，在一种约定下（垂直线标记枚举边界）。该份额保持在小预算水平直到$s=256$，而它适用的差距（由丢弃质量封顶，最后一行，汇总）崩溃。平衡在$21\%$到$30\%$的Qwen2.5-1.5B行和$47\%$到$59\%$的OLMo-2行上，跨预算至少比最大质量好$10\%$。最后一行给出了在已部署预算下的剩余差距，作为两个审计族（Qwen2.5-1.5B/OLMo-2-1B，§2.4）本然预算记录上$s=8$值的份额。

### 2.3 预测
参考说明图2：地图。每个单元格，左面板显示$s=8$时的中位数丢弃质量，右面板显示相同记录的中位数$\hat{\kappa}$。单元格级别的AUC为$0.82$到$0.94$，平衡闭合了那些中位数$\hat{\kappa}$达到$1.11$的单元格。由于$\hat{\kappa} \leq \kappa$，这些单元格是确定的。

#### 丢弃质量证明。
我们发现$\bar{m}_s$能唯一预测一个实例是否具有$\mathrm{es}(A_s^\star) > 0$和$\hat{\kappa} > 1.11$，在四个头条族上AUC为$0.76$到$0.85$，在十个分支上为$0.76$到$0.89$。我们测试了一个$O(Nd^2)$的谱替代方案；它表现如随机。已发表的绝对界将$\mathrm{es}(A_s^\star)$的Spearman相关性排到$0.98$，但在$\hat{\kappa}$上降至$0.21$到$0.70$[34]。该预测在不同内容类型和检索上下文中可复制（表2，附录B.5）。我们发现引理2.1中的$\Phi=\|g_{A_s^\star}\|$是一个单遍$O(Nd)$统计量，并在参考族上跨预算与$\mathrm{ES}_{\mathrm{pool}}$的Spearman相关性为$0.84$到$0.98$，按族汇总为$0.80$到$0.98$（表8和表6）。机制源于§2，因为具有小$\bar{m}_s$的行将选择器的增益限制在$2D\bar{m}_s$，而具有大$\bar{m}_s$的行保留了$p_j(v_j-\mu)$项，交换可以抵消这些项。每个单元格，$\bar{m}_s$给出了图2的地图，并且平坦单元格的位置是架构性的，由查询-键归一化和窗口化设置（表6中每个族的边缘与内部比率），因此我们部署$\bar{m}_s$，因为一个硬编码的边缘规则在查询-键归一化和窗口化的模型上会失败。在H100上，计算$\bar{m}_s$是最大质量选择已经做的工作的$O(s)$增量，在$N=2,048$到$16,384$时，相当于密集注意力层的$0.002\times$到$0.03\times$（在$N=16,384$时每层$0.12$毫秒）。

表2：参考族上的内容多样性（72,576个实例）。“份额”是$\hat{\kappa} > 1.11$的实例比例，并且AUC在所有三种内容类型上可复制。余量本身依赖于内容，代码携带最多（中位数$\kappa$到$1.06$），这与较平坦的注意力留下更大尾部的情况一致。输入级别的$95\%$区间在份额上约为$\pm 5$个百分点，在AUC上为$\pm 0.01$到$\pm 0.035$。

#### 任务结构化上下文。
我们在任何捕获之前记录了所有界限，并且所有界限在构建为集中检索的上下文中都成立。汇总的$\hat{c}$保持在每个预算$0.016$到$0.042$（记录的上限$0.09$），检索关键行相对于背景的第90百分位余量比为$0.83$到$0.97$（上限$2$）。需要值感知选择的情况发生在$s=8$时$1.87\%$的检索行上（上限$5\%$），预测在AUC $0.75$到$0.80$（下限$0.70$）上传递。我们在植入的针[28]、多跳变量链和长文档QA上进行测试，在令牌空间中组装，使得针位置精确，检索行至少占实例的$20\%$。地图的单元格标签（平坦和非平坦）在这些上下文中成立（标签一致性$0.90$到$0.93$，排序相关性$+0.94$到$+0.97$）。

### 2.4 审计
#### 已部署选择器与损失。
已部署的选择器SnapKV、H2O、Quest和StreamingLLM在小预算下远高于最优，在$s=8$时，中位数是$\mathrm{ES}_{\mathrm{pool}}$的$1.4$到$2.1$倍，而三个更敏锐族上的最大质量为$1.02$到$1.03$，同时TOVA的保留集本身就是最大质量[22, 41, 29, 33, 38]。SnapKV的误差在已部署预算下保持在同一预算最大质量误差的$1.8$到$2.2$倍；$\bar{m}_s$在无查询-键归一化时，将每个规则的多余误差按Spearman相关性$0.70$到$0.84$排序（附录C）。仅将平坦单元格切换到平衡，在$s=8$时将五个族（四个系，1B到77B，所有区间低于零）的留出续写交叉熵降低了$0.122$到$0.243$纳特。我们在模型前向传播中测量损失。