Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs

We thank the reviewer for the kind words and suggestions. As the reviewer noted, extending the existing analysis to the practically motivated beam search regime was a key motivation for this work. Additionally, we adopted a distance-based approximation scheme, leveraging our novel factor-revealing SDP to establish improved approximation guarantees for the Euclidean metric. While we agree that a probabilistic analysis of graph-based data structures would be valuable, it is important to note that DiskANN is deterministic and always returns the same set of nearest neighbors for a given query. Therefore, conducting a probabilistic analysis of exact top-1 nearest neighbor retrieval would require a new theoretical framework with a well-motivated assumption on the query distribution—an interesting yet challenging direction for future research.

We appreciate the reviewer’s detailed feedback and would like to clarify the key contributions of our work. Rather than proposing a new algorithm that outperforms DiskANN, our primary contribution is theoretical, providing a deeper understanding of the DiskANN algorithm in two key ways. First, we establish an improved approximation guarantee for DiskANN by leveraging two critical insights: (a) explicitly analyzing the $\ell_2$ setting, which is widely used in practice and has favorable mathematical properties, and (b) examining the sorting step in the prune procedure. Using these insights, we introduce a novel factor-revealing SDP to demonstrate an improved approximation factor of $\frac{\alpha}{(\alpha - 1)}$, compared to the previously known bound of $\frac{\alpha + 1}{\alpha - 1}$ from Indyk and Xu (NeurIPS 2023). Moreover, we show that omitting either sorting or the $\ell_2$ setting results in a best possible approximation ratio of $\frac{\alpha + 1}{\alpha - 1}$, matching Indyk-Xu’s original result. This suggests that DiskANN may perform better under the $\ell_2$ metric than other distance metrics.

Second, we introduce techniques that establish the first-ever theoretical bounds for retrieving $k > 1$ candidates in a beam search setting using a graph-based ANNS algorithm. Despite its practical significance in scalable retrieval, this regime remains underexplored, with prior work (NeurIPS 2023, ICML 2020, SoCG 2018, SODA 1993) exclusively focusing on the $k = 1$ case. We also believe our factor-revealing LP/SDP framework will be valuable for further research in this setting. In short, our core contribution lies in the theoretical understanding of the sorted prune step in DiskANN, and to support our theoretical findings, we conducted experiments evaluating the impact of sorting during graph construction. We did not compare DiskANN with other ANNS algorithms, as this has been extensively studied in prior work.

We thank the reviewer for suggesting additional experiments. Based on the suggestions, we include plots and tables for 100M-scale datasets, key metrics such as build times, and RAM usage and disk I/O reads per query (for SSD-based indices). Please note that all dropbox links are anonymized. This comprehensive empirical study will be included in the final version.

Link to DiskIO plots: https://www.dropbox.com/scl/fo/c44n8ij92zpt19qdedw1o/AJ-GeHiB6-38q1eRqJ7XYSw?rlkey=yfvqwr98038o4xuvq9dj1ghcy&st=ws3cd67g&dl=0

Link to RAM usage and Build Times: https://www.dropbox.com/scl/fo/v3cdv5iv76aryqcrh639x/AJgfthBn3IFAVaUGdWGzHwU?rlkey=ghddj7evgo7ldcrl1whc6st7m&st=nsjbz81n&dl=0

Link to Large-Scale dataset plots: https://www.dropbox.com/scl/fo/mp2cq55hz6bbd7rswojyu/AHJF6oHGCVUt5xz6Ah-OPao?rlkey=rt7dvticzt2jlsvq3pkf4nncf&st=j4saygfe&dl=0

Q1 (varying k):

On two large scale datasets, we have included plots of Recall@k vs. QPS for different values of k to analyze the effect of sorting during pruning. The search behavior remains consistent with our observations for k= 100.

Link to varied-k plots: https://www.dropbox.com/scl/fo/m6f1pdq01npiy0dlv2ueq/AJa2AL5Ij3J1S8hhkvVhax8?rlkey=6f83rhwgkafme6s6v6r4ke3v6&st=um503h2h&dl=0

Q2 (degree reduction and varying dimension):

We appreciate the reviewer’s insightful question. While the degree does decrease for graphs built using sorted pruning on real-world datasets (as shown in Table 2), there is no clear correlation between this decrease and data dimensionality. Consider a simple one-dimensional example: let $p, a, b, c$ be four points on a line with distances $d(p,a)=1$, $d(a,b)=0.5$, and $d(b,c)=1.5$. The sorted algorithm would connect p to both $a$ and $c$ to maintain $\alpha$-reachability, whereas a more efficient algorithm could instead connect $p$ to $b$ while still preserving $\alpha$-reachability. This example illustrates that degree change is not tied to dimensionality. Additionally, a lower degree does not necessarily translate to improved performance, as latency depends on both the average degree and the graph’s diameter. A reduced degree may increase the graph’s diameter, making the impact on final latency difficult to predict. To further investigate the effect of data dimension on the performance of sorted vs unsorted index construction, we conducted an additional experiment on the OpenAI dataset. We used a random Johnson-Lindenstrauss matrix to project the 1536-dimensional OpenAI embeddings into a 352-dimensional space and measured the degree change due to sorting. With sorting, the average degree was 54.15; without sorting, it increased to 57.3—a 5.8% rise. This aligns closely with the 5.6% increase observed in the original dataset (Table 2), suggesting that the degree change is a property of the dataset rather than a direct function of dimensionality. So it might be more a function of the inherent structure of the dataset as opposed to the dimension itself.

We thank the reviewer for their kind words and thoughtful suggestions. As suggested by the reviewer, we have included a link to plots on two large 100M-scale datasets from big-ann-benchmark, confirming the importance of sorting irrespective of dataset size. We will include all of these plots in the final version of our submission. For convenience, we also include a table capturing one such plot for the 100M-scale Microsoft SPACEV dataset, comparing QPS to 100@100Recall. See that for this dataset, the sorted index outperforms the unsorted index, delivering 23% higher QPS for a recall of ~0.93.

(Anonymized Dropbox link) Large Scale Experiment Plots: https://www.dropbox.com/scl/fo/mp2cq55hz6bbd7rswojyu/AHJF6oHGCVUt5xz6Ah-OPao?rlkey=rt7dvticzt2jlsvq3pkf4nncf&st=7z86irq4&dl=0

We thank the reviewer for their thoughtful comments and suggestions. We will address all typos and wording mistakes in the final version. We want to emphasize one point: in addition to giving the first analysis for beam search, which is widely used in practice, we also improve the current state of the art approximation guarantees for the DiskANN algorithm, when the underlying metric is euclidean. This suggests that DiskANN may perform better under the $\ell_2$ metric compared to other distance metrics.

Regarding experiments for quantifying the solution quality, we include a link to plots demonstrating average approximation ratio across queries versus QPS for two large 100M-scale datasets: Microsoft SPACEV and BIGANN (https://big-ann-benchmarks.com/neurips23.html) for different values of $k$. The average approximation ratio is the mean over all queries, of the maximum over all items $i$ in the final beam of size $k$, of the distance of the $i$th candidate computed by the algorithm upon the $i$th closest NN.

(Anonymized Dropbox link) Approximation Ratio Plots: https://www.dropbox.com/scl/fo/y76d8hn51pkl097g6yaa0/AGyI89kxLaI8ouvgG8FNjRM?rlkey=xahf5obtefjqz35jj1yig6p3r&st=5h6r0brf&dl=0

For convenience, we include the raw data for the BIGANN approximation ratio plot below. Note that for an approximation ratio of 1.008, the sorted instance supports a QPS of around 58000 (row 7) while the unsorted instance supports a QPS of only 25000 (row 11).