跳到主要内容

加法量化器（Additive Quantizer）简介

加法量化器是一种将高维向量 xx （维度为 dd）近似为多个查找表中向量之和的方法：

x≈x′=T1[i1]+...+TM[iM] x \approx x' = T_1[i_1] + ... + T_M[i_M]

其中，TmT_m 表示第 mm 个查找表，包含若干 dd 维向量，可通过索引 imi_m 访问。第 mm 个表的大小为 KmK_m。向量 xx 可用索引组合 (i1,...,iM)(i_1, ..., i_M) 表示。表示该向量所需的比特数为 ⌈log⁡2(K1)⌉+...+⌈log⁡2(KM)⌉\lceil \log_2(K_1) \rceil + ... + \lceil \log_2(K_M) \rceil。

如同其他数据自适应量化方法一样，T1,...,TMT_1, ..., T_M 这些查找表需要通过训练数据进行学习。

产品量化（Product Quantization，简称 PQ）可以视为加法量化的特例——在 PQ 每个查找表 TmT_m 中，仅 d/Md/M 维的子向量非零，其余为零。

更多关于加法量化的详细介绍，可参考论文 Additive quantization for extreme vector compression，Babenko 和 Lempitsky，CVPR 2014。

Faiss中的加法量化器实现

Faiss 实现基于 AdditiveQuantizer 对象。

Faiss 要求每个 KmK_m 必须为 2 的幂次，但各 KmK_m 之间数值可以不同。

加法量化器的解码过程是确定性的，但训练和编码（即如何找到最佳的 (i1,...,iM)(i_1,...,i_M)）通常没有简单的方案。因此，Faiss 提供了两种不同的加法量化器实现：残差量化器（Residual Quantizer, RQ）和局部搜索量化器（Local Search Quantizer, LSQ）。

残差量化器（Residual Quantizer，RQ）​

Faiss中的残差量化器位于 ResidualQuantizer 对象中。

在残差量化中，编码过程采用顺序式方法。在对 xx 的第 mm 阶段编码时，编码器选择一个查找表条目，使其能最优地重构 xx 的残差：

im=argmin⁡j=1..Km∥Tm(j)−(x−T1[i1]−…−Tm−1[im−1])∥2i_m = \underset{j=1..K_m}{\operatorname{argmin}} \| T_m(j) - (x - T_1[i_1] - \ldots - T_{m-1}[i_{m-1}]) \|^2

这种“贪心”方法（greedy approach）容易陷入局部最优。

提示

为减少陷入局部最优的风险，编码器会维护多个编码候选（beam），并在最终阶段 MM 选出最优编码。beam 的大小由 max_beam_size 属性控制，取值越大，精度越高，但编码速度越慢。

训练过程中，各查找表按步骤依次使用 k-means 聚类进行训练，max_beam_size 同样适用于训练过程。Faiss 的 ResidualQuantizer 支持低维度启动的 k-means 训练过程，具体参考"Improved Residual Vector Quantization for High-dimensional Approximate Nearest Neighbor Search"，Shicong 等，AAAI 2015。

这种 k-means 的递进式实现由 ProgressiveDimClustering 对象提供。

局部搜索量化器（Local Search Quantizer，LSQ）​

LSQ 量化器源自论文 "LSQ++: Lower running time and higher recall in multi-codebook quantization"，Julieta Martinez 等，ECCV 2018。实现在 LocalSearchQuantizer。

编码时，LSQ 以向量的随机编码为初始值，随后采用模拟退火方式进行迭代优化，以提升编码准确率。编码步数由 encode_ils_iters 参数控制，可平衡编码速度与精度。

important

Faiss 当前对 LSQ 的实现仅支持每个查找表 K1=...=KMK_1 = ... = K_M 大小一致的情况。

加法量化器工厂字符串快速入门

Screenshot 2025-02-18 at 1 23 42 PM

作为编码解码器（Codec）使用

加法量化器最简单的用法是作为编码解码器（codec）使用。它们带有 compute_codes（编码）和 decode（解码）两个主要函数。

由于编码是近似且迭代式的，所以编码时间与精度之间需要做权衡。

备注

本节将比较不同量化器的重构误差和召回率等性能。

不同加法量化器选项的对比​

我们在 Deep1M 和 Bigann1M 数据集上评估不同加法量化器选项（bigann 数据集比 SIFT1M 更大，便于使用超过 10 万训练向量）。结果采用平均的对称 L2 编码误差，方便与Codec benchmarks对比。

评估参数为 64 位和 128 位编码。由于编码时间常成为性能瓶颈，此处绘制“准确率-编码时间”曲线。

对于同一量化器，通过调整 max_beam_size（残差量化器）或 encode_ils_iters（LSQ）参数，可以获得不同准确/速度权衡点。

64 位编码结果​

128 位编码结果​

主要结论：

  • PQ 系列（PQ 和 OPQ）在所有选项中编码速度最快。
  • 建议尝试不同于传统 8 位量化的配置，使用更大词表能探索更多有趣的权衡点，但训练耗时可能较长。
  • 大多数情况下，残差量化器优于 LSQ 量化器。
  • 对于残差量化器，采用查找表（rq_lut）在高 max_beam_size（以及高维度数据，未在上图列出）时尤为有用。其方法是将量化器对象的 use_beam_LUT 属性设为 1。
如何复现实验结果

实验源码： benchs/bench_quantizer.py

实验脚本：

for dsname in deep1M bigann1M ; do

    for q in pq rq lsq rq_lut; do
        for sz in 8x8 6x10 5x12 10x6    16x8 12x10 10x12 9x14 8x16; do
            run_on_half_machine BQ.$dsname.$q.$sz.j \
                /usr/bin/time -v python -X faulthandler -u $code/benchs/bench_quantizer.py $dsname $sz $q
        done
    done
done

绘图请参考：相关 notebook

残差量化器 use_beam_LUT=1 实现原理​

在编码第 mm 步时，需要计算当前 beam 候选与查询的距离：

im=argminj=1..Km∥Tm(j)−(x−T1[i1]−...−Tm−1[im−1])∥2⏟Dji_m = \underset{j=1..K_m}{\mathrm{argmin}} \underbrace{\| T_m(j) - (x - T_1[i_1] - ... - T_{m-1}[i_{m-1}]) \|^2 }_{D_j}

采用 use_beam_LUT 时，距离分解如下：

Dj=∥Tm(j)∥2+∥x−T1[i1]−...−Tm−1[im−1]∥2−2⟨Tm(j),x⟩+2∑ℓ=1m−1⟨Tm(j),Tℓ(iℓ)⟩D_j = \| T_m(j) \|^2 + \| x - T_1[i_1] - ... - T_{m-1}[i_{m-1}] \|^2 - 2 \langle T_m(j), x \rangle + 2 \sum_{\ell=1}^{m-1} \langle T_m(j), T_\ell(i_\ell) \rangle

各项具体计算方式：

  • ∥Tm(j)∥2\| T_m(j) \|^2：保存在 cent_norms 表中
  • ∥x−T1[i1]−...−Tm−1[im−1]∥2\| x - T_1[i_1] - ... - T_{m-1}[i_{m-1}] \|^2：为第 m−1m-1 步的累计编码距离
  • ⟨Tm(j),x⟩\langle T_m(j), x \rangle：在函数入口计算（计算复杂度随 dd 成正比）
  • $\sum_{\ell=1}^{m-1} \langle T_m(j), T_\ell(i_\ell) \rangle$：保存在 codebook_cross_products 表中
提示

上述方法在高维（dd 较大）且量化步数 MM 不是非常大时更具优势，因为第 3 项的计算量随 MM 的平方增长。

Flat类型索引

通过加法量化器，可以在压缩域内直接做距离比较，实现高效的“查询-数据库”比对。Flat 类型索引由 IndexAdditiveQuantizer 实现，并被其子类 IndexResidualQuantizer 和 IndexLocalSearchQuantizer 继承。

search（查询）函数只依赖于加法量化器的解码方式，并适用于上述任一子类。

查找表（LUT，Look Up Table）实现​

对于给定查询向量 qq，可以预先计算以下查找表：

LUTm[i]=⟨Tm[i],q⟩∀m=1..M,  i=1..Km \mathrm{LUT}_m[i] = \langle T_m[i], q \rangle \quad \forall m = 1..M, \; i = 1..K_m

则编码为 [i1,...,iM][i_1, ..., i_M] 的向量 x′x' 与 qq 的内积为：

⟨q,x⟩≈⟨q,x′⟩=LUT1[i1]+...+LUTM[iM] \langle q, x \rangle \approx \langle q, x' \rangle = LUT_1[i_1] + ... + LUT_M[i_M]

L2 距离查询与范数存储问题​

直接使用 LUT 难以计算 L2 距离，但如下公式成立：

∥q−x′∥2=∥q∥2+∥x′∥2−2⟨q,x′⟩ \|q - x'\|^2 = \|q\|^2 + \|x'\|^2 - 2 \langle q, x' \rangle

因此只需单独存储 ∥x′∥\|x'\| 即可支持距离计算。此功能由 AdditiveQuantizer 对象的 search_type 属性控制。

可取值如下：

  • ST_decompress：不存储范数，运行时解压向量重算
  • ST_LUT_nonorm：假设 ∥x′∥=0\|x'\| = 0（仅适用于已归一化向量）
  • ST_norm_float, ST_norm_qint8, ST_norm_qint4：不同压缩级别下存储范数

性能评估​

TODO

IVF 索引结合加法量化编码

加法量化器可与IVF（倒排文件）索引结合，和产品量化（PQ）或标量量化（SQ）无缝替换使用。具体做法是：数据库向量 xx 首先经 coarse quantizer（粗量化器）分桶存储。

Faiss实现体现在对象 IndexIVFAdditiveQuantizer、IndexIVFResidualQuantizer 和 IndexIVFLocalSearchQuantizer。

同时，每个桶关联一个质心 cc（即粗量化器结果）。通常，编解码向量 x−cx-c（残差）效果更佳，因为残差范数更小。编码是否基于残差，由 by_residual 属性决定。

性能评估​

对于百万规模（1M）数据集，coarse quantizer 维持不变（Flat，1024 个质心）。我们对比各 IVF 变体在不同 nprobe 下的速度与精度，并给出添加时间。编码耗时常为主要瓶颈。有关量化器字符串说明详见The index factory。

LSQ 与残差量化器对比​

主要观察：

  • IVF PQ 明显比加法量化器变体更快，主要原因是加法量化器暂未实现预计算查找表（precomputed tables）相关优化。
  • 由于加法量化器配置为 7x8 位加上 8 位范数（qint8），总计 64 位，等同于 PQ8x8。令人意外的是，向量范数的精确编码（_Nfloat）不一定优于 8 位量化（_Nqint8）。
  • 加法量化器在准确率方面通常具有明显优势。
  • LSQ 的添加速度比残差量化器更快。

本实验残差量化器 beam size 固定为 30，下面会进一步探讨该参数的影响。

残差量化器结合查找表​

在此实验中启用了查找表（use_beam_LUT=1），并让 beam size 可变（BSx 后缀表明不同 beam size）。

主要观察：

  • 启用查找表后，残差量化器（RQ）的编码速度大幅提升。
  • 增大 beam size 并不总能获得最优准确率。
如何复现实验结果

实验源码： benchs/bench_all_ivf/bench_all_ivf.py

实验脚本：

for dsname in sift1M deep1M; do

    for indexkey in \
        IVF1024,RQ7x8_Nqint8 IVF1024,RQ7x8_Nfloat IVF1024,PQ8x8 \
        IVF1024,LSQ7x8_Nqint8 IVF1024,LSQ7x8_Nfloat
    do
        run_on_half_machine IVFQ.$dsname.$indexkey.f \
            python -u $code/benchs/bench_all_ivf/bench_all_ivf.py --db $dsname --indexkey $indexkey
    done

    for indexkey in IVF1024,PQ8x8np
    do
        run_on_half_machine IVFQ.$dsname.$indexkey.d \
            python -u $code/benchs/bench_all_ivf/bench_all_ivf.py --db $dsname --indexkey $indexkey --autotune_range ht:64
    done

    run_on_half_machine IVFQ.$dsname.IVF1024,RQ8x8_Nnone.c \
            python -u $code/benchs/bench_all_ivf/bench_all_ivf.py --db $dsname --indexkey IVF1024,RQ8x8_Nnone

    run_on_half_machine IVFQ.$dsname.IP.IVF1024,RQ8x8_Nnone.c \
            python -u $code/benchs/bench_all_ivf/bench_all_ivf.py --force_IP --db $dsname --indexkey IVF1024,RQ8x8_Nnone

done

for beam_size in 1 2 4 8 16 32 64; do
    for dsname in sift1M deep1M; do

for indexkey in IVF1024,RQ7x8_Nqint8 IVF1024,RQ7x8_Nfloat do run_on_half_machine IVFQ.dsname.dsname.indexkey.BSbeamsize.a python−ubeam_size.a \ python -u code/benchs/bench_all_ivf/bench_all_ivf.py
--db dsname−−indexkeydsname --indexkey indexkey --RQ_use_beam_LUT 1
--RQ_beam_size $beam_size done

done done

绘图请参考：此Jupyter Notebook。

加法粗量化器（Additive coarse quantizers）

每个量化器（quantizer）都有一组重构值（reproduction values），也就是它可以解码的所有向量。这组值在不是很大的情况下，可以看作一组质心（centroids）。通过在质心集合上执行最近邻搜索，我们可以得到IVF（倒排文件）索引的粗量化器。

如果设置 nprobe > 1，则可以自然地支持访问多个桶（bucket），方法就是查找距离最近的 nprobe 个质心。

与“平坦”粗量化器相比，加法粗量化器的准确率略低，但分配过程更高效，且粗量化器的码本（codebook）更为紧凑。

以下为加法粗量化器的相关类：

  • AdditiveCoarseQuantizer
  • 其子类 ResidualCoarseQuantizer（残差粗量化器）
  • 其子类 LocalSearchCoarseQuantizer（局部搜索粗量化器）

对于采用L2距离的粗量化器，会默认将所有质心的范数（norms）保存在 centroids_norms 中，以提升效率。如需关闭该功能，可以在 rcq.rq.train_type 中设置 ResidualQuantizer::Skip_codebook_tables。

检索最近的质心有两种方式，通过 ResidualCoarseQuantizer 的 beam_factor 字段选择：

  • 束搜索（Beam Search，默认） ResidualCoarseQuantizer 默认使用束搜索。束的大小为 beam_factor × nprobe。

  • 穷举搜索（Exhaustive Search） 若beam_factor为负值，则对所有质心计算距离，保留距离最近的 nprobe 个质心。在这种模式下，由于需要范数，因此不能设置 Skip_codebook_tables。 LocalSearchCoarseQuantizer 总是采用穷举搜索。

可通过 set_beam_factor 方法设置 beam_factor，此方法会进行必要的校验，并在需要时计算表格。

提示

L2距离即欧氏距离，常用于向量之间的距离度量。

性能评估（Evaluation）​

我们对四种粗量化方法进行比较：平坦量化器（flat quantizer）、IMI（倒排多重索引 Inverted Multi-Index）量化器、残差粗量化器（residual coarse quantizer）、以及两级量化。

第四种“两级量化”是一种非常简单的方法，由微软的Harsha Simhadri提出，他也是 十亿级近似最近邻挑战赛 的发起人。该方法仅通过两级分层聚类获取质心，但在分配（assignment）时，并没有层次化路由，而是直接从全量表中查找。

每个实验均运行一个 IndexIVFFlat，并采用不同的量化器配置，统一生成 nlist = 128² = 16384 个质心。检索时，根据 nprobe 的不同设置，可以在1-recall@1（准确率）和距离计算次数（检索时间的代表量）之间做权衡。

bigann1M任务的粗量化器评测结果 deep1M任务的粗量化器评测结果

观察：

  • 平坦量化与两级聚类的准确率最佳，但需要存储全部质心。在所有“紧凑”方法中，RCQ（残差粗量化器）的准确率明显优于IMI。
  • 图中已标出训练时间，对于平坦索引来说，训练时间呈二次增长，是所有方法中最慢的。
  • 对于两级聚类和平坦方式，增量时需全表检索质心，通常会在质心集合上建立HNSW（分层导航小世界）索引。但在本小规模实验中，HNSW的性能与理论曲线几乎一致，差别微乎其微。

性能评测代码请参阅：large_coarse_quantizer.ipynb

残差量化器的前缀和后缀拆分​

残差量化器（residual quantizer）有一个特殊特性：平坦结构的 IndexResidual 可直接无须重新编码（re-encoding）地转为 IndexIVFResidual。操作方式如下：

  • 将编码（codes）分割成前缀和后缀，例如 [i1,...,i3][i_1, ..., i_3] 和 [i4,...,iM][i_4, ..., i_M]
  • 残差编码器也相应拆分为 ResidualCoarseQuantizer（前3个码本），其余的 M-3 个码本由 IndexIVFResidual 管理
  • [i_4, ..., i_M] 对应的编码存储于倒排表（inverted lists）中

检索时，距离的计算结果与平坦结构下的IndexResidual完全等价，只是加入了非穷举检索的能力。

代码测试见：test_residual_quantizer.TestIndexResidualQuantizer.test_equiv_rq