# HubKV 论文 Walkthrough

接下来我会用一条主线讲清楚 HubKV：它解决什么问题，为什么现有 Top-K 范式会有局部冗余，方法如何从 submodular coverage 落到可并行实现，以及早期尝试为什么最后收敛到当前方案。早期方案没有进入最终版本，主要原因是实验效果一般；后面提到的“可能原因”是基于实现逻辑和论文主线做的机制解释，目的是帮助理解试错过程，而不是替代实验结果本身。

## 1. 这篇论文一句话在讲什么

HubKV 想解决的是一个很朴素的问题：长上下文推理时，KV cache 太大，我们必须删掉一部分历史 token，但现有很多方法只是把每个 token 单独打分，然后保留分数最高的 Top-K。这个做法看起来合理，却会忽略一个关键事实：语言里的信息常常是成团出现的。一个实体名、一个代码片段、一句定义、一个公式附近的 token 往往一起高分；如果 Top-K 把预算都花在这个局部高分簇里，cache 里留下的东西虽然“每个都高分”，但整体覆盖面会很窄。

HubKV 的核心观点是：KV cache 压缩不应该只问“每个 token 自己有多重要”，还应该问“如果附近已经有代表 token 被保留了，这个 token 还能带来多少新增信息”。这就是论文从 modular Top-K 走向 submodular coverage 的逻辑。

本文最终方案是 `fastkvzip_head_nms_gated_k5_p0.5_mild`。它不是重新训练一个 scorer，也不是实现昂贵的全局组合优化，而是在 FastKVzip/KVzip 这类已有 scorer 之后加一个轻量 score refinement：找局部 hub、软折扣 hub 的邻居、根据 head selectivity 做温和校准，再用 compression ratio 控制干预强度，最后仍然走原来的 Top-K pruning 接口。

## 2. 背景：KV cache 为什么需要压缩

Transformer 在自回归生成时，会把历史 token 的 Key 和 Value 缓存在显存里。这样生成下一个 token 时，模型不用重新计算全部历史，只需要让新 token 的 Query 去 attend 已经缓存的 Key/Value。这个机制让推理快很多，但它的显存成本会随着上下文长度线性增长。

当 context 从几千 token 增长到几十万 token 时，KV cache 会变成主要瓶颈。压缩 KV cache 的任务就是：在预算有限的情况下，选出一部分历史 KV pair 保留，让模型后续生成仍然尽可能保留长上下文能力。

很多已有方法都遵循同一个工程范式：

```text
历史上下文 -> 给每个 token/KV pair 打重要性分数 -> 保留 Top-K -> 删除其余 KV
```

FastKVzip 也可以放进这个范式里理解。它用训练好的 gate 预测每个 layer/head/token 的重要性分数；sink tokens 和 recent local window 会被强制保护；最后仍然通过 budgeted Top-K/bottom-K pruning 删除低分 KV pair。因此，HubKV 的切入点不是推翻 FastKVzip，而是在“分数进入 Top-K 之前”修正它。

## 3. 先理解 modular vs. submodular

### Modular：每个 token 的价值互相独立

如果我们把每个 token 的分数记为 `s_i`，标准 Top-K 等价于最大化：

```text
F_mod(S) = sum_{i in S} s_i
```

这叫 modular objective。它的意思是：选中 token `i` 的收益永远等于 `s_i`，不管集合 `S` 里已经有什么。它把 cache 压缩看成“捡最高分物品”的问题。

这个假设的好处是简单、并行、GPU 友好。坏处是它完全不关心冗余。例如一个局部片段里有 10 个 token 都高分，Top-K 可能连续选走很多个；但对理解上下文来说，保留其中几个代表 token 以后，旁边 token 的新增收益可能已经很小。

### Submodular：新增收益会递减

Submodular objective 想表达的是 diminishing returns：同一个 token 的新增价值取决于当前已经选了什么。如果附近已经有相似 token 被保留，那么再保留一个邻居带来的增量就应该下降。

直观例子是做一份文章摘要。第一句关于“实验设置”的话很重要，因为它覆盖了一个新主题；如果后面连续五句话都重复同一个设置，那么它们虽然也相关，但边际收益会越来越小。一个好的摘要不会只摘取同一个段落里的高分句子，而会尽量覆盖多个主题。

HubKV 把 KV cache retention 类比成一个局部覆盖问题：选中的 token 不仅代表自己，也覆盖附近相似的信息。于是理想目标更像 facility-location：

```text
F_sub(S) = sum_i max_{j in S} w_{i,j}
```

这里 `w_{i,j}` 表示 token `j` 对 token `i` 的覆盖能力。这个目标自然具有 submodular 性质：如果某个区域已经被一个 hub token 覆盖，再选附近 token 的新增覆盖就会变小。

关键点是：HubKV 不直接运行 sequential submodular greedy。真正的 greedy 需要一轮轮计算边际收益，太慢，不适合 LLM inference。论文把 sequential greedy 当作理论 oracle，然后设计一个 one-pass、可并行的近似：Submodular Marginal Discounting，也就是 SMD。

## 4. 论文整体逻辑

整篇论文可以按六步讲：

1. **问题**：KV cache 随上下文长度线性增长，必须压缩。
2. **现有范式**：大多数 score-based 方法先打分，再 Top-K 保留，本质是 modular selection。
3. **观察**：高分 token 并不是均匀散开，而是局部聚集；Top-K 的覆盖效率会快速下降；不同 attention head 的分数分布也有不同选择性。
4. **理论解释**：局部高分簇意味着 token utility 不是独立的，应该用 submodular local coverage 描述 diminishing returns。
5. **方法**：HubKV 用 SMD 做 one-pass score refinement，保留 Top-K 的工程接口，但让分数带有局部边际收益意识。
6. **实验结果**：在这些尝试中，`fastkvzip_head_nms_gated_k5_p0.5_mild` 的效果最好，因此被选为当前 paper 的最终方案；其他改型效果一般，可以作为理解最终选择的对照。

这条主线的好处是很清楚：paper 不是单纯提出一个 trick，而是从 Top-K 的目标函数缺陷出发，用观察证明缺陷真实存在，再用 submodular coverage 给出建模语言，最后落到一个足够轻量的工程实现。

## 5. 关键观察：Top-K 的局部冗余

论文的观察部分主要说明：Top-K 的问题不是“完全找不到重要 token”，而是容易把有限预算集中在局部高分簇里。这个现象可以从覆盖效率、分数局部相关性和 head 功能差异三个角度看到。

第一，Top-K 的 marginal spatial gain 会下降。也就是说，一开始选择高分 token 时，可能覆盖很多新的 context segment；但很快后续 token 就开始落在已经覆盖过的局部区域里，新覆盖越来越少。这说明 Top-K 正在把预算花到重复区域。

第二，importance score 有明显短距离 autocorrelation。相邻 token 的分数高度相关，说明高分不是孤立点，而是局部簇。这为“局部冗余”提供了统计证据。

第三，不同 attention head 的行为不一样。有的 head 很尖锐，能清楚指出关键 token；有的 head 更平坦，像背景分布。最终方法因此不能只做 token-level local suppression，还需要 head-wise selectivity calibration。

论文中的 1D-NMS 观察实验提供了一个直接信号：压低局部高分簇中的非峰值邻居，可以把预算推向更多上下文 segment。最终方法不是简单使用 hard NMS，而是把这个思路软化成 SMD，并叠加 head-wise 与 ratio-aware 的稳定机制。

## 6. HubKV 方法：从观察到实现

HubKV 的方法可以从 FastKVzip 的原始 score tensor 开始讲。设原始分数为：

```text
s_{layer, head, token}
```

HubKV 只改这些分数，不改 scorer，不改 cache 数据结构，也不改最终 Top-K pruning。

### Step 1：Local hub detection

对每个 layer 和 head，沿 token 维度做一维 max-pooling。局部窗口中分数最高的 token 被视为 hub。它代表该局部区域里最有信息密度的 token。

```text
M_i = 1 if token i is a local maximum, else 0
```

### Step 2：Submodular Marginal Discounting

hub 保留原分数，非 hub 邻居做软折扣。最终方案中 `p0.5` 对应 discount factor `gamma=0.5`：

```text
q_i = M_i * s_i + (1 - M_i) * 0.5 * s_i
```

这一步就是 SMD。它不是把邻居直接删除，而是降低邻居在全局 Top-K 里的竞争力，让预算更容易流向其他局部区域。

### Step 3：Bounded head-wise selectivity

HubKV 在非保护 content region 上计算每个 head 的选择性：

```text
c_h = std_h / (mean_h + epsilon)
```

如果一个 head 的分数更尖锐，它可能更擅长指出关键 token；如果一个 head 很平坦，它可能更像背景。最终方案用温和的 clipped weight：

```text
beta_h = clip((c_h / mean_head(c_h))^0.5, 0.8, 1.2)
u_i = beta_h * q_i
```

这里的 `[0.8, 1.2]` 很重要。它允许 head calibration 起作用，但不允许它压过原始 scorer。

### Step 4：Compression-ratio gate

压缩率越高，预算越紧，越需要去冗余；压缩率越低，原始分数已经足够安全，不应该过度干预。所以最终方案用：

```text
alpha = compression_ratio^2
z_i = s_i + alpha * (u_i - s_i)
```

这就是 gated 的含义。它让 HubKV 在轻度压缩时接近 FastKVzip，在重度压缩时更积极地打散局部冗余。

### Step 5：Protected bypass

sink tokens 和 recent local window 是稳定推理的基础。HubKV 最后把这些 token 的分数重新设为最高保留分，避免它们被 local discount 或 head calibration 误伤。

## 7. 最终方案为什么是 `fastkvzip_head_nms_gated_k5_p0.5_mild`

最终方案的参数如下：

| 参数 | 值 | 直观含义 |
| --- | --- | --- |
| `nms_kernel` | `5` | 小窗口局部 hub detection，中心左右各约 2 个邻居 |
| `penalty_factor` | `0.5` | non-hub 邻居保留一半分数，属于 soft discount |
| `head_weight_temperature` | `0.5` | head calibration 温和化 |
| `min_head_weight` | `0.8` | head 权重下界 |
| `max_head_weight` | `1.2` | head 权重上界 |
| `gate_power` | `2.0` | 默认 ratio gate 指数 |

这组参数体现的是“保守但有效”的选择。`k=5` 不会像大窗口那样过度打散连续证据；`gamma=0.5` 不会像 hard NMS 那样直接清零邻居；`mild` head calibration 不会让某些 head 的统计量主导全局排序；`compression_ratio^2` gate 让干预强度跟 cache pressure 绑定。

最终选择 `fastkvzip_head_nms_gated_k5_p0.5_mild`，最直接的原因是它在现有尝试中效果最好。从机制上看，它不是“最强局部抑制”，而是“最稳的 score correction”：保留了局部排斥的有效部分，又通过 mild head calibration 和 ratio gate 避免过度改写原始 FastKVzip 分数。这也更贴合 paper 的主张：HubKV 是一个 bounded、hardware-parallel 的 marginal-gain proxy。

## 8. 早期尝试与可能的失败原因

这些早期 idea 大多没有进入最终方案，主要原因是实验效果一般。下面的解释保留为“可能的失败原因”：它们从机制上说明为什么这些方法可能不稳定、收益有限，或者与最终论文主线不够贴合。它们不是无用尝试，反而帮助收敛出了最终方案的三个原则：不要扩大局部簇，不要过度重写原始 scorer，不要引入顺序瓶颈。

| 路线 | 代表类 | 动机 | 做法 | 效果一般的可能原因 |
| --- | --- | --- | --- | --- |
| 局部平滑 | `CommunitySmoothFastKVzipPress` | 连续 token 形成语义社区 | avg-pool 平滑分数 | 会扩大高分簇，削弱 hub 辨别，和去冗余目标相反 |
| 方差置信度 | `VarianceCalibratedFastKVzipPress` | 方差高的 head 更有判断力 | head variance 乘回分数 | 全局统计过粗，尺度不稳，可能误伤保护 token |
| 朴素 NMS | `NMSFastKVzipPress` | 打散局部高分簇 | local max 保留，邻居折扣 | 有效内核，但缺 head calibration 和 ratio gate |
| Head-aware NMS | `HeadwiseNMSFastKVzipPress` | 区分尖锐 head 和平坦 head | selectivity 权重乘 NMS 分数 | 有效组件，但固定强度干预可能过强 |
| 因果加法子模 | `StreamingSubmodularFastKVzipPress` | 用历史冗余模拟边际收益递减 | 因果卷积后做加法扣分 | 方向偏置、超参敏感、可能把分数截到零 |
| 低秩谱滤波 | `LowRankSpectrumFastKVzipPress` | 跨 head 分数有低秩主干 | SVD 截断重建 | 可能抹掉稀有但关键的 head-specific anchor |
| 信息瓶颈 | `InfoBottleneckFastKVzipPress` | 惩罚所有 head 都喜欢的大众 token | 减去跨 head global prior | 多 head 共识常常正是关键 token |
| 残差 SVD | `ResidualSVDFastKVzipPress` | 比纯 SVD 更保守 | raw 与 low-rank 混合 | 仍不直接解决局部冗余 |
| 层级残差 SVD | `LayerwiseResidualSVDFastKVzipPress` | 深层更适合强去噪 | alpha 随层数增加 | 引入额外层级假设，主线变复杂 |
| IB + SVD | `IB_SVDFastKVzipPress` | 先去大众信息，再提主成分 | IB 后做 SVD | 两种风险叠加，仍非局部冗余建模 |
| 乘法 CMA | `CMAFastKVzipPress` | 避免加法扣分的负值问题 | `score * exp(-redundancy)` | 更稳但仍是因果卷积，超参敏感 |
| 随机贪心 | `StochasticGreedyFastKVzipPress` | 直接近似 facility-location greedy | 多步随机候选贪心 | 顺序、随机、慢，不适合 inference path |
| 自适应 CMA | `AdaptiveTauCMAFastKVzipPress` | 自动估计覆盖半径 | 几何均值推导 tau | 自适应规则间接，跨任务稳定性存疑 |

最终方案从这些尝试里留下了两件真正有用的东西：一维局部排斥和 head selectivity。但它用 gated + bounded 的方式把它们收住，避免走向过强修正。

## 9. 当前 NMS family 的尝试与可能失败原因

当前代码已经从早期发散探索收敛到 NMS family。最终选择 `fastkvzip_head_nms_gated_k5_p0.5_mild` 的直接原因仍然是它效果最好；其他 NMS 改型效果一般。下面是这些结果背后可能的机制原因，用来解释为什么最终方案需要同时包含 soft local discount、mild head calibration 和 ratio gate。

| 改型 | 做法 | 效果一般的可能原因 |
| --- | --- | --- |
| `fastkvzip_nms` | 只做一维 NMS/SMD | 缺少 head-wise selectivity 和 ratio gate，不同压缩率下不够稳 |
| `fastkvzip_head_nms_*` | 固定强度 head-aware NMS | 轻度压缩时也完整改写分数，干预可能过强 |
| `*_tiny` | head 权重 `[0.9, 1.1]`，temperature `0.25` | 太保守，head 功能差异体现不充分 |
| `k7_p0.2_mild` | 更宽窗口、更强折扣 | 覆盖更激进，但可能破坏连续事实、代码片段和推理链 |
| `head_budget_waterfill` | NMS 后直接做硬选择 | 从 score refinement 变成硬预算分配，破坏原始 ranking 的连续竞争 |
| `head_budget_selectivity` | 按 selectivity 给 head 分配保留数 | selectivity 不一定等于任务价值，离散预算脆弱 |
| `head_budget_entropy` | 按 entropy 信息量分配预算 | 对尺度和分布形状敏感，可能误判 head |
| `head_budget_hybrid` | selectivity 与 entropy 组合 | proxy 组合更复杂，主线解释成本变高 |

decoding 版本可以作为扩展能力提及，但不建议成为 paper 主线。HubKV 当前最清楚的故事仍然是 prefill-time score refinement。

## 10. 可以写进论文的核心表达

可以把 paper 的核心表达压成下面这段：

HubKV starts from the observation that score-based KV eviction is usually modular: each token is ranked independently and the cache keeps the Top-K entries. However, high-importance tokens in long contexts are spatially clustered, so retaining several neighboring tokens often yields diminishing marginal returns. HubKV therefore views cache retention as a score-weighted local coverage problem and uses the corresponding submodular objective as a theoretical oracle. Instead of running sequential greedy optimization, HubKV implements a one-pass score correction: it detects local hubs, softly discounts neighboring non-hubs, applies bounded head-wise selectivity calibration, and gates the correction by compression ratio. The corrected scores are then passed to the same Top-K pruning interface as the base scorer.

中文讲法则是：

> HubKV 的贡献不是发明一个更复杂的选择器，而是指出 Top-K 的目标函数假设错了：它把 token utility 当成互相独立，但长文本里的信息天然局部冗余。HubKV 用 submodular coverage 给这个问题建模，再把边际收益递减压缩成一个可以并行执行的分数修正层。