Thank you for the feedback. We respond to specific questions below:

W1: We can add further discussion of the equivalence. In short, for standard beam search, if at any point a node is in the $(b+1)$st or higher position in $\mathcal{C}$, it will never be “explored”. In particular, this means that at least $b$ other nodes are closer to the query, so the termination condition is guaranteed to trigger immediately if that node is ever popped off $\mathcal{C}$. Accordingly, the neighbors of a node not currently in the top $b$ are never added to $\mathcal{C}$. Moreover, for this reason, the method does not change if the length of $\mathcal{C}$ is truncated to $b$, which is the more standard implementation suggested by the reviewer. We hope this clarifies any confusion.

W2: We do not claim splitting into two queues as a contribution. We view this as more of an implementation detail. As for “decoupling” into a search order + termination rule, it does seem that [2] shares this perspective, and we will be sure to add a citation. To be clear, in the paper we wrote: “We suspect the “decoupled view” of beam search is not novel, but we have not seen it presented”. The main novelty in our paper is observing that a simple alternative to the beam search termination criteria yields strong provable approximation guarantees when run on navigable graphs, and these guarantees also translate into better empirical performance.

W3: We have not, but it is an interesting direction for future work. We value the simplicity of Adaptive Beam Search (which, like standard beam search, only involves a single hyperparameter). However, multiple phases could indeed be helpful.

W4: The x-axis of all plots is on a log scale, so typical improvements range between a 10% and 50% reduction in distance computations. We consider this significant for a problem of such practical importance, especially given that Adaptive Beam Search is a very light-weight, simple to implement modification of Beam Search. That said, we do think there is room for further improvement! We did not notice a strong correlation with the improvement and $k$, although we agree that this is worth exploring more. We did notice that some datasets resulted in very little differences between the methods. MNIST is a good example. We believe this is because most MNIST queries have a very close nearest neighbor in the dataset. For such queries, even basic greedy search should perform quite well (indeed, basic greedy search always succeeds on a navigable graph if the query is exactly in the dataset). This leaves little room for improvement for Adaptive Beam Search or standard beam search for datasets like MNIST, so it makes sense that they perform similarly.

W5: It is important to point out that local optima are an issue even in navigable graphs – standard greedy search is not guaranteed to return a good approximate nearest neighbor. Thus, the main goal of Adaptive Beam Search is to escape local minima exactly as the reviewer described. It does so by also “enlarging the queue”, just like standard beam search. The difference is that the amount of enlargement is “adaptive” rather than restricted to a fixed upper limit, b. As illustrated in Figure 1, this allows Adaptive Beam Search to spend more effort on more challenging queries. We can add more discussion about this intuition in the paper.

W6: Thanks for the question – we will clarify this example. We agree that the current explanation is incomplete. To be more concrete, have the points $y_1,...,y_m$ all be equidistant from the query point $q$ (with distance $1.01$). Have $y*$ be the closest point in $y_1,...,y_m$ to $x*$. Have $y*$ connected to $x*$ and all $y_1,...,y_m$ points connected to each other. We can check that this graph is navigable. However, suppose we start search at $y_1$. $x*$ will only ever be found if we explore its neighbor $y*$. We won't do so in standard beam search with beam width $< \Omega(m)$ if we assume node ids are arbitrary (since $y*$ will not be preferenced for exploration over any of $y_1$'s $m$ other neighbors).

W7: Any $\alpha$-shortcut reachable graph for any $\alpha \geq 1$ (which is the relevant parameter regime studied in prior work) is also navigable. In particular, the existence of $z$ with $\alpha d(z,y) < d(x,y)$ implies the existence of $z$ with $d(z,y) < d(x,y)$. Thus, it is always possible to construct a navigable graph at least as sparse as any $\alpha$-shortcut reachable graph (take the $\alpha$-shortcut reachable graph itself). In many cases, navigability allows for much higher levels of sparsity. E.g., in Appendix A.2, we discuss random point sets for which any $\alpha$-shortcut reachable graph for fixed $\alpha > 1$ requires $\Omega(n^2)$ edges. At the same time, by citation [12] in the paper, there exist navigable graphs with just $O(n^{3/2})$ edges for these (and all) point sets.

Thank you for the positive feedback. Answers to specific comments and questions are below:

Re: Query Complexity Bound. We think Claim 2 (the beam search lower bound) is comparable to Theorem 1 in the following sense: Theorem 1 shows that we can obtain a provable approximation bound when the Adaptive Beam Search method is run with a fixed relaxation parameter that only depends on the desired approximation quality. On the other hand, Claim 2 shows that, setting the beam width $b = c*k$ for essentially any reasonable factor $c > 1$ won’t guarantee that a good approximation is returned from standard beam search. Indeed, if $b = n$, then beam search performs an exhaustive search, and our lower bound holds all the way up to $b = n-3$. The goal was to rule out the existence of a comparable result to Theorem 1 for standard beam search – e.g., we rule out results of the flavor “setting $b = (1+\gamma)*k$ yields to a $1/\gamma$-approximation.”

That said, it is interesting to ask about both upper and lower bounds on number of distance computations (which we believe is what the reviewer means by query complexity?). It is possible to construct adversarial navigable graphs for which even Adaptive Beam Search requires many distance computations. For example, consider points arranged along a one-dimensional line. If these points are connected via a bidirectional path, the resulting graph is navigable. However, a typical query (even when the query point is in the dataset) will require $\Omega(n)$ distance computations to answer.

Nevertheless, as discussed in our response to Reviewer gJ9t03, citation [12] in the paper shows how to construct sparse navigable graphs with "low depth" – i.e., greedy search terminates in just two steps for queries that are in the dataset. This implies sublinear query complexity on average for query points in the dataset. Thus, there is hope to give query/computational complexity upper bounds for sparse navigable graphs satisfying such a low-depth or related condition. We believe this would be an exciting direction for future work.

Re: Greedy Search in experiments. We did not include greedy search in our plots since there is not a natural way to trade-off between distance computations and recall. Indeed, greedy search is a special case of beam search with $b = k$ or Adaptive Beam Search with $\gamma = 0$. In this sense, it produces a single point to the far left of the curves for Adaptive Beam Search and Standard Beam Search, which often has such low recall, it would be off the charts. That said, we think this point is worth emphasizing, so will consider including some annotation for the plots to indicate what specific distance computation/recall point greedy search would have produced.

Re: Adaptive Search V2. Another reviewer commented on this as well, and the point is well taken. We will either appendicize or remove entirely.

We thank the reviewer for their helpful feedback and address specific concerns and questions below.

W1: This is true, however, given the diversity of graph construction algorithms, any broadly applicable theoretical results for graph-based near neighbor search will necessarily need to make some assumptions about the resulting graph produced. We believe that navigability is a reasonable assumption since 1) it is explicitly discussed as a target/inspiration for these heuristic graph constructions, 2) sparse navigable graphs are known to exist for all datasets [12], and 3) our method gives performance improvements not just on navigable graphs but on these popular heuristic constructions, evidencing that our theoretical results are still informative in practice. Prior theoretical results, such as those of Indyk and Xu, NeurIPS 2023 for graph-based near neighbor search require strictly stronger assumptions on the underlying graph, in particular, $\alpha$-shortcut reachability.

W2 (1): All of the plots in the experiments section that plot recall vs. distance computations explore the effect of varying $\gamma$: we obtain these plots by starting with a small value for $\gamma$ and increasing its value in small increments, which strictly increases both the number of distance computations and the recall. For example, the first plot in Figure 2 uses gamma values ranging between .1 and .65. Nevertheless, we agree with the reviewer that it would be helpful to clarify this point in the writing. We propose to add annotations to the points on a few of the plots showing what choice of gamma led to what point.

W2 (2) and Q1: We were able to run comparisons with the Fabian Groh et. al paper. Thank you for pointing this paper out – we were unaware of the method. Indeed, that paper uses an additive instead of a multiplicative slack factor. While we cannot share new plots due to the rules for this year’s rebuttal, in our experiments, the Groh et. al method usually performs somewhere in between our adaptive beam search and regular beam search. There are a few exceptions: for some datasets (e.g., SIFT) it performs worse than beam search on some graphs (in contrast, our Adaptive Beam Search always performs better than standard beam search). We also note that, for MNIST, the Groh et. al method performs very close to our Adaptive Beam Search, which we attribute to the fact that the nearest-neighbor distance in this dataset is fairly uniform. In this case, a multiplicative vs. additive slack factor should behave fairly similarly. We will plan on adding these plots to the paper, as we believe they strengthen our work.

Concerning a comparison to the method in [33], we have run experiments on the method in the past. Unfortunately, we found the method to be finicky and difficult to get good results on a variety of graphs and datasets. This seems to be due to a critical choice of hyperparameter that is difficult to estimate from the training data. We did not wish to include these results (which show [33] performing poorly in most scenarios) in case there is some implementation issue on our end. We would be happy to contact the authors to discuss the method so that we can include it for comparison. However, we do want to emphasize that we believe simple methods like standard beam search, Adaptive Beam Search, and the Groh et al. method are worth considering regardless of approaches like [33], which requires a training period and expects temporal consistency between queries to make the learned stopping rule meaningful in the future. In our experience, the simpler methods are more widely adopted in practice due to their robustness and ease of implementation.

W3: The referenced Jiadong et al. paper came out after we made this submission. We did not ignore it – indeed, we have an email thread discussing the work! We are happy to continue considering that work, but do not have time to do a full experimental comparison during the short rebuttal period.

Q2: Parameters for the graph construction methods are included in Appendix B, Table 3. Let us know if there are other parameters you are interested in.

Thank you very much for the positive feedback. The comments on presentation are helpful, and we will include the reviewer’s suggestions in the next draft. We will also consider moving Adaptive Beam Search V2. Indeed, this method is a relic of explorations from early stages of this project. Given its poor performance, moving it to an appendix probably makes sense.

In response to the question about implementation: all search algorithms were implemented from scratch. For the graph constructions (HNSW, NSG, Vamana, and EFANNA) some were implemented from scratch and some used existing codebases – see Appendix B.3 for details. Thanks for the suggestion about integrating the method into FAISS – this is definitely something we will consider.

Thank you for the positive feedback and useful questions. We address the specific questions below:

Question 1. We also became aware of this paper after our submission, and plan to add a citation. Basically, the paper generalizes the cited work of [Indyk, Xu, NeurIPS 2023] to approximate $k$-nearest neighbors for $k > 1$. What is called “beam search” in that paper is equivalent to what we call “classic greedy search”, since the beam width is set exactly equal to $k$, the number of nearest neighbors desired.

We believe that, like the Indyk-Xu work, the referenced work is complementary to ours. It also provides a multiplicative error guarantee (as well as a stronger convergence time bound). However, the bounds in these papers apply only when G is $\alpha$-shortcut reachable for $\alpha$ strictly greater than 1. In particular, their error bound is of the form $(\alpha+1)/(\alpha-1)$ for general metrics, so it becomes vacuous when $\alpha = 1$, which corresponds to the navigability property. In general, $\alpha$-reachability is a much stronger property than navigability when $\alpha > 1$: as discussed in Section 2, navigable graphs with sublinear sparsity have been shown to exist for any dataset, whereas it is easy to construct datasets where any $\alpha$-reachable graph requires $O(n^2)$ edges, and thus does not admit fast search, even if the search converges quickly – see our Appendix A.2 for more detail. We thus think it is valuable to study guarantees for approximate neighbor search under the weaker notion of navigability.

Perhaps as further reason to study navigability, recent work by Conway et al. “Efficiently Constructing Sparse Navigable Graphs” and Khanna et al. “Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness” both study algorithms for finding minimum sparsity navigable and $\alpha$-shortcut reachable graphs. Based on the results of these papers, it seems that finding a minimum sparsity navigable graph for a given point set is an easier problem than finding a minimum sparsity $\alpha$-shortcut reachable graph.

Finally, we find it interesting that our bounds require some sort of relaxation on greedy search. As mentioned, the referenced work and that of Indyk-Xu both obtain the same guarantees even when running beam search with $b = k$ (i.e., running classical greedy search). While very nice results, these bounds thus do not provide theoretical evidence for why a choice of beam width larger than $k$ (or, in our case, $\gamma > 0$) is critical to good performance in practice.

Question 2. Strictly speaking, navigability itself is indeed too weak a notion to prove convergence guarantees. Consider e.g., $n$ points arranged on a line, connected with a bi-directional path. This is a navigable graph, but if the query is on one end of the line and the starting vertex is on the other, convergence may require $n$ steps.

Nevertheless, citation [12] in the paper shows that it is possible to construct sparse navigable graphs with “depth 2”, meaning that greedy search converges in just two steps if the query is in the dataset. We agree that a very interesting future direction would be to see if properties like low-depth can be leveraged to prove fast convergence for queries not in the dataset (for which the goal is to return an approximate solution). We do not see any inherent barriers to doing so.

Question 3. Yes, you are correct. The cited result proves convergence for standard beam search for $\alpha$-shortcut reachable graphs. Our perspective on this is as follows: if you want the flexibility to work with navigable graphs (which are in general sparser and easier to find) you need to look beyond standard beam search. As mentioned in the response to Question 1, $\alpha$-shortcut reachability seems to be stronger than what is achieved by heuristic graph constructions used in practice – indeed for these constructions, beam width $> k$ is generally required for good performance. However, the cited result proves convergence results for $\alpha$-shortcut reachable graphs even for beam width $k$ (i.e., classic greedy search).

Question 4. This is a good question – we do not immediately see how to do this. In our implementation, however, data structures only factored minimally into total runtime, which was dominated by distance/inner product computations. Note that the second priority queue ($\mathcal{B}$ in Algorithm 2) has size bounded by $k$, the number of target nearest neighbors. Since $k$ is typically rather small, the data structure is inexpensive to maintain.