betaFeedback

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 α+1α−1\tfrac{α+1}{α-1}. Independently, Al-Jazzazi et al. proposed adaptive beam search (ABS) with a relaxation parameter γ>0γ> 0, showing a 2γ\tfrac{2}γ approximation on navigable graphs (α≈1α\approx 1), 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 α+1α(γ+1)−1\tfrac{α+1}{α(γ+1)-1} for any metric. Moreover, on sorted αα-reachable graphs (introduced by Gollapudi et al.) under the ℓ2\ell_2 metric, we obtain the tighter bound max⁡(αα(γ+1)−1,α2+1α2(γ+1)−1)\max\bigl(\tfracα{α(γ+1)-1}, \tfrac{α^{2}+1}{α^{2}(γ+1)-1}\bigr). 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 29.6%29.6\% relative to classical beam search (CBS). Relative to ABS, it is faster in 1111 of 1515 settings, by up to 6.5%6.5\%, and at most 1.4%1.4\% slower in the other 44; at 95%95\% recall, its advantage over ABS grows from 0.80.8–4.2%4.2\% for 100100 neighbors to 4.64.6–5.6%5.6\% for 500500 neighbors. In memory, it needs 1.31.3–23.7%23.7\% fewer distance computations than CBS and 0.00.0–3.9%3.9\% 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 nn vectors and a query vector qq, the goal is to retrieve the kk data vectors nearest to qq. Since exact search typically takes linear time in nn 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 α\alphareachable graphs (α>1\alpha> 1). 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 qq is at most α+1α−1\frac{\alpha+1}{\alpha-1} 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 α+1α−1\frac{\alpha+1}{\alpha-1} approximation guarantee for all elements maintained in the beam. In addition, they showed that DiskANN’s RobustPrune procedure produces a special class of sorted α\alpha-reachable graphs, and proved that under the ℓ2\ell_2 metric these graphs admit the sharper approximation bound of αα−1\frac{\alpha}{\alpha-1}. Complementing these works, Al-Jazzazi et al. [1] proposed a modified search procedure called adaptive beam search (ABS), parameterized by γ>0\gamma> 0, which delays termination to enable additional exploration. They proved a 2γ\frac{2}{\gamma}-approximation guarantee on navigable graphs—corresponding in our terminology to the regime α≈1\alpha\approx1—where classical beam search does not admit any provable guarantees.

Given these two extremes—classical beam search on α\alpha-reachable graphs (α>1,γ=0\alpha> 1, \gamma= 0) and adaptive beam search on navigable graphs (α≈1,γ>0\alpha\approx1, \gamma> 0)—it is natural to ask the following questions.

Q1. What approximation guarantee can adaptive beam search, parameterized by γ≥0\gamma\ge0, achieve on α\alpha-reachable graphs with α>1\alpha> 1?

Q2. Can the improved ℓ2\ell_2-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 α\alpha-reachable graphs achieves an improved approximation guarantee, summarized in the following theorem.

Theorem 1.1. Let G=(V,E)G = (V, E) be an α\alpha-reachable graph with α>1\alpha> 1, let qq be a query whose distances to the points of VV are pairwise distinct, let B⋆={b1,…,bk}B^{\star} = \{b_1, \ldots, b_k\} be the result of adaptive beam search (sorted by increasing distance from q)withparameter$0≤γ≤2/αq) with parameter \$0 \le\gamma\le2/\alpha, and let A={a1,…,ak}A = \{a_1, \ldots, a_k\} denote the true top-kk neighbors of qq sorted by increasing distance. Then for any metric DD,

D(bi,q)≤C⋅D(ai,q),i=1,…,k,C=α+1α(γ+1)−1.D(b_i,q) \le C \cdot D(a_i,q), \qquad i = 1,\ldots,k,\qquad C = \frac{\alpha+1}{\alpha(\gamma+1)-1}.

Building on this result, our second contribution addresses the second question by establishing a sharper approximation guarantee for adaptive beam search on sorted α\alpha-reachable graphs under the ℓ2\ell_2 metric, as summarized below.

Theorem 1.2. Under the hypotheses of Theorem 1.1, if in addition GG is sorted α\alpha-reachable and DD is the ℓ2\ell_2 metric, then for any 0≤γ≤max⁡(1/α,2/α2)0 \le\gamma\le\max(1/\alpha, 2/\alpha^2),

D(bi,q)≤C⋅D(ai,q),i=1,…,k,D(b_i,q) \le C \cdot D(a_i,q), \qquad i = 1,\ldots,k,
C=max⁡(αα(γ+1)−1,α2+1α2(γ+1)−1).C = \max\left(\frac{\alpha}{\alpha(\gamma+1)-1},\frac{\alpha^2+1}{\alpha^2(\gamma+1)-1}\right).

The general-metric bound is tight, and it recovers the bound of Indyk and Xu [13] at γ=0\gamma= 0 and that of Al-Jazzazi et al. [1] as α→1\alpha\to1. The sorted-ℓ2\ell_2 bound is tight where the first term of the max dominates, and it recovers the bound of Gollapudi et al. [10] at γ=0\gamma= 0. § 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) α\alpha-reachable graphs, such as those built by DiskANN’s slow preprocessing, whose naive construction takes O(n3)O(n^3) 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 γ\gamma, 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-kk, so it stops early on an easy query, whose top-kk settles after a few steps, and keeps searching a hard query, whose top-kk 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 K=500K = 500 than at K=100K = 100 on all three datasets: from K=100K = 100 to K=500K = 500, 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 K=500K = 500 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 α\alpha-reachable graphs. On α\alpha-reachable graphs, ABS with parameter γ\gamma returns a α+1α(γ+1)−1\frac{\alpha+1}{\alpha(\gamma+1)-1}-approximation for any metric (Theorem 1.1), and on sorted α\alpha-reachable graphs under ℓ2\ell_2 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 K=500K = 500 than at K=100K = 100 (§ 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 d≪log⁡nd \ll\log n. 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 α\alpha-reachable graphs, Gollapudi et al. [10] extend it to beam search and tighten it on sorted α\alpha-reachable graphs under ℓ2\ell_2, and Al-Jazzazi et al. [1] prove an Algorithm 1 General beam search (adapted from [1])

Image not extracted

Figure 1.

  1. Input: Graph G=(V,E)G=(V,E), start node s∈Vs \in V, distance function DD, query q∈Xq \in\mathcal{X}, target k≤∣V∣k \le|V|.

  2. Output: Set B⋆={b1,…,bk}B^\star= \{b_1,\ldots,b_k\} of kk approximate nearest neighbors of qq.

  3. Initialize two min-priority queues (sorted by distance to qq): BB containing all discovered nodes, Bu⊆BB_u \subseteq B containing the not-yet-expanded nodes.

  4. Insert ss into both BB and BuB_u; set B⋆←∅B^\star\leftarrow\emptyset.

  5. while Bu≠∅B_u \ne\emptyset do

  6.     x←x \leftarrow top element of BuB_u.

  7.     if termination condition holds then

  8.         break.

  9.     end if

  10.     Pop xx from BuB_u.

  11.     for y∈Nout(x)y \in N_{\mathrm{out}}(x) do

  12.         if y∉By \notin B then

  13.             Insert yy into BB and BuB_u.

  14.         end if

  15.     end for

  16. end while

  17. Return the top kk elements of BB as B⋆B^\star.

:::

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], τ\tau-MG [21], α\alpha-CG [18] and LMG [31]; these guarantees concern their own constructions and search procedures, whereas ours concern ABS on (sorted) α\alpha-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 (X,D)(\mathcal{X},D) where X\mathcal{X} is a set of points and D:X×X→R≥0D:\mathcal{X}\times\mathcal{X}\to\mathbb{R}_{\ge0} is a distance function that satisfies, for all u,v,p∈Xu,v,p\in\mathcal{X}: (i) D(u,v)≥0D(u,v)\ge0; (ii) D(u,v)=0⟺u=vD(u,v)=0\Longleftrightarrow u=v; (iii) D(u,v)=D(v,u)D(u,v)=D(v,u); and (iv) the triangle inequality D(u,p)≤D(u,v)+D(v,p)D(u,p)\le D(u,v)+D(v,p). We are given a dataset of nn points in X\mathcal{X}, which form the node set VV of a directed graph G=(V,E)G=(V,E), and we let Nout(u)={v∈V:(u,v)∈E}N_{\mathrm{out}}(u)=\{v\in V:(u,v)\in E\} be the out-neighbors of uu. The definition of α\alpha-reachable is as follows.

Definition 3.1 (α\alpha-reachable graph [13 Definition 3.1]). A directed graph G=(V,E)G=(V,E) is α\alpha-reachable with α>1\alpha>1 if for every pair u,v∈Vu,v\in V and u≠vu\ne v, either (u,v)∈E(u,v)\in E or there exists t∈Vt\in V such that (u,t)∈E(u,t)\in E and D(v,t)≤D(v,u)/αD(v,t)\le D(v,u)/\alpha.

Informally, from any node uu there is a local step towards any target vv whose distance shrinks by a factor of at least α\alpha.

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 O(n3)O(n^3) time, and the result is an α\alpha-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 RR. It carries no such guarantee. Our guarantees (§ 4) hold for any (sorted) α\alpha-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 pp, a candidate set V\mathcal{V}, a parameter α\alpha, and a degree bound RR, RobustPrune first sorts V\mathcal{V} in increasing distance from pp, then iterates through the sorted list and adds each p′p' to Nout(p)N_{\mathrm{out}}(p) unless some already-accepted xx satisfies α⋅D(x,p′)≤D(p,p′)\alpha\cdot D(x,p') \le D(p,p'). Slow preprocessing corresponds to calling RobustPrune with V=V∖{p}\mathcal{V} = V \setminus\{p\} and R=n−1R = n - 1 for every p∈Vp \in V.

Because the candidate list is sorted, the certifying neighbor tt for a non-edge (u,v)(u,v) also satisfies D(u,t)≤D(u,v)D(u,t) \le D(u,v). Gollapudi et al. [10] captured this extra structure in the following stronger definition.

Definition 3.2 (Sorted α\alpha-reachable graph [10]). A directed graph G=(V,E)G = (V,E) is sorted α\alpha-reachable with α>1\alpha> 1 if for every pair u,v∈Vu,v \in V and u≠vu \ne v, either (u,v)∈E(u,v) \in E or there exists t∈Vt \in V satisfying all three conditions: (1) (u,t)∈E(u,t) \in E, (2) D(v,t)≤D(v,u)/αD(v,t) \le D(v,u)/\alpha, and (3) D(u,t)≤D(u,v)D(u,t) \le D(u,v).

Gollapudi et al. [10] show that the DiskANN RobustPrune construction in fact uses the sorted pruning rule. Sorted α\alpha-reachability is stronger than α\alpha-reachability and enables tighter approximation bounds under the ℓ2\ell_2 metric.

DiskANN uses classical beam search (CBS) for its search procedure (Algorithm 1 of [16]), parameterized by a list size L≥kL \ge k: the algorithm maintains LL approximate neighbors of qq and returns the top kk 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 L≥kL \ge k nodes v1,…,vL∈B∖{x}v_1,\ldots,v_L \in B \setminus\{x\} with D(vi,q)≤D(x,q)D(v_i,q) \le D(x,q).

Adaptive beam search (ABS) [1]: The search terminates when there exist kk nodes v1,…,vk∈B∖{x}v_1,\ldots,v_k \in B \setminus\{x\} with (γ+1)⋅D(vi,q)≤D(x,q)(\gamma+ 1) \cdot D(v_i,q) \le D(x,q) for parameter γ≥0\gamma\ge0.

Setting γ=0\gamma= 0 recovers the classical rule, so ABS with γ=0\gamma= 0 is exactly CBS at width L=kL = k.

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 ℓ2\ell_2 metric on sorted α\alpha-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 n=∣V∣n = |V|, s∈Vs \in V be the starting node for search in Algorithm 1, let A={a1,…,ak}A = \{a_1,\ldots,a_k\} denote the ground-truth nearest neighbors of qq ordered by increasing distance, and let B∗={b1,…,bk}B^* = \{b_1,\ldots,b_k\} denote the top-kk items of BB at termination (see Algorithm 1), also ordered by increasing distance. We assume that the distances D(u,q)D(u,q), u∈Vu \in V, are pairwise distinct, so that these orders are strict.

Let Bu⊆BB_u \subseteq B be the unexpanded set and Be=B∖BuB_e = B \setminus B_u the expanded set. As each expansion inserts every out-neighbor into BB, every w∈Nout(u)w \in N_{\mathrm{out}}(u) of an expanded node u∈Beu \in B_e lies in BB. The α\alpha and γ\gamma parameter ranges in both theorems imply C≥1C \ge1, so the statements are non-trivial.

Adaptive beam search (Algorithm 1) terminates in exactly one of two ways: either (i) BuB_u empties (line 5), or (ii) the termination condition fires (line 7). We treat the two cases separately.

Case A: BuB_u empties

The argument for this case follows [1]; we give it in full. If the search terminates because BuB_u is empty, the termination condition never held, so every popped node had all of its out-neighbors inserted into BB. In particular, BB contains every node reachable from ss in GG. We claim that every node of VV is reachable from ss.

Fix an arbitrary target node u∈Vu \in V, and order the remaining nodes x1,x2,…,xn−1x_1, x_2, \ldots, x_{n-1} in increasing distance from uu. For every t∈V∖{u,x1}t \in V \setminus\{u, x_1\}, because α>1\alpha> 1 we have α⋅D(u,t)>D(u,t)≥D(u,x1)\alpha\cdot D(u,t) > D(u,t) \ge D(u,x_1), so no other node can certify α\alpha-reachability from x1x_1 to uu; hence by Definition 3.1 there must be an edge from x1x_1 to uu, and uu is reachable from x1x_1.

Suppose inductively that uu is reachable from each of x1,…,xi−1x_1, \ldots, x_{i-1} for some i>1i > 1. For every j>ij > i we have α⋅D(u,xj)>D(u,xj)≥D(u,xi)\alpha\cdot D(u,x_j) > D(u,x_j) \ge D(u,x_i), so any certifying neighbor for the pair (xi,u)(x_i,u) must lie in {u,x1,…,xi−1}\{u, x_1, \ldots, x_{i-1}\}; α\alpha-reachability thus guarantees an edge from xix_i into this set, and so uu is reachable from xix_i.

By induction uu is reachable from every xjx_j, in particular from ss. Since uu was arbitrary, every node in VV is reachable from ss, so B=VB = V at termination and ABS returns the exact top-kk nearest neighbors of qq. Both theorems therefore hold in this case.

Case B: the termination condition fires

If B⋆=AB^\star= A there is nothing to prove, so pick the smallest index ii with ai∉B⋆a_i \notin B^\star. For every j<ij < i we have bj=ajb_j = a_j. Since aia_i is the point closest to qq outside {a1,…,ai−1}\{a_1, \ldots, a_{i-1}\} and distances are distinct, D(ai,q)<D(bk,q)D(a_i,q) < D(b_k,q); hence ai∉Ba_i \notin B, for otherwise aia_i would be among the top-kk items of BB.

Let xx be the top element of BuB_u when the termination condition fires, so that D(x,q)≤D(u,q)D(x,q) \le D(u,q) for every u∈Buu \in B_u. The condition provides kk nodes of B∖{x}B \setminus\{x\} whose distances to qq are at most D(x,q)/(γ+1)D(x,q)/(\gamma+ 1). Hence x∉B⋆x \notin B^\star, and

(γ+1)⋅D(b,q)≤D(x,q)for every b∈B⋆.(\gamma+ 1) \cdot D(b,q) \le D(x,q) \qquad\text{for every } b \in B^\star.

Now let v∈B⋆v \in B^\star be arbitrary. Then D(v,q)<D(x,q)≤D(u,q)D(v,q) < D(x,q) \le D(u,q) for every u∈Buu \in B_u, where the first inequality is strict because v≠xv \ne x and distances are distinct, so v∉Buv \notin B_u. Since v∈B⋆⊆Bv \in B^\star\subseteq B, this forces v∈Bev \in B_e. In particular, there is no edge from vv to aia_i, since expanding vv would have inserted aia_i into BB. Applying α\alpha-reachability of GG repeatedly, starting from vv, therefore gives nodes t0,t1,…,tℓt_0, t_1, \ldots, t_\ell with ℓ≥2\ell\ge2 such that:

  • (i) t0=vt_0 = v;

  • (ii) tℓ=ait_\ell= a_i;

  • (iii) (tz,tz+1)∈E(t_z,t_{z+1}) \in E for z=0,…,ℓ−1z = 0, \ldots, \ell- 1;

  • (iv) α⋅D(tz+1,ai)≤D(tz,ai)\alpha\cdot D(t_{z+1},a_i) \le D(t_z,a_i) for z=0,…,ℓ−1z = 0, \ldots, \ell- 1; and,

  • (v) when GG is sorted α\alpha-reachable, additionally D(v,t1)≤D(v,ai)D(v,t_1) \le D(v,a_i).

Informally, the path t0→t1→⋯→tℓt_0 \to t_1 \to\cdots\to t_\ell approaches aia_i by a factor of at least α\alpha per hop.

We have shown that t0=v∈Bet_0 = v \in B_e and tℓ=ai∉Bt_\ell= a_i \notin B. Since all out-neighbors of an expanded node are inserted in BB, it follows that tℓ−1∉Bet_{\ell-1} \notin B_e.

Let z⋆z^\star be the largest index with tz⋆∈Bet_{z^\star} \in B_e; then 0≤z⋆≤ℓ−20 \le z^\star\le\ell- 2. As tz⋆∈Bet_{z^\star} \in B_e, we have tz⋆+1∈Bt_{z^\star+1} \in B, and by maximality of z⋆z^\star, the node tz⋆+1t_{z^\star+1} is not expanded, so tz⋆+1∈But_{z^\star+1} \in B_u. We consider two sub-cases.

Sub-case B1: z⋆=0z^\star= 0

Here t1∈But_1 \in B_u, so the termination condition gives (γ+1)⋅D(v,q)≤D(t1,q)(\gamma+ 1) \cdot D(v,q) \le D(t_1,q), and α\alpha-reachability gives α⋅D(t1,ai)≤D(v,ai)\alpha\cdot D(t_1,a_i) \le D(v,a_i). General metric. Chaining the triangle inequality,

(γ+1)⋅D(q,v)≤D(q,t1)≤D(q,ai)+D(ai,t1)≤D(q,ai)+D(v,ai)α≤D(q,ai)+D(v,q)+D(q,ai)α=D(v,q)α+α+1α⋅D(q,ai).\begin{aligned} (\gamma+1)\cdot D(q,v)&\le D(q,t_1)\\ &\le D(q,a_i)+D(a_i,t_1)\\ &\le D(q,a_i)+\frac{D(v,a_i)}{\alpha}\\ &\le D(q,a_i)+\frac{D(v,q)+D(q,a_i)}{\alpha}\\ &=\frac{D(v,q)}{\alpha}+\frac{\alpha+1}{\alpha}\cdot D(q,a_i). \end{aligned}

Rearranging,

(γ+1−1α)⋅D(q,v)≤(α+1α)⋅D(q,ai)\left(\gamma+1-\frac{1}{\alpha}\right)\cdot D(q,v)\le\left(\frac{\alpha+1}{\alpha}\right)\cdot D(q,a_i)
⟹D(q,v)D(q,ai)≤α+1α(γ+1)−1.\Longrightarrow\quad\frac{D(q,v)}{D(q,a_i)}\le\frac{\alpha+1}{\alpha(\gamma+1)-1}.

ℓ2\ell_2 metric, sorted α\alpha-reachable GG. Sorted α\alpha-reachability adds the constraint D(v,t1)≤D(v,ai)D(v,t_1)\le D(v,a_i). The largest ratio D(q,v)/D(q,ai)D(q,v)/D(q,a_i) compatible with the three constraints is the value of a semidefinite program over the Gram matrix of qq, vv, t1t_1 and aia_i, and Appendix A exhibits a dual solution of value (α/(α(γ+1)−1))2\left(\alpha/(\alpha(\gamma+1)-1)\right)^2. Hence

D(q,v)D(q,ai)≤αα(γ+1)−1.\frac{D(q,v)}{D(q,a_i)}\le\frac{\alpha}{\alpha(\gamma+1)-1}.

Sub-case B2: $z^\star\ge 1

Now tz⋆+1∈But_{z^\star+1}\in B_u, so (γ+1)⋅D(v,q)≤D(tz⋆+1,q)(\gamma+1)\cdot D(v,q)\le D(t_{z^\star+1},q). Iterating α\alpha-reachability along the chain gives

αz⋆+1⋅D(tz⋆+1,ai)≤D(v,ai),\alpha^{z^\star+1}\cdot D(t_{z^\star+1},a_i)\le D(v,a_i),

and since z⋆+1≥2z^\star+1\ge2, in particular α2⋅D(tz⋆+1,ai)≤D(v,ai)\alpha^2\cdot D(t_{z^\star+1},a_i)\le D(v,a_i). This is precisely the structure of Sub-case B1 with α\alpha replaced by α2\alpha^2 and t1t_1 by tz⋆+1t_{z^\star+1}. The general-metric argument of Sub-case B1 therefore gives

D(q,v)D(q,ai)≤α2+1α2(γ+1)−1.\frac{D(q,v)}{D(q,a_i)}\le\frac{\alpha^2+1}{\alpha^2(\gamma+1)-1}.

Assembling the bound

Combining Sub-cases B1 and B2, for every v∈B⋆v\in B^\star:

D(q,v)≤C0⋅D(q,ai),(1)D(q,v)\le C_0\cdot D(q,a_i), \tag*{(1)}

where

C0={max⁡(α+1α(γ+1)−1,α2+1α2(γ+1)−1)=α+1α(γ+1)−1,(general metric, α-reachable G):max⁡(αα(γ+1)−1,α2+1α2(γ+1)−1),(ℓ2 metric, sorted α-reachable G):C_0=\begin{cases} \max\left(\frac{\alpha+1}{\alpha(\gamma+1)-1},\frac{\alpha^2+1}{\alpha^2(\gamma+1)-1}\right) =\frac{\alpha+1}{\alpha(\gamma+1)-1}, & \text{(general metric, }\alpha\text{-reachable }G\text{):}\\[1.2em] \max\left(\frac{\alpha}{\alpha(\gamma+1)-1},\frac{\alpha^2+1}{\alpha^2(\gamma+1)-1}\right), & (\ell_2\text{ metric, sorted }\alpha\text{-reachable }G\text{):} \end{cases}

The simplification in the general case follows from α>1⇒(α+1)/(α(γ+1)−1)≥(α2+1)/(α2(γ+1)−1)\alpha>1\Rightarrow(\alpha+1)/(\alpha(\gamma+1)-1)\ge(\alpha^2+1)/(\alpha^2(\gamma+1)-1). Thus C0=CC_0=C in both theorems.

Finally, fix 1≤j≤k1\le j\le k. If j<ij<i then bj=ajb_j=a_j and the claim is immediate. If j≥ij\ge i then bj∈B⋆b_j\in B^\star, so by (1) applied with v=bjv=b_j,

D(bj,q)≤C⋅D(ai,q)≤C⋅D(aj,q),D(b_j,q)\le C\cdot D(a_i,q)\le C\cdot D(a_j,q),

where the last inequality uses that a1,…,aka_1,\ldots,a_k are sorted by increasing distance from qq. 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 k=1k = 1, start the search at a node vv, and let GG be the complete graph on three nodes {v,a,t}\{v, a, t\} with the single edge (v,a)(v, a) removed, so that the search reaches the true nearest neighbor aa of qq only through tt.

General metric, α\alpha-reachable. Place the three nodes and the query on R\mathbb{R}, with DD the Euclidean metric on R\mathbb{R} (which is also a general metric):

v=α+1α(γ+1)−1,q=0,a=−1,t=−(α+1)(γ+1)α(γ+1)−1,v = \frac{\alpha+ 1}{\alpha(\gamma+ 1) - 1}, \qquad q = 0, \qquad a = -1, \qquad t = -\frac{(\alpha+ 1)(\gamma+ 1)}{\alpha(\gamma+ 1) - 1},

with α>1\alpha> 1 and 0<γ<2/α0 < \gamma< 2/\alpha. A direct check shows α⋅D(t,a)≤D(v,a)\alpha\cdot D(t, a) \le D(v, a), so GG is α\alpha-reachable. Starting from vv, only tt is added to the priority queues; since (γ+1)⋅D(q,v)≤D(q,t)(\gamma+ 1) \cdot D(q, v) \le D(q, t), tt is not expanded and the search terminates with vv as its output. The realized ratio is

D(q,v)D(q,a)=α+1α(γ+1)−1,\frac{D(q, v)}{D(q, a)} = \frac{\alpha+ 1}{\alpha(\gamma+ 1) - 1},

matching the bound of Theorem 1.1.

ℓ2\ell_2, sorted α\alpha-reachable. Place the three nodes in R2\mathbb{R}^2 together with a query:

v=(−α2,0),t=(α2,0),a=(α2−12α,1−14α2),v = \left(-\frac{\alpha}{2}, 0\right), \qquad t = \left(\frac{\alpha}{2}, 0\right), \qquad a = \left(\frac{\alpha}{2} - \frac{1}{2\alpha}, \sqrt{1 - \frac{1}{4\alpha^2}}\right),
q=(α2(1−(γ+1)2)2(α(γ+1)2+α−(γ+1)),α(γ+1)4α2−12(α(γ+1)2+α−(γ+1))),q = \left(\frac{\alpha^2(1 - (\gamma+ 1)^2)}{2(\alpha(\gamma+ 1)^2 + \alpha- (\gamma+ 1))}, \frac{\alpha(\gamma+ 1)\sqrt{4\alpha^2 - 1}}{2(\alpha(\gamma+ 1)^2 + \alpha- (\gamma+ 1))}\right),

with α>1\alpha> 1 and 0<γ<1/α0 < \gamma< 1/\alpha. A direct check shows α⋅D(t,a)≤D(v,a)\alpha\cdot D(t, a) \le D(v, a) and D(v,t)≤D(v,a)D(v, t) \le D(v, a), so GG is sorted α\alpha-reachable. Starting the search at vv, tt is never expanded because (γ+1)⋅D(q,v)≤D(q,t)(\gamma+ 1) \cdot D(q, v) \le D(q, t), and the algorithm returns vv. The realized ratio is

D(q,v)D(q,a)=αα(γ+1)−1,\frac{D(q, v)}{D(q, a)} = \frac{\alpha}{\alpha(\gamma+ 1) - 1},

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-KK after a few expansions, while hard ones need much larger lists. Beam predictor therefore gives each query its own list size LL 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 rTr_T, in percent. For a training query qiq_i, let dist_cmps⁡(qi,L)\operatorname{dist\_cmps}(q_i, L) and recall⁡(qi,L)\operatorname{recall}(q_i, L) be the number of distance computations and the recall@KK, in percent, of CBS with list size LL; one sweep of CBS over a grid L\mathcal{L} of list sizes measures both. The grid contains every integer in [K,1000][K, 1000] and every multiple of 10 in (1000,10K](1000, 10K]. The best allocation of list sizes to the QQ training queries solves

min⁡L1,…,LQ∈L1Q∑i=1Qdist_cmps⁡(qi,Li)(2)\min_{L_1,\ldots,L_Q \in\mathcal{L}} \frac{1}{Q}\sum_{i=1}^{Q} \operatorname{dist\_cmps}(q_i, L_i) \tag*{(2)}
s.t. 1Q∑i=1Qrecall⁡(qi,Li)≥rT.\text{s.t. } \frac{1}{Q}\sum_{i=1}^{Q} \operatorname{recall}(q_i, L_i) \ge r_T.

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

min_cmps⁡[i][r]=min⁡{dist_cmps⁡(qi,L):L∈L, recall⁡(qi,L)≥r},r∈{0,1,…,100},\operatorname{min\_cmps}[i][r] = \min\{\operatorname{dist\_cmps}(q_i,L) : L \in\mathcal{L},\ \operatorname{recall}(q_i,L) \ge r\},\quad r \in\{0,1,\ldots,100\},

with min_cmps⁡[i][r]=∞\operatorname{min\_cmps}[i][r] = \infty if no L∈LL \in\mathcal{L} reaches recall rr, together with the smallest list size min_L⁡[i][r]∈L\operatorname{min\_L}[i][r] \in\mathcal{L} that reaches recall rr. Instead of Problem (2), we work with

min⁡r1,…,rQ∈{0,…,100}1Q∑i=1Qmin_cmps⁡[i][ri]s.t.1Q∑i=1Qri≥rT,(3)\begin{aligned} \min_{r_1,\ldots,r_Q \in\{0,\ldots,100\}} \quad& \frac{1}{Q}\sum_{i=1}^{Q}\operatorname{min\_cmps}[i][r_i] \\ \text{s.t.}\quad& \frac{1}{Q}\sum_{i=1}^{Q}r_i \ge r_T, \tag*{(3)} \end{aligned}

and the target list size of query qiq_i is Li∗=min_L⁡[i][ri]L_i^* = \operatorname{min\_L}[i][r_i]. For K=100K = 100, recall@K is a whole percentage, and Problem (3) is equivalent to Problem (2). For K=200K = 200 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 λ≥0\lambda\ge0 on distance computations. For a fixed price the problem decouples into independent per-query problems,

ri(λ)=arg⁡max⁡r∈{0,…,100}(r−λ⋅min_cmps⁡[i][r]).r_i(\lambda) = \underset{r \in\{0,\ldots,100\}}{\arg\max}\left(r-\lambda\cdot\operatorname{min\_cmps}[i][r]\right).

A higher price lowers the recall each query buys, so we binary-search λ\lambda over [0,5⋅104][0,5\cdot10^4] for 80 steps and keep the allocation of the largest price whose mean recall still meets rTr_T. This takes O(80⋅101⋅Q)O(80\cdot101\cdot Q) 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 dp⁡i[s]\operatorname{dp}_i[s] be the minimum total cost of queries q1,…,qiq_1,\ldots,q_i when their recall levels sum to ss. Then dp⁡0[0]=0\operatorname{dp}_0[0]=0,

dp⁡i[s]=min⁡r∈{0,…,100}(dp⁡i−1[s−r]+min_cmps⁡[i][r]).\operatorname{dp}_i[s] = \min_{r\in\{0,\ldots,100\}}\left(\operatorname{dp}_{i-1}[s-r]+\operatorname{min\_cmps}[i][r]\right).

and the optimum of (3) is min⁡s≥QrTdp⁡Q[s]/Q\min_{s\ge Qr_T}\operatorname{dp}_Q[s]/Q. Since ss ranges up to 100Q100Q, the DP takes O(101⋅100Q2)O(101\cdot100Q^2) 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 K=200K=200 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.

KKrrρ\rhoRecallWorstLagr. vs DP
SIFT100M
100900.6390.000.41+0.20 (max 0.7)
100950.7894.990.21+0.24 (max 1.0)
200900.4789.980.47+0.07 (max 0.2)
200950.8094.970.23+0.11 (max 0.3)
500950.7495.000.24+0.16 (max 0.3)
DEEP100M
100900.6689.970.38+0.31 (max 1.3)
100950.7794.940.26+0.18 (max 0.5)
200900.6089.940.33+0.19 (max 0.7)
200950.8094.960.24+0.25 (max 0.6)
500950.6694.970.19+0.09 (max 0.3)
MSSpaceV100M
100900.4090.020.45+0.45 (max 2.1)
100950.7495.020.22+0.30 (max 1.1)
200900.3390.040.40+0.24 (max 1.0)
200950.7595.010.17+0.52 (max 1.5)
500950.7795.000.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). ρ\rho: Spearman correlation between predicted and Lagrangian-optimal list sizes on the test half; Recall: mean test recall (%); Worst: largest ∣recall−r∣|\mathrm{recall}-r| 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 Li∗L_i^* 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 L=KL=K run to convergence, and summarizes it in six features. Let d1≤⋯≤dKd_1\le\cdots\le d_K be the distances of the pilot’s top-KK results, and let σ0,σ1,…,σT\sigma_0,\sigma_1,\ldots,\sigma_T be the sum of the current top-KK distances recorded after each of the TT expansion steps of the pilot.

  • Scale features: d1d_1, dKd_K, and the mean and standard deviation of d1,…,dKd_1,\ldots,d_K.

  • Trajectory features: sdp =100⋅(σ0−σT)/σ0=100\cdot(\sigma_0-\sigma_T)/\sigma_0, the percentage drop of the top-KK distance sum, and c90, the number of distance computations after which σt\sigma_t first falls below σ0−0.9(σ0−σT)\sigma_0-0.9\left(\sigma_0-\sigma_T\right).

The scale features describe the distances of the query’s current neighbors; dKd_K 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 log⁡L⋆\log L^\star by linear regression on the six features xx, weighting query ii by (Li⋆/K)2(L_i^\star/K)^2 so that queries with large targets, which dominate the cost, are fit more closely:

log⁡L^=w⊤x+b.\widehat{\log L} = w^\top x + b.

A single scale factor ss calibrates the predictions,

L^=min⁡(10K,max⁡(K,round⁡(s⋅exp⁡(w⊤x+b)))),\widehat{L} = \min\left(10K,\max\left(K,\operatorname{round}\left(s\cdot\exp(w^\top x+b)\right)\right)\right),

where ss is the smallest value in {0.300,0.305,0.310,…}\{0.300, 0.305, 0.310, \ldots\} for which the training queries reach mean recall rTr_T. 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 KK, the pilot’s list size, the clipping range, ss, bb and ww. 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 KK, so its sorted candidate list always holds the KK 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 W=4W = 4 reads) the search records the sum of the current top-KK 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 d1,…,dKd_1,\ldots,d_K 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 O(K+T)O(K+T) time and evaluates L^\widehat{L}: six multiply-adds, one exponential and the clipping.

Extension. The search re-inserts the best L^−K\widehat{L}-K buffered candidates that are not in the list and continues with list size L^\widehat{L}. For example, with K=100K=100 and L^=420\widehat{L}=420, the 320 best candidates outside the list are appended to it and the search continues with list size 420; if L^=K\widehat{L}=K, the pilot’s result is returned. Since the list holds the cc best candidates discovered so far (c=Kc=K unless fewer were found), which are also the cc smallest entries of the buffer, the next t=min⁡(L^−c,∣buffer∣−c)t=\min(\widehat{L}-c,\lvert\text{buffer}\rvert-c) are found without sorting the buffer: std::nth_element\texttt{std::nth\_element} at position cc moves the list’s entries to the front, a second call at position c+tc+t moves the next tt candidates into positions cc to c+t−1c+t-1, and only those tt entries are sorted. They are appended to the list as unexpanded, its capacity is raised to L^\widehat{L}, and the loop resumes with the same visited set until all L^\widehat{L} entries are expanded. The overhead is one append per distance computation during the pilot and O(∣buffer∣+tlog⁡t)O(\lvert\text{buffer}\rvert+t\log t) work at the transition.

Alternative without a buffer. We also implemented a variant in which the pilot’s list keeps up to 10K10K candidates in sorted order, the pilot stops once the first KK are expanded, and after the prediction the list is truncated to L^\widehat{L} 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 10K10K 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 L^\widehat{L}. In two settings that we checked query by query (SIFT100M, sorted graph, K=100K=100 and 500, r=95%r=95\%), every query whose L^\widehat{L} 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 L=1000L = 1000, the sweep advances in steps of 10 and the estimate rounds L^\hat{L} 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 KK-th neighbor, whereas the per-query tables count only the first KK 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 γ\gamma 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 KK 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.

DatasetPointsDimTypeQueriesMetric
SIFT100M100,000,000128uint810,000ℓ2\ell_2
DEEP100M100,000,00096float3210,000ℓ2\ell_2
MSSpaceV100M100,000,000100int828,690ℓ2\ell_2

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 R=32R = 32 and build list size Lbuild=100L_{\mathrm{build}} = 100. DiskANN’s pruning parameter is set to α=1.2\alpha= 1.2. DiskANN sorts the candidate list before pruning, the rule that makes slow-preprocessing graphs sorted α\alpha-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 α\alpha-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 α\alpha-reachable but not necessarily sorted α\alpha-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 W=4W = 4 [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 LL for every query, ABS [1] the same relaxation parameter γ\gamma, 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 KK, the list size of the pilot search, the grid L\mathcal{L} 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 KK: step 1 up to 1000 and step 10 above. One sweep serves every KK of a dataset. The traversal of CBS depends only on LL; KK only decides how many of the final, sorted results are returned. We therefore search each LL in the union of the grids of Table 2 once, return the top K′K' results, where K′K' is the largest studied KK not exceeding LL, and read recall@KK for every K≤K′K \le K' off the same result list; we checked that this reproduces separate per-KK 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 KK 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.

KKPilotSweep grid L\mathcal{L}∣L∣|\mathcal{L}|rr (%)
100100100, 101, …\ldots, 100090190, 95
200200200, …\ldots, 1000, 1010, …\ldots, 200090190, 95
500500500, …\ldots, 1000, 1010, …\ldots, 500090195

Table 2. Beam predictor configuration for each KK. Pilot: list size of the pilot search; L\mathcal{L}: list sizes swept on the training queries; predictions are clipped to [K,10K][K, 10K].

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 KK (the kk of § 3) and target mean recall rr, we train beam predictor on the training half and measure its mean recall@KK on the test half. We then set the LL of CBS and the γ\gamma 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 L∈{1.2,1.6,2,3,4,5,6,5.8,10}⋅KL \in\{1.2, 1.6, 2, 3, 4, 5, 6, 5.8, 10\} \cdot K and ABS at γ∈{0.02,0.04,…,0.2}\gamma\in\{0.02, 0.04, \ldots, 0.2\}, 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; LL is an integer and γ\gamma has four decimals. The baselines are thus tuned on the test queries themselves. We use r∈{90,95}%r \in\{90, 95\}\% for K∈{100,200}K \in\{100, 200\} and r=95%r = 95\% for K=500K = 500; at K=500K = 500, CBS at its smallest list size L=KL = K 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 α\alpha-reachable and sorted α\alpha-reachable graphs: the bound shrinks monotonically in γ\gamma and is smaller for sorted α\alpha-reachable graphs under ℓ2\ell_2. 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 γ∈{0,0.01,…,0.2}\gamma\in\{0, 0.01, \ldots, 0.2\} and K=100K = 100 on the sorted and the shuffled graph and measured recall@100. Figure 1 shows that on all three datasets recall@100 rises monotonically with γ\gamma on both graphs, and that the sorted graph reaches a higher recall than the shuffled graph at every γ\gamma.

Figure 1. Recall@100 of ABS versus the relaxation parameter γ\gamma on the three datasets, for the sorted graph and the shuffled graph (§ 6.1), both built with DiskANN (R=32R=32, Lbuild=100L_{\mathrm{build}}=100), 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 r=95%r = 95\%. In the other four settings, all at r=90%r = 90\%, 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 r=90%r = 90\% the gains are small because very little search is left to reallocate: at K=200K = 200, CBS with its smallest list size L=KL = K already reaches 88.9% recall on both SIFT100M and MSSpaceV100M.

Latency (ms)I/Os per queryΔCBS\Delta_{\mathrm{CBS}} (%)ΔABS\Delta_{\mathrm{ABS}} (%)ΔABS/CBS\Delta_{\mathrm{ABS/CBS}} (%)
KKrrCBSABSBPCBSABSBPLat.I/OsLat.I/OsLat.I/Os
\multicolumn{14}{l}{SIFT100M}
100908.42±0.038.42\pm0.038.06±0.098.06\pm0.098.00±0.038.00\pm0.03170.5163.0159.6−4.9-4.9−6.4-6.4−0.8-0.8−2.1-2.1−4.2-4.2−4.4-4.4
1009514.78±0.0214.78\pm0.0213.24±0.0713.24\pm0.0712.68±0.1512.68\pm0.15305.0269.9261.0−14.2-14.2−14.5-14.5−4.2-4.2−3.3-3.3−10.4-10.4−11.5-11.5
2009011.37±0.1611.37\pm0.1611.38±0.1911.38\pm0.1911.45±0.0511.45\pm0.05232.7231.1229.2+0.6+0.6−1.5-1.5+0.6+0.6−0.8-0.8+0.0+0.0−0.7-0.7
2009520.43±0.0820.43\pm0.0818.92±0.1618.92\pm0.1617.69±0.1017.69\pm0.10421.3387.9360.8−13.4-13.4−14.4-14.4−6.5-6.5−7.0-7.0−7.4-7.4−7.9-7.9
5009532.10±0.1532.10\pm0.1531.56±0.2531.56\pm0.2529.79±0.1329.79\pm0.13667.3646.3609.0−7.2-7.2−8.7-8.7−5.6-5.6−5.8-5.8−1.7-1.7−3.1-3.1
\multicolumn{14}{l}{DEEP100M}
100909.70±0.119.70\pm0.119.18±0.129.18\pm0.129.21±0.049.21\pm0.04205.2192.0190.5−5.0-5.0−7.2-7.2+0.3+0.3−0.8-0.8−5.3-5.3−6.4-6.4
1009518.58±0.1218.58\pm0.1215.95±0.0815.95\pm0.0815.82±0.0415.82\pm0.04397.5335.9335.9−14.8-14.8−15.5-15.5−0.8-0.8+0.0+0.0−14.2-14.2−15.5-15.5
2009013.25±0.1313.25\pm0.1313.14±0.1113.14\pm0.1112.90±0.1012.90\pm0.10280.3272.8268.1−2.6-2.6−4.4-4.4−1.8-1.8−1.7-1.7−0.8-0.8−2.7-2.7
2009525.36±0.2625.36\pm0.2622.62±0.2422.62\pm0.2421.90±0.2721.90\pm0.27540.8476.5464.7−13.7-13.7−14.1-14.1−3.2-3.2−2.5-2.5−10.8-10.8−11.9-11.9
5009539.74±0.3239.74\pm0.3237.44±0.3637.44\pm0.3635.51±0.2935.51\pm0.29851.7793.2754.0−10.6-10.6−11.5-11.5−5.2-5.2−4.9-4.9−5.8-5.8−6.9-6.9
\multicolumn{14}{l}{MSSpaceV100M}
100907.46±0.057.46\pm0.057.01±0.077.01\pm0.077.11±0.207.11\pm0.20159.3147.2150.6−4.6-4.6−5.5-5.5+1.4+1.4+2.3+2.3−5.9-5.9−7.6-7.6
1009520.61±0.1520.61\pm0.1514.77±0.1214.77\pm0.1214.51±0.1314.51\pm0.13448.3322.1312.1−29.6-29.6−30.4-30.4−1.8-1.8−3.1-3.1−28.3-28.3−28.2-28.2
2009011.40±0.1311.40\pm0.1311.15±0.1611.15\pm0.1611.25±0.2211.25\pm0.22247.3238.9241.1−1.3-1.3−2.5-2.5+0.9+0.9+1.0+1.0−2.1-2.1−3.4-3.4
2009529.98±0.9829.98\pm0.9823.40±0.4523.40\pm0.4522.96±0.1322.96\pm0.13662.9515.8495.5−23.4-23.4−25.2-25.2−1.9-1.9−3.9-3.9−22.0-22.0−22.2-22.2
5009560.21±0.1660.21\pm0.1650.03±0.2150.03\pm0.2147.71±0.3047.71\pm0.301,309.11,084.61,039.4−20.8-20.8−20.6-20.6−4.6-4.6−4.2-4.2−16.9-16.9−17.1-17.1

Table 3. SSD index, sorted graph: beam predictor (BP) versus CBS and ABS in mean query latency in ms (mean ±\pm std. dev. over 5 runs) and mean SSD reads (I/Os) per query at matched mean recall@KK on the test half. rr is the target recall (%); the LL of CBS and the γ\gamma 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: ΔCBS=(BP−CBS)/CBS\Delta_{\mathrm{CBS}}=(\mathrm{BP}-\mathrm{CBS})/\mathrm{CBS}, ΔABS=(BP−ABS)/ABS\Delta_{\mathrm{ABS}}=(\mathrm{BP}-\mathrm{ABS})/\mathrm{ABS} and ΔABS/CBS=(ABS−CBS)/CBS\Delta_{\mathrm{ABS/CBS}}=(\mathrm{ABS}-\mathrm{CBS})/\mathrm{CBS}; negative values mean that BP, or ABS for ΔABS/CBS\Delta_{\mathrm{ABS/CBS}}, is cheaper. Bold marks the lowest latency and the lowest I/Os in each row. Single search thread, W=4W=4, 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 10⋅K10 \cdot K, 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 r=95%r = 95\% 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. latencyMedian recallStd of recall
KKrrCBSABSBPCBSABSBPCBSABSBP
SIFT100M
1009012.613.316.894.093.092.010.810.29.1
1009517.429.436.798.097.097.06.96.15.2
2009020.619.820.493.093.093.010.09.99.6
2009529.333.846.497.597.096.56.45.84.7
5009541.244.265.897.297.096.45.95.74.8
DEEP100M
1009013.417.017.794.094.093.011.811.110.4
1009524.735.640.598.098.097.07.76.86.3
2009023.525.522.993.593.593.011.010.710.1
2009535.541.958.998.097.597.07.26.55.9
5009582.058.994.597.697.296.66.76.35.3
MSSpaceV100M
1009015.117.616.396.096.096.015.815.115.3
1009533.2122.252.599.098.098.09.58.48.1
2009020.021.520.295.595.095.013.813.513.5
2009544.7136.282.998.598.097.58.57.67.2
5009595.5265.8163.498.297.697.47.86.96.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@KK (%) 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_cmpsRelative change (%)
KKrrCBSABSBPΔCBS\Delta_{\mathrm{CBS}}ΔABS\Delta_{\mathrm{ABS}}ΔABS/CBS\Delta_{\mathrm{ABS/CBS}}
SIFT100M
100904,0313,9093,839−4.8−1.8−3.0
100956,7866,2376,096−10.2−2.3−8.1
200905,3245,2895,253−1.3−0.7−0.7
200958,9348,4828,153−8.7−3.9−5.1
5009513,46213,23112,734−5.4−3.8−1.7
DEEP100M
100904,5944,3904,373−4.8−0.4−4.4
100958,2037,3587,348−10.4−0.1−10.3
200906,0185,9315,879−2.3−0.9−1.4
2009510,6689,8729,792−8.2−0.8−7.5
5009515,80815,26214,972−5.3−1.9−3.5
MSSpaceV100M
100903,1622,9622,961−6.4−0.0−6.3
100957,7776,0965,937−23.7−2.6−21.6
200904,5694,4804,480−2.0−0.0−2.0
2009511,4409,2959,105−20.4−2.1−18.7
5009521,13418,08917,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; rr, recall matching, the relative changes Δ\Delta (%) and bold as in Table 3.

Effect of KK. Al-Jazzazi et al. [1, App. C.1] observe that on navigable graphs ABS gains less over CBS at K=100K = 100 than at K=1K = 1 and 10. The ΔABS/CBS\Delta_{\mathrm{ABS/CBS}} columns of Table 3 and Table 4 show that this trend continues for K∈{100,200,500}K \in\{100, 200, 500\}: at r=95%r = 95\%, the saving of ABS over CBS shrinks as KK 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 K=100K = 100, 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 r=95%r = 95\% is therefore larger at K=500K = 500 than at K=100K = 100 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 K=500K = 500 beam predictor has the lowest latency and the fewest SSD reads on all three datasets. In memory, its saving over ABS at K=500K = 500 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 K=100K = 100, over 10 random 50/50 splits of the queries (Table 5), and then at K=200K = 200 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 (K=100K = 100), 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.

SIFT100MDEEP100MMSSpaceV100M
Target recall rr (%)909590959095
Spearman’s ρ\rho of L^\widehat{L} vs. L⋆L^\star
training half0.630.780.670.770.410.74
test half0.630.780.660.770.400.74
Calibration: test recall (%)
mean over splits90.0094.9989.9794.9490.0295.02
worst split, ∣recall−r∣\lvert\text{recall} - r\rvert0.410.210.380.260.450.22
Cost vs. CBS at equal recall (%)
beam predictor−4.8−10.0−4.7−10.3−6.8−23.7
&nbsp;&nbsp;&nbsp;&nbsp;no trajectory features−4.5−9.4−4.3−9.1−6.5−22.1
&nbsp;&nbsp;&nbsp;&nbsp;trajectory features only−4.1−8.6−3.3−7.5−5.8−21.2
&nbsp;&nbsp;&nbsp;&nbsp;dKd_K 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 L⋆L^\star: 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 r=90%r = 90\% 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 rr 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-KK distance dKd_K, 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 K=100K = 100, 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 tt-value of each feature in the weighted regression at every KK and rr. The trajectory feature c90 gains weight as KK grows: for example, at r=95%r = 95\%, its tt-value rises from 6.2 to 19.4 to 34.1 on SIFT100M. Because the features are correlated, a tt-value measures a feature’s contribution given the others; Table 7 measures the effect of removing feature groups on cost.

KKrrd1d_1dKd_Kmeanstdsdpc90
SIFT100M
100902.8−12.413.42.8−10.86.0
100951.0−15.216.82.2−16.66.2
200902.9−7.07.51.6−3.46.5
200952.9−15.316.63.9−9.919.4
500950.7−8.28.91.94.434.1
DEEP100M
100905.4−17.918.97.3−10.25.2
100954.9−22.624.19.5−16.07.0
200904.3−14.114.95.82.916.2
200953.5−24.326.09.4−2.618.1
500950.2−13.515.02.525.940.4
MSSpaceV100M
100904.8−0.81.8−3.2−17.0−12.1
100956.7−23.926.68.3−40.8−2.4
200905.11.9−1.0−4.2−10.8−5.6
2009510.4−29.131.412.6−47.68.2
5009510.4−37.440.916.4−27.037.1

Table 6. tt-values of the six features in the weighted regression on log⁡L⋆\log L^\star (in-memory sorted graph, mean over 10 random 50/50 query splits).

KKrrBPno traj.traj.dKd_K
SIFT100M
10090−4.8−4.5−4.1−3.1
10095−10.0−9.4−8.6−6.4
20090−1.4−1.3−1.0−0.7
20095−8.5−8.2−7.3−5.2
50095−5.2−4.7−4.8−2.7
DEEP100M
10090−4.7−4.3−3.3−1.9
10095−10.3−9.1−7.5−4.6
20090−2.5−2.3−1.8−1.0
20095−8.9−8.1−6.6−4.3
50095−5.7−5.1−4.5−2.3
MSSpaceV100M
10090−6.8−6.5−5.8−4.5
10095−23.7−22.1−21.2−14.6
20090−2.3−2.1−1.8−1.4
20095−19.3−17.3−16.8−9.9
50095−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; dKd_K: dKd_K only.

Larger KK. The conclusions hold at K=200K = 200 and 500 (Table 8, Table 6 and Table 7). The mean test recall is within 0.06 points of rr, 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 r=95%r = 95\%, and lower at K=200K = 200 and r=90%r = 90\%: 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 α\alpha-reachable graphs, which include the graphs built by DiskANN’s slow preprocessing. On α\alpha-reachable graphs, ABS with parameter γ\gamma returns neighbors within a factor α+1α(γ+1)−1\frac{\alpha+1}{\alpha(\gamma+1)-1} of the true ones for any metric, and on sorted α\alpha-reachable graphs under the ℓ2\ell_2 metric the factor improves to max⁡(αα(γ+1)−1,α2+1α2(γ+1)−1)\max\left(\frac{\alpha}{\alpha(\gamma+1)-1},\frac{\alpha^2+1}{\alpha^2(\gamma+1)-1}\right). 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 γ\gamma, and the graph built with sorted pruning reaches a higher recall than the one built with shuffled pruning at every γ\gamma, 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 K=100K = 100 to 4.6–5.6% for K=500K = 500. 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 α\alpha-reachable and sorted α\alpha-reachable graphs, such as those built by DiskANN’s slow preprocessing, whose naive construction takes O(n3)O(n^3) 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 ℓ2\ell_2 datasets of 100 million points.

Future work. Evaluating beam predictor on more datasets, distance functions and values of KK, 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 ℓ2\ell_2 metric on sorted α\alpha-reachable graphs, D(q,v)/D(q,ai)≤α/(α(γ+1)−1)D(q,v)/D(q,a_i) \le\alpha/(\alpha(\gamma+1)-1).

Sorted α\alpha-reachability adds the constraint D(v,t1)≤D(v,ai)D(v,t_1) \le D(v,a_i), giving the optimization

max⁡D(q,v)D(q,ai)s.t.(γ+1)⋅D(q,v)≤D(q,t1),α⋅D(t1,ai)≤D(v,ai),D(v,t1)≤D(v,ai).\begin{aligned} \max\quad& \frac{D(q,v)}{D(q,a_i)} \\ \text{s.t.}\quad& (\gamma+1)\cdot D(q,v) \le D(q,t_1),\\ & \alpha\cdot D(t_1,a_i) \le D(v,a_i),\\ & D(v,t_1) \le D(v,a_i). \end{aligned}

The objective and constraints depend only on ratios of DD, so the problem is invariant under positive scaling. Without loss of generality fix D(q,ai)=1D(q,a_i)=1, which we further relax to D(q,ai)≤1D(q,a_i)\le1 (any feasible solution with D(q,ai)<1D(q,a_i)<1 can be rescaled to increase the objective while preserving the constraints). The optimization becomes

max⁡D(q,v)s.t.(γ+1)⋅D(q,v)≤D(q,t1),α⋅D(t1,ai)≤D(v,ai),D(v,t1)≤D(v,ai),D(q,ai)≤1.\begin{aligned} \max\quad& D(q,v) \\ \text{s.t.}\quad& (\gamma+1)\cdot D(q,v) \le D(q,t_1),\\ & \alpha\cdot D(t_1,a_i) \le D(v,a_i),\\ & D(v,t_1) \le D(v,a_i),\\ & D(q,a_i) \le1. \end{aligned}

For Euclidean metric DD and squaring the terms of the optimization problem, we obtain a semi-definite program:

max⁡∥q−v∥2s.t.(γ+1)2⋅∥q−v∥2≤∥q−t1∥2,α2⋅∥ai−t1∥2≤∥v−ai∥2,∥v−t1∥2≤∥v−ai∥2,∥q−ai∥2≤1.\begin{aligned} \max\quad& \lVert q-v\rVert^2 \\ \text{s.t.}\quad& (\gamma+1)^2\cdot\lVert q-v\rVert^2 \le\lVert q-t_1\rVert^2,\\ & \alpha^2\cdot\lVert a_i-t_1\rVert^2 \le\lVert v-a_i\rVert^2,\\ & \lVert v-t_1\rVert^2 \le\lVert v-a_i\rVert^2,\\ & \lVert q-a_i\rVert^2 \le1. \end{aligned}

Let the Gram matrix X=Gram⁡(q,v,t1,ai)⪰0X=\operatorname{Gram}(q,v,t_1,a_i)\succeq0. For brevity set t=t1t=t_1, a=aia=a_i, and τ=γ+1\tau=\gamma+1.

SDP primal.

p∗=max⁡  qq+vv−2qvs.t.(τ2−1)qq+τ2vv−tt−2τ2qv+2qt≤0,(α2−1)aa+α2tt−2α2at−vv+2av≤0,tt−2vt−aa+2av≤0,qq+aa−2aq≤1,X⪰0.\begin{aligned} p^* &= \max\; qq+vv-2qv\\ \text{s.t.}\quad&(\tau^2-1)qq+\tau^2vv-tt-2\tau^2qv+2qt\le0,\\ &(\alpha^2-1)aa+\alpha^2tt-2\alpha^2at-vv+2av\le0,\\ &tt-2vt-aa+2av\le0,\\ &qq+aa-2aq\le1,\\ &X\succeq0. \end{aligned}

SDP dual.

d∗=min⁡ y4d^* = \min\ y_4
s.t.∑iyiAi−M⪰0,yi≥0,\begin{aligned} \text{s.t.}\quad&\sum_i y_i A_i - M \succeq0,\\ &y_i \ge0, \end{aligned}

where

X=[qqqvqtqavqvvvtvatqtvtttaaqavataa],M=[1−100−110000000000],X = \begin{bmatrix} qq & qv & qt & qa\\ vq & vv & vt & va\\ tq & tv & tt & ta\\ aq & av & at & aa \end{bmatrix}, \qquad M = \begin{bmatrix} 1 & -1 & 0 & 0\\ -1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix},

the four primal constraint matrices and their right-hand sides are

A1=[τ2−1−τ210−τ2τ20010−100000],A2=[00000−10100α2−α201−α2α2−1],A_1 = \begin{bmatrix} \tau^2-1 & -\tau^2 & 1 & 0\\ -\tau^2 & \tau^2 & 0 & 0\\ 1 & 0 & -1 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}, \qquad A_2 = \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & -1 & 0 & 1\\ 0 & 0 & \alpha^2 & -\alpha^2\\ 0 & 1 & -\alpha^2 & \alpha^2-1 \end{bmatrix},
A3=[000000−110−110010−1],A4=[100−100000000−1001],A_3 = \begin{bmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & -1 & 1\\ 0 & -1 & 1 & 0\\ 0 & 1 & 0 & -1 \end{bmatrix}, \qquad A_4 = \begin{bmatrix} 1 & 0 & 0 & -1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ -1 & 0 & 0 & 1 \end{bmatrix},
b1=b2=b3=0,b4=1.b_1=b_2=b_3=0,\quad b_4=1.

Substituting the AiA_i’s, the dual feasibility constraint is equivalent to

Y=[(τ2−1)y1+y4−1−τ2y1+1y1−y4−τ2y1+1τ2y1−y2−1−y3y2+y3y1−y3−y1+α2y2+y3−α2y2−y4y2+y3−α2y2(α2−1)y2−y3+y4]⪰0.Y = \begin{bmatrix} (\tau^2-1)y_1+y_4-1 & -\tau^2y_1+1 & y_1 & -y_4\\ -\tau^2y_1+1 & \tau^2y_1-y_2-1 & -y_3 & y_2+y_3\\ y_1 & -y_3 & -y_1+\alpha^2y_2+y_3 & -\alpha^2y_2\\ -y_4 & y_2+y_3 & -\alpha^2y_2 & (\alpha^2-1)y_2-y_3+y_4 \end{bmatrix} \succeq0.

Dual certificate. We exhibit a dual-feasible point:

y1=ατ(ατ−1),y2=α(ατ−1)(α(τ2+1)−τ),y_1=\frac{\alpha}{\tau(\alpha\tau-1)},\qquad y_2=\frac{\alpha}{(\alpha\tau-1)(\alpha(\tau^2+1)-\tau)},
y3=αα(τ2+1)−τ,y4=(αατ−1)2.y_3=\frac{\alpha}{\alpha(\tau^2+1)-\tau},\qquad y_4=\left(\frac{\alpha}{\alpha\tau-1}\right)^2.

All four values are positive in the parameter range τ≥1\tau\ge1 that is relevant here. Substituting gives

Y=[ατ2+α−ττ(ατ−1)2−1ατ−1ατ(ατ−1)−α2(ατ−1)2−1ατ−1τατ2+α−τ−αα(τ2+1)−τα2τ+α−τ(ατ−1)(ατ2+α−τ)ατ(ατ−1)−αα(τ2+1)−τα2τ(ατ2+α−τ)−α3(ατ−1)(α(τ2+1)−τ)−α2(ατ−1)2α2τ(ατ−1)(ατ2+α−τ)−α3(ατ−1)(α(τ2+1)−τ)α4τ(ατ−1)2(ατ2+α−τ)].Y = \begin{bmatrix} \frac{\alpha\tau^2+\alpha-\tau}{\tau(\alpha\tau-1)^2} & -\frac{1}{\alpha\tau-1} & \frac{\alpha}{\tau(\alpha\tau-1)} & -\frac{\alpha^2}{(\alpha\tau-1)^2}\\ -\frac{1}{\alpha\tau-1} & \frac{\tau}{\alpha\tau^2+\alpha-\tau} & -\frac{\alpha}{\alpha(\tau^2+1)-\tau} & \frac{\alpha^2\tau+\alpha-\tau}{(\alpha\tau-1)(\alpha\tau^2+\alpha-\tau)}\\ \frac{\alpha}{\tau(\alpha\tau-1)} & -\frac{\alpha}{\alpha(\tau^2+1)-\tau} & \frac{\alpha^2}{\tau(\alpha\tau^2+\alpha-\tau)} & -\frac{\alpha^3}{(\alpha\tau-1)(\alpha(\tau^2+1)-\tau)}\\ -\frac{\alpha^2}{(\alpha\tau-1)^2} & \frac{\alpha^2\tau}{(\alpha\tau-1)(\alpha\tau^2+\alpha-\tau)} & -\frac{\alpha^3}{(\alpha\tau-1)(\alpha(\tau^2+1)-\tau)} & \frac{\alpha^4\tau}{(\alpha\tau-1)^2(\alpha\tau^2+\alpha-\tau)} \end{bmatrix}.

Setting

U=[1ατ−1α(τ2+1)−ττ−τα(τ2+1)−ταττα(τ2+1)−τ−α2ατ−1τα(τ2+1)−τ].U = \begin{bmatrix} \frac{1}{\alpha\tau-1}\sqrt{\frac{\alpha(\tau^2+1)-\tau}{\tau}}\\ -\sqrt{\frac{\tau}{\alpha(\tau^2+1)-\tau}}\\ \frac{\alpha}{\tau}\sqrt{\frac{\tau}{\alpha(\tau^2+1)-\tau}}\\ -\frac{\alpha^2}{\alpha\tau-1}\sqrt{\frac{\tau}{\alpha(\tau^2+1)-\tau}} \end{bmatrix}.

one verifies by direct computation that Y=UU⊤Y = UU^{\top}; hence Y⪰0Y \succeq0 and the chosen (y1,y2,y3,y4)(y_1, y_2, y_3, y_4) is dual-feasible. By weak duality,

p⋆≤d⋆≤y4=(αα(γ+1)−1)2,p^\star\le d^\star\le y_4 = \left(\frac{\alpha}{\alpha(\gamma+ 1) - 1}\right)^2,

and taking square roots recovers the bound D(q,v)/D(q,ai)≤α/(α(γ+1)−1)D(q,v)/D(q,a_i) \le\alpha/(\alpha(\gamma+ 1) - 1) 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@KK over the test queries, which are the same in every run.

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [14]Masajiro Iwasaki. NGT: Neighborhood graph and tree for indexing high-dimensional data. https://github.com/NGT-labs/NGT, 2015.
  15. [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. [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. [17]Thijs Laarhoven. Graph-based time-space trade-offs for approximate near neighbors. arXiv preprint arXiv:1712.03158, 2017.DOI
  18. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_btu5a39w
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

AI assistants

View statement
Looking for related papers…
Contents