作者：Amir Zandieh, Majid Daliri, Majid Hadian, Vahab Mirrokni
机构：Google Research, New York University, Google DeepMind
链接：arXiv:2504.19874v1
一句话总结
TurboQuant 对输入向量做随机旋转使每个坐标服从已知的 Beta 分布，然后逐坐标应用预计算的最优标量量化器（Lloyd-Max），无需看数据、无需预处理，在任意位宽下 MSE 和内积失真均在信息论下界的 倍以内。
背景：为什么需要在线向量量化
向量量化（VQ）的核心目标是将高维浮点向量压缩为低位宽整数表示，同时尽量保持几何结构（距离和内积）。它在两个场景中至关重要：
- KV cache 压缩：LLM 推理时必须缓存所有已生成 token 的键/值向量，内存随上下文长度线性增长。量化 KV cache 是降低内存和通信开销的最直接手段。
- 近邻搜索：向量数据库需要在数十亿嵌入中做内积/余弦相似度搜索，量化压缩索引大小并加速距离计算。
现有方法存在明显的权衡：
| 类别 | 代表方法 | 核心缺陷 |
|---|---|---|
| 离线 / 数据依赖 | GPTQ, AWQ, 乘积量化（PQ） | 需要校准数据和大量预处理（k-means、Hessian），不适合 KV cache 等动态场景 |
| 在线 / 数据无关 | RTN, KIVI | 简单均匀量化，失真率随位宽的改善是多项式级别，远非最优 |
| 在线 + 理论保证 | QJL, PolarQuant | QJL 仅支持 1-bit；PolarQuant 仅优化内积，MSE 非最优 |
TurboQuant 的目标：设计一个在线、数据无关、加速器友好的量化器，在所有位宽下同时达到 MSE 和内积的近最优失真率。
问题定义
设计量化映射 （，位宽 ）和反量化映射 ，最小化以下两种失真：
MSE 失真（量化前后向量的 L2 距离）：
内积失真（量化前后内积的误差）：
对于内积量化器，还要求无偏性：
论文假设 ，这不具限制性：对一般向量先存储 L2 范数（一个浮点数），量化归一化后的向量，反量化时乘回范数即可。
核心方法一：MSE 最优 TurboQuant
随机旋转与 Beta 分布
TurboQuant 的第一步是对输入向量 乘以一个随机旋转矩阵 （通过对随机高斯矩阵做 QR 分解生成）。旋转后 均匀分布在单位超球面 上。
关键数学事实（引理 1）： 的每个坐标 服从 Beta 分布：
高维时该分布收敛到正态分布 。更重要的是，不同坐标 和 （）在高维中近似独立。
这两个性质的组合意味着：可以把 d 维向量量化问题拆解为 d 个独立的一维标量量化问题，每个坐标的分布已知且相同，大幅简化了算法设计。
最优标量量化（Lloyd-Max）
既然每个坐标都服从已知分布 ，最优标量量化就是一个连续一维 k-means 问题：将区间 划分为 个区域，每个区域用一个质心 代表，使加权 MSE 最小：
最优解满足 Voronoi 划分：区间边界是相邻质心的中点。这个优化问题通过 Lloyd-Max 迭代算法数值求解，对每个实际位宽 只需求解一次，结果预存为码本。
例如在中等维度 下， 的最优码本为 ， 的最优码本为 。
算法流程
量化（Quant_mse）：
- 计算 （随机旋转）
- 对每个坐标 ，找到最近质心：
- 输出索引向量 （共 bits）
反量化（DeQuant_mse）：
- 查表：
- 逆旋转：
- 输出重建向量
定理 1：MSE 性能保证
对任意位宽 和任意 ，TurboQuant_mse 的 MSE 失真满足：
推导过程：
由于 是正交矩阵，旋转保持 L2 范数不变：
每个坐标 独立地服从同一分布 ，且被同一最优标量量化器量化，因此：
对于 ，数值求解 得到精确值：
| 位宽 | ||||
|---|---|---|---|---|
对于更大的位宽 ，使用 Panter-Dite 高分辨率近似公式：
乘以 即得整体上界 。
核心方法二：内积最优 TurboQuant
为什么 MSE 量化器对内积有偏
MSE 量化器最小化了 ，但不保证内积的无偏性。以 为例，此时量化器将每个坐标映射到 （即符号函数），可以证明：
内积被系统性地缩小了 倍。偏差随位宽增加而减小，但在低位宽时不可忽略。
如果直接用 MSE 量化器做近邻搜索或注意力计算，所有内积都会被低估，导致 softmax 分布变平、检索召回率下降。
QJL：1-bit 无偏内积量化
量化 Johnson-Lindenstrauss（QJL）变换是一种 1-bit 量化方案，天然无偏：
其中 ，。反量化：
QJL 的性能保证：对任意 和任意 ：
- 无偏：
- 方差：
两阶段算法
TurboQuant_prod 将 MSE 量化和 QJL 组合为两阶段方案：
- 阶段 1：用位宽 的 TurboQuant_mse 量化 ，最小化残差的 L2 范数。残差 满足 。
- 阶段 2：对残差 应用 1-bit QJL 量化，得到 。
总位宽 = bits。
量化（Quant_prod）：
- 输出
反量化（DeQuant_prod）：
- 输出
MSE 量化器把残差的 L2 范数压得很小，QJL 对这个小残差做 1-bit 无偏估计。残差越小，QJL 的方差越低，最终内积误差就越小。两者各取所长：MSE 量化器负责“压小残差”，QJL 负责“消除偏差”。
定理 2：内积性能保证
对任意位宽 ，任意 和 ：
无偏性：
失真上界：
| 位宽 | ||||
|---|---|---|---|---|
| () |
推导核心：反量化输出 ，内积误差为：
由 QJL 的无偏性，（条件期望），因此整体无偏。方差项由 QJL 的方差界给出：
将 代入，结合 MSE 上界即得最终结果。
信息论下界
TurboQuant 不仅给出了上界，还证明了任何量化算法都无法做得更好的下界，从而说明 TurboQuant 是近最优的。
Shannon 失真率下界
对于均匀分布在 上的随机向量 ，Shannon 下界给出：
其中 是微分熵， 是总 bit 复杂度。代入超球面均匀分布的熵并化简，得到：
定理 3：下界
利用 Yao 的极大极小原理（将“最坏情况输入上的随机算法”转化为“随机输入上的确定性算法”），证明对任何量化算法 ：
与上界的对比
| TurboQuant 上界 | 信息论下界 | 比值 | |
|---|---|---|---|
对 MSE 而言，TurboQuant 与最优值仅差 倍。在低位宽时差距更小： 时实际比值仅约 。
上界和下界都以 的速率随位宽指数衰减。这意味着每增加 1 bit，失真降低 4 倍。相比之下，简单的均匀量化（RTN）失真仅以 衰减——TurboQuant 在位宽效率上实现了指数级改进。
实验结果
KV Cache 量化：大海捞针测试
在 Llama-3.1-8B-Instruct 上，将 KV cache 压缩至 25%（4× 压缩），评估 4K~104K token 长度下的信息检索能力：
| 方法 | KV 大小 | 检索性能 |
|---|---|---|
| Full Cache | 16 bit | 完美 |
| SnapKV / PyramidKV | 25% | 长序列显著衰减 |
| KIVI | 25% | 部分位置遗漏 |
| PolarQuant | 25% | 接近完美 |
| TurboQuant | 25% | 与全精度完全一致 |
KV Cache 量化：LongBench 端到端生成
| 方法 | KV 大小 | 单文档QA | 多文档QA | 摘要 | 平均 |
|---|---|---|---|---|---|
| Full Cache | 16 | 45.29 | 45.16 | 26.55 | 50.06 |
| KIVI | 3 | 43.38 | 37.99 | 27.16 | 48.50 |
| PolarQuant | 3.9 | 45.18 | 44.48 | 26.23 | 49.78 |
| TurboQuant | 2.5 | 44.16 | 44.96 | 24.80 | 49.44 |
| TurboQuant | 3.5 | 45.01 | 45.31 | 26.00 | 50.06 |
3.5-bit TurboQuant 的平均分与 16-bit Full Cache 完全持平，同时实现了 4.5× 压缩。2.5-bit 时仅有轻微下降。
近邻搜索
| 方法 | |||
|---|---|---|---|
| 乘积量化（PQ） | 37.04s | 239.75s | 494.42s |
| RabitQ | 597.25s | 2267.59s | 3957.19s |
| TurboQuant | 0.0007s | 0.0013s | 0.0021s |
TurboQuant 的量化时间比 PQ 快 倍，因为不需要运行 k-means 构建码本。在召回率上，TurboQuant 也持续优于 PQ 和 RabitQ。
总结
TurboQuant 的核心洞察极为简洁：随机旋转消除最坏情况输入，将向量量化问题归约为已知分布上的标量量化。这一设计同时满足了三个通常互相矛盾的目标：
- 近最优失真率：MSE 和内积失真均在信息论下界的常数倍以内，位宽效率以 指数衰减。
- 在线 / Data-oblivious：无需校准数据、无需预训练码本，对 KV cache 等动态生成的向量可以即时应用。
- 加速器友好：核心操作仅有矩阵乘法（旋转）和逐元素查表（量化），天然支持 GPU 向量化。
与 PolarQuant 等同期工作相比，TurboQuant 的独特优势在于同时优化了 MSE 和内积两个失真度量，并通过两阶段设计（MSE 量化 + 残差 QJL）巧妙地解决了 MSE 量化器的内积偏差问题。其理论贡献——信息论下界的严格证明——也为未来量化算法的设计提供了明确的性能基准。