Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations

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.

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. 2) 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. 3) 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: - 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. - 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. - 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. - 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. - Figure 6 analyzes the approximation ratio for three algorithms but not for DiskANN with slow preprocessing. In 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. Some comments on the presentation: - 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. - A short description of NSG and HNSW would also help follow their empirical analysis. - 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. - After Theorem 3.4, it would be helpful to write how the claimed statement follows from (1) and (2). - Figure 2: $0.5 \epsilon$ should probably be $0.5 \epsilon / \sqrt{n}$ here. Minor comments: - I suggest defining the aspect ratio in Section 2 (preliminaries). - $q$ denotes the query but also some other points in $X$ (e.g., in Sections 2 and 3). - 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. - In l136, a reference to Lemma 2.1 can be helpful. - 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. - Parameter R (degree limit) is not discussed in Appendix A (except for the pseudocode). Some typos: - l14: “in a some” - l37, l63: footnotes are properly typeset after punctuation marks - l70: “they live a 2-dimensional” – missing “in” - l110: “run” -> “runs” - l146: “the algorithms performs” - l153: redundant “for” - l234: “!.” - l406: “of with”

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. 2. l182 – here a constant bound is given for $\epsilon$, but we also need $\epsilon < 1/(\alpha-1)$ for $a$ to be the nearest neighbor. 3. How specific is Theorem 3.6 to $l_1$ distance? Can similar examples be constructed for $l_2$? 4. Can the analysis be extended to beam search instead of greedy search? 5. 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. 6. Could you give more details on how a logarithmic number of steps follows from Theorem 3.4? 7. Can the intuition in the last paragraph of Section 4.1 be potentially transformed to a formal result? 8. Is $d$ assumed to be constant in the paper? Or do all the results hold for $d = d(n)$? 9. 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.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Limitations are not discussed, the negative societal impact is not relevant for this work.

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.

Strengths

**Important class of algorithm analysed.** Graph-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. **Wide coverage of graph-based search algorithms.** Both 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.** 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 $\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)? **Interpreting the motivation behind the hard synthetic examples.** The 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. Minor: - 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.

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? - 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$. - In Lemma 3.3, why is it that the index $i$ of the Rings are restricted to $i \in [\log_2 \Delta]$? - 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. - 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. - 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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

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.

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.

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. S2. 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. S3. 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. It 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.

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)? Q2. 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?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Relevant limitations seem to be discussed.