A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search

Sajad Faghfoor Maghrebi; Navid Eslami; Niv Dayan

Source-linked AI summary

A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search

Sajad Faghfoor Maghrebi, Navid Eslami, Niv Dayan

arXiv:2609.02143v1Sep 2, 2026cs.DBcs.AIcs.IRcs.LG

TL;DR

Graph-based vector indexes are widely believed to have poly-logarithmic search-cost growth, but that claim is incompletely supported for practical indexes and rarely tested across dataset sizes. This paper combines experiments with a theory of beam-search cost and finds two scale-dependent regimes: sublinear power-law growth before a transition, followed by subpolynomial growth when datasets sufficiently resolve their distributions.

Problem
The paper asks how graph-based vector-search cost scales with dataset size at fixed recall, addressing limited proof and cross-size evaluation of the poly-logarithmic claim.
Method
The authors measure scaling across datasets, recall targets, query hardness levels, and index configurations, then model beam-search cost through shortcut and exploration phases.
Results
Search cost follows a Sublinear Power Law, N^c for 0<c<1, below a transition and slows to subpolynomial growth beyond it.
Takeaways & Limitations
The theory attributes both regimes to intrinsic dimensionality increasing with dataset size until the data resolves its underlying distribution.
Takeaways & Limitations
The shortcut-phase analysis assumes points are uniformly distributed on a sphere, while sparse datasets can alter the outer hyper-ball’s shape and point count.

Abstract

from arXiv · show

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.

1 Introduction

Vector databases use graph-based indexes to make semantic nearest-neighbor search feasible at scale, but the accepted claim that their cost grows poly-logarithmically with dataset size remains incompletely proven and tested.

Embedding models map semantically similar unstructured objects to nearby dense vectors, enabling semantic search.
Graph-based indexes, especially HNSW and Vamana, support approximate nearest-neighbor search by narrowing queries to promising candidates.
Exact nearest-neighbor search is prohibitively expensive at scale, motivating approximate search with a small accuracy loss.
The prevailing poly-logarithmic scalability claim is largely untested because benchmarks usually measure recall–cost trade-offs at only one dataset size.

2 Background

Graph-based indexes represent vectors as navigable graphs and answer queries with beam search, while their scalability claims depend on graph construction, dimensionality, and search conditions.

Vector Search: Vector search embeds data and queries in a high-dimensional space, returning the point or points closest to the query.
Graph-based Indexes: Graph-based indexes connect each vector to nearby vectors plus longer-range edges, allowing beam search to navigate toward a query.
Randomized Neighborhood Graph: Randomized NG has poly-logarithmic query cost under its theoretical analysis, combining O(log^2 N) search steps with logarithmic out-degree factors.
Sparse Neighborhood Graph: SNG suppresses an edge p–q when an already connected point r lies in the lune between p and q, preserving a closer intermediate route.
Sparse Neighborhood Graph: For SNG, proven search-step bounds depend on intrinsic dimensionality and distance gaps, while out-degree is independent of N but exponential in dimensionality.
Scaling with Dataset Size: As datasets grow with fixed HNSW parameters, distance computations per query increase slightly while recall drops significantly.
Practical Indexes: HNSW uses hierarchical layers and SNG pruning, whereas practical Vamana uses α-based pruning; their logarithmic cost claims differ in theoretical support.

3 How Graph-Based Indexes Scale

Across HNSW and Vamana experiments, fixed-recall search cost generally follows a sublinear power law as datasets grow, with exponents shaped by recall, graph construction, and data hardness. At billion scale, SIFT and DEEP retain this pattern, while SpaceV’s growth slows.

Experimental setup: The experiments study query-cost scaling for HNSW and Vamana while holding recall fixed across growing datasets.The evaluation measures distance computations per query and varies datasets, recall targets, and index configurations.
Sublinear Power Law: Fixed-recall query cost forms approximately linear curves on log-log axes, indicating a Sublinear Power Law with exponent 0 < c < 1.The fitted exponent c is reported at the right end of each curve.
Factors affecting scaling: Higher recall targets increase the exponent, whereas larger efconstruction and maximum out-degree M reduce it.Higher recall leaves less margin for missing true neighbors, while stronger graph construction helps beam search reach them in fewer hops.
Query and dataset hardness: Harder datasets and queries exhibit steeper scaling, but both the easiest and hardest query groups still follow the Sublinear Power Law.GloVe has higher intrinsic dimensionality than SIFT and a higher exponent at the same recall level; hard-query groups also have higher exponents than easy groups.
Interpretation and scope: The observed scaling challenges the conventional logarithmic characterization, although SpaceV and OpenAI show possible departures that require larger datasets to assess.OpenAI has already reached its full base dataset, while SpaceV can grow by another order of magnitude.
Larger data: At billion scale, the Sublinear Power Law persists for SIFT and DEEP, while SpaceV’s query-cost slope decreases as the dataset grows.The billion-point experiment uses Vamana with efconstruction = 100 and M = 32 because its smaller memory footprint enables the largest datasets.

4 Unifying Theory

The theory explains graph-based search-cost scaling through two search phases and the growth of intrinsic dimensionality with dataset size. It predicts an initial Sublinear Power Law followed by subpolynomial growth once the data sufficiently resolves its underlying manifold.

Regime Change: At fixed recall, graph-based query cost initially follows a Sublinear Power Law and later slows to subpolynomial growth as dataset size increases.The theory attributes both regimes to how intrinsic dimensionality changes with dataset size.
Search Phases: Exploration accounts for at least 80% of measured search cost because reaching the query vicinity does not make all nearest neighbors easily reachable.The shortcut phase moves inward toward the query neighborhood; exploration then searches outward among overlooked candidate paths.
Local Geometry: Local uniformity models the query neighborhood as approximately uniform on a lower-dimensional manifold, enabling point-count estimates inside expanding hyper-balls.The number of points scales with hyper-ball volume, which depends on intrinsic dimensionality.
Empirical Regimes: LID grows approximately linearly with log N for most datasets, while OpenAI and SpaceV show decreasing slopes consistent with deviations from the Sublinear Power Law.The theory places the sparse-to-dense transition near the scale where dataset size becomes exponential in manifold dimensionality.
Dense Regime: In the dense regime, intrinsic dimensionality is o(log N), so the exponent converges to zero and neighborhood size grows slower than any power of N.The transition occurs after enough samples densely resolve local manifold neighborhoods.
Sparse Regime: In the sparse regime, intrinsic dimensionality grows as Θ(log N), producing N^c points in the query neighborhood for constant c and power-law search cost.The exponent c = log(1 + ε)/ρ is independent of N.

5 Cost Modeling

The paper develops empirical models for how query and insertion costs scale with dataset size and index parameters. These models quantify exponent effects, fit tightly across datasets and algorithms, and expose trade-offs between search and construction costs.

5.1 Modeling Query Cost: Query-cost modeling relates the scaling exponent c to recall demand, efconstruction, and maximum out-degree M.Higher recall demand raises c, while efconstruction and M provide graph shortcuts that reduce search growth.
5.1 Modeling Query Cost: The fitted query-cost model explains approximately 88% of measured exponent variation across datasets and algorithms.The average R^2 is approximately 0.88, and fitted coefficients match the partial-regression slopes.
5.1 Modeling Query Cost: Distance computations per query scale as a power law in efsearch, with tight fits across all datasets.Figure 10-c shows the relationship on log-log axes, with R^2 > 0.98.
5.2 Modeling Insertion Cost: Insertion cost is modeled through the same beam-search structure as query cost, but without a recall-demand term.The model uses dataset size N, out-degree M, and efconstruction because insertion performs the beam search used to locate new neighbors.
5.2 Modeling Insertion Cost: At fixed M, average insertion cost is log-linear in both efconstruction and N, confirming power-law scaling in each variable.The build exponent c' captures how construction cost scales with N, while other coefficients represent geometry, efconstruction, and M effects.
5.2 Modeling Insertion Cost: Insertion-cost fits achieve R^2 ≥ 92%, with efconstruction exponents usually between 0.80 and 0.92.Except for Rand64, doubling efconstruction raises average insertion cost by about 1.8×, making insertion more sensitive than query search.

6 Conclusion

The conclusion revises the prevailing poly-logarithmic account of graph-based search cost by identifying two scale regimes. It explains both through intrinsic dimensionality and presents cost models for parameter choices as data grows.

6 Conclusion: Below a transition point, query cost grows as a Sublinear Power Law, N^c, while most datasets remain in this regime through their full size.The power law appears across eight datasets, recall targets from 90% to 99%, hard and easy queries, and many configurations up to billion scale.
6 Conclusion: Cost bends toward poly-logarithmic growth only after the dataset densely samples its underlying distribution.The theory connects the two regimes through the intrinsic dimensionality exhibited by the dataset at its current size.
6 Conclusion: The resulting cost models let practitioners set index parameters and sustain a recall target as the dataset grows.The models provide a principled way to navigate search-cost, insertion-cost, and recall trade-offs.