← 返回归档

TurboQuant: 近最优失真率的在线向量量化

一、论文摘要

向量量化是源于香农信源编码理论的一个经典问题，其目标是在量化高维欧几里得向量时最小化其几何结构的失真。本文提出 TurboQuant 方法，同时解决均方误差（MSE）和内积失真问题，克服了现有方法无法达到最优失真率的局限性。

TurboQuant 的数据无关算法适用于在线应用场景，在所有位宽和维度下都能达到近最优失真率（仅相差一个小常数因子）。其核心思想是：首先对输入向量进行随机旋转，使各坐标服从集中的 Beta 分布，然后利用高维空间中不同坐标的近独立性特性，对每个坐标独立应用最优标量量化器。

针对 MSE 最优量化器在内积估计中引入偏差的问题，本文提出两阶段方案：先应用 MSE 量化器，再对残差应用 1-bit 量化 Johnson-Lindenstrauss (QJL) 变换，从而获得无偏内积量化器。

本文还给出了信息论下界的严格证明，证明 TurboQuant 与最优下界仅相差约 2.7 倍的常数因子。实验验证了理论结论：在 KV 缓存量化中，3.5 位/通道可实现绝对质量无损，2.5 位仅有轻微质量下降；在最近邻搜索任务中，该方法在召回率上优于现有产品量化技术，同时将索引时间降至接近零。

二、基本信息

**论文 ID**: 2504.19874
**标题**: TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
**作者**: Amir Zandieh, Majid Daliri, Majid Hadian, Vahab Mirrokni
**单位**: 
  - Amir Zandieh: Google Research
  - Majid Daliri: New York University
  - Majid Hadian: Google DeepMind
  - Vahab Mirrokni: Google Research
**会议/期刊**: arXiv preprint
**原文保存位置**: ~/.openclaw/workspace/papers/20260330_TurboQuant/source/
**报告生成日期**: 2026-03-30

三、论文主体分析

1. 引言

向量量化（VQ）在欧几里得空间中的应用对于高效处理高维向量至关重要，涵盖从训练和部署大规模 AI 和深度学习模型到为搜索/检索系统提供向量数据库支持的广泛计算领域。核心目标是通过量化——将浮点坐标值转换为低位宽整数——来压缩高维向量，同时最小化由均方误差（MSE）或内积误差等指标量化的失真。通过保持这些属性，可以以最小延迟和减少的计算与通信资源快速响应内积查询。

这一问题的根源追溯到香农关于信源编码理论的开创性工作，该工作确立了块信源编码（现称为向量量化器）可达到的最小失真由香农失真率函数定义，取决于信源的统计特性和所选的失真度量（如 MSE）。今天，VQ 在 AI、深度学习和搜索系统等基础计算领域中扮演着关键角色。

1.1 问题定义

形式化地，目标是设计一个量化映射 $Q: \mathbb{R}^d \to \{ 0, 1 \}^B$，将 $d$ 维向量转换为 $B$ 位的二进制串。如果设 $B = b \cdot d$（其中 $b \ge 0$），则该量化器的位宽为 $b$，表示编码 $\mathbb{R}^d$ 的每个实值坐标所使用的平均位数。

关键是需要一个逆映射 $Q^{-1}: \{ 0, 1 \}^B \to \mathbb{R}^d$ 执行反量化，近似从量化表示重建原始向量。由于 $Q$ 不是双射，这种转换本质上是损失性的。因此，主要目标是最小化失真，特别关注均方误差（MSE）和内积失真。

不对输入向量数据集做任何假设，考虑最坏情况。允许量化器 $Q(\cdot)$ 是随机的，产生随机输出。对于随机量化器，更合适的是定义量化器输出随机性上的期望失真。目标是设计对于任意位宽 $b$ 和任意（最坏情况）向量 $\x, \y \in \mathbb{R}^d$ 最小化以下期望失真度量的量化器：

$$ \textbf{(MSE)}~~~~~ D_{\tt mse} := \E_{Q}\left[\left\| \x - Q^{-1}\left( Q(\x) \right) \right\|_2^2 \right] $$ $$ \textbf{(inner-prod error)}~~~~~ D_{\tt prod} := \E_{Q}\left[\left| \langle \y, \x \rangle - \langle \y, Q^{-1}\left( Q(\x) \right) \rangle \right|^2 \right] $$

上述期望关于量化器 $Q(\cdot)$ 的随机性取值。此外，对于内积量化器，要求内积估计器的无偏性，这是许多应用所期望的性质：

$$ \textbf{(unbiased inner-prod)}~~~~~ \E_{Q}\left[ \langle \y, Q^{-1}\left( Q(\x) \right) \rangle\right] = \langle \y, \x \rangle $$

1.2 相关工作

VQ 的起源：向量量化理论始于香农关于可达到失真率函数的开创性工作。1963 年，Zador 使用高分辨率方法推导了固定速率量化在高速率下的极限操作失真率函数，与香农失真率函数紧密匹配。Gersho 的论文进一步推进了向量量化，普及了高分辨率理论，简化了 Zador 的结果，引入格向量量化，并提出一个塑造该领域的关键猜想。

在线与离线量化：在线（数据无关）量化方法可即时应用，无需数据特定调整或校准。相反，离线（数据依赖）方法需要大量预处理和学习来适应量化映射到数据，不适合动态数据场景。例如，一些方法使用二阶（Hessian）信息调整量化映射，需要大量预处理甚至后处理。

在线 KV 缓存压缩：已提出多种压缩 KV 缓存的方法，包括架构修改（重组 transformer 以减少存储的键值对数量）和修剪/驱逐冗余或不太关键的 token。一种简单而有效的方法是量化 KV 缓存，已开发多种专门用于此目的的量化技术。最近，QJL 引入了一种高效的、数据无关的 1 位量化方法，基于 sketching 技术，为内积查询提供无偏估计。

产品量化（PQ）：在欧几里得数据集的最近邻（NN）搜索问题中，索引大小构成显著的内存瓶颈，通常通过量化技术（在 NN 文献中常称为产品量化 PQ）来缓解。许多算法依赖在索引阶段使用 k-means 变体构建量化码本，因此由于需要大量预处理而不适合在线场景。

1.3 技术与贡献概述

MSE 优化的 TurboQuant：第一个 VQ 算法设计用于最小化 MSE 失真。通过对输入向量应用随机旋转，使每个坐标服从 Beta 分布，与输入向量本身无关。在高维 $d$ 中，每个坐标的分布由于测度集中和中心极限定理收敛到高斯分布 $\mathcal{N}(1, 1/d)$。此外，任意两个不同坐标变得几乎不相关，更重要的是几乎独立（超越单纯相关性的深层结果）。这种近独立性是简化量化设计的关键方面，允许对每个坐标使用最优标量量化而忽略不同坐标间的相互作用或相关性。

通过求解连续 1 维 k-means 问题使用 Max-Lloyd 算法，为具有 Beta 分布的随机变量找到最优标量量化器。预先计算并存储这些最优码本以用于一系列实用位宽，使后续 TurboQuant 调用高效。

定理（TurboQuant_mse 性能保证）：对于任意位宽 $b \ge 1$ 和任意向量 $\x \in \mathbb{S}^{d-1}$，$b$ 位 MSE 优化 TurboQuant $Q_{\tt mse}: \mathbb{R}^d \to \{ 0, 1 \}^{b \cdot d}$ 达到以下失真界限：

  • $D_{\tt mse}(Q_{\tt mse}) := \E\left[\left\| \x - Q_{\tt mse}^{-1}\left( Q_{\tt mse}(\x) \right) \right\|_2^2 \right] \le \frac{\sqrt{3} \pi}{2} \cdot \frac{1}{4^{b}}$，对于任意 $b \ge 0$
  • 对于小位宽，具体地 $b = 1, 2, 3, 4$，有 $D_{\tt mse}(Q_{\tt mse}) \approx \mathbf{0.36}, \mathbf{0.117}, \mathbf{0.03}, \mathbf{0.009}$

内积 TurboQuant：证明 MSE 优化量化器在内积估计中是有偏的，因此需要不同的 VQ 方案来获得无偏内积量化器。解决方案是两阶段算法：首先应用上述 $Q_{\tt mse}$（位宽比目标预算少一位），然后对残差误差应用 QJL。这被证明是无偏的，并且具有近最优的内积误差率。

定理（TurboQuant_prod 性能保证）：对于任意位宽 $b \ge 1$ 和任意向量 $\x \in \mathbb{S}^{d-1}$，$b$ 位内积优化 TurboQuant 达到：

  • $\E\left[ \left< \y, Q_{\tt prod}^{-1}\left( Q_{\tt prod}(\x) \right) \right> \right] = \langle \y, \x \rangle$（无偏）
  • $D_{\tt prod}(Q_{\tt prod}) \le \frac{\sqrt{3} \pi^2 \cdot \norm{\y}_2^2}{d} \cdot \frac{1}{4^{b}}$，对于任意 $b \ge 0$
  • 对于 $b = 1, 2, 3, 4$，有 $D_{\tt prod}(Q_{\tt prod}) \approx \frac{\mathbf{1.57}}{d}, \frac{\mathbf{0.56}}{d}, \frac{\mathbf{0.18}}{d}, \frac{\mathbf{0.047}}{d}$

下界：利用 Shannon 下界和 Yao 极小极大原理证明，对于任意随机量化算法 $Q: \mathbb{R}^d \to \{ 0, 1 \}^{b \cdot d}$：

    $D_{\tt mse}(Q) \ge \frac{1}{4^{b}}$ $D_{\tt prod}(Q) \ge \frac{\norm{\y}_2^2}{d} \cdot \frac{1}{4^{b}}$

TurboQuant 的 MSE 失真与信息论下界的因子至多为 $\frac{\sqrt{3} \pi}{2} \approx \mathbf{2.7}$。对于较小位宽，该因子显著减小。例如，在 $b=1$ 时，TurboQuant 达到的失真仅比最优差约 $\mathbf{1.45}$ 倍。

2. 预备知识

使用粗体小写字母如 $\x$ 和 $\y$ 表示向量，粗体大写字母如 $\M$ 表示矩阵。使用 $\mathbb{S}^{d-1}$ 表示 $\mathbb{R}^d$ 中半径为 1 的超球面。对于随机变量 $x$，其微分熵记为 $h(x)$。随机变量 $x$ 和 $y$ 之间的互信息记为 $I(x; y) = h(x) - h(x|y)$。

由于 TurboQuant 使用随机旋转来缓解最坏情况输入场景，理解超球面上随机点的统计性质至关重要。

引理（超球面上随机点的坐标分布）：对于任意正整数 $d$，如果 $\x \in \mathbb{S}^{d-1}$ 是均匀分布在单位超球面上的随机变量，则对于任意 $j \in [d]$，坐标 $\x_j$ 服从以下（缩放/平移）Beta 分布：

$$ \x_j \sim f_{X}(x) := \frac{\Gamma(d/2)}{\sqrt{\pi} \cdot \Gamma((d-1)/2)} \left( 1 - x^2 \right)^{(d-3)/2} $$

在高维中，该 Beta 分布收敛到正态分布 $f_{X}(\cdot) \to \mathcal{N}(0, 1/d)$。

2.1 Shannon 失真下界

Shannon 下界（SLB）是源于 Shannon 有损信源编码定理的强大工具，为任意有损压缩方案的最优可达到失真率提供通用下界。

引理（SLB）：设 $\x \in \mathbb{R}^d$ 为具有任意概率分布 $p_X$ 和有限微分熵 $h(\x)$ 的随机向量。定义总位复杂度 $B \ge 0$ 的 MSE 失真率函数 $D(B)$ 为：

$$ D(p_X, B) := \inf \left\{ \E \left[ \norm{\x - \y}_2^2 \right] : I(\x; \y) \le B \right\} $$

其中下确界在 $\x$ 和重建随机向量 $\y \in \mathbb{R}^d$ 的所有联合分布上取值，使得互信息 $I(\x; \y)$ 至多为 $B$。则对于任意位复杂度 $B \ge 0$：

$$ D(p_X, B) \ge \frac{d}{2 \pi e} \cdot 2^{(2/d) (h(\x) - B)} $$

引理（超球面上随机点的 SLB）：设 $\x \in \mathbb{S}^{d-1}$ 为均匀分布在单位超球面上的随机变量。则对于任意位复杂度 $B \ge 0$：

$$ D(B) \ge 2^{-2B/d} $$

2.2 QJL：1 位内积量化

设计两个 VQ 算法：一个优化用于最小化 MSE，另一个优化用于最小化内积误差。证明 MSE 优化量化器不一定提供无偏内积估计，特别是在较低位宽时表现出显著偏差。内积量化的解决方案是两阶段算法：首先使用比目标位宽少一位的 MSE 优化量化器，最小化残差的 L2 范数；然后对残差应用无偏最优单一位量化器。对于单一位内积量化器，使用最近提出的量化 Johnson-Lindenstrauss (QJL) 算法。

定义（QJL）：对于任意正整数 $d$，QJL 映射 $Q_{\tt qjl}: \mathbb{R}^d \to \{ -1, +1 \}^d$ 定义为：

$$ Q_{\tt qjl}(\x) := {\tt sign} \left( \S \cdot \x \right) ~~~~\text{ 对于任意 } \x \in \mathbb{R}^d $$

其中 $\S \in \mathbb{R}^{d \times d}$ 是具有从正态分布 $\mathcal{N}(0, 1)$ 独立采样条目的随机矩阵，${\tt sign}$ 函数逐元素应用于其向量输入。反量化映射 $Q_{\tt qjl}^{-1}: \{ -1, +1\}^d \to \mathbb{R}^d$ 定义为：

$$ Q_{\tt qjl}^{-1}(\z) := \frac{\sqrt{\pi/2}}{d} \cdot \S^\top \cdot \z ~~~~\text{ 对于任意 } \z \in \{ -1, +1\}^d $$

引理（QJL 性能保证）：设 $Q_{\tt qjl}$ 和 $Q_{\tt qjl}^{-1}$ 如上述定义。对于任意向量 $\x \in \mathbb{S}^{d-1}$ 和任意 $\y \in \mathbb{R}^d$：

  • 无偏：$\E\left[ \left< \y, Q_{\tt qjl}^{-1}\left( Q_{\tt qjl}(\x) \right) \right> \right] = \langle \y, \x \rangle$
  • 方差界：$\mathtt{Var} \left( \left< \y, Q_{\tt qjl}^{-1}\left( Q_{\tt qjl}(\x) \right) \right> \right) \le \frac{\pi}{2 d} \cdot \norm{\y}_2^2$

3. TurboQuant：高性能量化

开发了两个 VQ 算法，每个针对特定目标定制。第一个算法设计用于最小化量化后原始向量与重建向量之间的 MSE。第二个算法优化用于无偏内积估计，解决 MSE 优化量化器固有的偏差问题。

3.1 MSE 最优 TurboQuant

设 $\x \in \mathbb{S}^{d-1}$ 为维度 $d$ 中单位球面上的（最坏情况）向量。目标是将 $\x$ 量化为每坐标 $b$ 位，同时最小化重建 MSE。

首先通过乘以随机旋转矩阵 $\BPi \in \mathbb{R}^{d \times d}$ 来随机化该向量。可通过在具有独立同分布正态条目的随机矩阵上应用 QR 分解来生成 $\BPi$。

结果旋转向量 $\BPi \cdot \x$ 均匀分布在单位球面 $\mathbb{S}^{d-1}$ 上。如引理所示，$\BPi \cdot \x$ 的每个坐标服从 Beta 分布，在高维中收敛到正态分布。此外，在高维中，$\BPi \cdot \x$ 的不同坐标变得几乎独立，允许对每个坐标独立应用最优标量量化器。

因此，任务简化为为具有分布 $f_{X}(x) = \frac{\Gamma(d/2)}{\sqrt{\pi} \cdot \Gamma((d-1)/2)} \left( 1 - x^2 \right)^{(d-3)/2}$（$x \in [-1, 1]$）的随机变量设计标量量化器。

最优标量量化问题（给定已知概率分布）可表述为维度 1 的连续 k-means 问题。具体地，目标是将区间 $[-1, 1]$ 划分为 $2^b$ 个簇/桶。最优解遵循 Voronoi 镶嵌，意味着区间边界是排序后连续中心点之间的中点。

因此，用 $c_i$ 表示升序排列的中心点，可将标量量化表述为以下 k-means 优化问题：

$$ \mathcal{C}(f_X, b) := \min_{-1 \le c_1 \le c_2 \le \ldots \le c_{2^b} \le 1} \sum_{i=1}^{2^b} \int_{\frac{c_{i-1} + c_i}{2}}^{\frac{c_i + c_{i+1}}{2}} |x - c_i|^2 \cdot f_X(x)~dx $$

$\mathcal{C}(f_X, b)$ 表示位宽 $b$ 的最优 MSE 成本函数。该问题可使用迭代数值方法以任意所需精度求解。为一系列实用相关位宽 $b$ 求解一次，存储结果供量化器后续使用。

例如，在中等高维 $d$ 中，分布 $f_X(x)$ 紧密近似正态分布时，位宽 $b = 1, 2$ 的最优量化中心点为 $\left\{ \pm \frac{\sqrt{2/\pi}}{\sqrt{d}} \right\}$ 和 $\left\{ \pm \frac{0.453}{\sqrt{d}}, \pm \frac{1.51}{\sqrt{d}} \right\}$。

量化器 $Q_{\tt mse}: \mathbb{R}^d \to \{ 0, 1 \}^{b \cdot d}$ 首先计算 $\BPi \cdot \x$，然后计算并存储该向量每个坐标最近中心点的索引。反量化映射 $Q_{\tt mse}^{-1}$ 通过检索对应存储索引的中心点重建向量，然后通过乘以 $\BPi^\top$ 将结果旋转回原始基。

图：MSE 失真与理论界限在不同位宽下的比较

图：MSE 失真与理论界限在不同位宽下的比较

:::

3.2 内积最优 TurboQuant

对于最近邻搜索等应用，拥有无偏内积估计器至关重要。然而，MSE 优化的 TurboQuant 不提供与查询向量的无偏内积估计。

为说明此点，考虑位宽 $b=1$ 的情况。此时，对于足够大的 $d$，求解优化问题的最优码本为 $\left\{ \pm \sqrt{\frac{2}{\pi d}} \right\}$。这意味着 TurboQuant_mse 的量化映射为 $Q_{\tt mse}(\x) = {\tt sign} \left( \BPi \cdot \x \right)$，反量化映射为 $Q_{\tt mse}^{-1}(\z) = \sqrt{\frac{2}{\pi d}} \cdot \BPi^\top \cdot \z$。因此，对于足够大的 $d$，$\E\left[ \left< \y, Q_{\tt mse}^{-1}\left( Q_{\tt mse}(\x) \right) \right> \right] = \frac{2}{\pi} \cdot \langle \y, \x \rangle$，具有 $2/\pi$ 的乘法偏差。该偏差随位宽 $b$ 增加而减小。

为解决此偏差，提出结合 TurboQuant_mse 与 QJL 实例的解决方案。具体地，设 $Q_{\tt mse}$ 为位宽 $b-1$ 的 TurboQuant_mse 对应量化映射。对于任意 $\x \in \mathbb{S}^{d-1}$，残差向量定义为 $\r := \x - Q_{\tt mse}^{-1}\left( Q_{\tt mse}(\x) \right)$，具有小的 L2 范数，期望上 $\E[\norm{\r}] = \sqrt{\mathcal{C}(f_X, b-1)}$。

然后可对该残差向量应用 QJL 量化映射 $Q_{\tt qjl}$，结果总位宽为 $b$，提供以下无偏内积估计器：

$$ \left< \y, Q_{\tt mse}^{-1}\left( Q_{\tt mse}(\x) \right) \right> + \norm{\r}_2 \cdot \left< \y, Q_{\tt qjl}^{-1}\left( Q_{\tt qjl}(\r) \right) \right> $$

更形式化地，量化映射 $Q_{\tt prod}: \mathbb{S}^{d-1} \to [2^{b-1}]^d \times \{ -1, 1 \}^d \times \mathbb{R}$ 定义为：

$$ Q_{\tt prod}(\x) = \left[ Q_{\tt mse}(\x), Q_{\tt qjl}\left( \x - Q_{\tt mse}^{-1}\left( Q_{\tt mse}(\x) \right) \right), \norm{\x - Q_{\tt mse}^{-1}\left( Q_{\tt mse}(\x) \right)}_2 \right] $$

图：TurboQuant_prod 内积估计误差分布

图：TurboQuant_prod 内积估计误差分布

:::

图：TurboQuant_mse 内积估计误差分布（存在偏差）

图：TurboQuant_mse 内积估计误差分布（存在偏差）

:::

图：TurboQuant_prod 2 位量化时内积误差方差保持恒定

图：TurboQuant_prod 2 位量化时内积误差方差保持恒定

:::

图：TurboQuant_mse 2 位量化时内积误差方差随平均内积增加而增加

图：TurboQuant_mse 2 位量化时内积误差方差随平均内积增加而增加

:::

3.3 下界

证明 TurboQuant 在任意位宽下达到最优失真率（相差一个小常数因子），通过证明任意压缩算法的最佳可达到失真的下界。

下界证明利用 Yao 极小极大原理。该原理允许将最坏情况确定性输入向量的随机算法下界与随机输入向量的确定性算法下界联系起来。随后，使用 Shannon 下界推导后者的可达到失真率下界。

定理（最佳可达到压缩失真的下界）：对于任意位宽 $b$ 的随机量化算法 $Q: \mathbb{S}^{d-1} \to \{ 0, 1 \}^{b \cdot d}$ 和任意重建映射 $Q^{-1}: \{ 0, 1 \}^{b \cdot d} \to \mathbb{R}^d$，存在困难输入实例 $\x \in \mathbb{S}^{d-1}$ 使得：

$$ D_{\tt mse}(Q) := \E\left[\left\| \x - Q^{-1}\left( Q(\x) \right) \right\|_2^2 \right] \ge \frac{1}{4^{b}} $$

此外，存在 $\y \in \mathbb{S}^{d-1}$ 使得：

$$ D_{\tt prod}(Q) = \E\left[\left| \langle \y, \x \rangle - \langle \y, Q^{-1}\left( Q(\x) \right) \rangle \right|^2 \right] \ge \frac{1}{d} \cdot \frac{1}{4^{b}} $$

图：内积误差与理论界限在不同位宽下的比较

图：内积误差与理论界限在不同位宽下的比较

:::

4. 实验

所有实验使用单个 NVIDIA A100 GPU 进行。实验部分分为两部分：一部分实证验证理论结果，另一部分评估方法在下游任务（KV 缓存量化和最近邻向量搜索）上的性能。

4.1 实证验证

使用 DBpedia Entities 数据集（已使用 OpenAI3 嵌入编码为 1536 维空间）验证理论结果。随机采样 100,000 个数据点作为训练集，提取 1,000 个不同条目作为查询集。

评估两种量化方法：$\TurboQuant_\text{\tt prod}$ 和 $\TurboQuant_\text{\tt mse}$。$\TurboQuant_\text{\tt mse}$ 设计用于优化量化向量与原始向量之间的 MSE。$\TurboQuant_\text{\tt prod}$ 对于估计量化向量与原始向量之间的内积是无偏的。

两种方法应用于内积估计任务，通过量化训练集并分析不同位宽下内积计算中的失真。如图所示，增加位宽减少两种方法的方差。然而，当用于内积估计时，$\TurboQuant_\text{\tt mse}$ 引入偏差，该偏差随位宽增加而减小并最终收敛到零。

实验结果确认 $\TurboQuant_\text{\tt prod}$ 在所有位宽下对内积估计保持无偏，而 $\TurboQuant_\text{\tt mse}$ 随位宽增加逐渐改善。

当量化到 2 位时，$\TurboQuant\text{\tt prod}$ 方法的方差保持恒定，无论原始向量的内积如何。然而，$\TurboQuant\text{\tt mse}$ 方法的偏差依赖于平均内积，随平均内积增加偏差也增加。

4.2 Needle-In-A-Haystack 测试

"Needle-In-A-Haystack" 测试是设计用于评估模型在长文档中检索特定信息能力的基准。测试涉及将一个唯一句子（"needle"）放置在更大文本（"haystack"）的任意位置，并评估模型是否能成功提取它。

使用 Llama-3.1-8B-Instruct 模型进行评估。为分析不同输入序列长度下的性能，将文档大小从 4k 到 104k token 变化。主要评估指标是召回分数，测量模型检索隐藏句子的准确性。

比较 PolarQuant、SnapKV、PyramidKV 和 KIVI 等最新高效内存方法。每种方法在内存压缩比 0.25 下测试，意味着仅使用完整 KV 缓存的 25%。

结果表明，具有理论保证的量化方法（如 PolarQuant 和 TurboQuant）优于缺乏正式理论保证的 token 级压缩技术（如 SnapKV 和 PyramidKV）以及标量量化方法（如 KIVI）。值得注意的是，TurboQuant 在 $4 \times$ 压缩下达到与全精度模型相同的性能，使其成为长上下文处理的稳健解决方案。

图：TurboQuant Needle-In-A-Haystack 测试结果（Score: 0.997）

图：TurboQuant Needle-In-A-Haystack 测试结果（Score: 0.997）

:::

图：全精度基线 Needle-In-A-Haystack 测试结果（Score: 0.997）

图：全精度基线 Needle-In-A-Haystack 测试结果（Score: 0.997）

:::

图：PolarQuant Needle-In-A-Haystack 测试结果（Score: 0.995）

图：PolarQuant Needle-In-A-Haystack 测试结果（Score: 0.995）

:::

图：KIVI Needle-In-A-Haystack 测试结果（Score: 0.981）

图：KIVI Needle-In-A-Haystack 测试结果（Score: 0.981）

:::

图：PyramidKV Needle-In-A-Haystack 测试结果（Score: 0.895）

图：PyramidKV Needle-In-A-Haystack 测试结果（Score: 0.895）

:::

图：SnapKV Needle-In-A-Haystack 测试结果（Score: 0.858）

图：SnapKV Needle-In-A-Haystack 测试结果（Score: 0.858）

:::

4.3 LongBench 端到端生成

在 LongBench 数据集上实验各种 KV 缓存压缩算法，涵盖广泛的长文本场景，包括单文档和多文档问答、摘要、少样本学习、合成任务和代码完成。为确保不同上下文长度下的平衡评估，使用 LongBench-E 子集。

使用 Llama-3.1-8B-Instruct 和 Ministral-7B-Instruct 比较 TurboQuant 与领先基线方法。与现有方法（如 KIVI 和 PolarQuant）不同，本文方法即使在流式生成过程中也应用量化。

如表所示，方法在 Llama 和 Ministral 上都优于其他方法，达到显著更高的平均分数。使用 2.5 位和 3.5 位量化评估方法。尽管使用比竞争技术更少的位，TurboQuant 保持与未量化模型相当的性能。同时将量化向量压缩至少 $4.5 \times$。

Method KV Size SingleQA MultiQA Summarization Few shot Synthetic Code Average
Full Cache 16 45.29 45.16 26.55 68.38 59.54 46.28 50.06
KIVI 3 43.38 37.99 27.16 68.38 59.50 44.68 48.50
KIVI 5 45.04 45.70 26.47 68.57 59.55 46.41 50.16
PolarQuant 3.9 45.18 44.48 26.23 68.25 60.07 45.24 49.78
TurboQuant (ours) 2.5 44.16 44.96 24.80 68.01 59.65 45.76 49.44
TurboQuant (ours) 3.5 45.01 45.31 26.00 68.63 59.95 46.17 50.06

4.4 最近邻搜索实验

使用 DBpedia Entities 数据集（使用 OpenAI3 嵌入编码为 1536 维和 3072 维空间）以及低维 GloVe 嵌入数据集评估最近邻搜索性能。随机采样 100,000 个数据点作为训练集，提取 1,000 个条目作为查询集。

比较 TurboQuant 与两种基线量化方法：产品量化（PQ）和 RabitQ。所有三种方法量化数据集训练集，基于 top-k 的召回比评估性能。

Approach d=200 d=1536 d=3072
Product Quantization 37.04 239.75 494.42
RabitQ 597.25 2267.59 3957.19
TurboQuant 0.0007 0.0013 0.0021

TurboQuant 在所有实验中的召回比上一致优于产品量化，同时将量化时间降至接近零。

图：GloVe 数据集（d=200）召回率比较

图：GloVe 数据集（d=200）召回率比较

:::

图：OpenAI3 数据集（d=1536）召回率比较

图：OpenAI3 数据集（d=1536）召回率比较

:::

图：OpenAI3 数据集（d=3072）召回率比较

图：OpenAI3 数据集（d=3072）召回率比较

:::

四、论文简评

创新点

  1. 近最优失真率：首次提出在所有位宽和维度下达到近最优失真率（仅相差约 2.7 倍常数因子）的在线向量量化方法，填补了理论保证与实践效率之间的空白。

  2. 两阶段设计：创新性地将 MSE 量化与 QJL 残差量化结合，巧妙解决了 MSE 最优量化器在内积估计中的偏差问题，实现了无偏且低失真的内积估计。

  3. 理论完备性：利用 Shannon 下界和 Yao 极小极大原理严格证明了信息论下界，为方法的最优性提供了坚实的理论基础。

  4. 实用性强：数据无关的特性使其完美适用于在线场景（如 KV 缓存量化），计算高效且易于向量化/加速器友好。

局限性

  1. 常数因子差距：虽然近最优，但与理论下界仍有约 2.7 倍差距，在极低失真要求场景下可能仍有改进空间。

  2. 单位向量假设：理论分析基于单位向量假设，实际应用需要额外存储 L2 范数并反量化时重缩放。

  3. 随机旋转开销：每次量化需要随机旋转矩阵乘法，在极高频次调用场景下可能有一定计算开销。

应用场景

  1. LLM KV 缓存压缩：长上下文模型的 KV 缓存内存瓶颈，3.5 位实现质量无损，2.5 位仅有轻微下降。

  2. 向量数据库/检索系统：最近邻搜索中的向量压缩与快速内积估计，召回率优于传统 PQ 方法。

  3. 模型部署量化：大规模模型权重和激活的在线量化，减少推理延迟和内存占用。

可改进方向

  1. 缩小常数因子：进一步优化标量量化器设计，尝试逼近信息论下界的 1 倍差距。

  2. 自适应位宽分配：根据向量各坐标的分布特性动态分配位宽，可能进一步提升效率。

  3. 硬件优化：针对特定加速器（GPU/TPU）优化随机旋转和量化操作的实现，进一步减少延迟。

  4. 扩展到其他失真度量：研究在其他失真度量（如最大误差、相对误差）下的最优量化设计。��计。��