一句话定义
IVF（Inverted File，倒排文件）用 k-means 把向量空间切成 nlist 个分区（Voronoi 单元），查询时只在与查询向量最近的 nprobe 个分区内做距离计算——"先粗定位、再细扫描"的分区剪枝思想，也是 PQ 组合（IVFADC）的经典载体。
为什么重要
IVF 是最古老、最普及的 ANN 工业结构：FAISS、Milvus、pgvector(ivfflat)、Elasticsearch 内核里都有它。它是理解"分区索引"这一大类的最小样本，其两个参数 nlist/nprobe 的调法，是所有向量索引参数分析的方法论样板。与 PQ 组合后（IVF-PQ），它是十亿级向量内存检索的经典解。
前置知识
kp-006（Flat 基线）；k-means 的基本概念（本篇内讲清使用方式）。
核心概念
- nlist：分区（质心）个数，建库时确定，改动需重建索引。
- 倒排表（inverted list）：每个质心下挂"落入该分区的所有向量"的列表。
- nprobe：查询时探查的分区数，在线可调，召回-延迟的直接旋钮。
- 残差（residual）：IVFADC 中存储"向量减去所在分区质心"的差值，让后续 PQ 在更小的动态范围内编码。
- 训练集代表性：质心质量取决于训练样本覆盖度，FAISS 经验训练点数至少为 nlist 的 30~50 倍。
原理与机制
建库：对全部向量跑 k-means 得 nlist 个质心；每个向量归入最近质心的倒排表。查询：先算 q 与 nlist 个质心的距离（很便宜，只有 nlist 个 d 维计算），取最近的 nprobe 个分区；只在这些分区内做暴力距离，合并 top-k。
剪枝收益来自两点：质心距离计算是 O(nlist·d)，远小于 O(N·d)；分区内只需扫 N/nprobe 量级的向量。总体扫描量约为 N × nprobe/nlist。
参数影响分析（本库要求的样板格式）：
| 参数 | 增大 → 召回 | 增大 → 延迟 | 改动成本 | 经验区间 |
|---|---|---|---|---|
| nlist | 先升后降（过大则每区过小、边界误差升） | 建库显著变慢；查询质心阶段微增 | 需重建 | 约 √N 到 4√N，数千至数万 |
| nprobe | 单调升 | 单调升 | 无需重建，在线可调 | 从 1 起，常取 nlist 的 1%~10% |
质心边界问题：最近邻可能恰落在"第二近质心"的分区里，nprobe=1 时必然漏——这是 IVF 召回上限的结构性来源，只能靠加大 nprobe 缓解。
公式或模型
单查询扫描量 ≈ nlist·d (质心) + (N/nlist)·nprobe·d (分区内)
压缩收益(IVF-PQ): 每向量存储 m 字节(见 kp-012)图示
质心 c1 质心 c2 质心 c3
● ● ●
╱ | ╲ ╱ | ╲ ╱ | ╲
· · · · · · · · ·
倒排表1 倒排表2 倒排表3
查询 q ● ──► 距 c1、c2 最近 ──► 只扫表1+表2 (nprobe=2), 跳过表3实例或案例
1000 万条 128 维向量：取 nlist = 4096（约 16√N），倒排表平均 2440 条；nprobe=16 时每查询扫描约 3.9 万向量，延迟较全扫降约 250 倍，召回 90%+；nprobe=64 时召回升至 98%，延迟升约 4 倍。pgvector 中同一套逻辑名为 lists / probes 参数（见 kp-020）。
直观类比
IVF 是"快递分拣"：全国地址先按大区分拣中心（质心）归类，查一个包裹只翻两三个大区的货架（nprobe），不必翻全国货架。分拣中心太少（nlist 小）每区太挤，太多（nlist 大）跨区错件变多。
常见误区
- "nlist 越大越准"——过大后每个分区向量过少、边界点占比升高，召回反而下降且建库训练困难。
- "nprobe 调到等于 nlist 就是最优"——那时等价于全扫，不如直接用 Flat 或换图索引。
- "质心一劳永逸"——数据分布漂移（新业务、新语种）后质心失配，召回悄悄下滑；应定期用 ground truth 抽检，必要时重训分区。
自测题
- N=400 万，nlist 取多少作为起点？
- 为什么 IVF 常与 PQ 搭配而不是单独用？
- nprobe 从 8 提到 32，召回与延迟如何变化？
答：按 √N ≈ 2000 到 4√N ≈ 8000 区间，取如 4096；训练样本至少 4096×30 ≈ 12 万条且有代表性。
答：IVF 只减扫描条数，每条仍存原始向量；PQ 把每条压成几十字节，两者组合（IVFADC）才同时解决"扫多少"与"每条多重"。
答：召回单调上升（覆盖更多近邻分区），延迟约按扫描量近似线性上升；是否值得由 recall-延迟曲线与业务预算决定。
与其他知识点的关系
kp-012 的 PQ 提供每向量的压缩表示，IVF 负责剪枝、PQ 负责压缩，合为 IVFADC；kp-020 展示 IVF 参数在 pgvector 中的对应物；kp-008 是"图路线"对"分区路线"的替代答案。
延伸阅读
Jégou, Douze, Schmid, "Product Quantization for Nearest Neighbor Search"（IEEE TPAMI 2011）——IVFADC 结构与残差编码的原始出处。