Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs
Authors: Siddharth Gollapudi
Ravishankar Krishnaswamy
Kirankumar Shiragur
Harsh Wardhan
Venue: ICML 2025 poster (2025)
Keywords: Nearest neighbor search
Primary area: theory
TL;DR: In this work, we enhance the theoretical guarantees of beam search for graph-based ANN methods.

Abstract: Graph-based data structures have become powerful and ubiquitous tools for scalable approximate nearest-neighbor (ANN) search over the past decade. In spite of their apparent practical performance, there has only recently been progress on the **worst-case** performance of these data structures. Indeed, the influential work of Indyx and Xu (2023) introduced the key concept of $\alpha$-reachable graphs, showing that graphs constructed by the DiskANN algorithm (Subramanya, et. al. 2023) produce an $\left(\frac{\alpha+1}{\alpha-1}\right)$-approximate solution with a simple best-first search that runs in poly-logarithmic query time. In our work, we improve and generalize this analysis as follows:
    -  We introduce **sorted** $\alpha$-reachable graphs, and use this notion to obtain a stronger approximation factor of $\frac{\alpha}{\alpha-1}$ for the DiskANN algorithm on Euclidean metrics.
    -  We present the **first** worst-case theoretical analysis for the popular **beam-search** algorithm, which is used in practice to search these graphs for $k > 1$ candidate nearest neighbors.
We also present empirical results validating the significance of sorted $\alpha$-reachable graphs, which aligns with our theoretical findings.

Sort Before You Prune: Improved Worst- Case Guarantees of the DiskANN Family of Graphs
Siddharth Gollapudi
Ravishankar Krishnaswamy Kirankumar Shiragur? Harsh Wardhan"
Abstract
is to design an efficient data structure which, for any query point q E X, and target k efficiently identifies the k nearest neighbors of from P. In real-world applications, these points can be thought of as mathematical representations of online data, such as documents, images, or user behaviors, with their distances being an appropriately chosen metric, such as Euclidean cosine similarity for vector represen- tations of objects, or Jaccard similarity when the dataset P consists of sets of words. In these settings, the approxi- mate version of the problem, abbreviated ANNS, is usually considered instead. For this problem, the data structure is allowed to return sub-optimal results, and its quality is typically measured by the approximation ratio: the ratio of the distances of the bth furthest point identified by the algorithm to that of the true 4 furthest point in the dataset. In more applied papers, a notion of recall@i @ k is instead used to measure the quality of a solution, which is the fraction of true nearest neighbors of a query that are computed by the algorithm in its candidate near neighbors, averaged over all queries.
Graph-based data structures have become pow- erful and ubiquitous tools for scalable approxi- mate nearest-
(ANN) search over the past decade. In spite of their apparent practical perfor- mance, there has only recently been progress on the worst-case performance of these data struc- tures. Indeed, the influential work of Indyk & Xu introduced the key concept of a-reachable graphs, showing that graphs constructed by the DiskANN algorithm (Subramanya et al., 2019) produce an approximate solution with a simple best- first search that runs in poly-logarithmic query time. In our work, we improve and generalize this analysis follows:
We introduce sorted a-reachable graphs, and this notion to obtain a stronger approxi- mation factor of - for the DiskANN algo- rithm on Euclidean metrics.
We present the first worst-case theoretical analysis for the popular beam-search algo- rithm, which is used in practice to search these graphs for k > 1 candidate nearest neighbors.
The ANNS problem has been extensively researched in the theoretical as well applied communities (Beygelzimer et al., 2006; Babenko & Lempitsky, 2014; Johnson et al., 2017; Weber et al., 1998; Baranchuk et al., 2018; Malkov & Yashumin, 2016; Jégou et al., 201 1; Arya & Mount, 1993; Indyk & Motwani, 1998a) and serves as the cornerstone for numerous applications across diverse domains: com- puter vision (Wang et al., 2012), data mining (Camerra et al., 2010), information retrieval (Manning al., 2008), classification (Fix & Hodges, 1989), and recommendation systems (Dahiya et al., 2021), to name a few. With the re- cent explosion of semantic search powered by deep learning models (Devlin et al., 2018) and large language models, the problem is playing an even larger role in powering the AI revolution.
We also present empirical results validating the significance of sorted a-reachable graphs, which aligns with our theoretical findings.
1. Introduction
In the nearest-neighbor search (NNS) problem, there is an underlying metrie space (X, D), where X is a set of points and D X x X - R2o is distance function between points in X. Given a dataset P C X of n. points, the goal
Initial ANNS results have focused on smaller datasets (on the order of millions of points represented as vectors in tens of dimensions), developing a plethora of breakthrough tech- niques centered around space partitioning (Johnson et al., 2017), such as Locality Sensitive Hashing (Indyk & Mot- wani, 1998b; Andoni Indyk. 2008), KD-trees (Arya et al., 1998), and cover trees (Beygelzimer al., 2006), name a
Authors listed alphabetically. 'UC Berkeley "Microsoft Re- scarch India. Correspondence to: Siddharth Gollapudi <sgol- lapu @ berkeley.edu>..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improved Worst-Case Guarantees for DiskANN
few. A potential drawback of these approaches is that the data structure typically needs to sean a very large (expo- nential in the dimension) number of neighboring partitions around a given query's partition to retrieve candidate near- est neighbors, and the problem of quickly identifying these nearby cells to scan becomes challenging. To circumvent these so-called "boundary effects," there has been an evo- lution of graph-based ANNS indexing algorithmss (Malkov & Yashunin, 2016; Fu et al., 2019; Iwasaki & Miyazaki, 2018; Sugawara et al., 2016; Iwasaki; Subramanya et al., 2019), which construct a navigation graph over the dataset P. allowing for a simple greedy walk search algorithm on the graph, which keeps on traversing neighbors provided they are closer to the query w.r.t the metric D. Many dif- ferent comparative studies (Aumüller et al., 2020; Echihabi et al., 2019; Li et al., 2020; Wang et al., 2021) of ANNS algorithms have concluded that these graph-based methods significantly outperform other techniques in terms of search performance on a range of real-world static datasets, and they enjoy usage in industry at scale (Simhadri et al., 2023).
2. The original DiskANN algorithm constructs edges for each node by applying a pruning procedure (with a parameter a > 1) to sorted list of potential candidate edges. However, Indyk and Xu (Indyk & Xu, 2024)'s s proof does not explicitly make use of this sortedness of the list to obtain their guaran- tees. Is this then needed in the original DisKANN algorithm, or can we leverage it to improve our the- oretical bounds?
3. The proof in (Indyk & Xu, 2024) provides guar- antees only for the single best neighbor found via greedy search, relative to the true nearest neighbor of the query. However, in practice, we often retrieve k > candidates using a generalized greedy search known as BeamSearch. Can we obtain any provable guarantees for beam search to get k >> results?
Given the strong empirical performance of these graph- based algorithms, it crucial to understand how they work and to establish provable guarantees on their behav- ior. Recent studies have analyzed the properties of the k-nearest neighbor graph for ANNS- -where each data- point connects to its k closest neighbors. and search pro- ceeds via a greedy walk (Laarhoven, 2017)-ar as well as the impact of adding long-range edges in k-nearest neighbor graphs (Prokhorenkova& & Shekhovtsov, 2020) for random datasets, where points are uniformly sampled from the unit sphere in d dimensions, and the query is placed near data- point.
Our Contributions In this paper, we address all three of these questions. Most interestingly, we show that ques- tions one and two alone cannot offer any improvements, but when combined, can be used to obtain improved analysis of the DiskANN algorithm! Intuitively, it establishes that the sorting step before pruning candidates offers theoretical benefits, and we validate this empirically. Next, we show that our improved analysis techniques can also be used to derive approximation guarantees when using beam search to compute & candidate results. Crucially, to the best of our knowledge, this is the first such result which obtains provable worst-case guarantees for graph methods when requiring to identify k 1 candidate nearest neighbors, which is one of the most common uses of this problem in practice:
More broadly, Indyk & Xu introduce a class of graphs known as a-reachable graphs (the definition of which is motivated by the DiskANN algorithm), achieving prov- able worst-case space and time complexity bounds for any dataset. The importance of this work comes from the fact that it sets apart the structural properties inherent in the DiskANN graph construction from the other methods such as HNSW and NSG, which have a set implicitly to one and thus come without provable worst-case guarantees. In- tuitively, having a > ensures that there are sufficient long-range edges present when the graph is constructed. While it takes an important step towards a theoretical un- derstanding of grsph ANNS algorithms, the work left three important questions, which form the crux of this work:
Theorem 1.1 (Final convergence bounds). Let G be a DiskANN graph. For any query 9. BeamSearch of size L in at most O (a-1)e) steps outputs a set of points (b1....,bu, bL} such that each by satisfies:
D(bj. 9) S c+
a
-Daa,, 9) for lg metric D
a -
a + 1 D(bj. 9) c
D(a,, 9) for any metric D
a a-1
where aj is the jth nearest neighbor q.
1. Indyk & Xu proved that the DiskANN graph construction algorithm achieves an approximation factor of a+1 for any metric. Can we leverage the fact that most modern applications use the Euclidean f2 metric to derive stronger guarantees?
Furthermore, the number of distance comparisons per step in the BearnSearc algorithm is upper bounded by the max- imum degree of the DiskANN graph, which Indyk & Xu showed to be O ((4a)* log 6). where 8 and A denote the dataset's 's maximum distance and doubling dimension, re- spectively. See Section 2 for definitions and further details.
a
2

---

Improved Worst-Case Guarantees for DiskANN
2. Preliminaries
Algorithm BeamSearch(s, (5, q, L)
Notation. Consider a dataset P of n points in a metric space D). For any query point q E X, a top-k nearest- neighbor search (k-NNS) data structure returns the & closest points to q in P based on the distance function D. Since ex- act nearest-neighbor search suffers from the curse of dimen- sionality (Clarkson, 1994), approximate methods are often preferred. In particular, under the following approximation model, if p E P is the ith nearest neighbor of q (i & k). a point p' E P is considered (1 + -)aaprooximttion to p if D(p', ,q) s (1 e) D(p.g) q).
Require: Graph G with start node 8, query g. result size search list size L 2 k
Ensure: Result set L containing k-approx nearest neighbors, and
a set V containing all the visited nodes
1: Initialize sets L <- {s). E 4- 0, and V < 0 [C is the list of best L. nodes, E the set of all nodes which have already been expanded from the list, and V is the set of all nodes which have been visited. i.c. inserted into the list)
2: while L' E + 0 do
3: Let + arg argmingeere D(p, q)
4: Update < LU (Nous (p") ) V) and E + 8 (r')
5:
if [ > I. then
6:
Update L to retain closest L points to
All graphs considered will be directed and represented as G=(M (V, F.), where V is the set of nodes and F is the set of directed edges of the form (u, v) or u + V. For any node E V. let Nour (u) denote its set of out-neighbors, i.e., {u I (u, v) E E}. In graph-based ANNS index structures, the graph nodes correspond one-to-one with the dataset points in P. To simplify notation, we use P to refer both the dataset and the graph nodes. Thus, an edge (p,p') in the graph represents a directed link from p to p', while D'p.p') denotes the metric distance between the corre- sponding dataset points. Similarly, D(p, () represents the distance from p to the query point q.
7:
end if
Update <- VU Nou (p")
9: end while
10: return closest k points from V; V
a D(p".p') for some p* already connected to p. This prevents unnecessary edges while maintaining search effi- ciency.
Algorithm 2 Prune(p, E, a, R)
2.1. DiskANN Algorithm Overview
Require: Graph G. point p E P, candidate set E C P, distance
threshold a > 1, degree bound R
Here we provide a brief overview of the key components of the DiskANN data structure and refer the reader to the original work (Subramanya et al., 2019) for further details.
Ensure: G modified by setting at most R new out-neighbors
for p
1: Update & +- (E U Nout \ {p}
2: Initialize (o <-
At high level, given a dataset P. DiskANN constructs
3: while E * # do
graph with |P] nodes, designed so that a simple greedy
4: Letp" +- arg minp'e D(p.p')
search algorithm efficiently returns good approximate near-
5: Update Nour(p) t Nout (p) U {p"}
est neighbors for a query q. The greedy search starts from a dedicated start node a and iteratively moves to the neighbor-
6:
if Nous [Nou(pp]] = R then break
7:
end if
ing node that is closest to q based on the metric D, stopping when all neighbors are farther than the current node.
E do 10: if D(p", < D(p,p') then
for p'
Update E <- E1((') 12: end if
11:
A generalized version of this search, deseribed in Algo-
rithm I, maintains a priority queue of size L. 2 1, continu- ously refining the queue until a local optimum is reached. This approach, known as BeamSearch, is the standard search strategy for graph-based ANN algorithms (HNSW; Subramanya et al., 2019).
13: end for
14:
end while
The slwwppreprocessing variant sets E = P {p} and al- lows maximum degree of R = n 1, leading to a ((n)) runtime, which is impractical for large datasets. However, the resulting graph is sparse when the dataset has low intrin- sie dimension (formalized in Section 2.2). and the greedy search converges to a good approximate solution (Indyk & Xu, 2024). The prepooeepooesssnng variant mitigates the high computational cost by capping the degree at a predefined parameter R and restricting E to nodes visited during the greedy search in Algorithm before finalizing p' edges. This significantly accelerates graph construction while pre- serving search quality.
The construction of graph for the dataset P can be ap- proached in two ways, as presented in (Subramanya al., 2019) and later formalized in (Indyk & Xu, 2024): a slow- preprocessing variant that illustrates the fundamental graph construction principles, and a fast--peepooesssingg variant that provides an efficient, scalable heuristic approximation for large datasets.
In both variants, each node p selects neighbors from can- didate set & using Prune procedure Algorithm 2, which ensures that edge (p, p') is retained only if D(p.p') <
3

---

Improved Worst-Case Guarantees for DiskANN
2.2. Overview of Indyk-Xu (Indyk & Xu, 2024)
improved empirical performance and enabling the retrieval of multiple (k > 1) nearest neighbors.
For convenience, we summarize the key results from Indyk & Xu, our work builds upon and significantly improves them. We start with the definition of a-reachable graphs. Definition 2.1. A directed graph G is said to be a-reachable for a 2 1 if, for any two nodes a E G, either the edge (v, a) exists or there exists a node / E G such that the edge (v. t) exists and ((t, a) & D(v, a)/a.
3. Overview of Proof
Here, we provide an overview of the proof for our main result, which offers an improved analysis of the DiskANN algorithm and extends it the beam search setting. Our contributions follow natural sequence: we first identify a stronger structural property of DiskANN graphs, use this to derive tighter approximation bounds (especially in Fu- clidean space), and ultimately provide the first provable guarantees for beam search in graph- data structures. The key insight behind our analysis is that DiskANN's s graph construction implicitly maintains a "sorting" property that, when properly leveraged, enables significantly stronger the- oretical guarantees.
In the pro-prsprocessinng variant of DiskANN, every node p considers all other nodes as candidate out-neighbors during the pruning procedure, with Algorithm 2 selecting the final subset to retain. Effectively, this means p's out-neighbors are given by Prune(p, P {p). a, n - 1). For such a graph, Indyk and Xu established the following results.
Lemma 2.2 (a-reachable lemma). For every node E P. if p is connected to the output of Prume(p, P\ (ppp), ap),a,n-1
The starting point of our analysis is subtle yet powerful ob- servation about DiskANN's behavior. Specifically, consider how DiskANN determines the out-neighbors of a node p from a set of candidates using Algorithm 2. While the pre- vious analysis in Lemma 2.2, which shows a-reachability, would hold even without step (4) of Prune meaning we could select any node p* from E - DisKANN explicitly chooses the closest remaining node to This seemingly minor implementation detail has significant theoretical im- plications for the quality of the computed solutions. We now formalize this insight, with a stronger notion of reachability. Definition 3.1 (Sorted c-reachable graphs). Given dataset P. distance metric D and > 1, we call directed graph G to be a sorted a-reachable graph if for any pair of points v, a E P, either the edge (v, a) exists in G or there exists a point t E P such that:
then G(P, E) is a-reachable.
This a-reachhailitty property is crucial for ensuring that the greedy search algorithm converges to high-quality solutions. Before demonstrating this, we first establish that the Prune algorithm produces sparse graphs, which in turn allows us to bound the search complexity of the greedy algorithm.
The sparsity of these graphs is governed by the intrinsic dimension of the data set, quantified by doubling dimension. A dataset has a doubling constant C. if, for any point p E P and radius r > the set P n B(p, 2r) can be cov- ered by at most C' balls of radius r. The doubling dimension A is then defined as log C. In this work, we assume that the datasets have a bounded doubling dimension, a reasonable assumption since many real-world datasets exhibit a sig- nificantly lower intrinsic dimensionality than their ambient space (Aumüller& & Ceccarello, 2019; Cayton et al., 2008).
1. (u, t) is an edge in G
Lemma 2.3 (Degree bound lemma). For every node p E P, p is connected the output of Prune(p, P P([p). a 1). then the degree of p is at most O ((4a) A log 6). where A and ō denote the doubling dimension and the aspect ratio of P.
2. D(t, a) S D(v, a)/a (a-reachability)
3. D(u, t) < D(e, a) (sorting property)
The first two properties define standard a-reachability. The third property, which we refer to as the sorting property, ensures that each vertex connects to closer points before far- ther ones. This property naturally emerges from DiskANN's graph construction and, as we will demonstrate, plays cru- cial role in enabling a tighter analysis in Euclidean space. In this context, Lemma 2.2, combined with the sorting step implicit in Algorithm 2, leads to the following result.
Indyk and Xu rely on these results to establish their main convergence theorem, stated next.
Theorem 2.4 (Convergence theorem). Let G(P, E) be a DiskANN graph constructed with the "soowpprerrcessing"" variant as in Lemma 2.2. Then, for any starting point E P and beam-size L 1, BeamScarch(s, q, 1) +e) -aprrxximate nearest neighbor in a-1
outputs an
[+1
Lemma 3.2 (Sorted o-reachable lemma). Given a dataset P, a distance metric D and an a 1, the "slow prepro- cessing" variant of DiskANN algorithm constructs a sorted a-reachable graph with respect distance metric D.
O (loga (a-1)e) steps and O ((4a)* d) distance com- parisons per step.
Note that Theorem 2.4 applics only when the beam size is 1. In practice, a larger beam size typically used, leading to
We defer the formal proof of the above result to Ap- pendix A. Given that Disk constructs this specialized
4

---

Improved Worst-Case Guarantees for DiskANN
V
(
a
D(vit)
D(t,a)
D(v,t) 5 Dvv.a)
(tt.a)
D(v.a)
Figure 1:
Sorted a-reachablilty property. The intermediate node & must satisfy both D(v, () < D(v, a) and a), s
Figure 2: Vanilla a-reachability property. The intermediate node t only needs to satisfy D(t, a) I D(v,a)/a.
class of sorted a-reachable graphs, we now analyze the qual- ity of solutions returned by beam search on these graphs. Indyk and Xu (Indyk& & Xu, 2024) conducted similar anal- ysis for a-reachable graphs, deriving a recurrence relation that shows how, each step of the greedy search algorithm, either the distance to the query decreases geometrically the search is already sufficiently close to the query. They then use a case analysis to establish the overall approxima- tion quality upon termination. For clarity, we first analyze the local optimality of solutions returned by the beam search algorithm on sorted aeaacchb graphs before presenting the convergence analysis.
In the above optimization problem we seek to find the worst possible arrangement of points which satisfies the struc- tural requirements of our algorithm. The first constraint Dig, v) S D(g, t) captures the fact that our current solution is locally optimal, the constraint D t) I D(u, a)/a follows from the a-reachability property of the graph, the constraint (vv, t) I D(v, a) follows from the sorting prop- erty, and finally, D(a, q) = 1 is standard normalization step for analyzing ratios. Indeed, the approximation ratio is actually Dvv, q) ((, q) which we upper bound by max- imizing D(t, q) (note that D(v. q) I D(t, q) and so this is valid relaxation) while enforcing D(a,g) q) 1. The part where replaced D q) by D g) in the objective function will help in analyzing the beam search result as well.
3.1. Approximation Quality of Local Optimum using Beam Search
We begin by analyzing the quality of a simple greedy search, that is, where the beam size is 1. We take different ap- proach from (Indyk& & Xu, 2024) in our analysis, to fully exploit the structure of the problem. To this end, suppose that we have a query for which the greedy search has already terminated to local optimum point v. and suppose the true nearest neighbor of is data point a. What can the worst possible termination be, for this algorithm? Indeed, it cannot be an arbitrary arrangement of points q. v, and since the algorithm has some structural properties. For example, it must be the case that v does not have edge to a, as otherwise a greedy search would have walked along the edge (v, a) to discover the global optimum a. But when can this edge be pruned? This happens when there exists another point which responsible for (u, a) being pruned, which satisfies additional conditions per Definition 3.1. The crucial observation then is that the approximation ratio achieved by any local optimum solution u can in fact be upper bounded by the following optimization problem.
In our first result we upper bound the objective value the above optimization problem for the general metric.
Lemma 3.3 (Objective value for general metric). When D is general metric, the optimum value of optimization problem 1 is upper bounded by a+1
The proof of this result follows from the triangle inequality and the a-reachable property; see Appendix A.2 for a formal proof. This result provides an alternative formulation the findings in (Indyk & Xu, 2024). Next, we strengthen this guarantee for the important case Euclidean metrics. The proof can be found in Appendix A.3.
Lemma 3.4 (Objective value for Euclidean metric). When D is the Euclidean & metric, the optimum value of opti- mization problem 1 is upper bounded by .-
Intuitively, the strengthening comes because for general met- rics, the optimization problem ends up being a linear pro- gram over the sixteen variables of the form D(x, y) where x, y E {u, q, t, a). which we can optimize. However, when the metrie is Euclidean, problem in terms of dot products (by considering squared distances in the first four constraints as well as the objec- tive function), and replace the metric constraint with the much stronger constraint that enforces that the matrix of the dot-product variables is sesitive-semidefiiiie We can then
re- re-write the optimization
Coop = max (l,,4) such that:
(1)
D(g. v) < D(g,t) t), D(a, < D(u, a)/a D(e,t) t) < a),,)), D(a.g) =1
D(.-)) a metric, i.e. satisfies triangle inequalities
5

---

Improved Worst-Case Guarantees for DiskANN
solve the resulting SDP using a solver to get the desired bounds for any given a. In this paper, we actually give formal geometrie proof for any without resorting to the use of solvers. by using SDP duality. The above two re- sults provide an immediate bound on the quality of the local optimum solution, which we summarize below.
BeamSearch algorithm on G. Then each by satisfies:
D(b a D(aj, ((aj)g)ma for lo metric D
D(b 9) a + -(aa, q) for general metric D
Corollary 3.5 (Guarantee of greedy search). For any dataset P. and query q. the greedy search algorithm ter- minates a local optimum point which an s+t-- approximation to the true nearest neighbor of for arbitrary metrics, which improves to a for Euclidean metrics.
where aj is the jth nearest neighbor to q.
The improvement from a-T to o-T in the Fuclidean met- ric follows directly from the sorting property D(c,t) < Div a) and is tight. In Appendix A.5, we provide beam search examples that confirm the tightness of our bounds.
While the previous result establishes bounds for the near- est neighbor candidate returned by the algorithm, we now extend this analysis to beam search, where we maintain a beam Bg (bb.....bb. of L candidates.
Additionally, we show that without the sorting constraint, the a-I bound remains tight even in Euclidean space. In Appendix A.6, construct an example illustrating this, highlighting the critical role of the sorting property.
To analyze beam search, our approach is the following: let denote the closest member in the optimal solution of L nearest neighbors which is not present in the locally optimal beam, and let v be the element in the locally optimum beam which is closest to a. Clearly, U does not have an edge to a, since otherwise, the beam would improve by including a and evicting by. Therefore, we can define to be the node responsible for blocking the edge (v, a), based the sorted a-reachable condition between and a. Moreover, since t is closer to a than v. it cannot be part of the beam! by virtue of the choice of v. However, because the beam has an outgoing edge to t. we get (tt, q) as an upper bound on (b,, q) for all the elements b, E B2 in the beam, in one shot! We can thus reuse optimization problem I to derive an upper bound on the quality of all points in the beam.
3.2. Convergence Rates of Beam Search
In the previous section, we analyzed the local optimum solution returned by beam search for an arbitrary number of candidates L. We now establish the convergence rate, i.e., the number of steps required for beam search to reach a good approximate solution. To do this, we modify optimization problem 1, which previously captured the guarantees of local optimum, to instead model the progress made in each step when the current point is 3 distant from the local optimum.
max D(I, v) such that
(2)
D(a,t) < D(v.a)
D(c,t) D(e,a).
Lemma 3.6 (Guarantee of beam search). Let G be sorted a-reachable graph with respect to distance function D. For any query point q E Rd, let BL = {bi.....bl, bL} be a local optimum solution of size L, with respect to the BeamSearch algorithm on G. For each j E [L]. define B₁ = (by....bb) as the first i points in the beam. Then each by satisfies:
D(a,g) = 1, and D(g, u) S 3 Copt
D(-,-) is metric, i.e., satisfies triangle inequalities
In comparison to optimization problem 1, the key difference is the addition of the constraint D v) S Cppt + 8, which bounds the distance from the local optimal solution. Here, quantifies the deviation from local optimality, and it should decrease with each step. To establish this, we bound the ob- jective value of the new optimization problem and show that the point f, identified via the sorted a-reachable property as a neighbor of u, satisfies D(t, q) S Copp + +B/a. Thus, by moving to i, we achieve progress by a multiplicative factor of a.
D(b, 9) S a
arg min P(..p) for l metric D a B
++ 1
arg min D(g.p) for general metric D g(b;,q)= a pEG.ppB,-1
This pointwise guarantee immediately demonstrates that the beam search maintains quality approximations for each position in the beam as summarized below.
Lemma 3.8 (Objective value bound for general metric). In optimization problem 2, the maximal value of D(1 q) is at 2 under general metric D.
most a+1
Theorem 3.7 (Pointwise guarantec of beam search). Ler G be a sorted a-reachable graph with respect to distance func- tion D. For any query point q E Rd. let B2 = {bI...., ., by} be a local optimum solution of size returned by the
Lemma 3.9 (Objective value bound for Euclidean metric).
In optimization problem 2, the maximal value of D(t, q) is at most a + 2 under Fuclidean metric D.
a
6

---

Improved Worst-Case Guarantees for DiskANN
The proofs of the above results follow similar reasoning as Lemma 3.3 and Lemma 3.4. Specifically,, for the gen- eral metric case, it relies on the triangle inequality and the a-reachable property, while for the Euclidean case. it involves formulating optimization problem 2 as an SDP and constructing a feasible dual solution with the required value. The full proofs are deferred to Appendix B.I and Appendix B.2, respectively.
the impact of sorting for past-preproeessing version of DiskANN. Specifically, compare two implementations of DiskANN: one where we sort the candidate neighbors provided to Algorithm 2, and one where we do not. We first state the setup for our evaluations and describe our datasets, and then we explain the DiskANN implementation. We then present two figures comparing 100@ 100Recall to QPS and the average number of distance comparisons performed during search.
It follows directly from optimization problem 2 and the up- per bound on the objective value that we achieve a progress factor of a in each step. Consequently, the beam search with size converges to a good approximate solution in log,r time steps. The proof for larger beam sizes follows a similar approach as our analysis of local optima for higher beam sizes. Applying the same reasoning, we derive the following main convergence result.
4.1. Setup
Hardware. We conduct all experiments on a bare-metal gegh-performance workstation with dual Intel Xeon Gold 5218 CPUs (32 cores, 64 threads) and 256GB DDR4 RAM.
Datasets. We evaluate on the following datasets: the well- known SIFTIM (Jegou et al., 2010), and three modern real- world workloads comprising of OpenAl embeddings encod- ing abstracts scraped from Arxiv, Cohere embeddings of pas- sages from Wikipedia articles (Cohere, 2022), and a large- scale dataset web search dataset generated using the Mi- crosoft SPACEV model (Xu et al., 2023). We obtained these datasets from the BigANN benchmark repository (Simhadri et al., 2024) at the url https://big ann wann-eechmarrssccom the details regarding the datasets can be found in Table 2.
It is immediate from optimization problem 2 and the upper bound on its optimum value that we make a multiplicative factor a progress in each time step. Thus it is immediate that the beam search with size converges to a good approximate solution in log, time steps. The proof for larger beam sizes follows a similar approach as our analysis of local optima for higher beam sizes. Applying the same reasoning, we derive the following main convergence result.
and
Theorem 1.1 (Final convergence bounds). Let G be DiskANN graph. For any query q, BeamSearch of size L in at most O(I + loga (a-1 steps outputs a set of points (bI...., bb} such that each by satisfies:
Dataset
Dimension
Document
Query
OpenAl
1536
2,321,096
20,000
SIFTIM
128
1 1,000,000
10,000
D(b,,9) S a-1 1
a
D(aj, for &g metric D
Wikipedia
788
35,000,000
5,000
SPACEV
100
100,000,000
5,000
a a+1 D(aj, for any metric D
D(b,, S set
a-1
Table 1: Dataset information
where aj is the jth nearest neighbor to
DiskANN Configuration. We use the ParlayANN DiskANN implementation to construct our instances and to build and search indices for these datasets (Manohar et al., 2024). We use the default DiskANN parameters for an in- memory build: a is set to be 1.2 for all the index builds, with max degree set 64 and beam-widde parameter Louild set to 100. During search, vary the beam-widte param- eter Leearch- The average degree of the graph constructions by DiskANN implementation with and without sorting are summarized below.
The detailed proofs of the above convergence result is pro- vided in the Appendix B.3. Together, these results establish that sorted a-reachable graphs not only provide better ap- proximation guarantees but also ensure rapid convergence to these improved solutions. Our improved bounds have sig- nificant practical implications, particularly for the common case of Euclidean distance. The reduction from (a+1)/(a-1) to (d((a1) means that for typical values of a (e.g., a=2), we reduce the worst-case approximation ratio from 3 to 2. This tighter theoretical guarantee helps explain DiskANN's strong empirical performance and suggests that implementa- tions should explicitly maintain the sorting property during graph construction.
Dataset
Sorted
Unsorted
OpenAl
53,899
56,924
SIFTIM
44.523
49.153
Wikipedia
24.660
30.730
4. Experiments
SPACEV
46.155
51.020
To complement our thcoretical analysis for the slow- preprocessing variant of DiskANN, we empirically study
Table 2: Average Degree per Constructed Graph
7

---

Improved Worst-Case Guarantees for DiskANN
SAM 10NE
0.81
100
D80
195 23
6/6
2514 199
2000
1800
0Te
Dataset: OpenAl
Dataset: SIFT
Dataset: Wikipedia
Dataset: SPACEV
Figure 3: The above plots illustrate the Queries per Second (QPS) versus 100@ 100 Recall for sorted a-reachable and standard a-reachable graphs.
0.800
Dataset: OpenAl
Dataset: SIFT
Dataset: Wikipedia
Dataset: SPACEV
Figure 4: The above plots illustrate the average number of distance comparisons versus 100@ 100 Recall for sorted a- reachable and standard a-reachable graphs.
Butdcf danc
1.344
12:50 2010 2000 2010 E0000000000
075
3003
6000
015
10000
18300
Dataset: OpenAl
Dataset: SIFT
Dataset: Wikipedia
Dataset: SPACEV
Figure 5: The above plots illustrate the average maximum approximation ratio versus 100@ 100 Recall for sorted a-reachable and standard a-reachable graphs.
Dataset
Sorted (s)
Unsorted (s)
recall achieved at the cost of different average distance comparisons per query, which is more indicative of the qualitative impact of the sorting step, and avoids any machine specific metrics.
OpenAl
910.7
1049
SIFTIM
20.91
24.35
SPACEV
1902
2352
Wikipedia 6068
7829
Approximation Ratio. We verify that the approxi- mation ratio for the sorted setting is better than the unsorted setting. We look at the average approxima- tion ratio: the mean over all queries. of the maximum over all items i in the final beam, of the distance of the ith candidate computed by the algorithm upon the ith closest NN.
Table 3: Build Times for Sorted and Unsorted Graphs
4.2. Main Empirical Evaluation
100@ 100 Recall Evaluations. For this benchmark, we evaluate the recall of our indices against a pre-computed bruteforce "groundtruth." We measure performance of these indices on basis of two metrics:
4.3. Results
In Table 2 and Table 3, see that DiskANN consistently produces denser graphs and takes longer build them in the unsorted setting. The unsorted index has an average degree 6 %% 10%, 25 %. and 11% higher than the sorted index for OpenAI, SIFTIM, Wikipedia, SPACEV, respectively. In addition, the unsorted index has build time that is 13.18 % 14.12%, 22.48% %, and 19.13 % slower for the same datasets.
Queries per Second. As mentioned, we evaluate recall along a curve by varying Lyearch from 10 to 400. As Lsearch increases, the corresponding queries per second (QPS) simply refers to the number of queries our index is able serve per second in multi-threaded setting.
Average Distance Comparisons. We also measure the
8

---

Improved Worst-Case Guarantees for DiskANN
5. Conclusion
Reca 11 1000100000 Disk
Unsorted Instance
In this work, we present improved approximation guaran- tees of the DiskANN family of graphs for Euclidean metrics, by exploiting the sorting step the algorithm performs during index construction. We also introduce techniques to analyze the approximation quality of the widely used beam search algorithm for retrieving L >> candidates. Finally we ex- perimentally validated the importance of the sorting step in index construction over diverse datasets. An interesting line of research going forward in understanding how we can similarly exploit the structure for other real-world metrics obtain improved guarantees, like we did for lg in this work.
-
Sorted Instance
Racar100@9100
634
190
Figure Plot illustrating the Disk IOs used versus the 100@ 100 Recall for sorted and standard o-reachable graphs.
For QPS (Figure 3), the unsorted index is slower across the board. The sorted index achieves 5%, 8%, and 7.5% higher QPS for SIFTIM (at 99% recall), OpenAl (at 90% recall), and SPACEV (at 95% recall), respectively.
For average distance comparisons (Figure 4), the sorted index is again superior. It uses 10% fewer comparisons for SIFTIM (99.9% recall), 6% fewer for OpenAl (90% recall), and 18% fewer for SPACEV (95% recall).
For the mean max approximation ratio, we see difference to the results of the prior experiments: the sorted index offers superior QPS across all datasets except OpenAl. This in spite of the numbers favoring the sorted indices for this dataset the rest of our evaluation. The sorted indices are worse by 25% % OpenA/ (at 1.008 approx. ratio), but better by 9% SIFT (at 1.001 approx. ratio) and 17% on SPACEV (at 1.020 approx. ratio).
As an additional sanity check on our claims on large-scale indices, we build a based index on the SPACEV dataset. As shown in Figure 6, the recall of the unsorted index is worse for every disk IO usage: at worst, 400 disk IOs, the sorted index has approximately 0.5 % improved recall.
For Wikipedia, the sorted index offers vastly superior perfor- mance to the unsorted index, in comparison to the smaller improvements shown for the other dataset. Along with the peculiar approximation ratio issues with the OpenAl dataset, we leave further study of these datasets in this setting for future work.
In conclusion, higher density graphs is usually associated with higher recall, and comes at the cost of latency. Despite the unsorted index forming denser graphs, we note that recall remains inferior to the sparser and faster sorted index, emphasizing the importance of the sorting step during index construction.

---

Improved Worst-Case Guarantees for DiskANN
Impact Statement
International Conference on Machine Learning, ICML
'06, pp- 97-104, New York, NY, USA, 2006. Associ- ation for Computing Machinery. ISBN 1595933832. doi: 10.1 10.11455114984441144888 org/10 11e./1145111111 1484444.4444 1143857.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
URL https: https::/doi. /doi.
Camerra, A., Keogh, E.,, Palpanas, T., and Shieh, J. isax 2.0: Indexing and mining one billion time series. In 2013 IEEE 13th International Conference on Data Mining, pp. 58-67, Los Alamitos, CA, USA, dec 2010. IEEE Computer Society. doi: 10.1109/CCM.2200..222 124. URL https://don www.eeeeteeerrcccccc..........ee wtw.sooctiittttoooo.ooooooo 10. www11199IIMM... 2010..2011.1.
References
Andoni, A. and Indyk, P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Communications of the ACM, 51(1):117-122, 2008.
Arya, S. and Mount, D. M. Approximate nearest neigh- bor queries fixed dimensions. In Proceedings of the Fourth Annual ACM-SIAN SIAM Symposium Discrete Algo- rithms, SODA '93, pp. 271-280, Philadelphia, PA, USA, 1993. Society for Industrial and Applied Mathematics. ISBN 0-89871-313-7. URL http: /dl..1l00 acm. org/ citation wwweeeffiiiiiniieeee 316768.
Cayton, L. et al. Algorithms for manifold learning. eSchol- arship, University of California, 2008
Clarkson, K. L. An algorithm for approximate closest-
point queries. In Proceedings of the Tenth Annual Sym- posium on Computational Geometry, SCG '94, pp. 160- 164, New York, NY, USA, 1994. ACM. ISBN 0-89791- 648-4. doi: 10.1145/1774244177769, URL http:
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., and Wu, A. Y. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. /ttpa////oo/oooooo/////////////1 the ACM (JACM), (5()))))55(6)99)1 45(6)8811-923, 1998.
Cohere.
Cohere wikipedia-22-12-e--embbee ttteps://augginggfaceeeo
Aumüller, M. and Ceccarello, M. The role of local intrinsic dimensionality in benchmarking nearest neighbor search. In Similarity Search and Applications: 12th International Conference, SISAP 2019, Newark, NJ, USA, October 2-4, 2019, Proceedingss, pp- 113-127, Berlin, Heidelberg, 2019. Springer- Verlag. ISBN 978-3-030-300 000-3--0003204---11 doi: 10. org 005//00.107///
Cohere http://g.......cootttaeteeeeeeee
2022. Accessed: 2010-09-30.
Dahiya, K., Saini, D., Mittal, A., Shaw, A., Dave, K., Soni, A., Jain, H., Agarwal, S., and Varma, M. Deepxml: deep extreme multi-label learning framework applied to short text documents. In Proceedings of the 14th Inter- national Conference on Web Search and Data Mining, WSDM '21, New York, NY, USA, 2021. Association for Computing Machinery.
11. URL https::///// //do... /oo. 3200--8222788811 11.
Aumüller, M., Bernharssson, E., and Faithfull, A. Ann-benchmarks: A benchmarking tool for ap- proximate nearest neighbor algorithms. Informa- tion Systems, 87, 2020. ISSN 0306-4379. URL http::/ww/r atticcle/p11/000044479113333
Devlin, J., Chang, M., Lee, K., and Toutanova, K. BERT: pre-training of deep bidirectional transformers for lan- guage understanding. CoRR, abs/1810.04500 2018. URL http: http://axxvvvv... org/ abs 1100.000000 048005
http://www.ccienediree..com wttp::/wwwwiinnnceeeee...ec com/ semm//cienee///////e/ee/
Babenko, A. and Lempitsky, V. S. Additive quantiza- tion for extreme vector compression. In 2014 IEEE Conference on Computer Vision and Pattern Recogni- tion, CVPR 2014, Columbus, OH, USA, June 23-28, 2014, pp. 931-9388 IEEE Computer Society, 2014. doi: 10.1 201109/CVVR.2214..00 10. 1109 CVVR. 201...2........... 2014. 124.
Echihabi, K., Zoumpatianos, K., Palpanas, T., and Ben- brahim, H. Return of the lernaean hydra: Experimental evaluation of data series approximate similarity search. Proc. VLDB Endow,, 13(3):403-200, 2019, doi: 10. 14778//336829993366333 URL http::/www. hwtp://wwww..bb...../../.. vldb. org org/pvldb/von 10/1113/pppp 3/ wws--eehhhaii.pp..c
http::/ /tt.doi..rrr///////////
Baranchuk, D., Babenko, A., and Malkov, Revisiting the inverted indices for billion-scale approximate nearest neighbors. In The European Conference Computer Vision (ECCV), September 2018
Fix, E. and Hodges, J. L. Discriminatory analy- sis. nonparametric discrimination: Consistency prop- erties. International Statistical Review / Revue Inter-
nationale de Statistique, 57(3):238-24 1989. ISSN
Beygelzimer, A., Kakade, S., and Langford, J. Cover trees for nearest neighbor. In Proceedings of the 23rd
03067734, 17515823. URL http: //wp:////wwww///// jstor. org/stable/1403799
10

---

Simhadri, H. V., Krishnaswamy, R., Srinivasa, G., Sub- ramanya, S. J., Antonijevic, A., Pryce, D., Kaczynski, Improved Worst-Case Guarantees for DiskANN
Fu, C., Xiang, C., Wang, C.,, and Cai, D. Fast approximate nearest neighbor search with the navigating spreading-out graphs. PVLDB, 12(5):461 474, 2019. doi: 10.14778/ 3303753.3303754. URL http:// /wwww vldb. org/ wwlabb/oo11/p44/1
Malkov, Y. A. and Yashunin, D. A. Efficient and robust ap-
proximate nearest neighbor search using hierarchical nav- igable small world graphs. CoRR, abs/ 2016. URL http: aww.v org/ abs
09320.
Manning, C. D., Raghavan, P., and Schütze, H. Introduction Information Retrieval. Cambridge University Press, USA, 2008. ISBN 0521865719.
HNSW. Hnsw github. URL attps://githuu com/ nms1 htthh//hhwwwl hb/blbbbbooo ob/ wttp///ttee/eaappll/////e//////e python/EXAMPiLn md.
Manohar, M. D., Shen, Z.,, Blelloch, G., Dhulipala, L., Gu, Y., Simhadri, H. V., and Sun, Y. Parlayann: Scal- able and deterministic parallel graph-based approximate nearest neighbor search algorithms. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Prin- ciples and Practice of Parallel Programming, PPoPP '24, pp. 270-285, New York, NY, USA, 2024. Associa- tion for Computing Machinery. ISBN 9798400704352. doi: 10.1 10.1145/3227533333844777 URL https: /doi. o org /1g/10..1 114 /111111//3335555111 3638475
Indyk, P. and Motwani, R. Approximate nearest neigh- bors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Sympo- sium Theory of Computing, STOC '98, pp. 604-613, New York. NY, USA. 1998a. ACM. ISBN 0-89791- URL http:
962-9. doi: 10.1 00.1145/276998226668878 //doi. acm. 1ttp////...11177766622222223
Indyk, P. and Motwani, R. Approximate nearest neigh- bors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604-613, 1998b.
Prokhorenkova, L. and Shekhovtsov, A. Graph-based near- est neighbor search: From practice to theory. In Interna- tional Conference on Machine Learning, pp. 7803-7813. PMLR, 2020.
Indyk, P. and Xu, H. Worst-case performance of popular approximate nearest neighbor search implementations: guarantees and limitations. Curran Associates Inc., Red Hook, NY, USA, 2024.
Iwasaki, M.
URL https://github... com/ yahoojapan/ BeetanNNGT/Aan NGT/TGGti /iiki.
D., Williams, S., Gollapudi, S., Sivashankar, V., Karia, N., Singh, A., Jaiswal, S., Mahapatro, N., Adams, P., Tower, B., and Patel, Y. DiskANN: Graph-structured Indices for Scalable, Fast, Fresh and Filtered Approx- imate Nearest Neighbor Search, 2023. URL https: www.icroooot/tsskkkkaeeo
Iwasaki, M. and Miyazaki, D. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data, 10 2018.
//github.
Jegou, H.. Douze, M., and Schmid, C. Product quantization for nearest neighbor search. IEEE transactions pattern analysis and machine intelligence, 3371):117-128, 2010.
Simhadri, H. V., Aumüller, M., Ingber, A., Douze, M.. Williams, G., Manohar, M. D.,, Baranchuk. D., Lib- erty, E., Liu, F, Landrum, B., et al. Results of the big ann: Neurips'22 23 competition. arXiv preprint arXiv:2409.1 WWVv:2409.11422 17424, 2024.
Jégou, H., Douze, M., and Schmid, C. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117~ 128. January 2011, doi: 10. 11109TTAMM..000..55 URL https:/ / /halhhahhh inrri. fr http//nnraa00000
Subramanya, S. J., Devvrit, F., Kadekodi, R., Krishnawamy, R., and Simhadri, H. V. Diskann: Fast accurate billion- point nearest neighbor search on single node. In Wal- lach, H. M., Larochelle, H., Beygelzimer, A., d' Alché Buc, F., Fox, E. B., and Garnett, R. (eds.), Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8- 14 December 2019, Vancouver, BC, Canada, pp. 13748-13755 2019.
Johnson, J., Douze, M., and Jégou, H. Billion-scale similar- ity search with gpus. arXiv preprint arXiv: 2017.
Laarhoven, Graph-based time-space trade-off's for approx- imate near neighbors. arXiv preprint arXiv:17/2.031158 2017.
Sugawara, K., Kobayashi, H., and Iwasaki, M. On ap- proximately searching for similar word embeddings. pp. 2265-2275, 01 2016. doi: 10. 10.18653/v/PP16-1144
Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., and Lin, X. Approximate nearest neighbor search on high dimensional data experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering. 32(8):1475-1488 2020. doi: 10.1 109/000F/ 2909204.
Wang. J., Wang. J., Zeng, G., Tu, Z., Gan, R., and Li, S. Scalable k-nn graph construction for visual descriptors. In 2012 IEEE Conference on Computer Vision and Pattern

---

Improved Worst-Case Guarantees for DiskANN
Recognition, pp. 1106-1113, June 2012. doi: 10.1 CVPR.2012.6247790.
Wang, M., Xu, X., Yue, Q. and Wang, Y. A compre- hensive survey and experimental comparison of graph- based approximate nearest neighbor search. CoRR, abs/2101.12631 2021. URL URl.httts://rrxi..org abs abs/2101.12 12631.
Weber, R., Schek, H.-J., and Blott, S. quantitative anal- ysis and performance study for similarity-search meth- ods in high-dimensional spaces. In Proceedings of the 24rd International Conference Very Large Data Bases, VLDB '98, pp. 194-205, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc. ISBN 1-55860-566- 5. URL http:/ / /dl. acm. org/ http:/iiatiiin..oooooeo cfm?
id 645924. 671192.
Xu, Y., Liang. H., Li, J., Xu, S., Chen, Q., Zhang, Q. Li, C.,, Yang, Z., Yang, F,, Yang, Y., et al. Spfresh: Incremental in-place update for billion-scale vector search. In Pro- ceedings of the 29th Symposium on Operating Systems Principles, pp. 445-561,74 2023.
12

---

Improved Worst-Case Guarantees for DiskANN
A. Approximation Quality of Local Optimum using Beam Search
Here we provide proof for the approximation guarantee achieved by local optimum solution of the beam search algorithm.
A.1. Proof for Lemma 3.2
Here we show that the slow-preprocesssnng variant of DiskANN constructs a sorted a-reachable graph. Lemma 3.2 (Sorted a-reachable lemma). Given dataset P, distance metric D and a >> the "slow preprocessing" variant of DiskANN algorithm constructs sorted a-reachable graph with respect distance metric D.
Proof. Proceed with contradiction. For an appropriate DiskANN graph G(V, E), suppose there exists pair of points V, E V such that there does not exist satisfying the conditions of Definition 3.1. We have two cases:
1. There exists an edge from e to This would satisfy the requirements of Definition 3.1, and trivially contradicts our assumption.
2. There does not exist an edge from e to a. Then, by Algorithm 2, there must exist another node u E V that was considered before a that pruned a. This implies that D(u, v) z (a, v), and by the prune condition, Du, a) S D(v, a)/a. Thus, we can u to be again contradicting our assumption.
A.2. Proof for Lemma 3.3
Here we provide the proof for Lemma 3.3 that upper bounds the optimum value of optimization problem for the case of general metric.
Lemma 3.3 (Objective value for general metric). When D is general metric, the optimum value of optimization problem 1 is upper bounded by a+1 a-1
Proof. The proof of this lemma follows from a repetitive use of triangle inequality and a-reachable property.
D(g.1) S a( + D(a,t) S D(g,a) a) + D(a,v)
a)q,a)+ D(a, g) + D).
D(a, 9) + D(g.t)
$ a(q.a) +
a
a+1
D(g. (1+ -- a)..a).
In the first and third inequality we used triangle inequality. The second inequality uses the a-reachability constraint. the fourth inequality we used local optimality of Finally, the fifth and sixth inequality, we rearranged and simplified the expression.
A.3. Proof for Lemma 3.4
Here we provide the proof for Lemma 3.4 that upper bounds the optimum value of optimization problem for the case of Euclidean metric. Lemma 3.4 (Objective value for Euclidean metric). When D is the Euclidean & metric, the optimum value of optimization problem is upper bounded by -
Proof. We first re-state the optimization problem we wish to upper bound.
max D(4,)) q) such that:
(3)
D(g, u) < D)g,t), t)a,t) 5 D(v.a)// D(e,t) t) $ a(,,a), D(a.g) =1
D(s.) is metric, i.e. satisfies triangle inequalities
13

---

Improved Worst-Case Guarantees for DiskANN
By squaring the terms, and relaxing the fourth equality an inequality, obtain the following vector program, which is essentially semi-definite program. The goal is to find the worst configuration of vectors in euclidean space which optimize the objective.
max || d|| such that:
(4)
|1g - u|1² < l1g =|l?, a²1 f/1 S 1|0 1o--aj al2
|/e - =|| & ||e all², 11q all? 1
The optimum objective value of optimization problem 3 we wish to bound, is then the square-root of the optimum value of optimization problem 4.
See that we can leverage weak duality of semidefinite programs upper-bound the objective function of optimization problem 4, and thus achieve an upper-bound for optimization problem 3. In order do so, we first introduce dual variables for each of the constraints of optimization problem 4:
A1 0,0,
200
A 2 0,
A4 2 0,
As is standard practice in deriving dual program, we first write the Lagrangian by multiplying all constraints with their dual variables (Lagrangian multipliers) and subtracting objective function of optimization problem 4 from it.
L(g, a, = -11- + A1 (1lg =ll² - |1q -=12) + X2 (a2lla - e12 - 11 - all?)
+>a (Ilu 111 - ||v - -all²) + da (1ly all²)
The resulting dual program is follows,
min X2 such that:
(5)
C(t, ((,)
A3 (2a-1) and 0 -(--1) Note that substituting these values dual variables, we get that, L(t, q, v, a) simplifies to perfect square, thus implying non-negativity for all the values f, q, U and and the feasibility of the dual constraints is satisfied. Therefore n is lower bound of the dual optimization function, giving an upper-bound on the optimal value for optimization problem by weak duality.
Now,let A1 --1. d2 (2a-1)(a-1)>
A.4. Proof for Lemma 3.6
Here we provide proof relating the objective value of the optimization problem 1 and the approximation ratio achieved by the beam search algorithm.
Lemma 3.6 (Guarantee of beam search). Let G be sorted a-reachable graph with respect to distance function D. For any query point q E Rdd let B1 (b1,...,bL) bL} be local optimum solution of size L with respect to the BeamSearch algorithm G. For each j E [T.,, define By = (bI....bbj] bi} as the first j points in the beam. Then each by satisfies:
D(b,, 9) S
a
arg min D(g.p) for l2 metric D BE
a -
D(b,, g) < a +
arg mig D(g.p) for general metric D
pEG
Proof. Let a be the first true nearest neighbor that is not in Br- We define := arg argming D(bj,a). Now using sorted-a reachability condition between and there exists such that
D(t, a) < D(c a)
14

---

Improved Worst-Case Guarantees for DiskANN
and D(e,)) 1) Du,, a) Since current beam is locally optimal
D(v. 9) S D(t.q)
Since é closer to a than v, cannot part of the beam. However, because the beam has an outgoing edge to t, we get [tt, q) as an upper bound on D(b, 9) for all b, Bz. Thus we try to maximize D(t, q). Now this maximization problem can be formulated as following optimization program.
D(I, g) such that, D(a,g)
(6)
D(g, v) s t), D(a,t) s D(o,a) D(u,t) s D(c,a).
We can always rescale this reported instance to make the distance between and unit; hence we can reformulate optimization problem 6 as optimization problem 1.
Thus, the optimal value of optimization problem under Copt then
D(br,q) I D(a,g)
D(t,q) D(a.g)
I Cppt
Thus after reshuffling we get
D(br, ②) S C'opt arg min D(g.p) p) p
Furthermore, using 3.6 and 3.4 we get the following result for the Euclidean metric.
D(b ②) S arg min d(g.p) p)
peG.
Using 3.6 we get the following result for the general metric,
+ arg min D(g.p)
D(bL, S a pE
A.5. Tight examples for local optimum solutions
Lemma A.1. For any 1, there exists point set P of 2L + points and query point q in 2 dimensional plane under euclidean distance function, such that there exists an locally optimal beam (bi...., br} such that:
d(br.9) = (-=1) (0-1) ===)===== d(ag.9)
where is the jth nearest neighbor to
Proof. We begin by constructing the point set P. Let:
L points {ui, U2 . Ur.) be co-located at the coordinate (- g.g 0).
A point / be located at (2, 0).
L points {a,, ......, } be co-located (g
1 v I
The query point y be located at (0, 2
2 2x-
15

---

Improved Worst-Case Guarantees for DiskANN
Now, consider the sorted a-shorteut graph over P. In this graph, there no edge between any is and aj, i.e., for all i,
d(t, a4) s d(t, vi)
and d(t, v.) - d(aj, va).
Furthermore, we observe that:
d(t. 9) = d(v..g) for each
Thus, the set {01 12..... ................................ f2 forms locally optimal beam.
Next, we show that the ratio d(vs.)) equals 1. d(ag-n)
Using the construction of the points and applying basic Euclidean distance calculations, we find:
d(v;,g) a-1
d(a,,
This completes the proof, showing that the set {Ui, , indeed forms a locally optimal beam, and the ratio of distances satisfies the given relation.
Lemma A.2. For any a > 1, there exists a point set P of 2L + points and a query point in 2 dimensional plane under general metric function, such that there exists an locally optimal beam .b, such that:
a + 1 (a-t a 11-1) d(ay.g)
d(b,,
where aj is the jth nearest neighbor to
Proof. We begin by constructing the point set P. Let:
L points {Ei, , ) be colocated, such that the distance between any two points e and by is zero. i.c., d(v,, for all i,
A point / be located such that the distance from to any i is d(t,, v.) = 2,
L points {a1, ....... aL be colocated, such that the distance from a, to any is d(aj, v.) distance from any aj is -يب
2a a-1
for all i, and
The query point g be located such that the distance from to any a, is d(g,a,) = 1, and the distance from to any 8; is d(q,, U:) a-1*
a+1 and d(q,t) t)
at1
a-1"
The above distance function forms a metric space. Now, consider the sorted a-shortcut graph over P. In this graph, there is no edge hetween any v; and aj. i.e., for all i,j.
d(t, < d(t,v)) vi)
and d(t, v.) S d(a,, 0z).
a
Thus, the set foi, V2, u2,.... .., forms locally optimal beam. And from the distance know the ratio d(v..g) d(ay.)) a-1"
equals a+1
A.6. Tight example without sorting constraint
Here we provide an example showcasing the importance of the sorting constraint. The construction of the example is as follows. Let t, a, q & all lie on x-axis abscissa st1 contain only 3 points f, and A complete directed graph with edge (v.a) removed is valid a-shorteut graph on P. Now and are equidistant from q, but approximation Note that since all these points lie on x-axis this holds for any 4, norm.
a-1* -1, and s+1 respectively. Now consider our point-set P to a-1
for query point if the search is at is at locally optimal solution
ratio for this case would be D(v.g) which is a+1
D(a.q)
a-!"
16

---

Improved Worst-Case Guarantees for DiskANN
B. Convergence analysis of beam search
For convenience, we restate optimization problem below.
max D(t, q) such that:
D)a,t) & a(v,a)
D(u,t) s ((,
D(a, =1, a
D(g. v) s 3 + Copt
Recall that Copt is optimal value of optimization problem 1 under metric D.
B.1. Proof for Lemma 3.8
Here we upper bound the objective value of optimization problem 2 for general metric D. The formal statement and proof given below.
Lemma 3.8 (Objective value bound for general metric). In optimization problem 2, the maximal value of D(t, q) is at most under general metric D.
a+1
Proof. By triangle inequality we have that,
D(1,)) & D(t,a)+ D(a,
using first constraint, that is the a-reachable constraint, we can rewrite the above equation as,
D(t, S D(v,a) -D(a q)
Using triangle inequality on D(e, a) and substituting value of D(v, q) and D(a, q) from the third and fourth constraint to get the desired bound as follows:
D(t.g) - D(v, g) + D(a,g)
+ D(a,9)
s + a a+1
3
8 a+l + (1+ 1)) x D(a,g))
a (a - l)a
a a-l
B.2. Proof for Lemma 3.9
Here we upper bound the objective value of optimization problem 2 for the Euclidean metric case. The formal statement and proof are given below.
Lemma 3.9 (Objective value bound for Euclidean metric). In optimization problem the maximal value of D(t. 9) is at most + under Euclidean metric D.
Proof. For convenience, let D be defined by - In our optimization problem, we can accomplish this by squaring all terms, giving the following modified version of optimization problem 2:
max D(1, g) such that:
(7)
D) D(a. 21, D(a.g) $ D(a,t) < a²
g+ a a- )
D(v,t) < D(v.)), D(g.v)
17

---

Improved Worst-Case Guarantees for DiskANN
Indeed, || _ can be expressed dot products of vectors, allowing expand optimization problem 7 into the following semidefinite program:
max(1" - 2-21--10000 q + d²4)
such that:
(8)
a² - d'a-2a" t v² 22- a + a²a
a²
a' 20 q q 92
d' - 20 T 1 1 11
v0 + fttttt 1505000- v- a
d' 24 u + u [ [++a 8+a=1 -
a
We will again leverage weak duality of semidefinite programs to upper-bound the objective function of 7, and thus achieve an upper-bound for 2. In order to do so, we first introduce dual variables for each of the constraints of 7:
A 0, 20 20 2
2 0
As is standard practice in deriving dual semidefinite program, we first construct the following constraint (for all values of 0, t):
C(t,q,1,a) = (a"a-20T+ 20 + 10-22'aaaaaa A2 aa=a- a 9 qt
a²
+ Aa (at a 20 q + g" 4) + h4 (v-u-200 1- 1 w²
20 0 a²
+ A (q" q 29 v + u u² - (f" 2t T 9"9))
This gives the following dual program:
+ do ( B
a a -
2
min A2 d
such that:
(1,, 20
Now, consider the following values for each of the dual variables:
1
1 a
3(a² - 1) + a²
\1
1
2
a(a + -a2-1)(2a 1)3 + (2a 1)a?
8
1 ( (st )
a²
A
d3
B+
a _-
a
a
8(a - 1)2 + a²(a (a -1
1 B + a² B
M = a(a - 1)2 + (a 12a - 1)B + (2a - l)a² A
a² +
Under these dual variables, L(I, q, v, a) simplifies to perfect square, thus implying non-negativity the values t, g, v, and and the feasibility of the dual constraints. Therefore ( بي 2 an upper-bound bound on the optimal value from equation 7 by weak duality.
is the value of the dual optimization function, giving
18

---

Improved Worst-Case Guarantees for DiskANN
B.3. Proof for Theorem 1.1
With the above lemmas we are now ready to prove Theorem 1.1 and we begin by stating few intermediate results.
Let be the vertex whose out-neighborhood Nout (v) is explored in the 7thh step. A step is successful if the first point of change in the beam is above (or before) the position of v in the beam: D(v, g) > (0)
(x, g)), where B(
denotes the state of the beam at step i. Otherwise, we call the step unsuccessful. Intuitively, an unsuccessful step makes no progress towards convergence, as no expanded out-neighbor has been added that is closer than to
First, we show that after unsuccessful steps, the ith member of the beam, denoted by vs is arbitrarily close to the 2t member of the locally optimal beam denoted by aç-
Lemma B.1. After unsuccessful steps, the following holds for 1th member is of the beam:
D q) I Copt D(a,, q)
Proof. We call a node in the beam inactive its neighborhood explored and results an unsuccessful step. node Up position p in the beam is inactive, then the first p members of the beam constitute locally optimal beam, and by Lemma 3.6 we have:
Deep q) S Copt D(ap: q).
(10)
Note that a node can become freshly inactive only if all the nodes above it are inactive. After i unsuccessful steps, there i inactive nodes, and each of these nodes became inactive at position less than equal to index i. Therefore, by Equation 10, each of these i inactive nodes has distance to q at most Clopt D(a;, 4).
Since the i-th element in the current beam, denoted by us is either one of these inactive nodes or has distance to g less than or equal to that of at least one of these i inactive nodes, it follows that:
D(u; 9) S Copt D(ai, 9)
This completes the proof.
Next, we show that after a series of successful steps, the 7th node in the beam upon completion of those steps gets close to the query as summarized the lemma below.
Lemma B.2. Consider a DiskANN graph G on n points with respect to a metric D, such that the maximal value of optimization problem I under Copp and the optimal value of optimization problem is less than -. Consider a query q and let the th member of the beam after S successful steps be (1,9)) The The following then holds for UQ,S))
r
a²
-2+1) D(a,,9)
D(v(.s), S 5- max
Copt: a²
Proof. We proceed with proof by induction over the number of successful steps S.
Base case: For S < i steps, that the following holds by the triangle inequality:
D(v(,s): 9) < D(vuss) a.) + D(a,,)) 9) S S + D(as.))
Induction claim: For all S < j. we claim that the following holds
D(v ②) < a- + max (oopt a² =1 D(a;,g)
a²
Induction Step: Let LL) be the lowest index in the beam that changes in the 4 successful step. Then, (Lz(K) must be the closest node to g introduced by 4ith successful step. Note that as a node's 's index in the beam gets closer to 1, its proximity to q also decreases.
19

---

Improved Worst-Case Guarantees for DiskANN
If LI()) then the beam given by (11.--1)----. is locally optimal by the definition of a successful step and of
LT(j). Therefore, if LT()) > i, Lemma 3.6 gives us:
(ia() 2) S Copt D(as; q)
As result, we need only show that for all steps < j. the following holds: LI(k) I i.
LI()) < i, then ((((s))) 4) must upper-bounded by D(V( 4), as o(1-1.5-1) would be pushed back in the beam by V(,L(()))- Therefore,
D(vGS) 9) S 1(0))-15-1).))
$ ((--))((--1) + Copt D(a;-1,9)
If LI()) = i, we run into two cases. For the case where the neighborhood some node below 0(1--1) explored, ((..)-))..((()j-))) must be a locally optimal beam. Therefore, we get:
D(v ②) S Copt D(as 9)
If ((1.-1) 's neighborhood is explored we have two (sub-)cases. For the case where U(j,)) a;, the approximation ratio trivially holds. Next, consider the case where V(i.j) o a; Since the now-preprocessing version of DiskANN is sorted a-reachable, we can define the following function for any pair (p.q):
9
if (p.q) E otherwise
f(.
arg min
D(i, q)
Let a be the closest vertex to which is not in the beam. Consider a series nodes S where
U(i--1), f(S:-1,ao).
if =
S
otherwise
See that Sint = dos and by the definition sorted a-reachabilltyy we have
D(S411, D(S,, a.)
Now, let the smallest index such that S, s neighborhood has not been explored by the beam search, Note that such an index always exists because S 1(1.-11) * a and Sint & B, where denotes the beam)
After 1 steps, see that
Copt: a 12+1) a² 1 D(a.q)
D(v ②) = 3 + max
In addition, we can show after j steps
D(vas): 9) < 3
a²+1)
max
Copt: a² -
D(a,g)
(11)
20

---

Improved Worst-Case Guarantees for DiskANN
We examine I 2 3,
D(S,, q) - DS,, 0o) + D(ao:)) q)
(triangle inequality)
D(v(as-)):00) D(a.:9)
(definition of St)
a²
D(v(G.-1):
+D(g + -(aa. :)
(triangle inequality)
a²
D(((..-1).))
+1 +1
+
D(as.g) q)
(definitions of Si)
a²
a²
+ max
Copts
a2+1 a=I
D(aor 4)
a² + D(ao,)) 9)
(Equation (11))
a²
a² + + max
Copts a1+1 a+=1
8
+
D(as: 9) (definitions of S₁)
a
a²
8
a2+1) D(ao. 9)
+ max Copt: a²
a
For = 2, we know S2 is an out-neighhor of v. Therefore, we can write
D(a,t) < D(r,a)
a D(v(as-1) St) - D(v,a)
We also rescale all the distances to make D(a, q) to be unit length, giving
D(a, 4) =
D(g,)) v) S B + Olopt.
where 3' is 3 after rescaling. In addition, by Equation (2), the distance between S, and g is bounded by Copt + 8 Therefore, we get
8
a=+11
D(v 9) max Copts
D(a.g)
a²2 -
a
and by comparing with equation from induction step
r
a² 1²+1) Copt: a²
D(v(s))
max
D(a,9)
aJ-i
Theorem (Final convergence bounds), Let be a DiskANN graph. For any query q, BearnSearc of size L in at most O(L log, (--1)e) steps outputs a set of points (bI....,bL, bb} such that each by satisfies:
a - D(b,, 9) S +
a
D(a,, for Eg metric
D(b,. s + a+1
D(a,, 9) for any metric D
where aj is the jth nearest neighhor to q.
Proof. Combining Lemma B.1 and Lemma B.2 we get that after i steps the following inequality holds,
r
a² +1+1 111 D(a. 9)
D(va,, 9) < a + max Capt: a² - 11
21

---

Improved Worst-Case Guarantees for DiskANN
which can be seen parallel from inequality (1) from Theorem 3.4 in (Indyk & Xu, 2024). Further substituting the value of Oopt from Lemma 3.8 for general metric and from Lemma 3.9 for Euclidean metric and following the proof similar that of (Indyk & Xu, 2024) we get our main result.
22


Reviews:
[{"review_id": "Hx6wOZTyIq", "reviewer": "Reviewer_USgk", "summary": "This paper addresses the problem of Approximate Nearest Neighbor Search (ANNS), which is crucial for various applications dealing with large datasets in high-dimensional spaces. Graph-based data structures, particularly those in the DiskANN family, have shown strong empirical performance. However, theoretical understanding of their worst-case behavior has been limited. This work builds upon the concept of alpha-reachable graphs introduced by for DiskANN, which provided the first provable worst-case guarantees. The authors identify three key open questions from that prior work:\n1.  Can stronger guarantees be derived for the Euclidean  metric, commonly used in practice?\n2.  Does the sorting step before pruning in the DiskANN algorithm contribute to the theoretical guarantees?\n3.  Can provable guarantees be established for beam search, the practical algorithm used to retrieve k > 1 nearest neighbors?\nThis paper aims to answer these questions, offering improved theoretical analysis for DiskANN, especially in Euclidean spaces, and providing the first worst-case guarantees for beam search in graph-based ANNS methods for retrieving multiple neighbors.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their kind words and thoughtful suggestions. As suggested by the reviewer, we have included a link to plots on two large 100M-scale datasets from big-ann-benchmark, confirming the importance of sorting irrespective of dataset size. We will include all of these plots in the final version of our submission. For convenience, we also include a table capturing one such plot for the 100M-scale Microsoft SPACEV dataset, comparing QPS to 100@100Recall. See that for this dataset, the sorted index outperforms the unsorted index, delivering 23% higher QPS for a recall of ~0.93.\n\n(Anonymized Dropbox link) Large Scale Experiment Plots: https://www.dropbox.com/scl/fo/mp2cq55hz6bbd7rswojyu/AHJF6oHGCVUt5xz6Ah-OPao?rlkey=rt7dvticzt2jlsvq3pkf4nncf&st=7z86irq4&dl=0\n\n| Row | Unsorted QPS | Unsorted 100@100 Recall | Sorted QPS | Sorted 100@100 Recall |\n|-------|---------------------|-------------------------------|-----------------------|----------------------------------|\n| 1     | 98,408              | 0.9044                        | 108,715               | 0.9132                           |\n| 2     | 88,007              | 0.9101                        | 95,070                | 0.9184                           |\n| 3     | 80,488              | 0.9153                        | 88,984                | 0.9228                           |\n| 4     | 76,305              | 0.9197                        | 84,397                | 0.9268                           |\n| 5     | 71,054              | 0.9235                        | 78,176                | 0.9301                           |\n| 6     | 63,347              | 0.9302                        | 68,483                | 0.9358                           |\n| 7     | 57,392              | 0.9357                        | 61,069                | 0.9405                           |\n| 8     | 54,370              | 0.9381                        | 58,041                | 0.9425                           |\n| 9     | 42,049              | 0.9479                        | 44,921                | 0.9505                           |\n| 10    | 33,312              | 0.9541                        | 35,845                | 0.9560                           |\n| 11    | 27,583              | 0.9587                        | 29,182                | 0.9602                           |\n| 12    | 22,502              | 0.9621                        | 23,804                | 0.9634                           |", "claims_and_evidence": "Authors introduce sorted α-reachable graphs, and use this notion to obtain a stronger approximation factor of α/(α−1) for the DiskANN algorithm on Euclidean metrics. Authors present the first worst-case theoretical analysis for the popular beam-search algorithm, which is used in practice to search these graphs for k > 1 candidate nearest neighbors.", "methods_and_evaluation_criteria": "The proposed algorithm is similar to the DiskAnn graph, except that the proposed method e sort the candidate neighbors before pruning the graph, and the baseline method does not. Authors then compare the graph degrees, recall, and QPS on modern hardwares.", "theoretical_claims": "Authors define the sorted alpha reachable graph as follows. Given a dataset P, a distance metric D and α > 1, a directed graph G to be a sorted α-reachable graph if for any pair of points v, a ∈ P, either the edge (v, a) exists in G or there exists a point t ∈ P such that:\n1. (v, t) is an edge in G\n2. D(t, a) ≤ D(v, a)/α (α-reachability)\n3. D(v, t) ≤ D(v, a) (sorting property)\nAuthor argues that when performing beam search on a sorted alpha reachable graph, the worst case is tight on the bounds:\nD(b_j , q) ≤ α/(α − 1) · D(a_j , q) for L2 metric, and D(b_j , q) ≤ (α + 1)/(α − 1) · D(a_j , q) for general metric, where a_j is the j'th nearest neighbor to q.", "experimental_designs_or_analyses": "Authors provided benchmarks on three datasets: OpenAI, SIFT-1M, and Wikipedia, with the baseline DiskANN implementation from ParlayANN. The benchmark and analysis compared the graph degrees, recall, and QPS on modern hardwares.\n\nIt could be interesting to see if the method scale to larger datasets that big-ann provides (https://big-ann-benchmarks.com/neurips23.html). Or if the method generalizes to other small datasets provided by ann-benchmarks (https://ann-benchmarks.com/index.html)", "relation_to_broader_scientific_literature": "-", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "-", "questions_for_authors": "Can authors provide more benchmarks such as the big-ann (https://big-ann-benchmarks.com/neurips23.html) or  ann-benchmarks (https://ann-benchmarks.com/index.html)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Xgl1OzI5nG", "reviewer": "Reviewer_gnMJ", "summary": "This paper conducts a theoretical analysis of graph-based approximate nearest neighbor search algorithms. In particular, the authors propose a new theoretical framework called the $\\alpha$-reachable graph and, using this framework, provide the first worst-case complexity analysis of beam search in situations where $k > 1$.\n\n## update after rebuttal\nAfter the rebuttal, I decided to keep my original score, WA.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments and suggestions. We will address all typos and wording mistakes in the final version. We want to emphasize one point: in addition to giving the first analysis for beam search, which is widely used in practice, we also improve the current state of the art approximation guarantees for the DiskANN algorithm, when the underlying metric is euclidean. This suggests that DiskANN may perform better under the $\\ell_2$ metric compared to other distance metrics.\n\nRegarding experiments for quantifying the solution quality, we include a link to plots demonstrating average approximation ratio across queries versus QPS for two large 100M-scale datasets: Microsoft SPACEV and BIGANN (https://big-ann-benchmarks.com/neurips23.html) for different values of $k$. The average approximation ratio is the mean over all queries, of the maximum over all items $i$ in the final beam of size $k$, of the distance of the $i$th candidate computed by the algorithm upon the $i$th closest NN. \n\n(Anonymized Dropbox link) Approximation Ratio Plots: https://www.dropbox.com/scl/fo/y76d8hn51pkl097g6yaa0/AGyI89kxLaI8ouvgG8FNjRM?rlkey=xahf5obtefjqz35jj1yig6p3r&st=5h6r0brf&dl=0\n\nFor convenience, we include the raw data for the BIGANN approximation ratio plot below. Note that for an approximation ratio of 1.008, the sorted instance supports a QPS of around 58000 (row 7)  while the unsorted instance supports a QPS of only 25000 (row 11).\n\n| Row | Unsorted Instance QPS | Sorted Instance QPS | Unsorted Approximation Ratio | Sorted Approximation Ratio |\n|-------|-----------------------|---------------------|-----------------------------|---------------------------|\n| 1     | 84464.5              | 93165.4            | 1.02061                     | 1.01429                   |\n| 2     | 78923.5              | 85955.7            | 1.01918                     | 1.01336                   |\n| 3     | 76587.9              | 79858.2            | 1.01795                     | 1.01257                   |\n| 4     | 71633.8              | 76934.9            | 1.01704                     | 1.01140                   |\n| 5     | 67506.9              | 67532.4            | 1.01612                     | 1.01064                   |\n| 6     | 59775.7              | 61504.0            | 1.01384                     | 1.00933                   |\n| 7     | 53310.9              | 58497.7            | 1.01267                     | 1.00846                   |\n| 8     | 51330.2              | 54442.5            | 1.01221                     | 1.00796                   |\n| 9     | 40633.4              | 42155.7            | 1.01029                     | 1.00675                   |\n| 10    | 32898.3              | 32861.8            | 1.00907                     | 1.00579                   |\n| 11    | 27124.3              | 28039.5            | 1.00812                     | 1.00524                   |\n| 12    | 22319.7              | 23551.2            | 1.00726                     | 1.00451                   |", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This paper advances the theoretical development of graph-based algorithms in approximate nearest neighbor search. In particular, it is a direct extension of [Indyk & Xu 2024].", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "## Strengths\n\nThe greatest strength of this paper lies in its extension of [Indyk & Xu, 2024] to analyze the worst-case complexity of beam search for $k > 1$. \n\nIntroducing the $\\alpha$-reachable concept is intuitive, and the problem setup is straightforward without conceptual difficulties.\n\nAdditionally, Problem 1 in Sec 3.1 is formulated clearly, and the restructuring of the problem in this way is intriguing. The proofs are elementary to follow.\n\nMoreover, the insight that a dual problem can be considered when transitioning from a general metric $D$ to the Euclidean distance is well-motivated and interesting.\n\n## Weaknesses\n\nThere are no major concerns, but if anything, the experiments in Sec 4 focus on illustrating the concept of \"sorting\" rather than supporting the paper's primary claim regarding worst-case complexity. It would be interesting to see a more direct evaluation of how the proposed bounds relate to general high-dimensional vector data.", "other_comments_or_suggestions": "In Sec A.4 of the supplementary material, the statement \"hence we can reformulate 6 as 1\" appears to be a typo and should likely be \"hence we can reformulate objective 6 as problem 1.\" Similarly, there is inconsistency throughout the paper regarding whether to write \"1\" or \"problem 1.\" I recommend unifying this notation. If only a number is used, it would be more precise to enclose it in parentheses as \"(1).\"", "questions_for_authors": "I have no particular questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None."}}, {"review_id": "6SYLXZrcBW", "reviewer": "Reviewer_fRUc", "summary": "This paper introduces a novel strategy for constructing graph structures to enhance Approximate Nearest Neighbor Search (ANNS) on high-dimensional vectors. This approach ensures a superior approximation ratio for L2 distance metrics compared to existing methods.\n\n## **Update After Rebuttal**\nThe rebuttal has carefully addressed these comments. Since I have no more concerns now, I have raised my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s detailed feedback and would like to clarify the key contributions of our work. Rather than proposing a new algorithm that outperforms DiskANN, our primary contribution is theoretical, providing a deeper understanding of the DiskANN algorithm in two key ways.\nFirst, we establish an improved approximation guarantee for DiskANN by leveraging two critical insights: (a) explicitly analyzing the $\\ell_2$ setting, which is widely used in practice and has favorable mathematical properties, and (b) examining the _sorting_ step in the prune procedure. Using these insights, we introduce a novel factor-revealing SDP to demonstrate an improved approximation factor of $\\frac{\\alpha}{(\\alpha - 1)}$, compared to the previously known bound of $\\frac{\\alpha + 1}{\\alpha - 1}$ from Indyk and Xu (NeurIPS 2023). Moreover, we show that omitting either sorting or the $\\ell_2$ setting results in a best possible approximation ratio of $\\frac{\\alpha + 1}{\\alpha - 1}$, matching Indyk-Xu’s original result. This suggests that DiskANN may perform better under the $\\ell_2$ metric than other distance metrics.\n\nSecond, we introduce techniques that establish the first-ever theoretical bounds for retrieving $k > 1$ candidates in a beam search setting using a graph-based ANNS algorithm. Despite its practical significance in scalable retrieval, this regime remains underexplored, with prior work (NeurIPS 2023, ICML 2020, SoCG 2018, SODA 1993) exclusively focusing on the $k = 1$ case. We also believe our factor-revealing LP/SDP framework will be valuable for further research in this setting. In short, our core contribution lies in the theoretical understanding of the sorted prune step in DiskANN, and to support our theoretical findings, we conducted experiments evaluating the impact of sorting during graph construction. We did not compare DiskANN with other ANNS algorithms, as this has been extensively studied in prior work.\n\nWe thank the reviewer for suggesting additional experiments. Based on the suggestions, we include plots and tables for 100M-scale datasets, key metrics such as build times, and RAM usage and disk I/O reads per query (for SSD-based indices). Please note that all dropbox links are anonymized. This comprehensive empirical study will be included in the final version.\n\nLink to DiskIO plots: https://www.dropbox.com/scl/fo/c44n8ij92zpt19qdedw1o/AJ-GeHiB6-38q1eRqJ7XYSw?rlkey=yfvqwr98038o4xuvq9dj1ghcy&st=ws3cd67g&dl=0\n\nLink to RAM usage and Build Times: https://www.dropbox.com/scl/fo/v3cdv5iv76aryqcrh639x/AJgfthBn3IFAVaUGdWGzHwU?rlkey=ghddj7evgo7ldcrl1whc6st7m&st=nsjbz81n&dl=0\n\nLink to Large-Scale dataset plots: https://www.dropbox.com/scl/fo/mp2cq55hz6bbd7rswojyu/AHJF6oHGCVUt5xz6Ah-OPao?rlkey=rt7dvticzt2jlsvq3pkf4nncf&st=j4saygfe&dl=0\n\n**Q1 (varying k)**:\n\nOn two large scale datasets, we have included plots of Recall@k vs. QPS for different values of k to analyze the effect of sorting during pruning. The search behavior remains consistent with our observations for k= 100. \n\nLink to varied-k plots: https://www.dropbox.com/scl/fo/m6f1pdq01npiy0dlv2ueq/AJa2AL5Ij3J1S8hhkvVhax8?rlkey=6f83rhwgkafme6s6v6r4ke3v6&st=um503h2h&dl=0\n\n**Q2 (degree reduction and varying dimension)**:\n\nWe appreciate the reviewer’s insightful question. While the degree does decrease for graphs built using sorted pruning on real-world datasets (as shown in Table 2), there is no clear correlation between this decrease and data dimensionality.\nConsider a simple one-dimensional example: let $p, a, b, c$ be four points on a line with distances $d(p,a)=1$, $d(a,b)=0.5$, and $d(b,c)=1.5$. The sorted algorithm would connect p to both $a$ and $c$ to maintain $\\alpha$-reachability, whereas a more efficient algorithm could instead connect $p$ to $b$ while still preserving $\\alpha$-reachability. This example illustrates that degree change is not tied to dimensionality.\nAdditionally, a lower degree does not necessarily translate to improved performance, as latency depends on both the average degree and the graph’s diameter. A reduced degree may increase the graph’s diameter, making the impact on final latency difficult to predict.\nTo further investigate the effect of data dimension on the performance of sorted vs unsorted index construction, we conducted an additional experiment on the OpenAI dataset. We used a random Johnson-Lindenstrauss matrix to project the 1536-dimensional OpenAI embeddings into a 352-dimensional space and measured the degree change due to sorting. With sorting, the average degree was 54.15; without sorting, it increased to 57.3—a 5.8% rise. This aligns closely with the 5.6% increase observed in the original dataset (Table 2), suggesting that the degree change is a property of the dataset rather than a direct function of dimensionality. So it might be more a function of the inherent structure of the dataset as opposed to the dimension itself.", "claims_and_evidence": "Regarding the theoretical results, the claims are generally okay for me. However, the evaluations have certain issues (please refer to the following comments).", "methods_and_evaluation_criteria": "The proposed sorted α-reachable graphs can achieve faster search performances than the existing method DiskANN. However, in the experimental studies, this paper only conducts evaluations on 3 relatively small-scale datasets, and only reports the results of the search efficiency. Quite a few critical metrics are ignored, so the proposed solution may not be practical enough under the general evaluation criterias under benchmarks of ANNS.", "theoretical_claims": "The theoretical results look okay and may offer insights to existing research. However, the proposed approximation ratio appears to be limited under L2 distance.", "experimental_designs_or_analyses": "In terms of the experimental designs, I have the following comments:\n\n1. **Dataset Scalability**: The datasets used in the experiments are relatively small. The authors should evaluate their method on larger-scale datasets containing over 100 million or even 1 billion vectors to demonstrate scalability and robustness. In particulr, the competitor DiskANN is designed for in-disk index, which aims to handle billion-scale vectors.  \n\n2. **Evaluation Scope**: The experimental study focuses only on the application scenarios of in-memory indexes. Except for the new graph structure, DiskANN also contributes to ANNS over large-scale data that needs to be stored on disk. This application scope should be emphasized and validated in the experiments.\"\n\n3. **Baseline Selection**: If authors try to claim that their contributions lay on the novel graph structure, they may have to compare their methods with other existing graph-based ANNS index like NSG [PVLDB2019] and NSSG [TPAMI22].\n\n[VLDB2019] Cong Fu, Chao Xiang, Changxu Wang, et al. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. PVLDB, 12(5): 461-474, 2019.\n\n[TPAMI22] Cong Fu, Changxu Wang, Deng Cai. High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility. IEEE Trans. Pattern Anal. Mach. Intell. 44(8): 4139-4150 (2022)\n\n=====================   \nThe rebuttal has carefully addressed these comments, so I have no concerns on these issues now.", "relation_to_broader_scientific_literature": "This paper propose a new strategy for ANNS index with a better approximation ratio.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. How does varying k (e.g., increasing from 20 to 100) affect search performance?\n\n2. For OpenAI dataset (dimension = 1536), the average node degree decreases from 56 to 53, while for SIFT1M (dimension = 128), it decreases from 49 to 44 (a similar trend is observed in the Wiki dataset). Does this imply that the performance of the proposed strategy diminishes as the dimensionality of the vectors increases?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "JI1FwHIorp", "reviewer": "Reviewer_eMvk", "summary": "This paper aims to strengthen the theoretical analysis of graph-based ANN algorithms. In DiskANN indexing, candidate vertices are considered in ascending order from their distance to the out-vertex $v$, a detail not leveraged in prior theoretical analysis works. By combining this sorted-distance implementation detail with the observation that most graph ANN indices are built over the Euclidean metric, rather than an arbitrary one, the work improves the distance approximation factor that such a graph index is guaranteed to satisfy. The work then analyzes beam search rather than greedy top-1 search and shows an analogous result.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the kind words and suggestions.  As the reviewer noted, extending the existing analysis to the practically motivated beam search regime was a key motivation for this work. Additionally, we adopted a distance-based approximation scheme, leveraging our novel factor-revealing SDP to establish improved approximation guarantees for the Euclidean metric. While we agree that a probabilistic analysis of graph-based data structures would be valuable, it is important to note that DiskANN is deterministic and always returns the same set of nearest neighbors for a given query. Therefore, conducting a probabilistic analysis of exact top-1 nearest neighbor retrieval would require a new theoretical framework with a well-motivated assumption on the query distribution—an interesting yet challenging direction for future research.", "claims_and_evidence": "The claims are well-supported.", "methods_and_evaluation_criteria": "The experiments make sense.", "theoretical_claims": "The proofs for the two main results both appear correct to me.", "experimental_designs_or_analyses": "The experiments make sense.", "relation_to_broader_scientific_literature": "This work improves the theoretical analysis of graph-based ANN algorithms. It is very much related to the Indyk & Xu paper it references extensively, and also focuses on a variant of the DiskANN indexing procedure.", "essential_references_not_discussed": "The essential references, to the best of my knowledge, are discussed.", "other_strengths_and_weaknesses": "This paper is very well written and easy to follow, and its extension of upper bound analysis to beam search is significant, because beam search is always used in practice in graph ANN algorithms. One weakness is that the work gives a distance approximation bound, which is difficult for typical ANN users to interpret. A probabilistic analysis of finding the exact top-1 neighbor would be more relevant, although difficult. The degree and step bounds are also quite weak still and often lead to trivial (brute-force level) upper bounds.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper provides an innovation for, a theoretical understanding of and an approximation worst-case guarantee for a widely used approximate nearest neighbor search known as DiskANN. The proposed additional sorting step is shown to improve performance and for which worst-case performance is provided.  Empirical results support both the advantages of the sorting step as well as its performance particularly on one dataset.
Decision: Accept (poster)