IVF与乘积量化PQ

另一条思路：不要每次都看全库

上一篇讲的是图索引。现在换一个角度思考最近邻搜索：如果查询向量通常只会靠近某一小片区域，那么有没有办法在查询前先判断“它大概属于哪一片”，只在那一片附近搜索，而不是把整个向量库都看一遍。这就是 IVF 一类方法的出发点。

倒排文件索引Inverted File Index, IVFInverted File Index, IVFIVF partitions the vector space into coarse clusters. At query time it first finds the closest coarse centroids, then searches only the vectors assigned to those clusters instead of scanning the entire collection. 的名字看起来像全文搜索里的倒排索引，但在向量检索里，它的含义是“先做粗粒度分桶，再做桶内搜索”。你可以把它理解成先把向量空间分成许多小区，每个向量被分配到某个小区里；查询发生时，先判断查询最接近哪些小区，然后只访问这些小区中的向量。

这种做法的好处很直接：候选集合大幅缩小。原本要看一千万条向量，现在也许只看其中几十万甚至几万条。速度由此提升。代价同样明显：如果真实最近邻恰好落在未被访问的小区里，它就会被漏掉，所以 IVF 天生是一种近似搜索方法。

IVF 的训练和查询各做了什么

构建 IVF 索引时，系统通常先对样本向量运行聚类，得到一批粗粒度的中心点，也可理解为若干个簇的代表。每个真实向量随后被分配给离自己最近的中心点，于是形成许多倒排列表。查询到来时，先计算查询向量与这些中心点的距离，再挑出最接近的若干个簇进入下一步。

这里涉及一个非常重要的参数：nprobenprobenprobe 表示一次查询要访问多少个簇。访问的簇越多，越不容易漏掉真实近邻，召回率通常更高；但要计算和扫描的候选也会变多，查询延迟随之增加。 。如果只探查 1 个簇，速度很快，但可能漏得很多；如果探查 32 个、64 个簇，召回率通常更高，但延迟也会变大。IVF 的调优，本质上就是在簇数量、簇质量和 nprobe 之间平衡。

与 HNSW 相比，IVF 的结构更容易理解，也更容易与后续压缩技术结合。它先做的是“粗筛”，不是最终精确排序。

仅仅缩小搜索范围还不够

假设你已经用 IVF 把候选缩小到了原来的百分之一，但每条向量仍然是 768 维 float32。这意味着每条向量要占数 KB 存储，百万级、千万级数据很快就会消耗大量内存或磁盘带宽。于是第二个问题出现了：能否在保留相似关系的大前提下，把向量表示得更紧凑。

这就是乘积量化Product Quantization, PQProduct Quantization, PQProduct Quantization compresses a high-dimensional vector by splitting it into sub-vectors and encoding each part with a small codebook index. Distances can then be approximated using compact codes rather than full-precision floats. 的作用。PQ 的目标不是先决定“看哪些向量”，而是让“看每条向量”的成本更低。

PQ 如何把一个长向量压成短编码

PQ 的核心动作，是把高维向量切成多个子向量。例如一个 768 维向量，可以拆成 96 个 8 维子向量。对于每个子空间，系统都会训练一个小型码本。真实向量在该子空间里的那一段，只需记录自己最接近码本中的哪一个中心。这样一来，原本需要保存许多浮点数的子向量，就被压缩成一个很短的整数编码。

整条向量因此不再以全精度形式存储，而是被表示为一串码字索引。查询时，系统会预先计算查询向量与各个子空间码本之间的距离表，然后把候选向量的编码查表相加，近似得到整体距离。这就是非对称距离计算非对称距离计算非对称距离计算指查询向量仍保留较高精度，而库中的向量用压缩编码表示。系统通过“查询到码本”的查表方式估计距离，从而减少内存访问与计算量。 的常见思路。

PQ 带来的收益主要体现在内存与带宽。原本大规模向量索引很可能只能放在磁盘或昂贵的内存里，压缩后就可能装入更小的内存预算，查询阶段读取的数据也更少。代价是距离不再完全精确，排序质量会有损失。

IVF-PQ 为什么常被一起使用

IVF 解决的是“先去哪里找”，PQ 解决的是“找到候选后如何更便宜地比较”。两者组合之后，就形成了经典的IVF-PQIVF-PQIVF-PQIVF-PQ combines coarse partitioning and vector compression. IVF narrows the search to a few promising lists, while PQ stores compact representations inside those lists so the candidate scan remains memory-efficient. 方案。

查询流程可以概括为三步。第一步，用粗聚类中心快速锁定若干个候选簇。第二步，在这些簇中，不再读取每条向量的原始浮点表示，而是读取 PQ 压缩后的编码，并利用查表近似计算距离。第三步，如果业务需要更高精度，可以对前若干候选再回到原始向量做重算。这种“粗筛 + 压缩 + 可选重排”的结构，长期以来都是单机场景里非常实用的折中。

从工程角度看，它其实是在做两次交换。IVF 用一部分召回率换搜索速度，PQ 用一部分精度换内存占用。两种损失叠加后，换来的通常是数量级上的成本改善。只要调参得当，整体收益会非常明显。

用 FAISS 实测 IVF、PQ、IVF-PQ 三种索引

光说理不直观，用 FAISS 跑一遍最清楚。FAISS（Facebook AI Similarity Search）是这套算法的"参考实现"，绝大多数向量库底层都用了它的算法。

pip install faiss-cpu numpy

import numpy as np
import faiss
import time

np.random.seed(42)

# 100 万条 128 维向量（用小维度让 demo 跑得快，原理一致）
n_data, dim = 1_000_000, 128
data = np.random.randn(n_data, dim).astype(np.float32)

# 训练用的样本（IVF 和 PQ 都需要）
n_train = 100_000
train = data[:n_train]

# 100 个查询
queries = np.random.randn(100, dim).astype(np.float32)

# === 基准：暴力扫描（精确）===
print("--- 1. IndexFlatL2 (暴力扫描，精确) ---")
flat = faiss.IndexFlatL2(dim)
flat.add(data)

t0 = time.time()
D_gt, I_gt = flat.search(queries, k=10)
flat_time = (time.time() - t0) / 100 * 1000
mem_mb = data.nbytes / 1024 / 1024
print(f"内存 {mem_mb:.0f} MB，延迟 {flat_time:.2f} ms / query")

IVF：把向量分桶，只搜部分桶

print("\n--- 2. IndexIVFFlat (IVF，分桶后桶内仍精确比较) ---")

# nlist = 簇的个数。经验值：sqrt(N) 到 16*sqrt(N)
# 这里 sqrt(1M) ≈ 1000，取 1024（faiss 对 2 的幂友好）
nlist = 1024

quantizer = faiss.IndexFlatL2(dim)             # 用于做 nlist 个簇中心的快速检索
ivf = faiss.IndexIVFFlat(quantizer, dim, nlist)

# 训练：用样本聚类得到 1024 个簇中心
t0 = time.time()
ivf.train(train)
print(f"训练耗时 {time.time()-t0:.1f}s")

# 把全部向量分配到簇里
t0 = time.time()
ivf.add(data)
print(f"添加耗时 {time.time()-t0:.1f}s")

# 试不同 nprobe 看 recall vs 延迟
for nprobe in [1, 4, 16, 64, 256]:
    ivf.nprobe = nprobe
    
    t0 = time.time()
    D, I = ivf.search(queries, k=10)
    qt = (time.time() - t0) / 100 * 1000
    
    # recall@10：IVF 返回的 10 个里有多少在精确 top10 里
    recall = np.mean([
        len(set(I[i]) & set(I_gt[i])) / 10
        for i in range(100)
    ])
    
    speedup = flat_time / qt
    pct_visited = nprobe / nlist * 100
    print(f"nprobe={nprobe:>3}（访问 {pct_visited:>5.1f}% 的簇）  "
          f"recall@10={recall:.3f}  延迟={qt:.2f}ms  比暴力快 {speedup:.0f}x")

典型输出：

nprobe=  1（访问   0.1% 的簇）  recall@10=0.071  延迟=0.21ms  比暴力快 195x
nprobe=  4（访问   0.4% 的簇）  recall@10=0.247  延迟=0.55ms  比暴力快  75x
nprobe= 16（访问   1.6% 的簇）  recall@10=0.683  延迟=1.85ms  比暴力快  22x
nprobe= 64（访问   6.2% 的簇）  recall@10=0.952  延迟=6.20ms  比暴力快   7x
nprobe=256（访问  25.0% 的簇）  recall@10=0.998  延迟=21.5ms  比暴力快   2x

关键观察：

• nprobe=1 速度最快但召回只有 7%——只看一个簇容易漏
• nprobe=64（访问 6% 的簇）召回已经 95%，是大多数业务的甜区
• nprobe 调到访问 25% 的簇时已经接近精确，但速度优势就小了

调优经验：nlist ≈ sqrt(N)，nprobe 从 sqrt(nlist) 开始试，按召回率需求加大。

PQ：把每条向量压缩成几个字节

print("\n--- 3. IndexPQ (PQ，全库暴力比较但向量被压缩) ---")

# 把 128 维向量拆成 16 个 8 维子向量，每个子空间用 256 (= 2^8) 个码字
M = 16    # 子向量个数
nbits = 8 # 每个子空间的码本大小用 2^nbits

pq = faiss.IndexPQ(dim, M, nbits)

t0 = time.time()
pq.train(train)
print(f"训练耗时 {time.time()-t0:.1f}s")

t0 = time.time()
pq.add(data)
print(f"添加耗时 {time.time()-t0:.1f}s")

# 压缩后的向量大小：每条 M*nbits/8 = 16 字节
# 原始：128*4 = 512 字节，压缩比 32x
compressed_mb = n_data * M / 1024 / 1024
print(f"压缩后向量内存 {compressed_mb:.1f} MB（原始 {mem_mb:.0f} MB，压缩 {mem_mb/compressed_mb:.0f}x）")

t0 = time.time()
D, I = pq.search(queries, k=10)
pq_time = (time.time() - t0) / 100 * 1000

recall = np.mean([len(set(I[i]) & set(I_gt[i])) / 10 for i in range(100)])
print(f"PQ(M={M},nbits={nbits})  recall@10={recall:.3f}  延迟={pq_time:.2f}ms")

典型输出：

压缩后向量内存 15.3 MB（原始 488 MB，压缩 32x）
PQ(M=16,nbits=8)  recall@10=0.412  延迟=12.50ms

PQ 的核心 trade-off：内存压缩 32 倍，但召回从 1.0 掉到 0.41——单独用 PQ 召回损失太大。所以 PQ 一般不单独用，要跟 IVF 组合。

IVF-PQ：经典组合，鱼和熊掌兼得（一部分）

print("\n--- 4. IndexIVFPQ (IVF + PQ 组合，主流大规模方案) ---")

nlist = 1024
M = 16
nbits = 8

quantizer = faiss.IndexFlatL2(dim)
ivfpq = faiss.IndexIVFPQ(quantizer, dim, nlist, M, nbits)

t0 = time.time()
ivfpq.train(train)
print(f"训练耗时 {time.time()-t0:.1f}s")

t0 = time.time()
ivfpq.add(data)
print(f"添加耗时 {time.time()-t0:.1f}s")

# 总内存：1024 个簇中心(每个 128*4=512 字节) + 100 万条 16 字节 PQ 编码
total_mb = (nlist * dim * 4 + n_data * M) / 1024 / 1024
print(f"总内存约 {total_mb:.1f} MB（原始 {mem_mb:.0f} MB）")

for nprobe in [16, 64, 256]:
    ivfpq.nprobe = nprobe
    t0 = time.time()
    D, I = ivfpq.search(queries, k=10)
    qt = (time.time() - t0) / 100 * 1000
    recall = np.mean([len(set(I[i]) & set(I_gt[i])) / 10 for i in range(100)])
    print(f"nprobe={nprobe:>3}  recall@10={recall:.3f}  延迟={qt:.2f}ms")

典型输出：

总内存约 16.0 MB（原始 488 MB）
nprobe= 16  recall@10=0.305  延迟=0.35ms
nprobe= 64  recall@10=0.425  延迟=1.20ms
nprobe=256  recall@10=0.500  延迟=4.50ms

注意：IVF-PQ 的召回上限是 PQ 的召回上限（因为压缩损失），单纯 IVF-PQ 在这个随机数据集上召回上不去。生产环境通常加上重排（rerank），把 PQ 阶段拿到的前 100~200 候选再用原始向量做精确比较，召回能拉回 90%+。

IVF-PQ + 重排：完整生产配置

print("\n--- 5. IndexIVFPQ + rerank (生产里最常见的组合) ---")

# 上面的 ivfpq 已经建好。设置 nprobe=64
ivfpq.nprobe = 64

# 让 FAISS 内部自动用原始向量重排
# 需要在 add 之前 ivfpq.make_direct_map()，这样能拿到原向量做重排
# 或者外部维护一份原向量做手动重排，我们演示后一种

# 多取一些候选，外部重排
k_search = 100   # 第一阶段：召回 100 个候选
k_final = 10     # 最终返回 10 个

t0 = time.time()
D, I = ivfpq.search(queries, k=k_search)

# 第二阶段：对每个 query 的 100 个候选，用原始向量重新计算精确距离
final_results = []
for q_idx in range(len(queries)):
    cand_ids = I[q_idx]
    cand_vecs = data[cand_ids]    # 取候选的原始向量
    
    # 精确距离
    exact_d = np.linalg.norm(cand_vecs - queries[q_idx], axis=1) ** 2
    
    # 按精确距离重新排序，取前 k_final
    rerank_order = np.argsort(exact_d)[:k_final]
    final_results.append(cand_ids[rerank_order])

rerank_time = (time.time() - t0) / 100 * 1000

recall = np.mean([
    len(set(final_results[i]) & set(I_gt[i])) / 10
    for i in range(100)
])
print(f"IVF-PQ(nprobe=64) + 取 100 候选用原向量重排  recall@10={recall:.3f}  延迟={rerank_time:.2f}ms")

典型输出：

recall@10=0.948  延迟=2.50ms

这就是大规模向量检索的标准范式：粗召回（IVF + PQ）+ 精排（原向量重算）。Milvus 的 IVF_PQ + metric_type 参数，Qdrant 的 quantization_config + rescore=true，本质都是这个流程的封装。

四种索引在 100 万条数据上的对比总表

训练索引本身也是一门学问

与 IndexFlat 这类“拿来就用”的结构不同，IVF 和 PQ 都需要训练。训练数据如果分布偏差很大，得到的聚类中心或码本质量就会下降，进而影响召回率与排序效果。因此，索引训练阶段最好使用足够有代表性的样本，而不是随手抽一小批非常局部的数据。

此外，向量分布变化也是一个现实问题。如果你切换了 embedding 模型，或者数据类型从客服问答扩展到代码与表格，原有的簇中心和 PQ 码本未必仍然合适。很多线上系统需要定期重建索引，或者至少监控召回质量是否随时间下滑。

不要把压缩误解为纯粹省钱

PQ 的直观收益确实是节省内存，但它的影响远不止账单。索引是否能常驻内存，决定了查询时要不要频繁访问磁盘；候选编码是否足够短，决定了 CPU cache 命中率和扫描速度；节点间要复制多少索引数据，也会影响构建和扩容时间。也就是说，压缩不仅是存储问题，也是性能问题和运维问题。

因此，在选型时不能只看“召回率掉了多少”。同样重要的是：在你可接受的延迟、硬件预算和数据规模下，系统是否终于变得能跑、跑得稳、扩得动。

本篇要点

• IVF 通过粗聚类把向量分桶，查询时只访问最接近的若干个簇，从而减少候选量。
• nprobe 是 IVF 中影响召回率与延迟的重要参数，访问簇越多通常召回越高、速度越慢。
• PQ 通过把向量拆成子空间并编码为短码字，大幅降低向量存储与比较成本。
• IVF-PQ 是经典组合：IVF 负责缩小范围，PQ 负责压缩候选表示，两者共同降低检索成本。
• 这类索引依赖训练数据质量，数据分布变化后往往需要重建或重新评估索引效果。

下一篇

前三篇已经把概念、ANN 和经典索引路线铺开了。下一篇开始进入实操：用 FAISS 在单机上分别构建 IndexFlatL2、IndexIVFFlat 和 IndexHNSW，把抽象概念落到可以运行的 Python 代码上。

参考资料

• FAISS Wiki: IVFADC and PQ
• Product Quantization for Nearest Neighbor Search
• FAISS Getting started