近似最近邻ANN算法

从最直接的方法开始：把每条向量都算一遍

最近邻搜索的定义非常简单。给定一个查询向量，再给定库中一批已存向量，计算查询与每个向量的距离，然后选出最近的前 k 条。这种方法通常被称为暴力扫描暴力扫描暴力扫描指不借助任何索引结构，直接对查询向量与库中所有向量逐一计算距离，再选出最接近的若干个结果。它的优点是实现简单且结果精确，缺点是在数据量增长后延迟和算力成本线性上升。 。

如果你的集合里只有一万条向量，维度是 384，那么暴力扫描未必是坏事。CPU 做一次矩阵乘法就能把结果算出来，代码简单、结果稳定、没有索引构建和维护负担。很多原型系统一开始都这样做，因为它足够直观。

问题在于规模。假设你有一千万条 768 维向量，每次查询都要与这全部一千万条做距离计算。即使底层做了 SIMD 优化或 GPU 加速，计算量依然很可观。更重要的是，这种方法的成本随着数据量几乎线性增长。查询翻十倍，延迟和资源消耗通常也要显著上升。这种增长趋势决定了它不可能成为大规模在线检索系统的长期方案。

精确搜索为什么会越来越贵

向量检索的麻烦之处，在于它面对的是高维空间high-dimensional spacehigh-dimensional spaceHigh-dimensional space means the vectors have hundreds or thousands of dimensions. Many indexing tricks that work well in low-dimensional geometry degrade badly here, a phenomenon often discussed as the curse of dimensionality. 。在低维几何里，许多空间划分方法都很有效；到了几百维甚至上千维，原本熟悉的直觉开始失效。很多点彼此都“看起来差不多远”，局部结构变弱，剪枝难度升高，这就是常说的维度灾难。

因此，工程上通常不会执着于“绝对精确”。只要返回的前 k 条结果与真实最近邻足够接近，能满足业务召回需求，那么用更少的计算换取更低的延迟，就是合理的设计。这种思想称为近似最近邻approximate nearest neighborapproximate nearest neighborApproximate nearest neighbor search accepts that the returned neighbors may not be the mathematically exact nearest ones, as long as they are close enough for the task. The gain is dramatic reductions in latency, memory access, and operational cost. ，简称 ANN。

ANN 的核心不是“随便猜几个结果”，而是用索引结构提前组织向量，让查询时只访问最有希望的一小部分候选。这样做几乎总要牺牲一部分召回率召回率召回率在向量检索中常指：真实应该命中的近邻里，有多少被系统成功找回。近似索引通常通过牺牲少量召回率，换来显著更低的查询延迟和资源消耗。 ，但换来的是数量级上的性能收益。在大多数线上系统里，这个交换是可接受甚至必要的。

ANN 并不是一种算法，而是一整类策略

从工程实现看，ANN 至少有几条主要路线。第一类是基于空间划分或聚类的索引，例如 IVF；第二类是基于压缩的索引，例如 PQ；第三类是基于图结构的索引，例如 HNSW。它们解决的是同一个问题，但做法不同。有的通过“先缩小候选集合”，有的通过“把向量压小后再计算”，有的通过“在图中逐步逼近最近邻”。

过去几年里，图索引方法尤其流行，其中最有代表性的就是HNSWHierarchical Navigable Small WorldHierarchical Navigable Small WorldHNSW is a graph-based ANN index. It organizes vectors into a multi-layer small-world graph so search can start with long jumps at upper levels and then refine locally at lower levels, achieving strong recall-latency trade-offs in practice. 。它兼具较高召回率与不错的查询速度，在许多向量数据库和检索库中都被作为默认或重要选项。

先理解小世界图

HNSW 的底层直觉可以分两步理解。第一步是小世界图。假设每个向量是图中的一个节点，每个节点连接若干个“附近”的节点。如果图构建得合理，那么你不需要看遍所有点，只需从某个入口节点出发，沿着越来越接近查询向量的方向不断跳转，就有机会迅速走到目标邻域。

这很像在陌生城市里问路。你不需要把每一条街都走一遍，只要不断找到一个“更靠近目的地”的中间点，路径通常会迅速收敛。图搜索之所以高效，靠的不是全局穷举，而是局部贪心前进。

但普通小世界图仍有一个问题：如果起点太差，或者局部结构复杂，搜索可能在某个局部区域里打转。于是 HNSW 又加上第二步：层次结构。

HNSW 的多层结构在做什么

HNSW 的“H”代表 hierarchical，也就是分层。索引中的每个节点会被随机分配到若干层，顶层节点最少，底层节点最多。越往上，图越稀疏、跨度越大；越往下，图越稠密、局部关系越细。

查询开始时，并不直接在最底层那张巨大图里盲找，而是先从最高层的一个入口点开始。因为顶层节点很少，连接跨度大，所以搜索可以快速完成粗定位。找到一个还不错的候选后，系统带着这个候选进入下一层，在更细密的图里继续搜索。这样层层向下，直到最底层做精细逼近。

你可以把它理解为两阶段以上的导航。上层负责远距离跳转，快速把搜索带到大致正确的区域；下层负责局部微调，把最终结果逼近真实最近邻。这种“先粗后细”的结构，是 HNSW 性能表现优异的重要原因。

HNSW 搜索过程如何推进

一次 HNSW 查询，大致会经历三个动作。首先从顶层入口节点开始，计算它与查询向量的距离。随后查看它连接的邻居，若某个邻居更近，就移动过去，并继续检查这个新节点的邻居。只要还能找到更近的点，就继续前进；找不到时，认为在当前层已经达到局部最优，于是下降到下一层，以这个节点作为新层的起点。

到了最底层，系统通常不只保留一个候选，而是维护一个候选集候选集候选集是搜索过程中暂时保留的一批“可能接近查询”的节点。相比只盯住单个当前节点，维护一个候选集可以降低陷入局部最优的风险，并在召回率和速度之间做更平滑的调节。 ，从中不断扩展更优节点。这样做能减少被局部最优困住的概率，也让召回率更稳定。最终从候选集中选出距离最近的前 k 条作为结果。

这个过程本质上是一种启发式图遍历。它不保证数学意义上的绝对最优，却在大多数现实数据分布下表现非常好。也正因为如此，HNSW 才成为许多向量系统的默认答案。

为什么 HNSW 很适合在线场景

很多线上系统关心的不是单次离线批处理，而是稳定、低延迟的实时查询。HNSW 在这一点上很有吸引力。它通常能够在较低延迟下保持不错召回，尤其适合内存型或热数据常驻的检索场景。同时，它对不同距离度量也有较好支持，实现生态成熟。

当然，HNSW 并非没有代价。它的内存占用往往高于更激进的压缩索引；构建过程也可能比简单聚类索引更重；在极大规模分布式环境中，还要额外处理分片与副本下的图管理问题。所以它不是所有场景都最优，而是“综合表现非常均衡”的选择。

精确与近似之间没有道德高低

很多初学者会把精确搜索理解为“正确做法”，把近似搜索理解为“妥协”。这种看法不太适合工程。系统设计永远在多个目标之间权衡：延迟、吞吐、成本、召回率、内存、更新频率。只要近似带来的召回损失在业务上可接受，而成本收益明显，它就不是退而求其次，而是更成熟的方案。

在实际应用里，常见做法甚至是分层处理：先用 ANN 索引召回几百个候选，再做精排或重排；或者先做元数据过滤，再在剩余集合上运行近似搜索。换句话说，ANN 并不是单点技巧，而是整个检索流水线里的一环。

本篇要点

• 暴力扫描的优点是简单且精确，但计算成本会随着数据规模线性增长。
• 高维空间中的最近邻搜索很难依赖传统低维索引方法，因此工程上通常采用 ANN。
• ANN 的核心思想是用少量召回率损失，换取数量级上的延迟和成本收益。
• HNSW 通过多层小世界图实现“先粗后细”的搜索，在召回率与速度之间表现均衡。
• HNSW 查询本质上是启发式图遍历，并依赖候选集来降低陷入局部最优的风险。

下一篇

图索引之外，向量检索还有另一条非常重要的路线：先把数据按簇分桶，再把向量压缩到更小的表示。这正是 IVF 与 PQ 的思路。下一篇会继续讲为什么它们能显著减少搜索量与内存占用，以及两者组合后为何成为经典方案。

参考资料

• HNSW 原始论文
• FAISS Indexes
• Pinecone Learn: Approximate Nearest Neighbors