伪装成对数的幂律：探究基于图的向量搜索的可扩展性

文章背景与核心概要

随着嵌入模型（Embedding models）的广泛应用和数据规模的急剧膨胀，现代向量数据库普遍依赖基于图的索引（如 HNSW 和 Vamana）来进行近似最近邻（ANN）搜索。然而，在维持固定准确率的前提下，搜索成本随数据集大小 \(N\) 呈何种规律增长，此前学术界和工业界普遍基于“多项式对数增长（poly-logarithmic growth）”的传统认知，却缺乏在实际索引和多尺度数据集上的充分验证。

这篇由 Sajad Faghfoor Maghrebi、Navid Eslami 和 Niv Dayan 共同完成的论文对这一经典假设进行了严格检验，并揭示了令人瞩目的全新标度规律：在数据集规模 \(N\) 相对于其固有维度（intrinsic dimensionality）较小时，搜索成本实际上遵循亚线性幂律（Sublinear Power Law，\(N^c\)，其中 \(0 < c < 1\)）；只有当 \(N\) 足够大时，增长才会放缓并趋近于多项式对数增长。作者通过深入探究其底层机制，建立了一个统一的束搜索（beam-search）成本理论，数学证明了这一扩展规律，并开发出能够预测幂律指数的模型，为在数据增长过程中平衡搜索成本、插入成本和召回率提供了有力的理论指导。

📌 摘要

Most modern vector databases rely on graph-based indexes like HNSW and Vamana for approximate nearest neighbor (ANN) search. As embedding models drive rapid dataset growth, understanding how search costs scale with dataset size (\(N\)) at a fixed accuracy is critical.

While the conventional wisdom assumes poly-logarithmic growth, this paper demonstrates that reality depends heavily on scale: 1. The Sublinear Power Law: When dataset size \(N\) is small relative to the data's intrinsic dimensionality, search cost grows as \(N^c\) (where \(0 < c < 1\)). 2. Transition to Subpolynomial: Once \(N\) becomes sufficiently large, growth slows down, aligning with the poly-logarithmic claim. 3. Underlying Mechanism: A dataset's intrinsic dimensionality grows with its size until the data resolves its underlying distribution, forcing the search to examine more vectors within the query neighborhood.

The authors provide a unifying theory of beam-search cost, mathematically prove these scaling laws for exact and bounded-degree constructions, and develop predictive models for power-law exponents to optimize trade-offs among search cost, insertion cost, and recall.

大多数现代向量数据库依赖于基于图的索引（如 HNSW 和 Vamana）来进行近似最近邻（ANN）搜索。随着嵌入模型推动数据集的迅速增长，理解在固定准确率下搜索成本如何随数据集大小 (\(N\)) 扩展至关重要。

尽管传统观点假设其呈多项式对数增长，但本文证明现实情况在很大程度上取决于规模： 1. 亚线性幂律（The Sublinear Power Law）： 当数据集大小 \(N\) 相对于数据的固有维度较小时，搜索成本呈 \(N^c\) 增长（其中 \(0 < c < 1\)）。 2. 向亚多项式过渡（Transition to Subpolynomial）： 一旦 \(N\) 变得足够大，增长就会放缓，从而与多项式对数断言保持一致。 3. 底层机制（Underlying Mechanism）： 数据集的固有维度随其规模增长，直到数据解析出其底层分布，这迫使搜索必须检查查询邻域内的更多向量。

作者提供了一个统一的束搜索成本理论，从数学上证明了精确构造和有界度构造的这些扩展规律，并开发了幂律指数的预测模型，以优化搜索成本、插入成本和召回率之间的权衡。

📑 元数据与参考资料

• 评论： 17页，10个图表
• DOI： 10.48550/arXiv.2609.02143
• 全文链接： 查看 PDF | HTML（实验性） | TeX 源码

📖 摘要

Most vector databases rely on graph-based indexes, notably HNSW and Vamana, for approximate nearest neighbor search. With embedding models widely adopted, the datasets these databases store grow rapidly. At a fixed accuracy, how does search cost scale with dataset size? The prevailing answer is poly-logarithmic growth. Yet the claim is proven only under special conditions and asserted without proof for the indexes used in practice. It is also largely untested: standard benchmarks measure cost at one dataset size, not across sizes.

We put the claim to the test. The answer depends on the scale itself. While the dataset size \(N\) is small relative to the data's intrinsic dimensionality, search cost grows as \(N^c\) for a constant \(0 < c < 1\). We call this scaling the Sublinear Power Law. Once \(N\) is large enough, growth slows to subpolynomial, consistent with the poly-logarithmic claim. The Sublinear Power Law appears on every dataset, mostly up to its full size, at every recall target, query hardness level, and index configuration we test. The transition to subpolynomial growth appears on the two datasets that grow large enough relative to their intrinsic dimensionality.

One mechanism underlies both behaviors: a dataset's intrinsic dimensionality grows with its size until the data resolves its underlying distribution. Higher intrinsic dimensionality packs more vectors into the query neighborhood the search must examine. We present a unifying theory of beam-search cost that explains our observations. For exact and bounded-degree constructions, we prove the Sublinear Power Law and the eventual transition to poly-logarithmic scaling, and derive the scale at which it occurs. We also develop models that predict the power-law exponents for any recall target and index configuration. These models give a principled way to navigate trade-offs among search cost, insertion cost, and recall as data grows.

大多数向量数据库依赖于基于图的索引（特别是 HNSW 和 Vamana）来进行近似最近邻搜索。随着嵌入模型的广泛采用，这些数据库存储的数据集正在迅速增长。在固定的准确率下，搜索成本随数据集大小如何扩展？主流的回答是多项式对数增长（poly-logarithmic growth）。然而，该论断仅在特殊条件下得到证明，而对于实践中使用的索引则是在没有证明的情况下断言的。它也未在很大程度上得到测试：标准基准测试是在单个数据集大小下衡量成本，而不是跨越不同规模进行衡量。

我们对这一论断进行了测试。答案本身取决于规模。当数据集大小 \(N\) 相对于数据的固有维度较小时，搜索成本随常数 \(0 < c < 1\) 呈 \(N^c\) 增长。我们将这种扩展称为亚线性幂律（Sublinear Power Law）。一旦 \(N\) 足够大，增长就会放缓至亚多项式（subpolynomial），这与多项式对数的断言相一致。在我们测试的每个数据集（大体上直至其完整规模）、每个召回率目标、每个查询难度级别以及每个索引配置中，亚线性幂律都存在。向亚多项式增长的过渡出现在相对于其固有维度增长得足够大的两个数据集上。

这两种行为背后都有一个共同的机制：数据集的固有维度随其规模增长，直到数据解析出其底层分布。更高的固有维度会将更多的向量挤压到查询邻域中，从而迫使搜索进行检查。我们提出了一种统一的束搜索成本理论来解释我们的观察结果。对于精确和有界度构造，我们证明了亚线性幂律以及最终向多项式对数扩展的过渡，并推导出了它发生时的规模。我们还开发了针对任何召回率目标和索引配置预测幂律指数的模型。这些模型提供了一种有原则的方法，在数据增长时驾驭搜索成本、插入成本和召回率之间的权衡。