Welfarist Formulations for Diverse Similarity Search
Authors: Siddharth Barman
Nirjhar Das
Shivam Gupta
Kirankumar Shiragur
Venue: ICLR 2026 Poster (2026)
Keywords: Vector Search
Approximate Nearest Neighbor Search
Nash Social Welfare
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: This work develops novel welfare-based formulations for balancing diversity with relevance in nearest neighbor search

Abstract: Nearest Neighbor Search (NNS) is a fundamental problem in data structures with wide-ranging applications, such as web search, recommendation systems, and, more recently, retrieval-augmented generations (RAG). In such recent applications, in addition to the relevance (similarity) of the returned neighbors, diversity among the neighbors is a central requirement. In this paper, we develop principled welfare-based formulations in NNS for realizing diversity across attributes. Our formulations are based on welfare functions---from mathematical economics---that satisfy central diversity (fairness) and relevance (economic efficiency) axioms. With a particular focus on Nash social welfare, we note that our welfare-based formulations provide objective functions that adaptively balance relevance and diversity in a query-dependent manner. Notably, such a balance was not present in the prior constraint-based approach, which forced a fixed level of diversity and optimized for relevance.  In addition, our formulation provides a parametric way to control the trade-off between relevance and diversity, providing practitioners with flexibility to tailor search results to task-specific requirements. We develop efficient nearest neighbor algorithms with provable guarantees for  the welfare-based objectives. Notably, our algorithm can be applied on top of any standard ANN method (i.e., use standard ANN method as a subroutine) to efficiently find neighbors that approximately maximize our welfare-based objectives. Experimental results demonstrate that our approach is practical and substantially improves diversity while maintaining high relevance of the retrieved neighbors.

Published as a conference paper at ICLR 2026
WELFARIST FORMULATIONS FOR DIVERSE SIMILARITY SEARCH
Siddharth Barman, Nirjhar Das & Shivam Gupta Indian Institute of Science Bangalore (barman, nir fairrhardde harrda, shi aat.ivaagutaa
Kirankumar Shiragur
Microsoft Research India ashiragurrmiccroott..com
ABSTRACT
Nearest Neighbor Search (NNS) a fundamental problem data structures with wide-ranging applications, such web search, recommendation systems, and, more recently, aurrieval-augmennt tions, in addition to the relevance (similarity) of the returned neighbors, diver- sity among the neighbors is central requirement. In this paper, we develop principled welfare- belfare-based formulations in NNS for realizing diversity across at- tributes. Our formulations are based on welfare functions-fron mathematical economics-tte that satisfy central diversity (fairness) and relevance (economic effi- ciency) axioms. With particular focus on Nash social welfare, we note that our welfare-bard based formulations provide objective functions that adaptively balance relevance and diversity in a query-dependent manner. Notably, such balance was not present in the prior constraint-based approach, which forced a fixed level of diversity and optimized for relevance. In addition, parametric way to control the trade-off between relevance and diversity, providing practitioners with flexibility tailor search results to task-specific requirements. We develop efficient nearest neighbor algorithms with provable guarantees for the welfare-bases objectives. Notably, algorithm standard ANN method (i.e., use standard ANN method as subroutine) to effi- ciently find neighbors that approximately maximize our welfare-basee objectives. Experimental results demonstrate that our approach is practical and substantially improves diversity while maintaining high relevance of the retrieved neighbors.
generations (RAG). such recent applica-
formulation provides a
be applied top of any
INTRODUCTION
Nearest Neighbor Search (NNS) is fundamental problem in computer science with wide- ranging applications in diverse domains, including computer vision (Wang et al., 2012), data min- ing (Camerra et al., 2010), information retrieval (Manning et al., 2008), classification (Fix & Hodges, 1989), and recommendation systems (Dahiya al., 2021). The relevance of NNS has grown further in recent years with the advent of retrieval-aus -ugmeentd generation (RAG); see, e.g., (Manohar et al., 2024), (Wu al., 2024), and references therein. Formally, given vectors P Rd (in ambient di- mension d) and a query vector q E IRd, the objective in NNS is to identify subset S of k (input) vectors from P that most similar to g under similarity function NNS corresponds to the optimization problem arg max sC| Eves (g. v). Note that, while most prior works in neighbor search express the problem in terms of minimizing distances, we work with the symmetric version of maximizing similarity.'
RRd x Rdd IR,. That is,
In practice, the input vectors are high dimensional: in many the above- mentto-metiooed applications the ambient dimension d is close to thousand. This scale and the large cardinality of P make exact NNS computationally expensive, since applications require, for real-time queries q. NNS solutions
This enables directly apply welfare functions.

---

Published as a conference paper at ICLR 2026
in time (sub)linear in the number of input vectors PP. To address this challenge, the widely studied framework of Approximate Nearest Neighbor (ANN) search relaxes the requirement of exactness and instead seeks neighbors whose similarities are approximately close to the optimal ones.
ANN search has received substantial attention over the past three decades. Early techniques relied on ppaccepartitioning methods, including Docality-Sensitiee Hashing (LSH) (Indyk & Motwani, 1998; Andoni & Indyk, 2008), k-d trees (Arya et al., 1998), and cover trees (Beygelzimer et al,, 2006). More recent industry-scale systems adopt clustering-based (Johnson al., 2017; Baranchuk et al., 2018) and graph-based (Malkov & Yashunin, 2016; Fu et al., 2019; Sugawara et al., 2016; Subramanya et al., 2019) approaches, along with other practically-efficien methods (Sun et al., 2023; Simhadri et al., 2024).
While meuurede in terms of a similarity function -i. a primary objective in NNS, prior work has shown that diversity in the retrieved set of vectors is equally important for user experience, fairness, and reducing redundancy (Carbonell & Goldstein, 1998). For instance, in 2019 Google announced a policy update to limit the number of results from single domain, thereby reducing redundancy (Liaison, 2019). Similarly, Microsoft recently introduced diversity constraints in ad recommendation systems to ensure that advertisements from single seller do not dominate the results (Anand et al., 2025). Such an adjustment was crucial for improving user experience and promoting fairness for advertisers.
A natural way to formalize diversity in these settings is to associate each input vector with one or more attributes. Diversity can then be measured with respect to these attributes. Building on this idea, the current work develops a principled framework for diversity in neighbor search by drawing on the theory of collective welfare from mathematical economies (Moulin, 2004). This perspective enables the design of optimization criteria that balance similarity-based relevance and attribute-based diversity in theoretically grounded manner.
This formulation is based on welfare functions, f 1R + I. which provide a principled approach to aggregate the utilities of c E 24 agents. Specifically, among agents with utilities uj,...: Ue, re- spectively, the collective welfare is f(u,,.... ue). The theory of collective welfare develops mean- ingful welfare functions, fs, and among them, Nash social welfare (NSW) is an exemplar that upholds multiple fairness axioms, including symmetry, independence of unconcerned agents, scale invariance and the Pigou-Dalton principle (Moulin, 2004). Nash social welfare is defined by setting
as the geometric mean, NSW Ue) (TTr=1 Uz) 1/fe The fact that NSW strikes bal- ance between fairness and economic efficiency is supported by the observation that it sits between egalitarian and utilitarian welfare: the geometric mean is at least as large as the minimum value, min Sese dg, and it is also at most the arithmetic mean _ >i= We (the AM-GM inequality).
Our Formulation. To achieve diversity across attributes in NNS while maintaining relevance of the returned & vectors, our modeling insight is to equate attributes with agents and apply Nash social welfare. In particular, consider setting where we have e E Σ different attributes (across the input vectors), and let S be any size-k subset of the input vectors P. In our model, each included vector E S, with attribute f [c], contributes to the utility de (see Section 2.1), and the NSW induced by S is the geometric mean of these utilities, Ui...., Me. Our objective is to find a size-k subset, S* C P. of input vectors with as large NSW as possible (Definition 1).2
Prior work (Anand et al., 2025) imposed constraints for achieving diversity in NNS. These con- straints enforced that, for each E [c]. at most ke' of the returned vectors can have attribute f. Such hard constraints rely on fixed ad hoc quota parameter k' and may fail to adapt to the intent ex- pressed in the query. By contrast, our NSW-based approach balances relevance and diversity in a query- dependeet manner. For example, in apparel search, if the query is "blue shirt," then a con- straint on the color attribute 'blue' (i.e., when ε stands for 'blue') would limit the relevance by excluding valid vectors. NSW, however, for the "blue shirt" query, is free to select all the k vectors with attribute 'blue' upholding relevance; see Figure 1 for supporting empirical results. Simultane- ously, if the query is just "shirts," " then NSW criterion is inclined to select vectors with different color attributes. These features of NSW are further substantiated quantitatively by the stylized instances given in Examples I and (Appendix B)
TThe following instantiation highlights the applicability of our model: In an advertising context with sellers, each selected ad S of seller E [c] contributes to E's exposure (utility) ue-
2

---

Published as a conference paper at ICLR 2026
Figure 1: Neighhor search results (k on the Amazon dataset. From left: First and Second images ANN and Nash-based results for query "shirts", respectively. Third and Fourth images ANN and Nash- based results for query "blue shirt", respectively. Note that the Nash-based method selects diverse colors for the query "shirts" but conforms to the blue color for the query "blue shirt".
Our welfarist formulation extends further control the trade-off between relevance and diversity. Specifically, we also consider p-mean welfare. Formally, for exponent parameter p E(-00, 1J, the pth mean Mp(-), of c utilities ui,.... E R,, is defined as Mp( Uo) = ( >i up)'/? The p-mean welfare, Mp(.), captures a range of objectives with different values of p. it corresponds to the utilitarian welfare (arithmetic mean) when p 1, the NSW (geometric mean) with p O, and the egalitarian welfare when p-+ -oo. Notably, setting p p= 1, we get back the standard nearest neighbor objective (relinquishing diversity). At the other extreme, p + -oo aims find attribute- diverse a set of k vectors as possible (while paying scarce attention to relevance).
We study, both theoretically and experimentally, two diversity settings: (i) single-attribute and (ii) multi-attribute. In the single-attribute setting, each input vector E is associated with exactly one attribute e E [c]. the more general multi-attriburt setting, each input vector E P can have more than one attribute.
The constraint- based formulation for diversity considered in Anand al. (2025) primarily addresses Lingle-attribur setting. In fact, generalizing such constraints to the multi-attribute leads to a for- mulation wherein is NP-hard even to determine whether there exist h vectors that satisfy the constraints." The NSW formulation does not run into such barrier.
Our Contributions
The NSW formulation for diversity, in both single-attribut and multi attribttt settings, is a key contribution of the work (Definition 1). Another contribution the generalization to p-mean welfare.
We also develop efficient algorithms, with provable guarantees, for the NSW and p-mean welfare formulations. For the single-attribute setting, we develop an efficient greedy algorithm for finding vectors that optimize NSW among the attributes (Theorem 1). In addition, this algorithm can be provably combined with any sublinear ANN method (as a subroutine) to find near-optimal solutions for the Nash objective in sublinear time (Corollary 2).
For the aattii-tttiiute setting, we show that the NSW problem is NP-hard (Theorem 3). Also, we develop a volynomial-time 0.63-approximation algorithm for the logarithm of NSW (Theorem 4),
We complement our theoretical results with experiments on both real-world and semi-synthetic datasets. These experiments demonstrate that the NSW objective effectively captures the trade-off between diversity and relevance in a deeredde manner. We further analyze the behavior of the p-mean welfare objective across different values of (-oo, 1]. observing that interpolates smoothly between prioritizing for diversity, when p is small, and focusing on relevance, when large. Finally, benchmark the solution quality and running times of various algorithms for solving the NSW and p-mean formulations proposed in this work.
2 PROBLEM FORMULATION AND MAIN RESULTS
We are interested in neighbor search algorithms that not only achieve a high relevance, but also find a diverse set of vectors for each query. To quantify diversity work with model wherein each
$ For instance, the display-advertisement setup, each advertisement v belongs to exactly one seller f. "That is, it would be computationally hard to find any size-k ceastraintfeassble subset S, let alone an optimal This hardness result follows via reduction from the Maximum Independent Set problem.
3

---

Published as a conference paper at ICLR 2026
c). ,,.,, In particular, we write atb(u) S [c] to denote the attributes assigned to vector a E Also, let Dj denote the subset of vectors that are assigned attribute É E [c], i.., D2 = Plee atb(r)).
input vector P is assigned one more attributes from the set [c] =11,2....
2.1
OUR RESULTS
An insight of this work is equate these attributes with distinct agents. Here, the output of neighbor search algorithm-i.e. the selected subset S C P-induues utility among these agents. With this perspective, we define the Nash Nearest Neighbor Search problem (NaNNS) below. This novel formulation for diversity is a key contribution of this work. For any query E R² and subset S C.P. we define utility uz(S) = E LessnD, (q, v), for each é [c]. That is, uz(S) equal the cumulative similarity between q and the vectors in S that belong De. Equivalently, ue(S) (S) the cumulative similarity of the vectors in S that have attribute t.3
We employ Nash social welfare to identify size-k subsets that are both relevant (with respect to similarity) and support diversity among the attribute classes. The Nash social welfare among c agents defined as the geometric mean the agents' utilities. Specifically, in the above-mentioned utility model and with smoothening parameter 1) O, the Nash social welfare (NSW) induced by any subset S C P among the attributes is defined as NSW(S) == (T (uy(S) + 7))" Throughout, v) > 0 will be a fixed smoothing constant that ensures that NSW remains nonzero.
Definition 1 (NaNNS), Nash nearest neighbor search (NaNNS) corresponds the optimization problem: arg max scjjss: NSW(S), or, equivalently,
arg max log NSW(S)
SCP.ss=
Here, we have log - =
log (og(u((S)) n))
To further appreciate the welfarist approach, note that one recovers the standard nearest neigh- bor problem, NNS, in the single-atrribute setting, in-instead of the geometric mean-we maximize the arithmetic mean. That is, maximizing the utilitarian social welfare gives us maxsçP:(S)= - ur()) maxsgP:($)=* -.veso(q,
As stated the introduction, depending on the query and the problem instance, solutions obtained via NaNNS can adjust between the ones obtained through standard NNS and those obtained via hard constraints. This feature is illustrated in the stylized examples I and 2 stated in Appendix B.
With the above-mentioned utility model for the e attributes, we also identify an extended formu- lation based on generalized p-means. Specifically, for exponent parameter E (-o0, 1), the pth mean Mp(-). of e nonnegative numbers W1, W2 ... We R,, defined as Mp ..., we) = ( Ei w²")
1/p Note that Mi (wi,,..,, w.) is the arithmetic mean _ - We. Here, when p + O.
obtain the geometric mean (Nash social welfare): Mo(w1,... ... we) (li w/ Further, + xo gives us egalitarian welfare, M-oe (w),.. we) = ming wy.
Hence, generalizing both NNS and NaNNS, have the p-mean nearest neighbor search (p-NNS) problem defined, for exponent parameters p E (-o0, 1). as follows:
max SC 15
M)(ur(S),.... ... uc()))
Diversity in Single- and Multi-Attribute Settings. The current work addresses two diversity set- tings: the single-attribute setup and, the more general, the multi-attribute one. The single-attribute setting refers to case wherein |atb(u]] = for each input vector v E P and, hence, the attribute classes D,s are pairwise disjoint. In the more general multi-attribute setting, have |atb())] 2 1; here, the sets Dz-s intersect." 6 Notably, the NaNNS seamlessly applies to both these settings.
$ Note that in the above-mentioned display-ade aavertiin example, me(-) -)) is the cumulative similarity hetween the (search) query and the selected advertisements that are from seller &. 'oor a motivating instantiation for multi-atrributes, note that, in the apparel-search context, it is possible for product (input vector) to have multiple attributes hased v's seller and its color(s).
4

---

Published as a conference paper at ICLR 2026
Algorithmic Results for Single-Attribus NaNNS and p-NNS. In addition to introducing the NaNNS and p-NNS formulations for capturing diversity, we develop algorithmic results for these problems. thereby demonstrating the practicality of our approach in neighbor search. In particular, in the single-attribute setting, we show that both NaNNS and p-NNS admit efficient algorithms.
Theorem 1. In the single-atrribute attribute setting, given any query q E E and an (exact) oracle ENN for k most similar vectors from any set, Algorithm I (Nash-ANN) returns an optimal solution for NaNNS, iee, it returns a size-k subset ALG S P that satisfies ALG E arg ma (||Ss/= NSW (S). Furthermore, the algorithm runs in time Okke) + Ei-1 ENN( Dr, q), where ENN De, Q) is the time required by the exact oracle find I most similar vectors to q Di.
Further, to establish the practicality of our formulations, we present an approximate algorithm for NaNNS that leverages any standard ANN algorithm as an oracle (subroutine). i.e., works with any a-approximate ANN oracle (a E (0, 1)) which returns subset S containing k vectors satisfying a (q. (()) 2 a alg, i(g); for all i [k), where ((() and (% are the i-th most similar vectors to q in S and P. respectively. Formally,
Corollary 2. In the single-attributt setting, given any query q Rd and an a-approximate oracle ANN for k most similar vectors from any set, Algorithu 1 Mtash-ANN returns an a- approximate solution for NaNNS, i.e., returns a size-k subset ALG S P. with NSW(ALG) 2 maxsCP: [s|= [ (S). The algorithm runs in time O(kc) + Ei= ANN(Di, Q) with ANN(De, q) denoting the time required by the oracle to find k similar vectors to in Dz.
Furthermore, both Theorem and Corollary 2 generalize to p-NNS problem with slight modification in Algorithm 1. Specifically, there exists exact, efficient algorithm (Algorithm 3) for the p-NNS problem (Theorem 11 and Corollary 12). Due to space constraints, the algorithm and the analysis for p-NNS are deferred to Appendix E.
Algorithmic Results for Multi-Attribute NaNNS. Next, we address the multi-attribute setting. While the optimization problem (1) in the single attribute setting can be solved efficiently, the prob- lem is Hard in the the aulti-attribute setup (see Appendix C for the proof).
Theorem 3. In the multi-atribute setting, with parameter 1) = NaNNS is NP-hard.
Complementing this hardness result, we show that, considering the logarithm of the objective, NaNNS in the antti-et setting admits polynomial-timg - approximation algorithm. This result in established in Appendix D.
Theorem 4. In the multi-attribute setting, there exists a polynomial-ting algorithm (Algorithm 2) that, given any query q E Rd, finds size-k subset ALG S P with log NSW NSW(ALG) 2
2)-2)log (SPT):)); here, OPT denotes optimal solution (1).
Experimental Validation of our Formulation and Algorithms. We complement our theoretical results with several experiments real-world datasets. Our findings highlight that the Nash-based formulation strikes a balance between diversity and relevance.
3 ALGORITHM FOR NANNS
This section provides our exact, efficient algorithm (Algorithm 1) for NaNNS in the single-attribute setting. The algorithm has two parts: preprocessing step and a greedy, iterative selection.
Recall that in the single-attribute setting, the input vectors P are partitioned into subsets Dı,.... D.- where Dr denotes the subset of imput vectors with attribute each attribute f E [c]. we populate vectors from within De that are most similar to the given query q E Rdd Such a size-k subset, for each
[c]. In the preprocessing step, for
[c], can be obtained by executing any nearest neighbor search algorithm within Dj and with respect to query q. Alternatively, we can execute any standard ANN algorithm as subroutine and find sufficiently good approximations for the nearest neighbors (of q) within each D;-
Write Dj C D2 to denote the exact or approximate -eciiieeeeeesttteeeee neighbors of g E Id in Dr. We note that our algorithm is robust to the choice of the search algorithm (subroutine) used for finding Dys: If D&s are exact nearest neighbors, then Algorithm optimally solves NaNNS in the single-attribute
5

---

Published as a conference paper at ICLR 2026
Algorithm Nash ANN: Algorithm for NaNNS in the single-attribute setting
Require: Query q E Rd and, for each attribute & [c]. the set of input vectors D, C Rd
1: For each & E [c]. fetch De, the k (exact or approximate) nearest neighbors of q E I from Dr.
2: For every L E [c] and each index i E [k), let ofo denote the ith most similar vector to q in Dg.
3: Initialize subset ALG 0. along with count ky and utility we O, for each & [c].
4: while |ALG| < k do
5: Let a = arg max (log (w, + 17 ogq o 1) log(ws + n)) (Ties broken arbitrarily.)
EE(c]
6: Update ALG + ALG U f (opnat1) along with wa +- wa + (g. +1)++1)) and kia +- hia + 1.
along
7: Return ALG.
setting (Theorem 1). Otherwise, if Dys are obtained via an ANN algorithm with approximation guarantee E (0, 1), then Algorithm I achieves an approximation ratio of a (Corollary 2).
The algorithm then considers the vectors with each De in decreasing order of their similarity with q- Confining to this order, the algorithm populates the & desired vectors iteratively. In each iteration, the algorithm greedily selects new vector based the marginal increase in log NSW(-); Lines 5-6 in Algorithm 1. Theorem and Corollary 2 provide our main results for Algorithm I; Proof of Theorem is presented below while the proof of Corollary 2 is deferred to Appendix A.1.
Proof of Theorem 1. The runtime of Algorithm can be established by noting that Line requires Σi=1 (NN(DE, q) time to populate the subsets Djs, and the while-loop (Lines 4-6) iterates & times and each iteration (specifically, Line runs in (c) time. Hence, as stated, the time complexity of the algorithm is Okk) + >m= ENN(D;, 4).
Next, we prove the optimality of the returned set AL.G. Let OPT arg max NSW(S) be an optimal solution with attribute counts |OPT n Del as close to |LG De as possible. That is, among the optimal solutions, it is one that minimizes Ei=1 |k kel. where kj = |OPT n Del and kg ALG Del, for each e E [c). We will prove that OPT satisfies k ke for each & [c]. This guarantee along with Lemma 6 imply that, as desired, ALG is a Nash optimal solution.
Assume, towards a contradiction, that k * ke for some E [c]. Since OPT |LGG| = k, there exist attributes 2. y E [c] with the property that kg < kiz and ky > ky. For a given attribute é E [c]. define the logarithm of cumulative similarity upto the 7th most similar vector (e( = log EE=z og, of)) + n), where " is defined in Line of Algorithm 1.
Next, note that for any attribute E [c]. if Algorithm 1, at any point during its execution, has included Kg vectors of attribute l in ALG, then that point the maintained utility we = Σ o4 x Hence, at the beginning of any iteration of the algorithm, if the KG denotes the number of selected vectors of each attribute e E [c]. then the marginals considered in Line 5 are F& (K₃ + 1) Fe (k)).
These observations and the selection criterion in Line 5 of the algorithm give us the following in- equality for the counts kg |LL Dz and ky |LG n Dyl of the returned solution ALG:
F2 Fk (k 1) 2 (k + 1) F (ky.)
Specifically, equation (2) follows by considering the iteration in which 1:th (last) vector of attribute was selected by the algorithm. Before that iteration the algorithm had selected (k2 - 1) vectors of attribute x, and let k denote the number vectors with attribute y that have been selected till that point. Note that Ky < kg. The fact that the Athh vector was (greedily) selected in Line 5, instead of including an additional vector of attribute y. gives Fz (kz.) F. (k. 1) 2 Fy (KY + 1) - (2 > Fy (kg + 1) Fy (kyy): here, the last inequality follows from Lemma 5. Therefore we have,
(w)) F. (K + 1) Fa (K2) 2 (k(a)) - Fek 1) 2 (Ky + 1) (kw) 2 Fy(k)) - Fg (, - 1) (3)
Here, inequality (i) follows from ke < k and Lemma 5, inequality (ii), from equation 2, and inequality (iii), from ke > by and Lemma 5.

---

Published as a conference paper at ICLR 2026
Next, observe that the definition of De ensures that f/s is in fact the 7th most similar (to q) vector among the ones that have attribute é, i.e. 1th most similar in all of Dj. Since OPT is an optimal solution, the ky = |OPT n Del vectors of attribute E in OPT are the most similar ky vectors from De- That is, OPT n De = fe (1))...... (k;)) F. for each e E [c]. This observation and the definition of Fe(.) imply that the logarithm of OPT's NSW satisfies log NSW(OPT) - _ Ei Fe(kg), Now, consider a subset of vectors 5 obtained from OPT by including vector 1(k2+1) and removing u "A:)> i.e., S = - o (0))==)) {{
2/ (kg))) Note that
log NSW(S) - log (SW() = - (F 11) (o())) +
1 { (L -1) 1) F2, 2 O. e
where the last inequality is via eqn. (3). Hence, we have shown that (S) 2 (SPT) Given that OPT is Nash optimal solution, the last inequality must hold with equality, NSW(S) = (SW() i.e., S is an optimal solution as well. This, however, contradicts the choice of OPT as
an optimal solution that minimizes Σi= |kg
kyl: note that Σi= The
ke < Ei= 2kg kel.
where hyg IS n Del.
Therefore, by way of contradiction, we obtain that |OPT n Dz = |LLG n Del for each & E [c]. As mentioned previously, this guarantee along with Lemma 6 imply that ALG is a Nash optimal solution. This completes the proof of the theorem.
4 EXPERIMENTAL EVALUATIONS
In this section, we validate the welfare-based formulations and the performance of our proposed algorithms against existing methods on variety of real and semi-synthetic datasets. We perform three different kinds of experiments. In the first set of experiments (Figure 2, Top row), we compare Nash-ANN (Algorithm 1) with prior work on hard-constraint based diversity (Anand et al., 2025). Here, we show that - strikes a balance between relevance and diversity both in the single- and multi-attribute settings. In the second set of experiments (Figure 2, Bottom row), we study the effect of varying the exponent parameter p in the p-NNS objective on relevance and diversity, in both single- and aulti-attribute settings. In the final set of experiments,
compare our algorithm, Nash-ANN (with provable guarantees), and a heuristic that improves the runtime of Nash-ANN ANNN The heuristic directly utilizes standard ANN algorithm to fetch sufficiently large candidate set of vectors (irrespective of their attributes). Then, it applies the Nash (or p-mean) selection only within this set. Due space constraints, we defer the details of the third set of experiments Appendix F.5. Additional plots for the first two experiments appear in Appendices F.3 and F.4.
Below, we outline the metrics, experimental setup, datasets, and algorithms used in our experiments.
Relevance and Diversity Metrics. To quantify relevance of an algorithm we consider the ratio of the sum of the similarity scores. Formally, for a query q. if A is the set of neighbors returned by an algorithm and O is the set of k nearest neighbors, then the approximation ratio achieved by the algorithm is given by the ratio (EegA (v, 4)) (Eveo or (v. 4)). Hence, this ratio lies in [0. 1). and higher approximation ratio indicates a more relevant solution. We also report results in terms of recall, which is another metric for relevance; see Appendix F.1 for further details.
To quantify diversity, we use entropy that measures how uniformly an algorithm distributes its se- lected vectors across the attributes. Entropy of a size-k subset C the single-attribute setting is given by the quantity Exe(c) PP log(p:) where Pe- [ Note that higher entropy value indicates greater diversity. Moreover, it is not hard to see that the highest possible value of entropy is log(k) (achieved when S contains at most vector from each attribute). higher value of entropy indicates more attribute-level diversity in the algorithm's ''s output. We also experimentally validate the findings under other diversity metrics, namely the inverse Simpson index and distinct attribute counts; see Appendix F.I.
Note that the diversity metrics defined above are for the linle-attribute. setting. In the setting, in our experiments, we focus settings where the attribute set [c] is partitioned into sets {C.) (i.c., [c] = , C2) and every input vector v E P is associated with exactly one attribute from each C. In partieular, (atb(r)) m and (atb(r) n Cal 1 for each 1 x z 5 m. We call each
7

---

Published as a conference paper at ICLR 2026
Table 1: Summary of considered datasets. For synthetic attributes, we use two strategies: clustering- based (suffixed by Clus) and distribution-ban based (suffixed by P Prob), see Appendix F.2 for details.
Dataset
# Input Vectors
# Query Vectors
Dimension
Attributes
Amazon
92, 092
3,956
768
product color
ArXiv
200, 000
50, 000
1536
year, paper category
Siftim
1, 1,000, 000
10, 000
128
synthetic
Deeplb
9, 7,990, 000
10, 000
96
synthetic
C an attribute class. To measure diversity in the multi-attribute setting, we consider the aforemen- tioned diversity metrics like entropy and inverse Simpson index restricted to an attribute class C.. For instance, the entropy a set S C P restricted to a particular C₁ is given by LIEo,pE0 -pr log(ps), |
where Pt-
Experimental Setup and Datasets. We report results both semi-synthetic and real-world datasets consistent with prior works (Anand et al., 2025) and are summarized in Table and de- tailed in Appendix F.2.
Algorithms. Next, we describe the algorithms we executed.
1. ANN: This is the standard ANN algorithm that aims to maximize the similarity of the retrieved vectors to the given query without any diversity considerations. In our experiments, we use the graph based DiskANN method of Subramanya et al. (2019) as the standard ANN algorithm. We instantiate DisKANN with candidate list size L = 2000 and the maximum graph degree as 128. Here, we also set the pruning factor at 1.3, consistent with the existing recommendation in Anand al. (2025).
2. Div-ANN: This refers to the algorithm of Anand et al. (2025) that solves the hard- constraint- based formulation for diversity in the single-attribute setting. Recall that Anand al. (2025) aims to maximize the similarity of the retrieved vectors to the given query subject to the constraint that no more than E vectors in the retrieved set should have the same attribute. Note that the smaller the value of K, the more diverse the retrieved set of vectors. Moreover, k' has to be provided as an input to this algorithm. In our experiments, we set K' E 51, when k 10, and k' {1, 5, 103 when k = 50.
Nash-ANN and p-mean-ANN. Nash-ANN refers to Algorithm and p-mean ANN refers to Algorithm 3 (stated in Appendix E). Recall that Algorithm 1 and Algorithm 3 optimally solve the NaNNS and the p-NNS problems, respectively, in the single-attribute setting given access to an exact nearest neighbor search oracle (Theorems I and 11). Further note that the p-mean welfare function, (.).). reduces to the Nash social welfare (geometric mean) when the exponent parameter p 0+. For readability and required places, will write p O to denote Nash-ANN. We conduct experiments with varying values of p E {-10, -1, 0.5, 0, 13.
Multi Nash-ANN and Multi Div-ANN: In the multi-attribute setting, there are no prior methods to address diversity. Hence, for comparisons, we first fetch L = 10000 candidate vectors from P for each query q. using the standard ANN method, and then apply the following algorithms on the candidate vectors: (i) our algorithm for the NaNNS problem in the multi-attribute setting (Al- gorithm 2), which we term Multi ANNN and (ii) an adaptation of the algorithm of Anand et al. (2025), referred hereon Multi Div-ANN, which greedily selects the most similar vectors to the query subject to the constraint that there are no more than k vectors from each attribute. 8 We compare Multi Nash ANN (p- 0) against Multi Div ANN under different choices of k''
Multi p-Mean-ANN: In the multi-attribute setting, we also implement an analogue of Mu Multi Nash-ANN that (in lieu of NSW) focuses on the y-mean welfare, Mp. The objective in these experiments is to understand the impact of varying the parameter p and the resulting tradcoff between relevance and diversity. Here, for each given query, we first fetch set of L 10000 candidate vectors using ANN. Then, we populate a set of k vectors by executing a marginal-gains greedy
Both these choices are sufficiently larger than standard values, 200 and maximum graph degree 64. 'Note that one vector can have multiple attributes, hence contributing to the constraint of multiple attributes. Therefore, the issue of identifying an appropriate k is exacerbated on moving the multi-atribute setting.
8

---

Published as a conference paper at ICLR 2026
Deng
1310
Gatrer (orruee CD
gk015
J
tecress
PP
grom
AM
Mell
Mall lesh AN1
Apgrosimation Ratio
Appracimation Rablo
Approsimation Tallo
Apprestmation Radie
Anazen
Despib-iClss
Mal Di-
AR
AnS
ap-0.5
Eibragy
1P+05
Pgy
rg1
p4ron-Att
355
53
6.55
66 65
Aporeximation
66 6.0
Appresznation Paaioe
Approstration Ratio
Figure 2: Top Row: Columns and 2- Comparison of approximation ratio versus entropy trade-offs be- tween Nash-ANN, and Div-ANN with varying K', for k = 50 on Amazon and Deeplb-(Clus) datasets in the singlo-attribute setting. Columns 3 and 4 Comparison of approximation ratio versus entropy trade- offs (across attribute classes C1 and C2) between Multi Nash-ANN, and Multi DiV-ANN with varying k' on Sirtlm-(CLus and 2 Approximation ratio versus entropy trade-off's for p-mean-AND at various p values, for k 50 on Ama and DeepIb- (Cluus) datasets in the single-atrribute setting. Columns 3 and 4 Approximation ratio versus entropy trade-offs (across attribute classes Ci and C2) for Multi p-mean -NNN with varying p on Si siftlm-(Clus) dataset with k= in the multi-atribute setting.
dataset with & = 50 in the multi-atrrbbte setting. Bottom Row: Columns 1
method over the I. candidate vectors. In particular, we iterate l times, and in each iteration, select a new candidate vector that: (i) for p E (0, 1]. yields the maximum increase in Mp(-)P, or (ii) for p leads to the maximum decrease in (.).)²
4.1 RESULTS: BALANCING RELEVANCE AND DIVERSITY
Single-attribute setting. We first compare, in the single-attribute setting, the performance of our algorithm, Nash-ANN, with ANN and Div-ANN (with different values of k'). The results for the Amazon and Deep us) datasets with & = 50 are shown in Figure 2 (top row, columns one and two). Here, ANN finds the most relevant set of neighbors (approximation ratio close to 1), albeit with the lowest entropy (diversity). Moreover, as can be seen in the plots, the most diverse (highest entropy) solution is obtained when we set, in Giv-ANN, k' = 1; this restricts each é e [c] to contribute at most one vector in the output of Div-ANN, Also, note that one can increase the approximation ratio (i.e., increase relevance) of Div-ANN while incurring a loss in entropy (diversity). by increasing the value of the constraint parameter k'. However, selecting a 'right' value for k' is non-obvious, since this choice needs to be tailored to the dataset and, even within it, to queries (recall "blue shirt" query in Figure 1).
By contrast, ANN does not require such ad hoc adjustments and, by design, finds a balance between relevance and diversity. Indeed, as can be seen in Figure (top row), Nash-AM main- tains an approximation ratio close to while achieving diversity similar to Div-ANN with k = 1. Moreover, Nash -NNN ANN Pareto dominates Div-ANI with k' = 2 for Ama zon dataset and k' for Deeplb-(Clus) dataset on the fronts of approximation ratio and entropy. The results for other datasets and metrics follow similar trends and are given in Appendix F.3.
aulti-attribute setting, In the multi-attribute setting, we report results for Multi Nash-ANN and Multi Di on the si ft dataset (Figure 2, Top row-columns 3 and 4) for I = 50 and e = 80. These eighty attributes are partitioned into four sets, {C,) with each set of size [C,| = 20, i.e., [c] = - C. Further, each input vector e is associated with four at- tributes ((ab(()) = 4), one from each C₁ see Appendix F22 for further details. Here, to quantify diversity, we separately consider for each E [4], the entropy across attributes within a C.. In Fig- ure 2 (Top row-columns 3 and 4), we compare the approximation ratio versus entropy trade-offs of Multi Nash-ANN against Multi Div-ANN with varying k' Here we show the results for attribute classes C1 (column 1) and C2 (column 2) whereas the results for C3 and Ca are given in

---

Published as a conference paper at ICLR 2026
Figure 35. We observe that Multi Nash-ANN maintains high approximation ratio (relevance) while simultaneously achieving significantly higher entropy (higher diversity) than ANN. By con- trast, in the constraint-based method Multi Div-ANN, low values of k' lead to a notable drop in the approximation ratio, whereas increasing k' reduces entropy. For example, for k' below 15, one obtains approximation ratio less than 0.8, and to reach approximation ratio comparable to Multi Nash-ANN, one needs k' as high as 30. Additional results for the ArXiv dataset in the multi-attribute setting are provided in Appendix F.4, and they exhibit trends similar to the ones in Figure 2. These findings demonstrate that Multi Nash-ANN achieves a balance between rele- vance and diversity. In summary
Across datasets, and in both single- and multi-attribute settings, the Nash formulation consis- tently improves entropy (diversity) over ANN, while maintaining an approximation ratio (rele- vance) of roughly above 0.9. By contrast, the card-constrained formulation is highly sensitive the choice of the quola parameter K,, and in some cases incurs a substantial drop approx- imation ratio (even lower than 0.2).
Results for p-NNS. We experiment with p E (1,0,-1,-003 0, 0.5, 1) in both single- and multi- attribute settings and show that a trade-off between relevance (approximation ratio) and diversity (entropy) can be achieved by varying p. For the single-attribute setting, Figure 2 (Bottom row- columns and 2), and for the multi-attribute setting, Figure 2 (Bottom row-columns and 4) capture this feature on Siftlm-(Ci)) entropy but lower approximation ratio, while p = 1 matches ANN. For the multi-attribute setting, show results for attribute classes Ci (column 3) and C2 (column 4) in Figure 2 bottom row, whereas the results for C3 and C4 are shown in Figure 35. Note that in the multi-attribute setting, Multi p mean- -NN with p -- Pareto dominates Multi Div ANN with K' 1 in terms of approximation ratio and entropy. Moreover, analogous results are obtained for other datasets and metries; see Appendix F.3 and F.4.
dataset with k 50: For lower values of p. we have higher
CONCLUSION
In this work, we formulated diversity in neighbor search with welfarist perspective, using Nash social welfare (NSW) and p-mean welfare as objectives. Our NSW formulation balances diversity and relevance in a query-dependent manner, satisfies several desirable axiomatic properties, and naturally applicable in both single-attribute and multi-attribute settings. With these properties, our formulation overcomes key limitations of the prior hard-constrained approach (Anand et al., 2025). Furthermore, the more general p-mean welfare interpolates between complete relevance (p = 1) and complete diversity (p -oo), offering practitioners tunable parameter for real- world needs. Our formulations also admit provable and practical algorithms suited for low-latency scenarios. Experiments real-world and semi-synthetic datasets validate their effectiveness in balancing diversity and relevance against existing baselines.
An important direction for future work is the design of sublinear-tine approximation algorithms, in both single- and multi-attribute settings, that directly optimize our welfare objectives as part of ANN algorithms, thereby further improving efficiency. Another promising avenue to extend welfare- based diversity objectives to settings without explicit attributes.
ACKNOWLEDGEMENTS
Siddharth Barman, Nirjhar Das, and Shivam Gupta acknowledge the support of the Walmart Center for Tech Excellence (CSR WMGT-23-0001) and an Ittiam CSR Grant (OD/OTHR-24-0033)
REFERENCES
Sofiane Abbar, Sihem Amer- Yahia, Piotr Indyk, and Sepideh Mahabadi. Real-time recommendation of diverse related articles. In Proceedings of the 22nd international conference World Wide Web, pp. 1-12, 2013a.
Sofiane Abbar, Sihem Amer- Yahia, Piotr Indyk, Sepideh Mahabadi, and Kasturi R Varadarajan. Diverse near neighbor problem. In Proceedings of the twenty-ninth annual symposium on Com- putational geometry, pp. 207-214, 2013b.
10

---

Published as a conference paper at ICLR 2026
Piyush Anand, Piotr Indyk, Ravishankar Krishnaswamy, Sepideh Mahabadi, Vikas C. Raykar, Ki- rankumar Shiragur, and Haike Xu. Graph-basee based algorithms for diverse similarity search. In Forty- second International Conference Machine Learming, 2025. httpt:::s/ppeeeeiiiiit
net//oormm? forum? i d= fQ FQwwH.
Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neigh- bor in high dimensions. Communications of the ACM, 51(1):117-122, 2008
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), 45(6):891-923) 1998.
G. Ausiello, A. D' Atri, and M. Protasi. Structure preserving reductions among convex opti- mization problems. Journal of Computer and System Sciences, 2161):336-133, 1980. ISSN 0022-0000. doi: htt.://tw.......coooooaa/aa///// sciencedirect. http////wrrreeecccc//c/////////e
URL https://wwk
Dmitry Baranchuk, Artem Babenko, and Yury Malkov. Revisiting the inverted indices for billion- scale approximate nearest neighbors. In Computer Vision - ECCV 2018: 15th European Confer- ence, Munich, Germany, September 8-14, 2018, Proceedings, Part XII, pp. 209-224, Berlin, Hei- delberg, 2018. Beainger-Verlaeee ISBN 978- 3000--115-0--- doi: 10. 00077/778-3-30-012250 1.11. URL https:://// / /oii org 10. 1007 97 030 01258- 81.
Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Pro- ceedings of the 23rd International Conference on Machine Learning, ICML '06, pp. 97-104, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933832. doi: 10.1145/1 143844. 143857. URL https: /oo.. 1ttg//..111//1111 1143877
A. Camerra, E. Keogh, T. Palpanas, and J. Shieh. isax 2.0: Indexing and mining one billion time series. In 2013 IEEE 13th International Conference on Datu Mining, pp. 58-67, Los Alamitos, CA, USA, dec 2010. IEEE Computer Society, doi: 10.1109/CCD..2100.121 //doi. www.::ieeeecmeeeeeeeccec
URL https:
wwweett..rrgg.ooeeeeeeeee org/ 3zg/10.. 120/99..119////// /IWMM 2010.124.
Jaime Carbonell and Jade Goldstein. The use of mmr, prversity-basedd reranking for reordering documents and producing summaries. In Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, pp. 335-336, 1998.
Kunal Dahiya, Deepak Saini, Anshul Mittal, Ankush Shaw, Kushal Dave, Akshay Soni, Himanshu Jain, Sumeet Agarwal, and Manik Varma. Deepxml: A deep extreme multi-label learning frame- work applied to short text documents. Proceedings of the 14th International Conference on Web Search and Data Mining, WSDM '21, New York, NY, USA, 2021. Association for Computing Machinery.
Evelyn Fix and J. Hodges. Discriminatory analysis. nonparametric discrimination: Consistency properties. International Statistical Review / Revue Internationale de Statistique, 57(3)2238-277, 1989. ISSN 03067734, 17515823, URL http:////// // /www. jstor. org/
Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graphs. PVLDB, 12(5):461 474, 2019. doi: 10.14778/
3303753.3303754, URL http:///t// www. www.:vllb..ogggg....o.oo
vo 12/p4 61 ft..f..ppp...
Michael Garey and David S. Johnson. Computers and Intractability; Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1990. ISBN 0716710455
Marie Al Ghossein, Ching-Wer Wei Chen, and Jason Tang. Shopping queries image dataset (sqid); An image-enriched esci dataset for exploring multimodal learning product search. arXiv preprint 1rXi: 2024.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604-613, 1998.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion- similarity search with gpus. arXiv preprint arXiv: 00..177022.77.. 2017.
11

---

Published as a conference paper at ICLR 2026
Richard M. Karp. Reducibility among Combinatorial Problems, pp. 85- Springer US, Boston, MA, 1972 ISBN 978-1-4684-20011 doi: 10. 10.1007/97881-4644200011 URL https:// doi.org 10. 10--100777-----44-2-0--------
Search Liaison. Google announces site diversity change search results, 2019, URL https:
//www. searchengine journal.
311557/.
Yury A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR, has/16033093200 2016. URL http:
/ //arxiv. wwg. abs /133666....0 09320.
Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, USA, 2008, ISBN 0521865719.
Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vard- han Simhadri, and Yihan Sun. Parlayann: Scalable and deterministic parallel graph-based ap- proximate nearest neighbor search algorithms. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, pp. 270-285, 2024.
Hervé Moulin. Fair division and collective welfare. MIT press, 2004.
G. L. Nemhauser, L. A. Wolsey, and M. L.. Fisher. An analysis of approximations for maximizing submodular set functions-i. Math. Program., 14(1)2665-294, December 1978. ISSN 0025-5610. doi: 10.1007/BF01588977 URL attps: /tttpp:://oi..e /tt.:/ii..ogoooooooooooooooooo.r orrg////////ooooo..oooooooo 101. 100.100008/7077777..
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and llya Sutskever. Learning transferable visual models from natural language supervision. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 8748-8763. PMLR, 18 24 Jul 2021. URL pttps::/pprceee ngs. mlr wwllrprrssss. v199 radford21a. html.
Chandan K Reddy, Lluís Mårquez, Fran Valero, Nikhil Rao, Hugo Zaragoza, Sambaran Bandyopad- hyay, Arnab Biswas, Anlu Xing, and Karthik Subbian. Shopping queries dataset: A large-scale esci benchmark for improving product search. arXiv preprint 2rXiv:2206.06588, 2022.
Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingher, Matthijs Douze, George Williams, Mag- dalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, et al. Results of the big ann: Neurips 23 competition. arXiv preprint arXiv:2409 17424, 2024.
Suhas Jayaram Subramanya, Fnu Devvrit, Rohan Kadekodi, Ravishankar Krishnawamy, and Har- sha Vardhan Simhadri. Diskann: Fast accurate billion-point nearest neighbor search on a sin- gle node. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 1 13758, 2019.
Kohei Sugawara, Hayato Kobayashi, and Masajiro Iwasaki. On approximately searching for similar word embeddings. In Annual Meeting of the Association for Computational Linguistics, pp. 2265- 2275, 01 2016. doi: 111116//1//111111/1 1214.
Philip Sun, David Simcha, Dave Dopson, Ruiqi Guo, and Sanjiv Kumar. Soar: Improved indexing for approximate nearest neighbor search. In Neural Information Processing Systems, 2023. URL https://arrse org/ abs 2200444000000 00774.
TensorFlow. Tensorflow datasets.
catalog/A 2025. Accessed: 2025-07-10.
J. Wang, J. Wang, G. Zeng, Z. Tu, R. Gan, and S. Li. Scalable k-nn graph construction for visual descriptors. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1106- 1113, June 2012. doi: 10. 109/CV/P..201226247999
12

---

Published as a conference paper at ICLR 2026
August Wester. arxiv openai embeddings. https: //ww: httDs://www.kgggle..oomo/ wtt.aaaae...c//datttttttttata. arester//axxiv--mbeddd...
2022. Accessed: 2025-07-10.
Shangyu Wu, Ying Xiong, Yufei Cui, Haolun Wu, Can Chen, Ye Yuan, Lianming Huang, Xue Liu, Tei-Wei Kuo, Nan Guan, et al. Retrieval-augmented generation for natural language processing: A survey, arXiv preprint arXiv:2407. 13193, 2024.
13

---

APPENDIX: WELFARIST FORMULATIONS FOR
DIVERSE SIMILARITY SEARCH
Table of Contents
1
Introduction
2 Problem Formulation and Main Results
2.1
Our Results
3
Algorithm for NaNNS
Experimental Evaluations
4.1
Results: Balancing Relevance and Diversity
5
Conclusion
10
Acknowledgements
10
Supporting Lemmas for the Proof of Theorem 1 A.I Proof of Corollary 2
14
16
Stylized Examples for NaNNS
16
C Proof of Theorem 3
17
Proof of Theorem 4
19
E Extensions for p-NNS
20
F Experimental Evaluation and Analysis
25
F.1
Evaluation Metrics
25
F22
Datasets
26
F33
Balancing Relevance and Diversity: Single-attribute Setting
................................
28
F.3.1
Approximation Ratio Versus Entropy
29
F33.2
Performance on p--men- ANN
30
E.3.3
Approximation Ratio Versus Inverse Simpson Index
31
F.3.4
Approximation Ratio Versus Distinct Attribute Count
31
F.3.5
Recall Versus Entropy
F.4
Balancing Relevance and Diversity: Multi-atrribut Setting
34
F55
A Faster Heuristic for the Single Attribute Setting: -et Fetchhnion ANN
38
F66
Comparison with Diversity based on Minimum Pairwise Distance
40
A SUPPORTING LEMMAS FOR THE PROOF OF THEOREM
As in Algorithm 1, write D, to denote the k nearest neighbors of the given query q in the set D Recall that in the single-attribute setting the sets D,s disjoint across l E [c]. Also, of E Dr denotes the 7th most similar vector in De, for each index
[K]. We define function F((-) to
14

---

Published as a conference paper at ICLR 2026
denote the logarithm of the cumulative similarity of prefixes of these vectors; in particular,
Fe(d) = log Σ als (6) + for each sisk.
(4)
Note that (1) is equal to the logarithm of the cumulative similarity of the i most similar (to ②) vectors in Dj. The lemma below shows that Pe(-) satisfies useful decreasing marginals property. Lemma (Decreasing Marginals). For all attributes E [c] and indices i', E [k], with i' holds that
F((1) - F,(i - 1) (x(() Feli 1).
Proof. Note that
(g. (1) +1
(((1) Fe(i 1) log
og (1) +
Og, + 17 + o
( o
log
Ej 0 2n +
loo
1+
Σ 1j=1 olg (n)) +11
Similarly, we have F2(1" - (e log
1 Σラ o44.0
In addition, the indexing of the vectors un ensures that (4, (())) 2 ogg ) for 1' < i. More-
over, since the similarities o(g, v) are non- negative for all v E P. we have Σj=1 o(g v b) 2
E/ o(g, (
Combining these bounds, we obtain
(gg (()
2 Σj= al (1)
Ej +1
Adding to both sides of the last equation and taking log (which an increasing function and, hence, preserves the inequality) gives the desired inequality. Hence, the lemma stands proved.
The following lemma asserts the Nash optimality of the subset returned by Algorithm 1, ALG, within a relevant class of solutions.
Lemma 6. In the single-attribute setting, let ALG be the subset of vectors returned by Algorithm and S be any subset of input vectors with the property that |S Del = ALG n Del. each & [c]. Then, NSW(ALG) 2 (SW(S).
Proof. Assume, towards a contradiction, that there exists a subset of input vectors that satisfies IS n Del |ALG n Del. for each e E [c]. and still induces NSW strictly greater than that of ALG. This strict inequality implies that there exists an attribute a E [e] with the property that the utility (.()) ua (ALG)). That is,
Σ alg.t)
Σ
o4q v)
(5)
IESDD
DEALGOD.
On the other hand, note that the construction of Algorithm and the definition of D. ensure that the vectors in ALG n Da in fact the most similar to q among all the vectors in D.. This observation and the fact that |S n Dal = |ALG n Dal gives us EWEALOnD. (g, v) 2 Etesnn, a(g,t) t). This equation, however, contradicts the strict inequality (5).
Therefore, by way of contradiction, we obtain that there does not exist a subset S such that |5nDz] |ALG Del, for each E [c), and NSW(AL.)) < NSW(S). The lemma stands proved.
Recall the utility model specified in Section 2.1.
15

---

Published as a conference paper at ICLR 2026
A.1 PROOF OF COROLLARY
Here we state the proof of Corollary 2.
Corollary 2. In the single-attribute setting, given any query q Id and an a-approximate oracle ANN for k most similar vectors from any set, Algorithm I (Nash-ANN) returns an a- approximate solution for NaNNS, i.e., returns a size-k subset ALG S P with NSW(ALG) 2 maxxgCP: |8|=k (S) The algorithm runs in time O(kc) + Ei= ANN( Q), with De, q) denoting the time required by the oracle to find k similar vectors to in De.
Proof. The running time of the algorithm is established by an argument similar to that in proof of Theorem 1. Therefore, we only argue correctness.
For every [c], let the a-approximate oracle return D.. Recall that ((p- E [k], denotes the 7t most similar point to q in the set De. Further, for every & [c], let D2 be the set of l most similar points to q within D2 and define u8h, [k:] be the 2thh most similar point to q in Dj. Recall that by the guarantee of the a-approximate NNS oracle, we have (g, of))) 2 a -a oz (()) for all
i [R)] Let OPT be an optimal solution to the NaNNS problem containing k most similar points of attribute l for every 8 E [c]-
Finally, let OPT be the optimal solution to the NaNNS problem when the set of vectors to search over is P Ure(o De.
By an argument similar to the proof of Theorem 1, we have NSW(ALG) = (OPT. Therefore
NSW(ALG) = (OP))
la ( (0) +n +1))
II KE|d
Σ
( (eelc /0 ... (((7)) is feasible solution)
ky (g m1)) + n m))
II VEle
())
(by a-approximate guarantee of the oracle; kj s k)
Σ o(g. 0(6) +1) 1)
II α [E|c] (OPT)
(a E (0, 1))
(definition of OPT)
Hence, the corollary stands proved.
B STYLIZED EXAMPLES FOR NANNS
As stated in the introduction, depending on the query and the problem instance, solutions obtained via NaNNS can adjust between the ones obtained through standard NNS and those obtained via hard constraints. This is illustrated in the following stylized examples.
The first example shows that if all vectors have same similarity, then an optimal solution, S*, for NaNNS completely diverse, i.e., the vectors in S have different attributes.
The second example shows that if the vectors of only one attribute have high similarity with the given query, then a Nash optimal solution S* contains only vectors with that attribute.
Example (Complete Diversity via NaNNS). Consider instance in which, for a given query q Rdd all vectors in P are equally similar with the query: a(g, v) = for all v E P. Also, let Jatb())] 1 for all E P and write S* arg max [ NSW(S). If c > k, then here it holds that S O Del < 1 for all & [c].
16

---

Published as a conference paper at ICLR 2026
Proof. Towards contradiction, suppose there exists T E arg maxggP (SW such that [T n Dr. for some t" [c]. Note that according to the setting specified in the example, ((()) =
+ n for all & E (c)-
Since 2 k and D 1, there exists E' E [c] such that [Tn Tel 0. Let o' E TT De- and o' E Dr be two vectors. Consider the set T = (T) {o*}) u {u'}. We have,
NSW(T) (SW
(ue (T*) + 77) (ux (T') + +1)
(ue- (T) + 77) (up (T) + 17)
(ue(T") + n)
II
=
sEleMee .0 (ux(T') + 7)
(1 + m)
(up (T) - -1+ n)
(T) + 17)
II
(ue- (7) + (EIdMEr (ua(T) 77)
11
(1 + 7)
(ug- (T) - + 17)
17
(ue- (T") + 17)
uu- (T) - 1 1 mug- (T) 11²
>
(ue. (T) 2 2)
que (T) + 17²
Therefore, we have XTW(TT) NSW(T), which contradicts the optimality of T. Hence, must have 17 n Del < 1 for all l E [c]. which proves the claim.
Example (Complete Relevance via NaNNS). Consider an instance in which for a given query q E IRdd and for particular E [c]. only vectors e E De- have similarity (g, 2) and all other \ D;- have similarity (q.. p') )')= = O. Also, suppose that [atb(p) = for each E P. along with DD= 2 k. Then, for a Nash optimal solution S arg (.jSss NSW it holds that SS n De- = k. That is, for all other E [c] } we have 1S D 0.
vectors p' E P
Proof. Towards contradiction, suppose there exists T E arg max NSW(S) such that IT Dg. < Therefore, there exists l [c] \ {E*) such that [7 De Let DE- T and let v' E T n De. Note that ug (T) = 0 since alg. v) 0 for all v E Dr for any l E [c) \ } Moreover, we also have ug- (T) [T' n De-l-
Consider the set T" = "T (2))) {o*} J. We have,
NSW(T")
(T') + 17)
(T') + n) (T) 1)
(ux(T') + 11)
II
NSW(T)
(up (T) + +1)
(T) +
rE(d)(es))
(T) =o(g.0) v') +1)
(ue (T) + o(g, 8n +
(u:(T) + 17 tete]tee (ue(T) + 7))
(ur +11)
(ur- (T) + 1))
0 0 0+1)
De- / +1
0 0+n
(IT De- De-1+
1
>.
I De. +
Therefore, we have obtained NSW(T") > NSW(T), which contradicts the optimality T, Hence, it must be the case that [T' n Dz- = k. which proves the claim.
C PROOF OF THEOREM 3
This section restates and proves Theorem 3. Recall that in the e P are associated one or more attributes, (atb(u)) 2 1.
setting, input vectors
Theorem 3. In the multi-atribute setting, with parameter 7) NaNNS is NP-hard.
17

---

Published as a conference paper at ICLR 2026
Proof. Consider the decision version of the optimization problem: given real W. decide whether there exists S Ç P. |S| = such that log NSW(S) 2 W. We will refer to this problem as NaNNS. Note that the input to NaNNS instance is the following:
set of vectors P R PI n, similarity function a : Rd x TRd - I,, integer & E N. the sets Dr = {p E P E atb(p)) for every color E [c], query point o TR and real W. We will show that NaNNS is NP-Complete by reducing EXACT REGULAR SET PACKING (ERSP) to NaNNS.
In ERSP, are given universe of elements that we denote by 4 (1, .,..,,, n), a collection of subsets S = (S),..., } where S; C u, S.| - т, for all E [im] and an integer & E N. The problem is decide if there is a sub-collection C S. [1] k, such that for all distinct S, S S = 0.
To reduce ERSP to an instance of NaNNS, we view 24 as the set of attributes, i.e. c= n. The set of vectors P is embedded in R and is given by P { 1s S E S) and the query vector is 1. Here, is the all ones vector in IR", and 1g is the vector in R whose i-th coordinate 1 S} for all i E [n]]. Therefore, the set of vectors P is of size m. Moreover, the set of vectors having attribute l E [r]] denoted by D; = ( 1s I S E S, E S). The size of the solution set of the NaNNS is equal to the k of the ERSP instance. Finally, the similarity function IR" x IR" + I is taken to be the usual dot- dot-product. Finally, we set W = Th log 2. Note that the reduction takes time polynomial in n and m.
Also note that for any u E P. v) = ( 1s. 1) where u = + 1g for some S E S.
Now we prove the correctness of the reduction.
is a solution to ERSP instance. Consider the set N = { 1g S ]".. Clearly, N* C P and | k. hence N is feasible set of the NaNNS problem. Now, since 1 is a solution to the ERSP instance, for distinct S, S' E I" we have S'S'' = Particularly, if for attribute & E [c],
">>:: Suppose |* C S, | =
have l E S for some S E |", then & & S' for all S E / \ (S). ) Therefore, |N n Del S for all & E [c] which in turn implies that ue ue(N") is either or 0 for all
é E [c]. Finally, note that any point u P belongs to exactly T attributes, i.e., latb(v) т. Hence,
log NSW(N') 1 Σ log(1 + ue(N"))
1
log(1 1) MENN tEatb(F)
Σ
Σ
Th log
Therefore, if there is solution to the ERSP instance, then the corresponding NaNNS instance also has a solution.
"<" Suppose No C P. |N k, is solution to the NaNNS instance (i.e., log NSW(N*) 2 W) corresponding to the ERSP instance. Define T = {S 1 is E N*). Note that |7"| k. We will show that I* solution to the ERSP instance. First observe that,
Σ Cue(N=)= KE(O]
Σ Σ EE(C] DEN-ND2
oqq.v) = Σ Σ
a(g. v) = Tk.
VEN. (Eatb(u)
We also have the set of attributes with non-zero utility is given by A U. Clearly, s |A| < kh via Union Bound. Hence,
W = 7k log 2
log NSW(N*)=
Σ
log(1 + (x("))
EE(C]
log(1 + (N())))
C EEA
|
log(1 + ue(N)))
c
[
EEA
A
log
1 + ue((")))
(concavity of log)
A
ZEA
JORSSP is known to be NP-Complete due to Karp (1972) and W[1] hard with respect to solution size due Ausiello et al. (1980); also Garey & Johnson (1990)
18

---

Published as a conference paper at ICLR 2026
|AI
ErEA ErEAue(N
logg
1+
[A
|A|
log
+
|Al
rk log
c
Here, the last inequality follows from Lemma (stated and proved below). Hence, all the inequali- ties in the derivation above must hold with equality. Particularly, we must have |.A| = rk by equality condition of Lemma Hence, for distinct sets S, S' I*, we must have S 5n. S 0. Therefore, I* is a solution of the ERSP instance.
Lemma 7. For any a > and for all x E (0, x oloo(1 + 2) S a calog? 2. Moreover, the equality holds when a.
Proof. Let f(x) = x log(1 + 2). We have f(a) = a log(() and,
lim f(x)) lim, x-
log(a + x)) x log x
lim x log(a x) lim æ log(z) x-0
0.
--0
--0
We will show that f((x) > for all x E (0, a] which will Note that fa) = log(1 + 9) at. conclude the proof.
Case 1: x E (0, 21 We have log(1 1 + 2) 2 log(1+ a/2) = log(3) 1. On the other hand, a+2 I 1. Case 2: E ($.a). a]. In this case, log(1 =)= 2 log(1 + )) log(2) 0.693. However, a+= a+y = 1/2 S 0.667.
Therefore, (x) log(1 + 9) aiz for all (0, a] which concludes the proof.
D PROOF OF THEOREM
This section details Algorithm 2, based on which we obtain Theorem We establish this theorem by showing that the log NSW()) objective is submodular. Hence, we obtain the stated (1 - 2) approximation by applying the approximation algorithm for cardinality-constraime submodular maximization (Nemhauser al., 1978).
Algorithm Mult NashANN: Algorithm for approximate solution in the multi-attribute case
Require: Query q Rd 1: Initialize ALG = Ø.
do 3: 6= arg max log NSW(ALGU (c))
2: for i peri=,..... 1,...,A
4: ALG + ALG U (ū).
5: Return ALG.
Theorem 4. In the multi-attribute setting, there exists a polynomial-time algorithm (Algorithm 2) that, given any query E IR4, finds size-k subset ALG S P. with log NSW (ALG) >
(1 2) log (OFT):)): here, OPT denotes an optimal solution of (1).
Proof. We will show that function f 2p + R., f(S) = log NSW(S), S C P. is monotone
submodular. Observe that for S T C DS D hence (e()) < (T") for all e e [c] Moreover, since log is an increasing function, log (S) + 1) < log( (T) + 1) for all l E [c]
Therefore, conclude that f(S) J(T), hence f is monotone.
19

---

Published as a conference paper at ICLR 2026
For submodularity, let S _ T P be two subsets and let w E P T. We will denote by S + and + w the sets S (w) and TU {w). Now, we have
f(S + - -
f(() f(T + [ f(T)
1 Σ log
1 EvE (q
1+ 1+ EVEDiNT
1+ LvEDENSS)
1+ +VE (q.
LE/c]
(1+ I+ I EvEDins _
(g,w)
(
04g w)
Σ log
1+ I+ Σ EvEDIn o(q
(Eatb(w)
(1+ o(g,w) (1 (1+1+)(())
a(g,w)
log
1 ux(T)
(Eatb(w)
(ue(S) S ue(T) since S S T) Therefore, upon rearranging, we have f(S + w) f(S) 2 f(T + +)) f(T) which is a character- ization submodularity.
20
Hence, Algorithm 2, which, in every iteration, greedily picks the element with maximum marginal contribution, achieves a (1 apapprooximtooon (Nemhauser et al., 1978).
E EXTENSIONS FOR P-NNS
In this section, we discuss the extension of results for NaNNS to the p-NNS problem. We state an algorithm (Algorithm 3) and present its guarantee (Theorem 11 and Corollary 12) in finding the exact optimal solution for the p-NNS problem. Recall that p-mean welfare of agents with utilities (wi...., w.) is given by Mp(W1..... we) (t Ei= w?) for (-o0, 1]. The p-NNS problem stated as follows:
max SCP\S/==
Mp (5) (s))
Here, as in Section 2.1, the utility uz(S) Evesnd, a(q, v), for any subset of vectors S and attribute 8 E [c]. Also, we will write M2(S) = Mp (N.
Algorithm p-Mean-ANNY Algorithm for p-NNS in the single-attribute setting
Require: Query 9 Rd and, for each attribute f [c], the set of input vectors De C Rd and p E (-20, 1] \ {0}.
1: For each E [c]. fetch the l (exact approximate) nearest neighbors of q E Rdd from Dr. Write
D. S D, to denote these sets.
2: For every / [c] and each index i [k], let ufg denote the ith most similar vector q in De.
3: Initialize subset ALG = 0, along with count k = 0 and utility 0, for each / E [c].
4: while |LLG| k: do
5: if (0, 1] then
6: Let a = arg max (wwe+ + olg, of of - (we + +n))) (Ties broken arbitrarily.]
tE(c]
7: else if p 0 then
8: Let a = arg min (we + t 17 o of o(kr41)))² (we + n)p) (Ties broken arbitrarily.]
EE|c)
9: Update ALG + ALGU { b (otktt)) along with wa wa + o v)k,+1)) and hig ki + 1.
10:
Return ALG.
For given query q, let fe(i) Ej= ogg u(()) for any attribute E [d] and index i [b]]. Lemma 8 (Decreasing Marginal for > 0). Fix a E (0, 1] and attribuee [c]. Let Fy(1) = (fe(i) + p). Then, for < <i< sis k, have
F((1') Fe(d' - 1) Fe(i) Fe(i 1)
20

---

Published as a conference paper at ICLR 2026
Proof. Let G(j) Fe()) Fe(j - 1) for all j E [k]. We will show that G(j) is decreasing in j. Towards this, we have the following inequalities for j 2 2:
G(j ((j-1) (-i-1)-((5 G())
=Fi(j 1) Fi(j 2) +
=2F((j - 1) - (FF(j) - Fe(j- 2])
=2(feli 1) 7)) ((fe(t) + +n))= + +(f((j 2) + +))
o(g. olg. (-1))
olg 0g (-1) + o(q. ((2)))
1
- 2(feli - 2) - 7)
1+
1+
1+
Me(i - 2) +
2
Seli - 2) + 11
o(g, olg, ((--1))
20 of )(11))
2 2(Seli - 2) - -1)
1+
1
1+
1
2) +1
2
feli 2) +
(o (o()) 2 (g. (6)):
+ xº increasing for E (0, 1] and x 2 0)
2 2(feli - 2) -n) ((1+
o(g. 0(9. v(y-)))
2/2 (1
20 -
1 1+
felj - 2) +1
felj 2) + 7)
(x xe is concave for p (0, 1] and 0)
-0.
Therefore, we have G() < GÚ 1) for all 2 j S Particularly, for 1 S 1' G(7") 2 G(i), which is the claimed inequality.
we have
Lemma 9 (Increasing Marginals for p < 0). Fix p (-00, 0) and attribute & E [c]. Let Fe(1) (fe(1) + n)" Then, for 1 S <is k we have
Fi(t') - Feli' - 1) S (i(1) Fr(i 1)
Proof. The proof proceeds similarly to the proof of Lemma 8, except that we now seek the reverse inequality. More precisely, with G(j) same as defined in proof of Lemma 8, we wish to show that G(j) 2 G(j 1) for all 2 S j S k. Towards this, we have,
G(j-1) [ G(i)
1+ o(g, o(g, )
olg, of + o(q. o(2)))
1
2(fe(i -2 + -))
1+
1+
felj - 2) + +1/
2
feli - 2) +
|+
o(9. o(g. 11g-1))
1
20(g 26 x
s 2(fe( - 2) - 7)7
1+
Te(j - 2) +11
2
Jelj - 2) +
(o(9, )))) 2 o(9. u ))));
+
x decreasing for E (-00, 0) and x 2 2)
< 21((el 2) 2) 7)) ((1+
o(g. x(z-)))
1+ 1 (1
20 " - 1)) felj 2) + 1)
fe - 2) +
(x x is convex for E (-00, 0) and 0)
00.
Lemma 10. the single-attribute setting. let ALG be the subset of vectors returned by Algorithm and S be any subset of inpul vectors with the property that |S Dj! = ALLG Del, for each & E [c]. Then, (ALG)) 2 MS(
Proof. Assume, towards a contradiction, that there exists a subset of input vectors S that satisfies |S Del = |ALG n Drl, for each & E [c], and still induces p-mean welfare strictly greater than that of ALG. This strict inequality combined with the fact that M,(w,, (w),..,, w.) is an increasing function of w,s implies that there exists an attribute
[c] with the property that the utility ua( >
21

---

Published as a conference paper at ICLR 2026
Ua (ALG)) That is,
Σ (a.1)> >
Σ
(6)
IESnD,
dEALEND.
On the other hand, note that the construction of Algorithm 3 and the definition of D. ensure that the vectors in ALG Da are in fact the most similar to q among all the vectors in Da. This observation and the fact that |S n Dal |ALG O Dal gives us EEEALOD, ((, 2 EiesnD, olg, (). This equation, however, contradicts the striet inequality (6).
Therefore, by way of contradiction, we obtain that there does not exist subset S such that |SnDa] [ALG Del, for each E [c), and M,(ALG) < (2))). The lemma stands proved.
Theorem 11. In the single-atrribute setting, given any query q E Rd and an (exact) oracle ENN for k most similar vectors from any set, Algorithm 3 (p po-mean-Aie p-NNS, i.e,, returns a size-k subset ALG C P that satisfies ALG E arg max Mp(S). Furthermore, the algorithm runs in time O(ke) + Ei=i ENN( De, q), where ENN q) is the time required by the exact oracle find k most similar vectors to q Dr-
returns optimal solution for
Proof. The running time of the algorithm is established by the same arguments as in the running time analysis of Theorem
For the correctness analysis, we divide the proof into two cases: < 0 and p E (0, 1].
Case p E (o, 1]. Note that + xx is an increasing function for x 2 0. Hence, the prob- lem |, Mp(S) is equivalent to the problem ma M5(S)² or in other words, 1 Σi= (e(S)) The proof hereafter proceeds essentially similar the proof of The- maxggP,15) e
orem 1. Let kg ALG Del for all E [c]. Further, let OPT E arg maxscr.)s)=k 1 Ei=1 (e())) and kn = |OPT n D&| for all i E [c]. where OPT is chosen such that Ei=lkk kel is minimized.
c
We will prove that OPT satisfies ky ke for each & [c]. This guarantee along with Lemma 6 imply that, as desired, ALG is a p- p-mean welfare optimal solution.
Assume, towards contradiction, that kn * ky for some l E [c]. Since |OPT| exists attributes x, E [c] with the property that
|ALG| = k, there
Kッ> Ki With (i( as defined in Lemma 8, we have for any pair of indices 1 < S
K hz and
Fe(t') (1) Fe(i) Fr(( 1)
(8)
Next, note that for any attribute E [c]. if Algorithm 3, at any point during its execution, has included k vectors of attribute 8 in ALG. then at that point the maintained utility we fe())). Hence, at the beginning of any iteration of the algorithm, if the Kg denotes the number of selected vectors of each attribute l E [c]. then the marginals considered observations and the selection criterion in Line 6 of the algorithm give us the following inequality
Line are Fg (K₃ + 1) F2 (Kt). These
for the counts hg = |ALG n Dul and hi = ALG n D,, of the returned solution ALG:
F2 (k. 1) (k + 1) Fky))y)
(9)
Specifically, equation (9) follows by considering the iteration in which bith (last) vector of attribute was selected by the algorithm. Before that iteration the algorithm had selected (k, - 1) vectors of attribute x, and let Ki denote the number vectors with attribute y that have been selected till that point. Note that ky < kg. The fact that the Atth vector was (greedily) selected in Line 6, instead of including an additional vector of attribute y. gives F, (kz) Fa (k. 1) 2 (K, + 1) Fy (k > (ky + - (k.,), here, the last inequality follows from equation (8). Hence, equation (9) holds.
Moreover,
E. F2 +1) (xt)
> (ka) - (ki 1) 2 (ky + (ky) 2 Fy (kg) - Fy (Ki 1)
(via eqns. (7) and (8))
(via eqn. (9)
(10)
Recall the utility model specified in Section 2.1.
22

---

Published as a conference paper at ICLR 2026
The last inequality follows from equations (7) and (8).
Recall that ofe; denotes the ith most similar (to q) vector in the set De. The definition of De ensures that ufs) is in fact the Tt most similar (to q) vector among the ones that have attribute E, i..., 2thh most similar in all of De. Since OPT is an optimal solution, the k2 = |OPT n Dj vectors of attribute & in OPT the most similar kj vectors from De. That is, OPT n De {
(()......(.)) J. for each L E [c]. This observation and the definition of Fe(.) imply that the p-th power of OPT's p-mean welfare satisfies
M₂(OPT)P = : Σ F((
1
(11)
t=1
Now, consider a subset of vectors S obtained from OPT by including vector (1z+1) and removing
2il (kg) ie., 5 (OPT (utk:tu)) }) 1
(1 } Note that
Mp(S)* M₂(OPT)P 1 (k +1) FFa(kt)) (Fo - 11) -Fy(k;))
(via eqn. (10))
Hence, MS) 2 M2 Given that OPT is a p-mean welfare optimal allocation, the last inequality must hold with equality, (5) M, (OPT), i.e., S is optimal solution well. This, however, contradicts the choice of OPT as an optimal solution that minimizes Σi=1 [kg kel
note that Σi=1 ke ke
Ei= 1k@ - kel. where ke = |sn Del.
Therefore, by way of contradiction, we obtain that |OPT n Del = ALG n Del for each & E [c]. As mentioned previously, this guarantee along with Lemma 10 imply that ALG is p-mean welfare optimal solution. This completes the proof of the theorem for the case E (0, 1].
Case 2: p < O. In this case, the proof follows similar argument as the previous case. However, due to p being negative, the key inequalities are reversed. We present the proof formally below for the sake of completeness.
Note that x + x is a decreasing function for x 2 0. Hence, the problem maxsc M2(S) is equivalent to the problem minsgr.1s] Mp(S)² or in other words, min Ei=1 (e()). Let ke- |ALG n Del for all 8 E [c]. Further, let OPT E arg mignss..sss=.. a Σ (S) and kj = |OPT Del for all é E [c], where OPT is chosen such that Ei=lkk ke] minimized.
We will prove that OPT satisfies ky = kg for each E [c]- This guarantee along with Lemma 10 imply that, desired, ALG is p-mean welfare optimal solution.
Assume, towards a contradiction, that kg + kg for some E E [c]. Since |OPT] |ALG| = k, there exists attributes I, y E [c] with the property that
k < hz
and
Ky hy
(12)
With (i) as defined in Lemma 9, we have for any pair of indices 5 <isk
Fe(t') Fell' 1) Fi) Fe 1)
(13)
Next, note that for any attribute E [c]. if Algorithm 3, at any point during its execution, has included kG vectors of attribute l in ALG, then at that point the maintained utility w; (k)). Hence, at the beginning of any iteration of the algorithm, if the ky denotes the number of selected vectors of each attribute l E [c], then the marginals considered observations and the selection criterion in Line 8 of the algorithm give us the following inequality for the counts k. |LLG Dal and bi = ALG n D2y of the returned solution ALG:
Line are Fe (Kg + 1) F, (Kt). These
F. (kx)) F. (k. 1) (ky + 1) Fy (ky)
(14)
Specifically, equation (14) follows by considering the iteration in which 1ith (last) vector of attribute I was selected by the algorithm. Before that iteration the algorithm had selected (k,, - 1) vectors of attribute 5, and let K, denote the number of vectors with attribute y that have been selected till that
23

---

Published as a conference paper at ICLR 2026
point. Note that Ky I ky. The fact that the ki vector was (greedily) selected in Line instead of including an additional vector of attribute y, gives (k2)) Fa 1) S. Fy + - F Fy(Ky) -
Fg (k, + +) F (ky); here, the last inequality follows from equation (13). Hence, equation (14) holds.
Moreover,
(a +1 (x.) S (k(ss)) (k 1)
(via eqns. (12) and (13))
S (ky + +) Fg kig)
(via eqn. (14))
S Fg(kKg) Fy, (K.
(15)
The last inequality follows from equations (12) and (13).
Recall that ofs denotes the hth most similar (to q) vector in the set De. The definition of De ensures that ofs) is in fact the hh most similar (to q) vector among the ones that have attribute E, i..., 7t most similar in all of Dr. Since OPT is an optimal solution, the kg = -OPT n Del vectors of attribute &
in OPT are the most similar k vectors from De. That is, OPT n Dg = ii...... ((2) f. for each E lc]. This observation and the definition of Fe(.) imply that the p-th power of OPT's p-mean welfare satisfies
1 - Fe(k)).
Mp(OPT) =
(16)
Now, consider a subset of vectors S obtained from OPT by including vector o( and removing
2 (kkg) i..., S (OPT 20 (((++t)))
1 } Note that
- (00(5))-MM(00)) = 1 (k +1) - Fo(k))) -u)k)(())))) +
1 - (F)
FFy(k)) (viaeen.
0
(via eqn. (15))
Hence, M,(S) > (OPT). Given that OPT is p-mean welfare optimal allocation, the last inequality must hold with an equality, MS) = (OPT))). i.e. S is an optimal solution as well. This, however, contradicts the choice of OPT an optimal solution that minimizes Ei=1 [kg kel
note that Σi=1 Tee ke Ei=i kgg
ke/. where k ISS Del-
Therefore, by way of contradiction, we obtain that |OPT n Del = |LG n Del for each & E [c]. As mentioned previously, this guarantee along with Lemma 10 imply that ALG is a p-mean welfare optimal solution. This completes the proof of the theorem for the case p < 0.
Combining the two cases we have the proof of the theorem for all p E (-oc, 1] \ (0).
Corollary 12. In the single-atrriutte setting, given any query q E Rdd and an a-approximate or- acle ANN for k most similar vectors from any set, Algoritim 3 (p-mean-ANN) returns an a- approximate solution for p-NNS, i... it returns size-k subset ALG C. P with M,(ALG) N
maxxcp: |S|= |S|=k Mp(S). The algorithm runs in time Okke) + Σ ANN((De De, g). with ANN( being the time required by the approximate oracle to find k similar vectors to q in Dr-
Proof. The running time of the algorithm is established by an argument similar to that in proof of Theorem 11. Therefore, only argue correctness.
For every [c], let the a-approximate oracle return D.. Recall that o/j i [k], denotes the 2t most similar point to g in the set Dr. Further, for every & [c], let DŁ be the set of ls most similar points g within D; and define u() i [K]], to be the 1th most similar point to q in Dj- Recall that by the guarantee of the a-approximate NNS oracle, we have o(g, v(()) 2 a-o(g, w(() for all E [k]. Let ALG" be the solution obtained by rumning p-mean-AND with an exact NNS oracle, and let ALG" contain kj most similar points of attribute for every i E [c]. Moreover, let OPT be the optimal solution to the p-NNS problem. Note that we have by Theorem 11, M,LA'"") M, (OPT)).
=f
24

---

Published as a conference paper at ICLR 2026
Finally, let OPT be the optimal solution to the p-NNS problem when the set of vectors to search over is P = Ueeje] Dr-
By an argument similar to the proof of Theorem 11, we have Mp(ALG) = (OPT) Therefore, we can write,
Mp(AI.)) (OPT))
P (() +
1 Σ
(1.
C
LE(C]
(o is feasible solution)
(g (6) +
RE(c)
(by a-approximate guarantee of the oracle, and M, is increasing in its argument)
Σ
Σ (g. (ti
17
a
a
RE(d]
b/2
M2 (q. (1)) +
2 a
(a E (0, and Mp is increasing)
RE|c]
a Mp(AL)
= a Mp (OPT)
(by Theorem 11)
Hence, the corollary stands proved.
F EXPERIMENTAL EVALUATION AND ANALYSIS
In this section, we present additional experimental results to further validate the performance of Nash-ANN in comparison with the existing methods. We begin with detailed discussion of the evaluation metrics (Appendix F.1), followed by a description of the datasets used in our study (Ap- pendix F.2). Next, we report results for the single-attribute setting (Appendix F.3), where we com- pare the approximation ratio alongside all diversity metrics for k = 10 and h: = 50. We also include recall values for both & 10 and k 50 (Appendix F.3.5). The key observation in all these plots is that the NSW objective effectively strikes balance between relevance and diversity without having to specify any ad hoc constraints like quotas. Furthermore, we report experimental results for the multi-attribute setting on both synthetic dataset (Si ft1m) and real-world dataset (ArXi v). Fi- nally, we experimentally validate the performance-efficienee trade-off's of a faster heuristic variant of po-men-- ANN that can be used in addition to any existing (standard) ANN algorithm.
F.1 EVALUATION METRICS
We evaluate the performance of our proposed methods against baseline algorithms using the follow- ing metrics:
Relevance Metrics:
1. Approximation Ratio: For a given query let an algorithm of choice return the set S₁ and let a (standard) ANN algorithm return the set $2. Then the approximation ratio of the algorithm is defined as the ratio Epes, ø(g.)) Therefore, a higher approximation ratio Σpes, a(g.))
indicates more relevant solution.
2. Recall: For a given query let S* be the set of exact nearest neighbors of and let S be the output of an algorithm. Then the recall of the algorithm is the quantity [s Therefore, higher recall indicates
[3*
relevant solution.
25

---

Published as a conference paper at ICLR 2026
It is important to note that recall is fragile metric when the objective is to retrieve a relevant- diverse set of vectors for a given query. This can be illustrated with the following stylized example in the single-attribute setting. Suppose for given query q. all the vectors in the set of exact nearest neighbors 5* have similarity 1, i.e., for all p E S o(g p) = 1. However, let all vectors E 5 be associated with the same attribute l" [c]. i.e., atb(p) of exact nearest neighbors is not at all diverse. However, it may be the case that there is a set S of k vectors, all having different attributes (i.e. atb(p) * atb(p') and atb(p) + l for p.p' S', * p'), such that (gg. p/) 0.99 for all p' E S". In other words, there is highly relevant set of vectors that is also completely diverse. Note that for the set S', the recall actually but the approximation ratio is 0.99. Hence, in the context of diverse neighbor search problem, instead of recall, approximation ratio may be more meaningful relevance metric.
e for all p S Therefore, the set
Diversity Metrics:
Entropy: Let P. (S k, be the output of an algorithm. Then the entropy of the set of S in the single-attribute setting is given by the quantity Eeeeoppe>o -p log(Pe) where
|snDel Note that higher entropy value indicates greater diversity.
Pe
[s|
For a given set S C P. P. k in the single-attribute setting, the inverse Simpson index index is defined as Σi Pz where pe is as defined in the definition of entropy above. A higher value indicates greater diversity.
Inverse Simpson Index:
Distinet Attribute Count: In the single-atrribute setting, the distinct attribute count of set C PS| = le is the number [[ e [c] | Da > 0J|-
In the multi-attribute setting, in this work, we focus on settings where the attribute set [c] is parti- tioned into m sets {C (i.e., [c] = Ci) and every input vector v E P is associated with one attribute from each C,, i.e., latb(v) = m and Jatb(u) n nC = 1. To measure diversity in the multi-attribute setting, we consider the aforementioned diversity metrics like entropy and inverse Simpson index restricted to C.. More precisely. the entropy set $ _ P restricted to particular [anprl Similarly, the inverse Simpson index of set G is given by Etec. -Pe log(pe) where p [9]
1 S C P restricted to C; is given by Exco p? where pe is defined before.
F.2 DATASETS
Amazon Products Dataset (Amazon): The dataset also known as the Shopping Queries Image Dataset (SQID) (Ghossein et al., 2024), is based on the Amazon Shopping Queries dataset (Reddy et al., 2022) that is publicly available on the KDD Cup 2022 Challenge ! The SQID includes image embeddings for about 190, 000 products listed in the Amazon Shopping Queries dataset along with the text embeddings of user queries present in the same dataset. The image and text embeddings are obtained via the use of OpenAl's CLIP model (Radford et al., 2021) 1) which maps both images and texts into a shared vector space. The task is to retrieve product images relevant contains metadata such as product image url, product id, product description, product title, product color, etc. The dataset is publicly available on Hugging Face platform.
given text query. The SQID also
We directly use the embeddings from the Hugging Face repository and map product id-s to retrieve additional metadata from the Amazon KDD dataset. We use a(u, v) 1 + u TT ||l|--|||| as the similarity function between two vectors u and v. Note that the image and text embeddings in the dataset were generated using the cosine similarity metric in the loss function (see (Ghossein et al., 2024), Section 4.2) hence the similarity function defined in this work is a natural choice. We choose the set of product colors as our set of attributes [c). To obtain a clean label for the product color of given product in the dataset, we apply majority voting among the colors listed in the product color, description, and title of the product. the event of a tie, we assign the item to a separate color class labeled "color.mxx (e.g., if the title says 'blue" but the color column says 'red"). ) Product entries in
Phttpss/aamazzokdddeup github.io
13 http:///ww........oooo//oooooooa
26

---

Published as a conference paper at ICLR 2026
truin 18 9.1%)
Green (5 356
Red (4.5%)
"Cllrr C5 (5.0%)
Black (28.0 0%)
Gray 15. 15.3%)
(8.5%)
Blse (7.3%)
Figure 3: Distribution of product colors in the processed (cleaned) Amazon dataset.
the dataset whose metadata does not contain any valid color names are removed. The pre- processing script will be shared with reviewers an anonymous repository during the open discussion phase and will be publicly released the camera-ready version. The processed dataset contains approximately 92, 092 vector embeddings of products. Note that we do not apply any pre-processing to the query set which contains 8, 956 vector. The vector embeddings of both images and queries 768 dimensional. Note that the dataset exhibits a skewed color distribution, shown in Figure 3), with some dominant colors such as black and white.
2. ArXiv OpenAl Embedding (ArXiv): The dataset published by Cornell University con- sists of vector embeddings for approximately 250, 000 machine learning papers available through the arXiv search engine (Wester, 2022). The embedding of given paper gen- erated using OpenAl's text-embedion wwweeeeddinnaaaaa -nn-aaa-000 model on the augmented abstract of the paper that combined the paper's title, authors, year, and abstract. The dataset is publicly available on Kaggle (Wester, 2022).
We consider the year in which paper was last updated as the attribute in the single-attribute setting, and additionally consider the arXiv category the paper belongs to as second at- tribute in the multi-attribute setting. Note that this dataset does not contain a predefined query set; hence, we randomly split 20% of the total vector embeddings to serve as queries. Such queries simulate the task of finding papers similar to given query paper. The simi- larity function used for this dataset is the reciprocal of the Euclidean distance between two vectors, i.e, for two vectors and or (u,
(u, v) +u= where μ is small constant to avoid issues for the case when ||u - vll = O. Typically, we set = 7) (recall that is the smoothening parameter in the definition of N-)) The distribution of the input vectors across update-year and arXiv category are shown in Figure 4.
For our experiments, we only consider papers with update-year between 2012 and 2025 (both inclusive) and belonging to one or more of the following arXiv categories: cs ai, math. oc, CS 1g. Cs CV, stat ml, CS ro, cs.cl, cs cs. ir, cs sy, cs hc, cs cr, Cs. cs.cy, cs sd, eess ass, and eess. iv. The pre-processing script will be shared with reviewers and will be publicly released in the camera-ready version.
anonymous repository during the open discussion phase
3. SIFT Embeddings: It a popular benchmarking dataset for approximate nearest neighbor search using the Euclidean distance (TensorFlow, 2025). The dataset consists of treitrained SIFT embeddings, with 1, 000, 000 vectors for indexing and separate of 10, 000 vec- tors as the query set, both in a 128 dimensional space. The embeddings are publicly avail- 15le (TensorFlow, 2025). Note that this dataset does not contain any metadata that can be naturally adapted as attributes to model diversity. Therefore, adopt two strategies for synthetic attribute generation:
14 hhttps://wwww hww.://ww..ommaaeeee///eeerrreea 15 http:///ww..ttatooooo.o//aaaaaaa
27

---

Published as a conference paper at ICLR 2026
2018 SUPN
IRd- (LL39)
2012 (663
2011
(a)
(b)
Figure Distribution of (a) paper categories (b) last update year the ArXiv v dataset.
Clustering-based (Si (Siftlm-ff (Clus)): Since attributes such as color often occupy distinct regions in the embedding space, we follow a similar idea and apply k-means clustering to identify 20 clusters. Each cluster is then assigned a unique color, which serves our synthetic attribute. Therefore, in this case
20.
Probability distribution-based (sift (Siftlm- (Prob)): To remain consistent with the prior work (Anand et al., 2025), we also adopt a randomized approach to color (at- tribute) assignment. For each vector, we assign one of three majority colors uniformly at random with probability 0.9, and with the remaining probability 0.1, one of the remaining 17 colors is assigned. This results in a skewed distribution over colors that mimics real- world settings (c.g., market dominance by few sellers). The pre- processing script will be shared with reviewers as an anonymous repository during the open discussion phase and will be publicly released in the camera-ready version.
Multi-attribute setting:
We extend the clustering- based attribute generation strategy to the setting as follows. We divide each 128 dimensional input vector into four 64] etc.
equal segments of 32 dimensions {r*) i.e., v1 =
.32.. u² = o We then separately apply k-means clustering compute 20 clusters each segment, i.e., on the set of vectors {u' E P} for each E [4]. Let the set of cluster ids be C; for the set of vectors {ur assigned to the original imput vector v is the union of the cluster ids of u's. s. In other words, atb(v)
P}. E [4]. Note that |C&| 20. Thereafter, the of attributes
L (C, where Cv(v") (1") the cluster id v².
4. Deep Deseriptor Embeddings:
another benchmarking dataset for nearest neighbor search, evaluated using cosine distance (TensorFlow, 2025). The version used in this study contains approximately 9, 990, 000 vectors for indexing and 10, 000 separate query vectors, both residing in a 96 dimensional space. These embeddings publicly available (Ten- sorFlow, 2025), and we adopt the same synthetic attribute generation procedure as in the SIFT dataset produce DeepIb-(Clus) and Deep1b-(PPr)) variants.
Choice of Parameter 77: For our methods, tune and set the smoothing parameter, 7), to 0.01 for the Arxiv, Si ft 1m-(Clus) and Si 1iftlmmPProb datasets in comparing relevance with diversity, and set it 0.0001 analyze performance at different values p. For other datasets, namely Amazon, Deeplb (heplb-(Clus) and Deeplb-(Pe))
we set to 50 for both experiments.
F.3 BALANCING RELEVANCE AND DIVERSITY: SINGLE- SETTING
In this experiment, we evaluate the performance of p-mean-ANN (and the special case of = O, Nash-ANN) in its ability to balance relevance and diversity in the p-NNS (and NaNNS) problem in the single-attring attribue setting. We begin by examining the tradeoff between approximation ratio and entropy achieved by our algorithms on additional datasets beyond those used the main paper. Moreover, we also report results for other diversity metrics such as the inverse Simpson index (Ap- pendix F.3.3) and the number of distinct attributes appearing in the neighbors (Appendix F.3.4)
16 http:///wwwttaacooooooo//aaaaaae
28

---

Published as a conference paper at ICLR 2026
SIFTIm-(Clus)
SIFTIm-(Clun)
4P=0
AP=0
3.5
k==5
k'm2
Entropy
Entropy
k'=10
1.5
k'=5
ANN
ANN
1
Nash-ANN
1.5
Nash-ANN Div-ANN
DIv-ANN
0.6
0.65
0.7 0.75 0.8 0.85 0.9
0.95
0.3
0.4
0.5
0.7 0.8 0.9
Approximation Ratio
Approximation Ratio
Figure 5: The plots show results on approximation ratio and entropy for (Left) k = 10; (Right) A = 50 in single-attribute setting on Sifflmm(CClus dataset.
SIFT1m-(Prob)
SIFT1m- (Prob)
3.4
AP=0
AP=
3.2
k'=5
3-
Entropy
2.8
2.6
k'=2
Entropy
k=10
2.4
2.2
2
2.5
Nash-ANN
1.8
DIv-ANN
DIv-ANN
0.88
0.9
0.92
0.94
0.96
0.98
0.4
0.5
0.6
0.7
0.8
0.9
Approximation Ratio
Approximation Ratio
Figure 6: The plots show results approximation ratio and entropy for (Left) k 10; (Right) & 50 in single-attribute setting on Siftim-(PPoo) dataset.
retrieved by algorithms. These experiments corroborate the findings in the main paper, namely, Nash-ANN and Sadp--n---Ae ANN are able to strike a balance between relevance and diversity whereas ANN only optimizes for relevance (hence low diversity) and Div-ANN only optimizes for diversity (hence low relevance).
F.3.1 APPROXIMATION RATIO VERSUS ENTROPY
We report the results for different datasets in Figures 5, 6, 7, 8, and 9. On the Siftim- dataset (Figure 5), Nash-ANN achieves entropy close to that of the most diverse solution (Div-ANN with k' 1) in both & = 10 and 50 cases. Moreover, Nash Bash-ANN ANN achieves significantly higher approximation ratio than Div-ANN in both k 10 and k 50
when K' 1. For k = 10 case, Nash-AND ANN Pareto dominates Div-AND ANN even with the relaxed constraint of & 50, no other method
for 10. When the number required neighbors increased Pareto dominates Nash-AND Similar observations hold for the Sift 1m- 1a.lmmPrra (Prob) (Figure 6), and -e (Figure 7) datasets. In the results on the Arxiv dataset (Figure with k: 10, we observe that Di Div-ANN already achieves high approximation ratio. However, Nash-ANN matches the entropy of Div-AND with
while improving on the approximation ratio. For k == 50, Nash ANN nearly matches the entropy of Div- ANN with k' = 1, 2 whereas it significantly improves on the approximation ratio. The results for k 10 for datasets in the main paper are shown in Figure and have similar observations. In summary, the experimental results clearly demonstrate the ability of Mash-ANN to adapt to the varying nature of queries and consistently strike a balance between relevance and diversity.
29

---

Published as a conference paper at ICLR 2026
Deep1b-(Prob)
(Peob
3.4
Ap=0
3.2
AP=
k==5
3-
Entropy
2.8
k=2
Entropy
3.5
2.6
1-
2.4
2.2
ANN
ANN
2-
Nash-ANN
Nash-ANN Div-ANN
1.8
DIv-ANN
0.965 0.97 0.975 0.98 0.985 0.99 0.995
0.4
0.5
0.6
0.7
0.8
0.9
1
Approximation Ratio
Approximation Ratio
Figure 7: The plots show results on approximation ratio and entropy for (Left) k = 10; (Right) A = 50 in single-attribute setting on
dataset.
ArXiv
ArXiv
4P=0
ANN
3.8
Ap=0
3.2
Nash-ANN Div-ANN
3.6
3
Entropy
Entropy
2.8
3.2
ANN
K=10
2.4
Nash-ANN
2.2
2.8
Div-ANN
0.99
0.992
0.994
0.996
0.998
0.3
0.4 0.5 0.6 0.7 0.8 0.9
Approximation Ratio
Approximation Ratio
Figure& 8: The plots show results on approximation ratio and entropy for (Left) k = 10; (Right) k: 50 single-attribute setting on ArXiv dataset.
Amazon
Deep1b-(Clus)
ANN
ANN
3.2
Nash-ANN Div-ANN
Nash-ANN
3
Div-ANN
Entropy
2.8
2
Entropy
A
2.6
2.4
1.5
k'=5
k'=5
2
0.97
0.97
0.98
0.985
0.99
0.995
0.85
0.88
0.9
0.93
0.95
0.98
Approximation Ratio
Approximation Ratio
Figure 9: The plots show results approximation ratio and entropy for (Left) k = 10; (Right) A = 10 in single-attribute setting on Amazon and Deeplb-(Clus) dataset.
F.3.2 PERFORMANCE ON p- MEAN-ANN
In this set of experiments, we study the effect on trade-off between approximation ratio and en- tropy when the parameter p in the p-NNS objective is varied range. Recall that the p-NNS problem with + corresponds to the NaNNS problem and with p = corresponds to the NNS problem. We experiment with values of p E (-10, 11, -0.5, 0.5, 1} by running algorithm
30

---

Published as a conference paper at ICLR 2026
SIFTIm-(Clus)
SIFTIm-(Clus)
p=.10
Ap=-10
Ap=.1
Ap=-1
3.5
Ap=-0.5
Entropy
Ap=-0.5
Entropy
AP=0
AP=0
4p=
AP=0.5
1.5
ANN
ANN
1.5
1
p-mean-ANN
p-mean-ANN
DIv-ANN
P
Div-ANN
0.6
0.9 Approximation Ratio
0.7
0.8
0.3
0.4
0.5
0.7
0.8
0.9
Approximation Ratio
Figure 10: The plot reports the performance of p-mean-AND with varying values for (Left) k 10; (Right) k 50 on Si AafflmmmCllss dataset the single-attribute setting.
(IFoom-(Prob)
SIFT1m-(Prob)
3.4
Ap=-10
4P
3.2
3-
AP=0
Entropy
2.8
Entropy
2.6
2.4
2.2
ANN
ANN
2-
p-mean-ANN
p-mean-ANN
1.8
Div-ANN
Div-ANN
1==1
0.88
0.9
0.92
0.94
0.96 0.98
1
0.4
0.5
0.6
0.7
0.8 0.9
Approximation Ratio
Approximation Ratio
Figure 11: The plot reports the performance of p-mean-ANN with varying values for (Left) k 10: (Right) i 50 on Siftim-(Prob) dataset in aiglle-ttribute setting. Note that for all other E {-1, 00.5, 0.5, }} the approximation ratio and entropy were extremely close to ones of y=-10, 0. To avoid clutter plot we only show p= 10,
p-Mean-ANN (Algorithm 3) on the various datasets. The results are shown in Figures 10, 11, 12, and 14. We observe across all datasets for both & 10 and t: 50 that as p decreases from the entropy increases but approximation ratio decreases. This highlights the key intuition that de- creases, the behavior changes from utilitarian welfare (p- aligns exactly with ANN) to egalitarian welfare (more setribute-diverse) In other words, the parameter allows us smoothly interpolate between complete relevance (the standard NNS with = 1) and complete diversity (p - -oo).
F.3.3 APPROXIMATION RATIO VERSUS INVERSE SIMPSON INDEX
We also report results (Figures 15, 16, 17, 18, 19, and 20) on approximation ratio versus inverse Simpson index for all the aforementioned datasets, comparing Nash-ANT ANN with Div-ANN with various choices of quota parameter k'. The trends are similar to those for approximation ratio vs. entropy.
F.3.4 APPROXIMATION RATIO VERSUS DISTINCT ATTRIBUTE COUNT
We also report the number of distinct attributes appearing in the set of neighbors returned by dif- ferent algorithms. Note that Div-ANN by design always returns a set where the number of distinct attributes is at least (k/k'). We plot approximation ratio versus number of distinct attributes and the results are shown in Figures 21, 22, 23, and 24. The results show that while Div-ANN with k' has high number of distinct attributes (by design) its approximation ratio is quite low. On the other
31

---

Published as a conference paper at ICLR 2026
Deep1b-(Prob)
Deeplb-(Prob)
3.4
K=1
Ap=-10
Ap=-10
3.2
4P=0
3-
Ap=0.5
Entropy
2.8
Entropy
3.5
2.6
2.4
2.2
ANN
ANN
2-
p-mean-ANN
p-mean-ANN
1.8
DIv-ANN
Pp=1
Div-ANN
0.965 0.97 0.975 0.98 0.985 0.99 0.995
0.4
0.5
0.6
0.7
0.8 0.9
Approximation Ratio
Approximation Ratio
Figure 12: The plot reports the performance of p-mean-ANN with varying values for (Left)
10; (Right) & 50 on Deeplb-(Pro)) dataset in single-attribute setting. Note that for all
other E [-1 -0.5, 0, 0.5, } the approximation ratio and entropy were extremely close to ones of
p=-10 10 50. To avoid clutter in plot we only show p = -00. Due to same reasons we omit p =
-1, 0.5 for k 10.
ArXiv
ArXiv
4p=-10
AP4-10
3.2
3.6
3
Entropy
Entropy
3.4
2.6
ANN
ANN
2.4
p-mean-ANN
p-mean-ANN
2.2
Div-ANN
2.8
Div-ANN
0.975
0.98
0.985
0.995
0.5
0.7 0.8 0.9
Approximation Ratio
Approximation Ratio
Figure 13: The plot reports the performance of p-mean-ANN with varying values for (Left)
10; (Right) 1 50 ArXiv dataset in single-attribute setting. Note that for all other p {-1, 0.5, 0, 0.5) the approximation ratio and entropy were extremely close to ones of p=-10. To avoid clutter in plot only show p ==0. O.
hand, Nash-aa ANN has almost equal or slightly lower number of distinct attributes but achieves very high approximation ratio.
F.3.5 RECALL VERSUS ENTROPY
We also report results for another popular relevance metric in the nearest neighbor search literature, namely, recall. The results for different datasets are shown in Figures 27, 28, 29, 30, 31, and 32. Note that discussed earlier (Appendix F.1), recall can be fragile metric when the goal is to balance between diversity and relevance. However, we still report recall to be consistent with prior literature and to demonstrate that Nash- ANN does not perform poorly. In fact, it is evident from the plots that Nash-ANN recall value (relevance) surpasses that of Div-ANN with k' = (most attribute diverse solution) while achieving almost similar entropy. As already noted, the approximation ratio for Nash-AN remains sufficiently high, indicating that the retrieved set of neighbors lies within reasonably good neighborhood of the true nearest neighbors of given query.
32

---

Published as a conference paper at ICLR 2026
Amazon AP=
Deeplb-(Clus)
Ap=-10
ANN
p-mean-ANN
3-
p=0.5
2.5
Entropy
Entropy
2.6
AP=0.5
2.4
1.5
ANN
2.2
p-mean-ANN
2
Div-ANN
0.97 0.97 0.98 0.985 0.99 0.995
0.85
0.88 0.9
0.93
0.95 0.98
Approximation Ratio
Approximation Ratio
Figure 14: The plot reports the performance of p-mmannAAN with varying values for (Left) k: 10 on zonzon; (Right) 10 Deeplb-(Clup dataset in single-attribute setting. Note that for all other p E 1-1, -0.5, 0, 0.5) the approximation ratio and entropy were extremely close to ones of p=-10 in Deeplb-(Clus) dataset. To avoid clutter in plot we only show p = 0. Due similar reasons we omit p -1 in Ama on dataset as it was close to p { {-10) -0.5)
SIFTIm-(Clus)
SIFT1 (IFTum-(Clus) (Clus)
Inverse Simpson Index
Inverse Simpson Index
20
17.5
AP=0
AP=0
15
12.5
k=5
k'=2
10
ANN
ANN
k'110
Nash-ANN Div-ANN
k=5
5
Nash-ANN
2.5
Div-ANN
0.6 0.65
0.7 0.75 0.85 0.9
0.95
0.3
0.4
0.5
0.6
0.8
0.9
Approximation Ratio
Approximation Ratio
Figure 15: The plots show results on approximation ratio and inverse Simpson index for (Left) k: 10: (Right) & 50 in single-attribute setting on Sift Im-(Clus) dataset.
SIFT1m-(Prob)
SIFTIm-(Prob)
Inverse Simpson Index
10
AP=0
Inverse Simpson Index
20
17.5
15
k'
k'=2
5
7.5
k=10
Nash-ANN
Nash-ANN
km
5-
0.88
0.9
0.92
0.94
0.96
0.98
0.4
0.5
0.5
0.7
0.8
0.9
Approximation Ratio
Approximation Ratio
Figure 16: The plots show results approximation ratio and inverse Simpson index for (Leff) J: 10; (Right) l = 50 single-attribute setting on S 1 (m-rrob) dataset.
33

---

Published as a conference paper at ICLR 2026
Deep1b-(Prob)
Deep1b-(Prob] k
Inverse Simpson Index
Inverse Simpson Index
20
AP=
AP-0
k'5
12.5
k=2
10
=10
ANN
7.5
ANN
Nash-ANN DIv-ANN
Nash-ANN
Div-ANN
0.965 0.97 0.975 0.98 0.985 0.99 0.995
0.4
0.7
0.8
0.9
Approximation Ratio
Approximation Ratio
Figure 17: The plots show results on approximation ratio and inverse Simpson index for (Left) A 10; (Right) k = 50 in single-attribute setting on Deeplb (eeplb-(Prob) (Prob) dataset.
ArXiv
ArXiv
k==1
AP=
Inverse Simpson Index
Inverse Simpson Index
Nash-ANN
13
12
11
ANN
Nash-ANN
k-10
k'
Div-ANN
0.99
0.992
0.994
0.996
0.998
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Approximation Ratio
Approximation Ratio
Figure 18: The plots show results on approximation ratio and inverse Simpson index for (Left) A 10: (Right) k 50 in single-attribute setting on ArXiv dataset.
Amazon
Amazon
Inverse Simpson Index
Inverse Simpson Index
A
Nash-ANN
Nash-ANN Div-ANN
40
30
k'=2
20
k'=5
k=s5
10
k=100
0.97 0.975 0.98 0.985
0.99
0.995
0.85
0.9
0.95
Approximation Ratio
Approximation Ratio
Figure 19: The plots show results on approximation ratio and inverse Simpson index for (Left) A 10: (Right) k 50 in single-attribute setting on Amazon dataset.
F.4 BALANCING RELEVANCE AND DIVERSITY: MULTI-ATTRIBUTE SETTING
Recall that our welfarist formulation seamlessly extends to the multi-attribute setting. In Sec- tion 4, discussed the performance of Multi Nash-ANN and Multi Div-ANN (m-(uss,, where each input vector was associated with four attributes. In this section, repeat the same of experiments of the real-world dataset, namely Arxiv. which nat-
34

---

Published as a conference paper at ICLR 2026
Deep1b-(Clus)
Deep1b-(Clus)
20
k'=2
Inverse Simpson Index
Inverse Simpson Index
Nash-ANN
17.5
Nash-ANN
15
Div-ANN
AP-O
12.5
k=5
k'=2
p=0
7.5
k==10
k'w5
2.5
0.85
0.88
0.9
0.93
0.95
0.98
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Approximation Ratio
Approximation Ratio
Figure 20: The plots show results on approximation ratio and inverse Simpson index for (Left) A 10; (Right) k = 50 in single-attribute setting on Deeplb- (Cluss dataset.
SIFTIm-(Clus)
SIFTIm-(Cluss
20
Ap=
#Distinct Attributes
#Distinct Attributes
AP=0
15
12.5
k'=2
k==5
10
ANN
7.5
ANN
k k'110
Nash-ANN DIv-ANN
k=5
Nash-ANN
Div-ANN
0.6 0.65 0.7 0.75
0.85 0.9
0.95
0.3
0.4
0.5
0.6
0.8
0.9
Approximation Ratio
Approximation Ratio
Figure 21: The plots show results on approximation ratio and distinct counts for (Left) k = 10; (Right) k 50 single-attribute setting on si (Cllmm(Cuus) dataset.
SIFT1m-(Prob)
(IFTIm-(Prob)
k=
#Distinct Attributes
#Dsstinct Attributes
k==5
k=10
k'=2
12
ANN
10
ANN
Nash-ANN Div-ANN
Nash-ANN
km=5
Div-ANN
0.88
0.9
0.92
0.96 0.98
0.7 0.8
Approximation Ratio
Approximation Ratio
Figure 22: The plots show results on approximation ratio and distinct counts for (Left) k: = 10; (Right) k 50 single-atrribute setting on si sifflmm((P (P rob) dataset.
urally contains two partition sets of the attributes (m 2: see Appendix F.I, Diversity Metrics): update year (CCi 14) and paper category ([C2) = 16). Therefore, [C2 -
30. The
results for = 50 are presented Figure 33. Note that in each plot we restrict the entropy to one of the attribute partitions (C₃ and C2) so that the diversity within partition set can be understood from these plots. The results indicate that Multi Nash-ANN achieves an approximation ratio very close to while maintaining entropy levels comparable Mult? Div-ANN with k' or 2 for
35

---

Published as a conference paper at ICLR 2026
(eeo1b-(Prob)
Deeplb-(Prob)
20
#Distinct Attributes
AP=0
#Distinct Attributes
k=5
18
16
k=10
14
12
ANN
10
ANN
Nash-ANN DIv-ANN
Nash-ANN
Div-ANN
0.965 0.97 0.975 0.98 0.985 0.99 0.995
0.4
0.5
0.6
0.8
0.9
Approximation Ratio
Approximation Ratio
Figure 23: The plots show results on approximation ratio and distinct counts for (Left) k = 10;
(Right) & 50 single-attribute setting on Deeplb-(P rob) dataset.
ArXiv
ArXiv k=
10
ANN
14
AP=0
Distinct Attributes
Nash-ANN Div-ANN
#lsstinct Attributes
12
11
k==2
ANN
10
Nash-ANN
k=10
Div-ANN
0.99
0.992
0.994
0.996
0.998
0.3
0.4
0.5
0.6
0.7
0.8 0.9
Approximation Ratio
Approximation Ratio
Figure 24: The plots show results approximation ratio and distinct counts for (Left) k 10:
(Right) k- 50 in single-attribute setting on ArXiv dataset. dataset...
Amazon
Amazon
k'=1
50
#Distinct Attributes
#Distinct Attributes
Nash-ANN
40
Div-ANN
AP=
30
=2
k 2
25
20
k'=5
K'=5
k'100
15.
0.97
0.975 0.98
0.985
0.99
0.995
0.85
0.9
0.95
Approximation Ratio
Approximation Ratio
Figure 25: The plots show results on approximation ratio and distinct counts for (Left) k: = 10;
(Right) & 50 single-attribute setting on Amazon dataset.
both the attribute partition sets. In fact Multi Nash-ANN Pareto dominates Multi Div-ANN with 1'' = 5.
We also study the effect of varying p in p-NNS problem in the multi-attribute setting. The sults for performance Multi p-Mean-ANN (an analogue of Multi Nash-ANN) for p e {-10, 1, -0.5, 0.5, 1) shown in Figures 34 and 35. Interestingly, observe that with de-
36

---

Published as a conference paper at ICLR 2026
Deep1b-(Clus)
Deeplb-(Clus)
20
k==2
k==1
#Distinct Attributes
Nash-ANN
#Distinct Attributes
18
Ap=
16
14
k'=2
p=0
12
k'=10
ANN
k'=5
Nash-ANN
Div-ANN
0.85
0.875 0.9
0.925
0.95
0.975
0.3
0.4
0.5
0.7
0.8
0.9
Approximation Ratio
Approximation Ratio
Figure 26: The plots show results on approximation ratio and distinct counts for (Left) k = 10;
(Right) &: 50 single-attribute setting on Deeplb- (Clus) dataset.
SIFT1m-(Clus)
SIFTLm-(Clus)
ANN
4p=0
ANN
3-
4P=0
Nash-ANN Div-ANN
Nash-ANN
k==
Div-ANN
2.5
2²=2
Entropy
Entropy
2
2.5
1.5
1.5
1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.2
0.4
0.6
0.8
Recall
Recall
Figure 27: The plots show results recall and entropy for (Left) /s 10 (Right) k = 50 in single- attribute setting on Si sifflmm(CClus dataset.
SIFT1m-(Prob)
SIFTIm-(Prob)
3.4
*1p=0
ANN
ANN
3.2
Nash-ANN Div-ANN
k=5
Nash-ANN
3-
Div-ANN
Entropy
2.8
2==2
Entropy
3.5
k'=10
2.6
2.4
2.5
0.4
Recall
Recall
Figure 28: The plots show results on recall and entropy for (Left) 10: (Right) h: 50 single- attribute setting on Sife (ift1m-(Prob) dataset.
creasing p. the entropy (across C1 or C2) increases but the approximation ratio remains nearly the same and very close to 1. On the other hand, Multi Div-ANN with k' has very low ap- proximation ratio. In fact, Multi p-mean-AND with = and -10 Pareto dominates Multi Div-ANN with K 1.
37

---

Published as a conference paper at ICLR 2026
Deep1b-(Prob)
Deep1b-(Prob)
3.4
AP=0
3.2
AP=0
Nash-ANN
k==5
Nash-ANN
3-
Entropy
2.8
Entropy
3.5
k'=10
2.6
2.4
2.2
2
1.8
0.4
0.5
0.6
0.7
0.8
0.9
0.2
0.4
0.6
0.8
Recall
Recall
Figure 29: The plots show results on recall and entropy for (Left) k= = 10 (Right) k = 50 in single- attribute setting on Deepib- rob) dataset.
ArXiv
ArXiv
0=
3.8
k==2
AP=0
3.2
Nash-ANN
3.6
3-
k'=5
Entropy
Entropy
2.8
2.6
ANN
k'=10
2.4
Nash-ANN Div-ANN
2.2
2.8
0.5
0.6
0.7
0.8
0.9
0.2
0.4
0.8
Recall
Recall
Figure 30: The plots show results on recall and entropy for (Left) k == 10; (Right) A = 50 in single- attribute setting on ArXiv dataset.
Amazon
Amazon
5.5
4P=0
Nash-ANN
Nash-ANN
3
k==2
A
Div-ANN
Entropy
k'=2
Entropy
4.5
2.6
k'=5
2.4
k'=10
2.2
k'=5
2
0.5
0.6
0.7
0.8
0.9
1
0.2
0.3
0.4
0.5
0.6 Recall
0.7
0.8
0.9
Recall
Figure 31: The plots show results on recall and entropy for (Left) == 10 (Right) k 50 in single- attribute setting on Amazon dataset.
F.5 A FASTER HEURISTIC FOR THE SINGLE ATTRIBUTE SETTING: P-PEECIUNION--AAAAC
In this section, we empirically study a faster heuristic algorithm for NSW and p-mean welfare for- mulations. Specifically, the heuristic-calle called p-PetchUnionnANNY first fetches sufficiently large candidate set of vectors (irrespective of their attributes) using the ANN algorithm. Then, ap- plies the Nash (or p-mean) selection (similar to Line 5 in Algorithm 1 or Lines 6-8 in Algorithm 3)
38

---

Published as a conference paper at ICLR 2026
Deep1b-(Clus)
Deeplb-(Clus)
Nash-ANN
AP=o k'a
Nash-ANN
2.5
K=
AP=D
Entropy
Entropy
k'=10
2-
1.5
k'=5
0.2
0.4
0.8
0.2
0.4
0.6
0.8
Recall
Recall
Figure 32: The plots show results on recall and entropy for (Left) k= = 10 (Right) k = 50 in single- attribute setting on Deeplb- (Clus) dataset.
ardivv
ar3dv
(K=1)
[k =2)
(K=1)
[K =2)
P-0
P=O
(K=5)
3.6
Entropy (across
Entropy (across
3.4
3.2
(k=10)
Multi Div-ANN Multi Nash-ANN
(K=10)
2.8
Multi Nash-ANN
ANN
ANN
ANN
ANN
0.40
1.00
0.40
0.80
Approximation Ratio
Approximation Ratio
Figure 33: The plot shows approximation ratio and entropy trade-off ArXiv dataset in multi- attribute setting.
3.8
p=:
4.0
K=1
p=
ps.1
3.7
p=0
K=1
p=0
Entropy (across
Entropy (across
3.6
p=0.5
3.5
p50.5
3.4
3.4
3.2
3.2
Multi Div-ANN
3.0
Multi Div-ANN
Multi p-mean-ANN
Multi p-mean-ANN
3.1
p=1
p=1
0.30
0.40 0.50 0.60 0.70 0.80 0.90 1.00
0.30
0.40 0.50 0.60 0.70 0.80 0.90 1.00
Approximation Ratio
Approximation Ratio
Figure 34: The plot reports the performance of p-mean-ANN with varying p values for k 50 in multi-attribute setting ArXiv dataset.
within this set. That is, instead of starting out with & neighbors for each & E [c] (as in Line of Algorithm 1), the alternative here is to work with sufficiently many neighbors from the set Dr
We empirically show (in Tables to 7) that this heuristic consistently achieves perfor- mance comparable to p-Mean-ANN ANN across nearly all datasets and evaluation metrics. Since
39

---

Published as a conference paper at ICLR 2026
SIFTIm-(Clus)
SIFTIm-(Clus)
2.4
(k=2)
(K=5)
(k=10)
5k=
(k=10)
2.4
(K=2)
2.2
(k=1)
Entropy (across C-)
1K=
Entropy (across C.)
(k=15)
2.2
(K=1))
2.0
(K=20)
(k'=20)
1.8
2.0
P
1.6
(K=30)
(K=30)
1.4
Multi Div-ANN
Multi Nash-ANN
(k=400)
1.6
Multi
Multi Nash-ANN
(k:40)
1.2
ANN
ANN
ANN
0.20
0.40
0.80
0.20
0.40
0.50
0.80
1.00
Approximation Ratio
Approximation Ratio
SIFTIM-(Chus)
SIFTIM-(Clus)
Multi Div-ANN
3.2
Muiti Div-ANN
Multi p-mean-ANN
Multi p-mean-ANN
3.0
ANN
ANN
2.4
Entropy (across
k-11
Entropy (across
2.8
2.5
1
1.8
0.5
2.2
K=1
P=
2.0
p
1.4
p=p.5
1.8
p=0.5
1.2
p=] ANN
1.5
ANN
0.40
0.60
1.00
0.40
0.80
Approximation Ratio
Approximation Ratio
Figure 35: Top Row: The plots show approximation ratio entropy trade-off's for Nash against Biv-ANN with varying values of k' for attribute class C3 (left) and C₁ (right). Bot- The plots show approximation ratio versus entropy trade-offs for p-mean-ANN, as p varies, across attribute classes C3 (left) and C4 (right). Both the rows correspond to k 50 on sifftmm((llus) dataset in the multi-attribute setting.
tom Row:
p-PetchUnionnAAN retrieves larger pool of vectors with high similarity, it achieves im- proved approximation ratio over p-Mean-ANN. This trend is evident in two datasets, namely Deep1'o(Clls) and i ftim-(Clus)) although comes at the cost reduced entropy. which can be explained by the fact that in restricting its search to an initially fetched large pool of vectors, p p-Fetchunion ANN may miss out on a more diverse solution that exists over the entire dataset. Another important aspect of p- FetchUnion- ANN is that, because it retrieves all neighbors from the union at once, the heuristic delivers substantially higher throughput (measured as queries per sec- ond, QPS) and therefore lower latency. The results validating these findings reported in Tables and 9 for the Si ftlmmmmm (Clus) and Ama zon datasets, respectively. In particular, it serves almost and 3x
10x queries Si ft values exhibit a similar trend with reductions of similar magnitude. In summary, these observations position the heuristic notably fast method for NaNNS and p-NNS, particularly when is large.
queries Amazon dataset. The latency
F.6 COMPARISON WITH DIVERSITY BASED ON MINIMUM PAIRWISE DISTANCE
The current work studies diversity across specified attributes. Our comparisons focus on the hard- constrained approach, as it is the essential prior work that also addresses attribute diversity (Anand et al., 2025). In NNS, we found two additional threads of work on diversity and fairness. How- ever, the normative concepts in these prior works are not attribute-centric. The diversity criterion developed in (Abbar et al., 2013a;b) requires an additional distance function (and not specifically attributes) express diversity. The objective in (Abbar et al., 2013a) and (Abbar et al., 2013b) is to return, from the set of vectors that are at most r distance away from the query, a subset vectors that maximizes the minimum pairwise diversity distance.
40

---

Published as a conference paper at ICLR 2026
Metric
Algorithm
p 10
p
P 0.5
p
p Nean ANN
0.865:10.045
0.909=0.029
0.92240.0277
0.938=0.023
0.961100018
1.000=00.000
p Fetcchtiinn-A ANN
0.90710.003
0,912=0.030
0.92110.027
0.935=0.022
0,958100019
1.000=10.000
Approx. Ratio
ANN
1 1.00000.000
Div-ANN 11)
0.81++0.053
p Opean-ANK
5.644:10.00
5.382=0.135
5.25244..133
5.058=0.178
4.687:00.227
6.782:40.88
p- Fetchhnionn-AA ANN
1.364:0.156
5.333=0.149
5.261
5.099=0.171
4.736::0221
2.782:10.684
Entropy
ANN
2.782:00.684
Div-ANN (1=
5.594:0.049
Table 2: Comparison of performance across p values for Amazon at 50.
Metric
Algorithm
p
p=
2:
p=
p=
p M-e--eaa-- ANN
0,985 0.985100010
0.98510.010
0.986=0.009
0.9891100008
1.000=10.001
7- F--eetchtini D- AnN
0.989-00.007
0.989+0.007
0.989+00007
0.990-00000
0.991+00.006
1.000+0.001
Approx. Ratio
1.00+00.001
(V=1)
0.29310.007
P Mean- ANN
3.793:40.002
3.793=0.002
3.793+2.0002 0.0
3.793=0.002
3.793-10.002
2.790-10.510
p- -hhtiohunn
3.704:10.167
3.704=0.166
3.704+0.166
3.704:0.166
3.704
2.790=10.510
Entropy
ANN
2.790
ANN (1=
3.799100022
Table 3: Comparison of performance across p values for ArXiv at 50.
One way to adapt the distance-based diversity notion to the singlc-attribute setting is by considering Hamming distances. Specifically, any two vectors with the different attributes are set to have a diversity distance of and vectors with the same attribute are set at 0 distance. The key issue with this adaptation is that the solutions it finds will always be at the extremes (See Figure 36, and 37 for k == 10, and k= 50 respectively). That is, if the prefetched pool consists of more than & different
attributes, then the subset picked by this approach will consist of one vector from each attribute (i.e., it is the same as the one via the hard-constraint formulation with k' 1). Otherwise, if the prefetched pool consists of less than & different attributes, then any size-k subset will have minimum diversity distance 0. Hence, in this case, the selected subset can be arbitrary; say. the & most similar vectors. This observation underscores that the notion from (Abbar et al., 2013a) and (Abbar et al., 2013b) (with Hamming distance as the diversity function) does not provide comparison point stronger than Div-ANN with different values of K.
We also note that, in the function is quite ad hoc. This restricts the use of the distance-based diversity notion in multi-attribute settings.
setting, the Hamming distance based diversity distance
41

---

Published as a conference paper at ICLR 2026
Metric
Algorithm
10
-0.5
0.5
1
D-Mean-ANN
0.784:10.07
0.815=0.065
0.831+000063
0.858=0.060
0.904:000049
1.000=0.000
p FetchUnioo ANN
0.958:00033
0.961
0.962+0.029
0.963=0.028
0.968:0.022
1.000=0.000
Approx. Ratio
ANN
1.000000000
Div-ANN 11=
0.286+0.041
A-Meen-ANN
4.293:10.00
4.200=0.052
4.1054#.001
3.887=0.155
3.349:0.267
0.746:0.717
pr F-FechhnnionnA30
2.101#1..14
2.101
2.099:1.212
2.095=1..27
2.068=1.179
0.746=0.717
Entropy
ANN
0.746:0.717
Div-ANN (1=11)
4.191
Table 4: Comparison of performance across values for
at k = 50.
Metric
Algorithm
p= -10
p=
p= -0.5
p=
p 0.5
p 1
Mean-ANN
0.958:10.019
0.960=0.017
0.961:0.016
0.963:000114
0.969:100100
1.000=000000
0.958:10.019
0.960=0.017
0.901
0.963=00.14
0.969::00010
1.000=0.000
Approx. Ratio
10000000000
Div ANN (1=
0.395
P M-e--e-n-- ANN
4.293:10.000
4.29220.005
4.288:1.0110
4.275=0.020
4.217:10008
2.070=10.208
4.293:10.001
4.292=0.005
4.288110010
4.275=0.020
4.217=:0.68
2.070=10.207
Entropy
2.070+0.207
DiV-ANN 1)
4.322+:0.002
Table Comparison of performance across p values for Deep1 b- (Prob)
k 50.
SIFTIm-(Clus)
SIFT1m-(Prob)
ARN Div-ARN Nash ANH PairDi--AMM
+K-1
Entropy
Entropy
Entropy
ANN
ANN
DIr-AM Nesh-ANN
Dh-ANN
Neah-Alt
PuirDiv ANH
PairDiv ANH
0.97 0.975 0.90
0.685
8.99 6.995
0.6 0.65 0.7 0.75 0.0 0.85 0.9 0.95
0.08
0.0
0.92
0.94
6.06
0.30
Approsimation Ratio
Approximation Ratio
Approximation Ratio
DeapIb-(Clus)
DeepIb-(Prob)
ArXiv
1
3.2
24
AMN
Di--AM
Mash-ANM
Entropy
2.5
PairOi- ANN
Entropy
2.5
ANN
2.8
AMN
Div-ANN
DI--MN
Rush AMH
2.
Nash-AMt
Pair DiN-ANN
PulrDiv-A0
2.2
0.88
0.9
0.23
0.55 0.80
0.965 6.97 0.975 0,90 0.905 0.995
0.95
0.06
0.27
0.93
Approximation
Approximation
Approximation
Figure 36: Comparison of ANN Variants on different datasets for p= = 0 and k = 10.
Metric
Algorithm
p
p=-1
p -05
p=
p
p
p- p--een-ANN
0.749-10.051
0.810=0.045
0.812+0.043
0.846=0.036
0.932+0.028
1.000=0.000
D-Fetchunion-A3W
0.979-40.014
0.980=0.013
0.980+0.013
0.981=00012
0.983+0.011
1.000=0.000
Approx. Ratio
ANN
1. 1.00000.000
Div-ANN (1==1)
0.31510.021
p M-e-eeenn-a ANN PrPrtcchtnioo--AAA ANN
4.285:10012
4.29320.002
4.293+1.001
4.197=0.045
3.506:10.275
0.892-10.663
2.235
2.238 0.800
2.239+0.802
2.239+0.802
+0.800
0.892+0.663
Entroy
0.892=0.663
Div-ANN (1=1)
4.28911.053
Table 6: Comparison of performance across p values for Siftlm (Clus) at k 50.
42

---

Published as a conference paper at ICLR 2026
Metric
Algorithm
p
p
p 00.5
p
p
P Mean-ANN ANN
0.975:40.010
0.977 008
0.979:100008
0.980=000088
0.982-20.006
1.000=00.000
F-techhnioo--a ANN
0.975+0.010
0.977=0.008
0.979=000008
0,980=0.008
0.982-00.006
1.000=0.000
Approx. Ratio
ANN
1. 1.000=0.000
Div-ANN 11=
0.404+0.0004
p- Mean-ANN
4.292-10.006
4.292+0.003
4.293++0.002
4.293-00.02
4.269+0.020
2.068-+0.205
D-Fotchunion--WW ANK
4.292-+0.006
4.292+0.003
4.293++00002
4.293=40.03
4.269+0.020
2.068+0.205
Entropy
2.0 0.0
Div-ANN (1=1)
4.322:10.005
Table Comparison of performance across p values for Siftlm-(Pro)) k 50.
Amazon
SIFTIm-(Clus)
SIFTIm-(Prob)
5.5
+N-1
*K+1
Entropy
Entrop
3.5
ANN
1.5
0.53
0.6 Approximation
Approximation Ratio
Approximation
Desp1b-(Clus)
Deep1b-(Prob)
Arkiv
+V-1
3.8
.K-1
Entropy
Entropy
Div.ANN
Nosh ANH
Noch-ANt
Nosh
PairDir ANH
2.8
PairDiv
Approximation Ratio
Approximation Ratio
Approximation Ratio
Figure 37: Comparison of ANN Variants on different datasets for p = and 50. We set
Metric
Algorithm
p= -10
===
==
-0.5
== 0.5
p=
p-Mean-ANN
120.86
115.78
107.01
135.98
122.59
122.59
Query per Second
p-Fetchunion-AAR
1324.53
1324.62
1337.28
1442.03
1327.03
Meann-ANN
264566.00
276129.00
298804.00
230318.00
235144.00
260800.00
Latency (μa)
Fetchunion--aa ANN
24133.80
24134.00
23907.00
22170.20
22149.30
28990.40
P-Maan-ANN p-FetchUnicn-AME
484601.00
513036.00
477925.00
482777.00
4791.32.00
90.9th percentile of Latency
52943.40
53474.70
54283.40
56128.70
53082.20
24088.70
Table 8: Comparison of performance on Queries per second and Latency across p values on siftim-(Clus) dataset for l: = 50.
Metric
Algorithm
p= 10
p=
p -0.5
p
p=
p
p-Mean-ANN
198.08
195.97
199.08
179.03
171.22
189.31
Query per Second
P-FotchUnionn-A0
620.27
610.62
551.02
608.76
572.57
591.76
p M-Meenn-Aa ANN
161385.00
163121.00
160503.00
178555.00
186780.00
168856.00
Latency (us)
p O-FetchUnicn-AN
51539.90
52362,30
58028.60
52521.60
55843.70
$4030.80
MeannANN
433434.00
407151.00
418147.00
421725.00
475474.00
404477.00
99.9th percentile Latency
146632.00
144989.00
145620.00
145657.00
143627.00
146464.00
Table Comparison of performance on Queries per second and Latency across p values on Amazon dataset for & = 50.
43


Reviews:
[{"review_id": "3wRwY1saSE", "reviewer": "Reviewer_gr82", "summary": "This paper proposes a novel approach to nearest neighbor search (NNS) that balances relevance and diversity. It introduces welfare-based formulations based on Nash social welfare and p-means, which provide an adaptive, query-based balance between similarity and diversity. The effectiveness of these formulations is evaluated through experiments on several datasets, showing improved diversity while maintaining high relevance. The proposed algorithms, Nash-ANN and p-Mean-ANN, provide efficient solutions with provable guarantees.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**S1:** The paper provides a theoretical foundation by leveraging welfare functions from mathematical economics, particularly Nash social welfare, to address the challenge of diversity in NNS.\n\n**S2:** The paper provides practical and efficient algorithms for solving the proposed welfare-based NNS problems.\n\n**S3:** The paper's approach offers flexibility and adaptability by allowing the trade-off between relevance and diversity to be controlled through the parameter p in the p-mean welfare function. This allows practitioners to tailor the search results to specific task requirements, making the proposed methods versatile for different applications and user preferences.", "weaknesses": "**W1:** The proposed algorithms, both single-attribute and multi-attribute settings, are simple greedy-based algorithms. Although they are easy to implement and provide theoretical guarantees, they require multiple passes of linear scans over the dataset and thus become inefficient on large-scale datasets. Therefore, improving the efficiency of the proposed algorithms using ANN index structures is a critical issue.\n\n**W2:** The proposed query formulation relies on parameter tuning, particularly the smoothing parameter $\\eta$ and the exponent parameter $p$. Finding appropriate values for these parameters for specific queries can be challenging and may require extensive experimentation, which could be a practical limitation when used in practice.\n\n**W3:** The paper primarily compares its methods against a hard-constrained approach and a standard NNS method. In the literature, many other formulations and methods for diversity-aware (as well as fairness-aware) NNS have been proposed. Further comparison with them is necessary to validate the effectiveness of the proposed formulation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YiywQWkXV1", "reviewer": "Reviewer_nv7E", "summary": "The paper investigates variants of ANNs with new constraints on Nash social welfare measures (NSW) and discusses single-attribute and multi-attribute settings. The problems are verified to be intractable -- and efficient algorithms with provable approximation ratios are provided. Benchmark tests have verified the advantages of the proposed algorithms in efficiency and quality.", "questions": "D1. The utilities may have a positive or negative correlation. Will it be ensured that a single optimal solution always exists under the NSW setting? How will the problem compare with other options for multi-criteria queries that seek Pareto-optimality, with dominance but not necessarily optimizing a single value? \n\nD2. Consider providing examples of learning problems that could benefit from algorithmic and theoretical analysis. \n\nD3. NN queries have been extensively studied;  how the proposed solution may be improved with existing techniques such as indexing, sampling, etc, for NaNNS and p-NNS would also be interesting.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "S1. It's an interesting perspective to consider NSW for ANNs for fairness and diversity measures. \nS2. Problems and Algorithms are justified with hardness analysis, matching provable guarantees, and cost analysis. \nS3. Solutions with generality on oracles and ANN algorithms have been experimentally verified.", "weaknesses": "W1. The impact of correlated or contradictory utilities may warrant discussion. \n\nW2. The discussion on connecting the solution to machine learning/representation learning could be discussed. Examples of other ML issues, or real-world scenarios that may benefit from the proposed algorithms, can be provided and tested.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GJnlSGmmGs", "reviewer": "Reviewer_2kxy", "summary": "This paper introduces a framework for incorporating diversity into Nearest Neighbor Search (NNS) by drawing on welfare theory from mathematical economics. Traditional NNS methods mainly focus on maximizing relevance, measured by similarity between a query and data points, while in more recent approaches, diversity requirements are specified using constraints. The main difference of the approach in the paper is that welfare requirements are proposed using welfare-based objectives grounded in Nash Social Welfare. More specifically, attributes of data points (such as color, brand, or seller) are modeled as “agents” in an economic system, where each agent’s utility depends on how well its associated attribute is represented among the selected neighbors. The collective welfare of the result set is then measured using a welfare function, such as the geometric mean in the case of NSW. Empirical evaluations on real and synthetic datasets provide evidence that the approach may have practical applications.", "questions": "No questions.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The main strength is that the chosen approach enforces fairness (diversity across attributes) without requiring ad hoc parameters or fixed quotas, and it adapts to the intent expressed in each query—for example, selecting more homogeneous results when the query is specific and more diverse ones when it is broad.", "weaknesses": "The main weakness of the paper is the presentation. The introduction is way too long. Key justifications of correctness are totally relegated to the appendix (all proofs of theorems). Additionally, currently very basic information such as the very formal definition of diversity being used by the authors is not explicitly highlighted. My recommendation is to \n\n1) Shorten the introduction significantly to end at page 2. An introduction is usually expected to provide a brief summary of the results, a brief discussion of the main applications and appropriate connections with related work. \n\n2) Provide formal definitions in such a way that the newly introduced concepts are highlighted. This makes the paper much easier to read because it clearly separates your original contribution from contributions from the literature. Since you are proposing a new way of quantifying diversity I would expect something like \"Below we define our main notion of diversity...\" or something similar and then a clear statement \"Definition X (Diversity Mesure)\". \n\nWith saved space, move some key insights necessary to prove the theorems to the main body of the paper. Currently all arguments are relegated to the appendix. \n\nIn summary, In my opinion, the current organisation of the paper is suboptimal and makes the evaluation of the contributions of the paper more difficult than necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AvOM3zPzo4", "reviewer": "Reviewer_jBed", "summary": "The paper proposes a new problem setting and algorithms for the problem of similarity search with diversity. An interesting formulation is given where similarity and diversity are combined in one objective. The objective is tunable so as to cover some extreme cases: only relevance, only diversity, and mixing the two using hyperparameters. Diversity is measured with respect to a set of predefined attributes. The paper makes a distinction when an item has a single attribute and when it has many attributes. In the former case an exact algorithm is given. In the latter case the problem is shown to be NP-hard and the greedy method is shown to give a (1-1/e) approximation. Also approximate similarity search can be incorporate to trade efficiency with solution quality.", "questions": "Please answer the points mentioned above. Additionally, I noticed that the author(s) use the terms \"diversity\" and \"fairness\" almost interchangeably. I would like to know the views of the author(s) on this aspect.", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "S1. The problem formulation is quite elegant, providing a way to introduce diversity into the classic similarity search problem.\nS2. Rigorous analysis and strong theoretical results. \nS3. Good motivation and discussion.\nS4. Thorough experiments, evaluating different aspects of the problem setting and the algorithms.", "weaknesses": "W1. The paper contains lots of discussion and motivation. On the one hand this is a strength, on the other hand, it gets quite repetitive and tiring. I would prefer a shorter discussion, avoiding excessive repetition, and presenting more technical results in the main paper instead of the appendix.\nW2. In the intro, the use of geometric mean is motivated by the argument that the geometric mean is larger than the min value of an item and smaller than the arithmetic mean. This fact alone is not a strong motivation, as the fact that the values are different does not necessarily imply that the solutions of the respective problems will be different. \nW3. The formulation is elegant, however, it needs to assume the presence of attributes, which might not always be the case. Another simpler notion of diversity, not covered by the setting of the paper, can be defined by employing the same similarity function used to compare the query with the data items. Here, we would require k items that are similar enough to the query but not similar to each other.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)