向量数据库的量化压缩：从Product Quantization到RaBitQ的二十年技术博弈

一台配备64GB内存的服务器，要索引十亿个768维的向量，需要多少存储空间？

答案是超过3TB。而标准的内存索引方案，比如HNSW，要求将所有数据加载到内存中才能保证查询延迟在毫秒级。这意味着，即使是企业级的服务器，也无法在单机上完成这项任务。云服务器的内存按GB计费，3TB内存的月成本可能高达数千美元——这才是向量数据库规模化部署面临的真正瓶颈。

量化压缩技术正是为解决这个问题而生。通过将32位浮点数压缩到更少的比特位，向量数据库能够以数十倍甚至百倍的效率提升存储密度，同时保持可接受的搜索精度。这不是一个简单的"压缩"问题，而是一个在精度、速度、内存三者之间寻找最优权衡的二十年技术博弈。

量化的本质：不是降维，是值域压缩

在深入技术细节之前，需要澄清一个常见的误解：量化不是降维。

降维是将128维向量映射到64维向量，减少的是维度$D$；而量化是将32位浮点数映射到8位整数，减少的是值域范围$S$。

$$\text{降维：} D \rightarrow D' \quad (D' < D)$$

$$\text{量化：} S \rightarrow S' \quad (|S'| < |S|)$$

这个区别至关重要。降维改变了向量的几何结构，而量化只是在更小的空间中表示同样的几何结构。量化的目标是找到一种映射方式，使得原始向量之间的相对距离关系尽可能保留。

从数学角度，量化器$Q$是一个将连续值空间映射到有限离散集合的函数：

$$Q: \mathbb{R}^D \rightarrow \{c_1, c_2, \ldots, c_K\}$$

其中$\{c_1, c_2, \ldots, c_K\}$称为码本或质心集合，$K$是码本大小。一个好的量化器应该最小化量化误差：

$$\text{Error} = \mathbb{E}[\|x - Q(x)\|^2]$$

这个看似简单的目标，在二十年间演化出了多种截然不同的技术路径。

标量量化：最朴素的起点

标量量化（Scalar Quantization，SQ）是最直观的量化方法：将每个维度的32位浮点数映射为更低位宽的整数。

原理与实现

假设一个维度的值范围是$[min, max]$，标量量化将其线性映射到$[0, 255]$（8位）或$[0, 1]$（1位）：

$$x_{quantized} = \text{round}\left(\frac{x - min}{max - min} \times 255\right)$$

解量化则是逆过程：

$$x_{reconstructed} = \frac{x_{quantized}}{255} \times (max - min) + min$$

8位标量量化（SQ8）将内存占用减少4倍，因为每个维度从4字节变为1字节。对于100万个768维向量，原始存储需要约2.9GB，SQ8压缩后仅需约730MB。

二进制量化：极致压缩的代价

二进制量化（Binary Quantization，BQ）将压缩推向极致：每个维度仅保留符号位。

$$x_{binary} = \begin{cases} 1 & \text{if } x > 0 \\ 0 & \text{if } x \leq 0 \end{cases}$$

这实现了32倍压缩——768维向量仅需要96字节。距离计算也从欧氏距离变为汉明距离，可以通过CPU的POPCNT指令硬件加速。

然而，极致压缩的代价是显著的召回率损失。二进制量化仅保留方向信息，完全丢弃了幅值信息。在标准测试集上，BQ的召回率通常在60%-85%之间，远低于SQ的95%-99%。

这引出了量化技术面临的核心挑战：压缩比与召回率之间的权衡。有没有一种方法，能在更高压缩比的同时保持更高的召回率？

Product Quantization：拆分与重构的艺术

2010年，Hervé Jégou等人在IEEE Transactions on Pattern Analysis and Machine Intelligence上发表了题为"Product Quantization for Nearest Neighbor Search"的论文，提出了一个精妙的解决方案。

核心思想：分而治之

Product Quantization（PQ）的核心洞察是：直接对高维向量进行量化需要指数级大小的码本，但如果将向量拆分成多个子向量，对每个子向量独立量化，则可以用有限的码本覆盖整个空间。

具体而言，一个$D$维向量$x$被拆分成$m$个子向量：

$$x = [u_1, u_2, \ldots, u_m]$$

每个子向量$u_j$的维度为$D^* = D/m$。对每个子向量空间，独立训练一个包含$k^*$个质心的码本$C_j$。通常选择$k^* = 256$（8位编码），这样每个子向量可以用一个字节表示。

整个码本的大小是$m \times k^* \times D^* = m \times 256 \times (D/m)$个浮点数，与向量数量无关。每个向量仅需$m$字节存储（每个子向量一个字节索引）。

压缩比计算

对于128维向量，选择$m=8$，每个子向量16维，码本大小$256 \times 16 \times 8 = 32768$个浮点数（约128KB）。

每个向量的存储：

原始：$128 \times 4 = 512$字节
PQ编码：$8$字节
压缩比：$64$倍

如果选择$m=16$，压缩比可达128倍。这就是PQ的魔力：通过子空间分解，实现了理论上的高压缩比。

非对称距离计算

PQ最具创新性的贡献是非对称距离计算（Asymmetric Distance Computation，ADC）。

在查询时，计算查询向量$q$与数据库向量$x$的距离，$x$已被量化为编码。朴素方法需要先解码$x$再计算距离，但ADC提供了更高效的方案。

由于$x$被编码为$[i_1, i_2, \ldots, i_m]$（每个$i_j$是子向量$u_j$对应的质心索引），距离可以分解为：

$$d(q, x)^2 \approx \sum_{j=1}^{m} d(q_j, c_{j,i_j})^2$$

其中$q_j$是查询向量的第$j$个子向量，$c_{j,i_j}$是第$j$个子空间的第$i_j$个质心。

关键洞察：可以预先计算查询向量每个子向量与对应子空间所有质心的距离表$T$：

$$T[j][i] = d(q_j, c_{j,i})^2$$

这个表的大小是$m \times 256$。之后，对于每个数据库向量，只需查表并求和：

$$d(q, x)^2 \approx \sum_{j=1}^{m} T[j][i_j]$$

这避免了访问码本和重构向量，大大加速了搜索过程。

PQ的性能表现

根据Pinecone的测试数据，在SIFT1M数据集上：

指标	Flat Index	IndexPQ	IndexIVFPQ
召回率@10	100%	50%	52%
查询延迟	8.26ms	1.49ms	0.09ms
内存占用	256MB	6.5MB	9.2MB

PQ实现了40倍内存压缩，但召回率下降到50%。这是量化的本质权衡：用精度换取存储效率。

Optimized Product Quantization：旋转的力量

PQ有一个隐含假设：向量各维度之间是独立的，可以任意拆分。但实际数据往往存在维度间的相关性，某些维度高度相关，某些则相对独立。

2013年，微软研究院的Tiezheng Ge等人提出了Optimized Product Quantization（OPQ），通过引入旋转变换来优化子空间的划分。

数学原理

OPQ的核心是在量化前对向量应用一个正交旋转矩阵$R$：

$$x' = Rx$$

然后对旋转后的向量$x'$应用标准的PQ量化。目标是找到一个最优的$R$，使得量化误差最小：

$$\min_R \sum_x \|x - R^T Q(Rx)\|^2$$

其中$Q(\cdot)$是PQ量化函数，$R^T$是逆旋转（因为$R$是正交矩阵，$R^{-1} = R^T$）。

参数化与非参数化方法

论文提出了两种求解$R$的方法：

非参数化方法：交替优化$R$和码本。先固定$R$优化码本，再固定码本优化$R$，迭代直到收敛。
参数化方法：假设数据服从高斯分布，$R$可以通过特征值分解得到。将数据协方差矩阵的特征向量按降序排列，然后"平衡"地分配给各个子空间。

参数化方法更高效，但对非高斯分布的数据可能效果不佳。

OPQ的优势

OPQ的核心优势是平衡各子空间的方差。如果某些子空间的方差很大，而另一些很小，PQ的整体性能会受限于高方差子空间。OPQ通过旋转使得各子空间的方差更加均匀。

根据原始论文的实验，OPQ相比标准PQ可以提升约5%-10%的召回率，尤其是在数据维度间存在强相关性的场景。

IVF-PQ：聚类与量化的组合拳

单独使用PQ进行暴力搜索仍然需要遍历所有向量。为了进一步加速，业界广泛采用Inverted File（IVF）与PQ的组合方案。

IVF索引原理

IVF首先对数据进行粗粒度聚类（通常使用$k$-means），将向量空间划分为$nlist$个Voronoi单元格。每个单元格维护一个倒排列表，存储属于该单元格的向量ID。

查询时，首先找到距离查询向量最近的$nprobe$个单元格，然后只在这些单元格内搜索。这大大减少了搜索范围。

IVF-PQ组合

IVF-PQ将两层量化串联：

粗量化器（Coarse Quantizer）：将向量分配到$nlist$个簇
细量化器（PQ）：对簇内向量进行PQ编码

存储时，每个向量保存：

所属簇的ID（用于定位倒排列表）
PQ编码（用于距离计算）

查询时：

计算查询向量与所有簇质心的距离，选择最近的$nprobe$个簇
对每个选中的簇，使用ADC计算查询向量与簇内PQ编码向量的距离
合并结果，返回top-k

nprobe的权衡

$nprobe$是IVF-PQ最关键的参数，直接影响召回率与查询速度的权衡。

$nprobe = 1$：只搜索最近的簇，速度最快但召回率最低
$nprobe = nlist$：搜索所有簇，等同于暴力搜索，召回率最高但速度最慢

实际应用中，通常选择$nprobe$使得覆盖5%-10%的数据。例如$nlist = 2048$时，$nprobe = 48$可以在保持较高召回率的同时大幅减少搜索范围。

根据NVIDIA的测试数据，IVF-PQ在GPU上可以实现每秒数万次查询，同时保持90%以上的召回率。

DiskANN：突破内存限制的磁盘索引

无论是HNSW还是IVF-PQ，都假设索引能够完全加载到内存。但对于十亿级向量，即使是PQ压缩后的数据也可能超出单机内存容量。

2019年，微软研究院在NeurIPS上发表了DiskANN，提出了一种基于SSD的磁盘索引方案，能够在单机64GB内存上索引十亿级向量。

Vamana图算法

DiskANN的核心是一个名为Vamana的图索引算法，与HNSW和NSG类似但有关键改进。

Vamana的建图过程：

初始化一个随机图
计算全局质心，找到距离质心最近的点作为起点（导航点）
对每个点执行近似最近邻搜索，将搜索路径上的点作为候选邻居
执行修剪策略：对每个邻居，如果存在另一个邻居与它距离更近，则删除该邻居
调整修剪参数$\alpha > 1$（推荐1.2），重新执行步骤3-4

$\alpha$参数是Vamana的创新：通过放大距离参考值，允许更多的长边存在，从而减小搜索半径。

磁盘存储架构

DiskANN的关键创新是将图结构和原始向量存储在SSD上，仅在内存中保留压缩后的向量。

存储布局：

扇区对齐：将向量和邻居列表组合成一个节点，按扇区（通常4KB）对齐存储
内存缓存：缓存距离起点C跳（推荐3-4）内的所有节点
PQ编码：内存中保存PQ编码用于粗粒度距离估计

查询优化：

Beam Search：预加载邻居信息。当访问节点$p$时，同时加载$W$个未访问邻居，利用SSD的并行读取能力
两阶段距离计算：先用内存中的PQ编码估计距离，筛选候选后再从磁盘读取原始向量计算精确距离

性能表现

DiskANN在SIFT-1B数据集上的测试结果：

硬件：64GB RAM + SSD
索引大小：384GB（存储在SSD）
查询延迟：<3ms
召回率@1：>95%
QPS：5000

这意味着，使用消费级硬件，单机即可支持十亿级向量检索。

Additive Quantization：超越PQ的精度

PQ假设各子向量独立编码，这是一种近似。2014年，Babenko和Lempitsky提出了Additive Quantization（AQ），用求和代替拼接来近似原始向量。

数学形式

AQ将向量近似为多个码字的和：

$$x \approx \sum_{m=1}^{M} c_m^{(i_m)}$$

其中$c_m^{(i_m)}$是第$m$个码本的第$i_m$个码字。注意这里所有码字的维度都是$D$，与PQ不同。

重构向量的过程是简单求和，而PQ是拼接。这意味着AQ可以使用更灵活的编码组合。

FAISS中的实现

FAISS库提供了两种加性量化器的实现：

残差量化器（Residual Quantizer）：顺序编码。第$m$步编码第$m-1$步的残差：
$$x \approx c_1^{(i_1)} + c_2^{(i_2)} + \ldots + c_M^{(i_M)}$$
这是贪心方法，可能陷入局部最优。为缓解此问题，使用beam search维护多个候选编码路径。
局部搜索量化器（Local Search Quantizer，LSQ）：从随机编码开始，通过模拟退火优化编码。

在相同比特数下，AQ（RQ和LSQ）通常比PQ有更低的重构误差，但编码时间更长。

与PQ的对比

特性	PQ	AQ
码本存储	$m \times k^* \times D/m$	$m \times k^* \times D$
编码复杂度	$O(mk^*)$	$O(mk^* \cdot \text{beam\_size})$
重构误差	较高	较低
适用场景	大规模检索	高精度要求

AQ的码本更大（因为每个码本都是全维度的），但在相同比特数下精度更高。对于精度敏感的场景，AQ是PQ的有力替代。

RaBitQ：理论保证的1比特量化

2024年，来自中国的研究团队提出了RaBitQ，首次为1比特量化提供了理论误差界限保证，并在实践中实现了高召回率。

高维空间的几何直觉

RaBitQ的灵感来自高维几何的一个反直觉性质：维度越高，数据分布越"规则"。

考虑从单位球面上均匀采样的随机向量。在3维空间中，第一个坐标值均匀分布在$[-1, 1]$；但在1000维空间中，第一个坐标值高度集中在0附近。

这意味着，高维向量的每个维度本身就携带有限信息，用1比特编码不会丢失太多信息。

算法原理

RaBitQ的核心步骤：

参考点归一化：选择一个参考点（如数据集质心）$c$，将每个数据向量$x$相对于$c$归一化：
$$\tilde{x} = \frac{x - c}{\|x - c\|}$$
超立方体投影：将归一化向量投影到最近的超立方体顶点：
$$b_i = \begin{cases} 1 & \text{if } \tilde{x}_i > 0 \\ 0 & \text{if } \tilde{x}_i \leq 0 \end{cases}$$
这实现了$D$维向量到$D$比特的压缩。
无偏距离估计：RaBitQ提出了一个理论上无偏的距离估计器：
$$\hat{d}(q, x) = f(\text{Hamming}(b_q, b_x), \|q\|, \|x\|)$$
其中$b_q$和$b_x$分别是查询向量和数据向量的二进制编码，$\text{Hamming}(\cdot)$是汉明距离。

理论误差界

RaBitQ的核心贡献是证明了距离估计误差有理论上界：

$$\mathbb{E}[|\hat{d}(q, x) - d(q, x)|] \leq O\left(\frac{1}{\sqrt{D}}\right)$$

这意味着，随着维度$D$增加，估计误差按$\frac{1}{\sqrt{D}}$速率下降。对于768维向量，理论上误差很小。

实际性能

Milvus 2.6集成了RaBitQ，在1M 768维向量上的测试结果：

配置	QPS	召回率@10
IVF_FLAT	236	95.2%
IVF_RABITQ	648	76.0%
IVF_RABITQ + SQ8 Refine	864	94.7%

RaBitQ单独使用时召回率约76%，但配合SQ8重排序后，召回率接近95%，同时QPS提升3倍以上。这验证了RaBitQ作为粗筛选器的有效性。

量化方法对比与选择指南

经过对各种量化技术的分析，可以总结出以下对比：

方法	压缩比	召回率影响	查询速度	训练复杂度
SQ8	4×	1-5%损失	2-4×加速	无需训练
BQ	32×	15-40%损失	10-50×加速	无需训练
PQ	32-128×	5-20%损失	4-16×加速	需要训练
OPQ	32-128×	0-10%损失	4-16×加速	需要训练
AQ	32-128×	0-5%损失	2-8×加速	需要训练
RaBitQ	32×	5-25%损失	5-10×加速	无需训练

选择决策树

召回率要求 > 95%？
├── 是 → SQ8 或 OPQ
└── 否 → 内存极其受限？
          ├── 是 → PQ 或 RaBitQ + Refine
          └── 否 → 速度优先？
                    ├── 是 → BQ + 重排序
                    └── 否 → PQ 或 OPQ

实践建议

首选SQ8：对于大多数场景，8位标量量化提供了最佳的精度-压缩比权衡。4倍压缩换取约5%的召回率损失，是可接受的折中。
大规模数据用PQ/OPQ：当数据量达到亿级，内存成为瓶颈时，PQ或OPQ可以实现数十倍压缩。OPQ在数据维度相关性强时效果更好。
极致压缩用RaBitQ：对于内存极度受限的场景，RaBitQ提供了理论保证的1比特量化方案。配合重排序可以达到接近原始的召回率。
避免单独使用BQ：二进制量化虽然压缩比最高，但召回率损失严重。建议作为粗筛选器配合重排序使用。
注意数据分布：所有量化方法的效果都受数据分布影响。对于非均匀分布的数据，建议先进行预处理（如PCA白化）。

技术演进的逻辑

回顾二十年来的量化技术演进，可以清晰地看到一条技术主线：从简单的值域截断，到复杂的空间分解，再到理论保证的随机量化。

每个阶段都在解决前一阶段的缺陷：

SQ阶段：简单有效，但压缩比有限
PQ阶段：高压缩比，但假设维度独立
OPQ阶段：处理维度相关性，但增加了训练成本
AQ阶段：更高精度，但编码复杂度更高
RaBitQ阶段：理论保证，但需要高维度才有效

没有银弹。每种方法都是在精度、速度、内存、训练成本之间的权衡。理解这些权衡的本质，才能在实际应用中做出正确的选择。

参考资料

Jégou, H., Douze, M., & Schmid, C. (2010). Product quantization for nearest neighbor search. IEEE TPAMI, 33(1), 117-128.
Ge, T., He, K., Ke, Q., & Sun, J. (2013). Optimized product quantization for approximate nearest neighbor search. IEEE TPAMI.
Babenko, A., & Lempitsky, V. (2014). Additive quantization for extreme vector compression. CVPR.
Jayaram Subramanya, S., et al. (2019). DiskANN: Fast accurate billion-point nearest neighbor search on a single node. NeurIPS.
Guo, R., et al. (2020). Accelerating large-scale inference with anisotropic vector quantization. ICML.
RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound. arXiv:2405.12497.
FAISS Library Documentation. https://faiss.ai/
Milvus Documentation. https://milvus.io/docs
Qdrant Quantization Guide. https://qdrant.tech/documentation/guides/quantization/
Pinecone Learn: Product Quantization. https://www.pinecone.io/learn/series/faiss/product-quantization/

量化的本质：不是降维，是值域压缩#

标量量化：最朴素的起点#

原理与实现#

二进制量化：极致压缩的代价#

Product Quantization：拆分与重构的艺术#

核心思想：分而治之#

压缩比计算#

非对称距离计算#

PQ的性能表现#

Optimized Product Quantization：旋转的力量#

数学原理#

参数化与非参数化方法#

OPQ的优势#

IVF-PQ：聚类与量化的组合拳#

IVF索引原理#

IVF-PQ组合#

nprobe的权衡#

DiskANN：突破内存限制的磁盘索引#

Vamana图算法#

磁盘存储架构#

性能表现#

Additive Quantization：超越PQ的精度#

数学形式#

FAISS中的实现#

与PQ的对比#

RaBitQ：理论保证的1比特量化#

高维空间的几何直觉#

算法原理#

理论误差界#

实际性能#

量化方法对比与选择指南#

选择决策树#

实践建议#

技术演进的逻辑#

更多精彩内容

HNSW：为什么这个图算法正在统治AI时代的向量检索

数字孪生为何成为工业数字化的隐形支柱从NASA阿波罗计划到全球万亿市场的二十年技术演进

为什么D类功放能效高达90%却曾被发烧友鄙视：从甲类到D类放大器的七十年技术博弈

PostgreSQL的表为什么越用越大：从MVCC到Vacuum的完整清理机制解析

一张照片如何被压缩到十分之一：JPEG压缩技术的三十五年演进