Graph-Based Algorithms for Diverse Similarity Search

Thank you for your valuable feedback!

Response for W1/Q1: Thanks for your suggestion! For the colorful NN definition, the current algorithm 2 always optimizes the furthest point, which only provides approximation guarantees on the maximal distance but not the total distance. For the total (average) distance, we have developed a modified search algorithm (not included in the paper) that optimizes the k points together in a single step. For that algorithm we obtain a “uniform” guarantee $ALG_i\le (\frac{\alpha+1}{\alpha-1}+\epsilon)OPT_i$ for all $i<k$ where $ALG_i$ and $OPT_i$ are the distance from the i-th point in our solution ALG and the optimal solution OPT. Note that the point-wise guarantee implies a bound on the total distance.

Response for W2/Q2: Thanks for proposing this idea! This setting fits in our (k’,C)-diverse NN formulation in Definition A.3, so our algorithm can handle this setting, at least from a theoretical perspective. However, our codebase is optimized for the colorful NN problem (see Appendix B) because of the concrete application we targeted. Performing experiments under the general diversity setting requires a separately optimized algorithm implementation tailored to that case, which is possible but needs significant work.

Thank you for your valuable feedback!

W1: In my view, the experimental section could be more extensive by comparing against additional baseline methods for ANN and post-processing, such as HNSW.

Response: It is indeed possible that using different graph-based methods could improve the performance. However, this could hold for both for the baseline re-ranking and for the diversity-aware algorithm - we believe that other graph-based algorithms like HNSW should be amenable to the modifications we applied to DiskANN. Our strategy was instead to start from the existing DiskANN code and make as minimal changes to it as possible, in order to retain optimizations that have been already developed for that code. This allows us to make “apples to apples” comparisons, as we use the same code base for both re-ranking and our algorithm.

W2: Finally, one possible downside of this approach is the need to build the index for a specific diversity requirement: that is, for returning k neighbors with at most k′ of the same color. The proposed algorithm could be even more general if a flexible index could support queries with varying diversity constraints.

Response: We note that, to obtain theoretical guarantees, it suffices to know an “upper bound” on the value of k. (It is easy to see that building a graph on a larger value of k works for searching on smaller values of k. We are happy to include this remark in the paper.) On the practical side, we use the tunable parameter ‘m’ which determines the number of colorful neighbors a candidate needs to have (defined in Section 4, line 325). Empirically, we find that m can be set much smaller than k while retaining good results. In fact, in our experiments, we studied the performance of the algorithm even with m=1, i.e., where the graph construction method is the same as in the vanilla DiskANN but the search retrieves k>1 diverse candidates. Please see Figure 7 for this ablation study

We also want to emphasize that in the worst case, the index must account for the number of retrieved elements (k) in the colorful nearest neighbor (NN) problem. Consider an extreme scenario where we color a dataset using $k^*$ colors, $k^*-1$ of which are uniformly and evenly assigned across the dataset, and the last color is randomly assigned to only one point. For the colorful NN query with $k \leq k^*-1$, we can ignore the last color, and a diverse search applied to the standard index should work. However, for $k = k^*$, the data structure needs to find a set of $k−1$ close points, plus the unique point with the $k$-th color. Without appropriate preprocessing, identifying a point with a unique color in the data set can take linear time. Therefore, the index-building algorithm should account for this and add more edges toward the point with the unique color. This justifies the need to know the value of $k$ during the preprocessing.

Q1: The index is built based on the values of k and k′ and so they need to be known in advance. On the other hand, in the experimental section, you compare with using the 'diverse query' on the standard index. Is there some kind of intuitive interpolation between these cases, such a 'balanced index' which is effective at responding to non-diverse queries, and diverse queries whose parameters are not known in advance?

Response: We believe that the ideal index should take into account how restrictive the diversity constraint is e.g. for the colorful case, the larger k is, the more restrictive the constraint is, so our index should keep more edges between different colors. Please see the intuitive analysis above. Our experiment shows that the diverse search algorithm also helps find more diverse answers even when applied to the standard index. In conclusion, both the diverse index and the diverse search help solve this problem.

Thank you for your valuable feedback!

Response to W1: Since we cite HNSW, NGT and DiskANN earlier in the introduction, we did not want to repeat the discussion later.. However, given the feedback, we will expand the discussion and provide a comprehensive overview of graph-based NN algorithms.

Response to W2: Diversity-based retrieval has found many applications since the influential paper of (Carbonell & Goldstein, 1998). To the best of our knowledge, the predominant algorithmic approach to this problem relied on re-ranking/filtering as proposed in that paper.

As mentioned in our paper, Google emphasized the importance of “diversity” w.r.t intent during search to capture multiple intents. E.g., searching for “transformers” without other context should ideally return results related to the movie, the electrical engineering concept and the ML concept. We can capture this in our framework by using some classification algorithm to assign a color to each vector based on its underlying “intent”.

Similarly, there is a recent body of literature which highlights the importance of diverse retrievals in Retrieval Augmented Generation (RAG) systems. For example, the paper https://arxiv.org/pdf/2409.18110 argues that retrievals need to be diverse w.r.t perspective to excel in RAG queries. Similarly, the work https://arxiv.org/pdf/2502.11228v1 also argues for diverse retrieval using Vendi scores. Conceptually speaking, both these works seek to ensure diversity during retrieval, which is exactly what our work is targeting, albeit with slightly different modeling. We therefore believe that our work, which studies the problem of efficient diverse retrievals, will prove to be important in furthering this line of inquiry.

Regarding the specific formulation of colorful nearest neighbor, here are two specific real-world applications:

1. Seller diversity, which we include in the paper (please refer to e.g. line 295-right for the description).
2. Typically in RAG systems, documents are divided into chunks/passages and each passage is embedded as a vector. Therefore each vector in the data set is associated with a document (and has a docID which we see as a color). It has been noted in practice that when we retrieve top k vectors to the query, many vectors retrieved correspond to passages from the same document, making them redundant as the eventual goal is to pass the complete documents corresponding to the docIDs retrieved through the vector search. In such scenarios, retrieving vectors corresponding to diverse set of docIDs, would help improve the efficiency and accuracy of the RAG pipelines.

Response to W3.1: It is indeed possible that integrating faster methods for selecting promising nodes to expand [1,2] into DiskANN could improve its performance. Our strategy was instead to start from the existing DiskANN code and make as minimal changes to it as possible, in order to retain optimizations that have been already developed for that code. In addition to retaining the efficiency benefits of those optimizations, this also allows us to make “apples to apples” comparisons, as we use the same code base for both re-ranking and our algorithm. It is plausible, although not guaranteed, that further optimizations along the lines of [1] and [2] would equally benefit both our algorithm and the re-ranking baseline.

Response to W3.2: Thank you for mentioning reference [3], and it is an important distinction to make - it appears that their framework is indeed substantially different from ours. Most notably, attribute constraints in [3] are “local”: they specify a relation (or filter constraint) between the query q and a data point p which must be satisfied if p is to be included in the output. In contrast, diversity constraints are “global”, as they specify the overall constraint on the whole output (e.g., at most k’ out of k points can have the same color). This difference is reflected in the indexing procedures. In particular, the approach of [3] augments the distance function so that close points with similar attributes are linked in the graph. In contrast, the main goal of our indexing procedure is to connect each node to close points with dissimilar attributes (colors). We will include this discussion in the paper.

Response to W3.3: The number of categories can be very large. In our seller data set, this number is roughly 2500, and in the Amazon Automotive dataset, this number is roughly 85000. Therefore, in practice, it can be quite inefficient to enumerate the prepared data structure for each color.

Thank you for your valuable feedback!

Response for W1: Thank you for the suggestions. We will include preliminaries on the DiskANN algorithm in the appendix. We have included intuition on the new algorithms, but for completeness we will add informal descriptions of them too. We will also include a conclusion to the paper

Response for W2: We note that, to obtain theoretical guarantees, it suffices to know an “upper bound” on the value of k. (It is easy to see that building a graph on a larger value of k works for searching on smaller values of k. We are happy to include this remark in the paper.) On the practical side, we use the tunable parameter ‘m’ which determines the number of colorful neighbors a candidate needs to have (defined in Section 4, line 325). Empirically, we find that m can be set much smaller than k while retaining good results. In fact, in our experiments, we studied the performance of the algorithm even with m=1, i.e., where the graph construction method is the same as in the vanilla DiskANN but the search retrieves k>1 diverse candidates. Please see Figure 7 for this ablation study We also want to emphasize that in the worst case, the index must account for the number of retrieved elements (k) in the colorful nearest neighbor (NN) problem. Consider an extreme scenario where we color a dataset using $k^*$ colors, $k^*-1$ of which are uniformly and evenly assigned across the dataset, and the last color is randomly assigned to only one point. For the colorful NN query with $k \leq k^*-1$, we can ignore the last color, and a diverse search applied to the standard index should work. However, for $k = k^*$, the data structure needs to find a set of $k−1$ close points, plus the unique point with the $k$-th color. Without appropriate preprocessing, identifying a point with a unique color in the data set can take linear time. Therefore, the index-building algorithm should account for this and add more edges toward the point with the unique color. This justifies the need of knowing the value of $k$ during the preprocessing.

Response for W3: Please note that diverse-build+diverse-search is never outperformed by the baseline except in a tiny fraction of cases, and that too only by a small amount. Moreover, this occurs only in the very high latency regimes. A possible explanation for when and why this occurs could be the following: in datasets where there is more balance in the colors, the naive search itself organically retrieves diverse items which makes it easier for the baseline algorithm without the overheads of our slightly expensive diverse priority queue data structure. In a majority of cases (including on the real-world dataset), our approach is significantly superior to the baseline. Finally, real-world use-cases often deal with the lower latency regimes as long as the desired recall is achieved.

Response for Q1: Please see Definition 2.3 for $OPT_k$. We will add a reference to the definition in line 195

Response for Q2: The number of categories can be very large. In our seller data set, this number is roughly 2500, and in the Amazon Automotive dataset, this number is roughly 85000. Therefore, in practice, it can be quite inefficient to enumerate the prepared data structure for each color.

Response for Q3: In the Standard DiskANN algorithm, there is one search time parameter, L, which is the size of the priority queue the algorithm maintains till the search converges. Indeed, upon convergence, the algorithm knows the local optimal set of L potential candidates. We merely set ‘r = L’, and select the most diverse subset of these L candidates as a post-processing step. Therefore, in this baseline, we can think of r = L and sweep over the values of L as is usually done. There is an overloaded priority queue size parameter L during index construction, which we fix to be 200, which is within the range of commonly chosen values (typically around 2 to 3 times the graph degree). We apologize for this notational mistake and can disambiguate to Ls and Lb to denote search-time vs build-time parameters.

Response for Q4: We have suggested possible explanations for the reason why the baseline is marginally outperforming our approach. As for heuristics to improve, if there are scenarios where the baseline is significantly superior, one could then potentially have a pre-determined cut-off for the list-size ‘L’ parameter at search time, such that we implement our diverse search + diverse build algorithm for values of L below the cut-off, and we perform a post-processing approach on the diverse index built for values of L above the cut-off, which we have empirically validated to be superior to the baseline algorithm reported in the paper. As for the last question of whether Figure 7 holds for larger values too, we have tried much larger values as well, and it indeed holds that increasing ‘m’ yields better performance, but with diminishing returns as observed in the figure with values of m=2 and m=10.