倒排文件索引

1. 要解决什么问题

在向量检索（比如用 embedding 做相似性搜索）中，最朴素的做法是暴力搜索（Brute-force / Flat）：把查询向量和库中每一个向量做距离计算，取 Top-K。时间复杂度 O(N×D)，N 是向量总数，D 是维度。当 N 达到百万、亿级时，暴力搜索不可接受。

近似最近邻搜索（ANN） 的思路是：牺牲一点精度，换来数量级的加速。IVF（Inverted File Index）就是最经典、最常用的 ANN 方法之一。

2. 核心思想：先聚类，再搜索

IVF 分为两个阶段：

1
2
3
4
5
6
7
8
9


训练阶段（Indexing）：
  1. 用 K-means 对所有向量聚成 nlist 个类
  2. 每个类有一个质心（centroid）
  3. 建立倒排列表：每个质心 → 属于该类的所有向量

搜索阶段（Searching）：
  1. 对查询向量 q，找到离它最近的 nprobe 个质心
  2. 只在这些质心对应的倒排列表中搜索
  3. 返回全局 Top-K

关键参数：

nlist：聚类数量。越大，每个桶越小，但质心越多。
nprobe：搜索时探访的聚类数。越大，精度越高但速度越慢。

3. 理解 nprobe：搜索时探访多少个桶

nprobe 是 IVF 搜索阶段最重要的参数，它在精度和速度之间做权衡。

直观理解

训练阶段 K-means 把空间切成了 nlist 个桶：

1
2
3
4


所有数据点被分配到 nlist 个桶中
       ┌────┬────┬────┬────┬────┬────┬────┐
       │桶0 │桶1 │桶2 │桶3 │桶4 │桶5 │... │
       └────┴────┴────┴────┴────┴────┴────┘

搜索时，查询 q 先和所有 nlist 个质心算距离，按距离从小到大排序。nprobe 决定只取前多少个桶来搜：

1
2
3
4


离 q 最近的质心排序： 桶33(最近), 桶78, 桶12, 桶401, ...
                     ├───── nprobe=1 ─────┤
                     ├───── nprobe=3 ────────────┤
                     ├───── nprobe=10 ─────────────────────────┤

只搜这些桶里的向量，其他桶完全不碰。

三个基准值

nprobe	行为	速度	精度
1	只搜最近的 1 个桶	最快	可能很低（30-60%），见边界问题
nlist/10 左右	经验常用值，如 nlist=1000, nprobe=10	比暴力快 50-100x	通常 90-98%
nlist	搜全部桶 = 退化为暴力搜索	最慢	100%

关键性质

nprobe 是搜索时参数，建好索引后可以随时调整，不需要重新训练。 这意味着你可以先建索引，上线后根据实际场景灵活配置。

1
2
3
4


调优流程：
  1. 固定 nlist（决定索引结构）
  2. nprobe 从 1 开始增大
  3. 观察召回率曲线，在拐点附近选择一个值

典型拐点：在 nprobe=10-20 附近，召回率增长曲线从陡峭变得平缓，此时继续增大 nprobe 对精度帮助很小，但搜索时间线性增长。

4. 训练过程详解

Step 1: K-means 聚类

输入：N 个 D 维向量
输出：nlist 个质心（centroids），形状为 (nlist, D)
通常用 K-means++ 初始化，迭代直到收敛

Step 2: 建立倒排列表

1
2
3
4
5
6


index = {
  centroid_0: [vec_id_3, vec_id_7, vec_id_15, ...],
  centroid_1: [vec_id_1, vec_id_9, ...],
  ...
  centroid_{nlist-1}: [...]
}

每个向量被分配到离它最近的质心。

直观理解： IVF 把向量空间划分成 nlist 个 Voronoi cell，每个 cell 对应一个质心。

5. 搜索过程详解

1
2
3
4


1. 计算 q 到所有 nlist 个质心的距离
2. 选出距离最近的 nprobe 个质心
3. 收集这些质心对应的所有向量
4. 在这些向量中做暴力搜索，返回 Top-K

如果 nprobe = nlist，退化为全量暴力搜索（精度最高，速度最慢）。如果 nprobe = 1，只搜最近的那个桶（速度最快，精度最低）。

6. 与暴力搜索的对比

指标	暴力搜索 (Flat)	IVF
时间复杂度	O(N×D)	O(nlist×D + (N/nlist)×nprobe×D)
精度	100% (精确)	≈90-99% (近似)
内存	原始向量	原始向量 + 质心 + 倒排表
适用规模	≤10⁵	10⁵~10⁹

以 N=1,000,000, nlist=1000, nprobe=10 为例：

暴力搜索：计算 1,000,000 次距离
IVF：先算 1000 次（质心），再算约 10,000 次（每个桶约 1000 个向量，探访 10 个桶）
加速比约 100x，精度通常仍有 95%+

7. 内存消耗分析

IVF 本身不压缩向量，所以内存开销 = 原始向量 + 质心 + 倒排表。

原始向量：N × D × 4 字节（float32）
质心：nlist × D × 4 字节（float32）
倒排表：N × 4 字节（每个向量的 ID）

当 N=10⁸, D=768 时，仅原始向量就需要约 300GB 内存。

这正是 IVF 的瓶颈： 虽然搜索加速了，但内存没有减少。解决方案是与**乘积量化（PQ）**配合使用（IVF+PQ，即 Faiss 中的 IVFPQ），对残差做量化压缩。

8. 边界问题 — IVF 的固有精度瓶颈

问题本质

IVF 的搜索策略隐含一个假设：如果数据点 x 是查询 q 的最近邻，那么 x 所属的质心一定离 q 也很近。

这个假设在边界附近不成立。

假设K-means 的聚类结果将空间划分成若干 Voronoi cell——每个 cell 是到对应质心距离最近的所有点的集合，cell 之间的分界线是相邻两个质心的垂直平分线。

当查询点 q 靠近边界时，问题就出现了：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14



      C1 的 Voronoi cell     C2 的 Voronoi cell
      ┌──────────────────┼──────────────────┐
      │                  │                  │
      │                  │                  │
      │        C1●       │       ●C2        │
      │                  │                  │
      │                  │    x             │  ← 数据点 x（属于 C2）
      │                  │    ·             │
      │           q      │                  │
      │           ·      │                  │
      └──────────────────┼──────────────────┘

                    边界（垂直平分线）

查询点 q 离 C1 的质心更近 → 只搜 C1 的桶（nprobe=1）
但离 q 最近的数据点 x 属于 C2，因为它在边界的另一侧
C2 从未被探访，x 必然被漏掉

即使 nprobe=2 能覆盖两个桶，如果边界附近有多个质心交错，仍可能漏掉真正的最近邻——只是概率降低了。

量化影响

nprobe=1 的极端情况下，召回率可能只有 30-60%，取决于数据分布。随着 nprobe 增大，召回率曲线呈对数增长——前几个桶贡献最大，后面收益递减。

缓解手段

手段	原理	代价
增大 nprobe	覆盖更多边界区域	线性增加搜索时间
多分配（multi-assignment）	训练时把一个向量分配到最近的多个质心	增加存储和搜索范围
IVF + 重排	先用 IVF 粗筛出 Top-K×倍数，再用原始向量精确重排	多一次重排开销，需保留原始向量

重排是最实用的方案：比如 k=10 时 IVF 先取 k×倍数=100 个候选，再用原始向量算一遍距离精确排序，可以在几乎不损失速度的前提下把召回率从 85% 提升到 98%+。

9. 残差向量 — IVF+PQ 的数学基础

定义

残差 = 原始向量 - 所属质心

1

residual = vector - centroids[label]

为什么重要

原始向量在空间中散乱分布。减去质心后，残差向量的分布集中在零点附近，幅值显著减小。这种集中性使得**乘积量化（PQ）**对残差的编码效率远高于对原始向量的编码。

1
2
3
4
5
6
7


原始向量分布：                        残差向量分布：
    ·     ·                          · · ·
  ·   ·   ·    ·                    ········  
·  ·  ·  ·  ·  ·  ·                 ·········
   ·  ·   ·                          ·····
                                       ···
    （分散）                          （集中在零点）

IVF+PQ 的完整链路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


训练：
  1. K-means 聚类 → nlist 个质心
  2. 对每个向量：残差 = 向量 - 最近的质心
  3. 对残差做 PQ → 存储 PQ 编码（而不是原始向量）

搜索：
  1. 计算 q 到所有质心的距离 → 选 nprobe 个桶
  2. 对每个选中的桶：
     a. 计算 q 到该质心的残差：q - centroid
     b. 用 PQ 的查找表（LUT）快速估算距离
  3. 合并结果，取 Top-K

为什么残差让 PQ 更有效

PQ 的原理是把 D 维空间分成 M 个子空间，每个子空间用 k_sub 个码字编码。如果向量的幅值大、分布散，每个子空间需要更多码字来覆盖同样大的范围。残差集中在零点附近，同样的码字数量下量化误差更小——这意味着可以用更少的码字达到同样的精度，或者同码字数量下精度更高。

压缩收益

方案	单向量存储	N=10⁸, D=768
原始向量 (float32)	3072 字节	~300 GB
IVF (同上)	3072 字节	~300 GB
IVF+PQ (M=64, 每子空间 8 位)	64 字节	~6.4 GB

压缩比约 48x，使全内存索引成为可能。代价是 PQ 量化引入的额外精度损失通常为 1-3%。

10. 自适应 nprobe — 告别一刀切

固定 nprobe 的问题

不同查询的"难度"不同：

简单查询：离一个质心极近，其他质心很远 → nprobe=1 就够
困难查询：落在多个质心的边界附近 → 需要 nprobe=16 甚至更高

固定 nprobe 要么浪费计算（在简单查询上探访过多桶），要么损失精度（在困难查询上探访不够）。

方法一：基于距离比（最常用）

1
2
3
4
5
6
7


dists_to_centroids = sorted([d0, d1, d2, ..., d_{nlist-1}])
ratio = dists[0] / dists[1]  # 最近 / 次近

if ratio < threshold:    # d0 和 d1 接近 → 边界附近，多探访
    nprobe = large
else:                    # d0 明显更小 → 安全，少探访
    nprobe = small

直观含义：最近质心和次近质心的距离差距越小，q 越可能在边界上。

方法二：基于候选集质量（更鲁棒）

先以小的 nprobe 做一轮搜索，看 Top-K 候选的距离分布：

1
2


如果 top1 ~ topK 的距离没有明显断层 → 候选不稳定，增大 nprobe 再搜
如果 top1 << topK                   → 结果置信度高，停止

这其实是一种迭代加深策略，类似 IDDFS。

方法三：查询感知的历史统计

记录每个质心被选中的历史命中率（该桶中的向量有多少次出现在最终 Top-K 中）。搜索时，优先探访历史命中率高的桶，而不是一味按质心距离排序。但这种方法需要维护统计信息，且在面对分布偏移时可能劣化。

实际效果

好的自适应策略可以在保持精度的同时减少 30-50% 的搜索时间。距离比法实现成本最低，是实际中最常用的方案。

在 Faiss 中的使用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


import faiss

index = faiss.index_factory("IVF100,Flat")
index.train(vectors)
index.add(vectors)

# Faiss 支持在搜索时动态调整 nprobe
index.nprobe = 10
index.search(query, k)

# 不同查询可以用不同的 SearchParameters
params = faiss.SearchParameters(nprobe=5)
index.search(query, k, params=params)

注意 Faiss 本身不内置自适应 nprobe 逻辑，需要自己在外层实现距离比判断，然后为不同查询传入不同的 nprobe。

11. 一个简化的 Python 实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


import numpy as np
from sklearn.cluster import KMeans

class IVF:
    def __init__(self, nlist=100, nprobe=10):
        self.nlist = nlist
        self.nprobe = nprobe
        self.kmeans = None
        self.inverted_lists = {}
        self.vectors = None

    def train(self, vectors):
        """训练 IVF 索引"""
        self.vectors = vectors
        self.kmeans = KMeans(n_clusters=self.nlist, random_state=0)
        labels = self.kmeans.fit_predict(vectors)

        self.inverted_lists = {i: [] for i in range(self.nlist)}
        for vec_id, label in enumerate(labels):
            self.inverted_lists[label].append((vec_id, vectors[vec_id]))

    def search(self, query, k=10):
        """搜索 Top-K 近似最近邻"""
        dists_to_centroids = np.linalg.norm(
            self.kmeans.cluster_centers_ - query, axis=1
        )
        nearest_centroids = np.argsort(dists_to_centroids)[:self.nprobe]

        candidates = []
        for cid in nearest_centroids:
            candidates.extend(self.inverted_lists[cid])

        if not candidates:
            return [], []

        cand_ids, cand_vecs = zip(*candidates)
        cand_vecs = np.array(cand_vecs)
        dists = np.linalg.norm(cand_vecs - query, axis=1)
        topk_indices = np.argsort(dists)[:k]

        return [cand_ids[i] for i in topk_indices], dists[topk_indices]

注意事项： 仅用于教学理解，生产环境应使用 Faiss 等优化库（C++ 实现、SIMD 加速、多线程、GPU 支持）。

12. 常见问题

Q: nlist 和 nprobe 怎么选？

nlist ≈ 4√N 是一个经验值（也有 √N 的说法）
nprobe 从 1 开始调大，直到精度满足需求

Q: IVF 适合我的场景吗？

数据量大（>10⁵）且可以接受少量精度损失 → 适合
要求 100% 召回 → 不适合，应该用 Flat
内存受限 → 单独 IVF 不够，需要 IVF+PQ

Q: K-means 的训练开销？

K-means 复杂度 O(N×D×nlist×niter)，是建索引的主要成本
好在训练是离线一次性的
Faiss 实现了更快的 K-means（使用 IVF 本身加速 K-means 的训练）

13. IVF vs 其他 ANN 方法

方法	特点	适合场景
IVF	简单、高效、内存高	通用场景，配合 PQ 更佳
HNSW	图结构，精度高，内存极高	小到中等规模，精度敏感
PQ	向量压缩，精度损失	内存极度受限
IVF+PQ	速度 + 压缩，最均衡	大规模生产场景
NSW	HNSW 的前身	了解 HNSW 的必经之路