WorksComputer Science
Variants of Beam Search for DiskANN
Abstract
Graph-based data structures such as DiskANN, HNSW, and NSG constitute the state of the art for large-scale approximate nearest-neighbor (ANN) search. Indyk and Xu introduced the notion of -reachable graphs, which include graphs built by DiskANN's slow-preprocessing construction, and proved that greedy search achieves an approximation factor of . Independently, Al-Jazzazi et al. proposed adaptive beam search (ABS) with a relaxation parameter , showing a approximation on navigable graphs (), where greedy search admits no guarantees. In this work, we unify and generalize these results by proving that ABS with parameter on -reachable graphs achieves an approximation of for any metric. Moreover, on sorted -reachable graphs (introduced by Gollapudi et al.) under the metric, we obtain the tighter bound . Beyond these theoretical results, we design a beam predictor using features inspired by fine-grained analysis of ABS, trained via a constrained objective that minimizes mean distance computations subject to a target recall. On three 100-million-point benchmarks, using graphs built by DiskANN's practical construction, beam predictor lowers mean query latency on SSD-resident indices at matched recall by up to relative to classical beam search (CBS). Relative to ABS, it is faster in of settings, by up to , and at most slower in the other ; at recall, its advantage over ABS grows from – for neighbors to – for neighbors. In memory, it needs – fewer distance computations than CBS and – fewer than ABS.
Introduction
Nearest neighbor search is a fundamental problem in data structures, with applications in search, recommendation systems and, more recently, retrieval-augmented generation (RAG). Given a dataset of vectors and a query vector , the goal is to retrieve the data vectors nearest to . Since exact search typically takes linear time in in high dimensions, much research has focused on approximate nearest neighbor (ANN) search: data structures and algorithms that efficiently return high-quality approximate answers. Early work on ANN search targeted modest datasets—millions of points in tens of dimensions—and produced a rich line of space-partitioning techniques, including locality-sensitive hashing [2, 12], KD-trees [3] and cover trees [5]. These methods scale poorly with the dimension: tree-based partitions must examine a number of cells that grows exponentially with it, and hashing needs many hash tables to reach high recall. To avoid this curse of dimensionality, more recent work has turned to graph-based indices such as DiskANN [16], HNSW [20], NSG [9] and NGT [14, 15, 27], which have become the dominant approach in practice due to their strong empirical performance.
Despite this empirical success, the theoretical understanding of graph-based methods remained limited until the recent work of Indyk and Xu [13], who introduced a family of graphs called reachable graphs (). This family includes the graphs built by DiskANN’s slow preprocessing, and the authors showed that a simple greedy search on such graphs converges to a local optimum whose distance to the query is at most times the true nearest-neighbor distance. Subsequently, Gollapudi et al. [10] extended this analysis to the widely used classical beam search (CBS), showing the same approximation guarantee for all elements maintained in the beam. In addition, they showed that DiskANN’s RobustPrune procedure produces a special class of sorted -reachable graphs, and proved that under the metric these graphs admit the sharper approximation bound of . Complementing these works, Al-Jazzazi et al. [1] proposed a modified search procedure called adaptive beam search (ABS), parameterized by , which delays termination to enable additional exploration. They proved a -approximation guarantee on navigable graphs—corresponding in our terminology to the regime —where classical beam search does not admit any provable guarantees.
Given these two extremes—classical beam search on -reachable graphs () and adaptive beam search on navigable graphs ()—it is natural to ask the following questions.
Q1. What approximation guarantee can adaptive beam search, parameterized by , achieve on -reachable graphs with ?
Q2. Can the improved -metric guarantee of Gollapudi et al. [10] be combined with adaptive beam search?
Our results. We answer both questions and, building on the intuition behind ABS, design beam predictor, which chooses the list size for each query independently for the search; in our experiments it is faster than CBS in 14 of the 15 SSD settings and within the run-to-run variation of it in the other, and faster than ABS in most settings. Our first result addresses the first question by showing that adaptive beam search on -reachable graphs achieves an improved approximation guarantee, summarized in the following theorem.
Theorem 1.1. Let be an -reachable graph with , let be a query whose distances to the points of are pairwise distinct, let be the result of adaptive beam search (sorted by increasing distance from , and let denote the true top- neighbors of sorted by increasing distance. Then for any metric ,
Building on this result, our second contribution addresses the second question by establishing a sharper approximation guarantee for adaptive beam search on sorted -reachable graphs under the metric, as summarized below.
Theorem 1.2. Under the hypotheses of Theorem 1.1, if in addition is sorted -reachable and is the metric, then for any ,
The general-metric bound is tight, and it recovers the bound of Indyk and Xu [13] at and that of Al-Jazzazi et al. [1] as . The sorted- bound is tight where the first term of the max dominates, and it recovers the bound of Gollapudi et al. [10] at . § 4 proves both theorems, with the semidefinite program used for Theorem 1.2 solved in Appendix § 9, and gives the tight examples (§ 4.4).
Both theorems concern (sorted) -reachable graphs, such as those built by DiskANN’s slow preprocessing, whose naive construction takes time. The graphs that DiskANN builds in practice, including those in our experiments, are not known to satisfy these definitions, so the guarantees do not cover them. However, on these graphs used in practice, recall moves in the direction that the bounds suggest: on three 100-million-point datasets, the recall of ABS rises with , and it is higher on a graph built with DiskANN’s sorted pruning rule than on one built with the candidates in random order (§ 6.2).
Why does ABS help? As Al-Jazzazi et al. [1] observe, it adapts to the difficulty of each query. Its stopping rule compares the next candidate with the query’s current top-, so it stops early on an easy query, whose top- settles after a few steps, and keeps searching a hard query, whose top- is still improving. In effect, ABS moves distance computations away from queries that are already accurate, where more search buys little recall, toward queries that are not, where it buys the most. This is how it matches the mean recall of CBS with fewer distance computations, whereas CBS gives every query the same list size.
Beam predictor. We make this reallocation explicit and optimize it. Beam predictor chooses a list size for each query: it first runs a short pilot beam search, extracts features from the nodes it visits and their distances to the query, predicts from these features a list size that reflects how close the query is to convergence, and continues the search with that list size instead of starting over. It is trained to reproduce the list sizes that minimize the total number of distance computations of a batch of queries subject to a target mean recall, an allocation that we compute with a Lagrangian relaxation. Per-query search budgets have been studied before (§ 2); our beam predictor differs from those methods in learning from this cost-optimal allocation.
On three 100-million-point benchmarks from the NeurIPS’21 Billion-Scale ANN Challenge [23], with search done on graphs built with DiskANN’s sorted pruning rule, beam predictor has a lower mean latency than CBS in 14 of the 15 SSD settings that we test, by up to 29.6%, and in the remaining one it is 0.6% slower, within the run-to-run variation. Compared with ABS, it is faster in 11 of the 15 settings, by up to 6.5%, and at most 1.4% slower in the other 4; in memory, it needs 0.0–3.9% fewer distance computations than ABS. On the SSD at 95% recall, its lead over ABS is larger at than at on all three datasets: from to , the speedup of ABS over CBS shrinks from 10.4% to 1.7% on SIFT100M, while that of beam predictor shrinks less, from 14.2% to 7.2%, and at beam predictor is the fastest of the three methods on all three datasets. These gains are in mean latency: beam predictor gives long searches to the queries that it predicts to be hard, and short searches to the queries that it predicts to be easy.
Contributions. In summary, we make the following contributions.
Guarantees for ABS on -reachable graphs. On -reachable graphs, ABS with parameter returns a -approximation for any metric (Theorem 1.1), and on sorted -reachable graphs under it achieves the sharper bound of Theorem 1.2. The bounds are tight, the second where its first term dominates, and they recover those of Indyk and Xu, Gollapudi et al. and Al-Jazzazi et al. as special cases (§ 4).
Beam predictor. A per-query list-size predictor that is trained on the cost-optimal allocation of list sizes for a target mean recall and continues the short pilot search from which it extracts its features instead of restarting the entire search, so that the pilot’s work is reused (§ 5).
Evaluation. An evaluation on three 100-million-point benchmarks, on an SSD-resident index and in memory, both on graphs built with DiskANN’s sorted pruning rule, showing that beam predictor is faster than CBS in 14 of 15 SSD settings (and within the run-to-run variation of it in the other) and faster than ABS in 11 of 15 SSD settings (and at most 1.4% slower in the other 4), with a lead over ABS on the SSD at 95% recall that is larger at than at (§ 6).
Related work
Graph-based search and its theory. Graph-based indices such as HNSW [20], NSG [9] and DiskANN [16] perform strongly in large-scale ANN benchmarks [23, 25], and all three answer queries with beam search under a fixed list size. DiskANN, FreshDiskANN [26] and SPANN [7] serve billion-point datasets from a single machine with an SSD. Early work on graph-based search assumes random or low-dimensional data: Laarhoven [17] derives time-space trade-offs for greedy walks on near-neighbor graphs of random points on the sphere, and Prokhorenkova and Shekhtsov [22] analyze greedy search, shortcut edges and candidate lists when . Without distributional assumptions, Diwan et al. [8] bound how sparse a navigable graph can be, Indyk and Xu [13] prove an approximation guarantee for greedy search on -reachable graphs, Gollapudi et al. [10] extend it to beam search and tighten it on sorted -reachable graphs under , and Al-Jazzazi et al. [1] prove an Algorithm 1 General beam search (adapted from [1])
Figure 1.
Input: Graph , start node , distance function , query , target .
Output: Set of approximate nearest neighbors of .
Initialize two min-priority queues (sorted by distance to ): containing all discovered nodes, containing the not-yet-expanded nodes.
Insert into both and ; set .
while do
top element of .
if termination condition holds then
break.
end if
Pop from .
for do
if then
Insert into and .
end if
end for
end while
Return the top elements of as .
:::
approximation guarantee for ABS on any navigable graph. Our bounds combine the last three results. Other graph constructions come with guarantees for search on them, typically under assumptions on the query or the data, among them MRNG [9], FANNG [11], -MG [21], -CG [18] and LMG [31]; these guarantees concern their own constructions and search procedures, whereas ours concern ABS on (sorted) -reachable graphs.
Adapting the search effort to each query. Queries differ widely in how much search they need; this difficulty has been related to local intrinsic dimensionality [4] and to graph-native measures such as Steiner-hardness [29]. Several methods therefore choose the search effort per query. LAET [19] predicts a termination condition for each query from features collected during the search, and Tao [32] predicts it before the search from static features of the query. DARTH [6] terminates the search once a learned model estimates that the query has reached a declared recall target, PiP [28] terminates it once the improvement of the current nearest neighbors falls below a threshold, and Ada-ef [33] sets the HNSW list size of each query from a statistical model of the similarities between the query and the data. ANNiE [30] runs a preliminary search towards the query and predicts, from the neighborhood it reaches, the cost of answering the query at a given recall target. Beam predictor likewise predicts a per-query list size from a short pilot search, but it learns from the list sizes that minimize the total cost of a batch of queries subject to a target mean recall. This allocation is a multiple-choice knapsack problem, which we solve by Lagrangian relaxation.
Preliminaries
We consider a metric space where is a set of points and is a distance function that satisfies, for all : (i) ; (ii) ; (iii) ; and (iv) the triangle inequality . We are given a dataset of points in , which form the node set of a directed graph , and we let be the out-neighbors of . The definition of -reachable is as follows.
Definition 3.1 (-reachable graph [13 Definition 3.1]). A directed graph is -reachable with if for every pair and , either or there exists such that and .
Informally, from any node there is a local step towards any target whose distance shrinks by a factor of at least .
DiskANN graphs. DiskANN [16] builds its graph with the Vamana algorithm, whose edge selection uses the RobustPrune algorithm described below. Following [13], we distinguish two constructions built on this algorithm. Slow preprocessing prunes each point’s out-edges against all other points, with no degree bound; a naive implementation takes time, and the result is an -reachable graph. Fast preprocessing is Vamana itself: it prunes only the candidates found by greedy search on the partially built graph and caps the out-degree at . It carries no such guarantee. Our guarantees (§ 4) hold for any (sorted) -reachable graph, and in particular for slow-preprocessing graphs. Our experiments use fast-preprocessing graphs, the construction used in practice (parameters in § 6).
Both variants rely on the RobustPrune subroutine (Algorithm 2 of [16]). Given a node , a candidate set , a parameter , and a degree bound , RobustPrune first sorts in increasing distance from , then iterates through the sorted list and adds each to unless some already-accepted satisfies . Slow preprocessing corresponds to calling RobustPrune with and for every .
Because the candidate list is sorted, the certifying neighbor for a non-edge also satisfies . Gollapudi et al. [10] captured this extra structure in the following stronger definition.
Definition 3.2 (Sorted -reachable graph [10]). A directed graph is sorted -reachable with if for every pair and , either or there exists satisfying all three conditions: (1) , (2) , and (3) .
Gollapudi et al. [10] show that the DiskANN RobustPrune construction in fact uses the sorted pruning rule. Sorted -reachability is stronger than -reachability and enables tighter approximation bounds under the metric.
DiskANN uses classical beam search (CBS) for its search procedure (Algorithm 1 of [16]), parameterized by a list size : the algorithm maintains approximate neighbors of and returns the top at termination. Al-Jazzazi et al. [1] defined a new search variant called adaptive beam search (ABS) that differs from CBS in the choice of termination condition; the general skeleton of beam search is given in Algorithm 1.
The two standard termination conditions are:
Classical beam search (CBS): The search terminates when there exist nodes with .
Adaptive beam search (ABS) [1]: The search terminates when there exist nodes with for parameter .
Setting recovers the classical rule, so ABS with is exactly CBS at width .
Theoretical guarantees of adaptive beam search
The proofs of Theorem 1.1 and Theorem 1.2 share one structure, which we present as a single argument. Only one step depends on the metric and on whether the graph is sorted: the bound of Sub-case B1 (Section 4.2.1). For the metric on sorted -reachable graphs, this step is a semidefinite program, whose dual certificate is in Appendix § 9. § 4.4 shows that the bounds are tight.
Throughout this section let , be the starting node for search in Algorithm 1, let denote the ground-truth nearest neighbors of ordered by increasing distance, and let denote the top- items of at termination (see Algorithm 1), also ordered by increasing distance. We assume that the distances , , are pairwise distinct, so that these orders are strict.
Let be the unexpanded set and the expanded set. As each expansion inserts every out-neighbor into , every of an expanded node lies in . The and parameter ranges in both theorems imply , so the statements are non-trivial.
Adaptive beam search (Algorithm 1) terminates in exactly one of two ways: either (i) empties (line 5), or (ii) the termination condition fires (line 7). We treat the two cases separately.
Case A: empties
The argument for this case follows [1]; we give it in full. If the search terminates because is empty, the termination condition never held, so every popped node had all of its out-neighbors inserted into . In particular, contains every node reachable from in . We claim that every node of is reachable from .
Fix an arbitrary target node , and order the remaining nodes in increasing distance from . For every , because we have , so no other node can certify -reachability from to ; hence by Definition 3.1 there must be an edge from to , and is reachable from .
Suppose inductively that is reachable from each of for some . For every we have , so any certifying neighbor for the pair must lie in ; -reachability thus guarantees an edge from into this set, and so is reachable from .
By induction is reachable from every , in particular from . Since was arbitrary, every node in is reachable from , so at termination and ABS returns the exact top- nearest neighbors of . Both theorems therefore hold in this case.
Case B: the termination condition fires
If there is nothing to prove, so pick the smallest index with . For every we have . Since is the point closest to outside and distances are distinct, ; hence , for otherwise would be among the top- items of .
Let be the top element of when the termination condition fires, so that for every . The condition provides nodes of whose distances to are at most . Hence , and
Now let be arbitrary. Then for every , where the first inequality is strict because and distances are distinct, so . Since , this forces . In particular, there is no edge from to , since expanding would have inserted into . Applying -reachability of repeatedly, starting from , therefore gives nodes with such that:
(i) ;
(ii) ;
(iii) for ;
(iv) for ; and,
(v) when is sorted -reachable, additionally .
Informally, the path approaches by a factor of at least per hop.
We have shown that and . Since all out-neighbors of an expanded node are inserted in , it follows that .
Let be the largest index with ; then . As , we have , and by maximality of , the node is not expanded, so . We consider two sub-cases.
Sub-case B1:
Here , so the termination condition gives , and -reachability gives . General metric. Chaining the triangle inequality,
Rearranging,
metric, sorted -reachable . Sorted -reachability adds the constraint . The largest ratio compatible with the three constraints is the value of a semidefinite program over the Gram matrix of , , and , and Appendix A exhibits a dual solution of value . Hence
Sub-case B2: $z^\star\ge 1
Now , so . Iterating -reachability along the chain gives
and since , in particular . This is precisely the structure of Sub-case B1 with replaced by and by . The general-metric argument of Sub-case B1 therefore gives
Assembling the bound
Combining Sub-cases B1 and B2, for every :
where
The simplification in the general case follows from . Thus in both theorems.
Finally, fix . If then and the claim is immediate. If then , so by (1) applied with ,
where the last inequality uses that are sorted by increasing distance from . This completes the proof for both Theorem 1.1 and Theorem 1.2.
Tightness
The bound of Theorem 1.1 is attained exactly, and so is the first term of the bound of Theorem 1.2. Both examples below use , start the search at a node , and let be the complete graph on three nodes with the single edge removed, so that the search reaches the true nearest neighbor of only through .
General metric, -reachable. Place the three nodes and the query on , with the Euclidean metric on (which is also a general metric):
with and . A direct check shows , so is -reachable. Starting from , only is added to the priority queues; since , is not expanded and the search terminates with as its output. The realized ratio is
matching the bound of Theorem 1.1.
, sorted -reachable. Place the three nodes in together with a query:
with and . A direct check shows and , so is sorted -reachable. Starting the search at , is never expanded because , and the algorithm returns . The realized ratio is
matching the first term of the bound of Theorem 1.2.
Beam predictor
The guarantees of § 4 bound the quality of every query’s answer, but they do not say how much search each query needs, and in practice this varies widely: easy queries find their true top- after a few expansions, while hard ones need much larger lists. Beam predictor therefore gives each query its own list size for CBS, chosen to minimize the mean number of distance computations over a batch of queries subject to a target mean recall. It has three parts: an offline allocation that sets the best list size of every training query (§ 5.1), a model that predicts this list size from a short pilot search (§ 5.2), and a search that continues the pilot instead of restarting (§ 5.3).
Cost-optimal allocation
Fix a graph index and a target mean recall , in percent. For a training query , let and be the number of distance computations and the recall@, in percent, of CBS with list size ; one sweep of CBS over a grid of list sizes measures both. The grid contains every integer in and every multiple of 10 in . The best allocation of list sizes to the training queries solves
This is a multiple-choice knapsack problem: every query picks one list size, and the recalls must reach the target at the least total cost.
Reduction to recall levels. Only the recall level each query reaches matters for the constraint. From the sweep we therefore precompute
with if no reaches recall , together with the smallest list size that reaches recall . Instead of Problem (2), we work with
and the target list size of query is . For , recall@K is a whole percentage, and Problem (3) is equivalent to Problem (2). For and 500, recall@K moves in steps of 0.5 and 0.2 points, and Problem (3) counts each query’s recall rounded down to a whole percentage: its allocations still meet the constraint of Problem (2), but they can cost more than the optimum of Problem (2).
Lagrangian relaxation. We solve (3) approximately by putting a price on distance computations. For a fixed price the problem decouples into independent per-query problems,
A higher price lowers the recall each query buys, so we binary-search over for 80 steps and keep the allocation of the largest price whose mean recall still meets . This takes operations: less than two seconds for the 5,000, 5,000 and 14,345 training queries of SIFT100M, DEEP100M and MSSpaceV100M in our NumPy implementation. Because the per-query cost curves need not be convex, the resulting allocation can be suboptimal.
Exact dynamic program. To measure how far the Lagrangian allocation is from optimal, we solve (3) exactly by dynamic programming. Let be the minimum total cost of queries when their recall levels sum to . Then ,
and the optimum of (3) is . Since ranges up to , the DP takes time. We compare the two on 10 random subsets of 100 queries per in-memory setting, small enough for the DP (Table 8). Averaged over the subsets, the Lagrangian’s allocation costs 0.07–0.52% more distance computations than the optimum of (3), and 2.1% more on the worst single subset. At and 500, where the two problems differ, we also solve Problem (2) itself exactly, with the same DP over the number of true neighbors that each query finds instead of whole percentages: on the same subsets, the optimum of (3) costs 0.6–4.8% more than that of (2), and the Lagrangian’s allocation costs 0.6–4.9% more (6.3% on the worst subset). The DP took 0.12–0.20 s per 100-query subset and 14–17 s for 1,000 queries, against 3–6 ms for the Lagrangian on 100 queries.
| Recall | Worst | Lagr. vs DP | |||
| SIFT100M | |||||
| 100 | 90 | 0.63 | 90.00 | 0.41 | +0.20 (max 0.7) |
| 100 | 95 | 0.78 | 94.99 | 0.21 | +0.24 (max 1.0) |
| 200 | 90 | 0.47 | 89.98 | 0.47 | +0.07 (max 0.2) |
| 200 | 95 | 0.80 | 94.97 | 0.23 | +0.11 (max 0.3) |
| 500 | 95 | 0.74 | 95.00 | 0.24 | +0.16 (max 0.3) |
| DEEP100M | |||||
| 100 | 90 | 0.66 | 89.97 | 0.38 | +0.31 (max 1.3) |
| 100 | 95 | 0.77 | 94.94 | 0.26 | +0.18 (max 0.5) |
| 200 | 90 | 0.60 | 89.94 | 0.33 | +0.19 (max 0.7) |
| 200 | 95 | 0.80 | 94.96 | 0.24 | +0.25 (max 0.6) |
| 500 | 95 | 0.66 | 94.97 | 0.19 | +0.09 (max 0.3) |
| MSSpaceV100M | |||||
| 100 | 90 | 0.40 | 90.02 | 0.45 | +0.45 (max 2.1) |
| 100 | 95 | 0.74 | 95.02 | 0.22 | +0.30 (max 1.1) |
| 200 | 90 | 0.33 | 90.04 | 0.40 | +0.24 (max 1.0) |
| 200 | 95 | 0.75 | 95.01 | 0.17 | +0.52 (max 1.5) |
| 500 | 95 | 0.77 | 95.00 | 0.18 | +0.07 (max 0.5) |
Table 8. In-memory search, sorted graph: beam predictor in every setting of Table 4 (mean over 10 random 50/50 query splits). : Spearman correlation between predicted and Lagrangian-optimal list sizes on the test half; Recall: mean test recall (%); Worst: largest on any one split; Lagr. vs DP: excess cost of the Lagrangian over the optimum of Problem (3), computed exactly by DP, on 100-query subsets (%; mean, and largest subset).
Prediction from a pilot search
The targets require the recall of every list size, which is known only for training queries. At query time, beam predictor first runs a pilot search, CBS with list size run to convergence, and summarizes it in six features. Let be the distances of the pilot’s top- results, and let be the sum of the current top- distances recorded after each of the expansion steps of the pilot.
Scale features: , , and the mean and standard deviation of .
Trajectory features: sdp , the percentage drop of the top- distance sum, and c90, the number of distance computations after which first falls below .
The scale features describe the distances of the query’s current neighbors; is the quantity in ABS’s stopping rule. The trajectory features describe how quickly the sum of these distances fell during the pilot, which indicates how close the search is to convergence.
Model and calibration. We fit by linear regression on the six features , weighting query by so that queries with large targets, which dominate the cost, are fit more closely:
A single scale factor calibrates the predictions,
where is the smallest value in for which the training queries reach mean recall . The model, its calibration and the Lagrangian targets use only the training queries.
Continuing the pilot
We implement beam predictor inside DiskANN’s in-memory and SSD search loops. A trained model is a 60-byte file holding , the pilot’s list size, the clipping range, , and . As in DiskANN, each query runs on a single thread and different threads serve different queries, so the per-query list sizes need no coordination between threads. The pilot and the main search are one execution of the search loop, in three phases.
Pilot. The search starts as CBS with list size , so its sorted candidate list always holds the best candidates found so far. In addition, every newly discovered candidate is appended with its distance to a temporary per-query buffer, so the candidates that the list evicts, or never admits, are kept. After every expansion step (for in-memory search, one node; on the SSD, one batch of up to reads) the search records the sum of the current top- distances and the number of distance computations so far, the trajectory behind sdp and c90.
Prediction. The pilot has converged when no candidate in the list is unexpanded. The search then reads off the list (on the SSD as well, the distances are already in the list, so no extra I/O is needed), computes the six features in time and evaluates : six multiply-adds, one exponential and the clipping.
Extension. The search re-inserts the best buffered candidates that are not in the list and continues with list size . For example, with and , the 320 best candidates outside the list are appended to it and the search continues with list size 420; if , the pilot’s result is returned. Since the list holds the best candidates discovered so far ( unless fewer were found), which are also the smallest entries of the buffer, the next are found without sorting the buffer: at position moves the list’s entries to the front, a second call at position moves the next candidates into positions to , and only those entries are sorted. They are appended to the list as unexpanded, its capacity is raised to , and the loop resumes with the same visited set until all entries are expanded. The overhead is one append per distance computation during the pilot and work at the transition.
Alternative without a buffer. We also implemented a variant in which the pilot’s list keeps up to candidates in sorted order, the pilot stops once the first are expanded, and after the prediction the list is truncated to before the search continues. Its recall and distance computations were essentially the same as the buffered implementation’s, but it was slower, because its list holds up to entries for the whole pilot and every insertion into a sorted array moves all entries behind the insertion point. All our experiments use the buffered implementation.
Exactness of the continuation. For in-memory search, the continuation reproduces the CBS search at . In two settings that we checked query by query (SIFT100M, sorted graph, and 500, ), every query whose lies on the sweep grid reached the same recall and used exactly the same number of distance computations as in the sweep. The mean cost estimated from the sweep. differs from the measured one by at most 0.20%, mainly because, above , the sweep advances in steps of 10 and the estimate rounds up. The recall reported in the tables differs from the estimate by at most 0.06 points, owing to the same rounding and to DiskANN also counting as correct the results tied in distance with the -th neighbor, whereas the per-query tables count only the first ground-truth ids.
Experiments
We now evaluate beam predictor against CBS and ABS. After the experimental setup (§ 6.1), the evaluation has three parts. First, we check whether recall moves with the relaxation parameter and the pruning order in the direction that the bounds of Theorem 1.1 and Theorem 1.2 suggest, although our graphs are not known to satisfy their hypotheses (§ 6.2). Second, we compare beam predictor with CBS and ABS at equal recall (§ 6.3): query latency and SSD reads on an SSD-resident index, distance computations for in-memory search, and how the comparison changes as grows. Third, we analyze beam predictor itself (§ 6.4): how closely its predicted list sizes follow the optimal ones, how well its calibration carries over to unseen queries, how much each group of features contributes to its savings, and how the Lagrangian targets compare with the exact optimum.
Setup
Datasets. We use three benchmarks from the NeurIPS’21 Billion-Scale ANN Challenge [23] (Table 1): SIFT100M, DEEP100M and MSSpaceV100M, 100-million-point slices of SIFT1B, DEEP1B and SpaceV1B. The MSSpaceV query set contains 626 exact duplicates among its 29,316 queries; we remove them, leaving 28,690 unique queries. Each query set is split once at random (seed 42) into two halves, of 5,000 queries each for SIFT100M and DEEP100M and 14,345 each for MSSpaceV100M: beam predictor is trained on the first, and all results are reported on the second. The analysis in § 6.4 repeats the split 10 times.
| Dataset | Points | Dim | Type | Queries | Metric |
| SIFT100M | 100,000,000 | 128 | uint8 | 10,000 | |
| DEEP100M | 100,000,000 | 96 | float32 | 10,000 | |
| MSSpaceV100M | 100,000,000 | 100 | int8 | 28,690 |
Table 1. NeurIPS’21 Big-ANN datasets used in our experiments.
Hardware. All experiments ran on a server with two Intel Xeon Platinum 8160 CPUs (48 cores, 96 threads), 512 GB of RAM and a 3.2 TB Dell PM1725a NVMe SSD that stores the SSD indices.
Indices. All graphs are built with DiskANN’s Vamana algorithm [16], i.e., with fast preprocessing (§ 3), with maximum out-degree and build list size . DiskANN’s pruning parameter is set to . DiskANN sorts the candidate list before pruning, the rule that makes slow-preprocessing graphs sorted -reachable (§ 3); we call the graph it builds the sorted graph and evaluate search on it, in memory and on the SSD. Like other fast-preprocessing graphs, it is not known to be -reachable, so our guarantees do not apply to it. The SSD index stores each node’s vector and neighbor list on the SSD; we build it by writing the in-memory graph in DiskANN’s SSD layout, so in-memory and SSD search traverse the same graph. For the theory validation (§ 6.2) we also build, with the same parameters, a shuffled graph, which permutes the candidate list at random before pruning; with slow preprocessing, this rule yields graphs that are -reachable but not necessarily sorted -reachable. As in DiskANN, the SSD search computes the distances of the neighbors of each node it expands from compressed codes kept in RAM, one byte per dimension, and ranks its results by full-precision distance; the codes are nearly lossless: on a sample of 100,000 vectors, their relative reconstruction error (the Frobenius norm of the error divided by that of the vectors’ deviation from their mean) is below 1% on all three datasets. On the SSD index, the cost dist_cmps in Problem (2) is DiskANN’s per-query counter of distance computations, which adds the number of neighbors of every expanded node and adds one more for each newly discovered neighbor of a node read from the SSD; it is thus a proxy for the work of the search rather than an exact count. of distance computations. SSD searches use [24], i.e., they read up to 4 nodes from the SSD per step; they keep 10,000 nodes cached in RAM, read the SSD with direct I/O (bypassing the page cache) and run on a single thread, and every operating point is timed 5 times.
Search variants. We compare three procedures. CBS uses the same list size for every query, ABS [1] the same relaxation parameter , and beam predictor (§ 5) a list size predicted for each query by a model trained on the training half.
Beam predictor configuration. Table 2 lists, for each , the list size of the pilot search, the grid of list sizes swept on the training queries to build the per-query tables of § 5.1, the range to which predictions are clipped, and the target recalls. The grid has 901 values for every : step 1 up to 1000 and step 10 above. One sweep serves every of a dataset. The traversal of CBS depends only on ; only decides how many of the final, sorted results are returned. We therefore search each in the union of the grids of Table 2 once, return the top results, where is the largest studied not exceeding , and read recall@ for every off the same result list; we checked that this reproduces separate per- sweeps exactly. On the SSD index the sweep runs the same search code with the index file in the page cache and many threads; its outputs are identical to direct-I/O runs, and only the timed runs use direct I/O on a single thread. This sweep is the main offline cost of beam predictor: run once for all three and all queries, although training uses only the training half, it took 1.7 h for SIFT100M, 1.8 h for DEEP100M and 3.4 h for MSSpaceV100M on our server. Computing the targets and fitting and calibrating the model then take less than two seconds per setting. Neither cost is included in the latencies we report, which do include the pilot search, the computation of the features and the prediction.
| Pilot | Sweep grid | (%) | ||
| 100 | 100 | 100, 101, , 1000 | 901 | 90, 95 |
| 200 | 200 | 200, , 1000, 1010, , 2000 | 901 | 90, 95 |
| 500 | 500 | 500, , 1000, 1010, , 5000 | 901 | 95 |
Table 2. Beam predictor configuration for each . Pilot: list size of the pilot search; : list sizes swept on the training queries; predictions are clipped to .
Other per-query methods. We do not compare beam predictor experimentally with the per-query methods of § 2, so we make no claim about how it performs relative to them. Their objectives differ from ours: several aim for every query to reach a declared recall target [6, 30, 33], whereas beam predictor minimizes the total cost of a batch of queries at a target mean recall. They were also designed and evaluated for in-memory indices such as HNSW or partition-based (IVF) indices, whereas our evaluation centers on DiskANN graphs and their SSD search. A comparison under a common objective is left for future work.
Protocol. For each dataset, number of neighbors (the of § 3) and target mean recall , we train beam predictor on the training half and measure its mean recall@ on the test half. We then set the of CBS and the of ABS so that their test recall matches the predictor’s to within 0.05 percentage points, and compare cost at that recall. To find these values, we evaluate CBS on the test half at and ABS at , then repeatedly subdivide the interval that brackets the predictor’s test recall, extending the range when needed, until a value is within 0.05 percentage points of it; is an integer and has four decimals. The baselines are thus tuned on the test queries themselves. We use for and for ; at , CBS at its smallest list size already exceeds 90% recall on SIFT100M. On the SSD we report mean query latency and mean SSD reads (I/Os) per query; for in-memory search we report mean distance computations per query, one per newly discovered node.
Theory validation: gamma and the pruning order
Theorem 1.1 and Theorem 1.2 bound the worst-case approximation ratio on -reachable and sorted -reachable graphs: the bound shrinks monotonically in and is smaller for sorted -reachable graphs under . Our graphs are built with fast preprocessing and are not known to satisfy either definition, and we measure recall rather than the worst-case ratio, so this experiment does not test the theorems; it only checks whether recall moves in the direction the bounds suggest. We ran ABS with and on the sorted and the shuffled graph and measured recall@100. Figure 1 shows that on all three datasets recall@100 rises monotonically with on both graphs, and that the sorted graph reaches a higher recall than the shuffled graph at every .
Figure 1. Recall@100 of ABS versus the relaxation parameter on the three datasets, for the sorted graph and the shuffled graph (§ 6.1), both built with DiskANN (, ), over all queries of each dataset.
Comparison with CBS and ABS
We compare beam predictor with CBS and ABS on the SSD index and for in-memory search, both on the sorted graph.
SSD results. Table 3 reports latency and SSD reads. Beam predictor has a lower mean latency than CBS in 14 of the 15 settings: by 2.6–29.6% in 13 of them. Its mean latency is lower than that of ABS in 11 settings, by up to 6.5%, including all nine settings at . In the other four settings, all at , it is slower than ABS by at most 1.4%. It issues fewer SSD reads than CBS in every setting and fewer than ABS in 12. At the gains are small because very little search is left to reallocate: at , CBS with its smallest list size already reaches 88.9% recall on both SIFT100M and MSSpaceV100M.
| Latency (ms) | I/Os per query | (%) | (%) | (%) | |||||||||
| CBS | ABS | BP | CBS | ABS | BP | Lat. | I/Os | Lat. | I/Os | Lat. | I/Os | ||
| \multicolumn{14}{l}{SIFT100M} | |||||||||||||
| 100 | 90 | 170.5 | 163.0 | 159.6 | |||||||||
| 100 | 95 | 305.0 | 269.9 | 261.0 | |||||||||
| 200 | 90 | 232.7 | 231.1 | 229.2 | |||||||||
| 200 | 95 | 421.3 | 387.9 | 360.8 | |||||||||
| 500 | 95 | 667.3 | 646.3 | 609.0 | |||||||||
| \multicolumn{14}{l}{DEEP100M} | |||||||||||||
| 100 | 90 | 205.2 | 192.0 | 190.5 | |||||||||
| 100 | 95 | 397.5 | 335.9 | 335.9 | |||||||||
| 200 | 90 | 280.3 | 272.8 | 268.1 | |||||||||
| 200 | 95 | 540.8 | 476.5 | 464.7 | |||||||||
| 500 | 95 | 851.7 | 793.2 | 754.0 | |||||||||
| \multicolumn{14}{l}{MSSpaceV100M} | |||||||||||||
| 100 | 90 | 159.3 | 147.2 | 150.6 | |||||||||
| 100 | 95 | 448.3 | 322.1 | 312.1 | |||||||||
| 200 | 90 | 247.3 | 238.9 | 241.1 | |||||||||
| 200 | 95 | 662.9 | 515.8 | 495.5 | |||||||||
| 500 | 95 | 1,309.1 | 1,084.6 | 1,039.4 |
Table 3. SSD index, sorted graph: beam predictor (BP) versus CBS and ABS in mean query latency in ms (mean std. dev. over 5 runs) and mean SSD reads (I/Os) per query at matched mean recall@ on the test half. is the target recall (%); the of CBS and the of ABS are chosen so that their recall matches that of beam predictor within 0.05 percentage points. The last six columns give relative changes (%) in latency (Lat.) and I/Os: , and ; negative values mean that BP, or ABS for , is cheaper. Bold marks the lowest latency and the lowest I/Os in each row. Single search thread, , direct I/O.
The latencies of beam predictor include the pilot search, the computation of the features and the prediction. Its gains are in mean latency: because for the queries that it predicts to be hard, it allocates list sizes of up to , its 99.9th-percentile latency, averaged over the five runs, is higher than that of CBS in 13 of the 15 settings, by up to a factor of 2.1, and higher than that of ABS in 9. ABS has the heaviest tail on MSSpaceV100M, where at its 99.9th-percentile latency is up to 2.3 times that of beam predictor. Table 9 in Appendix B lists these latencies, together with the median and standard deviation of per-query recall. At matched mean recall, the per-query recall of beam predictor has a lower standard deviation than that of CBS in all 15 settings and than that of ABS in 13, and a median at most 2 points below that of CBS, so its per-query recall is more concentrated around the mean.
| 99.9th-pct. latency | Median recall | Std of recall | ||||||||
| CBS | ABS | BP | CBS | ABS | BP | CBS | ABS | BP | ||
| SIFT100M | ||||||||||
| 100 | 90 | 12.6 | 13.3 | 16.8 | 94.0 | 93.0 | 92.0 | 10.8 | 10.2 | 9.1 |
| 100 | 95 | 17.4 | 29.4 | 36.7 | 98.0 | 97.0 | 97.0 | 6.9 | 6.1 | 5.2 |
| 200 | 90 | 20.6 | 19.8 | 20.4 | 93.0 | 93.0 | 93.0 | 10.0 | 9.9 | 9.6 |
| 200 | 95 | 29.3 | 33.8 | 46.4 | 97.5 | 97.0 | 96.5 | 6.4 | 5.8 | 4.7 |
| 500 | 95 | 41.2 | 44.2 | 65.8 | 97.2 | 97.0 | 96.4 | 5.9 | 5.7 | 4.8 |
| DEEP100M | ||||||||||
| 100 | 90 | 13.4 | 17.0 | 17.7 | 94.0 | 94.0 | 93.0 | 11.8 | 11.1 | 10.4 |
| 100 | 95 | 24.7 | 35.6 | 40.5 | 98.0 | 98.0 | 97.0 | 7.7 | 6.8 | 6.3 |
| 200 | 90 | 23.5 | 25.5 | 22.9 | 93.5 | 93.5 | 93.0 | 11.0 | 10.7 | 10.1 |
| 200 | 95 | 35.5 | 41.9 | 58.9 | 98.0 | 97.5 | 97.0 | 7.2 | 6.5 | 5.9 |
| 500 | 95 | 82.0 | 58.9 | 94.5 | 97.6 | 97.2 | 96.6 | 6.7 | 6.3 | 5.3 |
| MSSpaceV100M | ||||||||||
| 100 | 90 | 15.1 | 17.6 | 16.3 | 96.0 | 96.0 | 96.0 | 15.8 | 15.1 | 15.3 |
| 100 | 95 | 33.2 | 122.2 | 52.5 | 99.0 | 98.0 | 98.0 | 9.5 | 8.4 | 8.1 |
| 200 | 90 | 20.0 | 21.5 | 20.2 | 95.5 | 95.0 | 95.0 | 13.8 | 13.5 | 13.5 |
| 200 | 95 | 44.7 | 136.2 | 82.9 | 98.5 | 98.0 | 97.5 | 8.5 | 7.6 | 7.2 |
| 500 | 95 | 95.5 | 265.8 | 163.4 | 98.2 | 97.6 | 97.4 | 7.8 | 6.9 | 6.5 |
Table 9. SSD index, sorted graph, same runs and matched settings as Table 3: 99.9th-percentile latency (ms, mean over the five runs), and median and standard deviation (Std) of per-query recall@ (%) over the test queries. BP: beam predictor.
In-memory results. Table 4 reports distance computations for in-memory search on the sorted graph. Beam predictor needs fewer distance computations than CBS in every setting, up to 23.7% fewer, and no more than ABS: between 0.0% and 3.9% fewer.
| Mean dist_cmps | Relative change (%) | |||||||
| CBS | ABS | BP | ||||||
| SIFT100M | ||||||||
| 100 | 90 | 4,031 | 3,909 | 3,839 | −4.8 | −1.8 | −3.0 | |
| 100 | 95 | 6,786 | 6,237 | 6,096 | −10.2 | −2.3 | −8.1 | |
| 200 | 90 | 5,324 | 5,289 | 5,253 | −1.3 | −0.7 | −0.7 | |
| 200 | 95 | 8,934 | 8,482 | 8,153 | −8.7 | −3.9 | −5.1 | |
| 500 | 95 | 13,462 | 13,231 | 12,734 | −5.4 | −3.8 | −1.7 | |
| DEEP100M | ||||||||
| 100 | 90 | 4,594 | 4,390 | 4,373 | −4.8 | −0.4 | −4.4 | |
| 100 | 95 | 8,203 | 7,358 | 7,348 | −10.4 | −0.1 | −10.3 | |
| 200 | 90 | 6,018 | 5,931 | 5,879 | −2.3 | −0.9 | −1.4 | |
| 200 | 95 | 10,668 | 9,872 | 9,792 | −8.2 | −0.8 | −7.5 | |
| 500 | 95 | 15,808 | 15,262 | 14,972 | −5.3 | −1.9 | −3.5 | |
| MSSpaceV100M | ||||||||
| 100 | 90 | 3,162 | 2,962 | 2,961 | −6.4 | −0.0 | −6.3 | |
| 100 | 95 | 7,777 | 6,096 | 5,937 | −23.7 | −2.6 | −21.6 | |
| 200 | 90 | 4,569 | 4,480 | 4,480 | −2.0 | −0.0 | −2.0 | |
| 200 | 95 | 11,440 | 9,295 | 9,105 | −20.4 | −2.1 | −18.7 | |
| 500 | 95 | 21,134 | 18,089 | 17,983 | −14.9 | −0.6 | −14.4 |
Table 4. In-memory search, sorted graph: mean distance computations per query at matched mean recall@K on the test half. BP: beam predictor; , recall matching, the relative changes (%) and bold as in Table 3.
Effect of . Al-Jazzazi et al. [1, App. C.1] observe that on navigable graphs ABS gains less over CBS at than at and 10. The columns of Table 3 and Table 4 show that this trend continues for : at , the saving of ABS over CBS shrinks as grows on every dataset, on the SSD and in memory. For instance, on the SSD index ABS is 10.4%, 7.4% and 1.7% faster than CBS on SIFT100M at , 200 and 500. Beam predictor keeps more of its saving: it is 14.2%, 13.4% and 7.2% faster than CBS. On the SSD, its lead over ABS at is therefore larger at than at on every dataset: it grows from 0.8% to 5.2% on DEEP100M and from 1.8% to 4.6% on MSSpaceV100M, and only slightly, from 4.2% to 5.6%, on SIFT100M. At beam predictor has the lowest latency and the fewest SSD reads on all three datasets. In memory, its saving over ABS at is 3.8% on SIFT100M, 1.9% on DEEP100M and 0.6% on MSSpaceV100M.
Analysis of beam predictor
We analyze the predictor on the in-memory sorted graph with , over 10 random 50/50 splits of the queries (Table 5), and then at and 500. To compare many variants we compute each one’s cost from the per-query CBS sweep instead of running the search; for beam predictor itself, the cost measured online matched this estimate to within 0.20% in every in-memory setting (§ 5.3).
Table 5: Analysis of beam predictor on the in-memory sorted graph (), averaged over 10 random 50/50 splits of the queries into a training and a test half. In the cost rows, negative values mean fewer distance computations than CBS, the indented rows retrain beam predictor with fewer features, and the scale factor of every variant is tuned on the test half so that all variants are compared at the same test recall.
| SIFT100M | DEEP100M | MSSpaceV100M | ||||
| Target recall (%) | 90 | 95 | 90 | 95 | 90 | 95 |
| Spearman’s of vs. | ||||||
| training half | 0.63 | 0.78 | 0.67 | 0.77 | 0.41 | 0.74 |
| test half | 0.63 | 0.78 | 0.66 | 0.77 | 0.40 | 0.74 |
| Calibration: test recall (%) | ||||||
| mean over splits | 90.00 | 94.99 | 89.97 | 94.94 | 90.02 | 95.02 |
| worst split, | 0.41 | 0.21 | 0.38 | 0.26 | 0.45 | 0.22 |
| Cost vs. CBS at equal recall (%) | ||||||
| beam predictor | −4.8 | −10.0 | −4.7 | −10.3 | −6.8 | −23.7 |
| no trajectory features | −4.5 | −9.4 | −4.3 | −9.1 | −6.5 | −22.1 |
| trajectory features only | −4.1 | −8.6 | −3.3 | −7.5 | −5.8 | −21.2 |
| only | −3.1 | −6.4 | −1.9 | −4.6 | −4.5 | −14.6 |
| Lagrangian vs. exact DP: excess cost (%) | ||||||
| 100-query subsets | +0.20 | +0.24 | +0.31 | +0.18 | +0.45 | +0.30 |
Table 5.
Prediction accuracy. On the training half, the predicted list sizes rank the queries similarly to the Lagrangian-optimal : Spearman’s rank correlation is 0.63 and 0.78 on SIFT100M, 0.67 and 0.77 on DEEP100M, and 0.41 and 0.74 on MSSpaceV100M, at and 95%. On the test half, the correlation is within 0.003 of these values in every setting, so the linear model does not overfit.
Calibration. With the scale factor tuned on the training half, the test recall averaged over the 10 splits is within 0.06 percentage points of in all six settings, and within 0.45 points on every individual split.
Components. The cost rows of Table 5 give the cost of each variant relative to CBS at the same test recall; to compare the variants at equal recall, the scale factor of each one, including the full beam predictor, is tuned on the test half rather than the training half. The trajectory features add 0.3–1.6 points of saving over the distance features alone, and each group alone recovers most of the saving. The largest top- distance , the quantity in ABS’s stopping rule, recovers 40–66% of it on its own, the least of all variants.
Lagrangian versus exact optimization. The allocation problem that defines the targets can be solved exactly by dynamic programming, but the DP’s running time grows quadratically with the number of queries (§ 5.1): at , it takes 0.12–0.19 s for 100 queries and 14–16 s for 1,000. The Lagrangian takes less than two seconds on a full training half, and on 100-query subsets, where the DP is cheap, its allocation costs on average 0.18–0.45% more distance computations than the optimum.
Feature significance. Table 6 gives the -value of each feature in the weighted regression at every and . The trajectory feature c90 gains weight as grows: for example, at , its -value rises from 6.2 to 19.4 to 34.1 on SIFT100M. Because the features are correlated, a -value measures a feature’s contribution given the others; Table 7 measures the effect of removing feature groups on cost.
| mean | std | sdp | c90 | ||||
| SIFT100M | |||||||
| 100 | 90 | 2.8 | −12.4 | 13.4 | 2.8 | −10.8 | 6.0 |
| 100 | 95 | 1.0 | −15.2 | 16.8 | 2.2 | −16.6 | 6.2 |
| 200 | 90 | 2.9 | −7.0 | 7.5 | 1.6 | −3.4 | 6.5 |
| 200 | 95 | 2.9 | −15.3 | 16.6 | 3.9 | −9.9 | 19.4 |
| 500 | 95 | 0.7 | −8.2 | 8.9 | 1.9 | 4.4 | 34.1 |
| DEEP100M | |||||||
| 100 | 90 | 5.4 | −17.9 | 18.9 | 7.3 | −10.2 | 5.2 |
| 100 | 95 | 4.9 | −22.6 | 24.1 | 9.5 | −16.0 | 7.0 |
| 200 | 90 | 4.3 | −14.1 | 14.9 | 5.8 | 2.9 | 16.2 |
| 200 | 95 | 3.5 | −24.3 | 26.0 | 9.4 | −2.6 | 18.1 |
| 500 | 95 | 0.2 | −13.5 | 15.0 | 2.5 | 25.9 | 40.4 |
| MSSpaceV100M | |||||||
| 100 | 90 | 4.8 | −0.8 | 1.8 | −3.2 | −17.0 | −12.1 |
| 100 | 95 | 6.7 | −23.9 | 26.6 | 8.3 | −40.8 | −2.4 |
| 200 | 90 | 5.1 | 1.9 | −1.0 | −4.2 | −10.8 | −5.6 |
| 200 | 95 | 10.4 | −29.1 | 31.4 | 12.6 | −47.6 | 8.2 |
| 500 | 95 | 10.4 | −37.4 | 40.9 | 16.4 | −27.0 | 37.1 |
Table 6. -values of the six features in the weighted regression on (in-memory sorted graph, mean over 10 random 50/50 query splits).
| BP | no traj. | traj. | |||
| SIFT100M | |||||
| 100 | 90 | −4.8 | −4.5 | −4.1 | −3.1 |
| 100 | 95 | −10.0 | −9.4 | −8.6 | −6.4 |
| 200 | 90 | −1.4 | −1.3 | −1.0 | −0.7 |
| 200 | 95 | −8.5 | −8.2 | −7.3 | −5.2 |
| 500 | 95 | −5.2 | −4.7 | −4.8 | −2.7 |
| DEEP100M | |||||
| 100 | 90 | −4.7 | −4.3 | −3.3 | −1.9 |
| 100 | 95 | −10.3 | −9.1 | −7.5 | −4.6 |
| 200 | 90 | −2.5 | −2.3 | −1.8 | −1.0 |
| 200 | 95 | −8.9 | −8.1 | −6.6 | −4.3 |
| 500 | 95 | −5.7 | −5.1 | −4.5 | −2.3 |
| MSSpaceV100M | |||||
| 100 | 90 | −6.8 | −6.5 | −5.8 | −4.5 |
| 100 | 95 | −23.7 | −22.1 | −21.2 | −14.6 |
| 200 | 90 | −2.3 | −2.1 | −1.8 | −1.4 |
| 200 | 95 | −19.3 | −17.3 | −16.8 | −9.9 |
| 500 | 95 | −15.0 | −13.7 | −12.1 | −6.2 |
Table 7. Mean distance computations relative to CBS at the same test recall (%; scale factor of each variant tuned on the test half), in-memory sorted graph, mean over 10 random 50/50 query splits. BP: beam predictor; no traj.: without the trajectory features; traj.: trajectory features only; : only.
Larger . The conclusions hold at and 500 (Table 8, Table 6 and Table 7). The mean test recall is within 0.06 points of , and within 0.47 points on every single split; the training and test correlations differ by at most 0.011, and the Lagrangian is on average within 0.52% of the exact optimum of (3). The correlation is 0.66–0.80 at , and lower at and : 0.47 on SIFT100M, 0.60 on DEEP100M and 0.33 on MSSpaceV100M, the settings in which beam predictor also saves the least over CBS (1.4%, 2.5% and 2.3%).
Conclusion
We studied adaptive beam search (ABS) on -reachable graphs, which include the graphs built by DiskANN’s slow preprocessing. On -reachable graphs, ABS with parameter returns neighbors within a factor of the true ones for any metric, and on sorted -reachable graphs under the metric the factor improves to . These bounds unify and generalize those of Indyk and Xu [13], Gollapudi et al. [10] and Al-Jazzazi et al. [1], which they recover as special cases, and the general-metric bound is tight. On three 100-million-point benchmarks, with graphs built by DiskANN’s fast preprocessing, which the bounds do not cover, the recall of ABS rises with , and the graph built with sorted pruning reaches a higher recall than the one built with shuffled pruning at every , in the direction that the bounds suggest.
Motivated by how ABS adapts its effort to each query, we designed beam predictor, which predicts a list size for each query from features of a short pilot search and is trained on the list sizes that minimize the total number of distance computations at a target mean recall. On the same benchmarks, with search on graphs built with DiskANN’s sorted pruning rule, beam predictor lowers mean query latency on SSD-resident indices at matched recall by up to 29.6% relative to classical beam search (CBS). Relative to ABS, it is faster in 11 of 15 settings, by up to 6.5%, and at most 1.4% slower in the other 4; at 95% recall, its advantage over ABS on the SSD grows from 0.8–4.2% for to 4.6–5.6% for . In memory, it needs 1.3–23.7% fewer distance computations than CBS and 0.0–3.9% fewer than ABS.
Limitations. Our guarantees hold for -reachable and sorted -reachable graphs, such as those built by DiskANN’s slow preprocessing, whose naive construction takes time. The fast-preprocessing graphs used in practice and in our experiments, as well as HNSW and NSG graphs, are not known to satisfy these conditions, so the bounds do not transfer to them, and our experiments illustrate the bounds rather than test them. The bounds also concern the quality of the returned neighbors, not the running time of ABS.
Beam predictor needs an offline sweep of CBS over training queries and a target recall chosen in advance. Its gains are in mean latency; its tail latency is usually higher than that of CBS. We compare it only with CBS and ABS, not with other per-query methods (§ 6.1), and our evaluation covers three datasets of 100 million points.
Future work. Evaluating beam predictor on more datasets, distance functions and values of , and comparing it with other per-query methods, are natural next steps. A predictor that works for out-of-distribution queries is also a natural direction to work on. On the theoretical side, the second term of the approximation constant of Theorem 1.2 is not known to be tight, so finding a tight bound is a natural research direction.
Acknowledgments
We used AI assistants to help write code, analysis scripts and parts of the text, and to check the reported numbers against our experimental data. The authors reviewed and verified all content and take full responsibility for it.
Semidefinite program of Sub-case B1
This appendix proves the bound of Sub-case B1 (Section 4.2.1) for the metric on sorted -reachable graphs, .
Sorted -reachability adds the constraint , giving the optimization
The objective and constraints depend only on ratios of , so the problem is invariant under positive scaling. Without loss of generality fix , which we further relax to (any feasible solution with can be rescaled to increase the objective while preserving the constraints). The optimization becomes
For Euclidean metric and squaring the terms of the optimization problem, we obtain a semi-definite program:
Let the Gram matrix . For brevity set , , and .
SDP primal.
SDP dual.
where
the four primal constraint matrices and their right-hand sides are
Substituting the ’s, the dual feasibility constraint is equivalent to
Dual certificate. We exhibit a dual-feasible point:
All four values are positive in the parameter range that is relevant here. Substituting gives
Setting
one verifies by direct computation that ; hence and the chosen is dual-feasible. By weak duality,
and taking square roots recovers the bound claimed in Sub-case B1 (Section 4.2.1).
Tail latency and per-query recall
Table 9 complements Table 3. For the same runs and the same matched settings of CBS and ABS, it gives the 99.9th-percentile latency of each method, averaged over the five runs, and the median and standard deviation of per-query recall@ over the test queries, which are the same in every run.
References
- [1]Yousef Al-Jazzazi, Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. Distance adaptive beam search for provably accurate graph-based nearest neighbor search. In Advances in Neural Information Processing Systems 38 (NeurIPS 2025), pages 110958–110987, 2025. Extended version: arXiv:2505.15636.
- [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]Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Y Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6):891–923, 1998.
- [4]Martin Aumüller and Matteo Ceccarello. The role of local intrinsic dimensionality in benchmarking nearest neighbor search. In Similarity Search and Applications: 12th International Conference, SISAP 2019, Newark, NJ, USA, October 2–4, 2019, Proceedings, page 113–127, Berlin, Heidelberg, 2019. Springer-Verlag. ISBN 978-3-030-32046-1. doi: 10.1007/978-3-030-32047-8_11. URL https://doi.org/10.1007/978-3-030-32047-8_11.
- [5]Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd International Conference on Machine Learning, ICML ’06, page 97–104, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933832. doi: 10.1145/1143844.1143857. URL https://doi.org/10.1145/1143844.1143857.
- [6]Manos Chatzakis, Yannis Papakonstantinou, and Themis Palpanas. Darth: Declarative recall through early termination for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 3(4):1–26, 2025. ISSN 2836-6573. doi: 10.1145/3749160. URL http://dx.doi.org/10.1145/3749160.
- [7]Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. Spann: Highly-efficient billion-scale approximate nearest neighborhood search. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 5199–5212. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper_files/paper/2021/file/299dc35e747eb7717d9cea10a802da2-Paper.pdf.DOI
- [8]Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, and Torsten Suel. Navigable graphs for high-dimensional nearest neighbor search: Constructions and limits. In Advances in Neural Information Processing Systems 37 (NeurIPS 2024), pages 59513–59531, 2024.arxiv.org/abs/2405.18680
- [9]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.arxiv.org/abs/1707.00143
- [10]Siddharth Gollapudi, Ravishankar Krishnaswamy, Kirankumar Shiragur, and Harsh Wardhan. Sort before you prune: Improved worst-case guarantees of the diskANN family of graphs. In Forty-second International Conference on Machine Learning, 2025. URL https://openreview.net/forum?id=JnXbUKtLzz.
- [11]Ben Harwood and Tom Drummond. FANNG: Fast approximate nearest neighbour graphs. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5713–5722, 2016. doi: 10.1109/CVPR.2016.616.DOI
- [12]Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pages 604–613, 1998.
- [13]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 (NeurIPS 2023), pages 66239–66256, 2023. Extended version: arXiv:2310.19126.arxiv.org/abs/2310.19126
- [14]Masajiro Iwasaki. NGT: Neighborhood graph and tree for indexing high-dimensional data. https://github.com/NGT-labs/NGT, 2015.
- [15]Masajiro Iwasaki and Daisuke Miyazaki. Optimization of indexing based on k-nearest neighbor graph for proximity search, 2018. URL https://arxiv.org/abs/1810.07355.
- [16]Suhas Jayaram Subramanya, Fnu Devrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi. Diskann: Fast accurate billion-point nearest neighbor search on a single node. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper_files/paper/2019/file/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Paper.pdf.
- [17]Thijs Laarhoven. Graph-based time-space trade-offs for approximate near neighbors. arXiv preprint arXiv:1712.03158, 2017.DOI
- [18]Binhong Li, Xiao Yan, and Shangqi Lu. Fast-convergent proximity graphs for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 4(1), 2026. doi: 10.1145/3786650.DOI
- [19]Conglong Li, Minjia Zhang, David G. Andersen, and Yuxiong He. Improving approximate nearest neighbor search through learned adaptive early termination. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 2539–2554, 2020.DOI
- [20]Yury A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4):824–836, 2020.
- [21]Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. Efficient approximate nearest neighbor search in multi-dimensional databases. Proceedings of the ACM on Management of Data, 1(1), 2023. doi: 10.1145/3588908.DOI
- [22]Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based nearest neighbor search: From practice to theory. In International Conference on Machine Learning, pages 7803–7813. PMLR, 2020.arxiv.org/abs/1907.00845
- [23]Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang. Results of the NeurIPS’21 challenge on billion-scale approximate nearest neighbor search. In Proceedings of the NeurIPS 2021 Competitions and Demonstrations Track, 2022.arxiv.org/abs/2205.03763
- [24]Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, Andrija Antonijevic, Dax Pryce, David Kaczynski, Shane Williams, Siddarth Gollapudi, Varun Sivashankar, Neel Karia, Aditi Singh, Shikhar Jaiswal, Neelam Mahapatro, Philip Adams, Bryan Tower, and Yash Patel. Diskann: Graph-structured indices for scalable, fast, fresh and filtered approximate nearest neighbor search, 2023. URL https://github.com/Microsoft/DiskANN.
- [25]Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, et al. Results of the big ann: Neurips’23 competition. arXiv preprint arXiv:2409.17424, 2024.arxiv.org/abs/2409.17424
- [26]Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. Freshdiskann: A fast and accurate graph-based ANN index for streaming similarity search. CoRR, abs/2105.09613, 2021. URL https://arxiv.org/abs/2105.09613.
- [27]Kohei Sugawara, Hayato Kobayashi, and Masajiro Iwasaki. On approximately searching for similar word embeddings. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2265–2275, Berlin, Germany, 2016. Association for Computational Linguistics. doi: 10.18653/v1/P16-1214.
- [28]Tommaso Teofili and Jimmy Lin. Patience in proximity: A simple early termination strategy for HNSW graph traversal in approximate k-nearest neighbor search. In Advances in Information Retrieval (ECIR 2025), Lecture Notes in Computer Science, pages 401–407, 2025. doi: 10.1007/978-3-031-88714-7_39.DOI
- [29]Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas, and Wei Wang. Steiner-hardness: A query hardness measure for graph-based ANN indexes. Proceedings of the VLDB Endowment, 17(13):4668–4682, 2024.
- [30]Zeyu Wang, Manos Chatzakis, Qitong Wang, Themis Palpanas, Peng Wang, and Wei Wang. ANNiE: A learned query cost estimator for graph-based approximate nearest neighbor search. Proceedings of the VLDB Endowment, 19(11):3820–3833, 2026. doi: 10.14778/3836663. 3836728.DOI
- [31]Jiadong Xie, Jeffrey Xu Yu, and Yingfan Liu. Graph based K-nearest neighbor search revisited. ACM Transactions on Database Systems, 50(4), 2025. doi: 10.1145/3736716.DOI
- [32]Kaixiang Yang, Hongya Wang, Bo Xu, Wei Wang, Yingyuan Xiao, Ming Du, and Junfeng Zhou. Tao: A learning framework for adaptive nearest neighbor search using static features only, 2021. URL https://arxiv.org/abs/2110.00696.
- [33]Chao Zhang and Renée J. Miller. Distribution-aware exploration for adaptive HNSW search. Proceedings of the ACM on Management of Data, 4(1), 2026. doi: 10.1145/3786639.DOI
