A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search
Sajad Faghfoor Maghrebi, Navid Eslami, Niv Dayan
cs.DB · cs.AI · cs.IR · cs.LG
Quick verdict
Claims graph-index cost obeys N^c, not poly-log, until data saturates its manifold; broad billion-scale evidence is persuasive, practical-index proofs lag.
Summary
The paper challenges the widely repeated claim that query cost in graph-based ANN indexes (HNSW, Vamana) grows poly-logarithmically with dataset size at fixed recall. Measuring distance computations across eight public datasets, four recall targets (90–99%), sixteen index configurations per index, and scales up to one billion points, the authors find that cost instead follows a Sublinear Power Law, dc ∝ N^c with 0<c<1, over most of the tested range; a transition toward subpolynomial growth appears only on SpaceV (clearly) and OpenAI (slightly), the two datasets that grow large relative to their intrinsic dimensionality. The proposed mechanism is that a dataset's exhibited intrinsic dimensionality (measured by LID) grows roughly with log N until the data densely samples its underlying distribution, while exploration cost is governed by the ~k(1+ε)^{d_int} points near the query. A unifying theory proves the power law and transition for exact SNG-style and bounded-degree constructions and derives the transition scale; a tight dense-regime upper bound for SNG/HNSW is left open. Regression models (average R²≈0.88 for the exponent model, >0.98 for the ef_search model, ≥0.92 for build cost) predict exponents and costs per dataset and configuration. Main limitations: the proofs target exact constructions rather than the measured heuristic indexes, fitted exponents carry no confidence intervals, and no code release is stated.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 0 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- At fixed recall, graph-index query cost follows dc ∝ N^c (0<c<1) — a Sublinear Power Law — on all eight datasets, at every tested recall target, hardness level, and index configuration, mostly up to each dataset's full size.
- Once N is large relative to intrinsic dimensionality, growth slows to subpolynomial/poly-logarithmic; this transition is observed on SpaceV (clearly) and OpenAI (slightly).
- The mechanism is that exhibited intrinsic dimensionality grows ~log N until the dataset densely samples its distribution, so the query's outer hyper-ball contains ~k(1+ε)^{d_int} points that the search must examine.
- For exact and bounded-degree constructions of HNSW/Vamana (analyzed via SNG), the power law and transition are proven and the transition scale derived; a tight SNG/HNSW dense-regime shortcut upper bound remains open.
- Additive log-linear models predict exponents and costs per dataset/configuration with average R²≈0.88 (exponent model), >0.98 (ef_search model), and ≥0.92 (build-cost model).
Strengths
Novel and well-motivated measurement question
First systematic cross-size, fixed-recall scaling measurement for HNSW/Vamana; Section 2 shows HNSW's own supporting evidence used d≤8 synthetic vectors with its largest point deviating from log-scaling, and benchmarks measure single sizes [4,43,93,107].
Unusual breadth and scale
Eight datasets × two indexes × sixteen (M, ef_construction) configurations × four recall targets (90–99%), plus billion-point Vamana runs (Fig. 5) and sensitivity checks on k∈{1,5,20} and Vamana α∈{1.5,2}.
Theory and measurement cross-validate
Honest boundary-drawing
Actionable cost models
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper attacks a piece of received wisdom: that at fixed recall, query cost in graph-based ANN indexes grows poly-logarithmically with dataset size. Section 2 ("The Logarithmic Folklore") documents that the claim is proven only for special constructions — HNSW's own supporting experiments used low-dimensional synthetic data (d ≤ 8) and its largest measured point deviated from log-scaling, while Vamana's logarithmic argument was never tested across sizes — yet the claim has propagated into vendor documentation and surveys. Against this the authors advance two empirical claims: a Sublinear Power Law, dc ∝ N^c with 0<c<1, below a transition scale, and subpolynomial (eventually poly-log) growth above it. The proposed mechanism is elegant: exhibited intrinsic dimensionality grows as Θ(log N) while the dataset sparsely samples its manifold (Theorem 3), and exploration cost — empirically ≥80% of query cost — is proportional to the ~k(1+ε)^{d_int} points in the query's outer hyper-ball (Theorem 1, Corollary 2), yielding c = log(1+ε)/ρ in the sparse regime. Eqs. 2–4 add regression models that predict exponents and costs.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 0 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
Does HNSW search really scale logarithmically with dataset size?
Not at practical scales, according to this paper. Measuring distance computations at fixed recall across eight datasets up to a billion points, the authors find cost grows as N^c with 0<c<1 (a power law) for most of the tested range. Only when a dataset becomes large relative to its intrinsic dimensionality (clearly observed for SpaceV, slightly for OpenAI) does growth slow toward the claimed poly-logarithmic behavior.
What is the 'Sublinear Power Law' in vector search?
The paper's name for the empirical law dc ∝ N^c (0<c<1) governing distance computations per query at fixed recall while the dataset sparsely samples its underlying distribution. It arises because the intrinsic dimensionality the data exhibits grows with log N, exponentially inflating the number of points near the query. Fitted exponents in the paper's experiments range roughly 0.08–0.69 depending on dataset, recall target, and index configuration.
What are the practical takeaways for sizing a vector database?
Expect per-query cost to keep climbing as data grows (roughly N^c) rather than flatten. The paper's models (Eqs. 2–4) let you predict the exponent from recall target, M, and ef_construction — higher M and ef_construction lower c but raise insertion cost (doubling ef_construction adds ~1.8× per-insertion work) — and set ef_search via its own measured power law.
Which datasets showed the transition to poly-logarithmic scaling?
Only SpaceV shows a clear downward bend from the power law at billion scale (Fig. 5), and OpenAI drifts slightly (Fig. 3). SIFT and DEEP remain straight power laws up to 10^9 points. The paper argues, via LID measurements and theory, that all datasets would eventually transition if grown large enough relative to their intrinsic dimensionality, but this remains an extrapolation for the other six datasets.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figure-embedded numbers (axis ticks, fitted-exponent labels in Figs. 3/5/10 and Table 4 values) arrive interleaved from PDF extraction; individual per-curve values cited here rely on label ordering and should be re-checked against the PDF before quoting.
- The metadata abstract is cut mid-word ('explains ou…'), but the embedded full text contains the complete abstract and runs through reference [117]; no substantive truncation was detected.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.