IVF-PQ向量索引加速方案

可视化演示

展示IVF-PQ两阶段加速架构：IVF聚类粗筛缩小搜索范围、PQ乘积量化压缩向量降低内存、ADC非对称距离计算加速查询，交互切换四种模式深入理解。

检索问题背景

想象你就是那位刚上任的图书馆管理员，面前是十亿本毫无分类的书。读者来问“有没有讲沙漠植物的书”，你只能从第一本开始翻。这就是向量检索中的暴力搜索：高维空间里，每个向量被抽象为一本书，查询时要与全部 $n$ 个向量逐一计算距离。当 $n$ 达到十亿、向量维度 $d$ 达到几百时，一次查询需要数十亿次浮点运算，用户早就失去耐心了。

于是近似最近邻（ANN） 的思想登场：不苛求 100% 精确，而是“高概率找到真正的最近邻”，用少量精度损失换取数量级的加速。这就像管理员不再保证“一定找到全世界最早那本”，而是保证“大概率找到最相关的那几本”。从工程角度看，纯粹依赖暴力搜索的系统根本无法支撑大模型时代的海量向量检索，索引设计成了刚需。

一个实用的索引需要回答三个问题：如何把“图书馆”分区？如何给“书”做摘要？如何在检索时把两者串起来？这正是 IVF 和 PQ 各自扮演的角色——一个负责粗粒度地理定位，一个负责细粒度快速比对。

面对这样的线性灾难，管理员决定动手改造图书馆：先按学科分区（IVF），再做摘要卡（PQ）。暴力检索在十亿级规模下不可行，但有了这两件工具，一切开始变得可控——这正是下一节要展开的第一级加速。

倒排文件IVF

管理员的第一步改造是“学科分区”：把十亿本书按内容聚成 $nlist$ 个区域，每个区域门口挂一块“主题标识牌”。这个标识牌在算法里叫聚类中心（centroid），由 K-Means 在全部向量上无监督训练得到。分区完成后，每条向量被分配到距它最近的聚类中心，归入对应的倒排列表（posting list）——这就是倒排文件（IVF） 的本体：一张“分区→书单”的索引表。

检索时，查询向量 $\mathbf{q}$ 先计算与所有 $nlist$ 个聚类中心的距离，挑出最近的 $nprobe$ 个区域（$nprobe$ 意思就是“查几个书架”），只扫描这些倒排列表里的向量，构成候选集。整个过程中，全库范围被迅速收缩到 $nprobe \times \frac{n}{nlist}$ 条候选向量上。比如 $nlist=4096$、$nprobe=8$ 时，候选量只有全库的 $8/4096 \approx 0.2\%$，这就是第一级加速。

有了分区，读者不用再翻遍全馆，但每个分区里依然可能躺着几百万本书。要把每本书都翻一遍还是太慢——这就是第二级加速（PQ 摘要卡）要解决的问题。IVF 负责“圈地”，PQ 负责“扫货”。

乘积量化PQ

分区找到后，管理员发现目标书架上的书仍以百万计。于是第三步改造：给每本书做一张“内容摘要卡”。做法很巧妙——把一本书的特征（$d$ 维向量）切成 $m$ 段，每段是一个子向量。针对每一段，在所有训练向量上单独跑一次 K-Means，学到 $k$ 个代表性码字，组成一个码本（codebook）。这段子向量离哪个码字最近，就用码字的编号（一个 0~255 的字节）来表示。全书只需 $m$ 个字节的短码。

这就是乘积量化（PQ） 的精髓：把高维空间的距离计算转化为查表。比较两本书时，不需要恢复原始内容，而是先为查询的每个子段在对应码本里查好“到各码字的距离表”，再按候选向量的码字编号把距离取出来求和。这个操作从 $O(d)$ 退化到 $O(m)$，而 $m$ 通常是 8~64，远小于 $d$。

有了摘要卡，管理员不必翻开每本书就能快速排序。但注意：摘要卡毕竟是“摘要”，比较时用的是码字之间的近似距离，存在量化误差。把“分区定位”和“摘要比对”串成一条流水线，就是 IVF-PQ 的完整工作流。

IVF-PQ协同

现在管理员的工作流变得非常清晰：第一步粗筛，根据查询向量的“主题”定位到最近的 $nprobe$ 个分区（IVF）；第二步精排，在这些分区的候选书架上，用摘要卡快速计算近似距离（PQ）。两条加速策略各管一段，前者缩减规模，后者压低单次比较成本，合起来产生乘法效应的加速。

从数学上看，一次 IVF-PQ 查询的总开销由两部分构成。第一部分是与所有聚类中心比距离，约 $nlist \times d$；第二部分是在候选分区内对每条向量做 PQ 查表，候选总数约 $nprobe \times \frac{n}{nlist}$，每条只需 $m$ 次查表。当 $nlist$ 和 $nprobe$ 配合得当时，总开销比暴力搜索小几个数量级。这也是为什么它能支撑十亿级向量库的在线检索。

两级加速的协同效应，就像先坐电梯到正确楼层、再在书架间用摘要卡扫视——每一级都避开了不必要的劳动。理解这条流水线后，接下来最关键的问题浮出水面：分区该分多细？该查几个书架？摘要卡该做几段？

参数与调优

图书馆的分区数量、读者愿意逛的书架数、摘要卡的精细度，分别对应 IVF-PQ 的三个核心参数：$nlist$、$nprobe$、$m$。它们像三个旋钮，共同决定系统的检索速度和召回质量。

$nlist$ 决定分区粒度。$nlist$ 太小，每个桶太长，候选集过滤效果差；$nlist$ 太大，聚类中心多到无法代表簇内分布，且第一阶段找分区的开销本身也在涨。实践上 $nlist$ 常取 $\sqrt{n}$ 到 $n/1000$ 量级，比如千万级数据用几千个分区。$nprobe$ 决定“逛几个书架”：增大 $nprobe$ 能覆盖更多桶、提升召回，但延迟线性上升；工业场景通常取 1~64，用 recall-QPS 曲线去选拐点。$m$ 决定摘要卡段数：$m$ 越大，量化越精细、精度越好，但内存占用也从 $m$ 字节同步上升。

调参的本质是在三个旋钮之间找平衡点。如果你把 $nprobe$ 调到等于 $nlist$，等于把全馆书架都逛一遍——第一级加速消失；如果 $m$ 设得过大，摘要卡比原书还厚——内存优势也不复存在。真正的高手会用一组实验曲线来选参数，而不是拍脑袋。

性能与召回

现在，我们把账算清楚：IVF-PQ 到底赢在哪里，又付出了什么代价。先看内存。原始向量若用 float32 存储，每条占 $4d$ 字节；PQ 压缩后每条只存 $m$ 个 8 位码字，占 $m$ 字节。当 $d=768$、$m=64$ 时，压缩比高达 $4 \times 768 / 64 = 48$ 倍——十亿条向量的内存从几个 TB 降到几十 GB，普通服务器就能扛住。

再看延迟。暴力搜索要做 $n \times d$ 次乘加，IVF-PQ 则缩到 $nlist \times d + nprobe \times \frac{n}{nlist} \times m$。以 $n=10^9$、$d=768$、$nlist=10^4$、$nprobe=8$、$m=64$ 估算，总计算量约为暴力搜索的 $1/5000$ 到 $1/10000$，配合 SIMD 指令级优化，单次查询轻松进入毫秒级。这正是向量数据库（如 Milvus、Faiss、Qdrant）把 IVF-PQ 作为工业标准方案的底气。

代价是召回率的下降。IVF 粗筛可能把真正的最近邻留在未扫描的分区里，PQ 码字也让距离带上量化误差。工业界的常规做法是：用 recall@k（前 k 个结果中包含真实最近邻的比例）作为指标，画一条“召回率 vs 每秒查询数（QPS）”的曲线，在业务可接受的召回阈值下选择吞吐最高的参数组合。图书馆管理员的智慧到最后其实是一句话：任何加速都有代价，关键是把代价花在用户看不见的地方。

AI 应用场景

Python 演示

import numpy as npfrom collections import defaultdict  class IVFPQ:    def __init__(self, nlist=8, m=4, nprobe=2, k=256):        self.nlist = nlist        self.m = m        self.nprobe = nprobe        self.k = k        self.d = None        self.sdim = None        self.centroids = None        self.codewords = None        self.posting = defaultdict(list)     def _kmeans(self, X, k, iters=6):        idx = np.random.choice(len(X), k, replace=False)        centers = X[idx].copy()        for _ in range(iters):            dists = np.linalg.norm(X[:, None, :] - centers[None, :, :], axis=2)            labels = np.argmin(dists, axis=1)            for c in range(k):                if (labels == c).sum() > 0:                    centers[c] = X[labels == c].mean(axis=0)        return centers     def train(self, X):        self.d = X.shape[1]        self.sdim = self.d // self.m        self.centroids = self._kmeans(X, self.nlist)        dists = np.linalg.norm(X[:, None, :] - self.centroids[None, :, :], axis=2)        assign = np.argmin(dists, axis=1)        self.codewords = []        for j in range(self.m):            sub = X[:, j * self.sdim:(j + 1) * self.sdim]            self.codewords.append(self._kmeans(sub, self.k))     def _encode(self, x):        code = []        for j in range(self.m):            sub = x[j * self.sdim:(j + 1) * self.sdim]            dists = np.linalg.norm(self.codewords[j] - sub, axis=1)            code.append(int(np.argmin(dists)))        return tuple(code)     def add(self, X):        dists = np.linalg.norm(X[:, None, :] - self.centroids[None, :, :], axis=2)        assign = np.argmin(dists, axis=1)        for i, cid in enumerate(assign):            self.posting[cid].append((self._encode(X[i]), i))     def search(self, q, topk=5):        dist_c = np.linalg.norm(self.centroids - q, axis=1)        probes = np.argsort(dist_c)[:self.nprobe]        cand = []        for cid in probes:            for code, idx in self.posting[cid]:                approx = 0.0                for j in range(self.m):                    sub_q = q[j * self.sdim:(j + 1) * self.sdim]                    table = np.linalg.norm(self.codewords[j] - sub_q, axis=1)                    approx += table[code[j]] ** 2                cand.append((approx, idx))        cand.sort()        return [i for _, i in cand[:topk]]  if __name__ == "__main__":    np.random.seed(0)    n, d = 2000, 32    X = np.random.randn(n, d).astype(np.float32)    index = IVFPQ(nlist=8, m=4, nprobe=2)    index.train(X)    index.add(X)    q = X[7]    print("IVF-PQ top5:", index.search(q, 5))

1. self.centroids = self._kmeans(X, self.nlist)对全量向量做 K-Means，学出 nlist 个分区标识牌（IVF 第一级）。
2. dists = np.linalg.norm(X[:, None, :] - self.centroids[None, :, :], axis=2)批量计算每条向量到所有聚类中心的距离。
3. assign = np.argmin(dists, axis=1)把每条向量分到最近的分区，决定它进哪个倒排列表。
4. self.codewords.append(self._kmeans(sub, self.k))对第 j 段子向量单独学码本，这是 PQ 的核心训练动作。
5. code.append(int(np.argmin(dists)))子向量落到最近的码字上，用编号替代原始连续值。
6. self.posting[cid].append((self._encode(X[i]), i))将压缩后的码和原始编号写入对应分区的倒排列表。
7. probes = np.argsort(dist_c)[:self.nprobe]查询时只取最近的 nprobe 个分区，完成粗筛。
8. table[code[j]] ** 2直接查“子段到码字距离表”取近似距离，避免真实向量计算。

常见误区

面试题