IVFFlat 与 HNSW 算法原理与对比

一、核心概念与适用场景

• IVFFlat（Inverted File with Flat）
  • 基于K-means 聚类将向量空间划分为多个簇（列表/桶），为每个簇维护倒排列表；查询时先找最近的若干簇，再在簇内做暴力精确距离计算（Flat 表示不压缩）。适合对召回精度较高、内存较充足、数据相对静态的场景。其优点是索引结构简单、可解释，缺点是需要训练、对数据分布变化敏感、频繁更新后可能需要重建索引。典型应用包括高精图像对比、需要可控召回的业务。
• HNSW（Hierarchical Navigable Small World）
  • 基于多层小世界图的近似最近邻搜索：顶层稀疏用于快速导航，底层稠密用于精检；查询从顶层入口点逐层下降，在底层通过贪婪/受限搜索找 Top-K。优点是高召回、低延迟、对高维向量和大规模数据更稳健；缺点是构建更慢、内存占用更高（需存储图连接）。常用于RAG、语义搜索、推荐系统等对召回与时延都敏感的场景。

二、算法原理

• IVFFlat
  • 训练阶段：对全量或采样数据做K-means，得到nlist 个质心；构建倒排列表将向量按最近质心分组。
  • 查询阶段：计算查询与所有质心的距离，选择最近的nprobe 个簇，在这些簇的倒排列表内做精确距离计算并归并取 Top-K。
  • 关键理解：通过'粗筛（质心）+ 精检（桶内暴力）'减少计算；若查询靠近簇边界，需增大nprobe提升召回。
• HNSW
  • 构图阶段：为每个向量随机确定最大层 l，自顶向下逐层插入；每层以ef_construction为宽度做近邻搜索，与M个最近且多样化的邻居建立双向连接，形成小世界图。
  • 查询阶段：从顶层入口点开始，逐层下降，在底层以ef_search为宽度做受限搜索，维护候选动态列表，最终返回Top-K。
  • 关键理解：多层结构提供'高速公路'式导航，底层精细搜索保证高召回；M与ef_construction控制图质量与构建成本，ef_search控制查询质量与延迟。

三、关键参数与调优要点

• IVFFlat 常用参数
  • lists（nlist）：聚类中心数。经验值：数据量**< 100 万时取rows/1000**，> 100 万时取sqrt(rows)；lists 越大，簇越小，查询更快但训练更慢、召回可能下降。
  • probes（nprobe）：查询时探测的簇数。经验值：从lists 的 1%–10%起步，或取sqrt(lists)；probes 越大，召回越高、延迟越大。