参考：近似最近邻索引

它是什么

Embedding 把文本、图像和用户变成向量（例如 768 个数），相似的条目彼此靠近。最近邻搜索找出与查询向量最近的那些向量。精确搜索要把查询与每个存储的向量比较，每次查询是 O(N × d)：对十亿个 768 维向量，那是几秒的计算量，并且要读取约 3 TB 的数据。近似最近邻（ANN） 索引放弃一点点召回率（找到的真实最近邻所占的比例），换来少几个数量级的工作量。

Important

核心要点： 三个家族，同一个取舍。HNSW（分层图）在内存索引、支持实时插入时，给出最好的召回率和延迟，代价是内存开销高。IVF（聚类）简单，内存开销低。乘积量化（product quantization） 把向量压缩 8 到 16 倍，使超大语料得以装下，代价是召回率。按哪种资源是约束来选：延迟、内存，还是更新速率。

何时需要它

语义搜索、检索增强生成、推荐召回和去重，都建立在向量索引之上。面试问题不是”说出 HNSW”，而是”你什么时候会选别的，它的代价是什么？”

Note

面试信号： 信号不是”HNSW 优于 IVF”，而是推理每一种在什么时候占优：当内存负担得起时，HNSW 在召回率和延迟上占优；当内存是约束时，IVF 加乘积量化占优。选了 HNSW 却没说出它的内存账单（十亿个 768 维向量大约 4.5 TB），是用错误的理由选对了答案。

各个家族

索引	工作方式	优势	弱点
IVF（倒排文件）	把向量聚类（k-means）成 K 个单元；查询时只搜索最近的 `nprobe` 个单元	简单；内存开销低；适合批处理负载	召回率依赖 `nprobe` 的调参；实时插入很别扭（放进哪个簇？）；簇不均衡
HNSW（分层可导航小世界）	一个多层图；每个向量连到它的近似最近邻；查询贪心地在图上行走	实践中最好的召回率和延迟；天然支持实时插入；不需要聚类步骤	内存高（图的边与向量一起存储）；图必须放在 RAM 里；构建时间 O(N log N)
乘积量化（PQ、ScaNN）	把每个向量压缩成一个短码；在压缩空间中搜索；用完整向量对前几名候选重排	内存少 8 到 16 倍；支持基于磁盘的索引	召回率随压缩而下降；需要调参；在高召回率下不如 HNSW

HNSW 搜索是怎么工作的

HNSW 是一个多层的、应用于图的跳表（skip list）类比。

构建。 每个插入的向量得到一个随机的最高层（越高的层指数级地越稀有，就像跳表）。在它加入的每一层里，它连接到该层中它的 M 个近似最近邻。最顶层的节点很少；最底层有全部节点。
搜索。 从最顶层中一个固定的入口点出发。在每一层，贪心地跳到离查询最近的邻居。当没有邻居能改进时，下降到下一层，那里有更多节点和更细的邻域。在最底层，保留一个优先队列，存放见过的 ef_search 个最佳候选，并返回前 k 个。
为什么有效。 上层是长距离的高速公路（粗粒度导航）；下层是局部搜索。行走大约需要 O(log N) 跳来到达正确的邻域，然后在 ef_search 个候选上做局部搜索来换取召回率。

算例。 十亿个向量、5 层：最顶层大约有 100 个节点。查询从那里进入，跳 2 到 3 次，下降到第 4 层（约 10,000 个节点），细化，然后一路下降；在最底层它探索 ef_search = 128 个候选。总共大约 500 到 1,000 次距离计算，而暴力搜索是十亿次。

参数，以及各自权衡的东西：

参数	含义	典型值	调大它
`M`	每个节点的连接数	16	召回率更好，内存更多
`ef_construction`	构建时的 beam 宽度	200	图更好，构建更慢
`ef_search`	查询时的 beam 宽度	调到满足召回目标	召回率更好，延迟更高

一个常见的目标是”召回率 95%（recall@10），延迟在 50 ms 以内”，而 ef_search 就是你为达到它而调的旋钮。

实时插入。 用同样的贪心搜索计算新向量在每一层的邻居并连上它。这需要对邻居的列表做细粒度的锁（或 compare-and-swap），并且是为并发的读写而设计的。IVF 没法这么优雅地做到。

内存算术

原始大小 = N × d × 每个值的字节数。十亿个 768 维的 float32 向量，是 10⁹ × 768 × 4 字节 ≈ 3 TB。HNSW 的图开销（在 M = 16 时约 1.5 倍）使它达到约 4.5 TB，约每个向量 4.5 KB。每个节点有 256 GB 可用内存，大约是每个节点 5,700 万个向量，所以至少约 18 个分片，并且为了满足 50 ms 的延迟目标，索引必须留在内存里。如果这太贵，压缩（PQ）会把内存降低 8 到 16 倍，代价是召回率；或者用基于磁盘的索引，用延迟换容量。

过滤

真实的查询会把相似度与属性结合起来（“这个租户在这个类别下最近的商品”）。两种做法：

后过滤（post-filter）： 先搜 top K，再丢掉不匹配的结果。如果 90% 的向量通不过过滤，你就必须取回远多于 K 的候选，召回率会崩溃。
在索引内过滤： 在图遍历期间或在一个预先过滤的子集上应用谓词，使搜索只针对匹配的向量。

Warning

生产实践： 过滤必须在索引里。 “先搜索再过滤”在演示里看起来没问题，但对高选择性的过滤会在规模下毁掉召回率。另外，预期在许多删除之后要定期重建或 compact HNSW，因为已删除的节点在被移除之前仍作为图的路标留着。

分片与复制

在十亿级向量时索引要分片。按向量集合的分区来分片（按 id 或按租户）：把查询发给每个分片，各自返回本地的 top K 和分数，由一个协调者合并，这与搜索索引的 scatter-gather 相同。为每个分片做复制，以保证可用性和吞吐。混合搜索把向量分数与关键词分数做加权组合，因为关键词能抓住 embedding 模糊掉的精确词项。

如何选择

约束	选择	原因
低延迟下的高召回率，内存负担得起，要实时插入	HNSW	最好的召回率与延迟的取舍
内存是约束	IVF 加乘积量化	压缩 8 到 16 倍
主要是批处理、静态数据	IVF	简单
磁盘上的巨大语料	基于磁盘的 PQ 索引	容量优先于延迟
带过滤的查询	支持过滤的索引，不要只靠后过滤	保住召回率
小数据集（不到约一百万）	精确搜索，可以用 GPU	索引可能不值得

Caution

常见错误： 在一个设置下报告召回率，然后把它当作”那个”召回率。召回率是一个旋钮：ef_search 或 nprobe 用它来换延迟。要说明目标（某个延迟下的 recall@10），并用你自己的数据和过滤条件去测量。