3 · KV 选择：读取、保留与淘汰

自回归解码每步只有一个新 query，却要读取不断增长的历史 KV。于是长上下文瓶颈从 prefill 的配对计算转向缓存容量和 HBM 流量。KV 选择至少包含两种不同动作：查询时只读取仍然存在的部分状态，以及提前删除被判断为以后不再需要的状态。前者下一步仍可改变选择，后者一旦误删便无法恢复，两者的质量风险和系统收益不能混为一个「压缩率」。

KV选择可按状态生命周期拆解。对第 $t$ 步，需要写清哪些 KV 被创建、驻留在哪一级存储、何时形成索引、哪些被读取、哪些被迁移或淘汰。若选择器仍需读取完整key矩阵, key流量与评分成本就没有消失, 但跳过未选value仍可能减少读取与AV计算. 小摘要也可以常驻HBM: Quest先读摘要再读候选K/V, 总流量低于稠密读取时仍有收益. 索引的存储位置、字节数与维护成本需要一起计算.量化、分页、前缀共享和卸载改变每个状态的字节数与位置，也会改变稀疏选择的交叉点。

1. 先算清 KV cache 的对象与成本

设 Transformer 有 $L$ 层，每层 KV head 数为 $H_{kv}$ ，单个 head 维度为 $d_h$ ，缓存元素使用 $s$ byte。保存长度为 $n$ 的单条序列，需要的 KV 容量近似为

M_{KV}=2LnH_{kv}d_hs.

系数 $2$ 分别对应 key 和 value。MQA与GQA通过减少 $H_{kv}$ 降低容量，但没有自动减少本步读取的 token 数。分页 KV cache 改善不规则请求的空间分配，也没有改变逻辑内容。Sparse Attention 若想进一步降低 decode 带宽，需要在发起 HBM 读取之前得到较小的地址集合，并让内核只加载这些地址对应的 KV。

容量和读取量也要分开。某种方法可以保留全部历史 KV，只在每步读取其中 $k$ 个位置；此时峰值容量仍随 $n$ 增长，单步注意力流量接近 $O(k)$ 。另一种方法把 cache 固定在 $k$ 个位置，容量与流量都受到限制，但被删除状态无法重新参与后续注意力。还有一类方法把冷 KV 迁移到主机或更慢介质，设备容量下降，命中失败时会增加传输和尾延迟。三个方案在平均 token/s 上可能接近，面对延迟引用时的行为却完全不同。

1.1. 重要性不是一个静态属性

注意力权重只描述某个 query 下的相对混合比例。一个历史 token 在连续数千步中权重很低，不代表未来不会突然成为关键约束。用累计权重定义 heavy hitter 可以保存长期高频状态，却可能漏掉低频但决定性的信息；只保留最近窗口能稳定处理局部模式，却无法独立应对远距离引用；永久保留 sink token 有助于窗口截断后的注意力稳定，也不等于保存了任务语义。

因此选择器需要说明时间尺度。逐步评分每生成一个 token 就更新重要性，响应快但成本高；按块或固定周期更新索引，能摊薄开销，却会在更新间隔内使用过期判断。跨层共享评分可以减少重复计算，但不同层关注的关系并不相同。若浅层偏向词法相似、深层偏向任务状态，统一淘汰表可能让某一层失去需要的信息。评价不能只报告平均保留率，还要观察每层、每 head 与不同生成阶段的选择差异。

SnapKV 一类方法利用观察窗口估计 prompt 中重要位置并压缩后续缓存，Quest 一类方法通过页级统计先筛选候选页，再读取页内 KV。二者都减少访问范围，前者更接近一次性压缩，后者更接近查询时选择。把方法放进生命周期后，差别会很明确：评分使用哪个 query 区间，索引何时建立，生成过程中是否更新，被排除状态是否仍存在，恢复需要什么额外路径。

2. 选择粒度决定系统形态

token 级选择在语义上细，但地址离散。GPU 读取许多不连续小片段时，实际传输会按 cache line 或更大的事务粒度发生，逻辑上未选中的字节仍可能进入芯片。块级或页级选择牺牲细粒度稀疏率，换来连续地址、较少索引和更规则的 kernel。块大小于是同时影响质量与执行：块大时关键 token 周围携带更多无关内容，块小时索引、排序和 gather 成本增加。

批处理又增加一层约束。连续 batching 中，不同请求的序列长度、生成进度和候选地址都不同。若每条请求独立选择，内核面对 ragged 的块表；若为批内请求合并候选，可以提高复用，却读取额外 KV。prefix cache 让多条请求共享前缀物理页，淘汰策略必须区分逻辑引用与物理引用，不能因一条请求结束便释放仍被其他请求使用的页。KV 选择最终必须与推理引擎的页表和引用计数协同。

分布式推理还要问 KV 位于哪里。张量并行通常让不同设备持有各自 head 或通道对应的 KV；序列并行或 context parallel 可能按位置切分。动态选择若跨越设备边界，就要发送 query、远程拉取 KV，或在各设备局部选择后再合并输出。局部 top-k 不一定等价于全局 top-k，合并过程也有通信成本。只有把设备映射写进选择算法，才能判断带宽是否从 HBM 转移到了互连。

读取选择保留完整 KV, 每个 decode step 再根据当前 query 决定读取哪些页. 这条路线先用 Quest 页级选择建立可计算的参照: 每页维护 key 的逐维最小值与最大值, 用一个只读摘要的上界筛选候选页, 随后只在候选有效token内计算attention并重新归一化;整体输出是稠密attention的近似. 它直接降低单步 HBM 流量, 但完整 cache 仍随上下文增长, 因而不能拿读取稀疏率冒充容量压缩率.

缓存驱逐把容量限制提前到状态生命周期: 新KV进入固定槽位时, 系统必须决定哪一项永久离开. H2O用累计attention保存反复访问的heavy hitters, 同时为最近token保留观察窗口. 这条路线能释放KV容量, 也承担不可恢复的误删风险; attention统计、page回收和位置元数据必须一起实现.

动态路由回答当前 query 怎样生成候选，训练继续处理选择器怎样获得监督和适应长度变化，内核则把候选页转成真实的 gather 与 attention 执行。KV 选择位于三者中间：它规定状态是否存在、驻留在哪儿，并为路由器提供可搜索的对象。若状态边界不明确，路由复杂度和内核流量都无法复算。

失效测试应主动制造未来相关性变化。例如某个名字在 prompt 开头只出现一次，生成很久以后才要求精确引用；多份相似文档只在一个数字上不同；同一事实被后文更新，模型必须使用较新的版本。此类测试能区分累计注意力、近期窗口和内容检索的能力边界。质量下降还要与缓存命中、索引更新和端到端延迟一起记录，才能知道错误来自信息已经删除、候选没有召回，还是内核没有按预期执行。

2.1. 比较时固定哪些条件

KV字节明细建立后, 再比较只读子集、永久淘汰与外存召回三条路线。每种方法都要说明选择粒度、恢复能力、与 GQA/MQA 的关系，以及真实推理引擎是否能跳过未选块。

沿单个 token 的生成过程，可以把 KV 状态变化写成一条完整链路：新状态写入、索引更新、候选页选择、字节加载以及未来恢复能力。「缓存压缩倍数」需要与质量任务、读取流量、更新成本和恢复能力一起报告，才足以支持部署判断。

工程复现时还要固定模型的层数、KV head 数、head 维度、缓存精度、页大小和请求长度分布。相同的保留比例放在 MHA 与 GQA 上，对总显存的绝对节省不同；相同的候选 token 数放在连续内存与分页布局上，读取事务也不同。报告这些配置不是附属信息，它们决定选择器有没有越过索引开销与稠密读取之间的性能交叉点。只有质量和系统两侧在同一组配置下测量，KV 选择的结论才可以复算。

稠密回退提供实验参照, 用同一模型、同一请求复算质量差额和系统差额, 也能暴露被漏选掩盖的问题。若恢复全部 KV 后答案仍然错误，问题不在选择器；若质量恢复但时延没有明显变化，瓶颈可能已经转移到线性层、调度或跨设备通信。

3. 一份 KV 的四种状态

按原始 KV 的可访问性, 把历史位置 $j$ 在时刻 $t$ 的状态记为 $z_{j,t}\in{\text{hot},\text{cold},\text{summary},\text{gone}}$ . hot 表示原始 KV 在当前设备上, 可直接参与 attention; cold 表示原值仍在较慢介质, 需要搬运; summary 表示原始 KV 已被聚合表示替代, 只能取得近似信息; gone 表示原值和可恢复副本都已删除. 这四类描述原始状态的去向, 辅助索引另行保存.

Quest 的页摘要与完整 KV 并存, 不会把页面变成只剩聚合表示的 summary 状态. min/max 用于筛选, 候选页的原始 K/V 随后进入 attention. 页未选中时仍保持 hot; 若系统把完整页卸载到外存, 则属于 cold, 需要回载. 后面的压缩摘要则用少量向量替代一组原始 KV, 逐 token 寻址能力随之丢失. 驱逐且没有恢复副本时才进入 gone.

这个状态机把「没有读到」分成三种机制。候选漏选时原 KV 仍在 hot，下一步可以重新选择；分层缓存未命中会增加时延，但信息仍可恢复；永久驱逐既节省容量，也把未来可选集合缩小。比较压缩方法时，应给出从每种状态恢复原 value 的条件，而不是只给保留 token 比例。

若第 $t$ 步的活跃集合为 $A_t$ ，设备容量约束为 $|A_t|\le B$ ，驱逐可写成在线决策：

A_{t+1}=(A_t\cup\{t+1\})\setminus E_{t+1}, \qquad |A_{t+1}|\le B.

$E_{t+1}$ 是处理第 $t+1$ 个输入位置时被淘汰的集合, 它依据截至该步的可见状态确定, 后续query尚未出现. 当步临时候选为 $A_t\cup{t+1}$ , 可暂时超过 $B$ ;公式约束的是驱逐后交给下一步的状态.它面对的是部分可观测问题：过去 attention 只能说明旧 query 如何使用 token，无法直接知道新 query 会问什么。H2O 的累计注意力、Scissorhands 的重要性持续假设以及近期窗口，都是利用历史统计估计未来价值。这些估计成立，需要未来访问分布与过去具有足够相关性；一句笼统的「注意力天然稳定」无法提供这个条件。

3.1. Query-aware 读取与永久驱逐的差别

Quest 为每个 KV 页保存 key 各维的最小值和最大值。给定 query $q$ ，逐维选择能让内积最大的端点，得到页内任意 key 分数的上界：

U(q,P)=\sum_{r=1}^{d_h} \begin{cases} q_r\max_{j\in P}k_{jr},&q_r\ge0,\\ q_r\min_{j\in P}k_{jr},&q_r<0. \end{cases}

若页 $P$ 的真实最优分数为 $M(q,P)=\max_{j\in P}q^\top k_j$ ，则 $M(q,P)\le U(q,P)$ 。上界由每一维可能来自不同 token 的极值拼成，通常并不对应页内某个真实 key，所以它可能宽松，却不会把真实高分页错误压低。选择top页后, 在候选有效token内用原KV计算QK、softmax与AV. QK分数保持原向量的点积, softmax分母则只包含候选, 整体近似由截断与重归一化共同产生.

永久驱逐没有这个安全网。被删除 key 的未来分数无法再算，除非另存摘要或外存副本。一个方法若用当前 query 选 top- $k$ 并直接删除其余项，便把「本步不重要」外推成「以后都不重要」；只有访问持续性很强时，这次选择才适合指导未来驱逐。打分可能来自当前 query、最近观察窗、从生成开始的累计量，也可能来自独立的未来价值预测器，这几种时间范围不能混用。

4. Heavy hitter 统计会偏向什么

令 $a_{tj}$ 为输入位置 $t$ 的query对位置 $j$ 的注意力权重, 因果mask允许 $j=t$ ，累计分数可写成

s_j(T)=\sum_{t=j}^{T}a_{tj}.

这里按在线保留集合归一化, 未进入当步候选的位置权重取0. 累计从自身可见的attention行开始, 与H2O手算的更新顺序相同. 它偏好持续得到小权重或多次得到大权重的位置.若两个 token 的总分相同，一个在最近一步突然升高，另一个在很早以前累积完成，原始累计和无法区分。可以使用指数衰减

s_j(T)=\rho s_j(T-1)+a_{Tj},\qquad 0<\rho<1,

使统计适应主题变化；代价是早期约束会逐渐失去保护。保留近期窗口相当于给新 token 一个观察期，在尚未积累足够分数前不参与淘汰。窗口太短会误删慢热证据，太长则挤压 heavy hitter 预算。

注意力头之间也不能直接相加而不说明尺度。各head的softmax总质量均为1. 低熵头集中在少数位置, 高熵头分散到更多位置;简单求和更偏向组内共同访问的位置, 而不额外增加高熵head的总质量.可以先按头归一化累计量，再取最大值、分位数或加权和。取最大值保护专门头，却容易被偶发尖峰占据；取平均值稳定，但可能删除只服务单一功能的 token。

4.1. 容量约束下的选择目标

理想策略希望最小化未来所有输出误差：

\min_{A_t:|A_t|\le B} \mathbb E\left[ \sum_{u=t+1}^{T} \|o_u-\hat o_u(A_t)\|_2^2 \mid \mathcal H_t \right],

其中 $\mathcal H_t$ 是当前可见历史。未来 query 与生成长度未知，使这个目标无法直接求解。累计注意力以过去访问近似未来访问，近期窗口以时间局部性作先验，分层预算以不同层的信息聚合程度作先验。所谓「重要性分数」都是对上述条件期望的代理。

如果只优化下一步，策略会忽略暂时沉默但以后重要的状态；如果对很长未来等权求和，又会让早期高频 token 长期占位。折扣因子、任务终止分布和恢复通道决定合理时间尺度。代理得分的消融应改变生成长度与主题切换位置，观察策略是否只适合固定评测轨迹。

5. 分层预算为何可能有效

PyramidKV 观察到低层 attention 较分散，高层逐渐集中，并据此给不同层分配不同 cache 预算。可以把第 $\ell$ 层的预算记为 $B_\ell$ ，总容量约束为

\sum_{\ell=1}^{L}B_\ell\le B_{\text{total}}.

若已知每层在预算 $B_\ell$ 下的误差曲线 $e_\ell(B_\ell)$ ，理想分配满足边际收益近似均衡：继续给某层增加一个槽位所减少的误差，与给其他层增加槽位的收益相当。真实网络中各层误差会相互作用，所以独立曲线只是起点；某一层删掉的信息可能在后续层无法重建。

层间共享 KV 的模型还会改变计数单位。若多个层读取同一组 KV，保留一个位置可能同时服务多层，边际收益不再属于单层。反过来，不同层拥有独立投影时，即使 token ID 相同，也必须保存各自的 K 与 V。报告「保留 128 个 token」时必须说明是每层 128、全模型共享 128，还是按层变化后平均 128。

5.1. 压缩摘要的可恢复边界

把一组 value 聚合成摘要 $\bar v=\sum_jw_jv_j$ 会保留某个加权方向，却丢失逐 token 可寻址性。以后 query 若只需要相同聚合，摘要足够；若要区分组内两个相近实体，单个向量无法还原。增加多个摘要槽相当于提高局部秩，可以用重构误差衡量保留能力：

\min_{C\in\mathbb R^{m\times d_h},\,W} \|V-WC\|_F^2,\qquad m<|P|.

低重构误差也不保证 attention 输出误差低，因为 query 关心的方向并非各向同性。用真实 query 分布加权，目标可改为比较 $\operatorname{softmax}(QK^\top)V$ 与压缩结果。这样能区分「value 可压缩」和「key 仍能把 query 路由到正确摘要」两件事。

驱逐与摘要可以组合：保留近期原 KV、若干 heavy hitter 原 KV，再为被删区域维护压缩槽。原值路径支持精确引用，摘要路径支持大范围背景。组合方法应分别关闭三条支路，确认质量来自哪一部分；只与全 cache 比总分无法判断摘要是否真正补回了被删信息。