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

A Power Law in Logarithm’s Clothing: On the Scalability of Graph-Based Vector Search Sajad Faghfoor Maghrebi

Navid Eslami

Niv Dayan

University of Toronto Canada smaghrebi@cs.toronto.edu

University of Toronto Canada navideslami@cs.toronto.edu

University of Toronto Canada nivdayan@cs.toronto.edu

arXiv:2609.02143v1 [cs.DB] 2 Sep 2026

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 polylogarithmically. 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 𝑁 is small relative to the data’s intrinsic dimensionality, search cost grows in step with 𝑁 𝑐 for a constant 0 < 𝑐 < 1. We call this scaling a Sublinear Power Law. (2) Once 𝑁 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 boundeddegree 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 [111]. Querying such datasets using traditional approaches based on attribute values and keywords fails to capture semantic similarity [105]. 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 [91]. 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 [7, 105]. Their core retrieval primitive is nearest neighbor search. However, computing the exact nearest neighbors is prohibitively expensive at scale [12, 14, 41]. 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 [32, 64, 97]. Graph-based Indexes. The ANN indexes that perform best in practice are graph-based [61, 107]. 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 [64, 97]. Some graph constructions provide guarantees on accuracy and on reaching a query’s neighborhood, but are often too expensive to build exactly [2, 97]. Practical graph-based indexes draw on these exact constructions but build them with cheaper heuristics [64, 97]. The two most widely used such indexes, HNSW [64] and Vamana [97], power vector search across databases [51, 69, 87, 99, 102, 109], search engines [77, 103], and libraries [26, 68, 72]. Sustaining Accuracy As Data Grows. The data stored in vector databases grows continuously [9, 94, 112]. As the data grows, however, search accuracy—typically measured by recall, the fraction of true nearest neighbors returned by the search—deteriorates [19, 27, 101]. Maintaining stable recall therefore requires adjusting the index parameters in response [27, 65, 115]. A common practice is to periodically measure recall using exact search [28, 86, 104] and adjust parameters accordingly [19, 65, 101]. 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 [101, 116] improves upon this practice by using statistical or learned models of the search effort required to achieve a recall target [19, 56, 114]. 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 [2, 42]. 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 (𝑑 ≤ 8), and its largest experiment deviates from logarithmic scaling [64]. 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

Sajad Faghfoor Maghrebi, Navid Eslami, and Niv Dayan

sizes [97]. The claim has nonetheless propagated into industry documentation [26, 69, 77, 83, 90, 109] and surveys [78, 79, 107], 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 [4, 43, 93, 107]. Observations. We put the folklore to the test and make two observations: (1) When the dataset size 𝑁 is small relative to the data’s intrinsic dimensionality, the average search cost of a graphbased index at fixed recall grows in step with 𝑁 𝑐 for a constant 0 < 𝑐 < 1. We call this scaling a Sublinear Power Law. (2) Once 𝑁 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 log 𝑁 . An exponential in log 𝑁 is a power of 𝑁 , 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 constructions1 of HNSW and Vamana, we prove the Sublinear Power Law and the eventual transition to polylogarithmic 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 [34, 48, 50, 106]. 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 𝑆 ⊂ R𝑑 and a query point 𝑞, the goal is to identify the point in 𝑆 closest to 𝑞. The 𝑘-nearest neighbor variant generalizes this, returning the 𝑘 points in 𝑆 with the smallest distance to 𝑞. The embedding 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.

model dictates the dimensionality 𝑑, which ranges from hundreds to thousands (e.g., 1536 for OpenAI’s text-embedding-3-small and 3072 for text-embedding-3-large [75]). 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 [11, 41], a phenomenon whereby most points lie at similar distances from the query, and the nearest neighbor is only slightly closer than the rest [38, 96]. Because distances concentrate, points do not separate cleanly, so traditional multidimensional indexes (e.g., Rtrees [37] or KD-trees [10]) lose their pruning power [13, 57, 110]. To distinguish the nearest neighbors from the many nearly equidistant points, the search must examine a large fraction of the dataset. This is expensive [70] and degrades to a linear scan in the worst case [15]. 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 [30]. These structures are called manifolds [16], 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 [54]. 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 [82]. 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 + 𝜖)-approximate distance guarantee: the returned point’s distance to query 𝑞 is within a factor of (1 + 𝜖) of the nearest neighbor distance. The same relaxation extends to the 𝑘-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 𝑅 the set of true 𝑘 nearest neighbors and 𝑅 ′ the returned set, recall is |𝑅 ∩ 𝑅 ′ |/𝑘. 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 [21, 107]. Graph-based Indexes. Graph-based indexes are widely regarded as the state of the art among vector indexes [64, 97]. 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

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

q

Table 1: Notations used in the paper.

r

r p

cone

p

d(p, q)

Symbol

q

𝑁 𝑑 amb 𝑑 int 𝑘 𝑞

lune

(a) Randomized NG

(b) SNG

Description

Dataset and query Number of vectors in the index Ambient dimensionality of the embedding space Intrinsic dimensionality of the dataset Number of nearest neighbors returned per query A query vector

Index parameters

𝑀 Maximum out-degree of each node in the graph 𝑒 𝑓construction , 𝑒 𝑓search Candidate list size at build and search time

r p

d(p, q)/α

q

(c) Vamana

r p

Cost metrics

q 3τ

(d) τ -MG

Figure 1: Edge selection across graph constructions. In each subfigure, 𝑝 decides whether to add an edge to 𝑞. The node 𝑟 already connected to 𝑝 (red directed edge) lies in the shaded region, where it occludes 𝑞 and suppresses the edge 𝑝–𝑞.

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) [2] 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 𝑞, the search finds a point whose distance to 𝑞 is within a factor of 1 + 𝜖 of the distance to 𝑞’s nearest neighbor. To build this graph, the construction process partitions the space around each point 𝑝 into cones with apex 𝑝. Within each cone, it scans the enclosed points in random order and links 𝑝 to every point closer to 𝑝 than all previously scanned points, i.e., every new running minimum. This scan results in an average of 𝑂 (log 𝑁 ) neighbors in every cone, at approximately geometrically increasing distances from 𝑝. 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 𝑁 points costs 𝑂 (𝑁 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 𝑁 . The search takes 𝑂 (log2 𝑁 ) steps: an ideal straight path to 𝑞 takes 𝑂 (log 𝑁 ) steps, each halving the remaining candidates as in a skip list [85], and each ideal step expands into 𝑂 (log 𝑁 ) actual steps as the path bends in high dimensions. The out-degree is 𝑂 ((1/𝜖)𝑑 −1 log 𝑁 ): the (1/𝜖)𝑑 −1 factor accounts for the number of cones around each point, and each cone contributes 𝑂 (log 𝑁 ) neighbors [2]. Although both factors scale poly-logarithmically with 𝑁 , the (1/𝜖)𝑑 −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 [2].

dc dcbuild

Distance computations per query Total distance computations to build an index of size 𝑁

Query-cost model (Eq. 1, 2, 3) Query-cost scaling exponent, dc ∝ 𝑁 𝑐 Dataset-specific baseline exponent Sensitivity of 𝑐 to recall demand ln(1/𝛿 ) Reduction in 𝑐 per ln(𝑒 𝑓construction ) and per ln(𝑀 )

𝑐 𝑐0 𝛼 𝛾1 , 𝛾2 𝛽

𝛽

Search-side exponent, dc/𝑞 ∝ 𝑒 𝑓search

Build-cost model (Eq. 4)

𝜅 𝛽′ 𝑐 0′ 𝛾 2′

Dataset-specific intercept for build cost Exponent of 𝑒 𝑓construction in build cost Baseline size-dependence of build cost Interaction coefficient between ln 𝑀 and ln 𝑁

Sparse Neighborhood Graph. The same paper [2] 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 𝑝 and 𝑞 only when no third point 𝑟 to which 𝑝 is already connected lies in the intersection of the two balls of radius 𝑑 (𝑝, 𝑞) centered at 𝑝 and 𝑞. This intersection is called the lune of 𝑝 and 𝑞 (Figure 1-b). Intuitively, such a point 𝑟 provides a closer intermediate step from 𝑝 toward 𝑞, so the direct edge from 𝑝 to 𝑞 can be removed while preserving navigability. SNG is built by considering, for each point 𝑝, all other points in increasing order of distance from 𝑝 and pruning candidates that violate this rule. A naive construction takes 𝑂 (𝑁 3 ) time, while the paper achieves 𝑂 (𝑁 2 ) [2] by drawing on algorithms for the relative neighborhood graph2 from the 1980s [45, 100]. For SNG,3 a later work [32] proves that the search takes in expectation 𝑂 (𝑁 1/𝑑 log 𝑁 /△𝑟 ) steps for uniformly distributed data and queries that are dataset points, where △𝑟 is the minimum gap between pairwise distances in the dataset. A later paper [80] proves that, under the same assumptions, △𝑟 shrinks as 𝑂 (𝑁 −1/𝑑 ), bounding the steps by 𝑂 (𝑁 2/𝑑 log 𝑁 ). The out-degree, in turn, is independent of 𝑁 and hence enters the query time only as a constant, but it is exponential in 𝑑: the SNG paper bounds it by the number of caps of angular diameter 𝜋/3 fitting on the 𝑑-dimensional sphere, i.e., 2𝑂 (𝑑 ) , and the empirical out-degree grows accordingly [2]. 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 [97] (Figure 1-c). Vamana connects two points 𝑝 and 𝑞 only when no point 𝑟 already connected to 𝑝 comes closer to 𝑞 than 𝑝 by a factor of at least 𝛼, i.e., 𝛼 · 𝑑 (𝑟, 𝑞) < 𝑑 (𝑝, 𝑞). At 𝛼 = 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 2 First introduced to capture the local structure of a set of points in a sparse manner. 3 Proposed as MRNG [32], with a construction identical [31] to that of SNG [2].

Sajad Faghfoor Maghrebi, Navid Eslami, and Niv Dayan

efsearch = 200

SIFT DEEP SpaceV Wiki GloVe Rand64 GIST OpenAI

128 96 100 768 100 64 960 1536

19.2 20.7 29.2 30.1 32.4 40.2 42.5 46.5

Type

Metric

Model

Sampled From

Image L2 SIFT descriptors [59] SIFT1B [47] Image L2 GoogLeNet [98] DEEP1B [6] Text L2 SpaceV Superior [92] SpaceV1B [67] Text L2 MPNet [95] Wiki-all [89] Text Angular GloVe [81] GloVe-100 [81] Synthetic Angular — Unif (𝑆 63 ) 5 Image L2 GIST descriptors [73] GIST1M [46] Text L2 ada-002 [74] OpenAI-ArXiv [76]

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 [42] proves that greedy search reaches an 𝛼𝛼+1 −1 + 𝜖 Δ approximate nearest neighbor in 𝑂 (log𝛼 (𝛼 −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 𝑁 [42, 96]. Each step pays the out-degree of the visited point, bounded by 𝑂 ((4𝛼)𝑑 log Δ), again exponential in the dimensionality.4 When Δ grows at most polynomially with 𝑁 , as under a uniform distribution, both log Δ factors become 𝑂 (log 𝑁 ), and multiplying steps by out-degree gives a query time poly-logarithmic in 𝑁 . Also, the construction process, as in SNG, prunes each point against the entire dataset, incurring a total cost at least quadratic in 𝑁 . 𝜏-Monotonic Graph. Also inspired by SNG, the 𝜏-Monotonic Graph (𝜏-MG) [80] 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𝜏, and for farther pairs applies an SNG-like rule on the lune shrunk by 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 𝑂 (𝑁 1/𝑑 log2 𝑁 ) steps. The paper does not analyze the out-degree, treating it as a constant. In fact, because all points within 3𝜏 are connected, the out-degree is Ω((3𝜏)𝑑 ), so the constant hidden in its query cost is exponential in the dimensionality. As in SNG, construction cost is at least quadratic in 𝑁 . Practical Graph-based Indexes. The quadratic construction cost of the above graphs is the core obstacle to their practical use at scale [2, 32, 80]. 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 𝑒 𝑓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 𝑀 of the closest survivors. The same beam search procedure is used at query time, with 4 Here 𝑑 is the doubling dimension, a measure of the intrinsic dimensionality. 5 Generated by sampling each vector i.i.d. from N (0, 𝐼

length, which yields a uniform distribution on 𝑆 63 .

Recall

Dataset Dim. Int. Dim. @ 1M

Dist. Comp. (log)

Table 2: Datasets used in the experiments.

5 × 103

efsearch = 100

efsearch = 40

efsearch = 20

efsearch = 10

sift

deep

glove

221 223 225 Dataset Size (log)

223 224 225 226 Dataset Size (log)

218 219 220 Dataset Size (log)

2 × 103

103

0.999 0.99 0.9

Figure 2: As the data grows, distance computations per query rise (top) and recall drops (bottom). Here, we use the HNSW index with 𝑒 𝑓construction = 200, 𝑀 = 32, and 𝑘 = 10, with one curve per 𝑒 𝑓search value. a candidate list of size 𝑒 𝑓search ≥ 𝑘, and the top-𝑘 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 [64] 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 [97] 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 𝑂 (𝑁 log 𝑁 ) [64]. The paper that introduced Vamana [97] 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 [4, 97]. These logarithmic scalability claims and similar claims from the same line of work [31, 32, 55, 63, 80] have since propagated into vendor documentation and industry blogs, which restate them as a settled property of these indexes [29, 69, 77, 83, 90, 109]. In the next section, we evaluate how these indexes scale and bridge this gap between claimed and measured scaling both theoretically and empirically.

3

How Graph-Based Indexes Scale

In this section, we study empirically how query cost scales as data grows, focusing on HNSW and Vamana6 , the most widely used graph-based indexes [69, 78]. 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 [27, 65, 115]. 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

64 ) and normalizing to unit 6We use the in-memory version of Vamana, built with build_memory_index [68].

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

HNSW M=32, efc =100

sift

10

0.27 10 0.24 5 0.21 0.18 2

5 2

1

2

20

2

23

2

1

26

deep

5 2

1

220

223

Dist. Comp. (×103 , log) spacev glove wiki

20

2

23

2

26

220

223

217

220

220

223

2

2

220

223

226

5 2

2

17

2

18

2

1

217

220

2

10

5 2

219

220

223

1

226

220

2

0.5

20

221

223

226

220

223

1

226

223

2

1

220

217

220

223

2

2

20

2

22

2

2

0.5

2

0.65 20 0.56 10 0.50 5 0.45

2

18

2

20

2

22

2

18

2

1 17 2

19

2

20

2

2

18

2

221

1 17 2

19

2

20

221

223

2

2

18

2

20

2

22

220

2

2

1

226

2

2

2

19

1 17 2

2

20

221

2

23

2

220

223

1

26

2

2 1 0.5

1

226

223

226

26

0.34 0.28 0.25 0.21

220

223

220

223

220

0.5 17

2

0.55 0.52 10 0.51 5 0.49 2

220

220

2

218 219 220

0.62 10 0.57 5 0.55 0.54 2

0.57 10 0.50 5 0.46 0.41

2

221

216 218 220 222

2

1 17 2

223

218 219 220

0.52 0.49 0.48 0.46

216 218 220 222 0.47 0.45 0.41 0.36

1 17 18 19 20 2 2 2 2 2 217 218 219 220 0.37 10 0.37 10 0.33 20

0.30 5 0.24 0.19 2

0.30 5 0.24 0.19 2

219

226

0.41 0.37 0.33 0.27

2

2

2

220

1

0.51 10 0.45 0.41 5 0.36

0.41 10 0.32 5 0.26 0.20 2

223

0.30 0.24 0.20 0.17

217

0.57 10 0.50 0.46 5 0.42 19

0.20 0.14 0.11 0.08

1

223

0.5

18

226

0.52 0.44 10 0.36 5 0.30

1

17

223

5 2

0.5

2

226 0.27 0.23 0.21 0.17

220 0.36 0.27 0.23 0.18

2

216 218 220 222

223

5 2

226

0.44 20 0.39 0.35 10 0.29 5

218 219 220

0.23 0.20 0.17 0.15

2

1

1

226

Vamana M=64, efc =400

0.26 0.19 10 0.14 5 0.10 2

220

223

5

0.5

1 17 18 19 20 2 2 2 2

Dataset Size (log)

2

1

217

1

219

2

23

0.34 10 0.26 5 0.22 2 0.18

2

216 218 220 222

1 17 2

20

0.24 0.17 10 0.12 5 0.09

220

223

0.28 0.24 0.21 0.18

0.28 0.24 10 0.21 5 0.18 2

0.68 0.63 10 0.60 5 0.58 2

0.40 10 0.32 5 0.24 0.18 2

219

20

0.45 10 0.32 5 0.25 2 0.20

218 219 220

2

18

1

0.56 20 0.48 10 0.40 0.32 5

0.58 0.50 10 0.45 5 0.39 17

5 2

0.35 10 0.29 5 0.26 0.22 2

226

Vamana M=32, efc =400

0.24 10 0.21 5 0.18 0.15 2

1

0.5 17

0.52 0.50 20 0.48 105 0.47

16

recall=90% Vamana M=64, efc =200

0.34 0.23 10 0.17 5 0.12

2

218 219 220

0.41 0.32 10 0.26 5 0.20 2

219

2

26

0.51 0.42 20 0.35 10 0.29 5

2

17

0.48 0.37 10 0.29 5 0.22 2

219

0.5

223

220

223

0.63 0.54 10 0.48 5 0.43

2

17

220

1

16

220

1

217

0.59 10 0.56 0.54 5 0.53 2

1

18

1

2

23

0.38 0.30 105 0.25 0.20 2

2

218 219 220

0.58 0.56 10 0.54 5 0.52 2

16

226

0.54 0.44 20 0.37 10 0.31 5

2

218 219 220

223

0.42 0.32 105 0.26 0.20 2

0.60 0.50 20 0.42 10 0.33 5

0.48 20 0.38 10 0.30 5 0.23 2

20

1 17 2

19

2

20

0.29 0.26 10 0.23 5 0.21 2

0.30 10 0.26 0.24 5 0.20 2

0.48 20 0.36 10 0.29 5 0.23 2

0.69 20 0.61 10 0.53 0.48 5

20

2

0.29 0.25 0.22 0.18

1

26

0.16 10 0.13 0.09

22

10

2

23

0.20 10 0.14 0.10

1

2

2

20

0.31 10 0.20 0.12

0.64 0.61 10 0.60 5 0.58 2

20

1

0.35 0.23 10 0.14

218 219 220

18

2

26

0.24

223

rand64

2

1

226

0.61 50 0.52 20 0.44 10 0.36 5

16

2

23

5 2

0.32

10

20 10 5 2 1 0.5

20

recall=95% Vamana M=32, efc =200

0.24 10 0.21 5 0.19 0.17 2

0.51

50 20 5 2

1

2

0.52 20 0.39 10 0.30 5 0.23 2

2

1

5 2

recall=97.5% HNSW M=64, efc =200

0.55

226

20

0.24 0.21 0.19 0.16

0.34 10 0.29 0.26 5 0.23 2

100

105

gist

2

1

226

100 10

openai

0.27 0.24 0.21 0.19

0.35 0.30 10 0.26 5 0.23 2

10

recall=99% HNSW M=32, efc =200

HNSW M=64, efc =100

221

1 17 2

219

221

1 17 2

0.27 0.22 0.17

219

221

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.

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 [32, 33, 113]. 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 𝑒 𝑓search parameter. For each of these curves, we observe that distance computations per query slightly increase with dataset size 𝑁 (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 [65]. This recall degradation is problematic for applications such as retrieval-augmented generation (RAG) [52] and recommendation systems [22], 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 [28, 86, 104] and adjust search parameters accordingly. If the measured recall falls below the target, the user increases the 𝑒 𝑓search parameter, measures recall again, and repeats this process until the target is reached [19, 65, 101]. Recent work in academia as well as in industry (e.g., Zilliz Cloud [116] and Turbopuffer [101]) improves upon this approach by using statistical or learned models of the search effort required to achieve a recall target [19, 56, 114]. Once recall is held

recall=99%

sift

10

5 2

0.29 0.26 20 0.23 10 0.21 5 0.22 0.16 0.13 0.10

1

0.5

Easy recall=97.5%

221 223 225 Dataset Size (log)

deep

Hard recall=95%

glove

5 0.21 2

2

1

0.5

0.34 50 0.29 0.27 20 0.24 10

223 224 225 226 Dataset Size (log)

0.14 1 0.11 0.09 0.5

recall=99%

recall=90% 0.62 0.55 0.48 0.43 0.25 0.19 0.17 0.17

Dist. Comp. (×103 , log)

Dist. Comp. (×103 , log)

Sajad Faghfoor Maghrebi, Navid Eslami, and Niv Dayan

218 219 220 Dataset Size (log)

20

10

5 2

sift

Vamana (M=32, efc =100, k=10) recall=97.5% recall=95% 0.32 0.28 0.25 0.22

1

0.5

deep

20

10

5 2

1

217 220 223 226 229 Dataset Size (log)

0.5

recall=90%

0.38 0.33 100 0.28 0.24 10

217 220 223 226 229 Dataset Size (log)

1

spacev

0.41 0.28 0.20 0.13

217 220 223 226 229 Dataset Size (log)

Figure 4: Both hard and easy queries follow a power law scaling. We use the same HNSW setup as Figure 2.

Figure 5: The power law persists to billion scale on SIFT and DEEP, while SpaceV’s slope decreases as the dataset grows.

fixed, another core question emerges: how does query cost scale as the dataset grows? Experimental Setup. To hold recall fixed, we set 𝑒 𝑓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 SpaceV7 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 𝑀 ∈ {16, 32, 64, 128} and construction list size 𝑒 𝑓construction ∈ {100, 200, 400, 800} varying across the columns.8 Due to limited space, we show four of the sixteen benchmarked (𝑀, 𝑒 𝑓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:

recall level. This suggests that beam-search cost scales more steeply with 𝑁 on harder datasets. Varying Query Hardness. As discussed in Section 2, queries within a workload can vary substantially in hardness [19, 56, 108], with queries in regions of higher intrinsic dimensionality generally being more expensive to answer [5]. To test whether the Sublinear Power Law holds across query hardness levels within the same workload, we rank queries by intrinsic dimensionality9 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.9, 9.6, and 11.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 𝑁 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.

dc ∝ 𝑁 𝑐 .

(1)

Here, 0 < 𝑐 < 1, and the value at the right end of each curve reports the fitted exponent 𝑐. Figure 3 also indicates the factors that impact the exponent 𝑐 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 𝑒 𝑓construction and 𝑀 reduce 𝑐 by yielding graphs in which the beam search reaches the query’s nearest neighbors in fewer hops. We also measured 𝑘 ∈ {1, 5, 10, 20} and found that varying it does not materially change 𝑐, so we report only 𝑘 = 10. The nearest neighbors lie at nearly the same distance from the query, so retrieving all 𝑘 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 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. 8 For Vamana, 𝛼 is a build parameter fixed to the default 1.2 [97]; testing 𝛼 ∈ {1.5, 2} left scalability unchanged, as out-degree typically saturates at cap 𝑀 .

3.3

Scaling with Larger Data

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 [94]. We therefore choose one representative configuration (𝑒 𝑓construction = 100, 𝑀 = 32) and repeat the experiment with Vamana10 . 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 9 Later, in Section 4.1, we show how to measure intrinsic dimensionality using LID;

Figure 7 reports the resulting estimates. 10We use Vamana here because it has a smaller memory footprint than HNSW and

therefore lets us scale to the largest available dataset sizes.

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

initial sublinear power-law scaling across all workloads, and why does this scaling eventually slow for some workloads?

4

(a) Dataset

(b) Zoom-in around q

εrk

Locally Uniform on the Manifold

rk q

Unifying Theory Zoom

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 [64, 107]. 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 𝑘-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 [19, 20, 58, 60]. 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 [96], 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 [17, 25], 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 𝑞. The inner hyper-ball extends from the query to its 𝑘-th nearest neighbor and thus has radius 𝑟𝑘 ; the outer hyper-ball extends to distance (1 + 𝜀)𝑟𝑘 . Here, 1 + 𝜀 is the smallest factor for which extensively searching the outer hyper-ball visits the true 𝑘-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 + 𝜀) unchanged (we return to this point later in Discussion 2). 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

q

inner hyper-ball k-NN outer hyper-ball ≈ k(1+ε)dint -NN

Figure 6: (a) The data is not globally uniform, but the query 𝑞’s neighborhood is roughly uniform on the manifold. (b) The 𝑘-NNs of 𝑞 lie within radius 𝑟𝑘 ; expanding this radius by a factor (1 + 𝜀) captures about 𝑘 (1 + 𝜀)𝑑int 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 𝑁 ? 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 [5, 84]. 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 [40, 62, 66]. 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 3 revisits what happens when each of these assumptions is dropped. 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).11 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 (𝑑 int ), rather than by the ambient

11 Similar measures have been used to estimate query hardness [18, 117].

Sajad Faghfoor Maghrebi, Navid Eslami, and Niv Dayan

sift deep

Table 3: The order of the query cost falls as 𝑁 grows. Sparse: 𝑑 int = Θ(log 𝑁 )

Shortcut 𝑂 (1) Exploration Θ(𝑁 ) Total

Θ(𝑁 )

∗ For 𝑀 = 2𝑜 (𝑑 int ) .

Θ(𝑑 int )

40

≻

𝑁 Θ(1) 𝑁 Θ(1)

𝑁 𝑜 (1) 𝑁 𝑜 (1)

Θ( poly log 𝑁 ) † 𝑂 ( poly log 𝑁 )

𝑁 Θ(1)

𝑁 𝑜 (1)

Θ( poly log 𝑁 )

40 20

bounds on the cost that may not be tight. For example, as argued in Section 4.2.2, SNG’s cost is at least 𝑁 (1−𝑜 (1) )/𝑑 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.

Theorem 1 (Scaling with Intrinsic Dimensionality). Let 𝐵(𝑞, 𝑟 ) be the hyper-ball of radius 𝑟 around query 𝑞 on the manifold, and let 𝐶 (𝑟 ) be the number of data points inside 𝐵(𝑞, 𝑟 ). For any radius 𝑟 and any 𝜀 such that the local uniformity model holds within 𝐵(𝑞, (1 +𝜀)𝑟 ), 𝐶 ((1 + 𝜀)𝑟 ) ≈ (1 + 𝜀)𝑑int 𝐶 (𝑟 ). In particular, if 𝑟𝑘 is the query’s distance to its 𝑘-th nearest neighbor, then the expected number of points inside the outer hyper-ball is 𝐶 ((1 + 𝜀)𝑟𝑘 ) ≈ 𝑘 (1 + 𝜀)𝑑int . Proof. A 𝑑 int -dimensional hyper-ball has volume proportional to 𝑟 𝑑int [8]. By assumption, the local uniformity model holds within 𝐵(𝑞, (1 + 𝜀)𝑟 ), and 𝐵(𝑞, 𝑟 ) 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 𝐶 ((1 + 𝜀)𝑟 ) ((1 + 𝜀)𝑟 )𝑑int = (1 + 𝜀)𝑑int . ≈ 𝐶 (𝑟 ) 𝑟 𝑑int □

The base 1 + 𝜀 can be rewritten as 𝑁 log(1+𝜀 )/log 𝑁 . Substituting this into the factor (1 + 𝜀)𝑑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 𝑑 int

k = 2000

k = 4000

k = 8000

k = 16000

217 219 221 223 225 227 229 217 219 221 223 225 227 229 217 219 221 223 225 227 229

Dataset Size (log)

dimensionality of the embedding space (𝑑 amb ). The following theorem counts the points inside the outer hyper-ball in terms of its volume on the manifold.

𝐶 ((1 + 𝜀)𝑟𝑘 ) ≈ 𝑘𝑁 log 𝑁

k = 1000

20

† For some graph-based indexes, these expressions are lower

Setting 𝑟 = 𝑟𝑘 gives 𝐶 (𝑟𝑘 ) ≈ 𝑘, so 𝐶 ((1 + 𝜀)𝑟𝑘 ) ≈ 𝑘 (1 + 𝜀)𝑑int .

k = 500

LID

22

median wiki gist glove rand64

LID

𝑁:

Dense: 𝑑 int = 𝑜 (log 𝑁 )

2Θ(𝑑int )

𝑂 (𝑀 ) ∗

mean spacev openai

log(1+𝜀 )

.

The exponent of 𝑁 in Corollary 2 depends on 𝑑 int through the ratio 𝑑 int /log 𝑁 , so applying it requires understanding how 𝑑 int behaves as 𝑁 grows. LID. We use the local intrinsic dimensionality (LID) as our empirical proxy for 𝑑 int , as it is computationally feasible and standard in practice [1, 5, 40]. 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 [5, 54] ! −1 𝑘 1 ∑︁ 𝑟𝑖 d LID𝑘 (𝑞) = − log . 𝑘 𝑖=1 𝑟𝑘

Dataset Size (log)

Dataset Size (log)

Figure 7: LID grows roughly with log 𝑁 , 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 𝑘; shaded bands mark the 25th–75th percentiles. Here, 𝑟𝑖 is the query’s distance to its 𝑖-th nearest neighbor. Figure 7 reports how LID changes with 𝑁 across datasets and values of 𝑘. For most datasets, LID follows an approximately straight line when plotted against a logarithmic dataset size, meaning LID grows in step with log 𝑁 . 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. Sparse and Dense Regimes. In principle, 𝑑 int can take any value from 1 to 𝑂 (log 𝑁 ). The upper bound is motivated by the JohnsonLindenstrauss (JL) lemma [24, 49]. The lemma states that any 𝑁 points in Euclidean space can be embedded into a space with an ambient dimensionality of 𝑂 (log 𝑁 ) while changing every pairwise distance by at most a constant factor. Since 𝑑 int never exceeds 𝑑 amb [23] and a constant-factor change in pairwise distances changes 𝑑 int by at most a constant factor [3, 39], the same bound holds for the original dataset.12 Motivated by this upper bound on 𝑑 int , and guided by the LID curves in Figure 7, we define two regimes of interest. In the sparse regime, 𝑑 int grows proportionally to log 𝑁 , i.e., 𝑑 int = Θ(log 𝑁 ). In the dense regime, 𝑑 int grows more slowly than log 𝑁 , i.e., 𝑑 int = 𝑜 (log 𝑁 ). Later, in Discussion 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 𝑁 grows. Sparse Regime: Power-Law. In the sparse regime, 𝑑 int = Θ(log 𝑁 ), so 𝑑 int = (log 𝑁 )/𝜌 for a constant 𝜌 = Θ(1). Plugging this into Corollary 2, the expected number of points in the outer hyperball is 𝑑 int

𝐶 ((1 + 𝜀)𝑟𝑘 ) ≈ 𝑘𝑁 log 𝑁

log(1+𝜀 )

= 𝑘𝑁 log(1+𝜀 )/𝜌 ∝ 𝑁 𝑐 .

Notably, 𝑐 = log(1 + 𝜀)/𝜌 is a constant independent of 𝑁 , which explains the power-law scaling of search cost in the sparse regime. Dense Regime: Subpolynomial. In the dense regime, 𝑑 int = 𝑜 (log 𝑁 ). Plugging this into Corollary 2, the expected number of 12 This holds even without the JL embedding: for any set of 𝑁 points, every ball is

covered by 𝑁 half-radius balls centered at the points, so the doubling dimension, a standard notion of intrinsic dimensionality [36], is 𝑂 (log 𝑁 ) (Theorem 3).

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

Total Exploration Shortcut

N Θ(1) N o(1) O(poly log N ) O(1)

Θ(dint )

2Θ(dint )

22

Dataset Size N

Figure 8: The total query cost falls from Θ(𝑁 ) to Θ(poly log 𝑁 ) as 𝑁 crosses the regimes of Table 3. points in the outer hyper-ball is 𝑑 int

𝐶 ((1 + 𝜀)𝑟𝑘 ) ≈ 𝑘𝑁 log 𝑁

log(1+𝜀 )

= 𝑘𝑁 𝑜 (1) .

𝑑 int The exponent log 𝑁 log(1 + 𝜀) converges to 0 as 𝑁 → ∞, so the number of points in the outer hyper-ball grows slower than any power of 𝑁 , resulting in subpolynomial scaling. 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 (𝑁 = 𝑂 (𝑀)), the outer hyper-ball contains the entire dataset, so the search skips straight to the exploration phase and the shortcut phase costs 𝑂 (1). When the dataset is larger than the graph out-degree but has not yet saturated the underlying manΘ(𝑑 ) ifold (we later establish the saturation point is 22 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 Θ(poly log 𝑁 ), matching the guarantees established for fixed dimensionality [58, 84, 97]. 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 𝑁 = 𝑂 (𝑀), the outer hyper-ball contains the entire dataset and the search cost is Θ(𝑁 ) (Corollary 2). As the dataset grows beyond 𝑂 (𝑀) points but stays at most exponential in the intrinsic dimensionality (𝑁 = 2𝑂 (𝑑int ) ), the cost follows a power law 𝑁 𝑐 for 0 < 𝑐 < 1. Once the dataset exceeds 2𝑂 (𝑑int ) points, the cost becomes Θ(𝑑 ) 𝑁 𝑜 (1) . Beyond 22 int points, the outer hyper-ball contains only 𝑂 (poly log 𝑁 ) points, the shortcut phase therefore governs the scaling, and the cost is Θ(poly log 𝑁 ). Discussion 1: Doubling Dimension. The literature offers several estimators for 𝑑 int , including the doubling dimension, the expansion dimension, and the local intrinsic dimensionality [3, 5, 40].13 We have already used the local intrinsic dimensionality to identify which regime the datasets of Table 2 fall into (Figure 7). We now 13 These measures differ in general, but for smooth data distributions they often coin-

cide [40].

visited fraction

Query Cost

Θ(N )

O(M )

1.0

Dense: dint = o(log N )

visited per query (100x)

Sparse: dint = Θ(log N )

0.5 0.0 0.5 0

sift

deep

62.5K 250K 1M

80% of comps

glove

1M 6.25M 25M

1

62.5K 250K 1M

5

0 0 1 1.25 1.5 1.75 2 1 1.25 1.5 1.75 2 1 1.25 1.5 1.75 2

r = d(q, v)/ d(q, NN10 (q))

Figure 9: Visited-node distance distributions for HNSW across three datasets and three dataset sizes at recall = 0.95 (𝑀 = 32, 𝑒 𝑓 𝑐 = 200, 𝑘 = 10). Distances are normalized by the 10th-NN distance. Dashed lines indicate the normalized distance containing 80% of distance computations. turn to the doubling dimension, prevalent in theoretical work [36, 42]. 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 𝑅. Find the smallest number of non-empty hyper-balls of radius 𝑅/2 that can cover all the data points within this hyperball. The largest such value over all dataset points and radii 𝑅 is the doubling constant 𝜆, and the doubling dimension is defined as log2 𝜆. Computing the value of 𝜆 exactly is NP-hard [35], so we use the doubling dimension only in our theoretical analysis. Theorem 3 places the data in the sparse regime whenever 𝑁 is at most exponential in the dimensionality of the underlying manifold. Theorem 3 (Logarithmic Scaling of the Doubling Dimension). Let 𝑃 consist of 𝑁 = 2𝑂 (𝑑 ) points drawn i.i.d. uniformly from S𝑑 −1 . With high probability, the doubling dimension of 𝑃 is Θ(log 𝑁 ). Proof. Fix a constant 𝑐 with 𝑁 ≤ 2𝑐𝑑 and set 𝜀 = 2− (𝑐+1) ≤ 21 . 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 𝜀𝑑 −2 fraction of the sphere. The expected number of bad pairs is thus at most 𝑁 2𝜀𝑑 −2 ≤ 𝑁 · 2𝑐𝑑 · 2− (𝑐+1) (𝑑 −2) = 22𝑐+2−𝑑 𝑁 , so by Markov’s inequality, with probability at least 1 − 22𝑐+3−𝑑 = 1 − 2−Ω (𝑑 ) there are fewer than 𝑁 /2 bad pairs. In that case, remove one point of each bad pair and let 𝑆 be the set of remaining points; then |𝑆 | > 𝑁 /2, and any two points of 𝑆 are at distance greater than 𝜀. Every ball can be covered by 𝜆 balls of half its radius. Start with a single ball of radius 2, which covers all of 𝑃, and halve 𝑘 times; this covers 𝑃 by at most 𝜆𝑘 balls of radius 21−𝑘 . After 𝑘 = ⌈log2 (4/𝜀)⌉ ≤ 𝑐 + 4 halvings, each ball has diameter at most 𝜀, so it contains at most one point of 𝑆. Since all of 𝑆 must be covered, 𝜆𝑘 ≥ |𝑆 | > 𝑁 /2, hence dim(𝑃) ≥ (log2 𝑁 − 1)/(𝑐 + 4) = Ω(log 𝑁 ). Also, any ball is covered by the 𝑁 balls of half its radius centered at the points, so 𝜆 ≤ 𝑁 and dim(𝑃) = 𝑂 (log 𝑁 ). □ 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

Sajad Faghfoor Maghrebi, Navid Eslami, and Niv Dayan

of Theorem 3 therefore reflects newly added points progressively resolving the manifold. Once 𝑁 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 𝑑 int only holds while 𝑁 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 [71], 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 𝑣 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: 𝑑 (𝑞, 𝑣)/𝑟𝑘 with 𝑘 = 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 hyperball 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 hyperball. The vertical dashed line marks the normalized distance below which 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 [16]. 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.14 Finally, we assume that the distance metric is Euclidean. If an angular metric is used instead, Euclidean distance between ℓ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 [44, 88]. 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 [2] in our proofs, and later argue how the same proofs can be adapted to other graph-based indexes such as HNSW [64] and Vamana [97]. 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., 𝑒 𝑓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, 𝑑 int = Θ(log 𝑁 ). As discussed in Section 4.1, such a value of 𝑑 int causes the number of points within the approximately uniform neighborhood of a query point to be 𝑁 𝑐 , where 𝑁 is the dataset size and 𝑐 ∈ (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 𝑁 . We then show that the same argument implies that SNG’s uniform shortcut cost grows similarly. Reduction to 𝑀-NN 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 𝑀 is small, SNG connects each node to its 𝑀 nearest neighbors with high probability, and (2) if 𝑀 is large, the 14 The maximum-likelihood estimator of local intrinsic dimensionality assumes a

smooth underlying distribution [54], which need not hold in out-of-distribution cases or when the dataset is too sparse.

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

average node degree follows a power law in 𝑁 . In the former case, SNG behaves similarly to an 𝑀-NN graph, which is known to have a power-law search cost [53, 84]. 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 𝑁 , 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 𝑘-th nearest neighbor: Lemma 4 (Connection Probability). Consider a node 𝑢 within a region of the space where points are (approximately) uniformly distributed. Denoting 𝑢’s 𝑘-th nearest neighbor as 𝑣𝑘 and letting Θ(1) 𝑝 ∗ = 𝑑 int · 2−𝑑int /2 = logΘ(1) 𝑁 · 𝑁 −𝑐/2 , 𝑢 is connected to 𝑣𝑘 with a probability of at least 1 − 2 · (𝑘 − 1) · 𝑝 ∗ when 𝑘 ≤ 𝑀. Proof. We observe that the exact version of SNG connects 𝑢 to its 𝑀 nearest neighbors that are not pruned. Recall that a node 𝑣𝑘 is pruned if 𝑢 is already connected to some other node 𝑣𝑖 with 𝑖 < 𝑘 that satisfies 𝑑 (𝑢, 𝑣𝑘 ) ≥ 𝑑 (𝑣𝑖 , 𝑣𝑘 ). This corresponds to the neighbor 𝑣𝑖 being included in the “lune” between 𝑢 and 𝑣𝑘 , as shown in Figure 1-b. Thus, denoting the lune between 𝑢 and 𝑣𝑘 by 𝐿𝑘 , 𝑣𝑘 is pruned with a probability of at most Pr[𝑣𝑘 pruned] = Pr[∃𝑣𝑖 , 𝑖 < 𝑘 : 𝑣𝑖 ∈ 𝐿𝑘 ] ≤

𝑘 −1 ∑︁

Pr[𝑢 connected to 𝑣𝑖 ∧ 𝑣𝑖 ∈ 𝐿𝑘 ]

𝑖=1

≤

𝑘 −1 ∑︁

Pr[𝑣𝑖 ∈ 𝐿𝑘 ].

𝑖=1

Now, we observe that the lune 𝐿𝑘 is comprised of two spherical caps of height 𝑑 (𝑢, 𝑣𝑘 )/2. The probability of a uniformly distributed point 𝑣𝑖 with 𝑖 < 𝑘 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 𝑑 (𝑢, 𝑣𝑘 ) around 𝑢. This quantity is known to be 𝑝 ∗ = Θ(1) 𝑑 int · 2−𝑑int /2 [53, Lemma 2]. Thus, the probability that 𝑣𝑖 is within the lune 𝐿𝑘 is at most 2 · 𝑝 ∗ . Plugging this expression into the sum Í −1 above yields Pr[𝑣𝑘 pruned] ≤ 𝑘𝑖=1 2 · 𝑝 ∗ = 2 · (𝑘 − 1) · 𝑝 ∗ . Finally, noting that 𝑢 must be connected to 𝑣𝑘 if 𝑣𝑘 is not pruned yields Pr[𝑢 connected to 𝑣𝑘 ] = 1 − Pr[𝑣𝑘 pruned] ≥ 1 − 2 · (𝑘 − 1) · 𝑝 ∗, establishing the lemma.

□

Proof. By applying a union bound to the connection probability of Lemma 4, it follows that SNG connects a node 𝑢 to all of its 𝑀 nearest neighbors with a probability of at least 1 − 𝑀 2 · 𝑝 ∗ = 1 − 𝑀 2 · logΘ(1) 𝑁 · 𝑁 −𝑐/2 . Through another union bound, this implies that all of the 𝑛 = 𝑁 𝑐/2 /(2 · 𝑀 2 · logΘ(1) 𝑁 ) nearest points to 𝑥 must be connected to their 𝑀 nearest neighbors with a probability of at least 1/2. □ When 𝑀 = 𝑁 𝑜 (1) , Theorem 5 implies that in the subgraph of SNG restricted to the 𝑁 𝑐/2−𝑜 (1) nearest points of 𝑥, denoted by 𝐺, each node is connected to at most 𝑀 of its nearest neighbors. Since the points in 𝐺 are uniformly distributed, this intuitively implies that each of its nodes is connected to at most 𝑀 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 [53], where the author shows that using greedy search on an 𝑀-NN graph15 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.16 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 𝑀. To analyze SNG’s uniform shortcut cost, we consider the subgraph 𝐺 entry around SNG’s entry point and apply Theorem 5. Then, by invoking the result of [53] for 𝐺 entry , we derive the cost as a power law in the size of the entry point’s neighborhood, i.e., 𝑁 𝑐 for some constant 𝑐 ∈ (0, 1]. As discussed at the beginning of this section, this corresponds to a Sublinear Power Law in 𝑁 . Similarly, to analyze SNG’s locally uniform exploration cost, we consider the subgraph 𝐺 𝑞 around the query 𝑞 and leverage the approximately uniform distribution of its points to apply Theorem 5. This allows us to once again invoke the result of [53] to show that the cost follows a power law in 𝑁 . Case (2) of Large 𝑀. In this case, each node within the approximately uniform neighborhood of the query 𝑞 has a high degree with high probability: Theorem 6 (High-Degree Graph). When the dataset is uniformly distributed and 𝑀 = 𝑁 Θ(1) , each node within the uniform neighborhood of a query 𝑞 has a degree of at least min(𝑀, 𝑁 𝑐/4−𝑜 (1) ) = 𝑁 Θ(1) with a probability of at least 1/2. Proof. If 𝑀 = 𝑁 Θ(1) < 𝑁 𝑐/4 /(2 · logΘ(1) 𝑁 ), a similar union bound to that of Theorem 5 applied to the connection probability of Lemma 4 shows that any node 𝑢 will be connected to its 𝑀 = 𝑁 Θ(1) nearest neighbors with a probability of at least 1/2. If 𝑀 ≥ 𝑁 𝑐/4 /(2 · logΘ(1) 𝑁 ), by the same union bound, any node 𝑢 will be connected to its 𝑁 𝑐/4 /(2 · logΘ(1) 𝑁 ) nearest neighbors with a probability of at least 1/2. □

Lemma 4 has two key consequences in the following two cases of the maximum degree 𝑀: Case (1) of Small 𝑀. This case leads to a large subgraph of SNG being an 𝑀-NN graph with high probability within a region of the space where the dataset is approximately uniformly distributed:

15 More precisely, the graph the author of [53] analyzes connects any two nodes that

Theorem 5 (𝑀-NN Subgraph). Consider a point 𝑥 around which the dataset is approximately uniformly distributed. The 𝑛 = 1/(2 · 𝑀 2 · 𝑝 ∗ ) = 𝑁 𝑐/2 /(2 · 𝑀 2 · logΘ(1) 𝑁 ) nearest points to 𝑥 are connected to their 𝑀 nearest neighbors with a probability of at least 1/2.

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 [53] can be adapted to the setting where the degree is strictly bounded by 𝑀 . 16 Specifically, instead of classic beam search, [53] 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.

Sajad Faghfoor Maghrebi, Navid Eslami, and Niv Dayan

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 𝑁 . As such, the results in the two columns on the left of Table 3 hold in both cases of 𝑀. 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., 𝑒 𝑓construction = ∞), the same Sublinear Power Law results hold.17 The reason is two-fold: (1) When the maximum degree 𝑀 is small, the same analysis as Lemma 4 shows that, with high probability, each node after the first 𝑀 nodes is connected to the 𝑀 nearest nodes from those that were inserted earlier. This does not affect our use of the results in [53], as it only slightly alters the probability of the search encountering a local minimum. (2) When 𝑀 is large, Lemma 4 applied to the 𝑁 /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 [42, Lemma 3.3], the degree of a node in Vamana is at most 𝑂 (2Θ(𝑑int ) · poly log 𝑁 ).18 We further observe that applying the same lemma with a value of 𝛼 = 1 shows that the degree of each node in SNG or HNSW is at most 𝑂 (2Θ(𝑑int ) ). Since, as described in Section 4.1, 𝑑 int = 𝑜 (log 𝑁 ) 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 𝑂 (2Θ(𝑑int ) · poly log 𝑁 ) = 𝑁 𝑜 (log 𝑁 )/log 𝑁 · poly log 𝑁 = 𝑁 𝑜 (1) . Lemma 7 posits that processing a single node, be it in the shortcut phase or the exploration phase, takes 𝑁 𝑜 (1) time. In particular, 𝑑 when 𝑁 ≥ 22 int , we have 𝑑 int = 𝑂 (log log 𝑁 ), which implies that 17 Here, we consider incremental insertion as most practical graph indexes are imple-

mented accordingly. 18 The poly-logarithmic term corresponds to log Δ in [42, Lemma 3.3], where Δ is the

ratio between the longest and shortest pairwise distances of points in the dataset. We have assumed that Δ = poly (𝑁 ) to reflect real-world datasets.

the degree of each node is at most 𝑂 (2𝑂 (log log 𝑁 ) ) = 𝑂 (poly log 𝑁 ). 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 𝑞 by a constant factor [42]. From [53, Lemma 2], we observe that the nearest neighbor of any query 𝑞 is within an expected distance of 𝑁 −Θ(1/𝑑int ) of it, implying that the outer hyper-ball around 𝑞 must have a radius of 𝑂 (𝑁 −Θ(1/𝑑int ) ). Thus, since the distance from the graph’s entry point to 𝑞 is at most a constant when the points are distributed on a sphere, the number of shortcut steps is at 𝑂 (1) most 𝑂 (log ) = Θ((1/𝑑 int ) · poly log 𝑁 ). Multiplying 𝑂 (𝑁 −Θ(1/𝑑int ) ) 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 Ω(𝑁 −1/𝑑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 𝑁 points uniformly distributed on a sphere, with high probability, all steps that take the search closer to a query 𝑞 reduce   log 𝑁 1/𝑑 int the distance to 𝑞 by at most poly(𝑑 int ) · 𝑁 . Proof. Our argument analyzes the maximum length of an edge in SNG. Recall that if two nodes 𝑢 and 𝑣 are connected, then there must be no other node in their lune. By [53, Lemma 2], the probability that a node 𝑤 is within 𝑢 and 𝑣’s lune is poly(𝑑 int ) · 𝑑 (𝑢, 𝑣)𝑑int .   log 𝑁 1/𝑑 int When 𝑑 (𝑢, 𝑣) = 𝑁 , this probability becomes poly(𝑑 int ) · log 𝑁 𝑁 , i.e., the expected number of nodes within the lune is Ω(log 𝑁 ).

By applying a standard Chernoff bound, it follows that such a lune is empty with a probability of at most 1/𝑁 3 . Thus, by a union bound over all pairs of nodes, we can conclude that all edges within SNG   log 𝑁 1/𝑑 int have a length of at most poly(𝑑 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 𝑂 (𝑁 −1/𝑑int ) in expectation. Thus, since the distance from the entry point to a query can be a constant number, Lemma 8 implies 𝑂 (1) that the shortcut phase requires at least 1/𝑑 int = poly(𝑑 int ) · (log 𝑁 /𝑁 )

Ω(𝑁 (1−𝑜 (1) )/𝑑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

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

Cost Modeling

The previous sections established that, across many datasets and scales, query cost follows a Sublinear Power Law in the dataset size 𝑁 , with exponent 𝑐, 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

(a) Query cost model Dataset

Modeling Query Cost

We begin with query cost, asking what determines the exponent 𝑐 for a given dataset. Our approach is to model how 𝑐 varies with the recall target and the construction parameters of the index, and then to connect the predicted cost back to the 𝑒 𝑓search value that realizes it. Parameters. We focus on three parameters that govern how 𝑐 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 𝑒 𝑓construction and the maximum out-degree 𝑀, 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 𝑐, but the rise is not linear in recall. Raising recall from 0.90 to 0.92 barely makes ANN search harder, but raising it from 0.97 to 0.99 does. To capture the nonlinearity, we quantify the demand for recall as 1/𝛿, where 𝛿 = 1−recall. In the previous example, the first increment raises 1/𝛿 from 10 to 12.5, while the second raises it from 33.3 to 100. On the other hand, increasing the construction parameters should lower 𝑐, 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.99, 𝑒 𝑓construction ∈ [100, 800], 𝑀 ∈ [16, 128]), this reversal never appears, and we observe 𝑐 decreasing throughout. Modeling the exponent 𝑐. The simplest model consistent with these effects treats them as independent: each parameter contributes its own term, and the exponent 𝑐 is their sum. Figure 10-a supports

𝑐0

𝛼

𝛾1

𝛾2

𝛽

𝑅𝑐2

(b) Build cost model

𝑅𝛽2

𝜅

𝛽′

𝑐 0′

𝛾 2′

𝑅2

HNSW

5

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 𝑅𝑐2 and 𝑅𝛽2 the respective fits. (b) Build cost model: coefficients of Eq. 4.

sift .244 .035 .012 .022 .762 .919 .992 deep .281 .054 .020 .022 .742 .934 .992 spacev .181 .067 .020 .017 .747 .818 .992 wiki .310 .079 .037 .022 .737 .886 .991 glove .336 .090 .036 .012 .759 .916 .993 rand64 1.068 .022 .055 .082 .812 .912 .992 gist .513 .096 .045 .017 .705 .859 .992 openai .191 .079 .029 .001 .741 .910 .992

2.497 .864 2.163 .880 2.653 .900 2.424 .869 2.147 .917 3.569 .681 1.268 .836 2.197 .858

.031 .020 .979 .048 .018 .983 .002 .024 .963 .032 .018 .991 .052 .023 .977 .028 .044 .922 .155 .015 .991 .063 .019 .981

Vamana

the exploration phase is upper bounded by the number of nodes in this neighborhood. Since 𝑑 int = 𝑜 (log 𝑁 ) in the dense regime, Theorem 1 implies that the number of nodes in the query’s uniform neighborhood is at most 2𝑑int = 𝑁 𝑑int /log 𝑁 = 𝑁 𝑜 (1) . Multiplied by the degree of a node (quantified in Lemma 7), this yields a locally uniform exploration cost of 𝑁 𝑜 (1) , matching the third column of Θ(𝑑 ) Table 3. Moreover, when 𝑁 ≥ 22 int , we have 𝑑 int = 𝑂 (log log 𝑁 ), making the number of nodes in the query’s neighborhood polylogarithmic in 𝑁 . 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.

sift .415 .046 .014 .069 .752 .841 .992 deep .479 .064 .021 .080 .730 .869 .992 spacev .351 .074 .021 .066 .739 .825 .991 wiki .447 .086 .036 .068 .742 .845 .992 glove .480 .086 .027 .059 .760 .835 .993 rand64 1.252 .020 .059 .111 .833 .929 .993 gist .670 .108 .026 .098 .706 .782 .991 openai .334 .081 .025 .046 .714 .947 .991

3.622 .826 3.388 .843 4.253 .857 3.137 .859 3.977 .857 5.239 .764 2.654 .797 4.492 .818

− .076 .041 .977 − .064 .038 .973 − .168 .055 .976 − .059 .037 .986 − .159 .063 .990 − .233 .076 .996 − .018 .046 .985 − .177 .057 .983

this decomposition empirically. Each column isolates the effect of one factor on the exponent (1/𝛿, 𝑒 𝑓construction , 𝑀). 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
𝑐 = 𝑐 0 + 𝛼 ln 𝛿1 − 𝛾 1 ln(𝑒 𝑓construction ) − 𝛾 2 ln(𝑀). (2) Here 𝑐 0 is the baseline set by the dataset’s geometry, 𝛼 the cost of higher demand for recall, and 𝛾 1 and 𝛾 2 the benefits of 𝑒 𝑓construction and 𝑀, 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 𝑅 2 of approximately 0.88, meaning it explains about 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 𝑒 𝑓search . The model above explains how fast the number of distance computations scales as the dataset grows, i.e., how large the exponent 𝑐 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, 𝑒 𝑓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 𝑒 𝑓search : 𝛽

dc/𝑞 ∝ 𝑒 𝑓search .

(3)

Figure 10-c shows this relationship on log-log axes, where the linear pattern indicates a power law, this time between 𝑒 𝑓search and the number of distance computations. The fit is tight across all datasets, with 𝑅 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

0.4

sift

partial residual partial residual partial residual partial residual partial residual partial residual partial residual partial residual

Sajad Faghfoor Maghrebi, Navid Eslami, and Niv Dayan

100

200

H 1 = 0.020 V 1 = 0.021

0.0

400

800

0.4 0.00

0.2 0.2 2 4 6 9 14 22 34 52 80 H = 0.067 0.2 0.50 V = 0.074

100

200

H 1 = 0.020 V 1 = 0.021

400

800 0.00

0.0

0.25

16

H 2 = 0.022 V 2 = 0.080

32

64

128

100 6

H 2 = 0.017 V 2 = 0.066

32

64

128

2 4 6 9 14 22 34 52 80 0.25 H = 0.079 V = 0.086 0.5 0.00

100

200

H 1 = 0.037 V 1 = 0.036

400

800 0.00

6

H 2 = 0.022 V 2 = 0.068

32

64

128

0.0

2 4 6 9 14 22 34 52 80 0.25 H = 0.090 V = 0.086 0.5 0.00

100 200 H 1 = 0.036 V = 0.027 1

400

800 0.0

6

rand64

0.2

2 4 6 9 14 22 34 52 80 H = 0.022 V = 0.020

200

0.2

400

0.25

0.4

0.0

0.5

100

H 1 = 0.055 V 1 = 0.059

0.5 800 0.00

2 4 6 9 14 22 34 52 80 H = 0.096 V = 0.108

64

128

100

200

H 1 = 0.029 V 1 = 0.025

400

800

400

800

64

128

6

220

2 200

400

H = +0.869 V = +0.859

226

4

222 223 224

226 4

c 0H = +0.002 c 0V = 0.168

224 226 3

219 220 221

223

0 c 0H = +0.052 c 0V = 0.159

200

400

H = +0.681 V = +0.764

4

0

64

128

100 6

200 H = +0.836 V = +0.797

400

800

4

219

220

c 0H = +0.028 c 0V = 0.233

5.0

0.25

16

H 2 = 0.001 V 2 = 0.046

32

64

128

2 4 6 9 14 22 34 52 80

100

200

400

efconstruction

H = 0.742 V = 0.730

800

16

32

M

64

128

200

400

H = +0.858 V = +0.818

2 100

H = 0.737 V = 0.742

217

800

0 c

200

400

efconstruction

(c) Beam-Width Model (slope = )

H = 0.747 V = 0.739

220 221

4

c 0H = +0.155 c 0V = 0.018

4

0.25

89.4

31.9

47.9

61.4

78.2

31.9

44.7

33.0

43.7

34.5

45.5 54.6

73.8

32.5

43.1

54.6

67.0

32.5

43.1

56.9

70.4

2H = +0.018 2V = +0.037

2H = +0.023 2V = +0.063

57.5

78.2

55.3

2H = +0.044 2V = +0.076

67.9

2H = +0.015 2V = +0.046

2

0 100

6

68.0

2.5 216 217 218

2

4

51.7

2H = +0.024 2V = +0.055

2

218

800

2

37.5

1 217

800

2 100

87.2

2

1 400

55.1 67.0

2H = +0.018 2V = +0.038

2

0 c 0H = +0.032 c 0V = 0.059

200 H = +0.917 V = +0.857

38.3

2

217 219 221

800

4

16 32 H 0.5 2V = 0.017 2 = 0.098

0.00

0.2

1/

partial residual ln(dc/q)

32

0.5

2 4 6 9 14 22 34 52 80 H = 0.079 0.50 V = 0.081 0.0

6

16

222 223 224

0

4 H 2 = 0.082 V 2 = 0.111

220

800

0.0

0.0

H = 0.762 V = 0.752

400

100 6

1

0.50

100 200 1 H = 0.045 1 V = 0.026 1 0

0.25

200

4 16 32 H 2 = 0.012 V = 0.059 2

0.25 0.0

800

2H = +0.020 2V = +0.041

2

0 c 0H = +0.048 c 0V = 0.064 1

H = +0.900 V = +0.857

100

0.25

0.25

400

4 16

0.25

200

H = +0.880 V = +0.843

100

4

0 c 0H = +0.031 c 0V = 0.076 1

4

0.25

0.2

(b) Build Cost Model

H = +0.864 V = +0.826

4

16

0.25

Vamana 6

0.25

0.0

glove

H 2 = 0.022 V 2 = 0.069

0.2

0.1

2 4 6 9 14 22 34 52 80 H = 0.054 0.4 V = 0.064

deep

0.0

0.0

0.0

wiki

spacev

H 1 = 0.012 V 1 = 0.014

0.1

0.2

gist

openai

HNSW

(a) Query Cost Model

H = 0.035 V = 0.046

219 4

0H = +0.063

c 0V = 0.177

217

800

218

218

2 219

N

H = 0.812 V = 0.833

H = 0.759 V = 0.760

2H = +0.019 2V = +0.057

220

ln M ln N

H = 0.741 V = 0.714

H = 0.705 V = 0.706

4

sift

2 20 80

400

efsearch

3200

deep 20 80

400

efsearch

3200

spacev 20 80

400

efsearch

3200

glove

wiki 20 80

400

efsearch

3200

20 80

400

efsearch

3200

gist

rand64 20 80

400

efsearch

3200

20 80

400

efsearch

3200

openai 20 80

400

efsearch

3200

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/𝛿), ln(𝑒 𝑓construction ), and ln 𝑀 on the scaling exponent 𝑐. (b) Insertion-cost model of Eq. 4: the effects of ln(𝑒 𝑓construction ), ln 𝑁 , and the interaction ln(𝑀) ln(𝑁 ) on average insertion cost ln(dcbuild /𝑁 ). (c) Beam-width model of Eq. 3: ln(𝑒 𝑓search ) vs. ln(dc/𝑞), centered within each configuration; the linear pattern confirms the power law with slope 𝛽.

the same distance computations that govern query cost, and it dominates the cost of insertion [64, 97]. We therefore measure the total number of distance computations during index construction, denoted dcbuild , and study how the average insertion cost dcbuild /𝑁 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

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

dataset size 𝑁 and the two construction parameters, the graph out-degree 𝑀 and the candidate list size 𝑒 𝑓construction . Expected Effects. A larger 𝑁 means each new point searches a larger graph, so insertion cost should rise with the dataset, and since query cost rises with 𝑁 as a Sublinear Power Law, we expect insertion cost to do the same; we empirically verify this power law. A larger 𝑒 𝑓construction makes each insertion explore more of the graph before identifying the new node’s neighbors, so, just as 𝛽 query cost scales as 𝑒 𝑓search (Equation 3), insertion cost should grow as a Sublinear Power Law in 𝑒 𝑓construction . A higher 𝑀 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 𝑀, the average insertion cost is log-linear in both 𝑒 𝑓construction and 𝑁 , as anticipated, verifying the power-law scaling on both counts. Raising 𝑀 increases the power-law exponent of 𝑁 , so a denser graph makes build cost grow faster with dataset size; 𝑀 therefore belongs inside the exponent of 𝑁 . We thus model ′

′

dcbuild = 𝑒 𝜅 (𝑒 𝑓construction ) 𝛽 𝑁 𝑐 ,

𝑐 ′ = 1 + 𝑐 0′ + 𝛾 2′ ln 𝑀.

(4)

Equivalently,   dcbuild ln = 𝜅 + 𝛽 ′ ln(𝑒 𝑓construction ) + 𝑐 0′ ln 𝑁 + 𝛾 2′ ln(𝑀) ln(𝑁 ). 𝑁 The primed symbols mark build-phase analogues of the query model’s coefficients of Section 5.1. The build exponent 𝑐 ′ explains how construction cost scales with the dataset size 𝑁 , the buildphase analogue of the query exponent 𝑐. Within 𝑐 ′ , the leading 1 is the trivial cost of performing 𝑁 insertions, 𝑐 0′ captures how perinsertion search cost grows with index size, and 𝛾 2′ captures how a larger 𝑀 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 (𝑅 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.80–0.92, running 0.07–0.16 above 𝛽. In other words, doubling 𝑒 𝑓construction raises the average insertion cost by about 1.8×. Insertion is thus more sensitive to its candidate list size than query cost is to 𝑒 𝑓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.68–0.76) staying below 𝛽 (0.81–0.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 𝑁 𝑐 , 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 [1] 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 [2] 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. [3] Patrice Assouad. 1983. Plongements lipschitziens dans R𝑛 . Bulletin de la Société Mathématique de France 111 (1983), 429–448. [4] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANNBenchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020), 101374. [5] 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 [6] 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. [7] 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 [8] Keith Ball et al. 1997. An elementary introduction to modern convex geometry. Flavors of geometry 31, 1-58 (1997), 26. [9] 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. [10] Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509–517. [11] Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999. When is “nearest neighbor” meaningful?. In International conference on database theory. Springer, 217–235. [12] Kevin S. Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. 1999. When Is ”Nearest Neighbor” Meaningful?. In Proceedings of the 7th International Conference on Database Theory (ICDT ’99). Springer-Verlag, Berlin, Heidelberg, 217–235. [13] 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. [14] 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. [15] Karl Bringmann. 2021. Fine-grained complexity theory: Conditional lower bounds for computational geometry. In Conference on Computability in Europe. Springer, 60–70. [16] 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). [17] 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. [18] 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. [19] 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. [20] 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

Sajad Faghfoor Maghrebi, Navid Eslami, and Niv Dayan

nearest neighbor search. In Proceedings of the ACM Web Conference 2023. 3225– 3235. [21] 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. [22] 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. [23] 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. [24] Sanjoy Dasgupta and Anupam Gupta. 2003. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures & Algorithms 22, 1 (2003), 60–65. [25] 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. [26] 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 [27] 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. [28] Elastic. [n.d.]. Measuring the Recall of Quantized Vector Search. https://www. elastic.co/search-labs/blog/recall-vector-search-quantization. Elasticsearch Labs blog. Accessed: 2026-07-21. Vector Search and kNN Implementation Guide. [29] Elastic. 2024. https://www.elastic.co/search-labs/blog/vector-search-implementationguide-api-edition Accessed: 2026-04-22. [30] Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. 2016. Testing the manifold hypothesis. Journal of the American Mathematical Society 29, 4 (2016), 983–1049. [31] 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. [32] 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 [33] 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. [34] 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). [35] Lee-Ad Gottlieb and Robert Krauthgamer. 2013. Proximity algorithms for nearly doubling spaces. SIAM Journal on Discrete Mathematics 27, 4 (2013), 1759–1769. [36] 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. [37] 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 [38] 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 [39] Juha Heinonen. 2001. Lectures on Analysis on Metric Spaces. Springer-Verlag, New York. https://doi.org/10.1007/978-1-4613-0131-8 [40] Michael E Houle. 2017. Local intrinsic dimensionality I: an extreme-valuetheoretic foundation for similarity applications. In International Conference on Similarity Search and Applications. Springer, 64–79. [41] 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. [42] 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. [43] 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). [44] 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 [45] 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. [46] 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. [47] 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. [48] 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. [49] William B Johnson, Joram Lindenstrauss, et al. 1984. Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics 26, 189-206 (1984), 1. [50] 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. [51] Andrew Kane. 2023. pgvector: Vector Similarity Search for PostgreSQL. https: //github.com/pgvector/pgvector. Open-source PostgreSQL extension for vector similarity search. [52] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for opendomain question answering. In Proceedings of the 2020 conference on empirical methods in natural language processing (EMNLP). 6769–6781. [53] Thijs Laarhoven. 2017. Graph-based time-space trade-offs for approximate near neighbors. arXiv preprint arXiv:1712.03158 (2017). [54] Elizaveta Levina and Peter Bickel. 2004. Maximum likelihood estimation of intrinsic dimension. Advances in neural information processing systems 17 (2004). [55] 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. [56] 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 [57] Ke Li and Jitendra Malik. 2017. Fast k-nearest neighbour search via prioritized DCI. In International conference on machine learning. PMLR, 2081–2090. [58] Peng-Cheng Lin and Wan-Lei Zhao. 2019. Graph based nearest neighbor search: Promises and failures. arXiv preprint arXiv:1904.02077 (2019). [59] David G. Lowe. 2004. Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision 60, 2 (2004), 91–110. [60] 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://www.cs.princeton.edu/~mfreed/ docs/terminus-mlsys26.pdf [61] 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 [62] 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). [63] 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. [64] 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 [65] 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. [66] Leland McInnes, John Healy, and James Melville. 2018. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426 (2018). [67] Microsoft. 2021. SPACEV1B: A Billion-Scale Vector Dataset for Text Descriptors. https://github.com/microsoft/SPTAG/tree/main/datasets/SPACEV1B. Accessed July 2026. [68] Microsoft. 2026. DiskANN: Graph-Structured Indices for Scalable, Fast, Fresh and Filtered Approximate Nearest Neighbor Search. https://github.com/

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

microsoft/DiskANN. Accessed: 2026-07-15. [69] Milvus. 2024. Index Explained. https://milvus.io/docs/index-explained.md Accessed: 2026-04-22. [70] Gonzalo Navarro. 2002. Searching in metric spaces by spatial approximation. The VLDB Journal 11, 1 (2002), 28–46. [71] 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. [72] NMSLIB. 2026. NMSLIB: Non-Metric Space Library, an Efficient Similarity Search Library and a Toolkit for Evaluation of k-NN Methods for Generic Non-Metric Spaces. https://github.com/nmslib/nmslib. Accessed: 2026-07-15. [73] 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. [74] OpenAI. 2022. New and Improved Embedding Model (text-embedding-ada002). OpenAI Blog. https://openai.com/index/new-and-improved-embeddingmodel/ Published December 15, 2022. Accessed July 2026. [75] OpenAI. 2024. New Embedding Models and API Updates. https://openai.com/ index/new-embedding-models-and-api-updates/. Accessed: 2026-06-22. [76] 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/. [77] OpenSearch. 2024. k-NN Performance Tuning. https://docs.opensearch.org/1. 0/search-plugins/knn/performance-tuning/ Accessed: 2026-04-22. [78] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of vector database management systems. The VLDB Journal 33, 5 (2024), 1591–1615. [79] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Vector database management techniques and systems. In Companion of the 2024 International Conference on Management of Data. 597–604. [80] 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 [81] 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://www.aclweb.org/anthology/D141162 [82] Vladimir Pestov. 2008. An axiomatic approach to intrinsic dimension of a dataset. Neural Networks 21, 2-3 (2008), 204–213. [83] Pinecone. [n.d.]. Hierarchical Navigable Small Worlds (HNSW). https://www. pinecone.io/learn/series/faiss/hnsw/. Accessed: 2026-06-24. [84] Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based nearest neighbor search: From practice to theory. In International Conference on Machine Learning. PMLR, 7803–7813. [85] 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 [86] Qdrant. [n.d.]. Measuring ANN Recall. https://qdrant.tech/documentation/ tutorials-search-engineering/ann-recall/. Qdrant documentation. Accessed: 2026-07-21. [87] Qdrant. 2025. Qdrant: Vector Search Engine. https://qdrant.tech. Accessed: 2026-01-29. [88] 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. [89] 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 paraphrasemultilingual-mpnet-base-v2 model. Accessed July 2026. [90] Redis. 2023. How Hierarchical Navigable Small World (HNSW) Algorithms Can Improve Search. https://redis.io/blog/how-hnsw-algorithms-can-improvesearch/ Accessed: 2026-04-22. [91] 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 [92] Xuan Shan, Chuanjie Liu, Yiqian Xia, Qi Chen, Yusi Zhang, Kaize Ding, Yaobo Liang, Angen Luo, and Yuxiang Luo. 2021. GLOW: Global Weighted SelfAttention Network for Web Search. In 2021 IEEE International Conference on Big Data (Big Data). IEEE, 519–528. [93] 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). [94] Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. Freshdiskann: A fast and accurate graphbased ann index for streaming similarity search. arXiv preprint arXiv:2105.09613 (2021).

[95] 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). [96] 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. [97] Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: fast accurate billionpoint nearest neighbor search on a single node. Curran Associates Inc., Red Hook, NY, USA. [98] 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. [99] Timescale. 2026. pgvectorscale: Postgres Extension for Vector Search with StreamingDiskANN. https://github.com/timescale/pgvectorscale. Accessed: 2026-07-15. [100] Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern recognition 12, 4 (1980), 261–268. [101] turbopuffer. 2024. Continuous Recall Measurement. https://turbopuffer.com/ blog/continuous-recall. Accessed: 2026-06-25. [102] 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-searchwith-diskann-part-1-full-space-search/. Accessed: 2026-07-15. [103] Thomas Veasey and Mayya Sharipova. 2025. Speeding up merging of HNSW graphs. https://www.elastic.co/search-labs/blog/hnsw-graphs-speed-upmerging [104] Vespa. [n.d.]. Nearest Neighbor Search Guide. https://docs.vespa.ai/en/nearestneighbor-search-guide.html. Vespa documentation. Accessed: 2026-07-21. [105] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A purpose-built vector data management system. In Proceedings of the 2021 international conference on management of data. 2614–2627. [106] Mengzhao Wang, Xiangyu Ke, Xiaoliang Xu, Lu Chen, Yunjun Gao, Pinpin Huang, and Runkai Zhu. 2024. 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. [107] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101.12631 (2021). [108] Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas, and Wei Wang. 2024. Steiner-hardness: A query hardness measure for graph-based ann indexes. Proceedings of the VLDB Endowment 17, 13 (2024), 4668–4682. [109] Weaviate. 2024. Vector Indexing. https://weaviate.io/developers/weaviate/ concepts/vector-index Accessed: 2026-04-22. [110] Roger Weber, Hans-J Schek, and Stephen Blott. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. (1998). [111] 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 [112] 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. [113] 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. [114] 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. [115] 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). [116] Zilliz. [n.d.]. AUTOINDEX Explained. https://docs.zilliz.com/docs/autoindexexplained. Accessed: 2026-06-25. [117] 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.

Related documents

• A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search#822540
• NAVIS: Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search#178847
• Overview of Zipf’s Law: Between Mathematics and the Human and Social Sciences#273919
• Search-Bound Proximity Proofs: Binding Encrypted Geographic Search to Zero-Knowledge Verification#2520
• Checks and Imbalances: A Discussion on the Separation of Powers#179692