小规模向量检索实测：5,183 篇文档下暴力搜索仍优于 HNSW

一位开发者从零实现了 HNSW 近似最近邻索引与 BM25 倒排索引,并以 FAISS、bm25s、rank_bm25 作为对照,在 BEIR 的 NFCorpus（3,633 篇）与 SciFact（5,183 篇）两个数据集上做了系统实测。结论出乎作者本人预料:在这样的文档规模下,精确暴力检索反而击败 HNSW,且查询编码才是整条链路真正的瓶颈。

实测延迟:HNSW 反而更慢

作者给出每个查询的中位延迟,核心数字如下:

NFCorpus（3,633 篇）
- faiss-flat（精确）: 0.153 ms
- faiss-hnsw（M=16, ef=256）: 0.135 ms
- 自实现暴力精确（mini-brute）: 0.295 ms
- 自实现 HNSW（mini-hnsw）: 3.227 ms
SciFact（5,183 篇）
- faiss-flat: 0.237 ms
- faiss-hnsw: 0.323 ms
- mini-brute: 0.410 ms
- mini-hnsw: 7.517 ms

自实现 HNSW 输给自实现暴力搜索 10.9× 与 18.3×。即使是与 FAISS 比较,FAISS 的 flat 索引在 SciFact 上比自家 HNSW 还快 1.36×;在 NFCorpus 上,HNSW 的运行间波动（0.023 ms）已超过两个系统均值之差（0.019 ms）,差异在统计上不显著。

索引构建成本方面,HNSW 比 flat 慢约 500×（0.93 s 对 0.0017 s）,但回报仅在召回可容忍的更大规模上才会出现。

为何暴力搜索在此规模占优

作者的解释聚焦在算术强度上:在 3,633 篇、384 维下,精确搜索本质是一次稠密矩阵乘法,约 140 万次乘加,BLAS 可以几乎无开销地完成;HNSW 则需要指针追踪、逐节点距离计算与优先队列操作,既无法向量化,又要在 Python 解释器中付出每跳开销,在 CPU 缓存层面也不友好。当线性扫描本身已经足够短时,跳过多数文档的收益不足以抵消图遍历的代价。

ANN 召回随 efSearch 变化的曲线也表明,两个 HNSW 实现都在高 ef 下干净地收敛到精确检索水平（ef=256 时约 0.998）,质量本身不是问题,问题在于速度与构建开销。

验证:对照已发表 BEIR 基线

作者把可复现性作为重点:

稠密检索用 MiniLM-L6-v2,NFCorpus 上 nDCG@10 = 0.3159（已发表约 0.314）,SciFact 上 0.6451（已发表约 0.645）,与文献一致。
对 FAISS 做 323 条查询的配对 bootstrap,在 36 对上做 Benjamini–Hochberg 校正:mini-brute 与 faiss-flat 效应量 d = +0.0000、p = 1.00;mini-hnsw 与 faiss-flat d = +0.0002、p = 0.68,均无显著差异。
BM25 在 NFCorpus 上比发表值低 0.019,作者把原因定位到分词差异（未做词干化、无停用词）:三种 BM25 实现互相之间差距仅 0.0036,但都低于发表值。

四套系统在检索质量上几乎无法区分——NFCorpus nDCG@10 落在 0.3159–0.3162,SciFact 全部为 0.6451。

真正的瓶颈:查询编码

最关键的一组数字是端到端的时间分配:

NFCorpus 上,查询 embedding: 25.8 ms
精确搜索: 0.295 ms

编码器耗时是它喂入的检索步骤的约 87 倍。所有关于索引结构的争论,都发生在真正运行步骤之下两个数量级的位置。

唯一显著的质量提升:RRF 融合

整次实验中唯一具有统计显著性的质量增益,来自 BM25 与稠密检索的倒数排名融合（RRF）:

NFCorpus:0.3423 对最佳单路 0.3162
SciFact:0.6969 对 0.6644
相对 faiss-flat 的效应量 d = +0.0264（p = 0.0045）与 d = +0.0518（p = 0.0009）

融合开销仅 7.36 μs。两个中庸的排序器以「有生产力地不同意」的方式互相补足,胜过任何一方单独使用。

局限与待解问题

作者明确列出边界:

仅两个数据集、一台机器、一个 embedding 模型;「暴力优于 HNSW 的临界规模」结论建立在两个数据点与一段论证之上。
延迟没有显著性检验,只有中位数与波动范围;质量比较做了 bootstrap,延迟没有。
HNSW 构建时间为单样本（同一配置三次分别为 270.0 s、95.4 s、216.0 s,作者无法解释这一波动）,构建成本比值误差约 2×。
全部单线程;理论上多核会进一步拉开暴力搜索的优势（BLAS 可扩展,图遍历难以并行）,但未经测量。
在更大语料上暴力搜索的劣势反而进一步扩大,这与渐近行为相反,作者承认这只是对这两个数据集的观察,不能外推为趋势。

作者求助于社区的两点:其一,是否有人在固定数据上做过跨规模扫描,标定真正的性能翻转点;其二,其第 0 层链接预算相对原论文 Algorithm 1 做了偏离,并针对聚类分布调优——只在合成均匀向量上做过 A/B,无法把这一偏离与低 ef 下在 BEIR 上的召回差距联系起来。

代码与复现步骤见 GitHub:sankalp021/mini-search;完整博客见 snklp.dev 上的对应文章。