Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
Authors: Yousef Al-Jazzazi
Haya Diwan
Jinrui Gou
Cameron N Musco
Christopher Musco
Torsten Suel
Venue: NeurIPS 2025 poster ()
Keywords: nearest neighbor search
navigable graphs
beam search
graph-based search
hsnw
diskann
Primary area: infrastructure
TL;DR: We propose a one-line modification of the ubiquitous beam search method for graph-based near neighbor search. Our new method yields strong theoretical approximation guarantees and better practical performance.

Abstract: Nearest neighbor search is central in machine learning, information retrieval, and databases. For high-dimensional datasets, graph-based methods such as HNSW, DiskANN, and NSG have become popular thanks to their empirical accuracy and efficiency. These methods construct a directed graph over the dataset and perform beam search on the graph to find nodes close to a given query. While significant work has focused on practical refinements and theoretical understanding of graph-based methods, many questions remain. We propose a new distance-based termination condition for beam search to replace the commonly used condition based on beam width. We prove that, as long as the search graph is navigable, our resulting Adaptive Beam Search method is guaranteed to approximately solve the nearest-neighbor problem, establishing a connection between navigability and the performance of graph-based search. We also provide extensive experiments on our new termination condition for both navigable graphs and approximately navigable graphs used in practice, such as HNSW and Vamana graphs. We find that Adaptive Beam Search outperforms standard beam search over a range of recall values, data sets, graph constructions, and target number of nearest neighbors. It thus provides a simple and practical way to improve the performance of popular methods.

Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
Yousef Al-Jazzazi New York University
Haya Diwan New York University md23710nyu.co edu
Jinrui Gou New York University jg62260nyu. edu
Abu Dhabi ya2225@nyu.edu
Cameron Musco
Christopher Musco New York University cmusco@nyu.co edu
Torsten Suel New York University torsten. torsten. sww.ennu.uullnuu.e.e
UMass Amherst cmusco@cs. umass edu
Abstract
Nearest neighbor search is central in machine learning, information retrieval, and databases. For high-dimensional datasets, graph-based methods such as HNSW, DiskANN, and NSG have become popular thanks to their empirical accuracy and efficiency. These methods construct a directed graph over the dataset and perform beam search on the graph find nodes close given query. While significant work has focused on practical refinements and theoretical understanding of graph-bact based methods, many questions remain. We propose a new distance-bar based termination condition for beam search to replace the commonly used condition based on beam width. We prove that, long the search graph navigable, our resulting Adaptive Beam Search method is guaranteed to approximately solve the nearest-neighbor problem, establishing connection between navigability and the performance of graph-based search. We also provide extensive experiments on our new termination condition for both navigable graphs and approximately navigable graphs used in practice, such HNSW and Vamana graphs. We find that Adaptive Beam Search outperforms standard beam search over a range of recall values, data sets, graph constructions, and target number of nearest neighbors. It thus provides a simple and practical way to improve the performance of popular methods.
Introduction
figh-dimensiooal nearest neighbor search is basic building block in many areas, including image and video processing [18 (6),, information retrieval [6] [1], and algorithm design [10] [28] It central to modern machine learning, underlying document and media search based on learned embeddings 99 40 48), as well retrieval-augmented generation (RAG) systems for large language
models [37 46 Nearest neighbor search also plays a role hard-negative mining (62) accelerating
transformer architectures
29 and other applications across machine learning [58]
Formally, in the k-nearest neighbor search problem, are given of data points, often machine- learned vector embeddings of documents, images, or other media [12 14]. We are also given a distance measure, such the Euclidean distance, or something more exotic like Chamfer distance
25 The goal is to pre-po pre-process the dataset into a search data structure so that, given any query point g. we can efficiently find the data points closest to g with respect to the distance measure.
Solving this problem exactly notoriously difficult in high dimensions, so applications typically rely approximate nearest neighbor (ANN) methods that attempt to find most of the & closest neighbors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Popular ANN methods include locality sensitive hashing (LSH) 2 3 23 41
inverted file indices 34 In this work. we focus on
based on quantization or clustering 26 27 49]. and more 8 graph-based ANN methods, which have been extensively studied and perform extremely well in practice, topping leader boards at several recent ANN competitions [55 56
30
Graph-Based Nearest Neighbor Search. The high-level idea of graph-based methods is simple. We construct index by building directed graph, G, with one node for each data point. Given query, 9, we search the index by starting at an arbitrary node and performing greedy graph traversal, exploring neighbors in that graph that are closest to q. A specific choice of graph construction and traversal method comprises a particular "graph-based nearest neighbor search method.
Many algorithms for graph construction have been proposed, including the Hierarchical Navigable [B3 [5], Navigating Spreading-out Graphs (NSG) [T],, and others [4 60] All of these methods construct graph G that, for a given node i, contains out-edges to nearest neighbors of i, as well as "long range" connections to nodes far away from i. Such constructions are loosely motivated by the concept of navigability, which dates back to pioneering work on local graph routing by Kleinberg [31 32 and Milgram [47]. We provide a formal definition of navigability in Section 2 but the property roughly guarantees that there is path from any node in G' to any node j so that the distance to j strictly decreases along the path.
Small World (HNSW) approach [43] Vamana/DiskANN
While graph constructions vary greatly, the choice of greedy traversal method used in graph based nearest neighbor search has seen less innovation. A variant of greedy search called beam search is almost ubiquitous. Parameterized by beam width b 2 k, beam search maintains list of b candidate nearest neighbors and computes the query's ' distance to each of those candidates' neighbors, updating them until it fails find any better candidates. See Section 3 for a formal description.
Our Contributions. While graph-based ANN methods have seen significant practical success, their performance is poorly understood from theoretical perspective. This is in contrast to methods like locality sensitive hashing, for which is possible to prove strong worst-case approximation guarantees [2) 4 A lack of theory makes it difficult to iterate on and improve existing graph- based methods, and to understand the limitations of these methods. We aim to address this gap, and in turn, introduce principled improvements to existing methods.
In particular, we re-examine the ubiquitous beam search method, viewing it, as in some previous work [17]. as specific stopping rule for much more general search procedure. This perspective motivates a new algorithm called Adaptive Beam Search, which stops searching for candidates based on a distance-based criterion instead of a fixed beam width, b. Our main theoretical result (Theorem [ is to prove that Adaptive Beam Search returns provable approximate nearest neighbors whenever the search graph G is navigable. To the best of our knowledge, this result is the first to theoretically connect the performance of greedy search (specifically, beam search) to the property of navigability.
Moreover, our theoretical results translate into practical performance. We perform an extensive experimental evaluation of Adaptive Beam Search, comparing it to fixed-width beam search over a wide range of data sets, graph constructions, recall values, and target number of nearest neighbors. The method universally outperforms classic beam search, typically providing a 10 50% reduction in the number of distance computations required for a given level of recall. Moreover, Adaptive Beam Search can be implemented with only minor code changes to existing graph- libraries. We thus hope that, beyond its theoretical relevance, the method will have practical impact.
Roadmap. The remainder of this paper is organized as follows. In Section 2 we discuss technical preliminaries and related work. In Section 3 we introduce our Adaptive Beam Search method and its motivating ideas. In Section 4 we prove that Adaptive Beam Search solves approximate nearest neighbor search on navigable graphs (Theorem []. In Section we evaluate Adaptive Beam Search on sparse navigable graphs and common heuristic graph constructions, including HNSW and Vamana.
Background and Related Work
We start by defining notation used throughout. Our goal in this paper is to find nearest neighbors in We are given database
a metric space X equipped with a distance function d' X x X' + +
In particular. we just require that for all i, & E X. d(i. = d(j. i). d(i > 0 when i * j. d(i i) = 0. and d(i.j) + d(j k) 2 d(i, k) (i.e., triangle inequality holds).

---

of n items in X, which we label f1..... nn. We want to find the nearest k I n items to given query q E X. E.g., for k = 1, the goal is find g (1,..... d(g. To avoid corner cases, we assume items in the database are unique, i.e. d(i,j) > for all j E ".....,njji.
In practice, the n database items and the query are usually associated with vectors (e.g., machine learned embeddings) X1,..., X5 and X2 E IR". The distance function d(i, is chosen be some function of these vectors, e.g., the Euclidean distance, d(2. = | x,112-
Graph Navigability. Our theoretical guarantees assume use of navigable search graph over n nodes corresponding to our n database items. While the term "navigable" is sometimes used informally in the literature, we use the following precise definition. Consider directed graph G (V. with V = [I,...,,] For a node z, let (z denote its set of out neigheegs Define:
Definition 1 (Navigable Graph), A directed graph G is navigable under distance function d if any nodes x. y E (1,...,n) n) with dx,, y) > 0, there is some E NN(xx) with d(2, y) < d(x y)-
Navigability ensures that, for any starting node 8 and target node t, standard greedy search where we always move to the neighbor of the current node closest to t, always converges to t.
When all distances between {L...., n are unique (this can be ensured by simply tie- brebiin based on node id) it was recently shown that any data set has an efficiently computable navigable graph with average degree ((vr) for any distance metric [33 While the above bound is nearly optimal for worst-case data sets, much sparser navigable graphs often exist. For the Euclidean distance in
m dimensions, Arya and Mount construct navigable graphs with degree 20(m) (5). For general metrics, Indyk and Xu construct navigable graphs with degree 20(m²)) log A where mn' the doubling dimension of the data under d and A = max.,j d(i.j) //mins.. j)
is the dynamic range [24].
Why do we focus on navigability? Navigabilityy has become a standard notion of "quality" for graphs used in nearest neighbor search. Indeed. the term lends its name to popular graph-baser search methods such as the Navigable Small World (NSW) 422 and Hierarchical Navigable Small World (HNSW) 43 methods. Neither of these methods constructs graphs that are provably navigable, al- though they produce graphs that should be approximately navigable in practical settings. Surprisingly, however, to the best of our knowledge, search to this intuitive notion of graph quality. As discussed, a major goal here is to address this theory-practice gap, and to use the resulting theory to propose new practical algorithms.
prior work formally links the accuracy of graph-based
Related to our approach is a recent paper by Indyk and Xu [24 (and more recent follow-up work (20)) which proves accuracy guarantees for standard beam search under the assumption that the search graph is "a-shortcut reachable", strictly stronger criterion than navigability. graph is a-shortcut reachable if, for all x, y E (1,..., n) with d(x,, v) > O. there is some NN(xx) with a d(z,y) y) < d(x;, y) for some parameter a 2 1. Indeed, navigability exactly corresponds to this definition with a = 1. However, the results from (24 20 only yield bounded approximation factor for a >> 1 (concretely, (24] obtains approximation factor L+a) ) Thus, obtaining theoretical results for graphs that are simply navigable remains an open question.
One reason this question is of practical importance is that navigable graphs can in general be much sparser than a-shorteut reachable graphs. While it is possible construct navigable graph with average degree O( /n) for any database under any metric (under the mild assumption of unique distances) [1T). it is not hard to observe that for any fixed Olog -imeensioa Euclidean space does not admit an a-shortcut reachable graph with average degree < n 1 with high probability (see Appendix A. for details). This is also the case for other stronger versions of navigability studied in recent work, like "r-monotonicity" [52
1, even a random point set in
2.1 Additional Related Work
few other papers have studied graph-based ANN search from theoretical perspective. E.g.. [35] and [54] study spaee tradeoffs akin to those available for LSH methods, but only for random data. More significant work has focused on practical algorithmic improvements. E.g., work has studied parallel implementations [45), methods for dynamic datasets [57 63), distance
Beyond 24
20
approximations (64), graph pruning (65). filtered search [19] search with coverage criteria (1. and better search initialization strategies
[66]. There has been relatively little work on alternatives to beam
width-based termination in beam search, although a few papers study "carly stopping" criteria that
3

---

incorporate distance information like our Adaptive Beam Search 44 21] There has also been some work on using machine learning to predict an optimal termination point [3]. In concurrent work, [6]] propose another algorithm called Adaptive Beam Search, but the approach is fundamentally different than ours: they adapt the edges considered during the search process based on the query q. They give theoretical bounds assuming G is 7-monotonic, a stronger variant of navigability [52] 22
3 Adaptive Beam Search
Beam search is the de facto search method used for graph-based ANN observation: beam search can be reframed by decoupling the method into key components 1) a search order, determined by a method for traversing the search graph to find candidate nearest neighbors and 2) stopping criterion, which governs when the algorithm stops considering candidates.
13 59
We start with key
Our Adaptive Beam Search method modifies the standard beam search algorithm only by changing the stopping criterion. The search order remains the same. Surprisingly, even this simple change leads to an algorithm that both enjoys strong theoretical approximation guarantees when the underlying graph is navigable (see Theorem D and outperforms standard beam search empirically.
The "decoupled view" of beam search is not entirely new. However, for completeness, we detail this reframing in the next section, and show how change in stopping criterion yields other search algorithms, like simple greedy search and Adaptive Beam Search. We intuitively motivate the stopping criterion used in Adaptive Beam Search before formally analyzing the method in Section
3.1 Decoupling Beam Search as Ordered Traversal With Stopping Condition
To be concrete, we provide pseudocode for a generic version of beam search in Algorithm I Implementation details are deferred to Appendix B.I Importantly, such details do not affect the number of distance computations performed by the algorithm i.e., how many times we evaluate d(g. i) for query point, q. and candidate nearest neighbor, i. Distance computations typically dominate the cost of search practice and, indeed, for the stopping criteria considered this paper, all other operations can be implemented in time nearly-lineal in the number of such computations.
Algorithm 1 Generalized Beam Search
Input: Search graph G over nodes (1...., n), starting node 8, distance function d, query g. target number of nearest neighbors k.
Output: Set of k nodes B C {l....,,k) n). where each æ E B is ideally close to with respect to d. Initialize min-priority queues C and D. > Elements nodes, priorities are distances q. 'D contains all discovered nodes, C contains discovered nodes that are not yet expanded.
1:
2: Insert (s, d(g, s)) into C and D.
3: while C is not empty do
4: (xr, d(q, .)) <- extractMin(C))
b Pop min. distance node.
5: if satisfies [termination condition] then
6: break
7: For all y E (a))),, if y not in D, insert (y, d(g. u)) into C and D > Expand node
8: Obtain B by running extractMin & times on D, which returns the k elements with the smallest distances from the query,
Algorithm I maintains queue of "discovered nodes" 'D whose distances have been computed, It repeatedly "expands" the nearest discovered (and not previously expanded) node to q by adding its neighbors to the queue (Line 6). It does so until this nearest node triggers the termination condition in Line The choice of termination condition leads to various versions of greedy search, including beam search and our new distance-based Adaptive Beam Search method. In particular, we have:
Classic Greedy Search. Terminate there are at least:
k items j1. .1.....jJ . E with d(g.j.) - d(g.
(1)
Note that if DD is simple priority queue, checking if E D may be inefficient. This can be resolved by storing dictionary of elements in D. as done in our more detailed pseudocode in Appendix B.I
B.I

---

Beam Search, with bidth parameter b 2 k. Terminate if there are at leas leas
b items , E D with d(q.jk) S d(g,x).
(2)
Adaptive Beam Search (our method) w/ parameter 7y. Terminate if there are at least:
k items ji.....Jk Jk E D with (1 + +)) d(g. S d(q.x))
(3)
The rule for greedy search is simple: we terminate if we have already found k points closer to than the current candidate considered for expansion. For 1, it takes a moment confirm that this criterion yields a method that is exactly equivalent to the more typical way of presenting greedy search: starting s, move to the neighboring node nearest to q. terminating if there is no neighbor closer than the current node. For l = 1, greedy search is known to converge to the exact nearest neighbor if there some x E {l,.. (L..... n2} for which d(zz, q) = 0 and the search graph G is navigable [T3 31 47). However, no comparable guarantees hold for & > or when q 's nearest neighbor is not distance 0, which is typical in practice. Moreover, greedy search performs poorly empirically, easily getting stuck in local minima and failing to find good approximate nearest neighbors.
3.2 Relaxing Greedy Search
The goal of beam search is to avoid such accuracy issues. It does so by relaxing the stopping criterion from greedy search: in particular, by (2), we only terminate if we have found b 2 lc nodes closer to the query g than our current node z. When b = k, the algorithms are identical. When > k. greedy search explores prefix of the nodes explored by beam search, which simply terminates the search at a later point. Beam search is thus guaranteed to obtain a more accurate result than greedy search, at the cost of an increased number of distance computations.
With the above view in mind, many other relaxations of the greedy search termination condition given in (I) become apparent. In (3). we introduce a slack parameter y > 0 and only terminate if is further from & than the h best discovered point by factor of + Setting 7 = recovers greedy search, and larger values of y will cause the search process terminate later, yielding better result, but at the cost higher runtime. This simple idea yields our Adaptive Beam Search procedure.
While intuitively similar to beam search, a key difference of this distance-based termination rule is that it naturally adapts to the query difficulty. For simplicity, consider the case of = 1. Greedy search tends to perform worse when there are many "false nearest neighbors". For example, suppose there is just one nearest neighbor x² with d(q, x²) 1, but many other points ..,..., Jm with d(g, .4) = 1.01. Assume that .i...., Zm, and x² are all connected with navigable graph. If the graph is sparse, only a small subset the nodes in (xI,..., Im will be connected to xt. Thus, we initialize greedy search from point in (II...., Tm unless we chose a very large beam width b, is likely that before reaching one of the nodes connected to x² (and thus finding x²), more than b points at distance 1.01 will get added to D. causing the search to terminate. In contrast, long as y > ,01, Adaptive Beam Search will continue to search through all of the He points, ultimately finding x= before terminating. At the same time, Adaptive Beam Search will more quickly terminate on easy queries if it becomes apparent that all remaining candidates are too far away to be useful in finding additional nearest neighbors. Indeed, a criterion identical to Adaptive Beam Search has been suggested as an "early stopping" heuristic in work on practical graph- ANN methods [4]
The intuition that Adaptive Beam Search adapts to query hardness shows clearly in our experiments: as seen in Figure [] the distribution of distance computations used by Adaptive Beam Search varies more widely, as fewer computations are used for "easier" queries. As result, across a variety of data sets and search graphs, Adaptive Beam Search consistently outperforms classic beam search in terms of total distance computations required to achieve a certain level of recall for given query set.
3 Remark on implementation: For beam search, it easy to see that a node will always satisfy termination condition (2) if is not one of the closest neighbors to in D. So, instead of maintaining two priority queues, it is more computationally efficient to maintain sorted list of the b closest nodes discovered so far. This is what is done typical implementations of beam search (59] and in our more detailed pseudocode in Appendix B.I
5

---

MSG Gregh: 069P236, Recal 0.55
HASW: Gmyhh DESFA Recall 93
Naviystle Goahh SFT Recall
300
Adaptive Soarch meathed
Aceplow bean Search mndivel)
1200
Alaiiie beam Search lou medrtdd
100
100 V0la
Ser Detar Carolotors
500
100
Soarth Sistence Cale dedees
500
1190 1963
Figure 1: Histograms for the number of distance computations performed by standard beam search and our Adaptive Beam Search method when answering 10,000 queries for various datasets and search graphs (see Section for details). For fair comparison, the parameter in beam search and parameter in Adaptive Beam Search were tuned to achieve a fixed level of recall for the batch of queries. The histograms for Adaptive Beam Search are consistently flatter, confirming the intuition that it better adapts to query difficulty, leading to fewer distance computations on average.
4 Theoretical Analysis
We support the improved empirical performance of Adaptive Beam Search with strong theoretical guarantees. Formally, we prove that the method is guaranteed to solve the approximate nearest neighbor search problem, assuming that the search graph G is navigable (Definition]) Tp:
Theorem 1. Suppose d a metric on X and G navigable under d. Then for any query q E X. if Adaptive Beam Search - i.e. Algorithm D with stopping criterion 3
is run with parameter
< 7 S 2, guaranteed to return set of points B such that:
for all E nn. \
d(g, v)
7 max d(g..)).
2 JEB
Notably, setting = 2. we ensure that all points not returned by the algorithm are at least as far from q as every point in B. Thus, for 2, Adaptive Beam Search on a navigable graph is guaranteed to exactly solve the k-nearest neighbor problem. For smaller 7, the method obtains an approximate solution: no point in B can be further from q than any point not returned by more than a 2/7 factor
We can see that Theorem 1 proves a trade-off between runtime and accuracy: smaller values of ? lead to strictly faster algorithm (since termination earlier) but a worse approximation guarantee. While our result falls short of proving worst-case runtime guarantees, to the best of our knowledge, is the first result linking the accuracy of a natural greedy search method to the notion of graph navigability. Importantly, we note that, unlike our Adaptive Beam Search, a result like Theorem cannot be proven for standard beam search. In particular, in Appendix A.2 we prove:
Claim 2. Standard beam search with beam width b S n 3 fails to approximately solve the nearest neighbor search problem on navigable graphs for any finite approximation factor.
Concretely, for any finite C, we can construct set of n points in 2-dimensional Euclidean space and navigable graph G such that, for some query point g, beam search run on G with beam width b < n returns ă with d(q. it) 2 C- min d(g,ar). .E(I.....)
Proof of Theorem 7 Our proof will use the terms "discovered" and "expanded"' to identify nodes in {1. nZ.. We consider node j "discovered" if j E D when Algorithm terminates; i.e., we have evaluated the distance between j and q. We consider a node j "expanded" if j is discovered and, at some point, was both popped off C on Line 4 and did not cause the termination condition on Line 5 to be triggered. This ensures that all of its out-neighbors are discovered (see Line 7).
Note that all discovered nodes are added to both 'D and C. Formally, if the algorithm terminates because the condition is true for some Tterm then U {Tterm) is the set of discovered but not yet expanded nodes, so the set of expanded nodes is D \ (C U {Iterm)).
'Many existing theoretical guarantees for approximate nearest neighbor search, such as those for LSH and related methods 2 4 23 focus on the case of A 1. A rephrasing of our result in this case is that Adaptive Beam Search returns approximate nearest neighbor ă with d(g, Z) min.g().....) d(g, x).

---

Let B be the set of nodes returned upon termination and let Ā argmax,e8 d(g,æ) x)) ) be the kth furthest point from q in that set. Since is navigable, and since we assume data points are unique, there must be a path in G' from any node to any other node y (consisting of nodes that get monotonically closer to y); i.e., G is strongly connected. Thus, if Algorithm [ terminaaess because an empty queue causes the while loop to terminate, then all nodes in the graph must have been discovered, and so B contains the exact k nearest neighbors to g, and the theorem holds immediately.
Thus, it suffices to consider the case when termination occurs because some node Xterm causes the termination condition in Line 5 to evaluate to true and the while loop to break early. We first claim:
Claim 3. When Algorithm terminates, E is guaranteed to have been expanded.
To see that this claim holds note that, by termination condition 33, it must be that d(q,, Iterm) ) 2 (1+7)d((,, Z) and thus d(q, Tterm) > d(g. σ) I.e., 7 is closer to q then Eterm- Thus, I must have already been popped off C and expanded before Tterm was popped off C.
With Claim 3 in place, we can get into our main proof. Our goal is to prove that for all & $ B,
d(g, 2)
7
dl(g, T). 2
suffices to prove the claim for all undiscovered nodes 2 & 'D, since if : E D and d(g, =) < 3 3d(g, then is closer to q than ö and would have clearly been included in B (recall that y I 2).
Now, suppose by way of contradiction that 4 is not true, i.e., that there is some undiscovered node & D with d(g, z) < 3d(q, .). We first observe that such z cannot be an out neighbor of z: since T is expanded by Claim 3 all its neighbors are discovered, i.e., all are in D.
Since G' is navigable and all database items are unique, there must be some directed path P from ă to 2 consisting of points that get monotonically closer z. Moreover, since & Na P must have length E 2 2. Denote the elements of P by P = { Po + P1 + + 2}. We have for all 1 S i S e, d(z.Pi-1) > d(). We make the following claim:
Claim 4. For any z & D, there exists some node E {(PI....,Pt. along the path from T to z that has been discovered but not expanded.
Proof. First observe that P1 must be discovered since, by Claim f was expanded and p1 is an out-neighbor of ă. Furthermore, if p--1 is discovered and expanded then p: must be discovered. So, inductively we see that there are two possible cases: either there is some i < É for which p: is discovered but not expanded (as desired) or is discovered and expanded for all i < f. However, the second case is impossible since is not in D and it would be if pe-1 I was expanded. We conclude the claim that there is some w E (PI,...,PE-- that is discovered but not expanded.
Consider the unexpanded node w guaranteed to exist by Claim When the algorithm terminates,
d(g, w) 2 (1 7))
If w Tterm this is trivially true consequence of the termination rule 3 Otherwise, if S were not true, then w would be closer to q than Fterm and it would have been popped off C before Sterm and expanded. With (5) in place, we ready to obtain our contradiction. By triangle inequality (since d is a metric) and our supposition that d(g. 2) < " d(q, ă), we have:
d(ž, S d(ž,g) + d(g,2) 2) (1+ ?) d(g. Z).
Combined with another application of triangle inequality and the fact the d(w, 2) d(ā, 2), we have
7 d(g, T) = (1 +1++000 7)) 7). d(w, 4) S d(w, z) + d(=, q) < d(ž, 2) + d(2, 4) < (1 2)) d(g, σ) + 2
2
However, this claim contradicts 5).
Thus, there cannot exist any & D with d(g, 2) < 3d .). L.e. holds, proving Theorem For a geometric illustration of the above proof, see Figure 2
'The strict inequality clearly holds when d(q, .2) > 0 since > O. When d(g, ē) = 0 it holds because database items are assumed to be unique, so we cannot also have d(g, 2term) = 0.
7

---

Figure 2: Visualization of the proof of Theorem We let d denote d(g, Ø). Our goal is to show that there no undiscovered in a ball of radius d around which is shown with dotted line. If there was, we obtain a contradiction. In particular, if G is navigable, we argue that there must be some unexpanded node w on a path of decreasing distance from 전 to 2. Since w is closer to 2 than ă, must lie in a ball of radius (1 + 3) d around 2, which is contained in a ball of radius (1 + ?) around q. However, by (5). no unexpanded node can lie in that ball.
d
W
(1+7)d
5 Experiments
We now experimentally compare our Adaptive Beam Search method with standard beam search, demonstrating improved tradeoffs between efficiency and accuracy in variety of settings.
Beam Search A Algorithms. We primarily compare standard beam search (termination condition (2) with Adaptive Beam Search (termination condition (3). To implement Algorithm | with these termination conditions, we follow the pseudocode Appendix B.T] For some settings, we test a third
method called Adaptive Beam Search V2, which terminates on node if
d(g.x) 2 d1 + de.
where d and dg are the distances from the query q to the closest and 1ath closest discovered nodes, respectively. Compared to 3 (6 replaces the threshold (1 + 7) dg with the smaller threshold d1 + dg. leading to more aggressive stopping. Surprisingly, while (6) is not relaxation of greedy search (when 7 < 1, it may stop earlier than greedy search), one can check that Theorem I still holds under this condition. This motivates its inclusion in our experiments. However, we observe that Adaptive Beam Search V2 generally underperforms Adaptive Beam Search. We leave open developing other stopping conditions that satisfy bounds similar to Theorem [ while obtaining strong empirical performance like Adaptive Beam Search
Appendix C.4 for some initial explorations.
Comparison Across Recall Values. The algorithms discussed above can all trade off accuracy for runtime by adjusting the beam width, b, or the parameter y. We thus vary these parameters to obtain a range of recall values, i.e., the average fraction of the l nearest neighbors found over all queries on given dataset. Recall is standard metric for evaluating ANN methods [43 59]. We compare the methods by plotting the average number distance computations performed per query to achieve a certain recall value. Since all three methods have essentially identical implementations, running time scales very similarly with the number of distance computations. See Appendix [B. for more details.
Datasets and Graph Constructions. We evaluate our Adaptive Beam Search on six standard benchmark datasets for nearest neighbor search, which are listed in Table All datasets consist of real-valued vectors in varying dimensions, and we use Euclidean distance for search. We perform evaluations using variety of popular heuristic "approximately navigable" graphs, along with truly navigable graphs for which the bound of Theorem holds. Specifically, for the heuristic graphs, we use four standard methods: HNSW (43), Vamana [59], NSG [16], and EFANNA [1]. Details on how parameters are set for these algorithms are in Appendix B.3
5.1 Experimental Setup
To construct the truly navigable graphs, we use the approach of [33 to create an initial navigable graph with average degree Ö(vn), and then further prune this graph while maintaining navigability. See Appendix B.2 for details. Pruning reduces the memory fooiprint of the graph, and results in levels of sparsity closer to those of the heuristic constructions. However, since it is computationally expensive, only run our navigable graph experiments for random subsets of three of the datasets,
8

---

# of Nodes in Navigable Graph Experiments
Dataset
Dimensions
# of Nodes
# Query Points
MNIST 36
784
60K
50K
10K
SIFTIM 26
128
IM
100K
10K
DEEP96 7
96
IM
100K
10K
DEEP256 39
256
IM
10K
GloVe [53
200
1M
10K
GIST 50
960
1M
10K
Table 1: Datasets used for evaluation. For further details, refer to Appendix B.3
with subsample sizes listed in T We believe that our subsample sizes are large enough to be representative. However, it would be interesting to improve the running time of constructing very sparse and truly navigable graphs, that such graphs can be evaluated for larger datasets.
5.2 Results
We now discuss our experimental results on both truly navigable graphs and the commonly used heuristic graphs discussed above.
Results for Navigable Graphs. Results for navigable graphs are shown in Figure 3 for SIFT. DEEP256, and MNIST for = and 10. Results for k 100 are included in Appendix C The y-axis shows recall, while the x-axis shows the average number of distance calculations per query. Adaptive Beam Search always performs at least on par with classic beam search, and often significantly better, with up to 30-40% decrease in distance computations for a given recall. Adaptive Beam Search V2 performs worse, so is not evaluated in future experiments. The underperformance of Adaptive Beam Search V2 is further explored in Appendix C.3 In nutshell, when di < dz. for small y we might stop when d(g. x) < dg. which means we do not even explore all the neighbors of current top-k results. If we increase y to avoid this, we terminate too late when dj is close to dg-
Nevigable Graph: SET k=
1.00
New! gabie, Groph: DEES6. k=
3.00
havigable. Graph: MNIST ks1
Adoptive Search medhodi
mehood
Adaptive
0.34
0.44
0:44
0.79
0:39
0.93
0.37
0:37
0.07
0.34
0.4
6.96
0.33
21
20
2
0:33
20
20
20z
0:33
0
28
201 Dssance Calculations
Search Calculations
Distnce Carculations
1.03
Novigable, Graph: SFT, ko-0
1.00
Navigable, Graph: DEEP96, k=10
3.00
Novigable, Graph: MNIST, k-10
Stancard Bears Search
Standard Zeam Search
Stancird Beam Search
Adaptive Boam Search, V2
Aduppive Beam Search yp
Adsptive Beam Searcs V2
Adoplive Boam Search (gi mathodi
Aduppive Beam Search fout michod)
Adaptive Bearn Search lout mithod)
0.70
035
0:95
0.2
0:33
0.03
of Search Disdancc Cakcolatiors
of Swarch Diolance Caltulations
Search D'adance Cattulationss
Figure 3: Navigable Graphs: Comparison of generalized bean search termination conditions on navigable graphs across three datasets: SIFTIM, DEEP96, and MNIST (columns), with l: 1, and k = 10 (rows). Adaptive Beam Search consistently outperforms standard beam search, while the alternative Adaptive Beam Search V2 underperforms both by significant margin. Note that for k = 1, Adaptive Beam Search and Adaptive Beam Search V2 are identical, so only one line is shown.
9

---

Results for Heuristic Graphs. Our results for heuristic graphs with k = 10 across three datasets are shown in Figure 4 For additional results covering the remaining datasets and values of k. see Appendix C.2 In all cases, we see that Adaptive Beam Search outperforms standard beam search, sometimes marginally, but sometimes by more than a factor of 2, e.g., on MNIST. The performance gains are robust to changing the graph construction, indicating that Adaptive Beam Search is a strong candidate for a drop-in replacement for standard beam search in graph-based ANN.
Adaptive Beam Search seems to outperform standard greedy search because the distance- based stopping criterion is more "adaptive" to query difficulty. For hard queries with many approximate nearest neighbors, it tends to use more distance computations. However, the method terminates quickly on easy queries when there are few points with d(g, r) S (1 + 7)2 This phenomenon is illustrated for a sample of settings in Figure
Adaptivity Across Queries. As discussed in Section 3.2,
1.80
NSG, Graph: SIFT, k-10
NSG Greph: DEEP256, L-10
45G Goaphy MUST k-10
3.0
Recall
1MT1
140
Standar Seam Search
Standard Deam Search
Standard Beam Search
Adapive Boarn Search four method)
Acaptive Beam Search method!
Adaptive Beam Search lour methes)
Search Distanca Caluratiirs
Search Distance Colculations
Search Datance Calouiatios
VAMANA, Graph: km10
VANANA, Graph: DEEP256, k=10
VAMANA, Grach: MNIST 1-10
Rocal
696
Sundor Beam Searc1
Standard Beom Search
onee
Standord Bear Search
Adkettow Beams Search [our method)
Acaprish feams Gearrh (our methodi
Adaphis feam Searth (ovr methar)
Search Distance Colcurations
Search Distance Calcurations
of Searci Distance Calculation
ETANNA, Graph: SET, k=30
CTANNO, Grash: DEEP256, k=10
ETANNA, Graph: MNST. k=
C19
ORO
onee
616
Stander Seam Search
Standard Deem Search
Standerd Deamn Search
Adaciive Beam Search four mathod)
Aceprive bean Search jour muthodl
Adaptive Beam Search lour mathest
of Search D Distanca Calcurations HNSW, Graph: SIFT, k--0
Search Disanne Calcuration
* Search Dalance Calculatios
HNSW, Graph: DEEP256, k-10
HNSW, Graph, MNIST
8501
Rooa
Standon Beam Searc1
Standard Bear Search Manthe Tewn Sworth (our methort
Mandard bears Search
Adkelte Bears Search [sur method)
faspii feam Seooth (ve methor)
of Sca th Distance Calorations
of Scorch Distance Calculations
4 Searoi Dizanco Caloulation"
Figure 4: Heuristic Graphs: Comparison of generalized beam search termination methods on heuristic graphs produced by NSG, Vamana, EFANNA, and HNSW (rows), for k = 10 with datasets: SIFTIM, DEEP256, and MNIST (columns). Adaptive beam search consistently outperforms standard beam search across all cases, sometimes by significant margin.
10

---

Acknowledgments
We would like thank Ramon Li for contributions at an early stage of this work. Christopher Musco was partially supported by NSF Award 2106888.
References
[1] Piyush Anand, Piotr Indyk, Ravishankar Krishnaswamy, Sepideh Mahabadi, Vikas C. Raykar, Kirankumar Shiragur, and Haike Xu. Graph-based algorithms for diverse similarity search. In Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025.
[2] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Communications of the ACM, 51(1):117-122, 2008
[3] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Iya Razenshteyn, and Ludwig Schmidt. Practical and optimal LSH for angular distance. In Advances in Neural Information Processing Systems 28 (NeurIPS), 2015.
[4] Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya Razenshteyn. Beyond locality hashing. In Proceedings of the 25th Annual ACM-SIAM Symposium Discrete Algorithmss (SODA), 2014.
[5] Sunil Arya and David M. Mount. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1993.
[6] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. ANN-Benchmarks: A bench- marking tool for approximate nearest neighbor algorithms. Information Systems, 87, 2020. Data accessed at htttts:://gttt htttt:/://gtthub....mmrrereeeee erikber//k ann-benchmarks
[7] Artem Babenko and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep descriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2055-2063, 2016. Data accessed at htttps://gttiiiie hwm.t..oooooooo..o...ooooooooott irikbern/ ann- benhharcc
[8] Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd International Conference on Machine Learning (ICML), 2006.
[9] Sebastian Bruch. Foundations of Vector Retrieval. Springer, 2024.
[10] Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis. Kernel density estimation through density constrained near neighbor search. In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020.
[11] Alex Conway, Laxman Dhulipala, Martin Farach-Colton Rob Johnson, Ben Landrum, Christo- pher Musco, Yarin Shechter, Torsten Suel, and Richard Wen. Efficiently constructing sparse navigable graphs. In Proceedingy of the 37th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), 2026.
[12] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4171 41861 2019.
[13] Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. Navigable graphs for high- nigh-dimensional nearest neighbor search: Constructions and limits. In Advances in Neural Information Processing Systems 37 (NeurIPS), 2024.
[14] Thibault Formal, Benjamin Piwowarski, and Stéphane Clinchant. SPLADE: sparse lexical and expansion model for first stage ranking. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2021.
[15] Cong Fu and Deng Cai. EFANNA: An extremely fast approximate nearest neighbor search algorithm based on kNN graph. arX1v:1609.002228 2016.

---

[16] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading out graph. Proceedings of the VLDB Endowment, 12(5):461-474, 2019. Data acccessed at: ttttps://githen wwt..//eeee...ernnnnnnn..a..
com
[17] Jianyang Gao and Cheng Long. High-dimg nigh-dimenssonal approximate nearest neighbor search: with reliable and efficient distance comparison operations. Proceedings of the ACM on Management of Data, 1(2), 2023.
[18] Vincent Garcia, Eric Debreuve, and Michel Barlaud. Fast k nearest neighbor search using GPU. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, 2008.
[19] Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Beg- wani. Swapnil Raz, Yiyong Lin, Yin Zhang, Neclam Mahapatro, Premkumar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. Filterd-DDssANDe Graph algorithms for approximate nearest neighbor search with filters. In Proceedings of the 32nd International World Wide Web Conference (WWW), pages
2023.
[20] Siddharth Gollapudi, Ravishankar Krishnaswamy, Kirankumar Shiragur, and Harsh Wardhan. Sort before you prune: Improved worst-case guarantees of the diskANN family of graphs. In Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025.
[21] Fabian Groh, Lukas Ruppert, Patrick Wieschollek, and Hendrik P. A. Lensch. GGNN; graph- based GPU nearest neighbor search. IEEE Transactions on Big Data, (1):2677277, 2023.
[22] Ben Harwood and Tom Drummond. FANNG: fast approximate nearest neighbour graphs. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[23] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the 30th Anmual ACM Symposium on Theory of Computing (STOC), 1998.
[24] Piotr Indyk and Haike Xu. Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations. In Advances in Neural Information Processing Systems 36 (NeurlPS), 2023.
[25] Rajesh Jayaram, Laxman Dhulipala, Majid Hadian, Jason Lee, and Vahab Mirrokni. MUVERA: Multi-vector retrieval via fixed dimensional encoding. In Advances in Neural Information Processing Systems 37 (NeurIPS), 2024.
[26] Herve Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117-128, 2011. Data accessed at htttt:://ooppus texmex. irisa.
[27] Jeff Johnson. Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(03)) 547, 2021.
[28] Matti Karppa, Martin Aumüller, and Rasmus Pagh. DEANN: Speeding up kernel-density estimation using approximate nearest neighbor search. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
[29] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
[30] Jon M. Kleinberg. Two algorithms for nearest-neighhor search in high dimensions. In Proceed- ings of the 29th Anmual ACM Symposium on Theory of Computing (STOC), 1997.
[31] Jon M. Kleinberg. Navigation in a small world. Nature, 406(6798):845 845, 2000.
[32] Jon M. Kleinberg. The small-world phenomenon: an algorithmic perspective. In Proceedings of the 32nd Annual ACM Symposium Theory of Computing (STOC), 2000.
[33] Ravishankar Krishnaswamy, Magdalen Dobson Manohar, and Harsha Vardhan Simhadri. The DiskANN library: Graph-based indices for fast, fresh and filtered vector search. IEEE Data Engineering Bulletin, 48(3):20-42 2024.
12

---

[34] Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), 1998.
[35] Thijs Laarhoven. Graph- based time-space trade-offs for approximate near neighbors. In Proceedings of the 34th Annual Symposium on Computational Geometry (SOCG), 2018.
[36] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-basse learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 22244, 1998. Data accessed at htttt::ttggiaeee ttt.b//.tttuu.... www/erikwern////eccct.cttcc http:///ttt...mmmmer///btt////a/ ann-bnnchabaasse
[37] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmented generation for knowledge-intensive NLP tasks. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[38] Conglong Li, Minjia Zhang, David G Andersen, and Yuxiong He. Improving approximate nearest neighbor search through learned adaptive early termination. Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, 2020.
[39] Jinfeng Li, Xiao Yan, Jian Zhang, An Xu, James Cheng, Jie Liu, Kelvin K. W. Ng, and Ti-chung Cheng. A general and efficient querying method for learning to hash. In Proceedings of the 2018 ACM SIGMOD International Conference on Management of Data, pages 1333-1347, 2018. Data accessed at htttts://wwat cse. cuhk, edu, hk/ syystemshhaase htapa//gg/ddaaaaae http:/daaasetss..o html html
[40] Chen Luo, Vihan Lakshman, Anshumali Shrivastava, Tianyu Cao, Sreyashi Nag, Rahul Goutam, Hanqing Lu, Yiwei Song, and Bing Yin. ROSE: Robust caches for amazon product search.
for-amazon www.amm-roououttttaaeessess sroduct-search, 2022.
[41] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe LSH: efficient indexing for nigh-dimensional similarity search. In Proceedings of the 33rd International Conference on Very Large Data Bases, pages 950-961, 2007.
[42] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45:61-65 2014.
[43] Yury. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42( 836, 2020.
[44] Magdalen Dobson Manohar, Taekseung Kim, and Guy E. Blelloch. Range retrieval with graph-based indices. (axXiv:2502.13245) 2025.
[45] Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Har- sha Vardhan Simhadri, and Yihan Sun. ParlayANN: Scalable and deterministic parallel graph- based approximate nearest neighbor search algorithms. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 270-285, 2024.
[46] Grégoire Mialon, Roberto Dessi, Maria Lomeli, Christoforos Nalmpantis, Ramakanth Pasunuru, Roberta Raileanu, Baptiste Roziere, Timo Schick, Jane Dwivedi- Yu, Asli Celikyilmaz, Edouard Grave, Yann LeCun, and Thomas Scialom. Augmented language models: a survey, Transactions on Machine Learning Research, 2023. Survey Certification.
[47] Stanley Milgram. The small world problem. Psychology Today, 2(1):60-67, 67, 1967.
[48] Bhaskar Mitra, Nick Craswell, al. An introduction to neural information retrieval. Foundations and Trends in Information Retrieval, 13(1):1-126, 2018.
[49] Marius Muja and David G. Lowe. Scalable nearest neighbor algorithms for high dimensional data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36( (6(11))2227-2222 2014.
13

---

[50] Aude Oliva and Antonio Torralba. Modeling the shape of the scene: A holistic representation of the spatial envelope. International Journal of Computer Vision, 42:145-175, 2001. Data accessed at
com/ er kbern/ aaaer////aambbbnccaararr
[51] Apostolos N. Papadopoulos and Yannis Manolopoulos. Nearest Neighbor Search:: Database Perspective. Springer Science & Business Media, 2005.
[52] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. Efficient approximate nearest neighbor search in multi muntiidimennsonal databases. Proceeding of the ACM on Management of Data, ((1), 2023.
[53] Jeffrey Pennington, Richard Socher, and Christopher D. Manning. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2014. Data accessed at https: / http:/gitttt thubb....... com/ er eeeeeriii ikbern//
ann chmarks
[54] Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based nearest neighhor search: From practice to theory. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
[55] Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingher, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, Mazin Karjikar, Laxman Dhulipala, Meng Chen, Yue Chen, Rui Ma, Kai Zhang, Yuzheng Cai, Jiayang Shi, Yizhuo Chen, Weiguo Zheng, Zihao Wan, Jie Yin, and Ben Huang. Results of the Big ANN: NeurlPS'23 competition. 2XXi:24499.14224 2024.
[56] Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamny, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang. Results of the NeurlPS'21 21 challenge on billion-scale approximate nearest neighbor search. In Proceedings of the NeurIPS 2021 Compe- titions and Demonstrations Track, 2022.
[57] Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. FreshDisk ANN: A fast and accurate graph-based ann index for streaming similarity search. 105 2021.
(58) Ryan Spring and Anshumali Shrivastava. Scalable and sustainable deep learning via randomized hashing. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 445-454, 2017.
[59] Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Har- sha Vardhan Simhadri. DiskANN: Fast accurate billion-point nearest neighbor search on a single node. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
[60] Javier Vargas Muñoz, Marcos A. Gonçalves, Zanoni Dias, and Ricardo da S. Torres. Hierar- chical clustering-bsser graphs for large scale approximate nearest neighbor search. Pattern Recognition, 96, 2019.
[61] Jiadong Xie, Jeffrey Xu Yu. and Yingfan Liu. Graph based k-nearest neighbor search revisited. ACM Transactions on Database Systems, 2025.
[62] Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Amool Overwijk. Approximate nearest neighbor negative contrastive learning for dense text retrieval. In Proceedings of the 9th International Conference on Learning Representations
(ICLR), 2021.
[63] Haike Xu, Magdalen Dobson Manohar, Philip A. Bernstein, Badrish Chandramouli, Richard Wen, and Harsha Vardhan Simhadri. Inlplace updates of graph index for streaming approximate nearest neighbor search. DrXiv:2502.13822 2025.
[64] Haike Xu, Sandeep Silwal, and Piotr Indyk. A bi-metric framework for fast similarity search. arXiv:2406.0m 0289] 2024.
14

---

[65] Minjia Zhang, Wenhan Wang, and Yuxiong He. GraSP: Optimizing graph-based nearest neighbor search with subgraph sampling and pruning. Proceedings of the 15th International Conference Web Search and Data Mining (WSDM), pages 1395-1405, 2022.
[66] Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. Towards efficient index construction and approximate nearest neighbor search high nigh-dimensional spaces. Proceedings of the VLDB Endowment, 16(8):197911911 2023.
15

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction accurately describe both the theoretical and experimental claims made in the paper.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss the main limitations of our work, including the failure to provide theoretical worst-case runtime guarantees (see Section 4). We also discuss limitations the experiments, like our inability to run very large graphs that are truly navigable.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
16

---

Answer: [Yes]
Justification: All theorems are rigorously stated, and proof' are correct. For the main theoretical result (Theorem [ one small lemma needed to moved the appendix- otherwise the full proof appears in the main body.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Extensive additional details on the experimental setup, including all hyperpa- rameter settings, are provided the appendix. URLs where datasets where accessed from are included in the references and cited. Moreover, very detailed pseudocode is included for all greedy-search variants implemented in the paper, including our new Adaptive Beam Search method.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
17

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: We able prepare sufficiently clean, publicly-viewable code by the submission deadline. However, we plan on making our code available on GitHub soon. All datasets are freely available online, and provide links ot each.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.co... ctaips..c/pubicc/guiicc httpa///gguiieee/eeeeutbiiaiii swt.suubbiiiiiooooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: As mentioned above, extensive additional details on the experimental setup, including all hyperparameter settings, are provided the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The search algorithms considered are deterministic and, all but one case, we used the same deterministic query/dataset split used in prior benchmarks (6] There is randomness in some of the graph construction methods like HNSW and the Navigable Graph construction algorithm, so in principal, could have trials across different random
18

---

constructions. However, doing so would have been computational prohibitive, and given the consistent ranking of methods tested across wide variety of datasets, values of k. etc. we believe the paper provides sufficient evidence of the potential performance of Adaptive Beam Search.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Information on compute resources is provided in Appendix B.3
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Our research process conforms to the code of ethics stated at the website. As for potential harmful consequences: our work addresses nearest neighbor search, which is a broadly applied algorithmic primitive that has been studied for decades. The problem has applications throughout the machine learning, and those applications could potentially have harmful consequences, but it is difficult to speculate.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
19

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: As discussed above, the paper focuses foundational algorithms research for nearest neighbor search. This problem so widely applied, is difficult to speculate on the impact of its many possible applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
20

---

Answer: [Yes]
Justification: License information for datasets and for the open course code used for various graph-constructions provided in Appendix B.3
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwppsppppeaaaaeeeee thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
21

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve such research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were only used for producing tikz figures. Not text written, edited, or formatted by LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non nta-standard components.
Please refer to our LLM policy //npur:////uurii cc. fc//oonferencee/2225/// for what should or should not be described.
22

---

A Additional Proofs
A.1 Nonexistence of Sparse a-Shortcut Reachable Graphs
Recent work of Indyk and Xu [2]] shows that, for = 1, standard greedy search (i.e., beam search with beam width 1) provably returns a
[a+1 a-1 + cc) approximmaee nearest neighbor for any constant when run on a-shoricul reachable search graph G. The a-shortcut reachability property requires that, for any nodes z, y E {l,.... n with d(z,z) > O, there is some z E (N with a d(z, y) < d(x, y) for some parameter 2 I. The requirement exactly corresponds to navigability (Definition D when a = and is strictly stronger condition when a >
The guarantee of [24] is non-vacuous when > 1. Unfortunately, it is also not hard to see that for any fixed a > 1. there exist relatively low-dimensional point sets with no sparse a-shorteut reachable graphs. In fact, for any constant a > 1, it suffices to consider random point set in O(log n) dimensional Fuclidean space. This contrasts the situation for navigability (a = 1), since [1I shows that an (()n)) average degree navigable graph can be efficiently constructed for any point set in any dimension (indeed, in any metric space), under the mild assumption of unique pairwise distances between points (which can be ensured, e.g., by tie-breaking with node id). Formally:
log For any a > 1, let m m= (1-]ja}) There are n points in m-dimensional Euclidean spuce with unique pairwise distances, but the only a-shortcul reachable graph for the points is the complete graph. Further, by [[TV, the points admit a navigable graph with ((y)) average degree.
Claim 5.
Note that for constant a > 1, - 1/ax a constant bounded away from 0, so m Ollgg)..
Proof. It suffices to find a set of n points whose pairwise distances all lie in the range (1/a, 1]. Then, for any x A y, the only with d(z,y) < d(z,z) y) is z y. Thus, to ensure a-shortcut reachability, all nodes must be connected to all other nodes - i.e. G must be the complete graph.
If we are not concerned about the dimensionality, finding a set of points in Euclidean space with all pairwise distances lying in (1/o,, 1] is trivial: take the standard basis vectors in RR,, scaled by 1 1/v2 so that they all have distance 1 from each other. Subtract an infinitesimally small random amount from the non-zero entry of cach so that all pairwise distances are unique, but still lie in (1/a, 1].
To obtain result in lower dimensions, we instead consider random points. Concretely, consider points in RT with each entry set independently to 1 or 1 with probability 1/2. For each x, y. we have E|||æ= 2 2m and by standard binomial concentration bounds, Príl]Iæ y1l2 2m 2
m11 - 1/a)] S exp(- 1ep(--(((11)))) - 1/a)² - m)). Setting m O log ). this probability is bounded [I-1/aj²
by 1/n" for large constant c. Taking union bound over all (?) n² pairs of points,
that all their squared pairwise distances lie in the range (2m(1 - 1-1/a), 2mm11 + 1-1/a) with probability at least 1 - 1/n0-2. Normalizing by 2m(1 (1 + 1-1/a) ). all the squared pairwise distances 1-1//
are less than one 1 and greater than 1-17 2 1 (1 1/a) = 1/a, where we use the fact that
I- 2 1 -1-22 2x for all x. Thus, all squared pairwise distances, and in turn all pairwise distances, lie in T+z the range (1/a, 1), as desired. We can again ensure unique pairwise distances by adding arbitrarily small random perturbations to each point, completing the claim.
A.2 Failure of Beam Search on Navigable Graphs
We next give simple counterexample, showing that, unless the beam width is set to essentially the full dataset size, standard beam search on a navigable graph can fail to find an approximate nearest neighbor when run on navigable graph. This observation in part motivates the definition of our alternative distance-based stopping rule, (3) and the resulting Adaptive Beam Search algorithm.
Claim 6. For any finite C, there exists set of n points in 2-dimensional Euclidean space and a navigable graph G such that, for some query point g beam search run on G with beam width
b < n - 3 returns T with d(g, σ) 2 C d(g,x").
23

---

X2 (1,1)
X3 (m,
v2
2 1
2
X1 (0
X224 R (1,0)
q (m, 0)
Figure 5: Example showing that standard beam search fails to find a nearest neighbor in navigable graph. Points X4.- ..... X,, all located arbitrarily close to (1,0). They are all nnected to x1 and X2. as well as to each other. The graph is navigable, since we can navigate from X1, X4, Xn to X3 and vice-versa through X2. All other nodes are directly connected to each other. Suppose beam search with beam width b Σ n - 3 is initialized at x with query Because X x, are all closer to the q than X2, the method will never expand X2 and thus fail reach the nearest neighbor X3.
Proof. Consider the following dataset in 2-dimensional Euclidean space shown in Figure 3 Xi (0, 0), X2 = (1, X3 (m, 1) for some arbitrarily large value m. Let X1, X...... Xn, all be located at arbitrary positions in an ball around (1, 0) for arbitrarily small c. We can check that the graph with the following two-way edges is navigable: (x2, X3) and (x, ) for all i E 11. E {4....,n}
Consider beam search initialized starting point x, (0, 0) with query q = (m, 0). The nearest neighbor to q is X3 with ||q X3 l2 = 1. In the first step of beam search, all neighbors of xı (x2, X4. :4....;;X, x,) will be added to the search queue. Since X2 is further from q than all nodes in X4...., x,, the algorithm will then expand nodes from this set in succession, adding no new nodes to the queue since none of these nodes are connected to X3, the only remaining unexplored node. If b S n2 3, the algorithm will then terminate, with X2 never expanded and X3 never explored.
As result, beam search returns some ž E {x1...., },} with distance ||q x||2 2 lq 2||2 || ||q-xa z m-c Setting m C + gives the result.
It thus
achieves approximation factor
B Additional Implementation Details
B.1 Pscudocode for Generalized Beam Search Variants
Below, we provide detailed pseudocode for generalized beam search (Algorithm [T] under stopping conditions (T) (classic greedy search), (2) (classic beam search), and (3) (Adaptive Beam Search). While the greedy search order and stopping rule determine the number of distance computations performed, it is possible to optimize runtime and storage requirements by using appropriate data structures to implement the stopping rule. Additionally, we can avoid adding nodes to the candidate that, if popped off C, those nodes would trigger the termination condition anyways.
set C if we
Adaptive Beam Search and Greedy Search. Pseudocode for Adaptive Beam Search is given in Algorithm 2 The same pseudocode can be used for greedy search, by setting the approximation parameter 7 0, so that the Adaptive Beam Search stopping rule becomes the greedy rule (
The key optimization that we maintain a heap. B3 of the k nearest points seen so far, which avoids having to extract these neighbors from the set of discovered nodes DD every time termination condition 33 is checked. Further, if a newly discovered node has distance larger than (1 + 7) times the 1s closest seen so far, it will always trigger termination if considered for expansion. Thus, we can avoid adding it to the candidate set unexpanded nodes, C. See Lines 12-17. This optimization avoids letting C grow unnecessarily large with nodes that will never be expanded.
Classic Beam Search. Pseudocode for classic beam search is given in Algorithm 3 The implementa- tion essentially identical to that of Adaptive Beam Search, except that heap of the b nearest points seen so far must be maintained to efficiently check stopping condition (2) each time node is considered for expansion or newly discovered. At the end of the algorithm, the nearest points from this heap are ultimately returned. See Lines 22-23.
24

---

then Algorithm 2 Adaptive Beam Search
Input:
Search graph G over nodes {1..... n), starting node distance function d, query g. target number of nearest neighbors k, approximation parameter 7,. Output: A set of k nodes B C (1,,... n.)...,n). Each x B is ideally close to y with respect to the
distance function d.
D {s}
Dictionary Discovered nodes
2: C + [s, s))}
D Min-heap of candidates D Max-heap of best results
3: B + [(s,d(g, 8))}
4: while C' is not empty do
5: (x, d(q. x)) < heappop(C))
6: if [B| k and (1+ findmax(B3) d(q. x)
7: break
Termination condition from Eq.
8:
for all E (x) do
9:
if y & D then
10:
D s insert(D..) y)
[B] k d(q.8) y) (1 +7) findmax(B) then
12:
heappush(B, (y, d(g. y))
heappush(C, (y. ((: y)))
14:
if [ k + then
heappop((3)
16:
return B
Algorithm 3 Classic Beam Search
Search graph G over nodes {1, ..... n2. starting node distance function d, query beam width b, target number of nearest-neighbors k. Output: A set of k nodes B C. [I, Each æ E B is ideally close to q with respect to the distance function d.
Input:
1: D {8}
Dictionary of discovered nodes D Min-heap of candidates b Max heap of best results
2: C + d(s s))}
3: B [(s,d(g s))}
4: while C is not empty do
5:
(x, d(q, .z) <- heappop
6: if [B] and findmax(B (8) < d(g, then
7: break
Termination condition from Eq.
8:
for all E Na(()) do
9:
if y & D then
10:
D <- insert(D,y)
11:
if [ or d(g. v) < findmax(B) then
12:
heappush(B, (y, d(g. v)))
heappush(C, (y, v)),
14:
if B b+ then
heappop((3)
16:
for i= 11...... (b
k) do hcappop(BB).
17:
> Reduce B down to the best & results.
return B
B.2 Sparse Navigable Graph Construction via Pruning
As discussed, in Section 5 evaluate the performance of our Adaptive Beam Search method both truly navigable graphs, where it is backed by the theoretical guarantee of Theorem I and on heuristic "approximately navigable" graphs constructed using variety of popular methods.
To construct sparse navigable graphs, use the construction of 13 For m |v3n In n... each uniformly random nodes. As shown in [13], such graph is navigable with high probability and has average degree V(Vnloonn
node is connected to its m nearest neighbors along with 3n lan
25

---

We further sparsify these graphs, both to facilitate running lcrge-scale experiments and to more accurately reflect performance on graphs with practical levels of sparsity. To do so, we employ pruning strategy that removes redundant edges from the graph while maintaining navigabilityy Pseudocode for the pruning method is given in Algorithm iterates over each node in the graph, only keeping minimal set of out edges needed to ensure navigability, In particular, for each node E {I....,W n {5}, by Definition [ we must ensure that s has an out neighbor æ with d(x, t) < d(s, t). The method iterates over each adding an neighbor of & to the keep set only it is needed to ensure this condition holds for some (i.e., if no edges already in keep ensure the condition). After checking all it removes all neighbors of not in keep.
starts with a navigable graph G, then
Algorithm 4 Navigable Graph Pruning
Input: Navigable graph G on nodes (1....,
n). distance function d. Output: Subgraph of G' that is still navigable over {I....,,)) ,.} but ideally has many fewer edges.
1: for all in (1..... (1....,.)) do
2: keep ()
Set of out neighbors that will remain after pruning. >> Set of out neighbors that will be removed after pruning.
3: remove f- (s)
4: for all in (1, [I,...,7) n {s} do
5: navigable + FALSE
6:
for all in keep do
7:
if d(z, t) < d(s,t) then
8:
navigable + TRUE > Navigability condition satisfied. No need add an edge. break not navigable then for all y in remove do if d(y,t) < d(s, t) then keep keep U {y}
9:
11:
12:
13:
D Keeppin edge from to y ensures navigability to
14:
remove + remove {v}
15:
break
16:
for all in remove do
C.remove_edge((..)) return G
The pruning strategy of Algorithm 4 can produce navigable graphs that are significantly sparser than those constructed by 13]. J. See T for summary of the average degrees achieved for our tested datasets. Unfortunately, the runtime our pruning method scales least quadratically with n. This limits our ability to apply the method to the full datasets. An interesting open question is to improve the running time of constructing very sparse and truly navigable graphs
Average Out Degree Before Pruning
Average Out Degree After Pruning
Dataset
Dimensions
# Nodes
SIFT M 26
128
100K
3682
59
DEEP96 7
96
100K
3682
77
MNIST 36
784
50K
2516
45
Table 2: Average out degrees of navigable graphs before and after pruning. Note that we run on subsamples of the full datasets from Table due to the high computational cost of pruning.
B.3 Omitted Details on Experimental Setup
We next give additional details on the datasets and graphs used evaluate Adaptive Beam Search.
Datasets. Table I summarizes the six benchmark datasets used in our experiments. The citation for each dataset includes note listing the URL where we obtained the specific version of the dataset used our work. The datasets are available under the following licenses: MIT License (MNSIST), CCO 1.0 Universal (SIFT, GIST), and the Open Data Commons Public Domain Dedication and License (G)oVe). We were unable to find license information for Deep96 and Deep256. Both are available in the public domain.
26

---

For DEEP96, we used a one-million-poie pre-sampled dataset from [6]. but our 100K points used for the navigable graph experiments were sampled from the original dataset available at https 7/github. www.comm//at/eeeeeec http/mmassui2282 BereB/deepbb____
For GloVe, we sampled one million nodes from the original dataset. The GIST data only includes 1K query points by default. To generate 10K query points, in order to match the other benchmarks, we sampled additional query points uniformly at random from the so-called learning data points, which are included with GIST for hyperparameter tuning. We did not use this set of points for any other purpose or any parameter tuning.
Graph Parameters. As discussed in Section 5 we construct heuristic graphs using four
mon methods: HNSW 43 Vamana [59], NSG [16), and EFANNA [13]. We used our own implementations of HNSW and Vamana. Code for NSG available under an MIT License at
https://giithub.comm com htte://oo///J/aaaiia /wt.////LLeaannnnnaaaaa
and for EFANNA under a BSD License at https
//gibbbb.cam///Uueerrnnng////
The heuristic graph construction algorithms employed take as input various hyperparameters. Settings given in Table 3] For Vamana, used the same hyperparameters
used for these hyperparameters for all datasets, matching those in the original paper [59]. which were found to work well for SIFT, DEEP96, and GIST; using the same parameters for the other datasets yielded similarly good results. The hyperparameters for EFANNA [15] and NSG [66 for SIFT and GIST are taken from authors' repository [16]. The same parameters were also used by (65] and [59] For NSG and EFANNA with DEEP96, we used the optimal values used by [65]. For EFANNA with MNIST, DEEP256, and
GloVe, we tested them using the two set of hyperparameters- the ones used for SIFT and GIST- and picked the better performing. We did similar thing for NSG with MNIST, DEEP256, and Glo
EFANNA
HNSW
NSG
Vamana
Dataset
K
L
iter
S
R
M
efC
nn
R
I
C
I.
R
SIFTIM
200
200
10
10
100
14
500
200
50
40
500
125
70
2
DEEP96
200
200
10
10
100
14
500
200
50
40
500
125
70
2
DEEP256
200
200
10
10
100
14
500
200
50
40
500
125
70
2
GloVe
200
200
10
10
100
16
500
400
70
60
500
125
70
2
GIST
400
400
12
15
100
24
500
400
70
60
500
125
70
2
MNIST
200
200
10
10
100
14
500
400
50
40
500
125
70
2
Table 3: Experimental Hyperparameters for Different Datasetsa dn Graph Constructions
For HNSW, we used the hyperparameters that 65 found to be optimal for SIFT, DEEP96, GIST, and GloVe. For HNSW on MNIST and DEEP256, we tested with values of M=14,16, 16,24 and used the best performing on the standard beam search. Since the authors found the ideal value of efc for SIFT, DEEP96, GIST, and GloVe be 500, we used this value for DEEP256 and MNIST.
Computational Resources. Navigable graphs were constructed using our pruning methods run on single core of 3.2GHz Intel Core 1290OK CPU with access to 128GB of DDR5 4800mhz RAM. To accelerate pruning and take advantage of available memory, we precomputed all pairwise distances between pairs of points in the dataset. Each graph required several hours construct. All other experiments were run on a single 2.9GHz Intel(R) Xeon(R) Platinum 8268 CPU with access to 32GM of RAM, although most 4GB was used for any individual experiment. Producing single recall/distance computation tradeoff curve requires several hours for each dataset and algorithm.
C Additional Experimental Results
In this section, we include additional experimental results.
C.1 Navigable Graphs
In Figure [ we compare beam search termination conditions on three datasets for 100. The results are similar to those reported in Figure 3 for & = and A: = 10, but with less significant gains seen for Adaptive Beam Search as compared to standard beam search. As for smaller values of Adaptive Beam Search V2 underperforms both other methods.
27

---

Nevigable, Graph: SFF. 100
1.00
Navigable, Groph: DEEPS6, k-100
1.00
Novigeble, Graph: MNIST. 100
Adoptive
0.28
0:35
0.93
0/37
0/37
0:97
0.37
26
215
212
21
0:45
215 21.
202
211
20
0:41
22
2
211
2
Search Dazance Carsulations
of Searth Didance Caruulatoos
Search Distanee Calculations
Figure 6: Comparison of generalized beam search termination conditions on navigable graphs across three datasets: SIFTIM, DEEP96, and MNIST (columns), with k = 100 (rows). Adaptive Beam Search consistently outperforms standard beam search, while the alternative Adaptive Beam Search V2 underperforms both by a significant margin.
IINOW, Graph: ke1k
HNSW, Graph: DEL2256, 1=
1N59, Graph: DUPP9, k=10
Standard Search
Azagtive Search lour mothod)
Rocal
Recal
Stardard Beam Search
Standard Beam Search
Ataptive Beam method
Adeptive Beam methort
Search Distance Calcuations
Search Distance Caicu altuuations
Search Distance Calculations
HNSW Graph: GLOVE, k-10
HNSW, Graph: GIST k-10
HNSW, Graph: MNIST, k-30
Adaptive
Decal
Reral
Search
2t
Calculations
Calculations
Figure 7: Comparison of generalized beam search termination methods HNSW graphs with = 10 across six datasets. Adaptive Beam Search outperforms standard beam search, with the degree of improvement varying across datasets.
C.2 Heuristic Graphs
In Figure 7 we compare beam search termination conditions on HNSW search graphs for all six benchmarks and h 10. In Figure 88] we include further results on HNSW graphs for k 1 and k = 50 across three datasets. As with our other experiments on heuristic graphs (see Figure 4 we see that Adaptive Beam Search generally outperforms standard beam search, sometimes by large margin. One exception is for GIST with k = 1, where beam search performs marginally better.
C.3 Adaptive Beam Search vs. Adaptive Beam Search V2
As illustrated in Figure 3 Adaptive Beam Search V2, which uses the more aggressive stopping condition of (6), generally underperforms both Adaptive Beam Search and classic beam search. We believe this is due to the fact that, to achieve high recall, the parameter for this rule needs to be set high, causing the method to terminate late and perform a large number of distance computations on some queries. This phenomenon is illustrated in Figure 9
28

---

HNSW, Graph: SIFT, k-
HNSW, Graph: DEEP96, k-50
HNSW, Graph: GIST, k-50
Adqptine
motloed)
Distance Calcuaaiinss
Search
2
Distance Calculations
HNSW Graph: SIFT,
HNSW, Graph: DEEP96, k-]
HNSW, Graph: GIST,
Shandars Deam Search
Adaptive Beam Search mathos)
Taccal
Paccal
Suanderd Bearn Search
Gaandard Beam Search
Adeptive Beam Search methos))
Aduptive Boam Search tour mathod)
Search Distance Calculations
Search Distance Calcuaation:
1n Search Distance Calculations
Figure& 8: Comparison of generalized beam search termination methods on HNSW graphs across three datasets with k = 50 and = 1. Adaptive Beam Search outperforms standard beam search as we vary k with the exception of GIST for k = 1, where it slightly underperforms.
Mevityetle
N56, Groph, DEEP236, Rooil 0.55
HUSWl Groph DEEPO6, Rocal - 8:95
Adoytive Beam Search 12 Adaptive Bean search (ou meethes
1000
Aceetive deam Search Jour (estrod)
Acactive deam Search (oa memoot)
200
Figure 9: Histograms for the number of distance computations performed by Adaptive Beam Search and Adaptive Beam Search V2. We tune the y parameter for each method to achieve fixed recall value, finding that Adaptive Beam Search V2 has a heavier tail of queries that require many distance computations, in part explaining its poor performance seen in Figure
1.03
HNSW, Graph: SIF,,
1.03
HNSW Graph: DEEP256,
HNSW, Graph: DEEP06, k-10
0.99
0/95
6.99
037 Stansard Bean Search
D197
Standard Beam Search
0:37
Sbinoard Beam Search
Adoptive Search (our mathod)
Adoptive Beam Search /our method)
Adsptive Beam Search (our methodi
Hiphid Beem Swithh /
llyrid Beam Search,
lyybed Beam Swirhh 8
hytnid Beam Soarch 2-20
hylrid Boat Searts -2200
Hybeidl Beam Saarch,
Hybrid Beam Search, 0.1
lybrid Deem Seatch y 0.1
Hybrid Deam Search, y 0.1
0.55
gl1 3
2
0/91
g 3 g/v gi
g
Calculations
Dizaance Colculation
Search Distance Calculations
Figure 10: Evaluation of the Hybrid Beam Search termination rule from 7 three datasets. There is very little difference in performance between the method and Adaptive Beam Search.
C.4 Hybrid Stopping Rule
As discussed in Section 5 would be interesting to consider other relaxations of greedy search beyond beam search and Adaptive Beam Search. For example, (21) considers rule similar to Adaptive Beam Search V2 ( instead of using the stopping criteria d(g. x) 2 (1 + 7 de as in Adaptive Beam Search, they use criteria d(g, x) du + y d1, where di and de are the distances
29

---

from the query q to the closest and hthh closest discovered nodes, respectively. Initial experiments on this approach suggest that performs very similarly Adaptive Beam Search.
Another obvious candidate is a stopping rule that combines the distance-based relaxation of Adaptive Beam Search and the rank-based stopping rule of standard beam search. In particular, in Algorithm T we could choose to terminate if there are at least:
b items ; D with (1+ ()+) d(g, S d(g,
where 6
distance-based relaxation. We ran initial experiments with this natural hybrid termination, which are shown in Figure T0 To obtain a trade-off curve between recall and distance computations, we either fixed b 3 for parameter and then varied 7 or we fixed and varied B3. Somewhat surprisingly. the hy bybi method appears to perform very similarly to Adaptive Beam Search, although further study of this termination condition and other relaxations would be valuable.
"width parameter" and y
30


Reviews:
[{"review_id": "IMa4vBNcEY", "reviewer": "Reviewer_gJ9t", "summary": "This work provides a new stopping criterion (the eponymous adaptive beam search) for the popular beam search algorithm on graph-based approximate nearest neighbor search (ANNS) data structures. As long as the constructed graph is _navigable_, one can provably achieve a clean tradeoff between accuracy of the beam search and its speed (i.e. number of steps of the search before stopping). In addition, this work shows that this tradeoff doesn't exist for the standard beam search: in the navigability model, it's entirely possible for it to diverge entirely. In the empirical evaluation, graphs searched with the adaptive beam search use fewer distance comparisons than the standard beam search to achieve a fixed recall.", "questions": "1. In the $\\alpha$-shortcut reachability setting, there does seem to be a recent paper on beam search (released publicly at ICML after the NeurIPS submission deadline): https://openreview.net/attachment?id=JnXbUKtLzz&name=pdf\nIf the authors believe the results to be analogous (with respect to $\\alpha$-reachability and navigability), it would be nice to get their thoughts on how the key beam-search results compare.\n\n2. With the weakness in mind, is it possible that the navigability property itself may be _too_ loose to provide a convergence guarantee? I'd appreciate the authors' thoughts on this, as the additional structure of the $\\alpha$-shortcut reachability setup seems to be more amenable to such a guarantee (just looking at the main result of Indyk/Xu).\n\n3. Similarly, is beam search's inability to converge for most possible beam-widths (claim 2) an issue with the navigability property? The paper linked above does seem to suggest that beam search does converge on graphs that satisfy $\\alpha$-shortcut reachability.\n\n4. Is it possible to get an implementation of the adaptive beam search with a single priority queue (like implementations of standard beam search)?", "limitations": "See questions, especially 3/4", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. This contributions of this paper are primarily theoretical: by the admission of the authors, the stopping criteria specified in this work has been described as a heuristic in prior works. Contributing theoretical grounding of heuristics in a research area where theory is usually well behind the empirical state-of-the-art is welcome and necessary.\n\n2. Navigability (in comparison to $\\alpha$-shortcut reachability) is a simple requirement that can (approximately) model a number of popular graph datastructures used in practice (HNSW, DiskANN, etc).\n\n3. The paper is well-written and easy to digest.\n\n4. The empirical evaluation is thorough and well-documented, and nicely complements the theoretical results. \n\n\n**Weaknesses/Limitations**\nWhile this work does show that adaptive beam search arrives at an approximate solution parametrized by $\\gamma$, it does not show any convergence guarantees: it might take an inordinate number of steps through the graph to achieve the result stated in theorem 1, although the empirical study seems to disagree with that possibility.", "was_revised": true, "final_justification": "The authors provide an illuminating discussion comparing $\\alpha$-shortcut reachability and navigability, and it helps in visualizing the difficulties that arise in producing (fast) convergence guarantees in the navigability model. However, I think this submission would have greatly benefitted from such a result, providing analogous results to existing work in the $\\alpha$-shortcut reachability setting and complementing the empirical results.\n\nNevertheless, I believe the existing work is otherwise solid, and so I maintain my original score.", "rebuttal": "Thank you for the positive feedback and useful questions. We address the specific questions below:\n\n**Question 1.** We also became aware of this paper after our submission, and plan to add a citation. Basically, the paper generalizes the cited work of [Indyk, Xu, NeurIPS 2023] to approximate $k$-nearest neighbors for $k > 1$. What is called “beam search” in that paper is equivalent to what we call “classic greedy search”, since the beam width is set exactly equal to $k$, the number of nearest neighbors desired. \n\nWe believe that, like the Indyk-Xu work, the referenced work is complementary to ours. It also provides a multiplicative error guarantee (as well as a stronger convergence time bound). However, the bounds in these papers apply only when G is $\\alpha$-shortcut reachable for $\\alpha$ strictly greater than 1. In particular, their error bound is of the form $(\\alpha+1)/(\\alpha-1)$ for general metrics, so it becomes vacuous when $\\alpha = 1$, which corresponds to the navigability property. In general, $\\alpha$-reachability is a much stronger property than navigability when $\\alpha > 1$: as discussed in Section 2, navigable graphs with sublinear sparsity have been shown to exist for any dataset, whereas it is easy to construct datasets where any $\\alpha$-reachable graph requires $O(n^2)$ edges, and thus does not admit fast search, even if the search converges quickly – see our Appendix A.2 for more detail. We thus think it is valuable to study guarantees for approximate neighbor search under the weaker notion of navigability.\n\nPerhaps as further reason to study navigability, recent work by Conway et al. “Efficiently Constructing Sparse Navigable Graphs” and Khanna et al. “Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness” both study algorithms for finding minimum sparsity navigable and $\\alpha$-shortcut reachable graphs. Based on the results of these papers, it seems that finding a minimum sparsity navigable graph for a given point set is an easier problem than finding a minimum sparsity $\\alpha$-shortcut reachable graph. \n\nFinally, we find it interesting that our bounds require some sort of relaxation on greedy search. As mentioned, the referenced work and that of Indyk-Xu both obtain the same guarantees even when running beam search with $b = k$ (i.e., running classical greedy search). While very nice results, these bounds thus do not provide theoretical evidence for why a choice of beam width larger than $k$ (or, in our case, $\\gamma > 0$) is critical to good performance in practice. \n\n**Question 2.** Strictly speaking, navigability itself is indeed too weak a notion to prove convergence guarantees. Consider e.g., $n$ points arranged on a line, connected with a bi-directional path. This is a navigable graph, but if the query is on one end of the line and the starting vertex is on the other, convergence may require $n$ steps. \n\nNevertheless, citation [12] in the paper shows that it is possible to construct sparse navigable graphs with “depth 2”, meaning that greedy search converges in just two steps if the query is in the dataset. We agree that a very interesting future direction would be to see if properties like low-depth can be leveraged to prove fast convergence for queries not in the dataset (for which the goal is to return an approximate solution). We do not see any inherent barriers to doing so.\n\n**Question 3.** Yes, you are correct. The cited result proves convergence for standard beam search for $\\alpha$-shortcut reachable graphs. Our perspective on this is as follows: if you want the flexibility to work with navigable graphs (which are in general sparser and easier to find) you need to look beyond standard beam search. As mentioned in the response to Question 1, $\\alpha$-shortcut reachability seems to be stronger than what is achieved by heuristic graph constructions used in practice – indeed for these constructions, beam width $> k$ is generally required for good performance. However, the cited result proves convergence results for $\\alpha$-shortcut reachable graphs even for beam width $k$ (i.e., classic greedy search).\n\n**Question 4.** This is a good question – we do not immediately see how to do this. In our implementation, however, data structures only factored minimally into total runtime, which was dominated by distance/inner product computations. Note that the second priority queue ($\\mathcal{B}$ in Algorithm 2) has size bounded by $k$, the number of target nearest neighbors. Since $k$ is typically rather small, the data structure is inexpensive to maintain."}, {"review_id": "SyAFRCXKb3", "reviewer": "Reviewer_DYui", "summary": "This paper presents a theoretical analysis and practical contributions regarding the search algorithm in graph-based approximate nearest neighbor search, known as beam search. The proposed method is called Adaptive Beam Search. Unlike conventional beam search, the proposed method fixes the beam width to match the top-k value while relaxing the distance condition related to the termination criterion of the algorithm. Controlling this relaxation parameter manages the trade-off between search speed and accuracy.\n\nA notable aspect of the proposed method is that it provides a theoretical analysis of the beam search component, which has not been previously explored. Indeed, the existing literature contains few theoretical analyses of beam search itself, and more importantly, it lacks any discussion relating to the navigability of the graph. In this work, the conventional beam search is generalized through a highly intuitive concept of \"termination condition\", which leads to the proposed method. The resulting theoretical conclusions are intuitive. Moreover, in practice, the proposed method has been shown to outperform standard beam search across many datasets.", "questions": "The authors do not mention which libraries or implementations were used for the search method. It would be helpful to include such information. Did the authors implement everything from scratch, or did they build upon existing frameworks such as DiskANN or faiss?\n\nNote that faiss is the de facto standard library for nearest neighbor search. If the proposed method can be integrated into faiss, users would welcome it.", "limitations": "None", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "I enjoyed reading this paper. The raised problem and the proposed solutions are clear, and the paper significantly contributes to the nearest neighbor search field. Therefore, I evaluate this paper as an Accept.\n\n# Strengths\n\nThe strengths of this paper are as follows:\n\n## Theoretical contribution\n\nThe theoretical contribution regarding the beam search component addressed in this paper has rarely been explored in previous theoretical studies on graph-based nearest neighbor search. In particular, by focusing on the \"termination condition\", the authors generalize the existing beam search and conduct discussions within that framework. The theoretical result obtained (Theorem 1) is very intuitive and practical. It is expected that deeper theoretical analysis will be developed based on this work.\n\n## Practical contribution\n\nAlthough this is a theoretical paper, extensive experiments validated its practical value. Many theoretical papers on graph-based nearest neighbor search have been purely theoretical and often unrelated to actual search performance. This is unfortunate, because graph-based nearest neighbor search is popular and widely used precisely due to its high practical performance. Theoretical work should explain that performance, but instead, they have often become theory for the sake of theory. This paper, while theoretical, provides insights that are closely linked to the practical performance of graph-based methods.\n\n## Completeness of the paper\n\nOverall, the paper is very well-structured. In particular, it gives the impression of a well-written document in which the authors successively present questions or points that readers may be wondering about or sympathizing with, then provide answers to them in order.\n\n# Weaknesses\n\nI do not have any strong weaknesses to point out, but I offer a few comments below.\n\n## Membership query for $\\mathcal{D}$\n\nIn Line 7 of Algorithm 1, there is a statement \"$y$ is not in $\\mathcal{D}$.\" This description is slightly inaccurate when reading only Section 3.1 and Algorithm 1. This is because $\\mathcal{D}$ is a priority queue, and checking for the existence of an element requires $O(|\\mathcal{D}|)$ time. This point is clarified in Algorithm 2, which provides more detailed pseudocode and represents $\\mathcal{D}$ as a dictionary, allowing for $O(1)$ membership checking. However, this is not evident from Algorithm 1 alone. A brief footnote in Section 3.1 mentioning this point may be helpful.\n\nAlso, in the faiss implementation of HNSW, a table (array) is used for $\\mathcal{D}$. It might also be worth mentioning that different libraries adopt different implementations.\n\n## V2 is necessary?\n\nThe only puzzling aspect throughout the paper is the introduction of Adaptive Beam Search V2 in Equation (6). I do not understand why this variant is introduced here. Its performance is inferior, and it does not need to appear in the main body of the paper. It would be better relegated to the supplementary material. Its presence slightly disrupts the rhythm of the paper overall.", "was_revised": true, "final_justification": "The technical contribution of this paper is significant, and I will maintain my original accept score.", "rebuttal": "Thank you very much for the positive feedback. The comments on presentation are helpful, and we will include the reviewer’s suggestions in the next draft. We will also consider moving Adaptive Beam Search V2. Indeed, this method is a relic of explorations from early stages of this project. Given its poor performance, moving it to an appendix probably makes sense. \n\nIn response to the question about implementation: all search algorithms were implemented from scratch. For the graph constructions (HNSW, NSG, Vamana, and EFANNA) some were implemented from scratch and some used existing codebases – see Appendix B.3 for details. Thanks for the suggestion about integrating the method into FAISS – this is definitely something we will consider."}, {"review_id": "PE6Q1Wib3C", "reviewer": "Reviewer_ZV7M", "summary": "This paper proposes Adaptive Beam Search to acclerate GANNS by replacing the classical beam search in order to reduce the expanded nodes in the graph. It provides theoretical guarantees in navigable graphs.  The authors also conduct experiments on real-world datasets to verify the proposed method.", "questions": "Q1. Could you compare your method with the three baselines mentioned above? i.e., (1) GGNN: Graph-Based GPU Nearest Neighbor Search (2) earned adaptive early termination (ref. [33] in this work) and (3) Jiadong Xie et. al. Graph Based K-Nearest Neighbor Search Revisited. \n\nQ2. Please specify the parameter selection in your experiments. \n\nIf those questions could be properly addressed, I would raise my rating.", "limitations": "Yes", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "S1. The authors proposed an interesting method for GANNS and established connections between search performance and navigable graphs in theory. \n\nS2. The experimental results are impressive, which reduces distance computations up to 50%. \n\nS3. The method is easy to implement and use in practice, which may be interesting for practical users or engineers. \n\nW1. The theoretical analysis depends on the assumption of navigability of the graphs, while widely-used HNSW, NSG and Vamana are just approximately navigable. \n\nW2. The experiments are not comprehensive. (1) There is no study on the effects of the parameter \\gamma. (2) There is no comparisons with the baselines such as learned adaptive early termination (ref. [33] in this work). (3) Another similar work is not mentioned in this work, i.e.,  Fabian Groh et.al.  GGNN: Graph-Based GPU Nearest Neighbor Search. GGNN also modify the termination condition of the beam search via a distance slacking factor. (4) It is not clear how the parameters of graphs are selected, which are key to the search performance. \n\nW3. The authors ignore the recent progress in GANNS, i.e., Jiadong Xie et. al. Graph Based K-Nearest Neighbor Search Revisited, in TODS. This work take an adaptive strategy on online selected neighbors of expanded nodes. This work should also be considered as the baseline. \n\nW4. The technique depth is kind of limited, since it only modifies the termination condition.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback and address specific concerns and questions below.\n\n**W1:** This is true, however, given the diversity of graph construction algorithms, any broadly applicable theoretical results for graph-based near neighbor search will necessarily need to make some assumptions about the resulting graph produced. We believe that navigability is a reasonable assumption since 1) it is explicitly discussed as a target/inspiration for these heuristic graph constructions, 2) sparse navigable graphs are known to exist for all datasets [12], and 3) our method gives performance improvements not just on navigable graphs but on these popular heuristic constructions, evidencing that our theoretical results are still informative in practice. Prior theoretical results, such as those of Indyk and Xu, NeurIPS 2023 for graph-based near neighbor search require strictly stronger assumptions on the underlying graph, in particular, $\\alpha$-shortcut reachability.\n\n**W2 (1)**: All of the plots in the experiments section that plot recall vs. distance computations explore the effect of varying $\\gamma$: we obtain these plots by starting with a small value for $\\gamma$ and increasing its value in small increments, which strictly increases both the number of distance computations and the recall. For example, the first plot in Figure 2 uses gamma values ranging between .1 and .65. Nevertheless, we agree with the reviewer that it would be helpful to clarify this point in the writing. We propose to add annotations to the points on a few of the plots showing what choice of gamma led to what point. \n\n**W2 (2) and Q1**: \nWe were able to run comparisons with the Fabian Groh et. al paper. Thank you for pointing this paper out – we were unaware of the method. Indeed, that paper uses an additive instead of a multiplicative slack factor. While we cannot share new plots due to the rules for this year’s rebuttal, in our experiments, the Groh et. al method usually performs somewhere in between our adaptive beam search and regular beam search. There are a few exceptions: for some datasets (e.g., SIFT) it performs worse than beam search on some graphs (in contrast, our Adaptive Beam Search always performs better than standard beam search). We also note that, for MNIST, the Groh et. al method performs very close to our Adaptive Beam Search, which we attribute to the fact that the nearest-neighbor distance in this dataset is fairly uniform. In this case, a multiplicative vs. additive slack factor should behave fairly similarly. We will plan on adding these plots to the paper, as we believe they strengthen our work. \n\nConcerning a comparison to the method in [33], we have run experiments on the method in the past. Unfortunately, we found the method to be finicky and difficult to get good results on a variety of graphs and datasets. This seems to be due to a critical choice of hyperparameter that is difficult to estimate from the training data. We did not wish to include these results (which show [33] performing poorly in most scenarios) in case there is some implementation issue on our end. We would be happy to contact the authors to discuss the method so that we can include it for comparison. However, we do want to emphasize that we believe simple methods like standard beam search, Adaptive Beam Search, and the Groh et al. method are worth considering regardless of approaches like [33], which requires a training period and expects temporal consistency between queries to make the learned stopping rule meaningful in the future. In our experience, the simpler methods are more widely adopted in practice due to their robustness and ease of implementation.\n\n**W3:** The referenced Jiadong et al. paper came out after we made this submission. We did not ignore it – indeed, we have an email thread discussing the work! We are happy to continue considering that work, but do not have time to do a full experimental comparison during the short rebuttal period. \n\n**Q2:** Parameters for the graph construction methods are included in Appendix B, Table 3. Let us know if there are other parameters you are interested in."}, {"review_id": "6XJthfzOT9", "reviewer": "Reviewer_gkoF", "summary": "The paper suggests a query algorithm for nearest neighbor search within the graph-based framework for storing and processing large-scale data. Nearest neighbor query algorithms for large, high-dimensional data have become important given that such queries are frequently used for mining vector datasets generated by large language models. One way to store and process such large vector datasets is to construct a sparse directed graph where the nodes are the data items, and the neighbors of a node are cleverly chosen so that a nearest neighbour query q can be processed by moving along the nodes of this search graph in the direction where the distance from q decreases. There are techniques to construct such graphs so as to make query processing fast. Construction of this search graph is not the subject of discussion in this paper. The main subject of discussion is the query algorithm over \"navigable graphs.\" These are graphs such that for every query node q and node x (it'll help to think this as the current node during exploration), if d(q, x) > 0, then there is a neighbor y of x such that d(q, y) < d(q, x). \n\nSuppose we want k nearest neighbors of a query point q. The search algorithm follows this general template (taken from the paper):\n- Maintain two priority queues C and D. Initialise C with (s, d(q, s)) for an arbitrary node s.\n- While (C is not empty):\n\t- x = extractMin(C)\n\t- if (x satisfies 'termination condition'): break\n\t- For all y in N(x), if y is not in D, insert (y, d(y, q)) into C and D\n- Return k nearest neighbors by running extractMin k times on D\n\nThis general template allows us to write various search strategies that are used. We just need to specify the 'termination_condition': \n1. Greedy search: if there are k nodes in D with a smaller distance from q than x\n2. Beam search: If there are b (b > k) nodes in D with a smaller distance than x.\n\nThe above two techniques have been used in the past for query search. The paper suggests the following method, which they call adaptive beam search:\n3. Adaptive beam search: If there are k nodes v1, ..., vk in D such that (1+\\gamma)*d(q, vi) < d(q, x) for every i.\n\nThe tradeoff is between speed and accuracy. Beam and Adaptive beam search may improve the accuracy, but at the cost of increasing the number of distance calculations. The paper shows the advantage of using adaptive beam search over beam search in the following aspects:\n1. There are much better theoretical guarantees for accuracy on navigable graphs given by adaptive beam search over beam search. For adaptive beam search, it is shown in the paper that for \\gamma=1, the query algorithm will output approximately accurate results. On the other hand, it is shown in the paper that for beam search, one can construct an input dataset on which the algorithm performs accurately only at a huge cost of distance calculations.\n2. Experimental results show that for the same value of accuracy, adaptive beam search uses a lesser number of queries for most datasets.", "questions": "Comments: \n\n- It will be good to also include the greedy search in the experimental results to get a comparison.\n- I do not see the point of including adaptive search V2 in the experimental analysis.\n- Some other questions are mentioned in the summary and strengths and weaknesses.", "limitations": "Yes. The paper presents theoretical results that do not have any potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper discusses a problem that is current and very relevant in AI-powered systems. The improvement in query time will have a significant impact on many applications.\n- The theoretical guarantees are interesting.\n\nWeaknesses:\n- The negative result for beam search (which is for query complexity) seems incomparable to the positive result for adaptive search (which is for accuracy). Are there negative results related to query complexity also for adaptive beam search?", "was_revised": true, "final_justification": "I remain positive about the paper after the rebuttal. My concerns have been addressed in the rebuttal. I will maintain my original score.", "rebuttal": "Thank you for the positive feedback. Answers to specific comments and questions are below:\n\n**Re: Query Complexity Bound.** We think Claim 2 (the beam search lower bound) is comparable to Theorem 1 in the following sense: Theorem 1 shows that we can obtain a provable approximation bound when the Adaptive Beam Search method is run with a fixed relaxation parameter  that only depends on the desired approximation quality. On the other hand, Claim 2 shows that, setting the beam width $b  = c*k$ for essentially any reasonable factor $c > 1$ won’t guarantee that a good approximation is returned from standard beam search. Indeed, if $b = n$, then beam search performs an exhaustive search, and our lower bound holds all the way up to $b = n-3$. The goal was to rule out the existence of a comparable result to Theorem 1 for standard beam search – e.g., we rule out results of the flavor “setting $b  = (1+\\gamma)*k$ yields to a $1/\\gamma$-approximation.”\n\nThat said, it is interesting to ask about both upper and lower bounds on number of distance computations (which we believe is what the reviewer means by query complexity?). It is possible to construct adversarial navigable graphs for which even Adaptive Beam Search requires many distance computations. For example, consider points arranged along a one-dimensional line. If these points are connected via a bidirectional path, the resulting graph is navigable. However, a typical query (even when the query point is in the dataset) will require $\\Omega(n)$ distance computations to answer. \n\nNevertheless, as discussed in our response to Reviewer gJ9t03, citation [12] in the paper shows how to construct sparse navigable graphs with \"low depth\" – i.e., greedy search terminates in just two steps for queries that are in the dataset. This implies sublinear query complexity on average for query points in the dataset. Thus, there is hope to give query/computational complexity upper bounds for sparse navigable graphs satisfying such a low-depth or related condition. We believe this would be an exciting direction for future work.\n\n**Re: Greedy Search in experiments.** We did not include greedy search in our plots since there is not a natural way to trade-off between distance computations and recall. Indeed, greedy search is a special case of beam search with $b = k$ or Adaptive Beam Search with $\\gamma = 0$. In this sense, it produces a single point to the far left of the curves for Adaptive Beam Search and Standard Beam Search, which often has such low recall, it would be off the charts. That said, we think this point is worth emphasizing, so will consider including some annotation for the plots to indicate what specific distance computation/recall point greedy search would have produced. \n\n**Re: Adaptive Search V2.** Another reviewer commented on this as well, and the point is well taken. We will either appendicize or remove entirely."}, {"review_id": "3AAnYJIA7p", "reviewer": "Reviewer_Lky8", "summary": "The paper introduces a new search algorithm that adjusts the termination condition according to distance and theoretically demonstrates its ability to approximately solve the nearest neighbor problem on the navigable proximity graph index. Extensive experiments on real-world datasets validate the efficacy of the proposed algorithm.", "questions": "Please refer to W1-W7.", "limitations": "Yes", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\nS1. The paper studies an important problem.\n\nS2. The paper theoretically verifies the efficacy of the proposed algorithm on navigable graphs.\n\nS3. The algorithm presented in this paper can be seamlessly integrated into all proximity graph approaches through simple modifications.\n\n**Weaknesses**\n\nW1. The definition of beam search on line 159 deviates from existing approaches, leading to confusion regarding their equivalence, necessitating further discussion.\n- In traditional approaches, the queue in beam search has a width of $b$, exploring iteratively until all neighbors of nodes in the queue are farther from the query vector.\n- In contrast, this paper defines the terminal condition as when the top-$(b+1)$ node in $\\mathcal{D}$ is the explored node.\n- The key distinction lies in the fact that the queues $\\mathcal{C}$ and $\\mathcal{D}$ in the search are infinite, whereas the queue size in beam search is limited to $b$. It may remove a node from the queue if it is not currently in the top-$b$, but its neighbor could still be one of the top-$k$. If it remains in $\\mathcal{C}$ without removal. Is the situation the same?\n\nW2. The concept of decoupling beam search into two queues has been implemented in HNSW [1] and further proposed in [2]. Therefore, it is essential to discuss and emphasize the differences here; otherwise, the contribution may not be considered original.\n\nW3. The paper [3] presents the beam search on proximity graphs involves two phases. Has the author considered setting different values of $\\gamma$ for the two phases to potentially enhance search performance?\n\nW4. The enhancement offered by the proposed search algorithm appears relatively minor, particularly for small values of $k$ and low dimensions. Is the performance correlated with the values of $k$ and $d? More experimental results may be necessary to delve into this aspect.\n\nW5. Transitioning from a navigable graph to a practical version poses challenges due to the absence of navigable paths between all node pairs. Thus, beam search is suggested to enlarge the queue size and overcome local optima. However, the rationale behind adaptive beam search in the practical proximity graph index version is unclear and requires further discussion.\n\nW6. The example presented in line 185 is perplexing. Why does beam search require $m+1$ to find $x^\\*$? Is $x^\\*$ a neighbor of one of $y_i$?\n\nW7. At line 119, the statement \"navigable graphs can in general be much sparser than $\\alpha$-shortcut reachable graphs\" raises an issue. Releasing the $\\alpha$ condition implies that it is easier for $x$ to have a neighbor $z$ such that $\\alpha \\cdot d(z,y) < d(x,y)$. Hence, $x$ may have fewer neighbors to achieve $\\alpha$-shortcut reachable graphs compared to navigable graphs.\n\n[1] Hnswlib - fast approximate nearest neighbor search. https://github.com/nmslib/hnswlib.\n\n[2] Jianyang Gao, Cheng Long. High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations. SIGMOD 2023.\n\n[3] Zhang et al. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. OSDI 2023.", "was_revised": true, "final_justification": "After the rebuttal, my main concerns are still as follows.\n\n- The provable approximation guarantee is based on the assumption of graph navigability, a condition that is challenging to meet in practical scenarios, thereby limiting the practical utility of these guarantees. Since the navigability graph may have a large number of degrees, line 7 in Algorithm 1 can not achieve good performance when considering the guarantee.\n- The performance improvements proposed seem relatively modest, especially for lower values of \\(k\\) and dimensions. Insufficient experimental evidence, particularly in the absence of further results, raises concerns. The clarification states that on the MNIST dataset, no significant differences were observed across approaches, highlighting the necessity for broader experimentation using datasets like those from ANN and BIGANN benchmarks to substantiate effectiveness.\n\nConsidering the aforementioned points, I maintain my negative score.", "rebuttal": "Thank you for the feedback. We respond to specific questions below:\n\n**W1:** We can add further discussion of the equivalence. In short, for standard beam search, if at any point a node is in the $(b+1)$st or higher position in $\\mathcal{C}$, it will never be “explored”. In particular, this means that at least $b$ other nodes are closer to the query, so the termination condition is guaranteed to trigger immediately if that node is ever popped off $\\mathcal{C}$. Accordingly, the neighbors of a node not currently in the top $b$ are never added to $\\mathcal{C}$. Moreover, for this reason, the method does not change if the length of $\\mathcal{C}$ is truncated to $b$, which is the more standard implementation suggested by the reviewer. We hope this clarifies any confusion.\n\n**W2:** We do not claim splitting into two queues as a contribution. We view this as more of an implementation detail. As for “decoupling” into a search order + termination rule, it does seem that [2] shares this perspective, and we will be sure to add a citation. To be clear, in the paper we wrote: “We suspect the “decoupled view” of beam search is not novel, but we have not seen it presented”. The main novelty in our paper is observing that a simple alternative to the beam search termination criteria yields strong provable approximation guarantees when run on navigable graphs, and these guarantees also translate into better empirical performance. \n\n**W3:** We have not, but it is an interesting direction for future work. We value the simplicity of Adaptive Beam Search (which, like standard beam search, only involves a single hyperparameter). However, multiple phases could indeed be helpful.\n\n**W4:** The x-axis of all plots is on a log scale, so typical improvements range between a 10% and 50% reduction in distance computations. We consider this significant for a problem of such practical importance, especially given that Adaptive Beam Search is a very light-weight, simple to implement modification of Beam Search. That said, we do think there is room for further improvement! We did not notice a strong correlation with the improvement and $k$, although we agree that this is worth exploring more. We did notice that some datasets resulted in very little differences between the methods. MNIST is a good example. We believe this is because most MNIST queries have a very close nearest neighbor in the dataset. For such queries, even basic greedy search should perform quite well (indeed, basic greedy search always succeeds on a navigable graph if the query is exactly in the dataset). This leaves little room for improvement for Adaptive Beam Search or standard beam search for datasets like MNIST, so it makes sense that they perform similarly.\n\n**W5:** It is important to point out that local optima are an issue even in navigable graphs – standard greedy search is not guaranteed to return a good approximate nearest neighbor. Thus, the main goal of Adaptive Beam Search is to escape local minima exactly as the reviewer described. It does so by also “enlarging the queue”, just like standard beam search. The difference is that the amount of enlargement is “adaptive” rather than restricted to a fixed upper limit, b. As illustrated in Figure 1, this allows Adaptive Beam Search to spend more effort on more challenging queries. We can add more discussion about this intuition in the paper. \n\n**W6:** Thanks for the question – we will clarify this example. We agree that the current explanation is incomplete. To be more concrete, have the points $y_1,...,y_m$ all be equidistant from the query point $q$ (with distance $1.01$). Have $y*$ be the closest point in $y_1,...,y_m$ to $x*$. Have $y*$ connected to $x*$ and all $y_1,...,y_m$ points connected to each other. We can check that this graph is navigable. However, suppose we start search at $y_1$. $x*$ will only ever be found if we explore its neighbor $y*$. We won't do so in standard beam search with beam width $< \\Omega(m)$ if we assume node ids are arbitrary (since $y*$ will not be preferenced for exploration over any of $y_1$'s $m$ other neighbors). \n\n**W7:** Any $\\alpha$-shortcut reachable graph for  any $\\alpha \\geq 1$ (which is the relevant parameter regime studied in prior work) is also navigable. In particular, the existence of $z$ with $\\alpha d(z,y) < d(x,y)$ implies the existence of $z$ with $d(z,y) < d(x,y)$. Thus, it is always possible to construct a navigable graph at least as sparse as any $\\alpha$-shortcut reachable graph (take the $\\alpha$-shortcut reachable graph itself). In many cases, navigability allows for much higher levels of sparsity. E.g., in Appendix A.2, we discuss random point sets for which any $\\alpha$-shortcut reachable graph for fixed $\\alpha > 1$ requires $\\Omega(n^2)$ edges. At the same time, by citation [12] in the paper, there exist navigable graphs with just $O(n^{3/2})$ edges for these (and all) point sets."}]

Author rebuttal:

Meta-review: The paper gives theoretical analysis for the beam search component of graph based nearest neighbor search indices. The theoretical insights give a better empirical algorithm which outperforms standard beam search across many datasets. The reviewers also highlighted the readability and clarity of the paper. This paper contributes towards a growing body of work understanding graph based data structures for search and I believe the insights will lead to further downstream work.
Decision: Accept (poster)