近似最近邻搜索

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

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

精确 k 近邻的朴素算法，是把查询和库里每一条向量比一遍距离。n 条 d 维向量，一次查询就要做大约 n 次距离计算。低维时，kd-树一类空间划分结构还能剪掉大片空间。高维时剪枝失效，顺序扫描反而更老实。

Weber、Schek 与 Blott 在 1998 年的 VLDB 论文里给出过一组定量观察。他们分析的若干划分索引，在维数升高后查询代价会退化成线性。在他们的设定里，平均表现甚至不如顺序扫描。交叉点大约落在十维附近。

这不是一条对所有数据、所有硬件都成立的魔法阈值。交叉点会随度量、分布以及磁盘与内存的相对速度而移动。维数灾难是动机，不是一张可以查表的拐点。

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

Beyer 等人 1999 年在 ICDT 的论文里，把「最近邻何时还有意义」写成形式条件。在某些独立同分布坐标的模型里，最近与最远的距离比会趋于 1。真实数据往往有低维结构，所以查询仍然有意义。意义来自内在几何，不是来自表观维数本身。

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

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

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

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

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

$$\Pr[h(u) = h(v)] = 1 - \frac{\theta(u,v)}{\pi}$$

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

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

LSH 属于随机算法：哈希函数从一族分布里抽样，碰撞概率由距离决定。Indyk 与 Motwani 的 1998 年 STOC 论文，给出的正是这种以概率换亚线性查询的框架。成功概率再用多张独立的表抬上去。要高召回，表的数量和内存会一起涨。

欧氏距离上常用的 p-稳定分布哈希，由 Datar、Immorlica、Indyk 与 Mirrokni 在 2004 年的计算几何年会上给出。做法是把向量投到一条随机直线上，再按固定宽度切桶。夹角用随机超平面，欧氏距离用这条投影。两者都服从同一条原则：近的点更可能相撞。

Andoni 与 Indyk 在 2008 年的综述里，把高维近似近邻的哈希下界与构造收成一张更清晰的地图。理论最优的指数，和工程上愿意付的内存，仍然不是同一条曲线。LSH 的位置因此很稳定：它是证明的来源，很少是生产默认。

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

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

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

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

它的直接前身是可导航小世界图（NSW）。Malkov、Ponomarenko、Logvinov 与 Krylov 在 2014 年给出单层邻近图：插入时沿已有边贪心走，再把新点接到当前近邻上。长边由较早插入的点自然形成。分层是后来才加上的。

HNSW 的预印本出现在 2016 年 3 月，正式文本于 2020 年发表在 IEEE TPAMI。论文把边按尺度拆到多层，并借用跳表的直觉：上层稀疏、下层稠密。层高按指数衰减的随机分布抽取。查询从顶层入口贪心走，走不动再下沉一层。

邻近图是图论对象，不是空间划分树。同一份实现可以接余弦，也可以接其他可比较的距离。它仍然没有 LSH 那种最坏情况的查询时间证明。工程上领先，不等于理论上被钉死。

代价同样清楚：

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

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

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

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

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

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

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

乘积量化的码本，常用k-means一类聚类在各子空间里分别学习。查询时，子空间距离可以预先算成一张表。距离在压缩域上查表相加，不必把向量解回浮点。这是精度换吞吐的显式交易。

FAISS 一类库把 IVF、PQ 与图索引做成可组合的流水线，并提供 GPU 上的实现。Johnson、Douze 与 Jégou 的论文讨论的是十亿级向量上的相似搜索框架。延迟取决于硬件、批次、召回目标与是否重排。某次演示里的毫秒数，不能当成物理常数搬走。

倒排文件先把库划成簇，查询只进最近的几个簇。探的簇越多，漏掉真近邻的机会越小，也越接近线性扫描。这组旋钮没有与数据无关的默认值。它和 HNSW 的边数一样，都是在召回、延迟与内存之间滑动。

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

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

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

过滤条件把候选集变成数据的一个子集。图上的边却是在全集上长出来的。子集一变，原来的捷径可能指向被滤掉的点。这不是调几个搜索宽度就能消掉的误差。

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

代价与争议#

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

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

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

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

精确 k-NN 在低维、小库、或必须可复现的评测里仍然有位置。空间划分没有被 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.
• Weber, R., Schek, H.-J. & Blott, S. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. VLDB 1998.
• Datar, M., Immorlica, N., Indyk, P. & Mirrokni, V. S. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. SoCG 2004.
• Malkov, Y., Ponomarenko, A., Logvinov, A. & Krylov, V. Approximate Nearest Neighbor Algorithm Based on Navigable Small World Graphs. Information Systems 45, 2014.
• Beyer, K., Goldstein, J., Ramakrishnan, R. & Shaft, U. When Is "Nearest Neighbor" Meaningful? ICDT 1999.
• 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.（高维距离集中现象的原始分析）