跳转到内容
← 返回算法
检索与索引计算机科学 · 算法 · 信息检索约 12 分钟阅读

近似最近邻搜索

Approximate Nearest Neighbor Search

给定一亿个向量和一个查询向量，找出与它最接近的十个——这个问题听起来像入门练习，实际上是过去三十年算法研究中最顽固的难题之一，也是今天每一个向量数据库、推荐系统与检索增强生成管线的地基。 难点不在"最近"，而在"高维"。

近似最近邻向量检索HNSW局部敏感哈希乘积量化

给定一亿个向量和一个查询向量，找出与它最接近的十个——这个问题听起来像入门练习，实际上是过去三十年算法研究中最顽固的难题之一，也是今天每一个向量数据库、推荐系统与检索增强生成管线的地基。

难点不在"最近"，而在"高维"。

破除误解：为什么不能精确地找

第一，精确最近邻在高维空间里退化成暴力扫描。 低维时 kd-树很好用：每次比较砍掉一半空间。但随着维度上升，能被剪枝的分支越来越少——因为查询点到分割超平面的距离，很容易小于它到当前最优点的距离，于是两侧都得搜。到几十维时，kd-树的性能就已经不如直接线性扫描。所有基于空间划分的精确方法都逃不过这一劫，这是维度灾难最直接的后果之一。

第二，"最近邻"这个概念本身在高维会变得脆弱。 在许多高维分布下，随机点对之间的距离会向同一个值集中：最近点与最远点的距离之比趋近于 1。当"最近"与"最远"几乎一样远，最近邻查询就失去了区分力。幸而真实数据通常不是均匀分布在高维空间里，而是聚集在低维流形附近——这个"内在维度远低于表观维度"的事实，正是所有 ANN 方法能工作的根本原因。

第三，"近似"不是偷工减料，而是唯一的出路。 既然精确解在高维不可能又快又准，正确的问题就变成：用多少召回率的损失，换多少倍的速度。放松到近似之后，理论上可以做到亚线性查询时间；工程上则得到了一个明确的三维取舍面——召回率、延迟、内存，三者不可能同时最优。任何 ANN 系统的参数，本质上都是在这个面上选一个点。

路线一：局部敏感哈希——理论最干净的答案

Indyk 与 Motwani 在 1998 年提出局部敏感哈希（LSH），给出了这个领域第一个有理论保证的解法。

核心想法优雅得出奇：设计一族哈希函数，使得距离近的点更可能落进同一个桶，距离远的点更可能落进不同的桶。查询时只在同桶（及邻近桶）中做精确比较，从而跳过绝大多数候选。

以余弦相似度为例，随机超平面哈希取一个随机方向，按点落在超平面哪一侧输出一个比特。两个向量哈希值相同的概率为

Pr⁡[h(u)=h(v)]=1−θ(u,v)π\Pr[h(u) = h(v)] = 1 - \frac{\theta(u,v)}{\pi}

夹角越小，碰撞概率越高。把多个比特串起来提高精度，再用多张哈希表提高召回，就得到了可调的取舍。

LSH 的价值在于它是有证明的：给定近似因子，可以推出查询时间与空间的渐近界。它的问题也同样明确——为了达到高召回率，需要的哈希表数量很多，内存开销大，而在真实数据上，它的实测表现常常输给下面这条没有漂亮理论保证的路线。这是算法领域一个反复出现的教训：最坏情况的保证与真实数据上的效率，经常不是同一件事。

路线二：图索引——工程上的赢家

近十年的实际主流是基于邻近图的方法，其中 HNSW（分层可导航小世界图）几乎成了默认选择。

它的构造思路借自小世界网络：把每个向量作为一个节点，与若干近邻连边；再叠加多层结构——上层稀疏、边长，用于快速跨越大距离；下层稠密、边短，用于精细定位。查询时从顶层的入口点出发，贪心地走向离查询更近的邻居，走不动了就下沉一层，直到最底层。

这是一次从"划分空间"到"在数据上导航"的范式转变。它不试图理解空间的几何，只利用数据点之间的邻接关系；因此它对数据分布的适应性极强，而这正是它在基准测试中长期领先的原因。

代价同样清楚：

  • 内存：图的边必须常驻内存，每个向量的邻接表往往比向量本身还大；
  • 构建成本：建索引比查询慢几个数量级，且难以并行到任意规模；
  • 删除困难：从邻近图里删掉一个节点会破坏连通性，多数实现只做"墓碑标记"，积累到一定比例后必须重建整个索引——这是向量数据库运维中最容易踩的坑；
  • 无理论保证：贪心搜索会不会陷进局部最优，取决于图的构造，没有像 LSH 那样的一般性证明。

针对内存问题，把图索引放到 SSD 上的方案（如 DiskANN 一系）改变了成本结构：用一次磁盘随机读换取十倍以上的容量，使单机索引十亿级向量成为可能。

路线三：量化——把向量压小

第三条路线不改变搜索结构，而是压缩向量本身。

乘积量化（Product Quantization）把一个高维向量切成若干段，每段独立用一本小码本聚类，向量因此被表示成一串码字编号。一个 768 维的 float32 向量占 3072 字节，经过乘积量化可以压到几十字节——压缩比两个数量级，且距离可以直接在压缩域上用查表近似计算，不必解压。

代价是精度损失。实践中的标准做法是两阶段：先用压缩表示快速筛出候选集（粗排），再用原始向量精确重排（精排）。这与信息检索里"召回—精排"的分层思想完全同构，也与主成分分析的取舍一脉相承——都是先降维再补偿。

倒排文件（IVF）结构常与量化搭配：先用聚类把向量分到若干簇，查询时只搜最近的几个簇。这样 IVF-PQ 就成了内存受限场景下的经典组合，而图索引则统治延迟敏感、内存充裕的场景。

被低估的难题：带过滤的检索

生产系统里的查询很少是纯向量查询，而是"在满足这些条件的文档中找最相似的十个"——限定时间范围、语言、权限、租户。

这个组合出奇地难。两种朴素做法都会失败：先过滤再搜索，若过滤后候选很少，索引结构的优势荡然无存；先搜索再过滤，若满足条件的文档比例很低，取回的近邻可能全被过滤掉，召回率崩溃。图索引在这里尤其脆弱——过滤会切断图的连通性，让贪心搜索走进死路。

这是当前 ANN 研究最活跃的方向之一，也是选型时最该问供应商的问题。很多向量库的基准分数是在无过滤条件下测出来的，与真实工作负载相距甚远。

代价与争议

基准测试的可比性长期存疑。 召回率、延迟、内存与构建时间四个维度，任何一个被隐去都会让比较失真。公开基准（ann-benchmarks 一类）改善了这一点，但数据集与真实业务分布的差异仍然巨大，且极少测试更新与删除。

"向量检索能替代关键词检索"是一个昂贵的误解。 稠密向量擅长语义相近，却在精确术语、产品型号、人名与罕见词上系统性失灵——因为这些信息在嵌入压缩中恰恰最容易丢失。成熟系统几乎总是混合检索，而这一课很多团队是在上线后重新学的。

嵌入模型才是真正的上限。 ANN 只负责"在给定的向量空间里高效找近邻"，如果嵌入本身没有把语义编码好，检索再快也无意义。把召回率低归咎于索引参数，是这个领域最常见的误诊。

参数默认值替使用者做了决定。 大多数向量库的默认配置在召回率、延迟与内存之间已经选好了一个点，而使用者往往不知道自己选了什么。知道这三者不可兼得，是用好任何一个向量数据库的前提。

跨域连接

  • 哈希：LSH 把哈希的设计目标彻底翻转——传统哈希追求均匀分散、让相似输入落到毫不相关的位置，局部敏感哈希则刻意制造碰撞，让相似输入尽量相撞。同一个数学工具，因为目标函数取反而变成了完全不同的东西，这是算法设计中最具启发性的对照之一。
  • 信息检索与搜索：召回—精排的分层结构、混合检索的必要性、评估集构建的困难，全部继承自半个世纪的信息检索传统。向量检索是这门老学科的新表示层，而不是它的替代品；忽视这一点的团队，正在逐条重新发现分词、停用词与精确匹配的价值。
  • 检索增强与智能体：RAG 的质量上限由检索质量决定，而检索质量由嵌入与 ANN 共同决定。ANN 的"近似"意味着 RAG 管线里存在一个通常无人测量的静默失真——召回率若是 0.9，就有一成本该被找到的材料从未进入上下文，而模型对此毫无察觉，只会基于手头材料自信作答。
  • 主成分分析：降维与量化处理的是同一个矛盾——高维表示信息完整但代价高昂，低维表示廉价但有损。PCA 给出了线性情形下"损失最小的降维方向"这一最优解，而乘积量化则放弃全局最优、换取分段独立编码带来的压缩比与查表速度。两者对照能看清一条通则：压缩的收益总是以某个特定的失真度量为代价。
  • 计算几何：最近邻查询是计算几何的经典问题，而维度灾难正是这门学科最深刻的负面结果——低维下漂亮的划分结构（Voronoi 图、kd-树）在高维全部失效。ANN 的整个发展史，可以读作几何直觉在高维空间中逐步失效、并被概率与图论方法接管的过程。

参考文献

  • Indyk, P. & Motwani, R. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998.
  • Malkov, Y. A. & Yashunin, D. A. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE TPAMI 42(4), 2020.
  • Jégou, H., Douze, M. & Schmid, C. Product Quantization for Nearest Neighbor Search. IEEE TPAMI 33(1), 2011.
  • Subramanya, S. J. et al. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. NeurIPS 2019.
  • Johnson, J., Douze, M. & Jégou, H. Billion-scale Similarity Search with GPUs. IEEE Transactions on Big Data, 2021.

延伸阅读

  • Andoni, A. & Indyk, P. Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. Communications of the ACM 51(1), 2008.
  • Guo, R. et al. Accelerating Large-Scale Inference with Anisotropic Vector Quantization (ScaNN). ICML 2020.
  • Aumüller, M., Bernhardsson, E. & Faithfull, A. ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. Information Systems, 2020.
  • Beyer, K. et al. When Is "Nearest Neighbor" Meaningful? ICDT 1999.（高维距离集中现象的原始分析）

正文中引用本条 · 1