KV缓存压缩比TurboQuant与逐向量香农极限高出900000倍

# 基于概率语言前缀树的序列式 KV 缓存压缩：超越单向量香农极限
Source: https://arxiv.org/html/2604.15356

###### 摘要
近期关于 KV 缓存量化的研究，以 TurboQuant [13](https://arxiv.org/html/2604.15356#bib.bib14) 为代表，已接近 Transformer 键值缓存*逐向量（per-vector）*压缩的香农熵极限。但我们观察到，该极限适用的问题比真正关键的问题要*严格弱得多*：将 KV 缓存作为*序列*进行压缩。存储在 KV 缓存中的 token 并非任意浮点数据——它们直接采样自模型训练所基于的确切形式语言，且该模型在设计上就是该语言的近乎最优预测器。我们提出*序列式 KV 压缩（sequential KV compression）*，这是一种利用该结构的两层架构。第一层为*概率前缀去重（probabilistic prefix deduplication）*，利用来自概率语言前缀树（Probabilistic Language Tries, PLTs）[9](https://arxiv.org/html/2604.15356#bib.bib13) 的树度量 $d_{\mathcal{T}}(s,s') = -\log_2 P_{\mathcal{M}}(s \wedge s')$，识别跨会话间语义等价的共享前缀。第二层为*预测性差分编码（predictive delta coding）*，仅存储每个新 KV 向量相对于模型自身预测的残差，从而实现每 token 熵界 $H(\mathrm{KV}_{t+1} \mid \mathrm{KV}_{\leq t}) \leq H(\mathrm{token}_{t+1} \mid \mathrm{token}_{\leq t})$。我们证明，在典型的语言模型困惑度下（流畅英文文本约为 10–20），该上限平均每个 token 位置仅为 3.3–4.3 比特，而 TurboQuant 需要 3 比特*每个向量分量*（典型注意力头拥有 64–128 个分量）。在香农极限下，相较于 TurboQuant 的理论压缩比约为 $914,000\times$。即使在上限为熵底 $1000\times$（这是刻意偏悲观的最坏情况开销，比实际信源编码器常见的 2–5$\times$高出两个数量级），压缩比仍保持在约 914$\times$（相对 TurboQuant），且随着上下文长度增加，压缩效果反而提升而非下降。这两层正交且可组合，能与包括 TurboQuant 在内的现有逐向量化方法协同工作。

###### 目录
1. [引言](https://arxiv.org/html/2604.15356#S1)
2. [背景](https://arxiv.org/html/2604.15356#S2)
   1. [Transformer 推理中的 KV 缓存](https://arxiv.org/html/2604.15356#S2.SS1)
   2. [逐向量化：当前最佳实践](https://arxiv.org/html/2604.15356#S2.SS2)
   3. [概率语言前缀树](https://arxiv.org/html/2604.15356#S2.SS3)
3. [序列熵界](https://arxiv.org/html/2604.15356#S3)
   1. [设定与符号说明](https://arxiv.org/html/2604.15356#S3.SS1)
   2. [确定性引理](https://arxiv.org/html/2604.15356#S3.SS2)
   3. [主要界限](https://arxiv.org/html/2604.15356#S3.SS3)
   4. [界限的紧致性](https://arxiv.org/html/2604.15356#S3.SS4)
4. [第一层：概率前缀去重](https://arxiv.org/html/2604.15356#S4)
   1. [精确前缀共享基线](https://arxiv.org/html/2604.15356#S4.SS1)
   2. [作为去重标准的 PLT 树度量](https://arxiv.org/html/2604.15356#S4.SS2)
   3. [概率前缀去重下的存储开销](https://arxiv.org/html/2604.15356#S4.SS3)
5. [第二层：预测性差分编码](https://arxiv.org/html/2604.15356#S5)
   1. [预测过程](https://arxiv.org/html/2604.15356#S5.SS1)
   2. [残差及其熵](https://arxiv.org/html/2604.15356#S5.SS2)
   3. [残差的自适应量化](https://arxiv.org/html/2604.15356#S5.SS3)
6. [组合与完整架构](https://arxiv.org/html/2604.15356#S6)
   1. [两层的正交性](https://arxiv.org/html/2604.15356#S6.SS1)
   2. [与逐向量化的组合](https://arxiv.org/html/2604.15356#S6.SS2)
   3. [随上下文长度的渐近行为](https://arxiv.org/html/2604.15356#S6.SS3)
7. [实际实现](https://arxiv.org/html/2604.15356#S7)
   1. [高效预测计算](https://arxiv.org/html/2604.15356#S7.SS1)
   2. [与推理循环的集成](https://arxiv.org/html/2604.15356#S7.SS2)
   3. [基于树的索引前缀](https://arxiv.org/html/2604.15356#S7.SS3)
8. [相关工作](https://arxiv.org/html/2604.15356#S8)
9. [讨论](https://arxiv.org/html/2604.15356#S9)
   1. [两个香农极限](https://arxiv.org/html/2604.15356#S9.SS1)
   2. [对“内存墙”的影响](https://arxiv.org/html/2604.15356#S9.SS2)
   3. [与杰文斯悖论的关系](https://arxiv.org/html/2604.15356#S9.SS3)
   4. [KV 压缩的率失真分析](https://arxiv.org/html/2604.15356#S9.SS4)
   5. [与推测解码的联系](https://arxiv.org/html/2604.15356#S9.SS5)
   6. [局限性与开放问题](https://arxiv.org/html/2604.15356#S9.SS6)
   7. [猜想与开放问题](https://arxiv.org/html/2604.15356#S9.SS7)
   8. [结论](https://arxiv.org/html/2604.15356#S9.SS8)
10. [参考文献](https://arxiv.org/html/2604.15356#bib)

## 1 引言
每当 Transformer 语言模型处理一个 token 时，它都会生成一对向量——一个*键（key）*和一个*值（value）*——存储于 KV 缓存中，并在所有后续的注意力计算中被复用。该缓存是模型的工作记忆：它包含模型在当前上下文中处理过的所有内容的压缩表示。它也是大规模推理中的主要瓶颈之一。对于一个具有 $L$ 层、$H_{\mathrm{head}}$ 个注意力头、头维度 $d$ 和上下文长度 $n$ 的模型，KV 缓存占用 $2LH_{\mathrm{head}}dn$ 个浮点数值。在典型规模下（$L=80, H_{\mathrm{head}}=64, d=128, n=128,000$），70B 参数模型的单个上下文在 fp16 精度下就需要约 80 GB 的缓存内存——这甚至比模型权重本身还要大。

围绕 KV 缓存压缩，学术界已积累了丰富的文献。量化方法以更少的比特数表示每个缓存条目[8](https://arxiv.org/html/2604.15356#bib.bib7)、[4](https://arxiv.org/html/2604.15356#bib.bib8)。淘汰机制会丢弃不太可能影响未来注意力分数的条目[14](https://arxiv.org/html/2604.15356#bib.bib9)、[7](https://arxiv.org/html/2604.15356#bib.bib10)。前缀共享机制在多个会话共享相同前缀时避免冗余计算[10](https://arxiv.org/html/2604.15356#bib.bib5)、[5](https://arxiv.org/html/2604.15356#bib.bib6)。TurboQuant [13](https://arxiv.org/html/2604.15356#bib.bib14) 近期统一并扩展了量化研究方向，通过 PolarQuant 旋转后接 QJL 残差校正，实现了近最优的逐向量压缩，并证明了严格的下界，表明没有任何逐向量方法能取得显著更好的效果。

#### TurboQuant 未能填补的差距
TurboQuant 的下界是紧致的——针对它所解决的问题而言。该问题是：*给定一个从旋转后分布中抽取的孤立 KV 向量，表示它所需的最小比特数是多少？* 论文给出的答案是每个分量约 3 比特，而 TurboQuant 正好达到了这一水平。但 KV 缓存并非孤立向量的集合。它是一个*序列*。每个向量都是在特定上下文的特定位置处理某个 token 时生成的，而该 token 及其位置均来自一个结构化概率分布——即模型训练时所建模的分布。在第 $t$ 个 KV 向量在所有先前向量条件下的信息论内容，并非其作为孤立样本的原始熵。而是其*条件熵*，即在处理完第 1 到 $t-1$ 个 token 后模型状态的条件熵。该条件熵可能小得多。对于处理连贯文本的优质语言模型而言，下一个 token 高度可预测——因此下一个 KV 向量也高度可预测。残差很小。其熵受限于模型的每 token 意外度（surprisal），在典型困惑度 10–20 下，整个 token 位置的熵仅为 3.3–4.3 比特，而非每个分量 3.3–4.3 比特。TurboQuant 的下界与该序列下界之间的差距并非四舍五入造成的误差。它是语言的完整冗余性——即香农在 1951 年[11](https://arxiv.org/html/2604.15356#bib.bib2)所发现的、且每个优质语言模型都内嵌的每 token 10–15 比特的可预测结构。

#### 本文贡献
我们精确定义了这一差距，并提出*序列式 KV 压缩*，这是一种能填补该差距的两层架构。我们的贡献如下：
1. **序列熵界**（Theorem 1）：严格证明在给定所有先前缓存条目的条件下，KV 向量的条件熵上界由模型的每 token 意外度决定。
2. **概率前缀去重**（第 4 节）：利用 PLT 树度量[9](https://arxiv.org/html/2604.15356#bib.bib13)，识别跨会话间语义等价的共享前缀，仅存储相对于共享质心的增量（delta），消除了超出精确前缀匹配之外的会话间冗余。
3. **预测性差分编码**（第 5 节）：在单个会话内，仅存储每个 KV 向量相对于模型自身预测的残差，该残差熵受限于 token 级别的意外度。
4. **可组合性**（第 6 节）：两层均与逐向量化方法正交，可叠放在 TurboQuant 或任何其他量化器之下协同工作。
5. **渐近行为**（推论 5）：与压缩比固定于头维度的逐向量方法不同，序列式压缩*随上下文长度增长而提升*，因为处理过更多 token 的模型对未来内容的预测分布更为精确。

#### 为何如今成为可能
KV 缓存的序列结构并非新鲜事物。新颖之处在于为其建立了形式化框架：PLT 树度量[9](https://arxiv.org/html/2604.15356#bib.bib13)在概率空间中给出了“token 序列间距离”的严格数学定义，该文中的先验引导缓存定理为使用模型自身的概率估计而非经验频率来识别共享结构提供了理论基础。本文将该框架应用于 KV 缓存压缩这一具体问题。

#### 文章结构
第 2 节回顾 KV 缓存、逐向量化及 PLT 框架。第 3 节建立序列熵界。第 4 节介绍概率前缀去重。第 5 节引入预测性差分编码。第 6 节分析各层的组合方式。第 7 节探讨实际实现细节。第 8 节将本研究置于相关文献脉络中。第 9 节讨论深远影响与开放性问题。

## 2 背景
### 2.1 Transformer 推理中的 KV 缓存
具有 $L$ 层的 Transformer 语言模型通过处理 token 序列 $\mathbf{t}=(t_1,\ldots,t_n)$ 来实现推理。在每一层 $\ell$ 和位置 $i$ 处，分别计算键向量 $\mathbf{k}^{(\ell)}_i \in \mathbb{R}^d$ 和值向量 $\mathbf{v}^{(\ell)}_i \in \mathbb{R}^d$。这些向量通过学习的投影矩阵从输入嵌入和前一层激活值中计算得出：
$$\mathbf{k}^{(\ell)}_i=W_K^{(\ell)}\mathbf{x}^{(\ell)}_i,\qquad \mathbf{v}^{(\ell)}_i=W_V^{(\ell)}\mathbf{x}^{(\ell)}_i$$
*KV 缓存* $\mathcal{K}$ 存储了所有层 $\ell\in\{1,\ldots,L\}$ 和处理过的位置 $i\in\{1,\ldots,n\}$ 对应的 $(\mathbf{k}^{(\ell)}_i,\mathbf{v}^{(\ell)}_i)$ 对，使得后续 token 能够注意力关注所有先前位置而无需重新计算。在自回归生成过程中，序列每延长一个 token 仅需一次前向传播加上针对缓存的 $O(n)$ 次注意力操作；若无缓存则需 $O(n^2)$ 次操作。总缓存大小为 $2LH_{\mathrm{head}}dn$ 个值，其中 $H_{\mathrm{head}}$ 为注意力头数量，$d$ 为单头维度。在 fp16 格式下（每个值 2 字节），70B 模型处理 128K 长度的上下文需要约 80 GB 显存。

### 2.2 逐向量化：当前最佳实践
KV 缓存压缩的主流方法是量化：以更少的比特数表示每个浮点向量分量。关键挑战在于 KV 向量存在离群分量（outlier components）——某些维度的幅值远大于其他维度，若统一处理会导致严重的量化误差。TurboQuant [13](https://arxiv.org/html/2604.15356#bib.bib14) 通过以下两个操作解决该问题：
- **PolarQuant**：对每个 KV 向量应用一个学习的旋转矩阵 $R \in \mathbb{R}^{d \times d}$，使旋转后的分量呈现更均匀、更可预测的分布。由于旋转均匀应用于所有向量，只需预先计算一次，无逐向量额外开销。此举消除了以往感知离群值的方法为元数据支付的每分量 1–2 比特开销。
- **QJL（量化 Johnson-Lindenstrauss）**：使用预计算的量化器将旋转后的向量量化为每个分量 $b$ 比特。额外使用 1 个符号位来校正量化引入的预期偏差，确保从压缩向量计算出的注意力分数在统计上无偏。

该组合方案实现了 $16/b$ 的压缩比（例如当 $b=3$ 时约为 $5.3\times$），且精度损失可忽略不计。论文证明了理论下界：若将向量视为从旋转后分布中抽取的独立样本，则任何量化方案在不牺牲精度的前提下都无法获得更高的压缩比。该下界是紧的：TurboQuant 已达到逐向量量化的近最优水平。

### 2.3 概率语言前缀树
我们简要回顾 PLT 框架[9](https://arxiv.org/html/2604.15356#bib.bib13)，它为本文的序列式方法提供了形式化工具。

###### 定义 1（概率语言前缀树[9]）
设 $V$ 为有限词表，$\mathcal{M}$ 为定义在 $V^*$ 上的生成模型。*概率语言前缀树* $\mathcal{T}(\mathcal{M})$ 是一棵有向根树，其节点为前缀 $x \in V^*$，从节点 $x$ 出发的出边由 token $t \in V$ 标记，权重为 $P_{\mathcal{M}}(t \mid x)$。

###### 定义 2（树度量[9]）
对于两个序列 $s, s' \in V^*$，它们在树中的*最长公共前缀*记为 $s \wedge s'$——即两者共享的最大前缀。*树度量*定义为：
$$d_{\mathcal{T}}(s,s') = -\log_2 P_{\mathcal{M}}(s \wedge s')$$
拥有长且高概率共享前缀的序列在该度量下彼此邻近；它们的 KV 轨迹共享大量结构。该树度量具有直接的压缩解释意义：$d_{\mathcal{T}}(s,s')$ 即为定位该前缀所需的比特数