快速扫描

什么是快速扫描？​

大多数产品量化（Product Quantizer，简称 PQ）分解会采用每个子向量8位编码，这是因为字节（8位）便于对齐。检索时，查找表（Look-up Table，简称 LUT）被存储在内存（通常是缓存）中，用于距离计算，详见论文 Product quantization for nearest neighbor search 的公式(13)。

但现代CPU在处理算术运算时，比执行内存查找要高效得多。你可以选择用更简单的向量编码方式（如二进制编码或标量分解）来避免频繁的内存查找。

另一种方法是将检索时需要的查找表直接存储在CPU寄存器中。这个思路最早见于论文 Cache locality is not enough: high-performance nearest neighbor search with product quantization fast scan, André等, VLDB 15。因此，这种实现方式命名为“fast-scan”（快速扫描）。

实现原理​

IndexPQFastScan 和 IndexIVFPQFastScan 这两个对象实现了4位PQ的快速扫描，灵感主要来源于Google的 SCANN项目。

由于编码是“打包”在32（或64、96）个为批次中，所以它们没有直接继承 IndexPQ 和 IndexIVFPQ，仅在少数操作点下后两者才具竞争力。

要将查找表存储在寄存器中，必须满足以下条件：

• 需要有大量向量寄存器并有查找指令（如shuffle），如Intel AVX（16个256位寄存器，当前唯一支持的平台），或ARM Neon（32个128位寄存器）。
• 查找表必须很短：8位PQ查找表有256项，需降至4位仅16项。
• 查找表的每个项必须很小：无法使用浮点数，所以每项需量化为8位。

重排序（Re-ranking）​

4位PQ的准确率相对较低（比如PQ32x4的准确率明显不如PQ16x8，即使它们占用同样内存），因此通常建议增加精确距离计算步骤来做重排序。

这可以通过 IndexRefine 对象实现。它同时维护两个索引，后者对前者的检索结果做更精确的提升。例如，需要得到 $k=10$ 个结果时，可以先从第一个索引查询 $k \times k\_factor = 100$ 个，然后对这100个再计算精确距离，最后返回最优的前 $k$ 个。

工厂字符串（Factory Strings）​

Faiss支持通过 index_factory函数 根据字符串描述自动构建索引。

新版本PQ支持新的工厂字符串：

• PQ32x4fs 为PQ32x4的“快速扫描”变体。如果加上 IVF 前缀，则生成IVF索引。IVFy,PQ32x4fsr 则为对中心残差向量做PQ编码的IVF变体（更准但略慢）。

• 重排序本就支持 RFlat 后缀。任何索引均可作为重排序方法，如 Refine(SQ8) 表示用SQ8索引做重排。

• 4位PQ也可以作为粗量化器。例如，IVF工厂字符串已拓展为 IVF1000(PQ32x4fs,Rflat)，即用 PQ32x4fs 和 Rflat 做粗量化以聚类至1000个中心。

更复杂的例子见官方Wiki。

性能对比​

• 与SCANN的比较：Faiss的4位PQ快速扫描在四个百万规模数据集上的速度和准确率均不逊色于SCANN，常常更快。
• 与HNSW对比：不加重排序时，4位PQ能达到1M QPS（每秒百万查询）；加重排序则0.9的一次召回率（1-recall@1）下有28万QPS，约2倍于HNSW的14万QPS，且内存占用更低（因为HNSW需存储图结构）。
• 适用于千万至亿级向量的最佳索引：不同编码长度下实验表明，4位PQ快速扫描十分高效，可用作粗量化，除了精度极高的场景外几乎都是最优选。
• 假如每个向量64字节，可将8字节用于快速扫描PQ，56字节做后续重排序。

加性量化（Additive Quantization, AQ）实现​

由 KinglittleQ 实现的加性量化在查询时原理类似于PQ。区别在于加性量化的L2版本里，距离累计时还需加上范数（即向量模长）。

实现细节​

目标是高效计算查询向量 $q$ 与数据库向量 $b$ 的距离：

distance[q, b] = \sum_{sq=0}^M LUT[q, list\_no, sq, code[b, sq]] + bias[q, list\_no]

• 每次核心计算可并发处理32个数据库向量。
• 由于使用4位编码，LUT[q, sq, :] 长度为16。
• 偏置项 $bias$ 仅用于IVF索引，表示每个倒排表因残差量化需加的修正项（与倒排表编号 list_no 有关）。

本实现主要兼容AVX（Intel），同时支持ARM Neon（感谢 @vorj、@n-miyamoto-fixstars、@LWisteria、@matsui528 的贡献）。底层用到轻量SIMD抽象库 simdlib.h。

代码布局（Code Layout）​

以批量大小bbs=32、M个子量化器为例，编码分布如下：

即每个32字节块，含两个子量化器对应32个向量的编码。

下图展示了32个向量及m、m+1号量化器的编码存储位置：

C++参考实现：pq4_fast_scan.h

查找表量化（LUT Quantization）​

非快速扫描实现累加用的是float32（单精度浮点），写法相对简单。但SIMD优化下需把距离量化为整数：

• 查找表LUT项为无符号8位整数
• 累加器和距离为无符号16位整数
• 偏置同为16位无符号

查找表算好后再四舍五入归为整数域（为简化略去 $q$ 的下标）：

A * (distance[b] - B) ≈ distance_i[b] = \sum_{sq=0}^M LUT_i[list\_no, sq, code[b, sq]] + bias_i[list\_no]

归一化系数A、B选取时需满足：1）极小精度损失，即A尽量大；2）16位结果不能溢出；3）每个8位查找表项也不能溢出。

查找表布局（LUT Layout）​

对于给定查询、量化器m和m+1的查找表布局如下：

借助掩码与移位操作，两个SIMD查找即可取出计算32个向量、2个量化器所需的2*32个查找表项。按16位累加，恰好能用4次无饱和加法完成所有距离求和。

具体代码见 faiss/impl/pq4_fast_scan_search_qbs.cpp

多查询任务处理（Multiple Queries）​

为提升CPU利用率，代码支持批量同时处理多个查询。即一次扫描可为多个查询向量同时建立距离表，加快整体检索效率。