大白话RaBitQ压缩算法

本篇播客

RaBitQ 向量压缩算法简介

本文深入浅出地介绍 RaBitQ（Random Binary Quantization with Theoretical Error Bound）向量压缩算法，包括其核心思想、压缩后的距离计算流程、量化偏差，以及为什么它通常不需要归一化。

🚀 RaBitQ 向量压缩算法简介

RaBitQ 是一种用于高维向量（如嵌入向量）压缩的算法，其主要目标是实现高压缩率的同时，保证近似最近邻搜索 (ANN) 的准确性和理论可控的误差。它属于二值量化（Binary Quantization, BQ）的范畴。

核心思想

1. 随机投影 (Random Projection) 与二值化：

• RaBitQ 首先对原始高维向量  执行一系列随机线性投影 ，将向量投影到一个较低维度的空间  。
• 接着，通过一个二值化函数（ 通常是符号函数  ），将投影后的结果转换为二进制码 或  。
• 其中，  是一个随机矩阵，其元素通常从标准正态分布中采样。

• 传统二值量化方法的缺点在于缺乏理论上的误差保证，可能导致在某些数据集上搜索精度急剧下降。
• RaBitQ 的创新点在于它利用了随机投影的性质（如 Johnson-Lindenstrauss 引理的变体）和特定的无偏距离估计器，来保证量化后的距离估计与原始距离之间的理论误差界限。这意味着算法能更好地控制量化带来的精度损失。

• 为了在压缩的二进制码上可靠地估计原始向量间的距离，RaBitQ 引入了一个无偏估计器。这个估计器可以有效地利用二值码中的信息来近似原始空间中的距离（通常是内积或欧氏距离），并最大限度地减少重构误差。

📏 压缩后向量距离计算流程

在 RaBitQ 中，向量  被压缩成一个二进制码 。对于查询向量  和数据库中的一个向量  ，我们不再计算它们原始的距离  ，而是计算它们二进制码之间的近似距离 。

1. 计算二值码之间的距离

由于是二值码，距离计算可以被极大地加速，通常使用汉明距离 (Hamming Distance) 或基于汉明距离的内积估计。

假设二进制码  ：

• 汉明距离 ：是两个码中不同位的数量。

• 这可以通过高效的位运算（如 XOR 操作后计算设置位 (popcount)）来完成，速度极快。

• 内积估计 ：

  RaBitQ 主要关注通过二值码来估计原始向量的内积（内积与角度和欧氏距离都有关）。

  首先计算两个二值码的点积（或相关性）：

  这个相关性与汉明距离有直接关系：  。

2. 使用无偏估计器估计原始距离

RaBitQ 使用这个二值码相关性来估计原始向量的内积 ，这通常涉及到一种非线性变换 （例如  或其他更复杂的函数）来校正二值化带来的偏差：

• 
  

  
• 其中，  是二值码的平均相关性。
• 这个估计器  是无偏的，即它的期望值等于原始的内积（或距离度量），且其方差（即估计的波动性）有理论界限。

通过这种方式，RaBitQ 在牺牲少量精度的前提下，实现了原始距离在高压缩率下的快速、可控误差的近似计算。

📉 量化后与量化前计算结果的偏差

偏差（或量化误差）是量化后的近似距离  与原始距离  之间的差异：  。

1. 系统误差 (Systematic Error) 或偏差 (Bias):

• 二值量化本身是一个非线性、有损的过程，通常会引入系统性的偏差。
• RaBitQ 的关键优势在于，它所使用的距离估计器 是一个无偏估计器。
• 无偏性意味着： 
• 即，在多次随机投影和量化的平均意义上，估计值是准确的。对于单一的量化结果，系统偏差被有效消除。

• 这个界限表明，随着码长  的增加（压缩率降低），估计的误差  会指数级下降。

• 虽然偏差被消除，但每次量化得到的估计值  仍然会围绕真实值  波动。这种波动就是随机误差或方差。
• RaBitQ 提供了对这种随机误差的理论界限：
• 这个理论保证了误差是可控的，并且通过选择合适的码长  ，可以保证搜索的召回率 (Recall) 达到预期的水平。

❓ 为什么不需要归一化？

在许多向量搜索场景中，归一化 (Normalization)（即将向量长度调整为 1）是非常常见且重要的一步。然而，在 RaBitQ 的特定设计下，它可以不需要对原始向量进行显式的长度归一化，原因如下：

1. 距离度量和内积的关系

• 内积 (  )：与向量的长度和它们之间的夹角都有关。
• 余弦相似度 ( cos_sim )：只与夹角有关，计算时需要归一化：
  

2. RaBitQ 的处理方式（处理长度信息）

RaBitQ 的无偏估计器设计可以同时估计原始向量的内积 ，以及向量的长度（或它们长度的乘积）。

• 长度分离： RaBitQ 通常将向量的长度信息（  ） 单独存储，而不对其进行二值量化。
• 距离重构： 在计算相似度时，可以利用量化得到的内积估计 和单独存储的长度信息，来重构出任何基于内积的度量：
• 余弦相似度估计： 
  

总结： RaBitQ 采用的是一种混合策略——对方向信息（内积或夹角信息）进行高效的二值量化，而对长度信息进行精确（非量化）或低损耗的存储。这避免了在量化前强制归一化带来的信息丢失，同时保留了计算余弦相似度的能力。

可不可以这么理解: RaBitQ既存储原始向量, 也存储量化后的bit, 计算相似度时主要依赖bit, 极少用到原始向量

这是一个很好的问题，并且您的理解方向基本正确，但需要更精确地界定 RaBitQ 在“存储”和“使用”上的策略。

🎯 对 RaBitQ 存储和使用策略的精确定位

您的理解可以概括为： "RaBitQ 是一种牺牲存储少量额外信息来保证高精度的高级量化方法。"

📚 总结您的理解和精确策略

您的核心理解是：计算相似度主要依赖压缩数据（bit） ，这是完全正确的，也是 RaBitQ 实现加速 和 压缩的核心。

最精确的理解应该是：

RaBitQ 存储的是原始高维向量的“压缩表示”：即一个高压缩率的 二进制码 （用于方向/角度信息）和一个 低维度的长度标量 （用于长度信息）。相似度计算 完全基于 这些存储的压缩表示（二进制码 + 长度标量），不需要 完整的原始高维向量。