Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations
Authors: Piotr Indyk
Haike Xu
Venue: NeurIPS 2023 poster (2023)
Keywords: Nearest neighbor search; graph-based algorithms; worst-case analysis

Abstract: Graph-based approaches to nearest neighbor search are popular and powerful tools for handling large datasets in practice, but they have limited theoretical guarantees. 
We study the worst-case performance of recent graph-based approximate nearest neighbor search algorithms, such as HNSW, NSG and DiskANN. For DiskANN, we show that its "slow preprocessing'' version provably supports approximate nearest neighbor search query with constant approximation ratio and poly-logarithmic query time, on data sets with bounded "intrinsic'' dimension. 
For the other data structure variants studied, including DiskANN with "fast preprocessing'',  HNSW and NSG,  we present a family of instances on which the empirical query time required to achieve a "reasonable'' accuracy is linear in instance size. For example, for DiskANN, we show that the query procedure can take at least  $0.1 n$ steps on instances of size $n$ before it encounters any of the $5$ nearest neighbors of the query.

Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations
Piotr Indyk
Haike Xu MIT
MIT indyk@ @ mit.edu
haikexu @ mit.edu
Abstract
Graph-based approaches nearest neighbor search are popular and powerful tools for handling large datasets in practice, but they have limited theoretical guarantees. We study the worst-case performance of recent graph-based approximate nearest neighbor search algorithms, such as HNSW, NSG and DiskANN. For DiskANN, we show that its "slow preprocessing" version provably supports approximate nearest neighbor search query with constant approximation ratio and poly-logarithmic query time, on data sets with bounded "intrinsic" dimension. For the other data structure variants studied, including DiskANN with "fast preprocessing", HNSW and NSG, we present family of instances on which the empirical query time required to achieve a "reasonable" accuracy is linear in instance size. For example, for DiskANN, we show that the query procedure can take at least 0.1n steps on instances of size before it encounters any of the 5 nearest neighbors of the query.
Introduction
The nearest neighbor search (NN) problem is defined as follows: given set of n points P in a metric space (X, D), build a data structure that, given any query point g E X, returns p E closest to g. More generally, given parameter k, the data structure should report & points in P that are closest to q. Often, though not always, the metric space is a d-dimensional vector space with the distance function induced by the Euclidean norm. Since its introduction in the influential book by Minsky and Papert in the 1960s B1J, the problem has found a tremendous number of applications in machine learning and computer vision [34]. In most of those applications, the underlying metric is induced by a set of points in a high-dimensional space. Since in this setting worst-case efficient nearest neighbor algorithms unlikely exist (see e.g., (2). various approximate formulations of the problem have been studied extensively. One popular formulation allows the algorithm to return any point p' P whose distance to the query q is at most times the distance between & and its true nearest neighbor in P; such point y/ is called c-approximate nearest neighbor. In practice the accuracy of an approximate data structure is often evaluated by estimating the recall, i.e., the average fraction of the true & nearest neighbors returned by the data structure.
Over the last few decades, many nearest neighbor data structures have been proposed, both exact and approximate. The most popular classes of data structures are tree algorithms (e.g., kd-trees [4);; locality sensitive hashing [I: learning-to-haat and product quantization 335 36 and metric data structures. The last class includes algorithms that work for point-sets in arbitrary metrics, not just those in d-dimensional vectors normed spaces. This category be further subdivided into algorithms based on metric trees 6 32), divide and conquer algorithms
[4] [ [0], and methods
based greedy search in proximity graphs 3 28
15
21
See the surveys
27 for further
overview these classes of algorithms.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Several algorithms in the latter class, such as HNSW 28) NSG [5] and DiskANN [2I]. are widely used in practice| They have been recently shown empirically to provide excellent tradeoffs between accuracy and query speed [27]. Their design is based on approximating theoretical concepts such as Delaunay or Relative Neighborhood Graphs. However, their worst-case performance is not well understood, especially when the dimension is high. For example, the authors of (28) point out that "Further analytical evidence is required to confirm whether the resilience of Delaunay graph approximations generalizes to higher dimensional spaces." This stands in contrast to the older algorithms, e.g., those based on the divide and conquer approach, which come with worst-case performance guarantees. Those algorithms are typically analyzed under the assumption that the input point set P has low doubling dimension (a measure of the intrinsic dimensionality of the point- set and provide near-linear space and logarithmic query time bounds, with the big-Oh constants depending on the doubling dimension. This raises the question whether similar bounds can be obtained for the newer algorithms. On the practical side, investigating the worst-case behavior of data structures is important to understand their benefits and limitations.
Our results In this paper we initiate the study of the worst-case performance of the recent metric data structures based on proximity graphs. As in (21), mostly focus three popular algorithms and their implementations: HNSW, NSG and DiskANN. (In addition, we present similar results for other graph-based algorithms in the supplementary material section.) We present both upper and lower bounds on their worst-case search times. Our specific contributions are as follows:
For one of the data structures studied, namely DiskANN version with "slow preprocessing", we are able to show provable worst-case upper bound on its performance. Specifically, we show that (a) the greedy search procedure returns an c
Upper bounds:
a-1 ++) -ap-poxxmiaa neighbor in O (loga ra- steps and (b) each step takes at
most (((4a)) log A) time. This implies that the overall running time poly-logari in A when d is constant. Here a > 1 denotes a parameter of the DiskANN algorithm (described in Preliminaries, typically set to 2), d denotes the doubling dimension, while A denotes the aspect ratio of the input set P. i.e., the ratio between the diameter and the distance of the closest p We also show that our approximation bound is tight, and that the logarithmic dependence of the query time bound on A cannot be removed.
Lower bounds: For the other data structure variants studied (NSG, HNSW and DiskANN with "fast preprocessing") we present a family of point sets of size for all n large enough, such that for each n, the empirical query time required to achieve "reasonable" accuracy is linear in n. For example, for DiskANN, we show that the query procedure can take at least 0.1n steps before it encounters any of the 5 nearest neighbors of the query. Remarkably, the point sets are relatively simple: they live in 2-dimensional Euclidean space, and therefore have constant doubling dimension (see Preliminaries). We use implementations provided
by the authors. publicly available on GitHub [6 29 22 available on GitHub at [18].
Our hard instance examples are
To the best of our knowledge, these the first worst-case upper bounds and lower bounds for these data structures.
We emphasize that our results do not contradict the empirical evaluations given in the original papers, or in summary studies such as [27]. Indeed, these algorithms have been demonstrated to be very useful and can be highly effective in practice. Nevertheless, we believe that results provide important information about the behavior of these algorithms. For example, they demonstrate the importance of validating the quality of answers reported by the algorithms when applying them to new data sets. They also shed light on the types of data sets which result in suboptimal performance of the algorithms.
'E.g., DiskANN has been developed and used Microsoft and NSG at Alibaba. 2 IInfrrmall,, this means that any subset of points that falls into a ball of radius 2r can be covered using a constant number of balls of radius r. See Preliminaries for the formal definition and discussion.
'We note running time bounds that depend on log(2) versus those that depend on log(n) are incomparable. Although A could be much larger than n, we observed that its value is typically quite low. For example, the MNIST data set [26 g contains n = 60, 000 points, while its aspect ratio A is around 20 when the distances measured according to the Euclidean norm.
2

---

Related work Approximate nearest neighbor search has been studied extensively, the references in the introduction provide some of the main milestones of that rich body of research. In the context of this paper, we also mention 25 33 which studied theoretical properties of modern wraph-based nearest neighbor data structure. However, their focus is on the average-case performance, i.e., under the assumption that the data is generated according to some well-defined distribution, like uniform over the sphere. In contrast, this work is focused on the worst-case behavior of those algorithms, and show that their empirical running time can be high even for relatively simple 2-dimensional data sets.
2 Preliminaries
We denote the underlying metric space by (X, D). For any point p E X and radius r > 0, we use B(p,r) r) to denote ball of radius centered at p. ie., B(p,r) {o E X D(p,g) < r)
Consider a set of points P. We say that P has the doubling constant C if for any ball B(p, 2r) centered at some p E P. the set P n Bip, 2r) can be covered using at most C' balls of radius r, and C' is the smallest number with this property. Doubling constant dimensionality" of high dimensional point sets, see c.g., [17 24
popular measure of "intrinsic []. The value log, C' is called the doubling dimension of P. Doubling dimension often used as measure of the "intrinsic dimensionality" of a data set. It generalizes the "standard" (topological) dimension: for any data set
P = Ted equipped with metric D(p1, P2) IP1 P2llp- the doubling dimension of P is at most Od). However, the doubling dimension of P D could be much lower than D, e.g., points in P lie on low-dimensional manifold. The doubling dimension can be viewed as finite version of the fractal Hausdorff dimension. Empirical studies (e.g.. [IT] showed that the fractal dimension of real data sets is often smaller than their ambient dimension D.
The following fact is standard and follows from the definition.
Lemma 2.1. Consider a set of points P with doubling dimension d. For any ball B(p,r) r) centered at some E and a constant k, the set B(p, r) e P can be covered by a set of m & O(K4) balls with diameter smaller than r r/k; i.e. B(p,r)
= U B(p,rr/k)
We use d to denote the doubling dimension of the point set P, A Dmmx to denote the aspect ratio of Dinin
the input set P. where D Dmaz (Dmin) is the maximal (minimal) distance between any pair of vertices in the point set. For two points Tas Ze in P = (.n,, we use D(ra, to denote the distance between them, sometimes D(u v) for simplicity.
3 Analysis of DiskANN
In this section we show bounds on the performance of DiskANN with slow preprocessing.
3.1 DiskANN recap
In this section we give an overview of the DiskANN procedures. For the full description the reader is referred to the original paper (21), or section A (supplementary material).
The DiskANN data structure is based on a directed graph G over the set P, i.e., the set of vertices V of G are associated with the set of points P. After the graph is constructed, to answer given query the algorithm performs search starting from some vertex s. In what follows we describe the search and insertion procedure in more detail.
The search procedure, GreedySearch(s, q, L), has the following parameters: the start vertex s, the query point q, and the queue size L. It performs length L, until the L vertices v with the smallest value of D(v, q) seen so far are all scanned. Upon completion, it returns list of vertices in an increasing distance from where the first vertex (or the first k vertices) are answers for the query. Note that as long as the graph is connected, the procedure runs for at least L steps. The total running time of the procedure is bounded by the number of steps times the out-degree bound of the graph G.
sest-iiis-scaacch using queue of with a bounded
The construction of the graph G (V, E) is done by repeated invocation of a procedure called Robust Pruning. For any vertex v, a set of vertices U (specified later), and parameters a > 1 and R. Wowustrrrningeeeggo Pruning(e, v, U, a, R) proceeds as follows. First, the set U is sorted in the increasing order
3

---

of the distance to v. The algorithm traverses this sequence in order. After encountering a new vertex u, the algorithm deletes all other vertices w from U such that Du, w) node v is connected to all vertices in U that have not been pruned.
< De, w) Finally, the
The starting point of the DiskANN data structure construction algorithm is the following simple procedure: for each vertex e, execute Robust Iitasssruuue Pruning(1, U, R) with U = V and It = n. That is, robust pruning applied to all vertices the graph. We refer to this procedure as slow preprocessing, as it can be seen that a naive implementation of this method takes time O(n²). Although the construction time is slow, we show that this construction method provably constructs graph whose degree depends only logarithmically on the aspect ratio of the graph (assuming constant doubling dimension), and guarantees that the greedy search procedure has polylogarithmic running time. We note that this result is inspired by an observation in [2I] about convergence of greedy search in logarithmic number of steps, though to obtain our result we also need to bound the degree of the search graph and analyze the approximation ratio.
Since the www.--pprocessingalggonee heuristic method to construct the graph G, which we call fast preprocessing method. At the be- ginning, the graph G initialized be a random R-regular graph. Then the construction of the graph G (V, E) is done incrementally. The construction algorithms make two passes of the point set random order. For each vertex met, the algorithm computes a set of vertices U = GreedySearchh Zv, L) (for some starting vertex s) and then calls the pruning procedure on U, not V. That is. it executes RobustPruning u, U, a,,,,, R). After pruning insertion procedure adds both edges (v, and (u, v) for all vertices u U output by the prunning procedure. Finally, if the degree of any of E U exceeds threshold R, then the set of neighbors of is pruned via RobustPruningle Pruning(u. u, Nout (u), o R) as well. This construction method is implemented and evaluated in the paper.
is too slow in practice, the authors of [21] propose a faster
performed, the
3.2 Analysis: preprocessing
For the sake of simplicity, we let RobustPruninngas V,a) be the no-degree- limit version of edge selection, i.e., where R = n. We first analyze the property of graph constructed by the no-degree-limit pruning, and then show that setting R = O(44a) log A) yields equivalent results.
Definition 3.1 (a-shorteut reachability). Let reachable from a vertex p if for any other vertex q, either (p, q) E E, or there exists p' s.t. (p.p') E E and D(p's 9)) a & D(p, q). We say a graph G is a-shorteut reachable if G is a-shorteut reachable from any vertex U V.
1. We say a graph G EV) is a-shortcut
First, we show that the slow preprocessing algorithm constructs graph that is a-reachable. Lemma 3.2 (a-shorteut reachable). For each vertex p. if connect p. to the output of Robust Pruning(,, V, then the graph formed is a-shortcuut reachable.
Proof. By Definition 3.1 we only need to prove that the constructed graph is a-shortcut reachable from each vertex. Suppose that, for some vertex p, vertex q is not connected p. Then, in RobustPruning V,a), there must have existed vertex p' E V connected to p s.t. D(p', ,4) & D(p. //a.
Next, we show that the graph produced by no degree limit Robust is actually sparse. Lemma 3.3 (sparsity). For any vertex p. let U Robust (p, V, then |U] < (((a)) log A) where d is the doubling dimension of the point set P.
Proof. We use Röng(p, rı; r2) denote the set of vertices that lie in B(p, r2) but not in B(p, r1). We use Dmnn (Dmin) to denote the maximal (minimal) distances between a pair of vertices in the point set P and by definition A Dmas__ For each E [log2 A]. we consider Ring(p, Dmox/2', Dmax 2 separately. We cover Ring(p, D Dmaz/2', Dmma/ /2 using balls with radius D Dmax/a2 by Lemma 2.1 The number of balls required is bounded by (((4a))) Because every two points in the same ball have distance at most Dman/a2' from each other, and this value is a
"See the discussion in Section 2.2 of 211.

---

times smaller than their distance lower bound to at most one of them will remain after per- forming Robust Pruningg, a, Therefore, the number of vertices remain after performing RobustPruning(p: V, is upper bounded by O((a)) log A).
3.3 Analysis: query procedure
We now show that if the graph constructed using the slow indexing algorithm analyzed in the previ- ous section, then GreedySeared
q, 1) starting from any vertex returns an (24) >aapprxximate nearest neighbor from query in a logarithmic number of steps.
Theorem 3.4. Let G = (V, E) be an a-shortcut reuchable graph constructed using the slow preprocessing method. Consider GreedySearchí 8, 9, I.) starting with any vertex E V and I. =
(i.e., the algoritium performs no brck-tracking) answering query q. The algorithm finds an a+1 + + approximate nearest neighbor in O (log,. (a-1)e) steps.
Proof. Let be the nearest neighbor of q. Us be the i-th scanned vertex, d; = D(us, q), with We use Dmax to denote the aspect ratio of the vertex set. Dmin
approximate ratio G;
d:
D(a.g)
We know that the distance between 2 and is no more than dç + D(a, q) by triangle inequality, and because G is a-shorteut reachable, each v; either connected to a, or v; connected to a vertex o' whose distance to a is shorter than D(a.() In best-firtt-eearch, the next scanned vertex 4 should have distance from y no farther than v', which is at most 4+ D(a.g) D(a,g). q). By induction:
((s q) d, < a + a D(a,g)
a
Consider the following three cases, depending on the value of D(a, q):
Case (1): ()+,g)= > 2Dmax- In this case we have D(a, q) ((s, 9) D(a, 8) > Dss, () Dmarr > a+1
di D(s.g) + a-1 2 a+1 D(s,9)/2 Plugging this into inequality 1 gives us D(a.g) a:D(a.g)
Therefore, for any > 0, we get
a+1
approximate nearest neighbor in log, 2 steps.
Case (2): D(s,g) g) & 2D max and D(a g) & 4[ Dmin- By inequality 1 the algorithm reaches an (a+1 + -)aaprooxi nearest neighbor when D(s.g) < <D(, q). Substituting the value of D(s, g) and D(a, 4) with corresponding upper and lower bound, we obtain that the number of steps needed is log, 8(a+1)A (a-1)c & O (log, (a-1je
a-1
Case (3): D(s, 4) & 2Dma and D(a,g) g) < --- Dmnn- Suppose at step i, d, >> d(a, g) is not the 4[a+1]
nearest neighbor. Here obtain new lower bound for d, We know d(e;, a) Dmins d( 9) d(a, q). and d(a, 9) < Dmin- By triangle inequality, we have d; = d(v;, q) > d(u; a)/2 > D Dmnn/22 /2. Combing this with inequality [ we obtain that if v;
the exact nearest neighbor, must satisfy
Dusn & de < D(s.g) + Dt)D(a, q) & 2Dmas + Dania This can only happen when & log, 8A. Therefore, the algorithm reaches the exact nearest neighbor in O(log, A) steps.
We note that similar neighbor selection strategies in the greedy search procedure are also used in HNSW (8 and NSG [5]. However, we cannot prove query performance guarantees similar to the ones above, those algorithms
1.
3.4 A tight convergence rate lower bound for DiskANN
In this section we show that the logarithmic dependence of the query time bound on A is unavoidable, i.c. we cannot replace log A with logn. n. The proof is deferred to appendix B
Theorem 3.5. For any choice of a 1, there exists a set of = 2k: points on a one dimensional line with aspect ratio A O(a"), and a query q, such that after the slow preprocessing version of DiskANN, greedy search must scan least 22 A) or 12()) vertices before reaching an 0(1)- approximate nearest neighbor of q.
5

---

3.5 A tight approximation lower bound for DiskANN
In Theorem 3.4 we know that the slow preprocessing version of DiskANN algorithm can asymptoti- cally get to an a-1 approximate nearest neighbor. Here, we provide simple instance showing that this approximation ratio is tight.
++1
Figure 1: a+1 -approximation ratio lower bound instance for a-1 slow preprocessing version DiskANN. The whole instance can be embedded in two-dimensional grid using I distance, and therefore has a constant doubling dimension. Black dots (solid or hollow) points in the database, the red dot is -- the query point. Grids are only used to show the layout structure. Please refer Section 3.5 for detailed instance description.
1+
9
2
P
Po
Theorem 3.6. For any a > 1, there exists a set of n. + points in the two dimensional plane under I distance where the slow preprocessing version of DisKANN will scan at least verfices before getling to a vertex with an approximation ratio smaller than 9+11 a
approximate nearest neighbor.
We draw the instance in Figure I The whole instance be embedded in a two dimensional grid using 1 distance. Note that in the figure, grids are drawn to label distances and highlight the layout structure. The vertex set V consists of point set P and further consists of a /n x /n (we assume that n is a perfect square) square grid with grid length 0.5e where each grid point associated with a point. We denote the upper-rightmost point in P by po- yn
single points p' and a. The point set P
Some important distances are ((po, p') 2, D(p',
- D(po. a)
20 a-I D(a, q) +
D(po 9) --1 + +1 E, where 0.01.
Lemma 3.7. Some properties regarding the graph G (V, F.) built on the instance in Figure using the slow preprocessing version of DiskANN:
(1) For any pe E P. (p.1/) E and (p.a) $ E
(2) The subgraph of G induced by point set P S V is strongly connected.
(3) The starting verlex is in P.
Proof. (1): According to the l distance, we can see that for any point p P, D(p,p') > D(pu, p') 2 -
2 and D(p,a) > D(po, a) = 2
a-I' Therefore, in the procedure Robust Pruning(, V, the edge p') remains and edge (p, a) pruned.
2a and D(p', a) 2 a-1
(2): Because the point set P is uniform grid, we know that for each vertex p. the distances between p and its four adjacent vertices in the grid are smaller than to all other vertices and must remain after Robust Pruning( pp, V, V, Therefore the subgraph induced by the vertex set P in the final graph G is strongly connected.
(3): In the implementation DiskANN, the starting point is the closest vertex to the centroid of the whole vertex set, which lies in P.
I1
Now we analyze the behavior of rumning GreedySeerch((s. q. L) on the instance above on the graph constructed by DiskANN's slow version. We will show that the first n vertices entering the queue are all vertices the set P. Additionally, the only neighbor of set P. p', is further from y than any vertex in the set P. If L & Greedy
Proof of Theorem 3.6
L) terminates before getting to p' or a. Consequently, the nearest vertex returned by GreedySearchh q, L.) has distance apprrximmae nearest neighbor when approaches 0. at least a-I + from q, which is not a
a-1

---

The first vertex in the queue is 8 P. According to property (1) in Lemma 3.7 no vertex in P is
connected to a. any vertex p E P has distance D(p. q) D(p'. q) thus has higher priority to be scanned than p/, and the subset P is strongly connected, so in the first steps (recall that P| n). GreedySearchl q, L.) will always sean vertices P.
4 Experiments
our experiments, we test the performance of DiskANN, NSG, and HNSW, on two of our constructed
hard instances. We rum each algorithm on 20 different data sizes {10$, 2 10y 2 10%). Each data set consists of n points in the swo-dimensional plane. We plot Recall rates (Figures and (5)
and approximation ratios (Figure for answering the query with queue length L equal to pn where the percentage p is enumerated from the set 1%, 2%..... 12%, 15,, 18%, 20%, 30%, 40%, 50%. Note that for all graph-based nearest neighbor search algorithms, the value L lower bounds the number vertices scanned (and therefore the running time) of the algorithm.
Our results show that, unlike standard benchmarks, the algorithms scan at least 10% of the points our instances before finding quality nearest neighbors. All experiments were ran on Google Cloud. Since our experiments only use combinatorial measures of algorithm complexity (i.e., the number of vertices searched), the results do not depend on the exact details of the computer architecture.
4.1 Hard instance for DiskANN
Though we provide ( [+11
-approximate ratio upper bound for slow preprocessing version of DiskANN algorithm, in the experiments, we show that there exists family of instances where the DiskANN algorithm with fast preprocessing cannot reach any top 5 nearest neighbor before scanning 10% of the vertices. We test our constructed instance using the authors' DiskANN code (fast preprocessing) on GitHub [22 For comparison, also test constructed instance on implementation of the slow preprocessing DiskANN algorithm.
Figure 2: Our constructed hard instance for DiskANN for n = 105. The instance lives in two-dimensional Euclidean space, and therefore has a constant doubling dimension. Black dots (solid hollow) points in the database, the red dot is the query point. Grids only used to show the layout structure. See section 4.1 for detailed description and supplementary materials for its implementa- tion.
(-12000
(0.00
(0210))
(-101.0)
(0000. OF
In Figure 2 we draw our constructed instance for the DiskANN algorithm for = 106. It is easy to mimic this instance for other data sizes. The parameters used in our experiment are R = 70, L = 125 (suggested in the original DiskANN paper (21), section 4.1, for in-memory search experiments). a 2, nummtthreeeeeeee threads
In the left plot of Figure we can see that in most cases, DiskANN (fast preprocessing version) cannot achieve non-zero Recall @5 unless scanning least 10% of the vertex set. In the right plot of Figure 3 we can see that DiskANN (slow preprocessing version) generates very sparse graph data structure given our hard instance. Furthermore, after preprocessing, greedy search is very efficient: finds the exact nearest neighbor in only 2 steps! Overall, it can be seen that, on the hard instances proposed in this paper, the greedy search procedure for query answering is highly efficient after slow preprocessing, and slow (linear time) after fast preprocessing.
7

---

DisKANN
DisKANN (slow preprocessing!
2096
34-
18%
0.6
9%
36-
8%
Lio
17
6%
38-
27
15
n untu of 10 point
0108 UTICOT 1D 200E))
Figure 3: Results for both variants of the DiskANN algorithm on the instance in Figure 2 (fast preprocessing DiskANN): the horizontal axis represents the data size n. in multiples of 10 points. The vertical axis represents the size of the search queue length L in terms of the percentage of the data size. Each pixel represents the average value of Recoll @5 E [0. 1J over 10 runs of the algorithm. Note the sharp transation of the recall (from O to 1) for L R 10%. Right figure (slow preprocessing DiskANN): as indicated by Theorem 3.4 slow preprocessing DiskANN constructs a very efficient data structure. In the experiment, it finds the exact nearest neighbor in at most 2 steps of greedy search, with the vertical axis) vs. the data size n in multiples of 10' points (on the horizontal axis). The plot ends at 105, as the slow preprocessing algorithm takes several hundred hours for larger values of n.
Left figure
1. the figure we plot the maximum degree of the constructed graph (on
Description of instance in Figure 2 The instance lives in 2-dimensional plane under the la distance, so in what follows, we give the coordinates for each point, which defines the distances between all points. In Figure 2 n 10 the vertex set V consists of three sets of points M, P and P", of sizes 0.8n, 0.1n, 0.1n respectively, and a single answer point a. Let / = 0.01 * n = 10a. M is a V VIM x VIM square grid with grid side length whose bottom-right corner m (-1.21, 1.21). P is a Pl x vPPl square grid with grid side length I whose upper-right corner is p = (-1,0). Pr MP'l x / P square grid with grid side length and whose bottom-left corner is p (0, (). (We assume that M [P), [P'| are perfect squares.) The query point is q = (-0.41, 0), whose nearest neighbor is (0, 0.1)). Since experiments measure Recall @5, we add another 4 points very close to a, which is not shown in the figure for simplicity.
Intuition First, the start point should lie in the point set M. The three key properties we want to maintain in the construction of the graph are that (1) s is always connected to at least one vertex in the point sets P and P'. (2) Except for the points randomly connected to a at initialization, only the points in the set P can still have edges to at the end of the construction. (3) In the final graph, at least L vertices in set P are reachable from start point without passing through any vertex not in P. If these three properties hold, Greedy s, 9, L) scans only the vertices in P (except for the start point s) until it finds a vertex p. P which is randomly connected to at initialization. In expectation, this requires scanning 22 R) vertices, and DiskANN won't reach the nearest neighbor a before that. The actual running time of the code is even slower.
4.2 Hard instance for NSG and HNSW
A variant of the hard instance from the previous section works for NSG [15] and HNSW 22 algorithms as well. In Figure we draw this instance for n = 1 It is easy to mimic this instance for other data sizes.
The parameters of NSG are as follows. We set K 400, L 400, iter 12, S 15, R 100 for EFANNA 12 to construct the KNN graph. We set L = 60. R = 70, C = 500 for constructing NSG from KNN graph. These parameters were used by the authors when testing on GISTIM M dataset, whose size is similar to ours. The parameters of HNSW are as follows. eeomstruction 200 (as used in their example code), M 64 (maximal degree limit in their suggested range), num_ -hrendd We test our constructed instance using the authors' code available at [29 (for HNSW) and at [16]
8

---

1200000 13000)
Figure 4: Our constructed hard instance for NSG and HNSW algorithms for data size 10 The instance lives in two-dimensional Euclidean space, and therefore has a constant doubling dimension. Black dots (solid or hol- low) are points in the database, the red dot is the query point. Grids are only used to show the layout structure. See Section [.2 for detailed description and supplementary materials for its implementation.
(0,00))
1-100-0000 .0
1000.00
50%
30%
15%
75%
17%
17%
68
11%
11%
06
9%
9%
04
L
07
196
196
4%
46
10 12
15
1930
10 19:30
Figure 5: Results for running NSG and HNSW algorithm on instance in Figure The horizontal axis represents the data size n, in multiples of 10 points. The vertical axis represents the size of the search queue length I. in terms the percentage the data size. Fach pixel represents the average value of R5call@5 E [0, 1] over 10 runs of the algorithm. Since the algorithm is randomized, each run generates and uses a different random seed.
(for NSG). We note that both implementations are randomized, but their random seeds are hardwired into the code. To obtain more informative results, we generate and use different random seeds for each algorithm execution, and plot the average recall.
In Figure 5 we can see that, for most values n, both NSG and HNSW algorithms cannot achieve good Recall @5 unless scanning least 10% of the vertex set.
Description of instance Figure This instance is based on the instance in Figure 2 The main difference is that Specifically, on the dotted line, we add points uniformly spaced out, separated by a distance of 5 in 10t and / 0.01n 10a, the instance consists of 400(0.04%) points on the diagonal (from m = (-1.21, 1221--122 to (-1, -T)). 2000(0.29) on the horizontal line (from (-1, to pf (O.t)) and 2000(0.2%) points the vertical line (from (-1, to p (-1,0). 0)). ). In total, there are 4400 new added points on the chain compared with the previous instance, occupying 0.44% of the vertex set.
few chains of points to connect the three subsets M, P. and Pl
the horizontal and/or vertical directions. For
Intuition for the instance in Figure 4 The new added vertex chains are there to make KNN graph connected for those nearest neighbor algorithms using KNN as part of their constructions. Thanks to these chains, most of the vertices in subset P. and P' are reachable from the start point. The construction algorithm will only add edges from the vertices in the set P' to but not from P. Then,

---

GeachySearch query will first traverse the whole subset P before going to P Therefore, GreedySearch cannot get to the nearest neighbor if the queue length limit L is smaller than |P).
4.3 Cross-comparisons
We also evaluated DiskANN on hard examples for NSG and HNSW, and vice versa. For n = 10 the results similar to the ones reported in earlier sections: none of the algorithms achieve non-zero recall unless L exceeds 10% of the data set size. We did not experiment with other values of n, two different families of instances anyway helpful for other algorithms, outlined in the next section and described detail in supplementary material.
4.4 Evaluating approximation ratio of the algorithms
In addition to Recallã5, we also measure the average approximation ratio of DiskANN (fast preprocessing), NSG and HNSW on slightly modified hard instances from Figure 2 and 4 The modifications only involve scaling of the entire instance and bringing points and g closer, to amplify the approximate ratio for other points. As per Figure the average ratio very high unless L > 0.1n. Note that we do not include the plot for DiskANN (slow preprocessing) here because, shown in Figure that algorithm (with 1) can find exact nearest neighbor in two steps.
Disk-AN
NSG
HNSWW
459
40%-
30
(nn pier centare of m1
22%
3P
Apgros Radi
0%
Aggraz
0%
06
12 224547 B111000000011000
3 455
55666 8 500 00134455011000000
11 onttstsoo of poincs
5t uniss of 10 pointst
on unit of 10 ntst
Figure 6: Average approximation ratio results for running DiskANN (fast preprocessing), NSG, and HNSW algorithm on instances in Figure 2 and 4 multiples of 10 The vertical axis depicts the size L of the search queue, ratio to n. Each pixel represents the average approximation ratio over 10 runs of the algorithm. Since the algorithms are randomized, each run generates and uses different random seed.
The horizontal axis depicts the data size in
4.5 Experiments on other popular approximate nearest neighbor search algorithms
We also tested other popular approximate nearest neighbor search algorithms covered in the survey [37 NGT (20]. SSG [14], KGraph [37], DPG (27), NSW (30]. SPTAG-KIL KDD 7 and EFANNA [12]. We ran them on our hard instances, with n ranging over 10 2 10 2 10 and the queue length
I. The table depicts average Recall @ rates over values of n and 5 or 10 repetitions. One
can see that all algorithms achieve sub-optimal recall. See the appendix for more details.
DiskANN
NSG
HNSW
NGT
SSG
KGraph DPG
NSW SPTAG-KITT
EFANNA
0.0
0.27
0.1
0.05
0.16
0.42
0.37
0.02
0.02
0.12
Table I: Average 5 for the 10 algorithms surveyed in [37], our constructed instances.
Conclusions
In this paper study the worst-case performance of popular graph-based nearest neighbor search algorithms. We demonstrate empirically that almost all of them suffer from linear query times on carefully constructed instances, despite being fast benchmark data sets [37]. The exception is DiskANN with propppeppo.....nng for which we bound the approximation ratio and the running time. However, its super-lineat linerr preprocessing time makes it difficult to use for large data sets.
An important question raised by our work is whether there is a fast preprocessing algorithm, and a query answering procedure, that are empirically fast (e.g., fast for DiskANN) while having worst case query time and approximation guarantees. Another interesting direction investigate whether it is possible to replicate our findings for real data sets, using adversarially selected queries.
10

---

This work was supported by the Jacobs Presidential Fellowship. the NSF TRIPODS program (award DMS- NMS-2022448), Simons Investigator Award and MIT-IBM Watson AI Lab.
Acknowledgement:
References
[1] 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.
[2] Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. Approximate nearest neighbor search in high dimensions. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3287-3318. World Scientific, 2018.
[3] Sunil Arya and David M Mount. Approximate nearest neighbor queries in fixed dimensions. In SODA, volume 93, pages 271-280, 1993.
[4] 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), (5(66)891-922) 1998.
[5] Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceedings of the 23rd international conference on Machine learning, pages 97-104, 2006.
[6] Edgar Chávez, Gonzalo Navarro, Ricardo Yatea,Yates, and José Luis Marroquín. Searching in metric spaces. ACM compuling surveys (CSUR), 33(3):273-321, 2001.
[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 neighbor search. CoRR, abs/2111.08566, 2021.
[8] Kenneth L Clarkson et al. Nearest-neighbon searching and metric space dimensions. Nearest- neighbor methods for learning and vision: theory and practice, pages 15-59, 2006.
[9] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142 2012.
[10] Yury Elkin and Vitaliy Kurlin. A new near-linear time algorithm for k-nearest neighbor search using& a compressed cover tree. In International Conference on Machine Learning, pages 9267-9311. 1. PMLR, 2023.
[11] Christos Faloutsos and Ibrahim Kamel. Beyond uniformity and independence: Analysis of r-trees using the concept of fractal dimension. In Proceedings of the thirteenth ACM SIGACT- SIGMOD-SIGART symposium on Principles of database systems, pages 4-13, 1994.
[12] Cong Fu and Deng Cai. EFANNA An extremely fast approximate nearest neighbor search algorithm based on knn graph. CoRR, abs/1609. hess/1609.7722/. 2016.
[13] Cong Fu, Changxu Wang, and Deng Cai. Ssg Satellite system graph for approximate nearest neighbor search. https://githi: wtt.ccoo/////... htt.://ww...omm//lluaaaaaa////// 2020.
[14] Cong Fu, Changxu Wang, and Deng Cai. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(8):4133 39 4150, 2022.
[15] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-on out graph. Proceedings of the VLDB Endowment, 12(5):461-474, 2019.
[16] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Nsg Navigating spread graph for approximate nearest neighbor search. https::/ thub com////eaarrnnnignnss 2019.
[17] Anupam Gupta, Robert Krauthgamer, and James R Lee. Bounded geometries, fractals, and low-distortion embeddings. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 534-543. IEEE, 2003,

---

[18] Piotr Indyk and paarreeeeeeabboosear---immmmmm
Hatc-hntttneee---ppppulappppppio https://github. wtt.:/oo//i/aeaaa Hard- http:///.......tooooo.oo///////a 2023.
Haike Xu.
[19] Masajiro Iwasaki. Neighborhood graph and tree for indexing nigh-dimensional data. https
//github. cww.blooooooaoooooo...ooooooooo httpyaahoojpaaaaaaaaa aaaj/NaannN 2023.
[20] Masajiro Iwasaki and Daisuke Miyazaki. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv:1810.07:3 2018.
[21] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion-point nearest neighhor search on a single node. Advances in Neural Information Processing Systems, 32, 2019.
[22] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann. https:// wtt.:cccmooo.oee..cc...e www.iiiroooooooooooooooo 2023.
[23] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Puttern Analysis and Machine Intelligence, 33(1):117-128, January 2011.
[24] Robert Krauthgamer and James R Lec. Navigating nets: Simple algorithms for proximity search. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 798-807. Citeseer, 2004.
[25] Thijs Laarhoven. Graph-based time-space trade-offs for approximate near neighbors. 34th International Symposium Computational Geometry (SoCG 2018). Schloss Dagstuhl-Leibniz- Zentrum fuer Informatik, 2018
[26] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11)2278-2324, 1998.
[27] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. Approximate nearest neighbor search on high dimensional data experimmess analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering, 32(8):1475 1488. 2019.
[28] Yu A Malkov and Dmitry 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, 2018.
[29] Yu A Malkov and Dmitry Yashunin. Hnswlib fast approximate nearest neighbor search. https://githur com/ wwwmmmmm//aooeeeeeccoo www.im/wmwsiiiiiiim...iiiiiiieee http///mssim/mmii////////// 2022.
[30] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45:61-68, 2014.
[31] Marvin Minsky and Seymour A Papert. Perceptrons, Reissue of the 1988 Expanded Edition with new foreword by Léon Bottou: An Introduction to Computational Geometry. MIT press, 2017.
[32]
Gonzalo Navarro. Searching in metric spaces by spatial approximation. The VLDB Journal, 1 11(1):28 46, 2002.
[33] 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.
[34] Gregory Shakhnarovich, Trevor Darrell, and Piotr Indyk. Nearest-neighhor methods in learning and vision, MIT press, 2006.
[35] Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al. A survey on learning to hash. IEEE transactions pattern analysis and machine intelligence, 40(4):769-790, 2017.
12

---

[36] Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. Learning to hash for indexing big data-a survey, Proceedings of the IEEE. 104(():34-577 2015.
[37] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101.12631, 2021.
[38] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. https hotph//.cccm//yyyprm/////aaaaaa 2021.
13

---

A DiskANN Algorithm
Algorithm 2 GreedySearchí 8, q, L)
Algorithm 1 RobustPruning(i, R)
1: Input Graph G (V, E). seed s, query
1: Input Vertex i, candidate neighbor set U, pruning parameter a, degree limit I'(default
point q, queue length limit
2: Output visited vertex list U
R is n if not given)
3: A - {s}
2: Result Update Now the set of out-
4: U 0
neighbors i
5: while AQU + Ø do argiiin D(r.. q)
3: U - U T (i)
6:
4: Nout(i)
Ø
A Au (o)
5: while U * Ø and [Naaa(i) < R do
6: t argmin ((
8:
U --- UU
7:
Nowt (i) - (ou U
9:
if |A| > L then
8:
U- U
10:
A < top L closest vertices to g in A
9:
U - fo' E U.- D(
11: end
12: end while
D(z,,
13: sort in increasing distance from g
10: end while
14:
return U
Algorithm 3 DiskANN indexing algorithm (with fast preprocessing)
Input Point set P {z1 ....,,,,,,, degree limit R. queue length L
2: Output A proximity graph G' (V, E) where V = {1..m) are associated with point sets P.
3: G randomly sample a R-regular graph on vertex set V (1..n]
4: <- vertex for the point closest to the centroid of P do 5: for random permutation of [1....]]
6:
7: for = to do
8: U GreeddySeacch(,, (i))) L)
9:
Robust Pacisstrruiiiin Pruning( (i), u. R) for vertex Nowt (a do
11:
Now (J) Nout (j) o()
12:
Nout(j)] > then Robust Pruningg Nouelj), R) end
13:
14:
15:
end for
16: end for
end for
Algorithm 4 DiskANN indexing algorithm (with slow preprocessing)
1: Input Vertex set = (II,.. parameters: degree limit
2: Output A proximity graph G = (V, E)) where {1.mz are associated with point sets P.
3: s < vertex for the point closest to the centroid of
4: for to do
5: Nout(i) - Robust Pruningi, V, R)
6: end for
B Dependence on aspect ratio
Consider the following 1-dimensional data set with 2k points located [x:] where
aa'
for 1 $ Si< l
5;
2
t 2k+1-i
for k < i &
14

---

and B max 1.
0-1: 1). This is symmetric line starting from 0 to (2 + 8)a*. Each point's
distance toward the closer endpoint is a times larger than that of the previous point.
Lemma B.1. The graph G (V, E) built on the above instance using the slow preprocessing version of DiskANN satisfies the following properties:
(1) For any [k- + 1, ki, E and (1.3) $ E for any j <
(2) For any j <isk k, (i,5) E if and only if --==i- --11
Since the x; 's are symmetric,, the same properties also hold in the other direction.
Proof. (1): For any e [k + n1, we can check that no vertex j such that ht j i can delete Is from i's neighborhood, because da-Rk -1-22 a*B+a"
> +. Thus, we have ki, E E. Similarly, we have that A will delete any vertex < k from i's neighborhood because 3e #4-21 -1- + & _.
These two incqualities use that B = max a-
(2): For any i E [1, kt. - is the closest point on x; left, so (2, 1 1 1) E. Then, for any j < j will be deleted from i's neighbor by 1 because #1-1 1- a.
1
Based on the graph properties in Lemma B. let determine the length of the shortest path from starting point (selected arbitrarily by the DiskANN algorithm) to a constant approximate nearest neighbor of given query q. We select our query q to be either 0 or 2a + a B, i.e., one of the two endpoints of the data set, whichever is farther from Tg. To find an appaapprooee nearest neighbor of the query q within steps of PreedySeaachh there should be at least one path with less than hops from to q approximate nearest neighbor. WLOG, let's assume q = 0 and s > k. By Property (1) of Lemma B.1| among {1...k). the vertex the only neighbor
Proof of Theorem 3.3
of any vertex on the right of k. By Property (2) of Lemma B. for any vertex E [1, k). its only
neighbor on its left is i 1. Therefore, takes at least > ([ and > (log A) steps for slow
preprocessing DisKANN with GreedySearch to reach any 0(1)- approximate nearest neighbor in this constructed instance.
C More experimental results
C.1 Hard instance for KD-Tree based nearest neighbor search algorithm
Some nearest neighbor search algorithms use KD-tree to find the entry point for greedy search. In this case, we design hard instance where KD-tree cannot get good entry point close to the nearest neighbor. See Figure 7 We draw our constructed instance for n = 10 It is easy to mimic this instance for other data sizes.
Description of instance in Figure Our instance has dimensions, where the first two dimensions of the instance are similar to Figure 2 but with different choices of parameters. Again, the vertex set V consists of three sets of points M, P' (with size 0. 0.1n, 0.1m, 0.8n respectively) and a single answer point a: M is a VIM x VlM square grid with unit length and with bottom right corner m = (-10% 109). is a vertical chain of points consisting of unit intervals from Pt (-109, -0.05m) to Ph = (-109, 0.055m) p' is vPPT x VPPl square grid with unit length whose bottom left corner is p' = (0, 109). The answer point is a = (0, 3 * 10a). The query point q = (-3 10a 0). For a vertex e E M J P U {a)., each of v's other 4 coordinates are sampled from uniform distribution supported on [5 * 10", 10"]. For vertex v E P. its other coordinates are sampled from a uniform distribution supported on [10? 2 10"]. And for point q, its other 4 coordinates
all O. Note that though such choices parameters are tailored to the implementation of KD-trees used in SPTAG and EFANNA in [37] some general ideas are reusable for constructing hard instances for other implementations.
Intuition for instance in Figure 7 handle the use of KD-tree to search for good starting point. Implementation of KD-tree provided in [37] always randomly picks one of the top 5 dimensions with the largest variance as the splitting
The main reason why we construct a new example here is to
15

---

Pr
(-10%) 100)
Figure 7: Our constructed hard instance for SPTAG on the scale n = 10 The instance lives in twodiieeniional Euclidean space, and therefore has a constant doubling dimension. Black dots (solid or hollow) are points in the database, the red dot is the query point. Grids are only used to show the layout structure. See section C.T for detailed description.
(0 10
(0.3 10*)
(-109,5+ 10t)
Ph
= (-3 10)
(-109, 11.1000... -5 10
dimension, and divides the vertices into two halves at their mean. In Figure 7 because of the separation on the other dimensions, our construction can make sure that KD-tree quickly gets to subtree with vertices only in P. Then KD-tree will only horizontally split the chain from Pk pt or split via the other 4 dimensions. In the vertical axis, the coordinates for vertices in P and are quite close, KD-tree will assign them a low distance estimation based on only horizontal split, resulting in KD tree scanning all vertices on the chain before scanning other vertices outside of the set As long as we make the KD-tree select a vertex in as the starting point, we can ensure (as in Figure that GreedySearch will scan all vertices in P before going to M or Pl.
C.2 More experiments on other popular nearest neighbor search algorithms
We further test the other 7 popular nearest neighbor search algorithms studied in the survey 37 We use the same setting as in Section We run each algorithm for 20 different data sizes n E {105 2 10a ..... 2 10%) using hard instances in Figure Figure 2 Figure 7 (introduced in Appendix C.1 We plot the Recall rate for answering the query with queue length equal to pn where the percentage p is enumerated from the set 1%, 2%...........................2.. ... 12% 15%, 18%, 20%, 30%, 50%.50%
We run NGT on the hard instance Figure 2 using all default parameters stated in GitHub's readme, except that we use the command "-i g" to generate only the graph index, because of our focus on graph- based nearest neighbor search algorithms. We use command "-p 1" set the number of threads 1. We run this experiment 10 times and report the average recall.
NGT (20] We use NGT's implementation from the authors' GitHub repository 19
SSG [14
We use SSG implementation from the authors GitHub repository [3]. We run SSG on the hard instance in Figure using parameters K 200, L 200, iter 12, S 10, R 100 (for building KNN graph) L 100, R 50, Angle = 60 (constructing SSG). The parameters chosen here are copied from the author's s selected parameters for data SIFTIM (23), whose data size is close to ours. We run this experiment 10 times using different random seeds and report the average recall.
KGraph We use KGraph implementation due to 37, from the GitHub repository 38 We run
KGraph on hard instance Figure 4 using parameter K 100, = 130, iler = 12, 20, R 50. Parameters here are copied from the authors' selected parameters used for their synthetic data set named "n_10000 1000000"""" whose size close ours. We run this experiment times using different random seeds and report the average recall.
16

---

NGT
20%
18%
8.6
9%
8%
74
0.0
2%
1%
8 On units ot 10" points
Figure 8: Results for running NGT algorithm on the family of instances in Figure 2 axis represents the data size n, in multiples of 10 points. The vertical axis represents the size of the search queue length in terms of the percentage of the data size. each pixel represents query result, with its Recall @5 [0, 1J mapping to the spectrum the right. We run NGT algorithm 10 times and report the average recall rate.
The horizontal
DPG [27 We use DPG implementation due to 37]. from the GitHub repository 38 We run DPG
on the hard instance in Figure 4 using parameter K 100, L 100, iter 1 20, R 300. Parameters here are copied from the authors' selected parameters for their synthetic dataset named "m_1000000", whose size is close to ours. We run this experiment 10 times using different random seeds and report the average recall.
NSW (30] We NSW's implementation due to 37.. from the GitHub repository 38 We
run NSW on the hard instance in Figure 4 (with a different vertex permutation) using parameter max_mo 1000_mmmm---0-_ 100, ef _construutiinnn 400. Parameters here copied from the author's selected parameters for their synthetic dataset named "n_ "n_1000000", whose data size is close to ours. We run this experiment 5 times using different random seeds and report the average recall.
SPT [7] We use SPTATG-KIN KDD implementation due to 37 from the GitHub repository 38 We run SPTATG-KIT
the hard instance in Figure 7 using parameters KDT_namid 1, TT number = 16, TPT PPT_eea leaf_sizee 1500, scale 2, CFF 1500. Parameters here are copied from the authors' selected parameters for their synthetic dataset named "v_1000000", whose size is close to ours. We run this experiment 5 times and report the average recall.
We EFANNA's implementation due 37 from the GitHub repository (88 We run EFANNA on the hard instance in Figure 7 using parameter freres = 4, m Level = 8, 80, I. 140, iler S 25, R 150. Parameters here copied from the authors' selected parameters for their synthetic dataset named "n pe_1000000", whose size is close to ours. We run this experiment 10 times and report the average recall.
EFANNA 12
Experimental results for these algorithms are plotted in Figure Figure and Figure I0 We can that all algorithms achieve suboptimal Recall @5 rates until the queue length L is greater than 10% of the data size.
17

---

aph
5019
5019
15%
19%
12%
12%
11.
06
02
6%
6%
776
576
4%
196
1
10 111211
14 36 1920
2
10
12
14 36 1920
points)
points)
DPG
NSW
50%
50%
40%
40%
307
30%
10
10
C8
68
11%
11%
10%
0.5
10%
C6
9%
C44
9%
64
8%%
0%
C2
62
396
C,0
6.0
4%
4%
556
29
25h
(th units of 10' poims)
En units points)
Figure 9: Results for running SSG, KGraph, DPG, NSW algorithms the family of instances in Figure The horizontal axis represents the data size n, in multiples of 10s points. The vertical axis represents the size of the search queue length L in terms of the percentage of the data size. Each pixel represents a query result, with its Recall@5 e [0, 1] mapping to the spectrum on the right. We run each algorithm 10 (or 5) times and report the average recall rate.
SPTAG-KDT
EFANNA
50%
50%
40%
40%
30%
30%
10
10
12%
C8
12%
03
10%
11%
C5
11%
30%
06
5%
C4
81
9%
C4
C2
02
596
0.0
60
4%
4%
754
15
12 1920
36 1920
units of 10' points)
n: units points)
Figure 10: Results for running SPTAG-KDT and EFANNA algorithms the family of instances in Figure 7 The horizontal axis represents the data size n, in multiples of 10 points. The vertical axis represents the size of the search queue length L in terms of the percentage the data size. Each pixel represents a query result, with its Recal/@5 [0, 1J mapping to the spectrum on the right, We each algorithm 10 times and report the average recall rate.
18


Reviews:
[{"review_id": "XBN7I7ztuG", "reviewer": "Reviewer_ZVW4", "summary": "Nearest neighbour (NN) queries select for a given data point the closest point in a set and can be answered exactly in linear time by scanning the whole set. c-approximate Nearest Neighbour (ANN) queries ask for an arbitrary data point that has at most a c times larger distance than the NN. A popular approach in the literature is DiskANN that builds as an index structure a proximity graph that links close-by points together. In this manuscript two variants of DiskANN are analysed.", "questions": "Q1. What is meant to be the (exact) nearest neighbour (NN) of \"q\" in Figure 1? If the NN of \"q\" is meant to be \"a\", why would \"p0\" not be a c-approximate nearest neighbour with c = (alpha+1)/(alpha-1)?\n\nQ2. If a point that coincides with the query point Q is in the data set, do all c-approximate nearest neighbours (for c > 1) then coincide with the (exact) nearest neighbours? What are the implications of this edge case on the claims in the paper?", "limitations": "Relevant limitations seem to be discussed.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1. The work seems to fill a gap left by prior works: works proposing the studied methods seem to lack a more extensive theoretical analysis as featured in this work.\n\nS2. Constructed problem instances used in experiments provided in supplementary material (as well as links to code of studied ANN approaches) and details of how various methods have been implemented are extensively documented in the supplementary material.\n\nS3. Combination of empirical and theoretical results to furthen the understanding of the worst-case / average-case performance of ANN methods.", "weaknesses": "W1. Some parts of the paper are a bit confusing.\n\nIt is not clear which point is meant to be the (exact) nearest neighbour (NN) in Figure 1. If \"a\" is the NN, then it would seem that \"p0\" would be an approximate nearest neighbour given the values.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reviewer ZVW4\n\nW1: It is not clear which point is meant to be the (exact) nearest neighbor (NN) in Figure 1. If \"a\" is the NN, then it would seem that \"p0\" would be an approximate nearest neighbor given the value\n\nA: In our figure 1, q represents the query point and a represents the true nearest neighbor. In the proof of Theorem 3.6, when $\\epsilon$ approaches 0, the approximation ratio of p0 is no better than $\\alpha+1/\\alpha-1$. We will modify the statement of Theorem 3.6’s statement to “before getting to a vertex with an approximation ratio *smaller* than $\\alpha+1/\\alpha-1$”. Thank you for your observation!\n\nQ2: If a point that coincides with the query point Q is in the data set, do all c-approximate nearest neighbors (for c > 1) then coincide with the (exact) nearest neighbors? What are the implications of this edge case on the claims in the paper?\n\nA: Yes. In this case the distance to the nearest neighbor is zero, so an approximate nearest neighbor algorithm must report the exact nearest neighbor. We believe this fact does not affect the claims in the paper, but if there are any specific concerns, please do let us know.\n\n"}, {"review_id": "Fh2JvG0EbG", "reviewer": "Reviewer_EYFR", "summary": "This paper studies a specific class of graph-based similarity search algorithms, and establishes approximation upper bounds, and runtime lower bounds for this algorithm. In the process of establishing lower bounds, the paper also presents various point configurations that would be hard for these graph-based search algorithms, and then evaluates multiple graph-based search algorithms on these hard instances, highlighting that these examples are hard for most search algorithms, even though these graph-based search algorithms are known to perform really well in practice.", "questions": "- Aspect ratios are somewhat misleading because they sometimes provide counter-intuitive results. For example, searching for near-duplicates (that is, the distance to the nearest-neighbor is close to zero) are arguably the easiest scenario for most nearest-neighbor search methods -- For branch & bound algorithms, the greedy branching usually finds the near-duplicate very quickly, and obtains the tightest possible bound and is able to prune most aggressively. For hashing based methods, near-duplicates almost always collide, hence the search will always find the nearest-neighbor even with a very small number of hash tables. For graph-based algorithms, as long as the graph is well-connected, the greedy search on the graph will get to the near-duplicate node quite quickly and prune everything else after that in the queue. However, bounds based on aspect ratios appear to tell a different story -- near-duplicates cause the aspect ratio to be arbitrarily high, leading to larger upper-bounds on the runtime complexity or the approximation ratio, making it appear that the search problem is harder with near-duplicates. This appears counter-intuitive. How do the results in this paper handle this issue?\n\n- The aspect ratio $\\Delta$ used in Lemma 3.3 is based on only the set of points $X$, while the aspect ratio $\\Delta$ used in Theorem 3.4 is based on the set of points and the query $q$. So in that case, is it fair to assume that the aspect ratio in Theorem 3.4 **can be** significantly greater than the aspect ratio in Lemma 3.3, especially if (say) $d_{min} \\approx 0$.\n\n- In Lemma 3.3, why is it that the index $i$ of the  Rings are restricted to $i \\in [\\log_2 \\Delta]$?\n\n- In Theorem 3.4, what is the range of interest for $i$? As mentioned in lines 170-171, we can \"asymptotically get to an $\\left(\\frac{\\alpha+1}{\\alpha-1}\\right)$-approximate nearest-neighbour\". However, it is easy to see that, for different values of $i$, different terms will be the dominating term in $\\left( \\frac{\\Delta}{\\alpha^i} + \\frac{\\alpha+1}{\\alpha-1} \\right)$, and it would good to understand which values of $i$ we are interested in, and what the guarantees are for those values.\n\n- Can you please provide a motivation for Theorem 3.5? It is quite well known that $O(\\log n)$ bounds are hard to get, and usually they come with exponential dependence in dimensionality (in the best case, exponential in the intrinsic dimensionality). Even the celebrated LSH guarantees sublinear bounds in $n$ with polynomial dependence on the dimensionality. So it is generally hard to expect that we can just replace the aspect ratio with the number of points.\n\n- For the experiment in Section 4.4, Table 1, are the results averaged over different \"hard instances\"? As in, are multiple problem configurations are selected for each of the Figure 1, 2, 4 and 7, and then the average recall@5 is reported across all such problem instances is reported? This point is not clear even in the discussion in Appendix C.2. Furthermore, it would have been good to understand the performances grouped by the hard instances (at least in the appendix). For example, with algorithms such as NSG, DPG, KGraph, where the average is significantly above 0, it would be good to see whether they performed at this mediocre level for all hard instances, or if they performed really well on some hard instances (for example, ones from Figure 2) while struggling on others (for example, figure 7). This information seems important.", "limitations": "I did not find any explicit discussion of limitations by the authors. However, I do not anticipate any potential negative societal impact of this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "**Important class of algorithm analysed.**\nGraph-based approximate nearest-neighbour search algorithms can be extremely efficient in practice, and the goal of this paper to analyse one such algorithm, DiskANN, is well motivated. This paper establishes upper bounds on the approximation in the nearest-neighbour search result at any given point of the greedy search algorithm. Then, the paper goes on to present explicit examples with interesting geometrical configurations, embedded into a 2 dimensional plane, which are challenging instances of nearest-neighbour search for DiskANN. These examples make explicit one scenario where the graph built on the data forces the greedy search to visit almost all nodes.\n\n\n**Wide coverage of graph-based search algorithms.**\nBoth in the empirical evaluation, and the development of \"hard instances\", this paper covers multiple graph-based search algorithms such as DiskANN, HSNW, NSG, and SPTAG-KDT. Each of these examples exploit the specific graph construction scheme for these methods. The empirical evaluation of these multiple algorithm highlights how these hard instances are hard (to different extents) for all such graph-based algorithms.", "weaknesses": "**Interpreting the worst-case upper-bounds.**\nOne weakness of this paper is that I am unable to get an intuition of what the bound in Theorem 3.4 is telling us. One interpretation is that, as $i \\to \\infty$ (in the asymptotic range), we get a solution that is $\\left(\\frac{\\alpha+1}{\\alpha-1}\\right)$-approximate (as stated in line 170-172). But the runtime for $i$ iterations is $O(i (4\\alpha)^d \\log \\Delta)$ (as per Lemma 3.3). But in the nearest-neighbor search, the runtime for the asymptotic $i \\to \\infty$ scenario is bounded by $O(n)$. So it seems that we are saying that if we wish to achieve constant approximation with DiskANN, we have to do $O(n)$ work, which seems a somewhat vacuous result -- if we are ready to do $O(n)$ work, usually we are able to get the exact solution (not even an approximation). And Theorem 3.5 seems to be saying the same -- we always need to do $O(n)$ work. Does that mean that we are unable to get anything better than $O(n)$ guarantees for DiskANN (even with the slow preprocessing)?\n\n**Interpreting the motivation behind the hard synthetic examples.**\nThe authors do a great job at creating examples such as the one in Figure 1 & 2, where the slow preprocessing and the fast preprocessing versions of DiskANN respectively are unable to find the constant approximation nearest-neighbor in time less than $O(n)$. Figure 4 is another great synthetic example that is hard for NSG and HNSW. However, it is not directly clear to me why these examples are of interest, or something we should evaluate graph-based algorithms on. These examples are very structured, with very specific careful placements of the query $q$ and its nearest-neighbor $a$. First, it is not clear whether these examples are unique and canonical in some sense, or are there other (similarly constructed) point configurations which would similarly be a hard instance for the graph based algorithms. If they are not unique, why should these examples be studied and not others? Or if we are able to do well on these examples, can we say anything about other \"hard\" or \"easy\" instances? Secondly, even if these examples are canonical in some way, it is not clear if these resemble real datasets in any form or if these examples are somehow practical viable. Without such motivation and justification, it is not clear why we should care about these examples.\n\n\n\nMinor:\n- Without the algorithms being analyzed in the main paper, the analysis is hard to follow. In my opinion, it would useful to have the algorithm being analysed in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reviewer EYFR\n\n\nW1: [interpreting the worst-case upper-bounds] Interpreting the worst-case upper-bounds. One weakness of this paper is that I am unable to get an intuition of what the bound in Theorem 3.4 is telling us. One interpretation is that, as $i\\to\\infty$ (in the asymptotic range), we get a solution that is  $\\frac{\\alpha+1}{\\alpha-1}$-approximate (as stated in line 170-172). ….\n\nA: We referred to the asymptotic behavior only for simplicity. It can be seen that already for $i=\\log_{\\alpha} \\frac{\\Delta}{\\epsilon}$ the additive term becomes $\\epsilon$, for any $\\epsilon>0$. Thus, the convergence to the  $\\frac{\\alpha+1}{\\alpha-1}$-approximation factor is very fast. \n\n\nW2: [interpreting the motivation behind the hard synthetic examples] Interpreting the motivation behind the hard synthetic examples. It is not directly clear to me why these examples are of interest, or something we should evaluate graph-based algorithms on.\n\nA: As we mention in the paper, we believe that our results provide important information about the behavior of these algorithms. For example, they demonstrate the importance of validating the quality of answers reported by the algorithms when applying them to new datasets. They also shed light on the types of data sets which result in suboptimal performance of the algorithms. \n\nIn general, understanding the worst-case performance of approximate nearest neighbor methods is a popular subject of study. See e.g., the references in our submission, and a recent paper:\n\nElkin, Yury, and Vitaliy Kurlin. \"A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree.\" International Conference on Machine Learning. PMLR, 2023.\n\n\nQ1: Aspect ratios are somewhat misleading because they sometimes provide counter-intuitive results. \n\nA:  We agree. However, as we show in the paper, the logarithmic dependence on $\\Delta$ in the running time bound for DiskANN is necessary (Theorem 3.5). \n\nQ2: The aspect ratio $\\Delta$ used in Lemma 3.3 is based on only the set of points  X, while the aspect ratio $\\Delta$ used in Theorem 3.4 is based on the set of points and the query  q.  So in that case, is it fair to assume that the aspect ratio in Theorem 3.4 can be significantly greater than the aspect ratio in Lemma 3.3,\n\nA:  Indeed, the main result (as stated in the introduction) uses $\\Delta$ defined by X and q, while the result stated in Lemma 3.3 uses $\\Delta$ defined by X, which could be smaller.  Apologies for the confusion, we will use two different symbols to denote these two quantities.\n\nQ3: In Lemma 3.3, why is it that the index i of the Rings are restricted to i belongs to $i\\in [\\log_2 \\Delta]$?\n\nA: In the earlier version of the paper, we assumed w.l.o.g. that the distances were scaled so that the diameter was equal to $\\Delta$, but we removed this assumption during editing.  Without this assumption,  the radius of the balls should be diameter/2^i instead of  $\\Delta/2^i$. Thank you for bringing this to our attention. \n\nQ4: in theorem 3.4, what is the range of interest for i?\n\nA: See answer for W1 above.\n\nQ5: Can you please provide a motivation for Theorem 3.5?\n\nA: The theorem shows that  the logarithmic dependence on $\\Delta$ cannot be avoided. In contrast, some algorithms achieve O(log n) query time, though under stronger assumptions about the input (bounded growth assumption).  See e.g., [5] and the Elkin - Kurlin paper listed earlier. \n\nQ6: For the experiment in Section 4.4, Table 1, are the results averaged over different \"hard instances\"?\n\nA: For Table 1 in section 4.4, the results for each algorithm are obtained by running it on its specific instance and averaged over all values of n with 5 or 10 repetitions. For every algorithm, it is executed solely on one specific hard instance (Figure 2, 4, or 7). Please refer to their figure captions to see which instance it is run on. Our objective is to analyze the worst case performance for each algorithm, leading us to construct distinct challenging instances tailored to each algorithm.\n"}, {"review_id": "a1foN3tvFd", "reviewer": "Reviewer_GZP3", "summary": "This paper theoretically analyzes the worst-case performance of DiskANN. It shows that DiskANN (with slow preprocessing) can provably solve the approximate nearest neighbor problem with a constant approximation ratio. It also provides empirical results for other algorithms, such as DiskANN with fast preprocessing, HNSW, and NSG, and shows that there are hard instances that require linear query time.", "questions": "1. In l134, should it be $diam/2^i$ instead of $\\Delta/2^i$? Since we want the radius to vary from the minimum distance to diameter.\n\n2. l182 – here a constant bound is given for $\\epsilon$, but we also need $\\epsilon < 1/(\\alpha-1)$ for $a$ to be the nearest neighbor.\n\n3. How specific is Theorem 3.6 to $l_1$ distance? Can similar examples be constructed for $l_2$?\n\n4. Can the analysis be extended to beam search instead of greedy search?\n\n5. Is it possible to guarantee finding the exact nearest neighbor under some conditions? I assume this should be possible if the distance between $q$ and its nearest neighbor is sufficiently small.\n\n6. Could you give more details on how a logarithmic number of steps follows from Theorem 3.4?\n\n7. Can the intuition in the last paragraph of Section 4.1 be potentially transformed to a formal result?\n\n8. Is $d$ assumed to be constant in the paper? Or do all the results hold for $d = d(n)$?\n\n9. I think that it is good to mention that the standard neighbor pruning (used, e.g., in HNSW) uses $\\alpha = 1$. Thus, a constant approximation cannot be guaranteed.\n", "limitations": "Limitations are not discussed, the negative societal impact is not relevant for this work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) The paper theoretically analyzes graph-based nearest neighbor search in quite a general context. While previous works made some strict assumptions about the distribution of elements (uniform), here the analysis is performed in terms of doubling dimension, which is a significant step forward.\n\n2) For one algorithm, DiskANN with slow preprocessing, the constant approximation ratio can be guaranteed. Moreover, it is proven that the theoretically obtained approximation is tight. The proofs are mostly clear and easy to follow.\n\n3) To the best of my knowledge, this is the first paper that shows the effect of neighbor pruning on the performance of graph-based NNS - previous works only considered nearest-neighbor graphs.", "weaknesses": "Most of my concerns are about the experimental part:\n- Theoretical analysis only shows the constant approximation factor, while the experiments mainly focus on Recall@5 – note that for Recall@5, there are no theoretical guarantees for DiskANN with slow preprocessing.\n- It would be informative if all the algorithms were tested on all the “hard” examples and both Recall@5 and approximation ratio were shown. These hard examples may also include the example for DiskANN from Section 3.4. Otherwise, it is hard to conclude that DiskANN is empirically better.\n- On the figures illustrating the performance, Recall@5 is shown as a function of L. The figures would be more informative if they showed the fraction of considered nodes (distance computations) instead, as is usually done.\n- For a better comparison of the two versions of DiskANN, it would be better to plot Recall@5 as a function of the number of distance computations for both of them.\n- Figure 6 analyzes the approximation ratio for three algorithms but not for DiskANN with slow preprocessing.\n\nIn summary, currently, it can be hard to conclude the advantage of DiskANN with slow preprocessing over other algorithms since all the algorithms are evaluated in different setups.\n\nSome comments on the presentation:\n- Description of DiskANN is important for understanding the theoretical part of the paper. Thus, I suggest moving the key steps of DiskANN to the main text — for instance, the definition of RobustPruning.\n- A short description of NSG and HNSW would also help follow their empirical analysis.\n- To make a connection with previous works, in Lemma 3.3, it can be useful to comment that for uniformly distributed data, $|U|$ is logarithmic in $n$ and exponential in dimension.\n- After Theorem 3.4, it would be helpful to write how the claimed statement follows from (1) and (2).\n- Figure 2: $0.5 \\epsilon$ should probably be $0.5 \\epsilon / \\sqrt{n}$ here.\n\nMinor comments:\n- I suggest defining the aspect ratio in Section 2 (preliminaries).\n- $q$ denotes the query but also some other points in $X$ (e.g., in Sections 2 and 3).\n- Proof of Lemma 3.2 is very simple and can be omitted – it can be written that the lemma directly follows from the RobustPruning definition.\n- In l136, a reference to Lemma 2.1 can be helpful.\n- In Section 4.1, it is better to move the description of the instance to the beginning. Otherwise, it is hard to follow the beginning of the section and Figure 3.\n- Parameter R (degree limit) is not discussed in Appendix A (except for the pseudocode).\n\nSome typos:\n- l14: “in a some”\n- l37, l63: footnotes are properly typeset after punctuation marks\n- l70: “they live a 2-dimensional” – missing “in”\n- l110: “run” -> “runs”\n- l146: “the algorithms performs”\n- l153: redundant “for”\n- l234: “!.”\n- l406: “of with”\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Reviewer GZP3\n\nW1: Theoretical analysis only shows the constant approximation factor, while the experiments mainly focus on Recall@5 \n\nA: We believe that our paper treats both measures (Recall@5 and approximation factor) in a fairly balanced way. In particular, for both of the three main algorithms studied (DiskANN, HNSW and NSG) we perform experiments for both Recall@5 and approximation factor. Note that the bulk of sections 4.1, 4.2 and 4.3 is used to describe the hard instances, which are used for both measures. Section 4.3 covers our evaluation of the approximation ratios\n\nW2: It would be informative if all the algorithms were tested on all the “hard” examples and both Recall@5 and approximation ratio were shown. .. Otherwise, it is hard to conclude that DiskANN is empirically better\n\nA: This is an interesting idea and we will perform these experiments for the final version of the paper . We note though that our goal was *not* to demonstrate that the DiskANN is better (or not) on benchmarks, as such a comparison was already made in [19]. Instead our goal was to show that it (the slow-preprocessing version) has strong worst-case guarantees. \n\nAs we mention in the paper, we believe that understanding worst case behavior of popular algorithms is very important. For example, they demonstrate the importance of validating the quality of answers reported by the algorithms when applying them to new datasets. They also shed light on the types of data sets which result in suboptimal performance of the algorithms.\n\nW3 & W4: For a better comparison of the two versions of DiskANN, it would be better to plot Recall@5 as a function of the number of distance computations for both of them\n\nA: Our goal for fast-preprocessing DiskANN was to demonstrate linear-time behavior of the search algorithm.  The queue length L lower bounds the number of vertices scanned, which in turn lower bounds the number of distance computations. Thus, the number of distance computations is at least 0.1*n, i.e., 10^4 for n=10^5. .  In contrast, the slow-preprocessing DiskANN search algorithm reported the true nearest neighbor in all cases in just two steps for 10^5 points, so the number of distance evaluations in this case is at most 2*maxdeg<80. This  demonstrates  a large gap between the two variants (on our synthetic examples). \nUnfortunately, performing the slow preprocessing takes lots of time for larger data sets, so we won’t be able to perform more in-depth experiments by the rebuttal deadline. We will, however, perform them for the final version of the paper. \n\nW5: Figure 6 analyzes the approximation ratio for three algorithms but not for DiskANN with slow preprocessing\n\nA: As mentioned on page 7, in the slow preprocessing version of DiskANN, the search algorithm  finds the *exact* nearest neighbor in only 2 steps. Thus, the approximation factor is 1. We will include this note in Figure 6 for clarity.\n\nQ1: In line 134, use $diam/2^i$ instead of $\\Delta/2^i$\n\nA:  In the earlier version of the paper, we assumed w.l.o.g. that the distances were scaled so that the diameter was equal to Delta, but we removed this assumption during editing.  Without this assumption,  the radius of the balls should indeed be diameter/2^i instead of  $\\Delta/2^i$. Thank you for bringing this to our attention. \n\nQ2: line 182, we also need $\\epsilon<1/(\\alpha-1)$ for $a$ to be the nearest neighbor\n\nA: Yes, in our proof of theorem 3.6, we consider the case when $\\epsilon$ approaches 0, so this constraint is satisfied.\n\nQ3: How specific is theorem 3.6 to l1 distance? Can similar examples be constructed for l2.\n\nA: This is a great question! We began with the l2 norm but found that this straightforward structure doesn’t hold in l2. While it’s possible that challenging instances could exist in the l2 normed space, they might involve greater complexity. To keep things simple, we have chosen to present it using the l1 normed space.\n\nQ4: Can the analysis be extended to beam search instead of greedy search?\n\nA: Our analysis shows that even if the queue length L is equal to 1 (i.e., the search uses a pure greedy algorithm), the algorithm quickly converges to an approximate nearest neighbor. If  L>1 (i.e., when the algorithm performs beam search), the algorithm performance is not worse than for L=1. \n\nQ5: Is it possible to guarantee finding the exact nearest neighbor under some conditions?\n\nA: Yes. For example, the Cover Tree algorithm [5] identifies the exact nearest neighbor in O(log n) time, under a so-called “bounded growth assumption”. Unfortunately,  in general it is not possible to achieve this assuming a bounded doubling dimension, which we consider in this paper.\n\nQ6: Could you give more details on how a logarithmic number of steps follows from Theorem 3.4?\n\nA: The fundamental idea here is that if a point p is not directly connected to q’s nearest neighbor a, then as per RobustPruning outlined in Algorithm 1 on page 12, point p should establish an a alpha-shortcut to a, so each step the distance to the nearest neighbor a is shortened by a factor of alpha.\n\nQ7: Can the intuition in the last paragraph of Section 4.1 be potentially transformed to a formal result?\n\nA: It might be possible to convert this intuition into a formal argument. This would, however, require addressing some subtle probabilistic dependence issues, due to the fact that DiskANN performs multiple passes over the input. Since our goal was to demonstrate a linear running time behavior for specific *implementations* of the studied algorithms, we decided not to pursue this direction in this paper.\n\nQ8: Is d assumed to be constant in the paper? Or do all the results hold for  d=d(n)?\n\nA: Yes, d can be an arbitrary parameter, it does not have to be constant.\n\nQ9: I think that it is good to mention that the standard neighbor pruning (used, e.g., in HNSW) uses $\\alpha=1$. Thus, a constant approximation cannot be guaranteed.\n\nA: Thank you for this observation, we'll add it to the paper. "}]

Author rebuttal:
We thank all reviewers for their useful comments and feedback. We will fix the typos and presentation issues in the final version of the paper. In what follows we address the issues identified by the reviewers as weaknesses and/or listed as questions. 

Meta-review: The paper focuses on theoretical worst case guarantees of popular graph based KNN algorithms. It provides good insight into why these algorithms work and shows hard instances where the algorithms does not work. They verify their findings with empirical experiments.  The reviews were generally positive but lack the excitement. Rebuttal pushed the paper in generally positive direction. The area chair went over the paper. In the end, the papers analysis even if worst case and may not reflect the general success of the paper, will still be useful and eye opening for the community as it points out important things to watch for in some of the most widely used algorithms.
Decision: Accept (poster)