向量数据库，堪称支撑推荐系统、图像识别及大模型检索增强生成（RAG）等 AI 应用的核心基石。然而，当业务数据规模从百万级跃升至百亿甚至千亿时，如何在海量数据下平衡检索性能、召回精度与硬件成本，直接决定了 AI 应用的商业价值与可行性。 传统的 HNSW 索引虽性能优越但内存成本高昂，限制了其在超大规模场景的应用；而 IVF 系列索引在降低成本时，又常以牺牲性能和召回率为代价。​RabitQ 的出现，正是为了解决这一业界难题。本文将深入剖析 RabitQ 算法从单 bit 到多 bit 版本的演进脉络与数学理论，并结合腾讯云 NoSQL 团队向量数据库（VDB）的工程实践，揭示其在并发读写、内存管理等方面的优化方案，为读者完整展示下一代向量索引技术如何兼得性能、成本与召回率。

本文作者：腾讯云 NoSQL 团队-何华均、霄文韬、章俊 &PCG 大数据部- 周建国、 白嗣东

*因公式显示原因，部分内容显示采用图片形式，如需更好的阅读体验欢迎联系作者取得原文 markdown 文件。

RabitQ 之前向量索引面临的现实问题

自从 2017 年 Faiss 库和 HNSWlib 开源后，向量索引近些年经过演进后，主要以 HNSW 图搜、IVF 聚簇索引两大方向为主要演进路线。在 RabitQ 算法出来之前，在索引面临实际业务场景落地的时候，始终会面临一些客观问题：

HNSW 图搜-性能好但成本高

HNSW 索引以 Search 性能佳的特点在很多业务场景中作为向量索引盲选目标，但随着数据规模的增加，HNSW 图搜默认放在机器中有限的内存资源上运行，所以硬件成本会随着数据规模的增加而线性增加。

例如在 100 万 1024d 的向量，在不量化的前提下数据本身会占用 4GB 内存空间，而 HNSW 的边也会占用内存空间，所以实际会占用 5-6GB，这个成本并不昂贵，但当数据规模达到 100 亿其内存资源将是现在的 1 万倍，值得注意的是这些资源并非用于计算，而是用于存储数据。而相对来讲，传统数据库的 100 亿数据属于家常便饭，成本相对来讲要低数百倍。

HNSW 量化在一定程度上可节约成本，通常可以使用 FP16、BF16、int8 三种方式，其中 FP16、BF16 的方式在 Tencent VDB 上已工程落地：《技术之向量数据库篇:腾讯云向量数据库如何实现召回不变，成本减半?》，int8 量化虽然可以进一步降低内存使用，但我们在多组数据集验证后，其召回率会有明显下降，因此 VDB 暂时未考虑基于 int8 量化进行工程落地。

即使不考虑召回率，通过 int8 量化后的图索引，也只会减少 4 倍的空间，对于 10 亿、100 亿乃至更大数据规模时，资源的成本依然是一个非常头痛的问题，我们需要更大的量化比，同时又希望召回率达到很高的标准。

IVF-SQ/PQ 量化-数倍降低成本但性能差且召回不可控

IVF-SQ/PQ 的量化等级可以做到更高，例如 IVF-PQ 的量化可以达到无限大，另外 IVF 索引在内存中并没有存放边，其额外内存较少且可控。同时 IVF 索引相对于 FLAT 暴搜，会提前将范围缩小到 nprobe 个聚簇中，这样相对于 FLAT 来讲性能通常有 10 倍以上的提升，所以在 RabitQ 正式推出前，其作为诸多业务选择百亿级规模向量存储方案之一，但是 IVF 同样会面临 2 大问题：

性能差： 相对于 HNSW 图搜索引的新能要低 1 个数量级（虽然相对 FLAT 会更好）。

召回率不可控： SQ 和 PQ 的量化方式，无法从数学上证明其精度损失的范围，更多需要基于数据特征做特定的选择和细节优化来提升召回率。

关于 HNSW 和 IVF 系列的索引问题不局限于上述提到的点（例如 IVF 的预训练和聚簇倾斜问题），但由于本文主要聚焦召回/成本/性能，在此不再继续展开。

RabitQ 改变现状格局

随着 AI 应用的爆发，业界对向量数据库的应用场景、规模上提出越来越高的要求，各向量服务厂商、开源组织一直通过各种方式在召回、性能、成本上下功夫，一直很难找到完美的解法，例如：DiskANN 是一种磁盘方案来降低成本，但其性能表现欠佳。大家一直期待有一种相对完美的索引来解决这样的问题，RabitQ 的诞生让我们对这块找到了希望。

很感谢南洋理工大学提供了一种 RabitQ 算法，其在性能（时间）、空间（成本）、召回上把向量索引带入一个新的理论阶段。在整个向量领域，作者第一个通过数学理论证明了经过 RabitQ 量化后的索引，其召回误差可以控制在一个公式内“距离无偏估计器”（与原始数据的特点关系不大），而经过实际的工程实践也符合作者推导的数学公式，RabitQ 最高可以做到 32 倍的量化，同时其性能也超越 HNSW。那么接下来就 RabitQ 理论和实践细节将展开介绍。

RabitQ 的数学理论

Rabit 在 2024 年作者推出了单 bit 版本，其量化等级固定 32 倍，虽然可通过“距离无偏估计器”进行误差估算，但单 bit 的量化依然会有明显的召回率下降，所以需要通过原始数据二次精排来提升召回，但这就导致了其性能的下降。而在今年（2025 年）作者推出了多 bit 版本，可以通过调整 bit 数来提升召回，实践证明通常 5-7bit 的量化就可以达到 99 的召回率，同时作者对查询性能上进行了大量的优化。

目前外部同行所推出的 RabitQ 版本是基于单 bit 版本，我们会先介绍单 bit 理论基础。TencentVDB 很有幸第一个在多 bit 版本上进行工程落地和实践，并已正式在 V2.7 版正式对外服务，所以我们会进一步介绍多 bit 的理论，以及在 TencentVDB 上的工程实践。

1-bit RaBitQ

公式衍变

以欧式距离为基础，RaBitQ 衍生出了仅依赖内积计算的理论。首先归一化原始向量$o_r$和原始查询向量$q_r$，即$o=\frac{o_r-c}{||o_r-c||}$,$q=\frac{q_r-c}{||q_r-c||}$，其中$c$为簇心向量. $D$维向量的欧式距离公式计算衍生如下（三角函数

）：

其中，$||(o_r-c)||$表示簇中原始向量到簇心的距离，可通过预计算提前保存下来；$||(q_r-c)||$为查询向量到簇心的距离，仅需计算一次。因此，公式中仅内积$⟨q,o⟩$不可提前计算。

码表构建

误差分析

RaBitQ 的无偏差估计是其核心贡献之一。通过理论分析，内积$⟨o,q⟩$可近似表示为，如下形式：

因此$\mathbb{E}(\frac{⟨\overline{o},q⟩}{⟨\overline{o},o⟩})=⟨o,q⟩$。进而，通过下面的公式来评估误差:

其中，${ϵ}_0$是可变参数，控制误差范围；$c_0$是常数项。因此，在置信度为$1-2e^{-c_0{ϵ}_0^2}$时，区间为

误差有很大的概率在$\frac{1}{\sqrt{D}}$附近。该理论推导涉及较多的数学证明，感兴趣的同学可以查看论文原文。

内积计算

回到$\frac{⟨\overline{o},q⟩}{⟨\overline{o},o⟩}$的计算上。其中$⟨\overline{o},o⟩$可预计算。因此，仅需要计算归一化后的查询向量$q$与量化向量$\overline{o}$的内积$⟨\overline{o},q⟩$即可。

其中，$q^{\prime }=P^{-1}q$.

• 查询向量$q^{\prime }$的量化过程：

• 计算量化向量内积: 将内积计算转${\overline{x}}_b$和${\overline{q}}_u$的内积

• 1. 单向量计算方案： 基于二进制“与”运算（bitwise-AND）和 popcount（数 1）运算。此方案适用于单个数据向量的距离估计，核心思想是将整数内积分解为二进制位操作，利用现代 CPU 的位指令（如 AND 和 popcount）实现高效计算。

• 硬件加速与优势：

指令支持：现代 CPU（如 x86）提供单周期位操作（AND）和 popcount 指令，延迟极低。

效率：仅需进行$Bq$次二进操作和在 D-bit 上做 popcount 操作，位操作效率远高于整数乘加。

2. 批量计算方案-基于 SIMD 和 LUTs 的 FastScan：其设计灵感来自 PQ 的 FastScan 实现，通过子段分割、查找表（LUTs）和 SIMD 指令实现高吞吐量。

两种方案共同支撑了 RaBitQ 在 ANN 搜索中的高效性，平衡了灵活性与吞吐量。实际系统中，可根据查询模式动态选择方案（如 IVF 索引中，批量处理候选向量）。此设计体现了 RaBitQ 在理论严谨性（无偏估计）与工程优化（硬件加速）间的平衡。

多 bits 版 RaBitQ

回顾 1-bitRaBitQ，其通过正交旋转矩阵$P$，将归一化后的数据向量$o$，映射到码表空间$C_r$中：

然而，其量化得到的量化码${\overline{x}}_b$的值仅为 0 或 1，导致最终得到的误差仍然较大。因此，作者 2025 年提出了 Extending RaBitQ，即多比特版 RaBitQ。主要的扩展在于提供了更精细的码本空间（B 比特）。

码表构建

• 码本空间：$$\mathcal{G}:={-\frac{2^B-1}{2}+u|u=0,1,2,...,2^B-1}^D.$$$${\mathcal{G}}_r:=P\frac{y}{||y||}|y\in \mathcal{G}.$$如下图所示，左图为集合$\mathcal{G}$，右图中红色实心点为归一化后的向量$y/||y||$。

• 
  

  

实验

1-bit 版 Rabit 实验

在 1-bit 版 RaBitQ 实验中，作者对比了普通 PQ，4bitPQ（ScaNN），优化版本的 PQ（OPQ/LSQ），以及 HNSW。实验结果表明，1-bit 版 RaBitQ 在精度和召回上均远好于 IVF-PQ，并且提供了更极致的压缩比例。

多 bit 版 Rabit 实验

在多 bits 版 RaBitQ 的实验中，可直观地看到 bit 设置的越大，RaBitQ 能获得的最大召回率越高，同时 QPS 会有所下降，但仍然比 LVQ 性能高。

实验结论

• 10 倍+性能： 在同等召回率下，其性能大约是 HNSW 的 1.5 倍，是 IVF-PQ 的 15-20 倍。

• 1/10 成本： 满足同等召回率下，其成本只有 HNSW 的 1/10 左右

• 召回随着维度和 bit 数增加而增加： 作者提出的“距离无偏估计器”公式上与之对应，实验也证明同等 bit 数下随着维度增加召回率会随之上升。

TencentVDB 在 RabitQ 工程落地

作者开源了 RabitQ-lib 库，其代码已接近工程实践水准，并进行了 AVX-512 的指令集优化。

不过在与 VDB 的框架结合过程中，依然避免不了诸多改造。框架与接口本身的适配，以及部分 bug 修复这里不一一说明，本文主要聚焦于内存存储结构和指令集的改造，主要包括以下几点：

● 开源版 RabitQ 不具备流式写入（增、删、改）能力，VDB 需要提供这样的能力，才可以满足最终用户对数据的 CRUD 操作。

● 开源版 RabitQ 在聚簇内部实现时，直接采用一大块连续内存存储向量数据，这种实现针对静态数据是高效的，但如果数据是持续写入和更新的，则不够高效：如果采取预分配策略，则前期可能导致大量内存空间浪费；预分配空间写满后，后续新增导致扩容时，会导致数据拷贝和内存临时翻倍的问题，影响在线读写延迟。

● 开源多 bit 版 RabitQ 默认不支持 avx-2 指令集，导致在相对低端的机型上无法运行。

内存体系结构 Segment 化

内存布局 &运行访问

TencentVDB 基于 IVF-RabitQ 代码，对其内存管理部分进行了重构，将聚簇内的内存存储结构从整块连续内存，优化为多 Segment 的分段连续存储的方式。

● 无大内存分配：此时一个聚簇内部不在是一块大的数组，而是有 1-N 个 Segment 组成，每个 Segment 的内存 size 是可控的，且按照 cache line 对齐，避免 False Sharing。因此后续新增数据时，只需要追加新的 Segment 数据块，从而避免数据拷贝。在代码层面 VDB 使用 SegmentCluster 来实现每个聚簇数据的存储：

多 Segment 快速寻址：经过多 Segment 调整后，通过统一的外部业务 id 到内部 id 映射，可快速定位到对应的聚簇 Cluster、Segment、Segment 内的 offset 偏移量。

● 读写加锁范围：Segment 化后，当数据要进行读写并发操作时，会针对局部 Segment 进行加锁（分段锁），例如聚簇内有 100 个 Segment，此时读写并发过程中“锁冲突概率”降低到：1/100，可以有效地提升系统的吞吐能力。

插入数据到 Segment

● 首先，计算出距离新数据距离最近的聚簇，该聚簇即为新数据插入的目标聚簇。

● 接着，尝试追加新数据到该聚簇的最后一个 Segment 的空闲区域，确保整体数据的紧密排布，从而充分利用空间。

● 如果 Segment 不存在空闲区域，则会创建新的 Segment 写入数据，这使得后续一段时间内持续写入“无需频繁分配”内存。

从 Segment 上删除和修改数据

● 尝试将 Segment 的尾部数据填充到删除数据的位置，确保删除后数据依然密集分布。通常的数组元素删除操作，需要将“数组元素大量向前移动的方式”来完成删除空间的填充，其时间复杂度是 O(n)，而改进后的方式时间复杂度是 O(1）

● 跨 Segment 移动的处理 2 种方式：

  ○ 方案 1：始终只保持最后 1 个 Segment 尾部存在空闲空间，其余的 Segment 删除数据时，都从最后一个 Segment 的尾部数据移动填补，所有插入数据也从最后一个 Segment 尾部追加。该方式简单直接，无需维护 Free-list 和空间碎片整理，如果最后一个 Segment 无数据时，可以整块内存直接释放，不会破坏整体结构。不过删除和修改数据时会出现跨 Segment 加锁，以及并发写入时，锁冲突概率相对较高。

  ○ 方案 2：每个 Segment 删除数据时，从当前删除数据所在 Segment 上移动其尾部数据到被删除的位置，确保 Segment 空间前缀部分是紧凑的，该方式在追加数据时，锁冲突会更小，删除阶段不会出现跨 Segment 加锁。但该方法需要维护 Free-list，期间内存空间会出现碎片，如果集中整理空间碎片可能会导致业务出现抖动。

● 当发生修改时，VDB 是通过先删除、再插入的方式进行封装，也就是复用上述删除和新增的两个步骤来完成。

AVX2 指令集适配改造

RabitQ 算法相比其他量化算法，存储空间小的一大关键在于量化后的向量各个元素通过高位打包，低位拼接的形式存储量化后的向量；召回率高的另一关键在于量化向量解压缩后，配合预先计算好的误差参数得到相对无损的距离；计算速度快在于硬件加速，引入更多向量寄存器的 avx2/avx512 指令集的 SIMD 计算架构比较适合当前的任务。

需要硬件加速的地方主要是涉及到到量化码的压缩/解压缩部分、以及部分计算结果累加的代码。

量化向量解压缩

压缩和解压缩是适配的。压缩阶段将量化后的向量的高位元素打包进一个为一个最近整型，低位不断拼接到多个 8 位整型数组中。最终合并到一起。期间大部分为移位操作，且性能约束低，直接使用 SSE 指令比较通用；解压缩阶段 avx 指令贯穿其中。解压缩阶段目的是将向量恢复压缩前的状态，此时主要涉及到查询场景，性能要求更高。

我们以以 3bit 版本的压缩和解压缩为例, 了解压缩原理并为其适配解压的代码，剩余的其他 1~8bit 的解压缩程序虽然都不一样，但原理近似。

● 压缩 3bit：以长度为 64 的向量，3bit 压缩，向量元素取值为 unit8：0~2^3-1 = 0~7。我们以下述向量为例

● 解压 3bit：以 avx 512 为例，解压缩时主要是将低位和高位还原，其还原原理图示如下。对于 avx2 而言，即是将一次性处理 512bit 转换为分两次各处理 256 bit 即可。

● 3bit 示例 code：

其基本逻辑遵循解包的流程，主要包括以下几步：

● 从内存中一次性加载此前被压缩的 64 个向量元素的：低位的 128 位数据到 128 个 XMM 寄存器（占 16byte）、以及高 64 位到一个 64bit 的整型中（占 8byte）

● 解出 64 个向量元素压缩前的低 2 位：利用整数左移函数，分批将 128 位共计 64 个向量元素拆解为 4 组，每组 16 个向量元素，与低位 mask 按位 &                         

● 解包 64 个向量元素压缩前的高 1 位：移位解，2 个 64 位整型组合成一个 128 位向量，与高位 mask 求与，得到 64 个元素的高 1 位

● 合并高低位，加载解包向量到 256 个 YMM 寄存器，执行内积计算

avx2/avx512 性能对比

使用 ann-benchmark 评测，avx2 性能微弱于 avx512，整体强于 Faiss 标准库；以 SIFT-1M 数据集为例，在 topk=10、100 下，avx2/avx512 优于 Faiss，且索引文件 size 大幅降低 4 倍于 Faiss IVF

机器环境：

● CPU: AMD EPYC 9754 128-Core Processor

● 内存：64GB

向量索引的进一步探索

RabitQ 是一种量化方式，目前 VDB 已提供多 bit 版 IVF-RabitQ，后续还会进一步提供 HNSW-RabitQ 索引服务，其综合 HNSW 的图搜与 RabitQ 的空间量化和计算代价低的优势。

RabitQ 的思路将向量索引算法带入一个新的阶段，不过向量索引本身还依然存在其它的工程问题是 RabitQ 也无法解决的。例如: IVF 索引的聚簇倾斜问题依然会发生，RabitQ 通过算法虽可以极大减少 input query 向量与聚簇内每个向量的计算代价，但其并不能解决 input query 命中数据倾斜的聚簇时，其匹配的向量数量会突然变多，我们需要通过其它的手段来处理以下几个重点：

● 发现聚簇倾斜（可观测）

● 不断优化“采样算法”让数据尽可能不倾斜，简单的思路是让倾斜的聚簇按照比例采集更多的样本，调整步长让采集的数据可分布在更大的写入时间序中

● 有效减少扫描行数，即使命中倾斜的聚簇，也依然可以保证稳定的性能和高召回

● 控制相对稳定的扫描行数，随着聚簇内数据规模增加，不会导致检索性能线性增加

VDB 团队也在上述方向上持续探索算法有一段时间，并已在理论和实验上取得一定的突破，将在此基础上构建自研索引（IVF-ABQ），其核心理论基础是基于三角函数中的距离和夹角来划分 Blocking 的思路。

目前 VDB 已在 1million~1billion 多组数据集下（开源/业务）实验验证结论，通过 IVF-ABQ 算法在几乎不降低召回的前提下，可减少 10 倍以上的“扫描行数”以降低整体向量计算次数，简单归纳：

● IVF-ABQ：减少扫描行数，相对稳定的扫描行数

● IVF-RabitQ：相同扫描行数下，降低计算代价

可见 IVF-ABQ、IVF-RabitQ 分别解决不同的问题，两者可以有效结合，发挥出更大的价值，这是我们 VDB 团队接下来落地自动弹性索引的坚实基础。

参考文献：

[1] Gao, J., & Long, C. (2024). Rabitq: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 2(3), 1-27.

[2] Gao, J., Gou, Y., Xu, Y., Yang, Y., Long, C., & Wong, R. C. W. (2025). Practical and asymptotically optimal quantization of high-dimensional vectors in euclidean space for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 3(3), 1-26.