acceptodds
Under review as a conference paper at ICLR 2027

Approximation Algorithms for Diversity-Aware -Nearest Neighbor Search

Abstract

As a fundamental computational primitive, Nearest Neighbor Search (NNS) retrieves the most relevant objects for a given query, underpinning a vast array of applications like image search, retrieval-augmented generation (RAG), and recommendation systems. However, traditional NNS schemes neglect diversity awareness, thereby suffering from severe redundancy and near-duplicate results. To tackle this limitation, diversity-aware -nearest neighbor search (DNNS) has been extensively studied. Despite these efforts, state-of-the-art DNNS methods still struggle with compromised result quality, efficiency bottlenecks, or inflexible trade-offs between relevance and diversity. To address these limitations, we study a DNNS formulation that linearly combines the relevance and diversity terms in a unified objective function, with a controllable parameter to adjust their relative importance. We prove that the problem is NP-hard and that, unless , no polynomial-time algorithm can approximate it with a factor of for any . Then, we propose a linear scan-based algorithm, threshold-greedy scan (TGS), for DNNS with a -approximation for any fixed . Furthermore, we integrate the threshold-greedy principle with graph-based indexes for NNS and propose multi-threshold graph search (MTGS), which achieves a -approximation under a shortcut-reachability assumption on the graph. Finally, we conduct extensive experiments on four real-world datasets. The results demonstrate that TGS achieves the best result quality for DNNS in almost all cases. Meanwhile, MTGS runs over two orders of magnitude faster than TGS and improves upon state-of-the-art DNNS baselines in both result quality and search efficiency.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Diversity-aware k-nearest neighbor search, Graph-based indexing, Approximation algorithms

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_o1KFOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

In this paper, the authors propose the new solution for the diversity-aware kNN search problem, which is a fundamental research problem in vector database (or AI infra). The authors prove that this problem does not have the polynomial-time approximation algorithm with the approximation ratio of 43−ζ\frac{4}{3} - \zeta, given that P≠NPP \neq NP. Moreover, they have proposed two solutions, namely (i) threshold-greedy scan (TGS) and (ii) multi-threshold graph search (MTGS), which can solve this problem (i) using a polynomial-time algorithm with 43+ϵ\frac{4}{3} + \epsilon approximation ratio and (ii) using a faster algorithm with 2+ϵ2+\epsilon approximation ratio.

Critical strengths

S1: The technical novelty/contribution of this work is very solid. The authors propose two approximation methods that can handle this problem with a non-trivial approximation guarantee.

S2: Solid theoretical analysis has been provided in this paper. For example, they have also proved that the hardness of this problem.

S3: Their methods can achieve the near-optimal performance with respect to the approximation guarantee.

S4: Finding diversity-aware kNN for each query is very important in many applications, especially for recommendation (because it may not be good to recommend the same movie for the users).

Critical weaknesses

W1: The datasets that are adopted in this paper are small-scale. In Table 1, the largest one is only with 1,183,514 objects. Nowadays, vector DB normally stores billion-scale/trillion-scale vectors. Therefore, algorithms that work for million-scale vectors may not be very meaningful in practice. The authors should better show that their algorithms can handle billion-scale vectors.

W2: I believe that the diversity-aware kNN search problem may not be new. Many research studies should have already shown that this problem is NP-hard. Therefore, is it necessary to provide a long proof for showing that this problem is NP-hard in Appendix C2. Is this problem different from those papers that have been published in the literature?

W3: I think the authors should also consider combining those parallel/distributed techniques for boosting the performance of their proposed algorithms. The main reason is that vector DB is normally very large nowadays. Only considering a single machine setting may not be very meaningful.

Questions for authors

Q1: Can the authors should the performance of their methods and competitor methods using large-scale datasets?

Q2: Is this problem different from those diversity-aware kNN search problem proposed from the literature?

Q3: Following Q2, why do we need to prove the NP-hardness again for this problem?

Q4: Can the authors comment how the parallel/distributed techniques can be combined with their methods to further improve efficiency?

2 comments

We sincerely appreciate your insightful questions and respond to each of them below.

For Q1/W1: Given the available computing resources, as the implementation of our algorithms and all baselines is memory-based, we additionally evaluated the SIFT-100M dataset, the largest dataset affordable for the memory space of the server we use (see Appendix D.6). TGS achieved the lowest mean objective at 109.29 s/query. Our graph-based MTGS averaged 61.85 ms/query, only 1.03% higher objective than TGS. Compared with LotusFilter, MTGS was 2.90× faster and achieved a 3.85% lower objective. PSS averaged 16.21 s/query with the highest objective among all diversity-oriented methods. Beam Search was fastest at 6.70 ms/query, but its mean minimum pairwise distance was 118.26, compared with 186.56 for MTGS and 190.36 for TGS. The added baseline, Anand-M, failed to complete the graph construction on SIFT-100M after 24 hours. On the large-scale dataset, MTGS still achieved the best trade-off between diversity and relevance.

For Q2/Q3/W2: We note that closely related works on diversity-aware kNN adopt different formulations from ours. They either impose diversity constraints, e.g., Zhao et al. (2026) and Anand et al. (2025)'s extension, or define diversity through categorical attributes, e.g., Barman et al. (2026) and Anand et al. (2025). After checking all the proofs of NP-hardness in these works, we confirm that none of their reduction procedures is directly applicable to our problem due to their formulation distinctions. We thus believe that establishing a new reduction procedure for the NP-hardness of our problem is necessary.

For Q4/W3: In the current experiments, we focus on a single-machine setting primarily to compare the solution quality and query overhead of different search algorithms in a fair and unified environment. Nevertheless, we think our approaches are extendable to the parallel/distributed setting along the following levels. 1) Inter-query parallelism: Different queries can execute TGS or MTGS independently, improving throughput through multi-core or multi-node concurrency. 2) Intra-query parallelism: Our threshold selection mechanism is naturally suited to parallelization and can be parallelized across queries without additional synchronization. For each candidate visited during graph traversal, feasibility checks and candidate-set updates for different thresholds can be performed in parallel without affecting one another. 3)Sharded retrieval and global selection: Each shard could perform local retrieval in parallel, followed by global diversity-aware selection over the merged candidates. We will consider extending to parallel/distributed settings for future work.

Reviewer_o1KFOpenReview ↗

Reply to the Comment

I have read the rebuttal from the authors and think that they have adequately addressed my comments.

Reviewer_8vMZOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates diversity-aware K-nearest neighbor search. To address the efficiency bottleneck of the traditional retrieve-then-rerank paradigm, the authors integrate diversity constraints directly into the search process. They propose a linear scan-based threshold-greedy algorithm and a multi-threshold graph search algorithm built on proximity graphs. Experiments on four real-world datasets validate the effectiveness of the proposed methods in objective values and query latency.

Critical strengths

S1. This paper is well-motivated. It accurately identifies the efficiency bottleneck caused by oversized candidate pools in retrieve-then-rerank pipelines for RAG and recommender systems. Integrating diversity directly into the search process holds strong practical value.

S2. The paper provides strict approximation bounds for the joint relevance-diversity objective function. The linear scan algorithm achieves a near-optimal theoretical lower bound.

S3. The multi-threshold graph search cleverly shares vertex discoveries and distance evaluations across multiple threshold candidates, effectively reducing redundant overhead during graph traversal.

Critical weaknesses

W1. The paper strictly adopts the minimum pairwise distance as the diversity metric. This metric is highly sensitive to outliers; a single pair of close points disproportionately degrades the overall diversity score, which may misalign with user perception in practical scenarios.

W2. The approximation bound of the graph-based algorithm heavily relies on the shortcut-reachability assumption. The paper lacks sufficient justification on whether mainstream proximity graphs inherently satisfy this property, questioning the practical significance of the theoretical bound.

W3. The linear scan algorithm requires global sorting and is impractical for large-scale data. For the graph-based algorithm, there is a lack of in-depth latency-recall trade-off comparisons against mature baselines on massive datasets, making it hard to prove its superiority in industrial-scale vector retrieval.

Questions for authors

Q1. How does the minimum pairwise distance metric perform compared to more robust metrics like max-sum dispersion or determinantal point processes in handling outliers during your experiments?

Q2. Can you provide empirical or theoretical evidence demonstrating that mainstream proximity graph indexes satisfy the shortcut-reachability assumption required for your graph algorithm?

Q3. How does the graph-based algorithm perform in terms of the latency-recall trade-off on massive-scale datasets compared to traditional retrieve-then-rerank baselines?

1 comment

We sincerely appreciate your insightful questions and respond to each of them below.

For Q1: Although max-min diversification itself is sensitive to outliers that are far from all normal points, as adding these outliers to the solution can lead to high diversity values, our problem formulation and search algorithms have already mitigated this issue. In the formulation, we require the relevance coefficient to be at least as large as the diversity coefficient. Under this setting, a distant outlier may increase the diversity term but incur a larger relevance penalty and, therefore, is unlikely to be a good choice. In both algorithms, we adopt a relevance-first search strategy that tends to first add objects closer to the query point. As such, distant outliers, which may lead to high diversity values, will not be evaluated by the algorithms due to distance-based sorting in TGS and the proximity property of graphs in MTGS.

For Q2: During the rebuttal, we identified a weaker entry reachability assumption to replace the stronger shortcut-reachability assumption for the theoretical analysis of MTGS. The entry reachability assumption requires that every vertex in the database must be reachable from the entry vertex of a search through a directed path. We prove that all theoretical results of MTGS still hold under the weaker assumption.

Entry reachability is verifiable on graphs via reachability queries. Theoretically, standard NSG enforces entry reachability during construction. It traverses the graph from its navigating node and adds edges from the reachable part until all vertices are covered (Fu et al., 2019). Since HNSW does not guarantee entry reachability, we measured the entry reachability and the nearest-1% object (typically the most relevant ones to a query) reachability of the HNSW graphs used in our experiments (see Appendix D.5). Entry reachability was 100% on SIFT, 99.9997% on MSong, 99.79% on GIST, and 57.94% on GloVe. Coverage improved for the nearest-1%, reaching 100% on SIFT and MSong, 99.97% on GIST, and 92.36% on GloVe. These results indicate that MTGS can reach most candidates relevant to the query on HNSW graphs, despite the fact that they cannot always satisfy the entry reachability assumption.

For Q3: Due to limited computational resources and the fact that our current implementation is solely in-memory, we additionally evaluated SIFT-100M, which contains 100 million objects, the largest dataset affordable for the memory space of the server we use (see Appendix D.6). Even on this large-scale dataset, MTGS was 2.90$\times$ faster than LotusFilter (the state-of-the-art retrieve-then-rerank baseline we compare) while achieving a 3.85% lower objective, thus improving both latency and recall over the two-stage baseline. The results confirm the scalability of MTGS on large datasets.

Reviewer_geK6OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers the diverse search problem in the following sense. Given a data set P of points and parameter k, preprocess P such that given a query q, it can find a subset S of P of size k such that the following function is minimized.

f(S)=(1−λ)d(q,S)−λdiv(S)+Δ.f(S) = (1-\lambda) d(q,S) - \lambda div(S) + \Delta.

  • λ\lambda is a parameter between 0 and 1/2 specified by the problem that tunes the importance of relevance vs diversity
  • Δ\Delta is the maximum pairwise distance (Diameter) in P
  • div(S) is the minimum pairwise distance notion of diversity in the set S
  • d(q,S) is the average distance of q to the points in S

The paper shows that the problem admits a 4/3+eps approximation using a linear scan. I want to mention that this is not hard given how the parameters are defined. In particular Δ−λdiv(S)\Delta - \lambda div(S) is always between Δ/2\Delta/2 and Δ\Delta (given λ≤1/2\lambda \leq 1/2) and thus the problem is more or less similar to the problem without diversity upto a constant. On the other hand given that d(q,S)≥div(S)/2d(q,S) \geq div(S)/2, the two terms relate and getting the result is more or less standard.

Their TGS algorithm sorts points by distance to the query and scans them in this order for each of O(1/ϵ)O(1/\epsilon) equally spaced separation thresholds. A point is accepted only if it is sufficiently far from all previously accepted points.

They further suggest a modification to the graph based ANN algorithm to incorporate this diversity.

A major concern with this paper is missing the contribution of the prior work of Anand et al., Graph-Based Algorithms for Diverse Similarity Search, ICML 2025. That work is not restricted to categorical colors: Section 1.1 and Appendix A explicitly allow an arbitrary diversity metric, including the same metric used for relevance. In particular it considers both the cases:

  • where the goal is to minimize the maximum query distance subject to a diversity requirement (minimum pairwise distance being at least a value D)
  • and maximizing diversity within a query radius.

They give theoretical guarantees with bicriteria apprxoimation and efficient query bounds under bounded-doubling-dimension assumptions.

Thus, the distinctive contribution here is the average-distance vs minimum-pairwise distance objective and its approximation analysis, rather than the introduction of distance-based diversity or graph-based diverse retrieval itself.

The above is missed both in the theory section and the experimental section of this paper. Anand et al also incorporate diversity based search algorithm into graph-based ANN and thus is very relevant for experimental comparison. However this paper mentions that Anand et al only considers the colored version (which is incorrect) and thus does not include the comparison with it.

Critical strengths

The problem is relevant, the formulation is explicit, and the nearly matching upper and lower bounds are nice.

Critical weaknesses

The closest graph-based prior work is materially mischaracterized. The statements in the introduction, lines 79-83, lines 344-345, and Appendix B.2, lines 764-769, that Anand et al. rely on categorical attributes and do not extend to metric diversity are incorrect. Their full paper, especially Section 1.1 and Appendix A, explicitly handles an arbitrary diversity metric. Thus the novelty discussion and the rationale for excluding this work from the comparisons need revision. A useful comparison would distinguish objectives, assumptions, preprocessing requirements, and query guarantees, and explain whether an adaptation provides a meaningful baseline.

Adding Δ\Delta is legitimate, but multiplicative approximation is not invariant under additive shifts. A large database diameter, potentially caused by objects irrelevant to the query, can therefore make the guarantee weak for the unshifted relevance-diversity tradeoff.

Questions for authors

Please see the weaknesses.

2 comments

We sincerely appreciate your insightful comments and respond to each of them below.

For W1: Comparison with Anand et al.'s Work. First, we acknowledge that our original description of Anand et al.'s work was not precise enough. They do extend their framework to arbitrary diversity metrics in Appendix A, which can potentially be compared with our method after adaptation. As such, we have added clarifications at the corresponding places.

Nevertheless, we should note that significant differences still remain between our work and Anand et al.'s. Specifically, the extension still follows a formulation of minimizing the average query distance (i.e., maximizing relevance) under a diversity constraint, whereas our formulation optimizes a weighted combination of average query distance and minimum pairwise distance. We further note that the main part of Anand et al.'s work focuses on a color-based (i.e., categorical attribute-based) diversity definition, and all of their implementations and experiments were conducted in that setting. Their general metric extension is presented as a theoretical algorithm in Appendix A and is not accompanied by empirical evaluation. In fact, the authors themselves acknowledge that their provable indexing algorithm has a runtime that “is quadratic in the size of the dataset and slow in practice,” which is why their experiments rely on a heuristic construction.

For the rebuttal, we adapted Anand et al.'s heuristic algorithm (originally published on their shared GitHub repository) to general metric diversity and included the adapted method as a new baseline, Anand-M, in our experiments. The detailed implementation and settings are provided in the revised version of our manuscript. We have incorporated Anand-M into our experiments: MTGS achieves a lower objective than Anand-M in six of the eight settings and is 1.97–19.88× faster in all eight. These results confirm that MTGS still achieves a clear advantage in terms of the overall quality–latency trade-off, with Anand-M taken into account.

For W2: Approximation Bound. We agree that adding the database diameter Δ preserves the minimizer but changes the meaning of a multiplicative bound. Nevertheless, introducing the additive shift Δ is indispensable for deriving a rigorous multiplicative bound. In addition, approximation bounds will not be significantly weakened by additive shifts in practice. To confirm this, we additionally assess how close our solutions are to the optimal ones. We compared their unshifted objective values against the optima computed by mixed integer linear programming (MILP). We solved a small SIFT instance with 5,000 objects and chose K=5K = 5. The results show that the relative gap to each query's optimum averaged only 0.89% for TGS and 5.68% for MTGS, demonstrating that the approximate solutions returned by TGS and MTGS attain significantly better approximation bounds in practice than those (i.e., 4/3+ϵ4/3+\epsilon and 2+ϵ2+\epsilon) for the worst case in the theoretical analysis.

Thank you for the response and the additional experiments. I appreciate the acknowledgment of the general-metric results of Anand et al., the addition of Anand-M, and the comparison with exact solutions. These are useful improvements, and I no longer regard the experimental comparison with that work as entirely missing. Nevertheless, the revision does not fully resolve my concerns about the positioning and significance of the contributions.

The comparison with prior work still needs a precise statement of the objectives and guarantees.

The rebuttal states that the general-metric extension of Anand et al. follows "a formulation of minimizing the average query distance." This is incorrect: Definitions 2.3 and A.3 of that paper minimize the maximum distance from the query to a selected point, subject to a diversity requirement. Definition A.4 also considers maximizing diversity within a query radius. The present paper instead combines average query distance and minimum pairwise separation in a weighted objective. Thus, both average versus maximum query distance and scalarization versus a constraint are meaningful differences that should be stated accurately.

I acknowledge the new footnote in the introduction and the clarification in Appendix B.2. However, the introductory comparison still discusses Anand et al. primarily through its color-based setting, leaving the directly relevant general-metric results to the footnote. My concern is not the placement of a citation by itself, nor a claim that the two papers solve identical problems. Rather, the contribution should be positioned explicitly relative to existing general-metric, graph-based diverse retrieval, with a comparison of the objectives, assumptions, and query guarantees. The new Anand-M results are useful evidence for the proposed heuristic at the tested configurations, but they do not replace this theoretical comparison.


Adding a large database diameter Δ\Delta can make the multiplicative bound weak for the unshifted relevance-diversity tradeoff. My concern is the significance of the guarantee, not its formal correctness.

I understand that adding the term Δ\Delta helps with getting the multiplicative approximation. But the reason is that adding it makes such approximation straightforward as I described in the content of my review.

In fact, ordinary exact nearest neighbors already give a constant-factor solution without optimizing diversity. Let NN be the exact KK-nearest-neighbor set, S∗S* an optimal solution, and b=div(S∗)b=div(S*). Nearest-neighbor optimality gives

fλ(q,N)≤fλ(q,S∗)+λbf_\lambda(q,N)\leq f_\lambda(q,S*)+\lambda b

By Lemma 2.1 and Δ≥b\Delta\geq b, we have fλ(q,S∗)≥(1−λ)b/2−λb+Δ≥32(1−λ)bf_\lambda(q,S^*)\geq (1-\lambda)b/2-\lambda b+\Delta \geq \tfrac32(1-\lambda)b.

Consequently, for 0≤λ≤1/20\leq\lambda\leq1/2, fλ(q,N)fλ(q,S∗)≤1+2λ3(1−λ)≤53\frac{f_\lambda(q,N)}{f_\lambda(q,S^*)} \leq 1+\frac{2\lambda}{3(1-\lambda)} \leq \frac53.

This establishes a 5/35/3 approximation even without diversity-aware selection, although it does not establish the sharper 4/3+ϵ4/3+\epsilon bound.


Also I noticed a pontential misunderstanding. Quoting from your rebuttal response to Q1 of reviewer 8vMZ: "Although max-min diversification itself is sensitive to outliers that are far from all normal points, as adding these outliers to the solution can lead to high diversity values, our problem formulation and search algorithms have already mitigated this issue."

Max-min diversification is sensitive to "close-by" points. E.g. when you add an outlier point that is very close to an already existing point, then the diversity suddenly decreases heavily. In your response you are saying the opposite that outliers are far from normal points. Adding such a point cannot suddenly increase the minimum pairwise distance between the other k-1 points arbitrarily. That is why the reviewer is asking you why you do not consider e.g. max-sum notion for diversity (i.e. sum of pairwise distances as opposed to the minimum pairwise distance).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.