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
TL;DR
At fixed recall, graph-search cost is commonly said to grow poly-logarithmically, but how it scales across dataset sizes remains an open question. The paper measures and models that scaling, finding sublinear power-law growth below a transition and growth bending toward poly-logarithmic when data densely samples its distribution.
Problem
The paper asks how fixed-recall graph-search cost scales with dataset size, given that the prevailing poly-logarithmic claim's applicable scale was unclear.
Source: §3.3 · p. 7, §6 · p. 15Method
It combines fixed-recall measurements using distance computations with a theory modeling how the cost exponent varies with recall and index-construction parameters.
Source: §3.1 · p. 5, §5.1 · p. 13Results
At fixed recall, cost follows a Sublinear Power Law below a transition; most datasets remain there through full size, with growth bending toward poly-logarithmic when data densely samples its distribution.
Source: §6 · p. 15Takeaways & Limitations
The cost models offer practitioners a principled way to set index parameters and sustain a recall target as datasets grow.
Source: §6 · p. 15The shortcut-phase analysis assumes points are uniformly distributed on a sphere because local uniformity alone yields no non-trivial bound without extra assumptions.
Source: §4.2 · p. 10
Abstract
from arXiv · showhide
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
At fixed recall, graph-based vector search follows a Sublinear Power Law while datasets are small relative to their intrinsic dimensionality, then slows to subpolynomial growth at larger scales. A unifying theory links both behaviors to query-neighborhood size and yields scaling results and cost models for HNSW and Vamana.
Graph-based Indexes
- Vector databases use embeddings for semantic search and approximate nearest neighbor search to avoid the prohibitive cost of exact search; practical graph indexes include HNSW [64] and Vamana.Their graph nodes represent vectors connected to nearby vectors and longer-range edges, and beam search walks the graph toward the query.Source: §1 · p. 1
The Logarithmic Folklore
- At fixed recall, the paper tests the prevailing poly-logarithmic scaling claim, which is unproven for practical heuristic indexes and largely untested across dataset sizes.Common benchmarks measure recall–cost trade-offs at a single dataset size; the HNSW paper’s scaling experiments use synthetic vectors with d≤8, while the Vamana paper reports no across-size cost measurements.Source: §1 · pp. 1–2
Observations
- At fixed recall, search cost grows as N^c (0<c<1) when N is small relative to intrinsic dimensionality, then slows to subpolynomial once N is large enough.The Sublinear Power Law appears across eight datasets, recall targets from 90% to 99%, many index configurations, and hard and easy queries; two datasets reach the slowdown.Source: §1 · p. 2
Core Contribution: Unifying Theory
- Search cost is governed by the number of vectors in a small query neighborhood, which grows exponentially with the dataset’s intrinsic dimensionality.While the dataset sparsely samples its underlying distribution, intrinsic dimensionality grows with log N, yielding power-law neighborhood and cost growth; dense sampling slows dimensionality growth and approaches poly-logarithmic cost.Source: §1 · p. 2
- For exact and bounded-degree HNSW and Vamana constructions, the theory proves the Sublinear Power Law and eventual poly-logarithmic scaling, derives the transition scale, and extends to other graph indexes.The passage identifies exact and bounded-degree constructions of HNSW and Vamana as the settings for these results.Source: §1 · p. 2
Additional Contribution: Cost Models
- The paper models HNSW and Vamana query cost by recall target and construction parameters under the Sublinear Power Law, and analogously models insertion cost.Together, the models help users navigate trade-offs among query cost, insertion cost, and recall.Source: §1 · p. 2
2 Background
The background defines vector search and its high-dimensional difficulty, then surveys graph-index designs and their scaling claims, motivating tests of whether query cost is truly poly-logarithmic.
Curse of Dimensionality & Exact Search
- Vector databases embed objects and queries in a shared high-dimensional space; approximate nearest-neighbor search trades exactness for speed and measures quality by distance guarantees or recall.The intrinsic dimensionality of the data, rather than the embedding dimension, is what makes search expensive.Source: §2 · p. 2
Graph-based Indexes
- Graph indexes connect nearby points while diversifying edge directions; Randomized NG guarantees (1 + ε)-approximate search with poly-logarithmic query factors but dimension-heavy degree.Its construction costs O(N^2), and its degree factor grows rapidly with dimension.Source: §2 · pp. 2–3
Sparse Neighborhood Graph
- SNG prunes an edge when an existing neighbor lies in its lune; expected step bounds assume uniform data and dataset-point queries, while its out-degree grows exponentially with dimension.The cited analyses bound search steps by O(N^(2/d) log N) under those assumptions.Source: §2 · p. 3
Vamana and τ-Monotonic Graph
- Vamana adds slack α to encourage constant-factor progress at the cost of more edges; τ-MG extends SNG's progress guarantee to nearby queries with dimension-exponential hidden degree.These graph constructions incur at least quadratic construction cost; Vamana's query-time degree bound is also exponential in dimensionality.Source: §2 · pp. 3–4
Practical Graph-based Indexes
- Practical indexes restrict edge candidates with beam search; HNSW [64] claims logarithmic query cost and O(N log N) construction, while practical Vamana leaves query scaling unstated.These logarithmic claims have been repeated in vendor documentation and industry blogs, despite the gap between claims and measured scaling.Source: §2 · p. 4
3 How Graph-Based Indexes Scale
The section empirically studies how query cost scales in HNSW and Vamana as datasets grow, finding that fixed-recall cost usually follows a sublinear power law, with scaling slowing for some large datasets.
3.2 The Impact of Fixing Recall
- At fixed recall, distance computations usually grow as a Sublinear Power Law across datasets and index configurations.The log-log curves are mostly approximately linear as datasets grow.Source: Figure 3 · p. 5, §3.2 · p. 6
3.1 The Problem: Recall Deterioration
- With fixed search parameters, recall drops as datasets grow because more nearby points slow beam-search convergence and compete for candidate-list places.The study measures query cost as distance computations per query, the dominant cost in graph traversal.Source: §3.1 · p. 5
3.2 The Impact of Fixing Recall
- Higher recall targets and harder datasets increase the fitted exponent, while larger construction list sizes and out-degree reduce it; easy and hard queries both follow the law.The easy and hard query groups have different exponents, but both retain Sublinear Power Law scaling.Source: §3.2 · p. 6, Figure 4 · p. 6
3.3 Scaling with Larger Data
- At billion-point scale, SIFT and DEEP retain Sublinear Power Law scaling, while SpaceV’s query-cost curve slopes downward as the dataset grows.The billion-point experiment uses Vamana with efconstruction = 100 and M = 32.Source: Figure 5 · p. 6, §3.3 · p. 6
4 Unifying Theory
The theory unifies shortcut and exploration costs to explain how query-cost growth depends on points in the query neighborhood and intrinsic dimensionality, from the sparse-regime Sublinear Power Law to slower growth in the dense regime. It analyzes scaling under explicit assumptions, derives shortcut bounds for Vamana versus SNG and HNSW, and extends sparse-regime results to exact graph indexes and practical versions with unbounded construction candidate lists.
4.1 Anatomy of Query Cost
- Exploration accounts for at least 80% of measured search cost because high-dimensional distance concentration and bounded degree impede direct paths among nearby points.This forces the search to explore beyond the true nearest neighbors to meet its recall target.Source: §4.1 · p. 7
- Under local uniformity, expected exploration cost tracks k(1 + ε)^d_int; d_int = Θ(log N) yields a constant-exponent power law, while d_int = o(log N) yields subpolynomial growth.The model assumes same-distribution queries, sufficiently dense data, and Euclidean distance; observed LID grows roughly with log N on most datasets, but flattens for SpaceV and slows for OpenAI.Source: §4.1 · pp. 8–9
4 Unifying Theory
- Total query cost scales as Θ(N), then N^c for 0 < c < 1, then N^o(1), and eventually Θ(poly log N) as dataset size crosses intrinsic-dimensionality-dependent thresholds.The power-law regime follows beyond N = O(M) while N is at most exponential in d_int; beyond 2^{2Θ(d_int)}, the outer neighborhood has O(poly log N) points and shortcut cost governs.Source: Figure 8 · p. 9, §4.1 · p. 9
4.1 Anatomy of Query Cost
- The sparse-to-dense transition occurs when added points stop revealing new local manifold directions, after the dataset has densely sampled neighborhoods at a scale exponential in manifold dimensionality.For out-of-distribution queries, cost is governed by the largest intrinsic dimensionality among intersected manifolds; the analysis also extends to angular distance for normalized vectors.Source: §4.1 · pp. 9–10
4.2 Theoretical Analysis
- The formal analysis uses exact SNG with free construction, models exploration under local uniformity, and bounds shortcut cost under uniform-on-a-sphere data.The authors state that proofs can adapt to HNSW and Vamana, and that sparse-regime results extend to practical indexes when neighbor construction uses an unbounded candidate list.Source: §4.2 · p. 10
4.2.1 Sparse Regime.
- When average node degree follows a power law in N, uniform shortcut and locally uniform exploration costs follow Sublinear Power Laws in N; latter-case navigation computes distances to a power-law number of neighboring nodes.For a point x with approximately uniform data distribution, Theorem 5 states that the n = N^(c/2)/(2·M²·log^Θ(1) N) nearest points connect to their M nearest neighbors with probability at least 1/2.Source: §4.2.1 · p. 11
- In the sparse regime, uniform shortcut and locally uniform exploration costs follow a Sublinear Power Law in N, based on the M-nearest-neighbor graph analysis of [53].The analysis applies [53] to neighborhoods around the entry point and query, respectively.Source: §4.2.1 · p. 11
- When M=N^Θ(1), query-neighborhood nodes have degree at least N^Θ(1) with probability at least 1/2, making the cost of processing even one node a power law in N.This applies to both uniform shortcut and locally uniform exploration costs.Source: §4.2.1 · pp. 11–12
- The sparse-regime Sublinear Power Law conclusions extend to exact HNSW, Vamana, and τ-MG, and to practical versions built with unbounded candidate lists (ef_construction=∞).For practical versions, the argument covers both small maximum degree and large maximum degree cases.Source: §4.2.1 · p. 12
4.2.2 Dense Regime.
- In the dense regime, node degree and locally uniform exploration cost are N^o(1); when d_int=O(log log N), the exploration cost is poly-logarithmic in N.The degree bound applies to SNG, HNSW, and Vamana.Source: §4.2.2 · pp. 12–13
- In the dense regime, Vamana’s shortcut phase takes at most O((1/d_int)·poly log N) steps, while SNG requires Ω(N^((1−o(1))/d_int)) steps; a tight SNG/HNSW upper bound remains open.The SNG lower bound follows from a bound on progress per step; the authors note that local minima may require still more steps.Source: §4.2.2 · p. 12
5 Cost Modeling
Section 5 develops empirical models for query and insertion costs, predicting how they scale with dataset size and index parameters to clarify trade-offs among query cost, insertion cost, and recall.
5.1 Modeling Query Cost
- The query exponent c is modeled as an additive log-linear function of recall demand 1/δ, efconstruction, and M, with average R2 ≈ 0.88 across datasets and algorithms.Higher recall demand raises c, while larger efconstruction and M lower it throughout the tested ranges: recall up to 0.99, efconstruction ∈ [100, 800], and M ∈ [16, 128].Source: §5.1 · p. 13, Figure 10 · p. 14
- Across datasets, query distance computations follow a power law in efsearch, with tight fits of R2 > 0.98.This relationship connects the candidate-list size used during search to the distance computations needed to reach the recall target.Source: §5.1 · p. 13, Figure 10 · p. 14
5.2 Modeling Insertion Cost
- HNSW and Vamana build-cost fits achieve R2 ≥ 92%, and average insertion cost grows log-linearly with efconstruction and N, with M steepening N’s power-law exponent.The insertion model omits recall demand and places M inside the exponent governing growth with N.Source: Figure 10 · p. 14, §5.2 · p. 15
- Except on Rand64, β′ is 0.80–0.92 and 0.07–0.16 above β, so doubling efconstruction raises average insertion cost about 1.8× and insertion is more sensitive to candidate-list size than query cost.The gap is attributed mostly to reverse-link rewiring when candidate neighbors have reached their degree budget; on Rand64, β′ is 0.68–0.76, below β at 0.81–0.83.Source: §5.1 · p. 13, §5.2 · p. 15
6 Conclusion
At fixed recall, graph-index query cost follows a Sublinear Power Law below a transition and bends toward poly-logarithmic growth once datasets densely sample their underlying distributions. A unifying theory attributes both regimes to intrinsic dimensionality as dataset size grows, while cost models help practitioners set index parameters as data grows.
6 Conclusion
- Below a transition, graph-index query cost follows a Sublinear Power Law, and most datasets remain in that 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; cost bends toward poly-logarithmic growth only once datasets densely sample their underlying distributions.Source: §6 · p. 15
- A dataset’s intrinsic dimensionality at its current size explains both scaling regimes and reconciles measured growth with logarithmic claims.The theory connects the transition to when the dataset densely samples its underlying distribution.Source: §6 · p. 15
- Cost models let practitioners set index parameters in a principled way and sustain a recall target as datasets grow.Source: §6 · p. 15