[In Progress] 向量检索为什么最后都变成了图

目录

• 一、为什么最后都变成了图
• 二、检索算法只有一个
• 三、Delaunay 图，和它为什么用不了
• 四、小世界，以及”能不能找到”
• 五、一个判据
• 六、HNSW：把长边放进层里
• 七、NSG：把长边放进候选池里
• 八、Vamana 与 DiskANN：把图搬上 SSD
• 九、回到选型
• 附：三个问题
• 参考文献

十亿个向量，每个 128 维，要在其中找出与查询最接近的十个。暴力扫描一遍是几千亿次浮点运算，单机几十秒起步。这就是近似最近邻检索（ANN）要解决的问题：放弃「一定正确」，换取几个数量级的加速。

过去十年这个领域的答案收敛得相当快。今天打开任何一个向量数据库，默认索引大概率是一张图；如果数据量再大一个数量级、内存装不下，答案会变成另一张图。

这篇文章想说清楚的是，这些图彼此之间的差别比它们的名字看起来小得多。HNSW、NSG、Vamana 用的是同一个邻居选择判据，只差一个参数；DiskANN 则是把其中一张图搬上 SSD 之后，整套系统被重新设计的结果。串起它们的是一个相当朴素的问题——一张必须稀疏的图，长边从哪里来。

一、为什么最后都变成了图

高维空间里精确检索是没有希望的。KD-tree 这类空间划分结构在大约二十维以上就退化到不如暴力扫描：维度越高，任意两点之间的距离越趋于相等，「划分空间」这个动作本身失去了区分度。所以实用方案一律是近似的，历史上形成过四条路线。

树把空间递归切开，Annoy 用的是随机投影树森林，靠多棵树的投票弥补单棵树的划分误差。哈希以 LSH 为代表，理论保证漂亮，但要在高召回区间工作需要的表数和表长都偏大，工程上不占优。量化与倒排是另一条主线：IVF 把空间聚成若干簇、查询时只扫最近的几个簇，PQ 把向量切成若干段分别量化、用查表代替浮点运算，两者常组合成 IVF-PQ，特点是内存可以压到极致。图则完全换了个思路——在数据点之间直接建立邻接关系，检索退化成图上的一次游走。

经验事实是，在维度上百的稠密向量上，图索引在「同等召回率下的 QPS」这个指标上大幅领先，通常快一个数量级。代价也很明确：图本身要占内存（每个点几十条边就是几百字节），构建慢，删除麻烦。

这个权衡在工业界基本已成定局。Milvus、Qdrant、Weaviate、pgvector、Lucene、Pinecone 的默认索引，不是 HNSW 就是 DiskANN 系。

二、检索算法只有一个

不管图是怎么建的，在图上找最近邻的算法都是同一个：贪心最好优先搜索。

GreedySearch(图 G, 起点 s, 查询 q, 候选池大小 L):
    候选集 C = {s};  已访问 V = {}
    while C 中存在未访问的点:
        p = C 中距 q 最近的未访问点
        V.add(p)
        C ∪= N(p)              # 展开 p 的邻居
        C 只保留距 q 最近的 L 个
    return C 的 top-k, 以及访问集合 V

HNSW、NSG、Vamana 在这一步上没有任何区别，连候选池大小 \(L\) 的含义都一样（HNSW 里叫 ef）。三者的全部差异都发生在建图阶段。于是整个领域的核心问题可以压缩成一句话：边，到底怎么连。

这件事有三个互相拉扯的目标。搜索要走得到，不能陷在局部最优里出不来；要走得快，跳数越少越好；边还不能太多——每条边都占内存，而且展开一个节点时要为它的每个邻居算一次距离，出度直接进入单跳成本。

三、Delaunay 图，和它为什么用不了

理论上这个问题有一个完美答案。在 Delaunay 图上，贪心搜索必然收敛到真正的最近邻，不存在局部最优陷阱——这正是「走得到」这个目标的精确形式化。

可惜维度一高，Delaunay 图的边数就爆炸，几乎退化成完全图，存储和单跳成本都无法接受。于是所有后续工作都在做同一件事：用稀疏子图去近似 Delaunay 图。最常用的近似是相对邻域图（RNG），它的边数是常数级的，保留了 Delaunay 图的大部分导航能力。

但稀疏化不是免费的。被删掉的边里有相当一部分是长边，而长边正是让搜索能够快速跨越空间的东西。RNG 这类邻近图的直径大约是 \(O(N^{1/d})\)——在十亿个点上，从一端走到另一端可能要几十上百跳。「走得到」保住了，「走得快」丢了。

这就把问题推到了一个看起来毫不相干的领域。

四、小世界，以及”能不能找到”

「小世界」这个名字字面来自那句感叹 “It’s a small world!”——在异国他乡遇到一个陌生人，聊几句发现有共同的朋友。学术源头是 1967 年 Stanley Milgram 的实验：给美国中西部的一批人一封信，要求只能寄给自己认识的人、逐跳转交，最终送到波士顿一位指定的股票经纪人手里。成功送达的信平均只经过了六跳。

1998 年 Watts 和 Strogatz 给了形式化定义。一个图是小世界的，当它同时满足两个通常互相矛盾的性质：平均最短路径长度像随机图一样短（\(O(\log N)\)），而聚类系数像规则格一样高。

构造方法很直观：从规则环形格出发，把每条边以概率 \(p\) 随机重连到远处。\(p=0\) 是规则格，高聚类、长路径；\(p=1\) 是随机图，低聚类、短路径。而在中间一大段 \(p\) 值上，只需要重连极少数边，平均路径长度就已经暴跌到接近随机图，聚类系数却几乎没掉。社交网络就是这个样子：绝大多数朋友是「邻居的邻居」，但只要有少数几个人搬去了外地，整个网络的直径就塌缩了。

真正关键的是第二步。2000 年 Kleinberg 指出了一个被忽略的问题：短路径存在，不等于你能找到它。 Milgram 实验里惊人的不是「存在六跳的路径」——随机图里当然存在——而是参与者仅凭本地信息（只知道自己认识谁、目标住在哪）就贪心地找到了它。

Kleinberg 在 \(d\) 维格子上给每个节点加一条长边，长边连到距离 \(r\) 处的概率正比于 \(r^{-\gamma}\)，然后证明：\(\gamma\) 太小则长边太随机，跳出去以后失去方向感；\(\gamma\) 太大则长边太短，退化回规则格；只有 \(\gamma = d\) 时，贪心路由的期望跳数才是 \(O(\log^2 N)\)。这个「能被贪心算法找到短路径」的性质叫 navigable（可导航），也就是 HNSW 里那个 N。

对照回来，结论就很清楚了。稀疏化之后的 kNN 图或 RNG 图扮演的是规则格的角色：聚类系数高、局部精度好，但直径大。缺的正是那批长边，而且长边的分布还必须恰当，否则贪心搜索用不上它们。

三个算法的分野，就是它们补长边的方式不同。 不过在补长边之前，它们要先决定删哪些边——那里有一个共用的判据。

五、一个判据

插入一个点 \(p\) 时，我们手里有一堆候选邻居，要从中挑出不超过 \(R\) 个。不能简单地取最近的 \(R\) 个：那样选出来的邻居会全部挤在同一个方向上，搜索一旦从另一侧接近就完全绕不过来。正确的做法是保证邻居在方向上是分散的，这就是遮挡剪枝。

其中 \(p^*\) 是已经选中的某个邻居。语义是：如果已经有一条通往 \(p^*\) 的边，而 \(p^*\) 到 \(q\) 的距离比 \(p\) 到 \(q\) 的距离小 \(\alpha\) 倍以上，那么「先走到 \(p^*\)，再从 \(p^*\) 走向 \(q\)」是一次实质性的进展，\(p \rightarrow q\) 这条直连边就是冗余的。

\(\alpha = 1\) 时这就是经典的 RNG 遮挡规则，HNSW 和 NSG 用的都是它。

\(\alpha\) 的作用可以用一个一维算例看清楚。设数轴上 \(p = 0\)，候选点在 \(1, 2, 4, 8\) 处。取 \(\alpha = 1\)：选中 \(a\)（距离 1）之后检查 \(d\)（距离 8），\(1 \times 7 = 7 \leq 8\)，删掉；\(b\)、\(c\) 同理。最终 \(N(p) = \{a\}\)，出度只剩 1，图退化成一条链，\(p\) 走到 \(d\) 要四跳。取 \(\alpha = 1.2\)：检查 \(d\) 时 \(1.2 \times 7 = 8.4 > 8\)，保留。最终 \(N(p) = \{a, d\}\)，一跳到位。

为什么恰好是 \(d\) 被保住？看比值 \(d(a,d)/d(p,d) = 7/8\)——绕道 \(a\) 只让剩余距离缩小 12.5%，收益达不到门槛要求的 20%，不划算，于是保留直连边。而绕道去 \(c\) 能把剩余距离从 4 缩到 3，缩小 25%，划算，直连边可以删。所以 \(\alpha\) 的物理含义是绕路的最低收益门槛：越靠外的点，绕道的相对收益越低（\(d(p^*,q)/d(p,q) \rightarrow 1\)），越容易被保留成长边。

这让 α 剪枝成为一个自适应的长边生成器——不需要任何额外的数据结构，长边直接从判据里长出来。真实高维数据没有一维算例这么极端，但趋势一致：纯 RNG 剪枝太贪心，把长边当成冗余删光了，这正是上一节所说的直径问题的来源。

有了这个共同底座，三条路线可以并排放在一起：

同一个判据，换个 \(\alpha\)、换个候选来源，就换了优化目标。下面沿着这条线走完。

六、HNSW：把长边放进层里

Malkov 和 Yashunin 2016 年提出的 HNSW，前身是 NSW（可导航小世界图）。NSW 的长边来自插入顺序的副产品——最早插入的那批点，当时图里点还少，它们连到的「最近邻」其实很远，这些边留存下来就成了长边。免费，但完全不可控。HNSW 把这件事显式化了。

节点插入时随机抽一个层数

得到指数衰减的层数分布。第 0 层含全部点，越往上越稀疏。搜索从顶层唯一入口开始，每层贪心走到局部最优再下沉一层，最后在第 0 层用 \(ef_{search}\) 大小的候选池做精细搜索。这实际上是跳表在度量空间里的类比，把复杂度做到 \(O(\log N)\)。上层是稀疏子采样，所以上层的「最近邻边」在原空间里天然就是长边，而层数的指数分布决定了长边的长度分布——对应的正是 Kleinberg 要求的那个恰当的 \(\gamma\)。

邻居选择用的就是上一节的遮挡剪枝，\(\alpha = 1\)。这一步比分层更关键：如果换成朴素的「取最近 M 个」，召回会断崖式下跌。

工程上，\(M\) 是每节点出度（第 0 层为 \(2M\)），典型 16 到 48，内存约 \(N \times 2M \times 4\) 字节再加原始向量；efConstruction 控制建图质量，取 128 到 500；efSearch 是唯一的在线旋钮，用来在精度和延迟之间滑动。HNSW 统治工业界的最大原因是它支持增量插入——建图和插入是同一套代码，不需要离线重建。短板同样明确：内存贵，删除只能打墓碑加定期重建，而且随机的层间跳转导致内存访问局部性极差，完全不适合放磁盘。

值得一提的是，后来的研究发现分层结构在高维数据上贡献很小，把 HNSW 拍平成单层几乎不掉性能（细节见文末）。这个结论恰好解释了为什么后面两个算法都选择了扁平单层图。

七、NSG：把长边放进候选池里

NSG（Navigating Spreading-out Graph，VLDB 2019）明确提出四个目标：保证连通性、降低平均出度、缩短搜索路径、减小索引体积。

它的理论基础是作者提出的 MSNET（单调搜索网络）：如果图上任意两点间存在一条距离单调递减的路径，贪心搜索就不会回退。他们证明 MRNG（Monotonic RNG）是一种 MSNET，且期望出度是常数级。MRNG 的边选择规则形式上和 HNSW 的启发式几乎一样，差别在候选集的来源和整体框架。

构建分四步：先用 NN-Descent 或 EFANNA 建一个近似 kNN 图作为基础；再计算数据集的 medoid 作为全局唯一的导航点；然后对每个点 \(p\)，从导航点出发做一次贪心搜索，把搜索路径上访问过的所有点——而不只是 \(p\) 的 kNN 邻居——作为候选池；最后施加 MRNG 剪枝，并用一次 DFS 生成树补边，强制保证全图连通。

第三步是精髓。搜索路径上天然包含了「从入口一路走到 \(p\)」沿途的点，其中有大量中远距离的点，正是长边的原料；同时这也让最终的图针对「从固定入口出发」这一搜索模式做了专门优化。Vamana 后来原封不动地继承了这个技巧。

效果是扁平单层加固定入口，路径短、索引比 HNSW 小数倍，同召回下 QPS 更高，是当年 ann-benchmarks 上的 SOTA。但它是纯静态索引：必须先建 kNN 图（本身开销就和建索引同一量级），无法增量插入。这是它没能像 HNSW 那样普及的直接原因。后续的 NSSG（TPAMI 2021）改用角度剪枝，把建图开销降下来，也不再依赖高质量的 kNN 图。

八、Vamana 与 DiskANN：把图搬上 SSD

到目前为止讨论的都是内存里的图。当数据量大到内存装不下，约束条件整个变了，而 DiskANN（NeurIPS 2019，Microsoft Research India）就是在新约束下重做一遍的结果。它包含两部分：图算法 Vamana，以及围绕它的存储与检索系统。

这个名字来自印度神话——Vamana 是毗湿奴的第五个化身，梵语意为「侏儒」。他向阿修罗王 Bali 只讨要「三步之地」，随即化身巨人，第一步跨过整个大地，第二步跨过整个天界。论文没有解释命名，但用极少的几步跨越整个空间恰恰就是这个算法唯一的设计目标。

磁盘改变了什么

DRAM 随机访问约 100 ns，NVMe SSD 随机 4 KB 读约 100 μs，慢一千倍。设定 5 ms 的端到端延迟目标，而图搜索的读是串行依赖的——必须读完当前节点、看到邻居列表，才知道下一个该读谁——那么整个查询能做的串行往返次数只有五十次左右。内存里的 HNSW 在 \(ef = 100\) 时轻松访问上千个节点，照搬到磁盘上就是 100 ms 起步。

还有一个更致命的问题。展开一个节点时，需要计算查询到它所有 \(R\) 个邻居的距离才能决定下一步；如果向量都在磁盘上，展开一个节点就等于 \(R\) 次磁盘读，\(R = 64\) 就是 64 次。这比跳数问题严重得多，也是「图索引不能放磁盘」这个印象的真正来源。

两个问题需要两个不同的解法：跳数由 Vamana 的图结构负责压低，而「看邻居距离」这一步的 IO 由内存里的压缩向量消掉。

RobustPrune

Vamana 的图算法就是把第五节的判据里的 \(\alpha\) 放大：

RobustPrune(p, 候选集 V, α, 出度上限 R):
    V ← (V ∪ N_out(p)) \ {p}          # 现有邻居也扔回候选池重新竞争
    N_out(p) ← ∅

    while V 非空:
        p* ← argmin_{q ∈ V} d(p, q)     # 取候选中离 p 最近的
        N_out(p) ← N_out(p) ∪ {p*}      # 选它当邻居
        if |N_out(p)| = R: break

        for q in V:
            if α · d(p*, q) ≤ d(p, q):  # p* 遮挡了 q
                V ← V \ {q}

这个判据直接给出跳数上界。当图满足「α-捷径可达」性质时，从任意点贪心走向目标，每一跳都保证把剩余距离至少缩小 \(\alpha\) 倍（直到进入目标邻域），于是

\(\Delta\) 是数据集直径，\(\delta\) 是目标邻域半径。\(\alpha = 1.2\) 时收缩很快；而 \(\alpha = 1\) 时 \(\log_1\) 发散，根本不存在乘性收缩保证——这就是 RNG 类图跳数失控的理论根源。

代价是出度变大，长边占了名额。但在磁盘场景这笔交易极其划算：出度从 32 涨到 64，邻居列表从 128 字节涨到 256 字节，反正一个 4 KB 扇区都装得下，读一次的成本完全不变；而跳数从 40 降到 15，直接省掉 25 次 100 μs 的往返。这里体现的是两类图索引的根本分歧——内存图优化的是「访问了多少个点」，磁盘图优化的是「串行往返了多少次」。同一个剪枝规则，换个 \(\alpha\) 就换了优化目标。

建图

VamanaBuild(数据集 P, R, L, α):
    G ← 随机 R-正则有向图
    s ← medoid(P)

    for α' in [1.0, α]:                       # 两遍
        for p in random_permutation(P):
            _, V ← GreedySearch(G, s, p, L)   # 取"访问过的所有点"
            N_out(p) ← RobustPrune(p, V, α', R)
            for p' in N_out(p):               # 反向边
                N_out(p') ← N_out(p') ∪ {p}
                if |N_out(p')| > R:
                    N_out(p') ← RobustPrune(p', N_out(p'), α', R)

四个细节值得解释。

初始图是随机的，而不是像 NSG 那样先建 kNN 图。随机 \(R\)-正则图是扩展图，直径天然是 \(O(\log N)\)，所以从第一次搜索开始就能到达全图任何地方；kNN 图则由紧密的局部团块组成，团块之间可能完全不连通，早期搜索会困在局部。同时这也省掉了一整个昂贵的预处理阶段——NSG 必须先跑 NN-Descent，开销和建索引本身同一量级，而 Vamana 是自足的。整个过程可以理解成从随机退火到有序：初始全是随机长边，每一轮把无用的替换掉，α 判据负责保留其中真正有价值的那些。

要跑两遍，而且第一遍用 \(\alpha = 1\)。第一遍以最严格的 RNG 规则快速建立高质量的局部结构，第二遍的贪心搜索才能返回有意义的访问集合——在纯随机图上搜索，访问集合基本是噪声，拿它做 α 剪枝毫无意义。第二遍再在好材料上做放松剪枝，精准注入长边。论文的消融实验显示单跑一遍 \(\alpha = 1.2\) 明显差于两遍。

候选集用的是访问集合而非 top-L 近邻，理由与 NSG 相同：只喂近邻，候选里根本没有远点，长边无从谈起。

反向边必须加。RobustPrune 只决定出边，而只有出边会导致某些点没有任何入边——那它就永远不可能被搜索到，哪怕它是某个查询的真正最近邻。加反向边让图近似双向，代价是可能把邻居的出度撑爆，所以要对邻居再剪一次枝，这也是构建期的主要开销之一。

存储布局

有了跳数很少的图，剩下的就是系统问题。

内存里只放近似信息，磁盘上是全部精确信息。节点 \(i\) 在 SSD 上存成一条定长记录，起始偏移 \(= i \times \text{node\_size}\)，直接算出来，不需要任何额外索引结构。

这个布局是点睛之笔：一次 4 KB 读同时拿到「我在哪」（原始向量，用于精确重排）和「往哪走」（邻居列表，用于继续搜索）。精确向量是免费搭车来的——为了拿邻居列表，这个扇区本来就必须读。

BeamSearch

BeamSearch(查询 q, 候选池大小 L, beam 宽度 W):
    C ← 优先队列 {medoid}, 按 PQ 近似距离排序, 容量 L
    V ← ∅                      # 已展开（已读盘）的节点
    Exact ← ∅                  # (id, 精确距离)

    while C 中存在未展开的节点:
        B ← C 中距离最近的 W 个未展开节点       # 组一个 beam
        并发发起 W 次 4KB 异步读, 等待全部返回   # 一次 IO 往返

        for each 读回的节点 b:
            Exact.add(b.id, d(q, b.raw_vector))     # ★  精确距离
            for n in b.neighbors:
                if n ∉ V and n ∉ C:
                    C.insert(n, PQ_dist(q, n))      # ★★ 纯内存计算, 零 IO
            V.add(b.id)
        C 截断到 L

    return  Exact 中精确距离最小的 top-k

两个标星的地方分别对应前面提出的两个问题。

展开邻居时用的是内存里的 PQ 距离。一个节点有 64 个邻居，读它们的真实向量是 64 次磁盘读，而查 PQ 码是 64 次约 100 ns 的内存访问，还能 SIMD 查表加速。于是总磁盘读次数等于展开的节点数，而不是节点数乘以 64。

精度则由精确距离兜底。PQ 有量化误差，会把候选顺序排错，但 PQ 距离只用来决定「下一步走谁」和「候选池留谁」；最终返回的 top-k 是从 Exact 集合里按精确距离选出来的，而这个集合有几百个元素，远大于 \(k\)。所以量化误差只会让路走得不够优，不会让排序出错。近似距离负责导航，精确距离负责定序——这个解耦正是 DiskANN 能用 32 字节压缩码达到 95% 以上召回的原因。

延迟账于是对上了：

正好卡在预算上。如果换成 \(\alpha = 1\) 的图，跳数翻两三倍就是 15 ms，方案不成立——α 剪枝不是锦上添花的优化，是这个系统能否成立的前提。

beam 宽度 \(W\) 是最重要的在线旋钮。\(W\) 越大，往返轮数越少、单查询延迟越低，但每轮会读一些本来不会被访问的节点，总读量上升、吞吐下降。所以低延迟场景调大到 4 至 8，高吞吐批量场景调小到 1 至 2。

十亿级怎么建

建图本身需要把数据放内存（贪心搜索要算精确距离），十亿点显然放不下。做法是在采样集上跑 k-means 得到若干中心（SIFT1B 上论文用了约 40 个），把每个点分配给最近的两个中心，每个分片约 \(2N/k\) 个点、能塞进内存，各自独立建 Vamana 图，最后合并——对同时出现在分片 A、B 中的点 \(v\)，令

重叠是关键。如果每点只属于一个分片，分片之间完全不连通，搜索无法跨越簇边界；有了重叠，边界点同时携带两边的边，成为天然的桥。论文报告这种合并式构建能达到单体构建约 95% 的质量。

后续演进

其中删除的处理值得单独一提。图索引删点的难处在于删掉 \(p\) 之后所有指向它的边都断了，图会出现空洞甚至断连。FreshDiskANN 的 consolidate 让邻居继承被删点的邻居——对每个有边 \(u \rightarrow p\) 的节点 \(u\)：

原本经过 \(p\) 的路径被局部修补成绕过 \(p\) 的路径，连通性和可导航性都得以保持，而且这个操作可以在后台批量做、不阻塞查询。

DiskANN 系已经落地在 Azure AI Search、Cosmos DB、Bing、Milvus 的 DISKANN 索引和 pgvectorscale 的 StreamingDiskANN 上。

九、回到选型

数据量在一千万以下、内存放得下、又需要频繁增删的，选 HNSW，生态和运维成熟度上没有对手，取 M=16~32, efConstruction=200，线上调 efSearch 即可。数据量到一亿以上，或者内存成本成为瓶颈而更新不频繁的，选 DiskANN，典型配置 R=64~96, L=100, α=1.2，PQ 码长按内存预算定，经验上内存里的 PQ 码总量不要超过可用内存的一半；需要更新就上 FreshDiskANN 那一套。纯静态底库又要压榨内存态 QPS 的场景——离线批量检索、固定物料库的召回——NSG / NSSG 值得一试，但要接受生态薄弱、需要自己维护。如果有 GPU 且追求极高吞吐，可以看 NVIDIA 的 CAGRA，它为 GPU 的并行访存模式重新设计了图结构，还能导出成 HNSW 格式在 CPU 上检索。

收束

回头看，这四个名字讲的是同一件事：在一张必须稀疏的图上，如何保住可导航性。

Delaunay 图能保证贪心收敛，但高维下太稠密，必须稀疏化；RNG 式的遮挡剪枝能稀疏化，却把长边删光了，直径随之失控。补长边有三种办法——加一层结构（HNSW）、换候选来源（NSG）、改判据本身（Vamana）。而当介质从 DRAM 换成 SSD，优化目标从「访问了多少点」变成「串行往返了多少次」，第三种办法就成了唯一解；再配上「内存近似导航、磁盘精确定序」的解耦，就是 DiskANN。

判据始终是同一个。变的只是 \(\alpha\)，和你在为哪一种介质做优化。

附：三个问题

ScaNN 是库还是算法？

是库。ScaNN 是 Google Research 2020 年开源的向量检索库，和 Meta 的 FAISS 同一层级，里面实现了多种算法，不该和 IVF、PQ 这些单点算法并列。

不过它的招牌贡献确实是一个量化算法，叫各向异性向量量化（ICML 2020），思路很漂亮。传统 PQ 的目标是最小化重构误差 \(\|x - \hat{x}\|^2\)，各方向一视同仁。但在最大内积检索里，把量化误差分解成平行于 \(x\) 和正交于 \(x\) 的两个分量后会发现：平行分量直接改变 \(x\) 的模长，从而直接改变内积大小、直接影响排序；正交分量只在查询恰好偏向那个方向时才起作用，平均影响小得多。而且真正需要排对的是内积本来就大的那批候选，对它们来说平行误差的杀伤力更大。所以 ScaNN 给平行分量加了更大的权重，故意牺牲一点正交方向的重构精度换排序精度——同样的比特预算下召回显著更高。它的完整流水线是「分区 + 量化 + 精排重打分」，属于倒排与量化路线，不是图。

HNSW 的分层到底有没有用？

2024 年有工作（“Down with the Hierarchy: The ‘H’ in HNSW Stands for Hubs”）系统验证了：在高维数据上分层结构几乎没有贡献，把 HNSW 拍平成单层图（只保留第 0 层加邻居启发式）性能基本不变，分层只在低维（大约 32 维以下）有明显收益。

原因是高维图里天然存在枢纽节点（hub）——少数节点因为分布特性会被大量其它节点选为邻居，它们事实上已经承担了长边的角色，分层提供的那点额外长边就显得多余了。这个结论反过来解释了为什么 NSG 和 Vamana 都直接采用扁平单层图，也说明第五节那个判据比分层结构重要得多。

为什么不直接给 HNSW 加 PQ 省内存？

可以，但精度损失通常比 DiskANN 大得多，原因在第八节已经埋好了：DiskANN 的 PQ 只参与导航，最终排序用的是从磁盘读回来的原始向量，量化误差被挡在排序之外；而 HNSW + PQ 的常见实现里没有这个重排步骤，量化误差会直接进入最终结果。

更本质地说，DiskANN 之所以能做这个重排，是因为它的存储布局让原始向量搭了邻居列表的便车、不产生额外 IO。纯内存的 HNSW 没有这个结构性便利——它要么把原始向量也留在内存里（那就没省到内存），要么放弃重排。所以内存真的紧张时，正确的方向是换成 DiskANN，而不是压缩 HNSW。

参考文献

1. Malkov & Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. TPAMI 2020.
2. Fu, Xiang, Wang, Cai. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. VLDB 2019.
3. Subramanya, Devvrit, Kadekodi, Krishnaswamy, Simhadri. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. NeurIPS 2019.
4. Singh et al. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search. 2021.
5. Gollapudi et al. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. WWW 2023.
6. Watts & Strogatz. Collective Dynamics of ‘Small-World’ Networks. Nature 1998.
7. Kleinberg. Navigation in a Small World. Nature 2000.
8. Guo et al. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. ICML 2020.
9. Munyampirwa, Lakshman, Coleman. Down with the Hierarchy: The ‘H’ in HNSW Stands for “Hubs”. 2024.

最后更新：2026 年 8 月 16 日