# TurboQuant 数学原理解析

> TurboQuant 数学原理推导：QJL 符号随机投影的无偏估计与方差界限、PolarQuant 递归极坐标量化如何免掉归一化开销，拆解「极坐标压缩 + 1-bit 残差修正」两阶段框架，说明 TurboQuant 为何能在 3-bit 下达到 FP32 精度并实现 6 倍 KV Cache 内存压缩。

Canonical: https://doraemeng.dev/notes/turboquant-math-principles/


TurboQuant 最抓人的数字是「3-bit 达到 32-bit FP 的精度」和「6 倍 KV Cache 压缩」。这两个数字容易被读成同一个结论，实际是两笔账：前者说的是注意力分数的误差，后者说的是存储占用。要判断它能不能用在生产推理里，得把比特拆开看：3d 的总预算里，哪些位给了主压缩，哪些位给了残差，为什么残差只留 1 bit 还能把内积的偏差拉回来。

这套方法由两个部件拼起来：PolarQuant 负责把向量的大部分坐标压成角度，QJL 负责用 1-bit 符号随机投影修正剩下的内积误差。下面的推导按「JL 的距离保持性—QJL 的无偏估计—PolarQuant 的递归极坐标—两阶段如何接进 attention」这条线展开，最后再算 3d 和 6x 之间的差额。

## QJL：从距离保持到内积估计

Johnson-Lindenstrauss 引理给了一个很反直觉的承诺：高维点集可以映射到低维，点间距离基本不变。对任意数据集 $X \subset \mathbb{R}^d$，存在映射 $f: \mathbb{R}^d \to \mathbb{R}^k$，其中 $k = O(\varepsilon^{-2} \log |X|)$，使得对所有 $u, v \in X$：

$$\|f(u) - f(v)\|^2 \approx \|u - v\|^2$$

这就是距离保持性。$k$ 只和点的数量、误差 $\varepsilon$ 有关，和原始维度 $d$ 没有线性关系；点集越大，需要的维度才会缓慢上升。标准 JL 的实现是乘一个随机高斯矩阵 $A$，再把投影后的浮点数存下来；QJL 把最后一步改成取符号，只保留 1 bit：

```python
# 标准 JL：随机投影 + 保存浮点数
projected = sign(A · x)  # A 是随机高斯矩阵

# QJL：只保存符号位（1-bit）
qjl_output = sign(A · x) ∈ {-1, +1}^k
```

`sign(A · x)` 这一行丢掉了投影的幅度，只留下方向；这是压缩的全部来源，也是误差的来源。单个符号只告诉你在某个随机方向上 $q$ 和 $k$ 是否同向，信息很少；但把 $m$ 个随机方向的符号乘起来，再用校准常数缩放后平均，内积的期望会回到真实值。原始内积是 $\langle q, k \rangle$，QJL 用

$$\tilde{s} = \frac{1}{m} \sum_{i=1}^{m} \text{sign}(A_i q) \cdot \text{sign}(A_i k) \cdot c_i$$

去估计它，其中 $c_i$ 是校准常数，用于消除量化偏差。这个估计器的价值在于它的误差会随 $m$ 增大而下降，而不是固定在一个不可控的偏差上；代价是每个方向都要一次投影，$m$ 越大，压缩率越差，计算也越多。

## PolarQuant：把坐标配对成半径和角度

PolarQuant 处理的是量化里的老问题：分组量化通常要为每个块存 min/max 或 scale/zero-point，块越小，这些常数占的比特越多。它的做法是把笛卡尔坐标两两配对，转成极坐标。对向量 $x \in \mathbb{R}^d$，每一对 $(x_{2i-1}, x_{2i})$ 变成 $(r_i, \theta_i)$，其中 $r_i = \sqrt{x_{2i-1}^2 + x_{2i}^2}$ 是半径，$\theta_i = \arctan2(x_{2i}, x_{2i-1})$ 是角度。转换只做一次还不够，PolarQuant 会把半径继续配对，形成层级结构：第一层得到 $(r_1, \theta_1)$、$(r_2, \theta_2)$、$(r_3, \theta_3)$、$(r_4, \theta_4)$；第二层把 $r_1$ 和 $r_2$、$r_3$ 和 $r_4$ 再转成 $(R_{12}, \phi_{12})$、$(R_{34}, \phi_{34})$；第三层把 $R_{12}$ 和 $R_{34}$ 转成 $(R_{1234}, \phi_{1234})$，最终只剩一个总半径和 $d-1$ 个角度。半径用更高的位数量化，角度用更低的位数量化，存储结构是「1 个总半径 + $d-1$ 个角度」。

这套结构消掉的是归一化开销。传统分组量化要存每个块的 min/max，边界随数据动态变化，还要额外花 1-2 位存这些常数；极坐标的角度天然落在 $[0, 2\pi)$，边界固定，可以用一个固定的「圆形网格」去量化，不需要为每个块单独存边界。为什么可以先做随机旋转？因为旋转让数据各向同性（isotropic），坐标对的能量分布更均匀，角度不会全挤在少数几个方向；如果不旋转，一个只在少数维度上有值的向量，角度会高度集中，固定网格的码字就浪费了。

代价在计算侧：每次压缩都要算平方、开方和 $\arctan2$，解压时还要把极坐标转回笛卡尔坐标。存储省下来的比特，换成了编解码的浮点运算；对 KV Cache 这种写一次、读多次的数据，这笔交易通常划算，但如果你的 kernel 本来就在为每个 token 做 dequant，额外的三角函数会成为新的瓶颈。

## 两阶段：主项 + 1-bit 残差

两阶段里的第一阶段是随机旋转加 PolarQuant。先旋转，再量化：

$$\mathbf{v} \xrightarrow{\text{Random Rotation } R} \mathbf{v}' \xrightarrow{\text{PolarQuant}} (\mathbf{r}, \boldsymbol{\theta})$$

随机旋转让数据各向同性，PolarQuant 把半径和角度分开量化：半径用高位，角度用低位。重建出 $\hat{\mathbf{v}}$ 之后，残差是 $\mathbf{\delta} = \mathbf{v} - \hat{\mathbf{v}}$。第二阶段用 QJL 把这个残差压成 1 bit：

$$\mathbf{\delta}_{\text{qjl}} = \text{sign}(A \cdot \mathbf{\delta})$$

接进 attention 时，分数被拆成两项。主项和修正项分别对应下面公式里的两项：

$$\text{Attention}(Q, K) = \underbrace{Q \cdot \hat{K}_{\text{polar}}}_{\text{主要项}} + \underbrace{\text{QJL\_Estimator}(Q, \delta_K)}_{\text{偏差修正}}$$

第一项用 PolarQuant 重建的 $K$ 算内积，第二项用 QJL 估计残差带来的偏差。这个拆法的关键在注意力只关心内积，不关心 $K$ 的逐元素重建质量；只要内积的期望无偏、方差可控，$K$ 本身可以压得很狠。QJL 的 1 bit 用来修正主项的系统性偏差，不需要恢复 $K$ 的细节，所以它不需要很多位。

理论保证落在两行上。期望上，量化后的分数等于真实分数：

$$E[\tilde{s}] = \langle q, k \rangle$$

方差也有上界。下面这个不等式给出它随 $m$ 收缩的方式：

$$\text{Var}(\tilde{s}) \leq \frac{C}{m} \|q\|^2 \|k\|^2$$

其中 $m$ 为 QJL 维度，增加 $m$ 可以任意减小误差。前者说明估计没有固定偏差，后者说明误差的上界按 $1/m$ 收缩。真正影响线上效果的是 $C$ 这个常数；原文没有展开它和 $m$、数据维度之间的关系，[待补：$C$ 的推导或实测范围、$m$ 与误差的实测曲线]。

## 账本：3d 和 6x 之间差在哪

把每向量的比特数摊开：FP32 是 $32d$，INT8 是 $8d$，KIVI 是 $4d$ 加分组量化的开销，TurboQuant 是 $3d$，内容为极坐标加 1-bit 残差。$32/3$ 约为 10.7，这是纯载荷的理论上限；材料给出的实际 KV Cache 收益是 6 倍。两个数字不矛盾，差额来自块对齐、元数据、残差索引这些实现开销，也来自实际 kernel 对非均匀位宽的支持程度。原文没有拆这 4.7 倍的账，[待补：6x 的测量口径、块大小与元数据开销拆分、TurboQuant 原始论文或技术报告的链接]。

从 $32d$ 到 $3d$，压缩比看起来最刺激；但对推理系统，真正决定吞吐的是内存带宽和省下来的字节能不能被 kernel 直接消费。如果 attention kernel 需要先把 3-bit 数据解压成 FP16 再算，省下的是 HBM 占用，付出的是反量化和额外的寄存器/共享内存流量；在 decode 阶段，KV Cache 读取本来就是带宽瓶颈，这种交换可能划算；在 prefill 阶段，计算更密集，解压开销未必能被带宽节省抵消。原文的「计算更快（低 bit 运算）」成立的前提是底层有对应的低 bit matmul 路径；没有这条路径，省的是显存，算的还是 FP16。

这套方案不需要训练，量化过程是数据无关的；好处是换模型不用重训量化器，代价是它不能像学习式量化那样针对数据分布做优化。数据无关也意味着它对异常值、长尾分布的鲁棒性只能靠随机旋转和残差修正兜底，不能靠训练时见过的分布去适配；原文没有给出异常值场景的评测，[待补：长尾/异常值下的精度退化数据]。

## 一个十进制例子

传统量化像把 3.1415926 存成「3.14 + 缩放因子 100」：数值本身只占几个字符，缩放因子还要额外空间。PolarQuant 像把 (3, 4) 存成「长度 5 + 角度 53°」：角度范围固定在 [0°, 360°)，解码时不需要再问「这个块的边界是多少」。QJL 则像把误差 0.0015926 存成一串符号「+ - + - ...」：只有 1 位，但 JL 变换保证这些符号的期望能把误差的方向估回来。三个例子各自的代价也很清楚：缩放因子是额外存储，角度是三角函数计算，符号是多次投影；TurboQuant 把这三笔代价压到同一个 3d 预算里。

TurboQuant 给出的 3-bit 和 6x 回答的是两个不同问题：3d 回答「内积还能不能估准」，6x 回答「KV Cache 能省多少」。要把这两个数字变成线上的吞吐，还缺三样东西：6x 的测量口径、C 和 m 的实测曲线、以及低 bit kernel 在目标硬件上的反量化成本。三样里缺任何一样，3-bit 都只是一个存储方案，未必是一个更快的推理方案。

