向量检索与 ANN 算法深入
「HNSW 的原理是什么？」「为什么用近似最近邻而不是精确检索？」——向量检索的数学与算法细节是 RAG / 搜索方向的硬核考点。本文深入相似度度量、ANN 索引（HNSW/IVF/PQ）与工程权衡。选型概览见 Embedding 与向量库。
一、问题定义
向量检索要解决的核心问题：给定一个 query 向量，在海量（百万~十亿级）向量中，快速找到最相似的 Top-K 个。
精确检索（暴力遍历，brute-force）要和每个向量都算一次相似度，复杂度 O(N·d)，在大规模下太慢。于是用 ANN（Approximate Nearest Neighbor，近似最近邻）——牺牲极小的精度（可能漏掉个别真正最近的），换取数量级的速度提升。
二、相似度度量
| 度量 | 公式直觉 | 特点 |
|---|---|---|
| 余弦相似度 | 向量夹角的 cos | 只看方向，与长度无关，最常用 |
| 点积（内积） | Σ aᵢbᵢ | 受方向和模长共同影响 |
| 欧氏距离 L2 | 两点直线距离 | 看绝对距离 |
关键：当向量归一化（单位长度）后，余弦相似度 = 点积，且与 L2 距离单调相关，三者检索结果一致。多数文本 Embedding 输出已归一化。
三、主流 ANN 索引
3.1 HNSW（分层可导航小世界图）★
思想：构建一个多层图。上层稀疏（长边，用于快速「跳远」），下层稠密（短边，用于精细搜索）。类似跳表（skip list）的多层结构。
查询过程：从顶层的入口点出发，贪心地向距离 query 更近的邻居移动；在本层走到局部最优后下沉到下一层继续，直到最底层得到 Top-K。
上层(稀疏长边) ●───────────● ← 快速跳到大致区域
│ │
中层 ●──●────●───● ← 逐步逼近
│ │ │ │
底层(稠密短边) ●●●●●●●●●●●●●● ← 精细定位 Top-K- 优点：查询快（平均近 O(log N)）、召回率高，是目前最主流的索引。
- 缺点：内存占用大（要存图结构/边）、构建较慢、增量更新成本高。
3.2 IVF（倒排文件索引）
思想：先用聚类（k-means）把所有向量分成 nlist 个「桶（簇）」。查询时只搜索离 query 最近的 nprobe 个桶，而非全部。
- 优点：省内存、构建快。
- 缺点：需训练聚类中心；nprobe 小则快但可能漏（桶边界问题），是「速度 vs 召回」的旋钮。
3.3 PQ（乘积量化）
思想：把高维向量切成若干段，每段用聚类量化成一个码字（codebook ID），从而把向量极度压缩。
- 优点：大幅省内存（一个向量可压到几十字节），适合超大规模。
- 缺点：有损压缩，精度下降；常与 IVF 组合成 IVF-PQ（先粗筛桶、再用 PQ 压缩距离计算）用于十亿级场景。
索引选型
| 需求 | 选择 |
|---|---|
| 高召回 + 低延迟，内存充足 | HNSW |
| 省内存、超大规模（亿级+） | IVF-PQ |
| 中小规模、要简单 | Flat（暴力）或 HNSW |
四、工程权衡
向量检索本质是在召回率、延迟、内存、构建/更新成本之间权衡：
- 召回率 vs 速度：HNSW 的
ef、IVF 的nprobe越大越准但越慢。 - 内存 vs 精度：PQ 压缩省内存但掉精度。
- 更新：HNSW 增量插入可以但删除/重建成本高；大规模常定期离线重建。
- 过滤 + 向量（混合）：先按元数据过滤再向量检索，或反之，影响性能与召回。
五、高频追问
Q：为什么用 ANN 而不是精确检索？ 精确检索要和每个向量都算相似度，O(N·d)，在百万/十亿级太慢。ANN 牺牲极小精度（可能漏个别最近邻）换取数量级提速，且召回率通常可调到很高，性价比远超精确检索。
Q：HNSW 为什么又快又准？ 它把向量组织成多层可导航小世界图：上层稀疏长边快速跳到目标区域，下层稠密短边精细定位，贪心搜索 + 逐层下沉，平均复杂度近 O(log N) 且召回率高。代价是图结构占内存大、构建慢。
Q：HNSW 和 IVF 怎么选？ 追求高召回 + 低延迟且内存够 → HNSW；要省内存、超大规模 → IVF（或 IVF-PQ）。HNSW 内存换性能，IVF 内存友好但需调 nprobe 平衡召回。
Q：PQ（乘积量化）是干嘛的？ 把向量切段后各段量化成码字，极度压缩存储（一个向量几十字节），适合十亿级。代价是有损、精度降。常与 IVF 组合成 IVF-PQ。
Q：余弦相似度、点积、L2 怎么选？ 文本 Embedding 通常归一化，此时三者等价、选哪个结果一致。未归一化时：只看语义方向用余弦；模长有意义（如某些推荐场景）用点积；看绝对距离用 L2。
Q：向量维度越高越好吗？ 不是。维度高语义更细，但存储、内存、检索成本都升，还有「维度灾难」。很多场景 768/1024 维已够，部分模型支持 MRL（套娃表示）按需截断维度。
Q：增删向量后索引怎么办？ HNSW 支持增量插入，但删除是「标记删除」、长期会退化，需定期重建；IVF 新增需考虑是否重训聚类中心。大规模生产常用「在线增量 + 定期离线重建」结合。