RaBitQ 量化深度解析：VexDB-Lite 如何用码字遍历图索引实现极限内存压缩

RaBitQ 量化深度解析：VexDB-Lite 如何用码字遍历图索引实现极限内存压缩

【免费下载链接】VexDB-LiteA cross-platform vector database, which can be integrated into existing databases as a plugin.项目地址: https://gitcode.com/gh_mirrors/ve/VexDB-Lite

VexDB-Lite 是一款跨平台向量数据库，可嵌入 PostgreSQL、DuckDB、SQLite 作为插件。它的 RaBitQ 量化器能把每条向量压缩成不到 1KB 的「码字」，让 HNSW 图索引在百万级向量下依然驻留内存，配合memory_mode='compact'实现极限内存压缩，同时保留 L2、cosine、内积三种距离度量。

1. 为什么图索引需要「极限内存压缩」

以图像检索为例：用户丢进来一艘海面上的红船作为查询条件——

数据库需要在候选图库里找出最相似的一张，比如这幅田野场景——

问题在于：HNSW 这类图索引搜索时几乎每次比较都要读一条向量。以 768 维 float32 向量计，100 万条就要3GB常驻内存。向量一多，图索引就从「内存索引」退化成「磁盘索引」，查询延迟陡增。

RaBitQ 的思路很直接：图里不再存原始向量，只存量化码字；搜索比较全部基于码字完成。码字足够小，整个图就能装进内存。

2. RaBitQ 码字长什么样：把 3072 字节压成 896 字节

码字的内存布局定义在 code_distancer.h 中，一条 768 维向量的 RaBitQ 码字由 4 部分组成：

尺寸公式见 utils.h：RABITQ_BIN_CODE_SIZE（每 64 维压成 1 个 64 位字）和RABITQ_EXT_CODE_SIZE（每维 8 bit），外加 3 个 float 校准系数。

2.1 先旋转，再量化

量化前的第一步是把向量乘上一个随机正交矩阵，实现见 rotator.h 的FhtKacRotator。它用 Fast Hadamard Transform（快速哈达玛变换）+ 随机符号翻转 + Kac walk 近似任意正交旋转，复杂度接近 O(d log d) 而非 O(d²)。

旋转的目的是打散向量能量的分布，让各维度幅度尽量均匀——这样「每维只存 1 bit / 8 bit」的粗粒度量化才不会在个别维度上误差爆炸。

2.2 两步编码：1-bit 符号 + 8-bit 幅值

编码主流程在 rabitq.cpp 的quantize()中：

1. 向量旋转后，就近分配到 16 个聚类质心之一（compute_closest_cluster，聚类数见HNSW_RABITQ_NUM_CLUSTERS）；
2. 残差 = 旋转向量 − 质心。残差每维的正负号就是 1-bit 二值码（one_bit_code），打包成 64 位字存储；
3. 残差每维的幅值再做 8-bit 标量量化得到扩展码（ex_bits_code），负数维的码字取反码，把符号位「藏」进码值里。

所以整条向量 =质心（16 选 1，共享）+ 二值码（方向）+ 扩展码（幅值），这就是「码字」的全部内容。

2.3 三个校准系数：让估算距离「无偏」

纯 1-bit 量化会系统性地歪曲距离。RaBitQ 的巧妙之处在于编码时为每条码字额外存 3 个 float 系数：f_add（加项）、f_rescale（缩放项）、f_error（误差界），见 rabitq.cpp 中quantize_bin_code的末尾。

查询时距离不再是「算出来的」，而是「套公式估出来的」：

est_dist = f_add + g_add + f_rescale × (ip + k1xsumq) low_dist = est_dist − f_error × g_error

其中ip是查询二值化码与存储二值码的位积（SIMD 加速），g_add/g_error是查询到质心的距离。low_dist是理论下界：真实距离一定 ≥ low_dist。这个下界正是图搜索里「何时可以剪枝」的数学依据。

3. 码字如何驱动图遍历：code-aware 搜索

这是标题里「码字遍历图索引」的核心。整条链路在 estimator.cpp：

• 查询预处理只做一次（preprocess）：旋转查询向量、二值化查询码、预计算查询到 16 个质心的距离表q_to_centroids——之后每次节点比较都省掉这些开销；
• 两级比较：
  • get_bin_dist：只用 1-bit 码，一次 64 位 POPCNT 级别的位运算就能估算距离 + 下界，用于图搜索的候选粗排与剪枝；
  • get_full_dist：加上 8-bit 扩展码的浮点内积，得到接近原向量精度的距离，用于候选集精排。
• 无需 refine：CodeDistancer中need_refine = false（code_distancer.h）。普通 PQ 索引搜完还要回表取原始向量重排，RaBitQ 的 8-bit 码精度已经足够，省掉一次随机读。

另一条关键能力是码字重构：reconstruct()（rabitq.cpp）可以从码字反推出「质心 + 残差」的近似向量，用于图维护时的邻居选择，因此 compact 模式下原始向量在索引侧完全不需要保留。

整个索引侧的持久化由宿主适配，例如 PostgreSQL 侧在 vexdb_pg/src/rabitq_distancer.cpp 中训练量化器并把码字块写入索引文件。

4. 极限内存压缩怎么落地：memory_mode='compact'

在 features.md 的 RaBitQ 一节可以查到用法，一行 SQL 开启：

CREATE INDEX idx_rabitq ON items USING vexdb (vec) WITH (metric = 'cosine', quantizer = 'rabitq', memory_mode = 'compact', m = 16, ef_construction = 160);

compact模式下，磁盘布局为：量化码字与图结构写入索引（kind 5/6），不写原始向量镜像（kind 4）；用户数据仍完整保存在%_vectors表中。

按 768 维、100 万条向量算笔账：

图节点开销之外，仅向量数据就省下约70% 内存；向量维度越高、数据量越大，收益越夸张。查询、增量插入、重启恢复全部基于码字完成，无需回表重排。

正确性有回归测试兜底，可参考 graph_index_rabitq.yaml：它覆盖空索引、memory_mode='compact'落盘校验（rabitq_codes_bytes > 0）、以及 L2 / cosine / inner product 三种度量下的建索引与查询，还验证了quantizer='rabitq'与pq_m互斥的参数约束。

5. 选型速览：什么时候该上 RaBitQ

一句话总结：VexDB-Lite 的 RaBitQ 量化 = FHT 随机旋转 + 16 聚类残差 + 1-bit/8-bit 两级码字 + 三系数无偏估算，配合码字下界剪枝和码字重构，让 HNSW 图索引在保留搜索精度的同时，把内存占用压到原来的三成左右——这正是「图索引 + 量化」在内存受限场景下的极限形态。

【免费下载链接】VexDB-LiteA cross-platform vector database, which can be integrated into existing databases as a plugin.项目地址: https://gitcode.com/gh_mirrors/ve/VexDB-Lite