向量索引：HNSW、IVF 与量化
本文基于模型知识整理（生成时未联网核对），关键结论建议对照经典文献复核。
一句话定义
精确最近邻搜索在亿级向量上不可行，近似最近邻（ANN）索引用"允许极小概率漏掉真近邻"换取百倍千倍加速：HNSW 构建分层可导航小世界图、IVF 先聚类再局部搜索、PQ 把高维向量压缩成字节码——三者的组合与参数决定检索的速度、召回率与内存占用三角。
为什么重要
向量库的选型调参（M/efSearch/nprobe/内存预算）直接决定线上延迟与召回率。不理解索引原理，就只能"凭感觉调参数"；理解后，能按数据规模与延迟预算推导出合理配置，并解释为什么召回率上不去。
前置知识
kp-008（度量与索引绑定）。
核心概念
- ANN 权衡三角：召回率（recall@k）↔ 延迟 ↔ 内存。任何索引调参都是在这个三角里滑动。
- HNSW（分层可导航小世界图）：多层图结构，上层稀疏长边负责"高速公路"跳跃，下层稠密短边负责精细搜索；查询从顶层贪心下降到底层。参数：
M（每节点连边数，影响图密度与内存）、efConstruction（建图质量）、efSearch（查询时候选队列长度，直接换召回与延迟）。 - IVF（倒排文件索引）：先用 k-means 把全库聚成 nlist 个簇，查询只访问最近的 nprobe 个簇。参数：
nlist（簇数，经验 √N 量级）、nprobe（探测簇数）。 - PQ（乘积量化）：把向量切成 m 段、每段用 256 个质心编码成 1 字节，向量从 1536 维浮点（~6KB）压缩到几十字节；有量化误差，常与 IVF 组合（IVF-PQ）。
- 扁平索引（Flat/Brute force）：暴力全扫；百万级以内延迟可接受时，它是最准最简单的选择，别迷信"必须上 ANN"。
原理与机制
HNSW 为什么快：小世界图兼具"长边跳远"与"短边精搜"，查询复杂度近似 O(log N)；贪心搜索天然支持增量插入（新向量挂图即可），适合数据持续更新的 RAG 场景。代价是内存：图邻接表 + 原始向量都要常驻（每 1536 维向量 + M=32 边，内存是纯向量的 1.5–2 倍量级）。
IVF-PQ 为什么省内存：PQ 把 6KB/向量压到 ~48–96 字节（16–32 倍），亿级向量从 TB 级降到百 GB 级；代价是量化误差压低召回上限，需要过采样（取 top-k·rescore 精排）弥补。工程组合拳：IVF-PQ 粗筛 → 原始向量精排（rescore），内存与召回兼得。
召回率怎么验证：以 Flat 精确结果为基准，对比 ANN 的 recall@10；每次调参（efSearch、nprobe）都必须用同一评测集量化（kp-016 的评测纪律延伸到索引层）。
公式或模型
- 内存估算（粗略）：原始 FP32 = 4×dim 字节/向量；PQ(m) ≈ m 字节/向量。
- IVF 参数经验：nlist ≈ 4·√N ~ 16·√N；nprobe 从 1 起按召回目标上调。
- HNSW：M 取 16–48；efSearch ≥ k 且按 recall 目标调（2–10 倍 k 常见）。
直观类比
在万人体育场找人：Flat=挨个问（准但慢）；IVF=先按看台分区，只搜最可能的几个区；HNSW=认识几个"社交枢纽"（上层长边），先跳到目标附近的人群圈，再在圈内逐个问（下层短边）；PQ=把每个人的特征压缩成一张小卡片，凭卡片初筛再核对本人（rescore）。
实例或案例
- 100 万 × 768 维：Flat 内存 ~3GB，单机查询毫秒级——直接 Flat，无需 ANN。
- 1 亿 × 1536 维：Flat ~600GB 不可行；IVF-PQ（nlist=65536, m=32）内存 ~百 GB 内，配合 rescore 达到 0.95+ recall@10。
- RAG 常见规模（十万~千万级）：HNSW 是默认甜点；增量更新频繁时优于需全量重训的 IVF。
常见误区
- 误区一："召回率下降是嵌入模型不行"。先查索引参数——efSearch/nprobe 过低、数据量涨了没调参，是更常见的原因；用 Flat 基准量化定位。
- 误区二："PQ 压缩后直接用压缩距离排序"。量化误差会明显错排；必须 rescore（用原始/未压缩向量重排 top 候选）。
- 误区三："向量库选型只看 QPS"。要看增量写入模式（HNSW 友好 vs IVF 需再平衡）、过滤检索支持（kp-006 的 pre-filter 是否索引原生支持）、内存预算。
与其他知识点的关系
自测题
- HNSW 的 efSearch 调大意味着什么？
答：查询时候选队列更长、搜索更充分——召回率上升、延迟与计算成本上升；是运行时可调的核心旋钮。
- IVF-PQ 为什么要 rescore？
答：PQ 距离有量化误差，直接排序会错排；用原始向量对粗筛候选重算精确距离，恢复排序质量。
- 什么情况下应该直接用 Flat 暴力检索？
答：数据量在百万级以内、延迟预算宽松时——零召回损失、零调参、实现最简单，避免过度设计。
延伸阅读
- Malkov & Yashunin, "Efficient and robust approximate nearest neighbor search using HNSW graphs"（TPAMI 2018）。
- Jégou 等, "Product Quantization for Nearest Neighbor Search"（TPAMI 2011）。
- ann-benchmarks（ANN 算法横向基准）与 faiss wiki 调参指南。