HNSW 与向量近邻：当距离代替关键词

破除误解：向量库不是会算余弦的 PostgreSQL#

把嵌入存进一张浮点数组表，再写 ORDER BY embedding <=> query LIMIT 10，语法上像数据库。物理上，若没有专门索引，这就是一次全表距离计算。B 树 按键的全序切页；高维欧氏距离没有这种全序。维度一高，空间划分的“格子”会空掉，这就是常说的维度灾难在检索里的样子：网格、KD 树、低维 R 树，都会在几十维之后退化成近乎扫描。

第二个误解，是把 ANN 当成“差不多就行的搜索，所以不用评测”。ANN 的契约是：在给定查询集上，前 k 个结果与精确近邻的重叠率（召回）达到多少，平均延迟是多少。没有金标准查询，召回只是口感。信息检索 的 Cranfield / TREC 传统在这里完全适用，只不过相关性变成了几何近邻。

第三个误解，是把 HNSW 和倒排索引对立成“新旧两种搜索”。倒排管稀疏词项，向量管稠密嵌入。许多系统两者并用：先倒排收窄，再在候选上算向量；或先向量召回，再用词项过滤。Lucene 后来也接了向量字段，并没有宣布词项死亡。买错的是把所有查询都收成 k 近邻，包括那些本该精确匹配主键的查询。

磁盘与内存上到底长什么样#

HNSW 把点做成一张多层近邻图。最底层包含全部向量。往上每一层是下一层的一个随机稀疏子集，层号按指数衰减的概率抽取。搜索从最顶层一个入口点开始，在该层贪心走到局部最近，再下一层，用更密的边做精细搜索。结构像跳表：上层走长边，下层走短边。Malkov 与 Yashunin 把这个类比写进论文，不是修辞。

每个节点在一层里保留至多 M 条边（常见取值 12 到 48）。构建时还有 efConstruction：候选队列越长，选边越仔细，图越好，建得越慢。查询时的 efSearch 是搜索队列长度：越大召回越高、延迟越高。这三套旋钮是 HNSW 真正的 API。没有它们，只说“图搜索很快”没有操作含义。

边是按距离选的邻居，不是外键。这和 属性图的无索引邻接 同属“把邻居指针写在记录里”，目标却不同。属性图的边是业务关系，类型和属性是一等公民。HNSW 的边是为了让贪心遍历尽快掉进真近邻的盆地。删点、更新向量会打乱这张盆地。早期实现常常不支持高效删除，正是因为图的局部最优邻居集合不是一次 B 树删除能维护的。

向量本身通常仍是一块连续的 float32 数组。HNSW 的图是额外的指针层。内存账大致是：d × 4 字节存坐标，加上约 M × 两层指针。维度 768、M=32 时，图的指针已经和坐标同一个数量级。这就是“HNSW 吃内存”的来源：它把随机访问换来了低延迟，前提是整图能放进 RAM。

查询时图上实际走哪几步#

一次查询不是在图上随便逛。从最高层的入口点开始，算法在这一层只做贪心：看当前点的邻居，挑距离查询更近的那个，直到没有更近的邻居。然后带着这个点下一层。上层边少、跨度大，作用像高速公路。下层边密，才在盆地里细搜。

细搜发生在最底层，但不是把整层扫完。efSearch 规定候选队列能留多少个点。队列里弹出当前最近的，检查它的邻居，把还没看过的点推进队列。队列被填满后，只有比队列里最差的那个更近的邻居才会进来。这就是延迟和召回的交换：队列短，早停，可能停在错误盆地；队列长，多看几跳，更可能摸到真近邻。

选边也不只是“每个点连最近的 M 个”。若只连最近邻，图会变成很多局部团，长距离跳转消失。论文里的启发式会丢掉一些太近且方向重复的边，换成能伸向更远处的边。小世界是被这样工程出来的，不是随机连一堆。M 太小，连通性变差，搜索会卡在小岛上。M 太大，内存和构建时间一起涨，查询时每个点要检查的邻居也变多。

构建时的 efConstruction 通常比查询时的 efSearch 更大。插入一个点，等于对已有图做一次更仔细的搜索，再把找到的邻居写成边，并可能回连。构建偷懒，查询再怎么加大 efSearch 也补不回一张坏图。重建索引的质量旋钮，和线上延迟旋钮不是同一个。

没有分层的可导航小世界图（NSW）已经能工作，但入口点若落在底层，早期跳转会在密图里浪费。HNSW 的分层把“先走远、再走细”写进结构。论文里的对数层数是期望意义上的。真实数据若高度簇集，层间跳转仍可能在簇与簇之间失败。评测必须包含跨簇查询，不能只用簇内查询报高召回。

乘积量化省下的是存储，不是魔法精度#

FAISS 把另一条工业线也做进同一库：倒排文件（IVF）加乘积量化（PQ）。先用 k-means 把空间切成 nlist 个粗簇，查询只探 nprobe 个簇。簇内向量再切成 M 段，每段用一本小码本代替。存储从每维 4 字节变成每段几个 bit。十亿向量开始变得可以放进一块 GPU 或一台机器的内存。

交换很硬。量化把距离变成近似距离。召回掉下来的部分，不是图没走到，而是距离本身被压扁了。nprobe 增大能找回一些被分到邻簇的点，但也把延迟拉回去。HNSW 适合“内存够、要高召回、集合是千万级”；IVF-PQ 适合“内存紧、十亿级、可以接受再排序”。把两者叠起来——用 HNSW 当粗量化器——是工程折中，不是一种新的数学对象。

训练也要分开写。HNSW 不需要单独的训练阶段，点是一个个插进去的。IVF 和 PQ 需要拿一份样本跑聚类。样本若和线上分布漂移，粗簇会过时。这是向量索引特有的运维：嵌入模型一换，旧索引上的距离不再表示同一件事，往往要整库重建。B 树换了比较器也会重建，但词项索引至少还指着同一套词。嵌入一换，几何本身改了。

再排序是 IVF-PQ 的常见补丁。粗检索用短码算出近似距离，取出一长串候选，再用原始 float 向量精排。精排把一部分被量化压扁的次序捞回来，也把延迟加回去。工程上常把“短码召回 + 原向量精排”当成默认，而不是宣称短码已经足够当最终名次。HNSW 在内存够时往往直接在 float 图上走，少了这一层；一旦图也开始量化节点，它同样会需要精排。名称不同，交换相同：先近似，再在短名单上花得起的精确计算。

什么时候这套设计会失效#

• 精确度要求是 100%。 法律检索里“必须找到这一条主键”、去重里“同一哈希必须命中”，ANN 的召回契约不够。用精确扫描、主键索引或倒排，不要用 HNSW 假装精确。
• 过滤条件极严。 “只在某用户可见的十个文档里找近邻”，图上的邻居可能全被过滤器删掉，遍历会空转。先过滤再暴力，或把过滤编进图，都比事后丢弃便宜。HNSW 原论文不解决带属性的约束近邻。
• 更新极频繁。 每秒插入删除一大片向量，图的局部修复跟不上。IVF 对插入稍友善，删除仍常是标记。需要近实时更新时，往往把新鲜向量放进一块可扫描的缓冲，再定期合并进图。
• 维度与度量换了却不重建。 余弦、欧氏、内积在归一化后可互换；没归一化就不是。模型升级后用旧图，测到的是错空间里的近邻。
• 评测集与线上查询不是一回事。 用随机高斯点调出来的 efSearch，对真实用户查询可能不够。必须用线上采样的查询向量做召回曲线。

过滤条件极严时，还有一种更隐蔽的失败。先在全库图上找近邻，再丢掉用户看不见的对象，看起来实现简单。图上的邻居可能全被过滤器删掉，遍历会空转，召回掉到接近零。先过滤再在剩余集合上暴力，或把可见性编进分片，都比事后丢弃便宜。HNSW 原论文不解决带属性的约束近邻。Lucene 后来把 HNSW 放进同一段文件，与倒排共用删除位图，是工程上的并列，不是倒排“升级成了向量”。

和数据库事务的分工也该说清。ACID 保证的是提交后能读到写入。ANN 索引常常在进程内、可重建、允许短暂不一致。把 HNSW 当成唯一真相源，崩溃后会丢图。正确的形状是：对象存在对象存储或关系表里，向量索引是可派生的加速结构，像倒排一样可以重做。

嵌入空间本身也不是中立的。训练语料里的刻板印象、语言比例和版权边界，都会变成近邻。检索到的“相似”可能是统计上的共现，不是学科上的相关。ANN 只保证几何，不保证应当被看见。把推荐失败写成“索引太近似”，有时真正的原因是嵌入把不该近的点拉近了。评测若只用几何金标准，会把这种失败标成高召回。

分布式部署把一层图切到多台机器时，入口点和层间跳转都要跨网络。论文里的对数层数假设内存里的随机读。一旦一跳是 RPC，常数会被网络改写。这时 IVF 的簇可以按机器切开，HNSW 则更常被做成单机内存服务前面的一层。系统选择再次回到访问形状：你的延迟预算里，有多少毫秒可以花在跨机。

召回曲线必须带 k。recall@10 和 recall@100 不是同一个契约。推荐场景常要前十；以图搜图有时要前一百再交给下游模型。把单一召回数字写成“索引很好”，会把 k 擦掉。M 与 efSearch 的甜点也随 k 移动。评测协议要先写 k，再写延迟分位数，最后才写平均值。

构建图时的随机层号一旦抽定，通常不再改。这让结构简单，也让“这一层该有多稀”变成概率而不是数据适应。高度簇集的语料里，上层可能仍挤在一个大簇里，跨簇的高速公路不够。此时 IVF 的粗簇反而更直白：簇就是你切出来的高速公路入口。选 HNSW 还是 IVF，是在问数据的簇结构能不能被随机分层看见，不是在问哪个名字更新。内存不够时，把 HNSW 当唯一方案，会把延迟预算花在换页上。换页会把随机读变成磁盘等待，分层跳转的优势被抹平。

跨域连接#

• 图论：HNSW 用的是近邻图上的贪心搜索，不是最短路算法。边权是嵌入空间的距离，不是交通时间。小世界性质保证随机图上的短路径存在；分层是为了让搜索从长边开始。把 HNSW 说成“图数据库”，会把业务拓扑和几何近邻叠成一个词。
• 信息检索：召回率对延迟的曲线，就是 Cranfield 评测在向量上的翻版。没有查询集与金标准近邻，调 M 只是调手感。倒排的 BM25 与向量的余弦，回答的是不同相关性；融合它们需要另一套评测，不能假设几何近邻等于用户相关。
• 认知偏误：高召回的演示集往往是近邻很近的“容易查询”。线上长尾查询落在低密度区域，贪心会停在错误盆地。用平均值汇报召回，会把难查询的失败平均掉。这是可得性偏差在评测里的形状。
• 供应链：嵌入模型是上游供应商。模型一换，下游所有图和 IVF 码本都要重做，像更换零件规格后整条库存作废。把“向量库”当成稳定的商品货架，会低估上游一次模型发布带来的全链重建。
• 公地治理：共享的 ANN 服务是全体查询的公地。一条把 efSearch 拉到极大的请求，会占满内存带宽，让别人的延迟一起崩。配额、队列和分开的在线/离线索引，是给共享结构划使用规则，不是算法细节。公地的损坏形态是热查询把图的热点节点锁在缓存里，冷查询去打磁盘或触发重建；治理要盯的是尾延迟，不是平均值。

参考文献#

• Yu. A. Malkov & D. A. Yashunin, "Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs", IEEE Transactions on Pattern Analysis and Machine Intelligence 42(4), 2020, pp. 824–836. 预印本 arXiv:1603.09320，2016. —— HNSW 的分层近邻图与搜索复杂度论证。
• Jeff Johnson, Matthijs Douze & Hervé Jégou, "Billion-Scale Similarity Search with GPUs", IEEE Transactions on Big Data 7(3), 2021, pp. 535–547. 预印本 arXiv:1702.08734，2017. —— FAISS 与 IVF-PQ 在 GPU 上的实现。
• Hervé Jégou, Matthijs Douze & Cordelia Schmid, "Product Quantization for Nearest Neighbor Search", IEEE TPAMI 33(1), 2011, pp. 117–128. —— 乘积量化把高维向量压成短码的原始方法。
• Matthijs Douze et al., "The Faiss Library", arXiv:2401.08281, 2024. —— 库所收录索引类型与选用规则的后期综述。

延伸阅读#

• 先在一份小的公开向量集上画召回–延迟曲线，再决定 M 与 efSearch。只看单次演示延迟，会把评测做成广告。
• 与 倒排索引 对读：词项匹配和几何近邻解决的是不同查询。系统选择是匹配访问形状，不是站队。
• 先固定嵌入模型再调 M。模型一换，旧图上的召回曲线没有意义。