Paper deep dive
A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search
Sajad Faghfoor Maghrebi, Navid Eslami, Niv Dayan
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 9/3/2026, 3:55:55 AM
Summary
This paper challenges the prevailing belief that graph-based vector search indexes (like HNSW and Vamana) scale poly-logarithmically with dataset size. Through extensive empirical testing and theoretical analysis, the authors demonstrate a 'Sublinear Power Law' where search cost scales as N^c (0<c<1) when dataset size N is small relative to intrinsic dimensionality. As N grows large enough to resolve the data's underlying distribution, the scaling transitions to subpolynomial (poly-logarithmic). The core mechanism is that intrinsic dimensionality grows with dataset size, increasing the number of vectors in the query neighborhood. The paper provides a unifying theory and cost models to predict these scaling behaviors and navigate trade-offs between search cost, insertion cost, and recall.
Entities (10)
Relation Signals (9)
HNSW → isinstanceof → Graph-Based Index
confidence 98% · Most vector databases rely on graph-based indexes, notably HNSW and Vamana, for approximate nearest neighbor search.
Vamana → isinstanceof → Graph-Based Index
confidence 98% · Most vector databases rely on graph-based indexes, notably HNSW and Vamana, for approximate nearest neighbor search.
Search Cost → scalesas → Sublinear Power Law
confidence 95% · As long as the dataset size N is small relative to the data’s intrinsic dimensionality, search cost grows in step with N^c for a constant 0<c<1. We call this scaling a Sublinear Power Law.
Intrinsic Dimensionality → influences → Search Cost
confidence 93% · Higher intrinsic dimensionality packs more vectors into the query neighborhood the search must examine.
Dataset Size → determines → Intrinsic Dimensionality
confidence 92% · A dataset's intrinsic dimensionality grows with its size until the data resolves its underlying distribution.
Search Cost → scalesas → Poly-logarithmic
confidence 90% · Once N is large enough, the growth slows to subpolynomial, consistent with the prevailing poly-logarithmic claim.
Beam Search → usedby → Graph-Based Index
confidence 90% · To answer a query, the index runs beam search, a generalization of greedy search that walks the graph toward the query
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2609.02143v1
- Canonical: https://arxiv.org/abs/2609.02143v1
Trouble viewing inline? Open PDF directly →
Full Text
125,884 characters extracted from source content.
Expand or collapse full text
A Power Law in Logarithm’s Clothing: On the Scalability of Graph-Based Vector Search Sajad Faghfoor Maghrebi Affiliation: University of Toronto, Canada email: smaghrebi@cs.toronto.edu , Navid Eslami Affiliation: University of Toronto, Canada email: navideslami@cs.toronto.edu and Niv Dayan Affiliation: University of Toronto, Canada email: nivdayan@cs.toronto.edu Abstract. Most vector databases rely on graph-based indexes, notably HNSW and Vamana, for approximate nearest neighbor search. With the recent widespread adoption of embedding models, the datasets these databases store have grown rapidly. This growth raises a natural question: at a fixed accuracy, how does search cost scale with dataset size? The prevailing answer is that search cost grows poly-logarithmically. Yet this claim is formally proven only under special conditions; for the indexes used in practice, it is asserted without proof. The claim is also largely untested: standard benchmarks measure search cost at a single dataset size, not across sizes. We put this claim to the test and measure how search cost scales across dataset sizes. The answer turns out to depend on the scale itself. (1) As long as the dataset size N is small relative to the data’s intrinsic dimensionality, search cost grows in step with NcN^c for a constant 0<c<10<c<1. We call this scaling a Sublinear Power Law. (2) Once N is large enough, the growth slows to subpolynomial, consistent with the prevailing poly-logarithmic claim. Empirically, the Sublinear Power Law appears on every dataset, mostly up to its full size, and at every recall target, query hardness level, and index configuration we test. Still, the transition to subpolynomial growth does appear on the two datasets that grow large enough relative to their intrinsic dimensionality. Underlying both behaviors is a single mechanism: the intrinsic dimensionality a dataset exhibits grows with its size, until the data resolves its underlying distribution. Higher intrinsic dimensionality packs more vectors into the small neighborhood around the query that the search must examine. We present a unifying theory that formalizes beam-search cost and explains all of our observations. For both 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 the transition occurs. We also develop models that predict the power-law exponents for any recall target and index configuration. These models provide a principled way to navigate trade-offs among search cost, insertion cost, and recall as data grows. 1. Introduction Unstructured data, spanning documents, images, videos, and audio, has grown rapidly (Wei et al., 2020). Querying such datasets using traditional approaches based on attribute values and keywords fails to capture semantic similarity (Wang et al., 2021b). Meanwhile, advances in learning-based methods, especially deep neural networks, have enabled models that transform unstructured data into dense vector representations suitable for semantic search (Reimers and Gurevych, 2019). These embedding models are trained so that semantic similarity corresponds to geometric proximity: the vectors closest to a query usually represent the most relevant data items. Vector Search. Together, these trends have driven the rise of vector databases, which index the embeddings produced by these models (Wang et al., 2021b; Baevski et al., 2020). Their core retrieval primitive is nearest neighbor search. However, computing the exact nearest neighbors is prohibitively expensive at scale (Beyer et al., 1999b; Indyk and Motwani, 1998; Borodin et al., 1999). Vector databases instead accept a small loss in accuracy and perform approximate nearest neighbor (ANN) search. To do so, they use an index that narrows the search to a small set of promising candidates (Fu et al., 2025; Subramanya et al., 2019; Malkov and Yashunin, 2018). Graph-based Indexes. The ANN indexes that perform best in practice are graph-based (Wang et al., 2021a; Lu et al., 2024). A graph-based index represents each vector as a node, connected to a subset of its nearby vectors, with a few longer-range edges that keep distant regions reachable in a few hops. To answer a query, the index runs beam search, a generalization of greedy search that walks the graph toward the query and returns the closest vectors encountered (Malkov and Yashunin, 2018; Subramanya et al., 2019). Some graph constructions provide guarantees on accuracy and on reaching a query’s neighborhood, but are often too expensive to build exactly (Arya and Mount, 1993; Subramanya et al., 2019). Practical graph-based indexes draw on these exact constructions but build them with cheaper heuristics (Malkov and Yashunin, 2018; Subramanya et al., 2019). The two most widely used such indexes, HNSW (Malkov and Yashunin, 2018) and Vamana (Subramanya et al., 2019), power vector search across databases (Milvus, 2024; Weaviate, 2024; Qdrant, 2025; Upreti, 2024; Kane, 2023; Timescale, 2026), search engines (Veasey and Sharipova, 2025; OpenSearch, 2024), and libraries (Douze et al., 2025; NMSLIB, 2026; Microsoft, 2026). Sustaining Accuracy As Data Grows. The data stored in vector databases grows continuously (Singh et al., 2021; Xu et al., 2023; Baranchuk et al., 2023). As the data grows, however, search accuracy—typically measured by recall, the fraction of true nearest neighbors returned by the search—deteriorates (Chatzakis et al., 2025; Duan et al., 2025; turbopuffer, 2024). Maintaining stable recall therefore requires adjusting the index parameters in response (Duan et al., 2025; Manohar et al., 2024; Zhao et al., 2026). A common practice is to periodically measure recall using exact search (Qdrant, [n.d.]; Vespa, [n.d.]; Elastic, [n.d.]) and adjust parameters accordingly (Manohar et al., 2024; turbopuffer, 2024; Chatzakis et al., 2025). If the measured recall falls short of the user’s recall target, the user raises the search effort, remeasures, and repeats until the target is reached. Recent work in academia as well as in industry (Zilliz, [n.d.]; turbopuffer, 2024) improves upon this practice by using statistical or learned models of the search effort required to achieve a recall target (Chatzakis et al., 2025; Zhang and J. Miller, 2026; Li et al., 2020). Underlying all these approaches is a natural research question: At a fixed level of accuracy, how does search cost scale as the dataset grows? The Logarithmic Folklore. The literature answers this question with poly-logarithmic scaling. For exact graph constructions, the claim is sometimes backed by proof (Arya and Mount, 1993; Indyk and Xu, 2023). For the heuristic indexes used in practice, it is asserted and left unproven. In particular, the paper introducing HNSW claims logarithmic search cost, but the scaling experiments supporting this claim use only low-dimensional synthetic vectors (d≤8d≤ 8), and its largest experiment deviates from logarithmic scaling (Malkov and Yashunin, 2018). The paper introducing Vamana argues that greedy search on its exact construction takes logarithmically many steps, but reports no measurement of search cost across dataset sizes (Subramanya et al., 2019). The claim has nonetheless propagated into industry documentation (Douze et al., 2025; Milvus, 2024; OpenSearch, 2024; Pinecone, [n.d.]; Redis, 2023; Weaviate, 2024) and surveys (Wang et al., 2021a; Pan et al., 2024a; Pan et al., 2024b), which restate it as a settled property of these indexes. It also remains largely untested: benchmarks commonly measure the recall–cost trade-off at a single dataset size, not the scaling of cost across sizes at fixed recall (Aumüller et al., 2020; Simhadri et al., 2024; Jäsaari et al., 2025; Wang et al., 2021a). Observations. We put the folklore to the test and make two observations: (1) When the dataset size N is small relative to the data’s intrinsic dimensionality, the average search cost of a graph-based index at fixed recall grows in step with NcN^c for a constant 0<c<10<c<1. We call this scaling a Sublinear Power Law. (2) Once N is large enough, the growth slows to subpolynomial, consistent with the prevailing poly-logarithmic claim. We verify these observations through extensive experiments: the Sublinear Power Law appears on all eight of our datasets, at recall targets between 90% and 99%, under many index configurations, and for hard and easy queries alike (Section 3.2). On two datasets, the data grows past the transition point and search cost begins to slow below the power law (Sections 3.2 and 3.3). Core Contribution: Unifying Theory. By analyzing the anatomy of query cost, we find the mechanism behind these scaling behaviors: search cost is governed by the number of vectors in a small neighborhood around the query. The size of that neighborhood grows exponentially with the intrinsic dimensionality the dataset exhibits at its current size. As long as the dataset sparsely samples its underlying distribution, that dimensionality grows in step with logN N. An exponential in logN N is a power of N, so the neighborhood, and hence the cost, grows as a power law. Once the dataset samples the distribution densely, intrinsic dimensionality growth slows and cost growth approaches poly-logarithmic (Section 4.1). Our unifying theory formalizes this claim. For both exact and bounded-degree constructions11 1 The exact construction applies the index’s pruning rule with every other vector as a candidate and keeps every surviving edge. The bounded-degree construction additionally caps each vector’s degree, as practical indexes do. of HNSW and Vamana, we prove the Sublinear Power Law and the eventual transition to poly-logarithmic scaling, derive the scale at which that transition occurs, and extend the results to other graph-based indexes (Section 4.2). Additional Contribution: Cost Models. Under the Sublinear Power Law, we model the query cost as a function of the recall target and the construction parameters, across datasets, for both HNSW and Vamana (Section 5.1). For insertions, we model the cost analogously (Section 5.2). Combined, the models help users navigate the trade-offs between query cost, insertion cost, and recall. 2. Background This section provides background on vector databases, graph indexes, and how they are thought to scale with dataset size. A vector database stores complex objects as points in a high-dimensional space, produced by an embedding model that maps similar objects to nearby points (Wang et al., 2024a; Jing et al., 2025; Gao et al., 2023; Joshi, [n.d.]). A query is embedded into that same space by the same embedding model, and the search process returns the point(s) closest to it. Formally, given a set of points S⊂ℝdS ^d and a query point q, the goal is to identify the point in S closest to q. The k-nearest neighbor variant generalizes this, returning the k points in S with the smallest distance to q. The embedding model dictates the dimensionality d, which ranges from hundreds to thousands (e.g., 1536 for OpenAI’s text-embedding-3-small and 3072 for text-embedding-3-large (OpenAI, 2024)). The dimensionality must be high enough to represent the many attributes needed to distinguish objects across a large and diverse corpus. Curse of Dimensionality & Exact Search. In such high-dimensional spaces, search is hard due to the curse of dimensionality (Indyk and Motwani, 1998; Beyer et al., 1999a), a phenomenon whereby most points lie at similar distances from the query, and the nearest neighbor is only slightly closer than the rest (Song et al., 2025; He et al., 2012). Because distances concentrate, points do not separate cleanly, so traditional multidimensional indexes (e.g., R-trees (Guttman, 1984) or KD-trees (Bentley, 1975)) lose their pruning power (Weber et al., 1998; Böhm, 2000; Li and Malik, 2017). To distinguish the nearest neighbors from the many nearly equidistant points, the search must examine a large fraction of the dataset. This is expensive (Navarro, 2002) and degrades to a linear scan in the worst case (Bringmann, 2021). Manifolds & Intrinsic Dimensionality. Real datasets, despite their high embedding dimension, do not span the entire embedding space. Instead, the data resides near lower-dimensional structures embedded within this space (Fefferman et al., 2016). These structures are called manifolds (Brown et al., 2022), each of which behaves locally like a flat, Euclidean space. Each manifold’s dimensionality is considered the intrinsic dimensionality of the data residing near the manifold (Levina and Bickel, 2004). What makes search expensive is this intrinsic dimensionality, not the number of dimensions in the embedding. It is smaller than the embedding dimension, but still big enough that exact search stays slow (Pestov, 2008). Approximate Nearest Neighbor Search. Approximate nearest neighbor (ANN) search sidesteps this expensive query cost by giving up the guarantee of returning the exact nearest neighbors. This allows the search procedure to apply a rough pruning rule that discards a sizable portion of the search space while ensuring that a nearest neighbor is retained with high probability. Query accuracy for ANN is commonly formalized in two ways. The first is the classical (1+ϵ)(1+ε)-approximate distance guarantee: the returned point’s distance to query q is within a factor of (1+ϵ)(1+ε) of the nearest neighbor distance. The same relaxation extends to the k-nearest neighbor case. This guarantee constrains only the distance, not whether the point is a true nearest neighbor. The second, recall, avoids this issue, and is defined as the fraction of the true nearest neighbors that the search returns. Formally, with R the set of true k nearest neighbors and R′R the returned set, recall is |R∩R′|/k|R∩ R |/k. A higher recall value indicates a closer match to the exact search result. This tolerance for inexact answers motivates a class of data structures, called vector indexes, built to answer ANN queries (Wang et al., 2021a; Chronis et al., 2025). Schematic subfigures, one per graph construction, each showing nodes p, q, and r with a red directed edge from p to r. A shaded region around r, whose shape differs across subfigures, marks the area in which r occludes q and suppresses the candidate edge from p to q. Figure 1. Edge selection across graph constructions. In each subfigure, p decides whether to add an edge to q. The node r already connected to p (red directed edge) lies in the shaded region, where it occludes q and suppresses the edge p–q.Schematic subfigures, one per graph construction, each showing nodes p, q, and r with a red directed edge from p to r. A shaded region around r, whose shape differs across subfigures, marks the area in which r occludes q and suppresses the candidate edge from p to q. Graph-based Indexes. Graph-based indexes are widely regarded as the state of the art among vector indexes (Malkov and Yashunin, 2018; Subramanya et al., 2019). They answer ANN queries by traversing a graph whose nodes are the data points. Edges connect each point to a small set of other points, arranged so that search toward a query approaches its nearest neighbors. All graph-based indexes draw these edges following two core intuitions: (1) each point’s edges should lead to points near it, so that once the search closes in on the query, it has easy access to the true nearest neighbors, and (2) the edges should spread across distinct directions, so that from any position some edge makes progress toward the query. The two intuitions act in tandem: every point has many nearby points it could connect to, but diversity decides which few of them become edges, sparsifying the graph while preserving navigability. A query that comes from the same distribution as the data lands amid points whose edges already cover its general direction, and is reachable for the same reason the data points are. Next, we present the popular graph constructions, beginning with the theoretically grounded designs and moving to the practical relaxations they inspired. Randomized Neighborhood Graph. The Randomized Neighborhood Graph (Randomized NG) (Arya and Mount, 1993) is one of the earliest graph-based indexes with a theoretical guarantee for ANN search (Figure 1-a). It builds a directed graph over the data points. Specifically, it guarantees that for any query q, the search finds a point whose distance to q is within a factor of 1+ϵ1+ε of the distance to q’s nearest neighbor. To build this graph, the construction process partitions the space around each point p into cones with apex p. Within each cone, it scans the enclosed points in random order and links p to every point closer to p than all previously scanned points, i.e., every new running minimum. This scan results in an average of O(logN)O( N) neighbors in every cone, at approximately geometrically increasing distances from p. Drawing the edges of a single point requires comparing it against all other points to track the running minimum per cone, so drawing the edges of all N points costs O(N2)O(N^2). The query cost of a graph-based index factors into the number of search steps and the out-degree at each step. For Randomized NG, both are poly-logarithmic in N. The search takes O(log2N)O( ^2N) steps: an ideal straight path to q takes O(logN)O( N) steps, each halving the remaining candidates as in a skip list (Pugh, 1990), and each ideal step expands into O(logN)O( N) actual steps as the path bends in high dimensions. The out-degree is O((1/ϵ)d−1logN)O((1/ε)^d-1 N): the (1/ϵ)d−1(1/ε)^d-1 factor accounts for the number of cones around each point, and each cone contributes O(logN)O( N) neighbors (Arya and Mount, 1993). Although both factors scale poly-logarithmically with N, the (1/ϵ)d−1(1/ε)^d-1 factor grows large in high dimension: smaller ϵε needs narrower cones, and higher dimension needs more cones to cover all directions. The graph therefore grows dense on both counts, which slows search (Arya and Mount, 1993). Table 1. Notations used in the paper. Symbol Description Dataset and query N Number of vectors in the index dambd_amb Ambient dimensionality of the embedding space dintd_int Intrinsic dimensionality of the dataset k Number of nearest neighbors returned per query q A query vector Index parameters M Maximum out-degree of each node in the graph efconstructionef_construction, efsearchef_search Candidate list size at build and search time Cost metrics dcdc Distance computations per query dcbuilddc_build Total distance computations to build an index of size N Query-cost model (Eq. 1, 2, 3) c Query-cost scaling exponent, dc∝Ncdc N^c c0c_0 Dataset-specific baseline exponent α Sensitivity of c to recall demand ln(1/δ) (1/δ) γ1 _1, γ2 _2 Reduction in c per ln(efconstruction) (ef_construction) and per ln(M) (M) β Search-side exponent, dc/q∝efsearchβdc/q ef_search^\,β Build-cost model (Eq. 4) κ Dataset-specific intercept for build cost β′β Exponent of efconstructionef_construction in build cost c0′c _0 Baseline size-dependence of build cost γ2′γ _2 Interaction coefficient between lnM M and lnN N Sparse Neighborhood Graph. The same paper (Arya and Mount, 1993) that introduced Randomized NG also proposed a simpler index, the Sparse Neighborhood Graph (SNG), which underlies many practical graph-based indexes today. SNG connects two points p and q only when no third point r to which p is already connected lies in the intersection of the two balls of radius d(p,q)d(p,q) centered at p and q. This intersection is called the lune of p and q (Figure 1-b). Intuitively, such a point r provides a closer intermediate step from p toward q, so the direct edge from p to q can be removed while preserving navigability. SNG is built by considering, for each point p, all other points in increasing order of distance from p and pruning candidates that violate this rule. A naive construction takes O(N3)O(N^3) time, while the paper achieves O(N2)O(N^2) (Arya and Mount, 1993) by drawing on algorithms for the relative neighborhood graph22 2 First introduced to capture the local structure of a set of points in a sparse manner. from the 1980s (Jaromczyk and Kowaluk, 1987; Toussaint, 1980). For SNG,33 3 Proposed as MRNG (Fu et al., 2025), with a construction identical (Fu et al., 2021) to that of SNG (Arya and Mount, 1993). a later work (Fu et al., 2025) proves that the search takes in expectation O(N1/dlogN/△r)O(N^1/d N/ r) steps for uniformly distributed data and queries that are dataset points, where △r r is the minimum gap between pairwise distances in the dataset. A later paper (Peng et al., 2023) proves that, under the same assumptions, △r r shrinks as O(N−1/d)O(N^-1/d), bounding the steps by O(N2/dlogN)O(N^2/d N). The out-degree, in turn, is independent of N and hence enters the query time only as a constant, but it is exponential in d: the SNG paper bounds it by the number of caps of angular diameter π/3π/3 fitting on the d-dimensional sphere, i.e., 2O(d)2^O(d), and the empirical out-degree grows accordingly (Arya and Mount, 1993). This makes each step, and hence the search, expensive in high dimensions even when the number of steps remains logarithmic. Vamana. Inspired by SNG, Vamana relaxes the pruning rule with a slack parameter α≥1α≥ 1 (Subramanya et al., 2019) (Figure 1-c). Vamana connects two points p and q only when no point r already connected to p comes closer to q than p by a factor of at least α, i.e., α⋅d(r,q)<d(p,q)α· d(r,q)<d(p,q). At α=1α=1, this is exactly the pruning rule in SNG. The intuition behind the slack parameter is that every node has an edge either to the query’s nearest neighbor or to a point at least α times closer to the query than the node itself is, so each greedy step cuts the remaining distance by the constant factor α. Guaranteeing this progress costs extra edges: a larger α makes the pruning condition harder to satisfy, so fewer edges are removed, increasing the graph’s out-degree. A later work (Indyk and Xu, 2023) proves that greedy search reaches an (α+1α−1+ϵ) ( α+1α-1+ε )-approximate nearest neighbor in O(logαΔ(α−1)ϵ)O( _α (α-1)ε) steps, where Δ is the ratio of the largest to smallest pairwise distance in the dataset (i.e., the spread). This ratio stays small in practice even at large N (Indyk and Xu, 2023; Song et al., 2025). Each step pays the out-degree of the visited point, bounded by O((4α)dlogΔ)O((4α)^d ), again exponential in the dimensionality.44 4 Here d is the doubling dimension, a measure of the intrinsic dimensionality. When Δ grows at most polynomially with N, as under a uniform distribution, both logΔ factors become O(logN)O( N), and multiplying steps by out-degree gives a query time poly-logarithmic in N. Also, the construction process, as in SNG, prunes each point against the entire dataset, incurring a total cost at least quadratic in N. τ-Monotonic Graph. Also inspired by SNG, the τ-Monotonic Graph (τ-MG) (Peng et al., 2023) extends SNG’s guarantees to query points within distance τ of some dataset point, for a fixed τ. The construction process connects any two points within distance 3τ3τ, and for farther pairs applies an SNG-like rule on the lune shrunk by 3τ3τ (Figure 1-d). These extra edges densify SNG and guarantee a path that moves at least τ closer to the query at every step. Assuming uniformly distributed data and a query within τ of some dataset point, the paper proves the search reaches the nearest neighbor in O(N1/dlog2N)O(N^1/d ^2N) steps. The paper does not analyze the out-degree, treating it as a constant. In fact, because all points within 3τ3τ are connected, the out-degree is Ω((3τ)d) ((3τ)^d), so the constant hidden in its query cost is exponential in the dimensionality. As in SNG, construction cost is at least quadratic in N. Table 2. Datasets used in the experiments. Dataset Dim. Int. Dim. @ 1M Type Metric Model Sampled From SIFT 128 19.2 Image L2 SIFT descriptors (Lowe, 2004) SIFT1B (Jégou et al., 2011) DEEP 96 20.7 Image L2 GoogLeNet (Szegedy et al., 2015) DEEP1B (Babenko and Lempitsky, 2016) SpaceV 100 29.2 Text L2 SpaceV Superior (Shan et al., 2021) SpaceV1B (Microsoft, 2021) Wiki 768 30.1 Text L2 MPNet (Song et al., 2020) Wiki-all (RAPIDS Team, 2024) GloVe 100 32.4 Text Angular GloVe (Pennington et al., 2014) GloVe-100 (Pennington et al., 2014) Rand64 64 40.2 Synthetic Angular — Unif(S63)Unif(S^63)55 5 Generated by sampling each vector i.i.d. from (0,I64)N(0,I_64) and normalizing to unit length, which yields a uniform distribution on S63S^63. GIST 960 42.5 Image L2 GIST descriptors (Oliva and Torralba, 2001) GIST1M (Jegou et al., 2011) OpenAI 1536 46.5 Text L2 ada-002 (OpenAI, 2022) OpenAI-ArXiv (OpenAI-ArXiv, 2023) Practical Graph-based Indexes. The quadratic construction cost of the above graphs is the core obstacle to their practical use at scale (Peng et al., 2023; Arya and Mount, 1993; Fu et al., 2025). Modern practical indexes lower this cost by restricting the set of points to which each point can connect. Rather than treating every point as a candidate for a point’s edges, they apply a greedy beam search to find a much smaller set of nearby points, then apply the pruning rule within that smaller set. More precisely, when inserting a new point, the index runs a beam search on the current graph for the new point. Beam search maintains a candidate list of fixed size, here efconstructionef_construction, and starts from one or more entry points. It repeatedly expands the closest unexpanded candidate, keeping only the closest points found so far in the list. Once no unexpanded candidate remains, the list is pruned locally and the new point is connected to at most M of the closest survivors. The same beam search procedure is used at query time, with a candidate list of size efsearch≥kef_search≥ k, and the top-k results are selected from it. The practical indexes differ mainly in the pruning rule each applies to this candidate list rather than to the full dataset. HNSW (Malkov and Yashunin, 2018) organizes nodes into hierarchical layers, assigning each node to higher layers with exponentially decaying probability, and applies the SNG rule within each layer. The practical version of Vamana (Subramanya et al., 2019) applies the α-based pruning rule; henceforth, we refer to this version of Vamana simply as Vamana. The HNSW paper claims that its query cost scales logarithmically with dataset size while its construction cost stays below quadratic, at O(NlogN)O(N N) (Malkov and Yashunin, 2018). The paper that introduced Vamana (Subramanya et al., 2019) argues that greedy search on its exact construction takes logarithmically many steps but leaves the query cost scaling of its practical version unstated; benchmarks nonetheless place it alongside HNSW as state-of-the-art (Subramanya et al., 2019; Aumüller et al., 2020). These logarithmic scalability claims and similar claims from the same line of work (Fu et al., 2025; Fu et al., 2021; Peng et al., 2023; Malkov et al., 2014; Li et al., 2026) have since propagated into vendor documentation and industry blogs, which restate them as a settled property of these indexes (Elastic, 2024; Milvus, 2024; OpenSearch, 2024; Pinecone, [n.d.]; Redis, 2023; Weaviate, 2024). In the next section, we evaluate how these indexes scale and bridge this gap between claimed and measured scaling both theoretically and empirically. Two stacked line charts over dataset size, with one line per search beam width value. The top chart shows distance computations per query increasing as the dataset grows; the bottom chart shows recall decreasing. Figure 2. As the data grows, distance computations per query rise (top) and recall drops (bottom). Here, we use the HNSW index with efconstruction=200ef_construction=200, M=32M=32, and k=10k=10, with one curve per efsearchef_search value.Two stacked line charts over dataset size, with one line per search beam width value. The top chart shows distance computations per query increasing as the dataset grows; the bottom chart shows recall decreasing. A row of log-log line plots, one per dataset, showing distance computations per query versus dataset size at several fixed recall levels. In every subfigure the curves form nearly straight lines, consistent with a Sublinear Power Law. Figure 3. When recall is fixed, the number of distance computations (y-axis) increases with dataset size (x-axis) across the datasets from Table 2, forming a linear pattern in the log-log diagram. This is consistent with a sublinear power-law. A row of log-log line plots, one per dataset, showing distance computations per query versus dataset size at several fixed recall levels. In every subfigure the curves form nearly straight lines, consistent with a Sublinear Power Law. 3. How Graph-Based Indexes Scale In this section, we study empirically how query cost scales as data grows, focusing on HNSW and Vamana66 6 We use the in-memory version of Vamana, built with build_memory_index (Microsoft, 2026)., the most widely used graph-based indexes (Milvus, 2024; Pan et al., 2024a). Later in Section 4 we show that our findings generalize to other graph-based indexes. 3.1. The Problem: Recall Deterioration Our first experiment verifies a known phenomenon: when the index parameters are held fixed, recall degrades as the dataset grows (Duan et al., 2025; Manohar et al., 2024; Zhao et al., 2026). To simulate data growth, we draw uniformly random subsets of increasing sizes from each of the datasets in Table 2 up to their full sizes. Each subset is shuffled before index construction. When a dataset provides a canonical query set, we use it as our query workload. Otherwise, we reserve 10,000 uniformly sampled points as queries, excluding them from the set of points over which the index is built. To compute the true nearest neighbors for each query (i.e., its ground truth), we perform an exact search by linearly scanning the entire dataset. We then execute the query using the index and compare the returned results against the ground truth to compute recall. We measure query cost in terms of the number of distance computations (dc) per query as this is the dominant cost in graph traversal (Fu et al., 2025; Yang et al., 2025; Gao and Long, 2023). By so doing, we avoid conflating algorithmic performance with implementation idiosyncrasies (cache evictions, prefetching, hardware-optimized distance computations, etc.). All experiments in the paper follow this setup. Figure 2 shows the results on HNSW using three representative datasets (the remaining ones behave similarly). Each column represents a different dataset (SIFT, DEEP, and GloVe). The top row reports distance computations and the bottom recall. Each subfigure shows one curve per setting of the efsearchef_search parameter. For each of these curves, we observe that distance computations per query slightly increase with dataset size N (top row), while recall drops significantly (bottom row). The reason for this behavior is that as the data grows, more points lie close to the query. Beam search therefore converges more slowly, and the true nearest neighbors face more competition for a place in the candidate list, as suggested in prior work (Manohar et al., 2024). This recall degradation is problematic for applications such as retrieval-augmented generation (RAG) (Karpukhin et al., 2020) and recommendation systems (Covington et al., 2016), which require stable recall even as datasets grow. 3.2. The Impact of Fixing Recall The experiment in the previous section raises a natural question: can recall be kept stable as the dataset grows? Although prior work has not addressed this question directly, it has considered the related problem of meeting a specified recall target. The standard approach is to periodically measure recall using exact search (Qdrant, [n.d.]; Vespa, [n.d.]; Elastic, [n.d.]) and adjust search parameters accordingly. If the measured recall falls below the target, the user increases the efsearchef_search parameter, measures recall again, and repeats this process until the target is reached (Manohar et al., 2024; turbopuffer, 2024; Chatzakis et al., 2025). Recent work in academia as well as in industry (e.g., Zilliz Cloud (Zilliz, [n.d.]) and Turbopuffer (turbopuffer, 2024)) improves upon this approach by using statistical or learned models of the search effort required to achieve a recall target (Chatzakis et al., 2025; Zhang and J. Miller, 2026; Li et al., 2020). Once recall is held fixed, another core question emerges: how does query cost scale as the dataset grows? Experimental Setup. To hold recall fixed, we set efsearchef_search to the smallest value that attains a given fixed recall target. Figure 3 reports the average number of distance computations per query across a grid of datasets, recall targets, and build settings. Rows correspond to different datasets. We progressively grow each dataset by increasing its number of points up to its original full size. For the substantially larger SIFT, DEEP, and SpaceV77 7 This dataset contains many duplicate points. To compare fairly against other datasets, we de-duplicate it and sample the query set exclusively from the base dataset. datasets, we cap the size at 100M points to keep the total experimental runtime to approximately one week. Recall targets of 90%, 95%, 97.5%, and 99% appear as separate curves in each subfigure. Each column corresponds to a different index configuration. HNSW occupies the left four columns and Vamana the right four, with the maximum out-degree M∈16,32,64,128M∈\16,32,64,128\ and construction list size efconstruction∈100,200,400,800ef_construction∈\100,200,400,800\ varying across the columns.88 8 For Vamana, α is a build parameter fixed to the default 1.2 (Subramanya et al., 2019); testing α∈1.5,2α∈\1.5,2\ left scalability unchanged, as out-degree typically saturates at cap M. Due to limited space, we show four of the sixteen benchmarked (M,efconstruction)(M,ef_construction) configurations per index; the remaining settings behave similarly. Results. On the log-log axes in Figure 3, most curves are approximately linear as the dataset grows, indicating that query cost follows a Sublinear Power Law: (1) dc∝Nc.dc N^c. Here, 0<c<10<c<1, and the value at the right end of each curve reports the fitted exponent c. Log-log line plot of distance computations per query versus dataset size, with separate lines for hard and easy queries. Both sets of lines are straight and nearly parallel, indicating power-law scaling for both query groups. Figure 4. Both hard and easy queries follow a power law scaling. We use the same HNSW setup as Figure 2.Log-log line plot of distance computations per query versus dataset size, with separate lines for hard and easy queries. Both sets of lines are straight and nearly parallel, indicating power-law scaling for both query groups. Figure 3 also indicates the factors that impact the exponent c in Equation 1. The exponent increases with higher recall targets, since they leave less margin for missing true nearest neighbors and force the search process to traverse more of the graph. Higher values of efconstructionef_construction and M reduce c by yielding graphs in which the beam search reaches the query’s nearest neighbors in fewer hops. We also measured k∈1,5,10,20k∈\1,5,10,20\ and found that varying it does not materially change c, so we report only k=10k=10. The nearest neighbors lie at nearly the same distance from the query, so retrieving all k is about as hard as retrieving one. We give more intuition for this in Section 4.1. Beyond these parameters, the exponent tends to increase with dataset hardness. The rows in Figure 3 are ordered by increasing intrinsic dimensionality, a proxy for hardness, with estimates listed in Table 2. For example, GloVe has higher intrinsic dimensionality than SIFT (32.4 vs. 19.2) and a higher exponent at the same recall level. This suggests that beam-search cost scales more steeply with N on harder datasets. Varying Query Hardness. As discussed in Section 2, queries within a workload can vary substantially in hardness (Wang et al., 2024b; Chatzakis et al., 2025; Li et al., 2020), with queries in regions of higher intrinsic dimensionality generally being more expensive to answer (Aumüller and Ceccarello, 2021). To test whether the Sublinear Power Law holds across query hardness levels within the same workload, we rank queries by intrinsic dimensionality99 9 Later, in Section 4.1, we show how to measure intrinsic dimensionality using LID; Figure 7 reports the resulting estimates. and rerun the experiment separately on the easiest and hardest 20%. On SIFT, DEEP, and GloVe, the hard group’s intrinsic dimensionality exceeds that of the easy group by at least 7.97.9, 9.69.6, and 11.011.0 points, respectively. Figure 4 shows that while the two groups have different exponents, both still follow the Sublinear Power Law. Summary. Our experimental results so far challenge the conventional logarithmic characterization of graph-based indexes from Section 2. Under logarithmic scaling, each doubling of N would add only a constant number of distance computations, causing the curves in Figures 3 and 4 to bend downward rather than remain straight. Instead, the Sublinear Power Law describes most of the datasets, index configurations, and query hardness levels we measure. That said, we also observe exceptions to the Sublinear Power Law. For SpaceV and OpenAI, some of the curves in Figure 3 seem to drift very slightly below their fitted power laws, as if the scaling were slowing down. Only larger dataset sizes can tell whether the drift is real. OpenAI already uses its full base dataset, whereas SpaceV can grow by another order of magnitude; we explore this next. 3.3. Scaling with Larger Data Log-log line plot of distance computations versus dataset size up to one billion points for the SIFT, DEEP, and SpaceV datasets. The SIFT and DEEP curves stay straight throughout, while the SpaceV curve flattens as the dataset grows. Figure 5. The power law persists to billion scale on SIFT and DEEP, while SpaceV’s slope decreases as the dataset grows.Log-log line plot of distance computations versus dataset size up to one billion points for the SIFT, DEEP, and SpaceV datasets. The SIFT and DEEP curves stay straight throughout, while the SpaceV curve flattens as the dataset grows. The SIFT, DEEP, and SpaceV datasets each have a base collection size of one billion points, but at that scale the index for a single configuration occupies 300 GB–1 TB and takes several days to build (Singh et al., 2021). We therefore choose one representative configuration (efconstruction=100ef_construction=100, M=32M=32) and repeat the experiment with Vamana1010 10 We use Vamana here because it has a smaller memory footprint than HNSW and therefore lets us scale to the largest available dataset sizes.. We grow each of the three datasets from 100K points to their full base size of one billion points. Figure 5 shows that on SIFT and DEEP, the same Sublinear Power Law continues to hold as the data grows. The query cost of SpaceV, however, behaves differently: it slopes downwards as the dataset grows. Thus, while the scalability of graph-based indexes exhibits clear empirical patterns, two questions remain: what explains the initial sublinear power-law scaling across all workloads, and why does this scaling eventually slow for some workloads? 4. Unifying Theory We now develop a unifying theory that explains the observations so far: when recall is held fixed, query cost initially scales as a Sublinear Power Law and then slows as the dataset grows. The theory suggests that the slowdown observed for SpaceV and OpenAI in the previous section is not specific to these datasets; we would observe the same transition on the other datasets if they could be scaled to sufficiently large sizes. 4.1. Anatomy of Query Cost Search Phases. Conceptually, beam search on graph-based indexes such as HNSW or Vamana involves two phases. The first, which we call the shortcut phase, navigates from the entry point toward the query’s neighborhood: at each step, the search picks the candidate closest to the query and checks its neighbors, moving steadily inward (Malkov and Yashunin, 2018; Wang et al., 2021a). In this phase, beam search behaves essentially like greedy search, since the best candidate improves at every step. The second, which we call the exploration phase, searches the neighborhood of the query for its true k-nearest neighbors: the search now moves outward, expanding candidates it had passed over and branching into paths it initially skipped, until it can no longer make useful headway. We now study the costs of these two phases. Exploration Phase. Across all benchmarks in Figures 3–5, we measure the proportion of search cost spent in the shortcut phase versus the exploration phase. In every case, the exploration phase accounts for at least 80% of the cost, consistent with prior observations (Chatzakis et al., 2025; Lu et al., 2026; Chen et al., 2023; Lin and Zhao, 2019). This phase is expensive because reaching the query vicinity does not imply that all true nearest neighbors are easily reachable. In high dimensions, distances concentrate (Song et al., 2025), so points close to the same query need not be close to one another. At the same time, bounded node degree limits local connectivity to control memory and per-hop search cost. Together, these effects prevent the query neighborhood from forming a tightly connected region (Diwan et al., 2024; Cai et al., 2013), forcing nearby points to be reached through roundabout rather than direct paths and requiring exploration beyond the true nearest neighbors to achieve a recall target. Modeling Exploration Cost. We now construct a mathematical model of the cost of the exploration phase, aiming to understand why the Sublinear Power Law arises. The model represents the query’s neighborhood as two nested hyper-balls (multi-dimensional balls) centered at the query point q. The inner hyper-ball extends from the query to its k-th nearest neighbor and thus has radius rkr_k; the outer hyper-ball extends to distance (1+ε)rk(1+ )r_k. Here, 1+ε1+ is the smallest factor for which extensively searching the outer hyper-ball visits the true k-nearest neighbors with probability equal to the recall target. As the dataset grows, the distances from the query to the points in its neighborhood shrink by a common factor. The inner and outer hyper-balls therefore contract by the same factor, leaving their radii ratio (i.e., 1+ε1+ ) unchanged (we return to this point later in Discussion 4.1). Henceforth, we define the exploration phase precisely as the distance computations the search performs within the outer hyper-ball, and the shortcut phase as the rest. The cost of the exploration phase is governed by the number of points inside the outer hyper-ball. Hence, the key question is: how does the number of points in the outer hyper-ball grow with the dataset size N? Local Uniformity on a Manifold. To answer the question above, we adopt a standard assumption from the literature: real embedding datasets exhibit complex structure at the global scale, yet if we zoom closely enough into any subspace, the distribution within it is approximately uniform (Prokhorenkova and Shekhovtsov, 2020; Aumüller and Ceccarello, 2021). More precisely, real-world datasets tend to concentrate across lower-dimensional manifolds. Within a sufficiently small neighborhood around the query, the data behaves as if its density were approximately uniform (McInnes et al., 2018; Houle, 2017; Ma et al., 2025). The intuition is that real-world data items vary along continuous attributes, such as the visual style of an image or the topical blend of a document. Embedding models are trained to map similar data items to nearby vectors, so the variation carries over to the vector space, where density changes gradually rather than abruptly. Within a small enough neighborhood, points can therefore be treated as uniform on their manifold. For example, in Figure 6, the dataset forms a complex manifold in three dimensions, yet the subspace we zoom into is two-dimensional with approximately uniform points. We thus model the points in both the inner hyper-ball, which contains the nearest neighbors, and the outer hyper-ball as uniformly distributed around the query; we call this the local uniformity model. Figure 9 later confirms that the outer hyper-ball is indeed local: the search rarely goes far beyond the nearest neighbors. Assumptions. Beyond the local uniformity model, our analysis in this section adopts three assumptions. (1) The query is drawn from the same distribution as the data. (2) The dataset is dense enough that the hyper-balls’ projections onto the manifold are themselves approximately lower-dimensional hyper-balls. (3) The distance metric is Euclidean. Discussion 4.1 revisits what happens when each of these assumptions is dropped. Figure 6. (a) The data is not globally uniform, but the query q’s neighborhood is roughly uniform on the manifold. (b) The k-NNs of q lie within radius rkr_k; expanding this radius by a factor (1+ε)(1+ ) captures about k(1+ε)dintk(1+ )^d_int points.Two schematic subfigures. Subfigure (a) shows a curved manifold in the ambient space with a query point q, where the small neighborhood around q appears uniformly sampled even though the whole dataset is not. Subfigure (b) shows two concentric balls around q: an inner ball of radius r_k containing the k nearest neighbors, and a slightly larger outer ball obtained by expanding that radius by a factor of one plus epsilon. Dimensionality and Ball Volume. Under the above assumptions, the cost of the exploration phase is proportional to the number of points inside the outer hyper-ball (we revisit this point in Section 4.2).1111 11 Similar measures have been used to estimate query hardness (Zoumpatianos et al., 2018; Ceccarello et al., 2025). The number of such points is proportional to the outer hyper-ball’s volume on the manifold. The volume, in turn, is governed by the manifold’s dimensionality, i.e., the intrinsic dimensionality near the query point (dintd_int), rather than by the ambient dimensionality of the embedding space (dambd_amb). The following theorem counts the points inside the outer hyper-ball in terms of its volume on the manifold. Theorem 1 (Scaling with Intrinsic Dimensionality). Let B(q,r)B(q,r) be the hyper-ball of radius r around query q on the manifold, and let C(r)C(r) be the number of data points inside B(q,r)B(q,r). For any radius r and any ε such that the local uniformity model holds within B(q,(1+ε)r)B(q,(1+ )r), C((1+ε)r)≈(1+ε)dintC(r).C((1+ )r)≈(1+ )^d_int\,C(r). In particular, if rkr_k is the query’s distance to its k-th nearest neighbor, then the expected number of points inside the outer hyper-ball is C((1+ε)rk)≈k(1+ε)dint.C((1+ )r_k)≈ k(1+ )^d_int. Proof. A dintd_int-dimensional hyper-ball has volume proportional to rdintr^d_int (Ball et al., 1997). By assumption, the local uniformity model holds within B(q,(1+ε)r)B(q,(1+ )r), and B(q,r)B(q,r) is contained in it, so the expected number of points in each of the two hyper-balls scales with its volume on the manifold (Figure 6-b). Specifically, we have C((1+ε)r)C(r)≈((1+ε)r)dintrdint=(1+ε)dint. C((1+ )r)C(r)≈ ((1+ )r)^d_intr^d_int=(1+ )^d_int. Setting r=rkr=r_k gives C(rk)≈kC(r_k)≈ k, so C((1+ε)rk)≈k(1+ε)dint.C((1+ )r_k)≈ k(1+ )^d_int. ∎ The base 1+ε1+ can be rewritten as Nlog(1+ε)/logN (1+ )/ N. Substituting this into the factor (1+ε)dint(1+ )^d_int and simplifying the exponent yields the following: Corollary 2 (Scaling with Dataset Size). Under the assumptions of Theorem 1, the expected number of data points inside the outer hyper-ball around the query can be written as C((1+ε)rk)≈kNdintlogNlog(1+ε).C((1+ )r_k)≈ kN d_int N (1+ ). The exponent of N in Corollary 2 depends on dintd_int through the ratio dint/logNd_int/ N, so applying it requires understanding how dintd_int behaves as N grows. Table 3. The order of the query cost falls as N grows. Sparse: dint=Θ(logN)d_int= ( N) Dense: dint=o(logN)d_int=o( N) N:N O(M)O(M)∗ 2Θ(dint)2 (d_int) 22Θ(dint)2^2 (d_int) ≻ Shortcut O(1)O(1) NΘ(1)N (1) No(1)N^o(1) Θ(polylogN) (poly N)† Exploration Θ(N) (N) NΘ(1)N (1) No(1)N^o(1) O(polylogN)O(poly N) Total Θ(N) (N) NΘ(1)N (1) No(1)N^o(1) Θ(polylogN) (poly N) ∗ For M=2o(dint)M=2^o(d_int). † For some graph-based indexes, these expressions are lower bounds on the cost that may not be tight. For example, as argued in Section 4.2.2, SNG’s cost is at least N(1−o(1))/dintN^(1-o(1))/d_int, which is larger than the poly-logarithmic term in the right column. Nevertheless, the table’s expressions are tight for the exactly constructed version of Vamana, intuitively because it behaves like a skip list. LID. We use the local intrinsic dimensionality (LID) as our empirical proxy for dintd_int, as it is computationally feasible and standard in practice (Houle, 2017; Amsaleg et al., 2015; Aumüller and Ceccarello, 2021). LID measures intrinsic dimensionality by how tightly the query’s distances to its nearest neighbors concentrate. The more these distances concentrate around a common value, the higher the intrinsic dimensionality. We estimate LID using the maximum-likelihood estimator (Levina and Bickel, 2004; Aumüller and Ceccarello, 2021) LID^k(q)=−(1k∑i=1klogrirk)−1. LID_k(q)=- ( 1k _i=1^k r_ir_k )^-1. Here, rir_i is the query’s distance to its i-th nearest neighbor. Figure 7 reports how LID changes with N across datasets and values of k. For most datasets, LID follows an approximately straight line when plotted against a logarithmic dataset size, meaning LID grows in step with logN N. Meanwhile, the LID of OpenAI still increases, but with a gradually decreasing slope. The decreasing slope matches Figure 3, where some of OpenAI’s curves deviate slightly from the Sublinear Power Law. SpaceV departs from the linear trend even more significantly than OpenAI: its LID rises at first but then almost flattens. This behavior of SpaceV is consistent with Figure 5, where it deviates from the Sublinear Power Law. Line chart of median local intrinsic dimensionality versus dataset size on a logarithmic axis, one curve per dataset, each with a shaded band marking the 25th to 75th percentiles. Most curves rise roughly linearly with the logarithm of dataset size, while two curves flatten at larger sizes. Figure 7. LID grows roughly with logN N, as the sparse regime predicts. Two datasets deviate and move toward the dense regime. LID is measured over 500 random queries and six values of k; shaded bands mark the 25th–75th percentiles. Line chart of median local intrinsic dimensionality versus dataset size on a logarithmic axis, one curve per dataset, each with a shaded band marking the 25th to 75th percentiles. Most curves rise roughly linearly with the logarithm of dataset size, while two curves flatten at larger sizes. Sparse and Dense Regimes. In principle, dintd_int can take any value from 11 to O(logN)O( N). The upper bound is motivated by the Johnson-Lindenstrauss (JL) lemma (Johnson et al., 1984; Dasgupta and Gupta, 2003). The lemma states that any N points in Euclidean space can be embedded into a space with an ambient dimensionality of O(logN)O( N) while changing every pairwise distance by at most a constant factor. Since dintd_int never exceeds dambd_amb (Dasgupta and Freund, 2008) and a constant-factor change in pairwise distances changes dintd_int by at most a constant factor (Heinonen, 2001; Assouad, 1983), the same bound holds for the original dataset.1212 12 This holds even without the JL embedding: for any set of N points, every ball is covered by N half-radius balls centered at the points, so the doubling dimension, a standard notion of intrinsic dimensionality (Gupta et al., 2003), is O(logN)O( N) (Theorem 3). Motivated by this upper bound on dintd_int, and guided by the LID curves in Figure 7, we define two regimes of interest. In the sparse regime, dintd_int grows proportionally to logN N, i.e., dint=Θ(logN)d_int= ( N). In the dense regime, dintd_int grows more slowly than logN N, i.e., dint=o(logN)d_int=o( N). Later, in Discussion 4.1, we further substantiate these two regimes and analyze the transition between the two. We now apply Corollary 2 to analyze the search cost in each regime as N grows. Sparse Regime: Power-Law. In the sparse regime, dint=Θ(logN)d_int= ( N), so dint=(logN)/ρd_int=( N)/ρ for a constant ρ=Θ(1)ρ= (1). Plugging this into Corollary 2, the expected number of points in the outer hyper-ball is C((1+ε)rk)≈kNdintlogNlog(1+ε)=kNlog(1+ε)/ρ∝Nc.C((1+ )r_k)≈ kN d_int N (1+ )=kN (1+ )/ρ N^c. Notably, c=log(1+ε)/ρc= (1+ )/ρ is a constant independent of N, which explains the power-law scaling of search cost in the sparse regime. Dense Regime: Subpolynomial. In the dense regime, dint=o(logN)d_int=o( N). Plugging this into Corollary 2, the expected number of points in the outer hyper-ball is C((1+ε)rk)≈kNdintlogNlog(1+ε)=kNo(1).C((1+ )r_k)≈ kN d_int N (1+ )=kN^o(1). The exponent dintlogNlog(1+ε) d_int N (1+ ) converges to 0 as N→∞N→∞, so the number of points in the outer hyper-ball grows slower than any power of N, resulting in subpolynomial scaling. Schematic plot of query cost versus dataset size, partitioned into successive regimes. The growth order of the cost decreases from linear at small sizes, through Sublinear Power Laws, to poly-logarithmic at very large sizes. Figure 8. The total query cost falls from Θ(N) (N) to Θ(polylogN) (poly N) as N crosses the regimes of Table 3.Schematic plot of query cost versus dataset size, partitioned into successive regimes. The growth order of the cost decreases from linear at small sizes, through Sublinear Power Laws, to poly-logarithmic at very large sizes. Shortcut Phase. Although the exploration phase empirically accounts for most of the search cost, we analyze the shortcut phase to complete the unifying theory. Unlike the exploration phase, the shortcut phase stretches beyond the neighborhood of the query. Its cost therefore depends also on the global geometry of the dataset. Because of that, the shortcut phase’s cost analysis assumes the data is uniformly distributed on a sphere. Our analysis is presented in Table 3’s first row and the formal proof of our arguments resides in Section 4.2. When the dataset has fewer points than the graph out-degree (N=O(M)N=O(M)), the outer hyper-ball contains the entire dataset, so the search skips straight to the exploration phase and the shortcut phase costs O(1)O(1). When the dataset is larger than the graph out-degree but has not yet saturated the underlying manifold (we later establish the saturation point is 22Θ(dint)2^2 (d_int)), the cost of the shortcut phase grows no faster than that of the exploration phase, as seen in the table. Once the dataset saturates the manifold, the shortcut phase costs Θ(polylogN) (poly N), matching the guarantees established for fixed dimensionality (Subramanya et al., 2019; Lin and Zhao, 2019; Prokhorenkova and Shekhovtsov, 2020). Unifying Theory. We now unify the two search phases into a single account of total search cost for data uniformly distributed on a sphere, summarized in Table 3 and visualized in Figure 8. While N=O(M)N=O(M), the outer hyper-ball contains the entire dataset and the search cost is Θ(N) (N) (Corollary 2). As the dataset grows beyond O(M)O(M) points but stays at most exponential in the intrinsic dimensionality (N=2O(dint)N=2^O(d_int)), the cost follows a power law NcN^c for 0<c<10<c<1. Once the dataset exceeds 2O(dint)2^O(d_int) points, the cost becomes No(1)N^o(1). Beyond 22Θ(dint)2^2 (d_int) points, the outer hyper-ball contains only O(polylogN)O(poly N) points, the shortcut phase therefore governs the scaling, and the cost is Θ(polylogN) (poly N). Discussion 1: Doubling Dimension. The literature offers several estimators for dintd_int, including the doubling dimension, the expansion dimension, and the local intrinsic dimensionality (Houle, 2017; Aumüller and Ceccarello, 2021; Assouad, 1983).1313 13 These measures differ in general, but for smooth data distributions they often coincide (Houle, 2017). We have already used the local intrinsic dimensionality to identify which regime the datasets of Table 2 fall into (Figure 7). We now turn to the doubling dimension, prevalent in theoretical work (Indyk and Xu, 2023; Gupta et al., 2003). Unlike LID, which models the dataset as i.i.d. draws from an underlying smooth distribution, the doubling dimension is defined for any dataset as given, so guarantees proven in terms of it hold for a broader class of inputs. Consider a hyper-ball centered at any dataset point with any radius R. Find the smallest number of non-empty hyper-balls of radius R/2R/2 that can cover all the data points within this hyper-ball. The largest such value over all dataset points and radii R is the doubling constant λ, and the doubling dimension is defined as log2λ _2λ. Computing the value of λ exactly is NP-hard (Gottlieb and Krauthgamer, 2013), so we use the doubling dimension only in our theoretical analysis. Theorem 3 places the data in the sparse regime whenever N is at most exponential in the dimensionality of the underlying manifold. Two rows of histograms of normalized visited-node distances for three datasets, with one curve per dataset size. Top row: the fraction of dataset points visited per distance bucket, with the curves for different sizes nearly coinciding. Bottom row: the absolute number of distance computations per bucket, concentrated just beyond normalized distance one, with a dashed vertical line marking the distance below which 80 percent of the computations occur. Figure 9. Visited-node distance distributions for HNSW across three datasets and three dataset sizes at recall =0.95=~0.95 (M=32M=32, efc=200efc=200, k=10k=10). Distances are normalized by the 10th-N distance. Dashed lines indicate the normalized distance containing 80% of distance computations. Two rows of histograms of normalized visited-node distances for three datasets, with one curve per dataset size. Top row: the fraction of dataset points visited per distance bucket, with the curves for different sizes nearly coinciding. Bottom row: the absolute number of distance computations per bucket, concentrated just beyond normalized distance one, with a dashed vertical line marking the distance below which 80 percent of the computations occur. Theorem 3 (Logarithmic Scaling of the Doubling Dimension). Let P consist of N=2O(d)N=2^O(d) points drawn i.i.d. uniformly from d−1S^d-1. With high probability, the doubling dimension of P is Θ(logN) ( N). Proof. Fix a constant c with N≤2cdN≤ 2^cd and set ε=2−(c+1)≤12 =2^-(c+1)≤ 12. Call a pair of points bad if its distance is at most ε . A fixed pair is bad only if the second point lands in a spherical cap of radius ε around the first, which occupies at most an εd−2 ^d-2 fraction of the sphere. The expected number of bad pairs is thus at most N2εd−2≤N⋅2cd⋅2−(c+1)(d−2)=22c+2−dN^2 ^d-2≤ N· 2^cd· 2^-(c+1)(d-2)=2^2c+2-dN, so by Markov’s inequality, with probability at least 1−22c+3−d=1−2−Ω(d)1-2^2c+3-d=1-2^- (d) there are fewer than N/2N/2 bad pairs. In that case, remove one point of each bad pair and let S be the set of remaining points; then |S|>N/2|S|>N/2, and any two points of S are at distance greater than ε . Every ball can be covered by λ balls of half its radius. Start with a single ball of radius 22, which covers all of P, and halve k times; this covers P by at most λkλ^k balls of radius 21−k2^1-k. After k=⌈log2(4/ε)⌉≤c+4k= _2(4/ ) ≤ c+4 halvings, each ball has diameter at most ε , so it contains at most one point of S. Since all of S must be covered, λk≥|S|>N/2λ^k≥|S|>N/2, hence dim(P)≥(log2N−1)/(c+4)=Ω(logN) (P)≥( _2N-1)/(c+4)= ( N). Also, any ball is covered by the N balls of half its radius centered at the points, so λ≤Nλ≤ N and dim(P)=O(logN) (P)=O( N). ∎ Regime Change. As long as the manifold close to a query point is undersampled, each new point can locally reveal a new geometric direction of the manifold. The growing intrinsic dimensionality of Theorem 3 therefore reflects newly added points progressively resolving the manifold. Once N is large enough to sample every neighborhood densely, new points reveal no new direction, and the intrinsic dimensionality stabilizes. Theorem 3 also suggests where the transition from the sparse to the dense regime occurs: the logarithmic growth of dintd_int only holds while N is at most exponential in the manifold’s dimensionality, and beyond that scale the data enters the dense regime. This aligns with the results of prior work (Niyogi et al., 2008), which shows that resolving the structure of a manifold requires dataset size exponential in the manifold’s dimensionality. Discussion 2: ε Interpretation. As noted earlier in this section, growing the dataset rescales the inner and outer hyper-balls by the same factor. The value of ε should therefore stay stable as the dataset grows. We report whether this holds on three datasets from Table 2; the others exhibit a similar pattern. For each dataset we record every node v that the beam search visits, i.e., every node for which it computes the distance to the query. For each visited node we then compute the normalized distance to the query point: d(q,v)/rkd(q,v)/r_k with k=10k=10. Figure 9 shows the histogram of these normalized distances and reveals how far beyond the true nearest neighbors the search explores to find them. In the top row, in each bucket of the normalized distance, we report the fraction of dataset points that the search process visits. For each dataset, this profile nearly coincides across dataset sizes. The fraction of points the search visits at each normalized distance is therefore scale-invariant. As a result, the outer hyper-ball rescales similarly with the inner hyper-ball, and ε stays stable as the dataset grows. The bottom row shows where the search process spends most of its effort, reporting the absolute number of visited nodes, i.e., distance computations, per bucket. At every dataset size, the cost concentrates in a band of near-ties just beyond the inner hyper-ball. The vertical dashed line marks the normalized distance below which 80%80\% of the distance computations occur, and this threshold stays small at every scale. Discussion 3: Relaxing the Assumptions. We now revisit the three assumptions behind our analysis and examine what changes when they are relaxed. The first assumption is that queries are drawn from the same distribution as the data. When this does not hold, as in out-of-distribution workloads, the outer hyper-ball may intersect multiple manifolds (Brown et al., 2022). In this case, the growth of the exploration phase’s cost is governed by the largest intrinsic dimensionality among the intersected manifolds. The second assumption is that the dataset is sufficiently dense. This ensures that the outer hyper-ball remains small relative to the scale at which the manifold bends. When the dataset is sparse, however, the projection of the hyper-ball onto the manifold may no longer resemble a hyper-ball and can instead take more irregular shapes. This changes the number of points contained in the hyper-ball and, consequently, affects Corollary 2. Nevertheless, the corollary continues to hold as long as the intrinsic dimensionality realized at each scale follows the same trend across the sparse and dense regimes. The same argument applies when the local uniformity model is violated: our analysis remains valid as long as this trend in intrinsic dimensionality is preserved.1414 14 The maximum-likelihood estimator of local intrinsic dimensionality assumes a smooth underlying distribution (Levina and Bickel, 2004), which need not hold in out-of-distribution cases or when the dataset is too sparse. Finally, we assume that the distance metric is Euclidean. If an angular metric is used instead, Euclidean distance between ℓ2 _2-normalized vectors is a strictly increasing function of the angle, so the two metrics induce the same ordering of distances from any query point and, in particular, the same nearest neighbors (Qian et al., 2004; Jain et al., 2016). Even more strongly, the two metrics are locally essentially identical; the outer hyper-ball around the query is therefore unaffected by the choice of metric, and the analysis carries over without modification. 4.2. Theoretical Analysis In Section 4.1, we estimated the search cost of graph-based indexes by empirically tying the search cost to the number of points in the query’s neighborhood. In this section, we rigorously establish the same cost bounds by also accounting for the effect of these graphs’ edges on the search. We analyze the costs of the shortcut and exploration phases in the sparse regime (Section 4.2.1), followed by the dense regime (Section 4.2.2). Together, these analyses establish the bounds of Table 3 and the relevant transition thresholds. Setting. To streamline our exposition, we focus on SNG (Arya and Mount, 1993) in our proofs, and later argue how the same proofs can be adapted to other graph-based indexes such as HNSW (Malkov and Yashunin, 2018) and Vamana (Subramanya et al., 2019). To provide the strongest result possible, we study the query cost of the exact version of SNG and allow the construction to run free of charge. We also discuss how the same results hold for the practical versions of the graph-based indexes in the sparse regime, as long as they are allowed to compute the highest quality neighbors for each node using a candidate list of unbounded size (i.e., efconstruction=∞ef_construction=∞). We analyze the exploration phase under the local uniformity model, where the points within a local neighborhood of a query are approximately uniformly distributed. Since the shortcut phase depends on the global geometry of the data, one cannot prove a non-trivial bound for it in the local uniformity model without additional assumptions. Thus, we restrict the shortcut phase’s analysis to datasets whose points are uniformly distributed on a sphere. Henceforth, we refer to the costs of these two phases in their respective settings as the locally uniform exploration and uniform shortcut costs. 4.2.1. Sparse Regime In the sparse regime, dint=Θ(logN)d_int= ( N). As discussed in Section 4.1, such a value of dintd_int causes the number of points within the approximately uniform neighborhood of a query point to be NcN^c, where N is the dataset size and c∈(0,1]c∈(0,1] is a constant. We now prove that SNG’s locally uniform exploration cost grows as a power law in the size of such a neighborhood, yielding a Sublinear Power Law in N. We then show that the same argument implies that SNG’s uniform shortcut cost grows similarly. Reduction to M-N Graphs or High-Degree Graphs. The central part of our argument shows that, when using SNG to index a set of uniformly distributed points, one of two scenarios occurs: (1) if the maximum degree M is small, SNG connects each node to its M nearest neighbors with high probability, and (2) if M is large, the average node degree follows a power law in N. In the former case, SNG behaves similarly to an M-N graph, which is known to have a power-law search cost (Laarhoven, 2017; Prokhorenkova and Shekhovtsov, 2020). In the latter case, navigating a single node entails computing the distances of a power-law number of neighboring nodes to the query. Together, these cases imply that the uniform shortcut cost and the locally uniform exploration cost follow Sublinear Power Laws in N, giving rise to the leftmost two columns of Table 3. Connection Probability. To prove the above results, we begin by bounding the probability of each node connecting to its k-th nearest neighbor: Lemma 4 (Connection Probability). Consider a node u within a region of the space where points are (approximately) uniformly distributed. Denoting u’s k-th nearest neighbor as vkv_k and letting p∗=dintΘ(1)⋅2−dint/2=logΘ(1)N⋅N−c/2p^*=d_int (1)· 2^-d_int/2= (1)N· N^-c/2, u is connected to vkv_k with a probability of at least 1−2⋅(k−1)⋅p∗1-2·(k-1)· p^* when k≤Mk≤ M. Proof. We observe that the exact version of SNG connects u to its M nearest neighbors that are not pruned. Recall that a node vkv_k is pruned if u is already connected to some other node viv_i with i<ki<k that satisfies d(u,vk)≥d(vi,vk)d(u,v_k)≥ d(v_i,v_k). This corresponds to the neighbor viv_i being included in the “lune” between u and vkv_k, as shown in Figure 1-b. Thus, denoting the lune between u and vkv_k by LkL_k, vkv_k is pruned with a probability of at most Pr[vk pruned] [v_k pruned] =Pr[∃vi,i<k:vi∈Lk] = [∃ v_i,i<k:v_i∈ L_k] ≤∑i=1k−1Pr[u connected to vi∧vi∈Lk] ≤ _i=1^k-1 [u connected to v_i v_i∈ L_k] ≤∑i=1k−1Pr[vi∈Lk]. ≤ _i=1^k-1 [v_i∈ L_k]. Now, we observe that the lune LkL_k is comprised of two spherical caps of height d(u,vk)/2d(u,v_k)/2. The probability of a uniformly distributed point viv_i with i<ki<k being within such a spherical cap is at most the ratio of the volume of this cap to the volume of the hyper-ball of radius d(u,vk)d(u,v_k) around u. This quantity is known to be p∗=dintΘ(1)⋅2−dint/2p^*=d_int (1)· 2^-d_int/2 (Laarhoven, 2017, Lemma 2). Thus, the probability that viv_i is within the lune LkL_k is at most 2⋅p∗2· p^*. Plugging this expression into the sum above yields Pr[vk pruned]≤∑i=1k−12⋅p∗=2⋅(k−1)⋅p∗ [v_k pruned]≤ _i=1^k-12· p^*=2·(k-1)· p^*. Finally, noting that u must be connected to vkv_k if vkv_k is not pruned yields Pr[u connected to vk]=1−Pr[vk pruned]≥1−2⋅(k−1)⋅p∗, [u connected to v_k]=1- [v_k pruned]≥ 1-2·(k-1)· p^*, establishing the lemma. ∎ Lemma 4 has two key consequences in the following two cases of the maximum degree M: Case (1) of Small M. This case leads to a large subgraph of SNG being an M-N graph with high probability within a region of the space where the dataset is approximately uniformly distributed: Theorem 5 (M-N Subgraph). Consider a point x around which the dataset is approximately uniformly distributed. The n=1/(2⋅M2⋅p∗)=Nc/2/(2⋅M2⋅logΘ(1)N)n=1/(2· M^2· p^*)=N^c/2/(2· M^2· (1)N) nearest points to x are connected to their M nearest neighbors with a probability of at least 1/21/2. Proof. By applying a union bound to the connection probability of Lemma 4, it follows that SNG connects a node u to all of its M nearest neighbors with a probability of at least 1−M2⋅p∗=1−M2⋅logΘ(1)N⋅N−c/21-M^2· p^*=1-M^2· (1)N· N^-c/2. Through another union bound, this implies that all of the n=Nc/2/(2⋅M2⋅logΘ(1)N)n=N^c/2/(2· M^2· (1)N) nearest points to x must be connected to their M nearest neighbors with a probability of at least 1/21/2. ∎ When M=No(1)M=N^o(1), Theorem 5 implies that in the subgraph of SNG restricted to the Nc/2−o(1)N^c/2-o(1) nearest points of x, denoted by G¯ G, each node is connected to at most M of its nearest neighbors. Since the points in G¯ G are uniformly distributed, this intuitively implies that each of its nodes is connected to at most M other nodes that are “random,” meaning that they may or may not aid in navigating closer to a query. In such a scenario, the search must traverse many nodes and compare the distances of many points to the query to find its nearest neighbor with a non-trivial probability. This intuition is formalized in (Laarhoven, 2017), where the author shows that using greedy search on an M-N graph1515 15 More precisely, the graph the author of (Laarhoven, 2017) analyzes connects any two nodes that are within a tunable distance threshold. This thresholding causes the nodes of this graph to have variable degrees rather than strictly bounded degrees. Nevertheless, the proofs of (Laarhoven, 2017) can be adapted to the setting where the degree is strictly bounded by M. to reach a node that is at most a constant factor farther than a query’s true nearest neighbor entails a number of distance computations that follows a Sublinear Power Law in the graph’s size.1616 16 Specifically, instead of classic beam search, (Laarhoven, 2017) analyzes a query algorithm where the search procedure restarts from a random node when it converges to a local minimum. Nevertheless, one can analyze beam search using a similar approach to random restarts. A slight adaptation of their proof would extend their result to any graph where each node is connected to some number of its nearest neighbors that is less than or equal to M. To analyze SNG’s uniform shortcut cost, we consider the subgraph G¯entry G_entry around SNG’s entry point and apply Theorem 5. Then, by invoking the result of (Laarhoven, 2017) for G¯entry G_entry, we derive the cost as a power law in the size of the entry point’s neighborhood, i.e., NcN^c for some constant c∈(0,1]c∈(0,1]. As discussed at the beginning of this section, this corresponds to a Sublinear Power Law in N. Similarly, to analyze SNG’s locally uniform exploration cost, we consider the subgraph G¯q G_q around the query q and leverage the approximately uniform distribution of its points to apply Theorem 5. This allows us to once again invoke the result of (Laarhoven, 2017) to show that the cost follows a power law in N. Case (2) of Large M. In this case, each node within the approximately uniform neighborhood of the query q has a high degree with high probability: Theorem 6 (High-Degree Graph). When the dataset is uniformly distributed and M=NΘ(1)M=N (1), each node within the uniform neighborhood of a query q has a degree of at least min(M,Nc/4−o(1))=NΘ(1) (M,N^c/4-o(1))=N (1) with a probability of at least 1/21/2. Proof. If M=NΘ(1)<Nc/4/(2⋅logΘ(1)N)M=N (1)<N^c/4/(2· (1)N), a similar union bound to that of Theorem 5 applied to the connection probability of Lemma 4 shows that any node u will be connected to its M=NΘ(1)M=N (1) nearest neighbors with a probability of at least 1/21/2. If M≥Nc/4/(2⋅logΘ(1)N)M≥ N^c/4/(2· (1)N), by the same union bound, any node u will be connected to its Nc/4/(2⋅logΘ(1)N)N^c/4/(2· (1)N) nearest neighbors with a probability of at least 1/21/2. ∎ Theorem 6 implies that, for both the uniform shortcut cost and the locally uniform exploration cost, processing even a single node entails a number of distance computations that follows a power law in N. As such, the results in the two columns on the left of Table 3 hold in both cases of M. Note that the uniform shortcut cost in the leftmost column is constant since, in that setting, Theorem 5 implies that all nodes are connected to each other, so the search begins in the exploration phase and skips the shortcut phase. Extension to Other Graph-based Indexes. The exact versions of the major graph-based indexes, such as HNSW, Vamana, and τ-MG, employ pruning rules at least as strict as that of SNG. As such, an analogue of Lemma 4 holds for them with a probability bound that is at least as high. This implies that the same conclusions as those of Theorems 5 and 6 hold for these graphs, as these results only depend on the bounds of Lemma 4. For the practical versions of these graphs, when allowed to find the highest quality neighbors of each node using an unbounded candidate list (i.e., efconstruction=∞ef_construction=∞), the same Sublinear Power Law results hold.1717 17 Here, we consider incremental insertion as most practical graph indexes are implemented accordingly. The reason is two-fold: (1) When the maximum degree M is small, the same analysis as Lemma 4 shows that, with high probability, each node after the first M nodes is connected to the M nearest nodes from those that were inserted earlier. This does not affect our use of the results in (Laarhoven, 2017), as it only slightly alters the probability of the search encountering a local minimum. (2) When M is large, Lemma 4 applied to the N/2N/2 points inserted later during construction implies that their degrees must be asymptotically as large as that of Theorem 6. Thus, processing even one of these nodes, which happens with a constant probability, incurs a power-law cost. 4.2.2. Dense Regime We now turn to the dense regime and analyze the uniform shortcut and locally uniform exploration costs. We begin by showing that the node degree is negligible in this regime, which leaves the bulk of the search costs to the number of steps. We lower bound the number of shortcut steps by analyzing the average progress each step makes towards the query. For the locally uniform exploration cost, we simply bound the number of points within a query’s neighborhood. Node Degree. As proven in (Indyk and Xu, 2023, Lemma 3.3), the degree of a node in Vamana is at most O(2Θ(dint)⋅polylogN)O(2 (d_int)·poly N).1818 18 The poly-logarithmic term corresponds to logΔ in (Indyk and Xu, 2023, Lemma 3.3), where Δ is the ratio between the longest and shortest pairwise distances of points in the dataset. We have assumed that Δ=poly(N) =poly(N) to reflect real-world datasets. We further observe that applying the same lemma with a value of α=1α=1 shows that the degree of each node in SNG or HNSW is at most O(2Θ(dint))O(2 (d_int)). Since, as described in Section 4.1, dint=o(logN)d_int=o( N) in the dense regime, we get the following lemma: Lemma 7 (Negligible Degree). In the dense regime, the degree of any node in SNG, HNSW, or Vamana is at most O(2Θ(dint)⋅polylogN)=No(logN)/logN⋅polylogN=No(1)O(2 (d_int)·poly N)=N^o( N)/ N·poly N=N^o(1). Lemma 7 posits that processing a single node, be it in the shortcut phase or the exploration phase, takes No(1)N^o(1) time. In particular, when N≥22dintN≥ 2^2^d_int, we have dint=O(loglogN)d_int=O( N), which implies that the degree of each node is at most O(2O(loglogN))=O(polylogN)O(2^O( N))=O(poly N). This establishes that the uniform shortcut and locally uniform exploration costs are at least as large as the expressions in the right two columns of Table 3. We now discuss upper bounds on these costs by analyzing the number of nodes processed in each phase. Uniform Shortcut Cost. For Vamana, it is known that each step of the shortcut phase takes the search closer to any query q by a constant factor (Indyk and Xu, 2023). From (Laarhoven, 2017, Lemma 2), we observe that the nearest neighbor of any query q is within an expected distance of N−Θ(1/dint)N^- (1/d_int) of it, implying that the outer hyper-ball around q must have a radius of O(N−Θ(1/dint))O(N^- (1/d_int)). Thus, since the distance from the graph’s entry point to q is at most a constant when the points are distributed on a sphere, the number of shortcut steps is at most O(logO(1)O(N−Θ(1/dint)))=Θ((1/dint)⋅polylogN)O( O(1)O(N^- (1/d_int)))= ((1/d_int)·poly N). Multiplying by each node’s degree, one derives upper bounds matching the expressions in the two columns on the right of Table 3. Compared to Vamana, upper bounding SNG and HNSW’s uniform shortcut costs is more complex. In fact, we show the number of steps in SNG’s shortcut phase is at least Ω(N−1/dint) (N^-1/d_int), i.e., significantly higher than Vamana’s poly-logarithmic number of steps. Our argument quantifies the average progress each search step makes: Lemma 8 (SNG Maximum Progress). In SNG’s shortcut phase on a dataset of N points uniformly distributed on a sphere, with high probability, all steps that take the search closer to a query q reduce the distance to q by at most poly(dint)⋅(logN)1/dintpoly(d_int)· ( NN )^1/d_int. Proof. Our argument analyzes the maximum length of an edge in SNG. Recall that if two nodes u and v are connected, then there must be no other node in their lune. By (Laarhoven, 2017, Lemma 2), the probability that a node w is within u and v’s lune is poly(dint)⋅d(u,v)dintpoly(d_int)· d(u,v)^d_int. When d(u,v)=(logN)1/dintd(u,v)= ( NN )^1/d_int, this probability becomes poly(dint)⋅logNpoly(d_int)· NN, i.e., the expected number of nodes within the lune is Ω(logN) ( N). By applying a standard Chernoff bound, it follows that such a lune is empty with a probability of at most 1/N31/N^3. Thus, by a union bound over all pairs of nodes, we can conclude that all edges within SNG have a length of at most poly(dint)⋅(logN)1/dintpoly(d_int)· ( NN )^1/d_int with high probability. Therefore, any edge that brings the search closer to a query must also be at most this long. ∎ As discussed above, the radius of a query’s outer hyper-ball is O(N−1/dint)O(N^-1/d_int) in expectation. Thus, since the distance from the entry point to a query can be a constant number, Lemma 8 implies that the shortcut phase requires at least O(1)poly(dint)⋅(logN/N)1/dint=Ω(N(1−o(1))/dint) O(1)poly(d_int)·( N/N)^1/d_int= (N^(1-o(1))/d_int) many steps to reach the outer hyper-ball. The actual number of steps required to reach this hyper-ball may be larger than this quantity, since beam search may run into local minima which prevent it from making progress towards a query. Since each layer of HNSW behaves similarly to SNG, similar concerns around an upper bound on its search cost persist. We leave deriving a tight upper bound for SNG and HNSW as an interesting open question for future work. Locally Uniform Exploration Cost. The exploration phase in any graph-based index searches at most all nodes within the locally uniform neighborhood of a query. Thus, the number of steps in the exploration phase is upper bounded by the number of nodes in this neighborhood. Since dint=o(logN)d_int=o( N) in the dense regime, Theorem 1 implies that the number of nodes in the query’s uniform neighborhood is at most 2dint=Ndint/logN=No(1)2^d_int=N^d_int/ N=N^o(1). Multiplied by the degree of a node (quantified in Lemma 7), this yields a locally uniform exploration cost of No(1)N^o(1), matching the third column of Table 3. Moreover, when N≥22Θ(dint)N≥ 2^2 (d_int), we have dint=O(loglogN)d_int=O( N), making the number of nodes in the query’s neighborhood poly-logarithmic in N. Multiplied by the node degree (Lemma 7), which is poly-logarithmic in this case, we derive a poly-logarithmic cost for the exploration phase. Thus, the bound in the fourth column of Table 3 also holds. Figure 10. Partial regression plots for the query-, insertion-, and beam-width-cost models; each subfigure shows the partial residual after removing all other fitted terms, so the fitted slope equals the associated model coefficient. (a) Query-side model of Eq. 2: the effects of ln(1/δ) (1/δ), ln(efconstruction) (ef_construction), and lnM M on the scaling exponent c. (b) Insertion-cost model of Eq. 4: the effects of ln(efconstruction) (ef_construction), lnN N, and the interaction ln(M)ln(N) (M) (N) on average insertion cost ln(dcbuild/N) (dc_build/N). (c) Beam-width model of Eq. 3: ln(efsearch) (ef_search) vs. ln(dc/q) (dc/q), centered within each configuration; the linear pattern confirms the power law with slope β. Three groups of partial-regression scatter plots, each with a fitted straight line. Group (a) shows the effects of recall, construction beam width, and degree bound on the query scaling exponent. Group (b) shows the effects of construction beam width, dataset size, and their interaction on average insertion cost. Group (c) plots search beam width against per-query distance computations. In all subfigures the points cluster tightly around the fitted lines. 5. Cost Modeling The previous sections established that, across many datasets and scales, query cost follows a Sublinear Power Law in the dataset size N, with exponent c, and explained why. A natural next step is to predict the exponent, so that its scaling is known before the data grows. This section develops such models empirically for query cost (Section 5.1) and insertion cost (Section 5.2). Together, they cover the parameter ranges of practical interest and expose the trade-offs between query cost, insertion cost, and recall. 5.1. Modeling Query Cost We begin with query cost, asking what determines the exponent c for a given dataset. Our approach is to model how c varies with the recall target and the construction parameters of the index, and then to connect the predicted cost back to the efsearchef_search value that realizes it. Parameters. We focus on three parameters that govern how c varies for a given dataset. The first is the recall target. A higher target leaves less room to miss a true nearest neighbor, so the search process must cover more of the local neighborhood and widen its candidate list. The other two are the construction list size efconstructionef_construction and the maximum out-degree M, which together set the quality of the graph and the number of edges it carries. Those edges act as shortcuts that bring every query within fewer hops of its neighborhood, at the cost of more work during construction. Expected Effects. Increasing recall should raise c, but the rise is not linear in recall. Raising recall from 0.900.90 to 0.920.92 barely makes ANN search harder, but raising it from 0.970.97 to 0.990.99 does. To capture the nonlinearity, we quantify the demand for recall as 1/δ1/δ, where δ=1−recallδ=1-recall. In the previous example, the first increment raises 1/δ1/δ from 1010 to 12.512.5, while the second raises it from 33.333.3 to 100100. On the other hand, increasing the construction parameters should lower c, since a denser graph offers more reliable routes into and within the query’s neighborhood. This benefit should diminish and eventually turn harmful: once the graph is dense enough, additional edges add little routing power while inflating the search cost per step. Across the parameter ranges we study (recall up to 0.990.99, efconstruction∈[100,800]ef_construction∈[100,800], M∈[16,128]M∈[16,128]), this reversal never appears, and we observe c decreasing throughout. Table 4. Fitted parameters and goodness of fit per dataset and algorithm. (a) Query cost model: coefficients of Eq. 2 and the exponent β of Eq. 3, with Rc2R^2_c and Rβ2R^2_β the respective fits. (b) Build cost model: coefficients of Eq. 4. (a) Query cost model (b) Build cost model Dataset c0c_0 α γ1 _1 γ2 _2 β Rc2R^2_c Rβ2R^2_β κ β′β c0′c _0 γ2′γ _2 R2R^2 HNSW sift .244 .035 .012 .022 .762 .919 .992 2.497 .864 −-.031 .020 .979 deep .281 .054 .020 .022 .742 .934 .992 2.163 .880 −-.048 .018 .983 spacev .181 .067 .020 .017 .747 .818 .992 2.653 .900 −-.002 .024 .963 wiki .310 .079 .037 .022 .737 .886 .991 2.424 .869 −-.032 .018 .991 glove .336 .090 .036 .012 .759 .916 .993 2.147 .917 −-.052 .023 .977 rand64 1.068 .022 .055 .082 .812 .912 .992 3.569 .681 −-.028 .044 .922 gist .513 .096 .045 .017 .705 .859 .992 1.268 .836 −-.155 .015 .991 openai .191 .079 .029 .001 .741 .910 .992 2.197 .858 −-.063 .019 .981 Vamana sift .415 .046 .014 .069 .752 .841 .992 3.622 .826 −-.076 .041 .977 deep .479 .064 .021 .080 .730 .869 .992 3.388 .843 −-.064 .038 .973 spacev .351 .074 .021 .066 .739 .825 .991 4.253 .857 −-.168 .055 .976 wiki .447 .086 .036 .068 .742 .845 .992 3.137 .859 −-.059 .037 .986 glove .480 .086 .027 .059 .760 .835 .993 3.977 .857 −-.159 .063 .990 rand64 1.252 .020 .059 .111 .833 .929 .993 5.239 .764 −-.233 .076 .996 gist .670 .108 .026 .098 .706 .782 .991 2.654 .797 −-.018 .046 .985 openai .334 .081 .025 .046 .714 .947 .991 4.492 .818 −-.177 .057 .983 Modeling the exponent c. The simplest model consistent with these effects treats them as independent: each parameter contributes its own term, and the exponent c is their sum. Figure 10-a supports this decomposition empirically. Each column isolates the effect of one factor on the exponent (1/δ1/δ, efconstructionef_construction, M). We subtract the fitted contributions of the other two, and plot what remains, the partial residual, against the factor in question. In each case the partial residual is approximately linear when the factor is shown on a logarithmic scale, so each factor contributes an additive logarithmic term to the exponent. We therefore model the scaling exponent as (2) c=c0+αln(1δ)−γ1ln(efconstruction)−γ2ln(M).c\;=\;c_0\;+\;α\, \! ( 1δ )\;-\; _1\, (ef_construction)\;-\; _2\, (M). Here c0c_0 is the baseline set by the dataset’s geometry, α the cost of higher demand for recall, and γ1 _1 and γ2 _2 the benefits of efconstructionef_construction and M, respectively. Goodness of fit. We fit the model separately for each dataset and index construction algorithm. Table 4-a reports the fitted coefficients and goodness of fit. The model achieves an average R2R^2 of approximately 0.880.88, meaning it explains about 88%88\% of the variation in the measured exponent across datasets and algorithms. The fitted coefficients are consistent with the slopes in Figure 10-a, showing the additive log-linear structure directly on the data. Effect of efsearchef_search. The model above explains how fast the number of distance computations scales as the dataset grows, i.e., how large the exponent c is for a given recall level and construction parameters. It leaves open a practical question: for a dataset of a given size, how should the candidate list size during search, efsearchef_search, be tuned so that the search performs the distance computations predicted by Equation 2 and thus reaches the recall target? We answer this by observing that, for a given graph-based index, distance computations per query scale as a Sublinear Power Law in efsearchef_search: (3) dc/q∝efsearchβ.dc/q\; \;ef_search^\,β. Figure 10-c shows this relationship on log-log axes, where the linear pattern indicates a power law, this time between efsearchef_search and the number of distance computations. The fit is tight across all datasets, with R2>0.98R^2>0.98 as reported in Table 4-a. 5.2. Modeling Insertion Cost As discussed in Section 2, the insertion process runs a beam search to locate the new point’s neighbors. This beam search performs the same distance computations that govern query cost, and it dominates the cost of insertion (Malkov and Yashunin, 2018; Subramanya et al., 2019). We therefore measure the total number of distance computations during index construction, denoted dcbuilddc_build, and study how the average insertion cost dcbuild/Ndc_build/N changes with the dataset size and the construction parameters. Parameters. Since insertion runs the same beam search as a query, the insertion cost model shares the structure of the query cost models. The key difference is that insertion has no recall target, so recall demand drops out of the model. The parameters are the dataset size N and the two construction parameters, the graph out-degree M and the candidate list size efconstructionef_construction. Expected Effects. A larger N means each new point searches a larger graph, so insertion cost should rise with the dataset, and since query cost rises with N as a Sublinear Power Law, we expect insertion cost to do the same; we empirically verify this power law. A larger efconstructionef_construction makes each insertion explore more of the graph before identifying the new node’s neighbors, so, just as query cost scales as efsearchβef_search^\,β (Equation 3), insertion cost should grow as a Sublinear Power Law in efconstructionef_construction. A higher M forces the beam search to scan more candidates per step, but may also help it converge in fewer steps; the net effect is settled empirically. Modeling the Scaling. Figure 10-b isolates each effect through partial regressions, as in Section 5.1. At fixed M, the average insertion cost is log-linear in both efconstructionef_construction and N, as anticipated, verifying the power-law scaling on both counts. Raising M increases the power-law exponent of N, so a denser graph makes build cost grow faster with dataset size; M therefore belongs inside the exponent of N. We thus model (4) dcbuild=eκ(efconstruction)β′Nc′,c′=1+c0′+γ2′lnM.dc_build=e^κ\,(ef_construction)^β \,N^\,c , c =1+c _0+γ _2 M. Equivalently, ln(dcbuildN)=κ+β′ln(efconstruction)+c0′lnN+γ2′ln(M)ln(N). \! ( dc_buildN )=κ+β (ef_construction)+c _0 N+γ _2 (M) (N). The primed symbols mark build-phase analogues of the query model’s coefficients of Section 5.1. The build exponent c′c explains how construction cost scales with the dataset size N, the build-phase analogue of the query exponent c. Within c′c , the leading 11 is the trivial cost of performing N insertions, c0′c _0 captures how per-insertion search cost grows with index size, and γ2′γ _2 captures how a larger M steepens that growth. The intercept κ depends on the data geometry and the graph construction algorithm, and β′β is the analogue of β in Equation 3, the exponent of the candidate list size. Goodness of Fit. Table 4-b lists the fitted coefficients for HNSW and Vamana. The fits are tight (R2≥92%R^2≥ 92\%), and the slopes we recover line up with the partial regressions in Figure 10-b. Except for the synthetic Rand64 dataset, β′β sits in a fairly narrow band, 0.800.80–0.920.92, running 0.070.07–0.160.16 above β. In other words, doubling efconstructionef_construction raises the average insertion cost by about 1.8×1.8×. Insertion is thus more sensitive to its candidate list size than query cost is to efsearchef_search (Equation 3). This gap comes from the extra distance computations insertion has to do beyond plain beam search, mostly reverse-link rewiring. This rewiring is triggered whenever a candidate neighbor has already hit its degree budget. Rand64 breaks this pattern: insertion is less sensitive to candidate list size than search, with β′β (0.680.68–0.760.76) staying below β (0.810.81–0.830.83). 6. Conclusion The literature has long held that, at fixed recall, the query cost of graph-based indexes scales poly-logarithmically. Our experiments and theory confine this claim to scales beyond a transition point. Below that point, cost follows a Sublinear Power Law, growing in step with NcN^c, and most datasets in practice stay in this regime up to 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 only once the dataset densely samples its underlying distribution. Our unifying theory explains both regimes through the intrinsic dimensionality the dataset exhibits at its current size, reconciling our measurements with the logarithmic claims as two regimes of the same scaling law. The resulting cost models let practitioners set index parameters in a principled way and sustain a recall target as the dataset grows. References Amsaleg et al. (2015) Laurent Amsaleg, Oussama Chelly, Teddy Furon, Stéphane Girard, Michael E. Houle, Ken-ichi Kawarabayashi, and Michael Nett. 2015. Estimating Local Intrinsic Dimensionality. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Sydney, NSW, Australia) (KDD ’15). Association for Computing Machinery, New York, NY, USA, 29–38. https://doi.org/10.1145/2783258.2783405 Arya and Mount (1993) Sunil Arya and David M. Mount. 1993. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Austin, Texas, USA) (SODA ’93). Society for Industrial and Applied Mathematics, USA, 271–280. Assouad (1983) Patrice Assouad. 1983. Plongements lipschitziens dans ℝnR^n. Bulletin de la Société Mathématique de France 111 (1983), 429–448. Aumüller et al. (2020) Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020), 101374. Aumüller and Ceccarello (2021) Martin Aumüller and Matteo Ceccarello. 2021. The Role of Local Dimensionality Measures in Benchmarking Nearest Neighbor Search. Information Systems 101 (2021), 101807. https://doi.org/10.1016/j.is.2021.101807 Babenko and Lempitsky (2016) Artem Babenko and Victor Lempitsky. 2016. Efficient indexing of billion-scale datasets of deep descriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2055–2063. Baevski et al. (2020) Alexei Baevski, Henry Zhou, Abdelrahman Mohamed, and Michael Auli. 2020. wav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations. arXiv:2006.11477 [cs.CL] https://arxiv.org/abs/2006.11477 Ball et al. (1997) Keith Ball et al. 1997. An elementary introduction to modern convex geometry. Flavors of geometry 31, 1-58 (1997), 26. Baranchuk et al. (2023) Dmitry Baranchuk, Matthijs Douze, Yash Upadhyay, and I Zeki Yalniz. 2023. Dedrift: Robust similarity search under content drift. In Proceedings of the IEEE/CVF International Conference on Computer Vision. 11026–11035. Bentley (1975) Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509–517. Beyer et al. (1999a) Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999a. When is “nearest neighbor” meaningful?. In International conference on database theory. Springer, 217–235. Beyer et al. (1999b) Kevin S. Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999b. When Is ”Nearest Neighbor” Meaningful?. In Proceedings of the 7th International Conference on Database Theory (ICDT ’99). Springer-Verlag, Berlin, Heidelberg, 217–235. Böhm (2000) Christian Böhm. 2000. A cost model for query processing in high dimensional data spaces. ACM Transactions on Database Systems (TODS) 25, 2 (2000), 129–178. Borodin et al. (1999) Allan Borodin, Rafail Ostrovsky, and Yuval Rabani. 1999. Lower bounds for high dimensional nearest neighbor search and related problems. In Proceedings of the thirty-first annual ACM symposium on Theory of computing. 312–321. Bringmann (2021) Karl Bringmann. 2021. Fine-grained complexity theory: Conditional lower bounds for computational geometry. In Conference on Computability in Europe. Springer, 60–70. Brown et al. (2022) Bradley CA Brown, Anthony L Caterini, Brendan Leigh Ross, Jesse C Cresswell, and Gabriel Loaiza-Ganem. 2022. Verifying the union of manifolds hypothesis for image data. arXiv preprint arXiv:2207.02862 (2022). Cai et al. (2013) T Tony Cai, Jianqing Fan, and Tiefeng Jiang. 2013. Distributions of angles in random packing on spheres. Journal of Machine Learning Research 14, 136 (2013), 1837–1864. Ceccarello et al. (2025) Matteo Ceccarello, Alexandra Levchenko, Ioana Ileana, and Themis Palpanas. 2025. Evaluating and generating query workloads for high dimensional vector similarity search. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2. 5299–5310. Chatzakis et al. (2025) Manos Chatzakis, Yannis Papakonstantinou, and Themis Palpanas. 2025. Darth: Declarative recall through early termination for approximate nearest neighbor search. Proceedings of the ACM on Management of Data 3, 4 (2025), 1–26. Chen et al. (2023) Patrick Chen, Wei-Cheng Chang, Jyun-Yu Jiang, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. 2023. Finger: Fast inference for graph-based approximate nearest neighbor search. In Proceedings of the ACM Web Conference 2023. 3225–3235. Chronis et al. (2025) Yannis Chronis, Helena Caminal, Yannis Papakonstantinou, Fatma Özcan, and Anastasia Ailamaki. 2025. Filtered vector search: State-of-the-art and research opportunities. Proceedings of the VLDB Endowment 18, 12 (2025), 5488–5492. Covington et al. (2016) Paul Covington, Jay Adams, and Emre Sargin. 2016. Deep neural networks for youtube recommendations. In Proceedings of the 10th ACM conference on recommender systems. 191–198. Dasgupta and Freund (2008) Sanjoy Dasgupta and Yoav Freund. 2008. Random projection trees and low dimensional manifolds. In Proceedings of the fortieth annual ACM symposium on Theory of computing. 537–546. Dasgupta and Gupta (2003) Sanjoy Dasgupta and Anupam Gupta. 2003. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures & Algorithms 22, 1 (2003), 60–65. Diwan et al. (2024) Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. 2024. Navigable graphs for high-dimensional nearest neighbor search: Constructions and limits. Advances in Neural Information Processing Systems 37 (2024), 59513–59531. Douze et al. (2025) Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2025. The Faiss library. arXiv:2401.08281 [cs.LG] https://arxiv.org/abs/2401.08281 Duan et al. (2025) Hao Duan, Yitong Song, Bin Yao, and Anqi Liang. 2025. PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs. Proceedings of the ACM on Management of Data 3, 4 (2025), 1–27. Elastic ([n.d.]) Elastic. [n.d.]. Measuring the Recall of Quantized Vector Search. https://w.elastic.co/search-labs/blog/recall-vector-search-quantization. Elasticsearch Labs blog. Accessed: 2026-07-21. Elastic (2024) Elastic. 2024. Vector Search and kNN Implementation Guide. https://w.elastic.co/search-labs/blog/vector-search-implementation-guide-api-edition Accessed: 2026-04-22. Fefferman et al. (2016) Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. 2016. Testing the manifold hypothesis. Journal of the American Mathematical Society 29, 4 (2016), 983–1049. Fu et al. (2021) Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 8 (2021), 4139–4150. Fu et al. (2025) Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2025. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. arXiv:1707.00143 [cs.LG] https://arxiv.org/abs/1707.00143 Gao and Long (2023) Jianyang Gao and Cheng Long. 2023. High-dimensional approximate nearest neighbor search: with reliable and efficient distance comparison operations. Proceedings of the ACM on Management of Data 1, 2 (2023), 1–27. Gao et al. (2023) Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yixin Dai, Jiawei Sun, Haofen Wang, and Haofen Wang. 2023. Retrieval-augmented generation for large language models: A survey. arXiv preprint arXiv:2312.10997 2, 1 (2023). Gottlieb and Krauthgamer (2013) Lee-Ad Gottlieb and Robert Krauthgamer. 2013. Proximity algorithms for nearly doubling spaces. SIAM Journal on Discrete Mathematics 27, 4 (2013), 1759–1769. Gupta et al. (2003) Anupam Gupta, Robert Krauthgamer, and James R Lee. 2003. Bounded geometries, fractals, and low-distortion embeddings. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE, 534–543. Guttman (1984) Antonin Guttman. 1984. R-trees: a dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data (Boston, Massachusetts) (SIGMOD ’84). Association for Computing Machinery, New York, NY, USA, 47–57. https://doi.org/10.1145/602259.602266 He et al. (2012) Junfeng He, Sanjiv Kumar, and Shih-Fu Chang. 2012. On the Difficulty of Nearest Neighbor Search. arXiv:1206.6411 [cs.LG] https://arxiv.org/abs/1206.6411 Heinonen (2001) Juha Heinonen. 2001. Lectures on Analysis on Metric Spaces. Springer-Verlag, New York. https://doi.org/10.1007/978-1-4613-0131-8 Houle (2017) Michael E Houle. 2017. Local intrinsic dimensionality I: an extreme-value-theoretic foundation for similarity applications. In International Conference on Similarity Search and Applications. Springer, 64–79. Indyk and Motwani (1998) Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. 604–613. Indyk and Xu (2023) Piotr Indyk and Haike Xu. 2023. Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations. Advances in Neural Information Processing Systems 36 (2023), 66239–66256. Jäsaari et al. (2025) Elias Jäsaari, Ville Hyvönen, Matteo Ceccarello, Teemu Roos, and Martin Aumüller. 2025. VIBE: vector index benchmark for embeddings. arXiv preprint arXiv:2505.17810 (2025). Jain et al. (2016) Himalaya Jain, Patrick Pérez, Rémi Gribonval, Joaquin Zepeda, and Hervé Jégou. 2016. Approximate Search with Quantized Sparse Representations. In Computer Vision – ECCV 2016 (Lecture Notes in Computer Science), Vol. 9911. Springer, 681–696. https://doi.org/10.1007/978-3-319-46478-7_42 Jaromczyk and Kowaluk (1987) Jerzy W Jaromczyk and Miroslaw Kowaluk. 1987. A note on relative neighborhood graphs. In Proceedings of the third annual symposium on Computational geometry. 233–241. Jegou et al. (2011) Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2011. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2011), 117–128. Jégou et al. (2011) Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011. Searching in one billion vectors: re-rank with source coding. In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 861–864. Jing et al. (2025) Zhi Jing, Yongye Su, and Yikun Han. 2025. When large language models meet vector databases: A survey. In 2025 Conference on Artificial Intelligence x Multimedia (AIxMM). IEEE, 7–13. Johnson et al. (1984) William B Johnson, Joram Lindenstrauss, et al. 1984. Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics 26, 189-206 (1984), 1. Joshi ([n.d.]) Satyadhar Joshi. [n.d.]. Introduction to Vector Databases for Generative AI: Applications, Performance, Future Projections, and Cost Considerations. International Advanced Research Journal in Science, Engineering and Technology ISSN (O) ([n. d.]), 2393–8021. Kane (2023) Andrew Kane. 2023. pgvector: Vector Similarity Search for PostgreSQL. https://github.com/pgvector/pgvector. Open-source PostgreSQL extension for vector similarity search. Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 conference on empirical methods in natural language processing (EMNLP). 6769–6781. Laarhoven (2017) Thijs Laarhoven. 2017. Graph-based time-space trade-offs for approximate near neighbors. arXiv preprint arXiv:1712.03158 (2017). Levina and Bickel (2004) Elizaveta Levina and Peter Bickel. 2004. Maximum likelihood estimation of intrinsic dimension. Advances in neural information processing systems 17 (2004). Li et al. (2026) Binhong Li, Xiao Yan, and Shangqi Lu. 2026. Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 4, 1 (SIGMOD (2026), 1–24. Li et al. (2020) Conglong Li, Minjia Zhang, David G. Andersen, and Yuxiong He. 2020. Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (Portland, OR, USA) (SIGMOD ’20). Association for Computing Machinery, New York, NY, USA, 2539–2554. https://doi.org/10.1145/3318464.3380600 Li and Malik (2017) Ke Li and Jitendra Malik. 2017. Fast k-nearest neighbour search via prioritized DCI. In International conference on machine learning. PMLR, 2081–2090. Lin and Zhao (2019) Peng-Cheng Lin and Wan-Lei Zhao. 2019. Graph based nearest neighbor search: Promises and failures. arXiv preprint arXiv:1904.02077 (2019). Lowe (2004) David G. Lowe. 2004. Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision 60, 2 (2004), 91–110. Lu et al. (2026) Jianan Lu, Asaf Cidon, and Michael J. Freedman. 2026. When Enough is Enough: Rank-Aware Early Termination for Vector Search. In Proceedings of the 9th MLSys Conference. Bellevue, WA, USA. https://w.cs.princeton.edu/~mfreed/docs/terminus-mlsys26.pdf Lu et al. (2024) Kejing Lu, Chuan Xiao, and Yoshiharu Ishikawa. 2024. Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search. In Proceedings of the 41st International Conference on Machine Learning (Proceedings of Machine Learning Research), Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (Eds.), Vol. 235. PMLR, 33177–33195. https://proceedings.mlr.press/v235/lu24l.html Ma et al. (2025) Xinran Ma, Zhaoqi Zhou, Chuan Zhou, Qi Meng, Zaijiu Shang, Guoliang Li, and Zhiming Ma. 2025. Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization. arXiv preprint arXiv:2509.15531 (2025). Malkov et al. (2014) Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61–68. Malkov and Yashunin (2018) Yu. A. Malkov and D. A. Yashunin. 2018. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. arXiv:1603.09320 [cs.DS] https://arxiv.org/abs/1603.09320 Manohar et al. (2024) Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. Parlayann: Scalable and deterministic parallel graph-based approximate nearest neighbor search algorithms. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 270–285. McInnes et al. (2018) Leland McInnes, John Healy, and James Melville. 2018. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426 (2018). Microsoft (2021) Microsoft. 2021. SPACEV1B: A Billion-Scale Vector Dataset for Text Descriptors. https://github.com/microsoft/SPTAG/tree/main/datasets/SPACEV1B. Accessed July 2026. Microsoft (2026) Microsoft. 2026. DiskANN: Graph-Structured Indices for Scalable, Fast, Fresh and Filtered Approximate Nearest Neighbor Search. https://github.com/microsoft/DiskANN. Accessed: 2026-07-15. Milvus (2024) Milvus. 2024. Index Explained. https://milvus.io/docs/index-explained.md Accessed: 2026-04-22. Navarro (2002) Gonzalo Navarro. 2002. Searching in metric spaces by spatial approximation. The VLDB Journal 11, 1 (2002), 28–46. Niyogi et al. (2008) Partha Niyogi, Stephen Smale, and Shmuel Weinberger. 2008. Finding the Homology of Submanifolds with High Confidence from Random Samples. Discrete Comput. Geom. 39, 1–3 (March 2008), 419–441. NMSLIB (2026) NMSLIB. 2026. NMSLIB: Non-Metric Space Library, an Efficient Similarity Search Library and a Toolkit for Evaluation of k-N Methods for Generic Non-Metric Spaces. https://github.com/nmslib/nmslib. Accessed: 2026-07-15. Oliva and Torralba (2001) Aude Oliva and Antonio Torralba. 2001. Modeling the Shape of the Scene: A Holistic Representation of the Spatial Envelope. International Journal of Computer Vision 42, 3 (2001), 145–175. OpenAI (2022) OpenAI. 2022. New and Improved Embedding Model (text-embedding-ada-002). OpenAI Blog. https://openai.com/index/new-and-improved-embedding-model/ Published December 15, 2022. Accessed July 2026. OpenAI (2024) OpenAI. 2024. New Embedding Models and API Updates. https://openai.com/index/new-embedding-models-and-api-updates/. Accessed: 2026-06-22. OpenAI-ArXiv (2023) OpenAI-ArXiv 2023. OpenAI-ArXiv: 2.3M ada-002 Embeddings of arXiv Abstracts. Dataset distributed with big-ann-benchmarks. 2,321,096 base vectors, 1536 dimensions, 20,000 queries. https://comp21storage.z5.web.core.windows.net/arxiv-openaiv2-2M/. OpenSearch (2024) OpenSearch. 2024. k-N Performance Tuning. https://docs.opensearch.org/1.0/search-plugins/knn/performance-tuning/ Accessed: 2026-04-22. Pan et al. (2024a) James Jie Pan, Jianguo Wang, and Guoliang Li. 2024a. Survey of vector database management systems. The VLDB Journal 33, 5 (2024), 1591–1615. Pan et al. (2024b) James Jie Pan, Jianguo Wang, and Guoliang Li. 2024b. Vector database management techniques and systems. In Companion of the 2024 International Conference on Management of Data. 597–604. Peng et al. (2023) Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. Proc. ACM Manag. Data 1, 1, Article 54 (May 2023), 27 pages. https://doi.org/10.1145/3588908 Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global Vectors for Word Representation. In Empirical Methods in Natural Language Processing (EMNLP). 1532–1543. http://w.aclweb.org/anthology/D14-1162 Pestov (2008) Vladimir Pestov. 2008. An axiomatic approach to intrinsic dimension of a dataset. Neural Networks 21, 2-3 (2008), 204–213. Pinecone ([n.d.]) Pinecone. [n.d.]. Hierarchical Navigable Small Worlds (HNSW). https://w.pinecone.io/learn/series/faiss/hnsw/. Accessed: 2026-06-24. Prokhorenkova and Shekhovtsov (2020) Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based nearest neighbor search: From practice to theory. In International Conference on Machine Learning. PMLR, 7803–7813. Pugh (1990) William Pugh. 1990. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33, 6 (June 1990), 668–676. https://doi.org/10.1145/78973.78977 Qdrant ([n.d.]) Qdrant. [n.d.]. Measuring ANN Recall. https://qdrant.tech/documentation/tutorials-search-engineering/ann-recall/. Qdrant documentation. Accessed: 2026-07-21. Qdrant (2025) Qdrant. 2025. Qdrant: Vector Search Engine. https://qdrant.tech. Accessed: 2026-01-29. Qian et al. (2004) Gang Qian, Shamik Sural, Yuelong Gu, and Sakti Pramanik. 2004. Similarity between Euclidean and Cosine Angle Distance for Nearest Neighbor Queries. In Proceedings of the 2004 ACM Symposium on Applied Computing (SAC). ACM, Nicosia, Cyprus, 1232–1237. RAPIDS Team (2024) RAPIDS Team. 2024. The Wiki-all Dataset. https://docs.rapids.ai/api/cuvs/stable/cuvs_bench/wiki_all_dataset/. 88M 768-dimensional embeddings of English and multilingual Wikipedia text, generated with the paraphrase-multilingual-mpnet-base-v2 model. Accessed July 2026. Redis (2023) Redis. 2023. How Hierarchical Navigable Small World (HNSW) Algorithms Can Improve Search. https://redis.io/blog/how-hnsw-algorithms-can-improve-search/ Accessed: 2026-04-22. Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019. Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks. arXiv:1908.10084 [cs.CL] https://arxiv.org/abs/1908.10084 Shan et al. (2021) Xuan Shan, Chuanjie Liu, Yiqian Xia, Qi Chen, Yusi Zhang, Kaize Ding, Yaobo Liang, Angen Luo, and Yuxiang Luo. 2021. GLOW: Global Weighted Self-Attention Network for Web Search. In 2021 IEEE International Conference on Big Data (Big Data). IEEE, 519–528. Simhadri et al. (2024) Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, et al. 2024. Results of the Big ANN: NeurIPS’23 competition. arXiv preprint arXiv:2409.17424 (2024). Singh et al. (2021) Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. Freshdiskann: A fast and accurate graph-based ann index for streaming similarity search. arXiv preprint arXiv:2105.09613 (2021). Song et al. (2020) Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and Tie-Yan Liu. 2020. MPNet: Masked and Permuted Pre-training for Language Understanding. In Advances in Neural Information Processing Systems (NeurIPS). Song et al. (2025) Yitong Song, Pengcheng Zhang, Chao Gao, Bin Yao, Kai Wang, Zongyuan Wu, and Lin Qu. 2025. TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–26. Subramanya et al. (2019) Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: fast accurate billion-point nearest neighbor search on a single node. Curran Associates Inc., Red Hook, NY, USA. Szegedy et al. (2015) Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. 2015. Going Deeper with Convolutions. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 1–9. Timescale (2026) Timescale. 2026. pgvectorscale: Postgres Extension for Vector Search with StreamingDiskANN. https://github.com/timescale/pgvectorscale. Accessed: 2026-07-15. Toussaint (1980) Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern recognition 12, 4 (1980), 261–268. turbopuffer (2024) turbopuffer. 2024. Continuous Recall Measurement. https://turbopuffer.com/blog/continuous-recall. Accessed: 2026-06-25. Upreti (2024) Nitish Upreti. 2024. Azure Cosmos DB Vector Search with DiskANN Part 1: Full Space Search. Azure Cosmos DB Blog, https://devblogs.microsoft.com/cosmosdb/azure-cosmos-db-vector-search-with-diskann-part-1-full-space-search/. Accessed: 2026-07-15. Veasey and Sharipova (2025) Thomas Veasey and Mayya Sharipova. 2025. Speeding up merging of HNSW graphs. https://w.elastic.co/search-labs/blog/hnsw-graphs-speed-up-merging Vespa ([n.d.]) Vespa. [n.d.]. Nearest Neighbor Search Guide. https://docs.vespa.ai/en/nearest-neighbor-search-guide.html. Vespa documentation. Accessed: 2026-07-21. Wang et al. (2021b) Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021b. Milvus: A purpose-built vector data management system. In Proceedings of the 2021 international conference on management of data. 2614–2627. Wang et al. (2024a) Mengzhao Wang, Xiangyu Ke, Xiaoliang Xu, Lu Chen, Yunjun Gao, Pinpin Huang, and Runkai Zhu. 2024a. Must: An effective and scalable framework for multimodal search of target modality. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 4747–4759. Wang et al. (2021a) Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021a. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101.12631 (2021). Wang et al. (2024b) Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas, and Wei Wang. 2024b. Steiner-hardness: A query hardness measure for graph-based ann indexes. Proceedings of the VLDB Endowment 17, 13 (2024), 4668–4682. Weaviate (2024) Weaviate. 2024. Vector Indexing. https://weaviate.io/developers/weaviate/concepts/vector-index Accessed: 2026-04-22. Weber et al. (1998) Roger Weber, Hans-J Schek, and Stephen Blott. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. (1998). Wei et al. (2020) Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: a hybrid analytical engine towards query fusion for structured and unstructured data. Proc. VLDB Endow. 13, 12 (Aug. 2020), 3152–3165. https://doi.org/10.14778/3415478.3415541 Xu et al. (2023) Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang, Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, et al. 2023. Spfresh: Incremental in-place update for billion-scale vector search. In Proceedings of the 29th Symposium on Operating Systems Principles. 545–561. Yang et al. (2025) Mingyu Yang, Wentao Li, Jiabao Jin, Xiaoyao Zhong, Xiangyu Wang, Zhitao Shen, Wei Jia, and Wei Wang. 2025. Effective and general distance computation for approximate nearest neighbor search. In 2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE, 1098–1110. Zhang and J. Miller (2026) Chao Zhang and Renée J. Miller. 2026. Distribution-aware exploration for adaptive hnsw search. Proceedings of the ACM on Management of Data 4, 1 (SIGMOD (2026), 1–27. Zhao et al. (2026) Xinkui Zhao, Hengxuan Lou, Yifan Zhang, Junjie Dai, Shuiguang Deng, and Jianwei Yin. 2026. GRAB-ANNS: High-Throughput Indexing and Hybrid Search via GPU-Native Bucketing. arXiv preprint arXiv:2604.16402 (2026). Zilliz ([n.d.]) Zilliz. [n.d.]. AUTOINDEX Explained. https://docs.zilliz.com/docs/autoindex-explained. Accessed: 2026-06-25. Zoumpatianos et al. (2018) Kostas Zoumpatianos, Yin Lou, Ioana Ileana, Themis Palpanas, and Johannes Gehrke. 2018. Generating data series query workloads: K. Zoumpatianos et al. The VLDB Journal 27, 6 (2018), 823–846.