TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate

向量量化是一个源于香农信源编码理论的问题，目标是以最小化几何结构失真的方式对高维欧几里得向量进行量化。我们提出了 TurboQuant 方法，旨在同时解决均方误差（MSE）和内积失真的问题，克服了现有方法无法达到最优失真率的局限性。我们的数据无关算法适用于在线应用，并在所有比特宽度和维度上实现了接近最优的失真率（仅相差一个小的常数因子）。TurboQuant 通过随机旋转输入向量，使坐标分布趋于集中化的 Beta 分布，并利用高维空间中不同坐标的近似独立性，为每个坐标简单地应用最优标量量化器来实现这一目标。鉴于 MSE 最优量化器会在内积估计中引入偏差，我们提出了一种两阶段方法：首先应用 MSE 量化器，然后对残差进行 1 比特量化 JL（QJL）变换，从而得到一个无偏的内积量化器。此外，我们还提供了任何向量量化器所能达到的最佳失真率的信息论下界的正式证明，展示了 TurboQuant 紧密逼近这些下界，仅相差一个小的常数因子（约 2.7）。实验结果验证了我们的理论发现，表明在 KV 缓存量化任务中，我们使用每通道 3.5 比特可以实现绝对的质量中立，而使用每通道 2.5 比特则只会带来轻微的质量下降。此外，在最近邻搜索任务中，我们的方法在召回率方面优于现有的乘积量化技术，同时将索引时间减少到几乎为零。

论文试图解决高维向量量化问题，特别是在最小化均方误差（MSE）和内积失真方面。这是一个经典问题，但现有方法在不同比特宽度和维度下难以达到最优失真率。

论文提出了一种名为TurboQuant的方法，通过随机旋转输入向量，将坐标分布转化为集中型Beta分布，并利用高维空间中坐标的近独立性，对每个坐标应用最优标量量化器。此外，为了减少内积估计的偏差，引入了两阶段方法：先用MSE最优量化器处理，再对残差应用1-bit Quantized JL (QJL)变换。这种方法在理论上接近信息论下界，仅相差一个小常数因子（约2.7）。

实验表明，TurboQuant在KV缓存量化任务中以3.5比特/通道实现了绝对质量中立，在2.5比特/通道时仅有轻微质量下降。在最近邻搜索任务中，该方法不仅提高了召回率，还将索引时间几乎降为零。论文还提供了理论证明，展示了TurboQuant与信息论下界的接近程度。代码是否开源未明确提及，但研究为未来优化高维量化提供了重要方向，例如探索更低比特宽度下的性能。

相关研究包括基于产品的量化方法（如PQ、OPQ）、基于学习的量化方法（如DSQ、LSH），以及专注于内积保持的量化技术（如Spherical Quantization）。一些近期工作如《Asymmetric Quantization for Efficient Nearest Neighbor Search》和《Optimized Product Quantization for Approximate Nearest Neighbor Search》也在探索高效的量化方案，但这些方法通常无法同时优化MSE和内积失真。