A Dense Subset Index for Collective Query Coverage
Authors: Kartik Nair
Pritish Chakraborty
Atharva Abhijit Tambat
Indradyumna Roy
Soumen Chakrabarti
Anirban Dasgupta
Abir De
Venue: ICLR 2026 Poster (2026)
Keywords: collective retrieval
subset search
submodular functions
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: DISCo casts retrieval as submodular coverage to enable scalable and collaborative subset search.

Abstract: In traditional information retrieval, corpus items compete with each other to occupy top ranks in response to a query.  In contrast, in many recent retrieval scenarios associated with complex, multi-hop question answering or text-to-SQL, items are not self-complete: they must instead collaborate, i.e., information from multiple items must be combined to respond to the query. In the context of modern dense retrieval, this need translates into finding a small collection of corpus items whose contextual word vectors collectively cover the contextual word vectors of the query. The central challenge is to retrieve a near-optimal collection of covering items in time that is sublinear in corpus size. By establishing coverage as a submodular objective, we enable successive dense index probes to quickly assemble an item collection that achieves near-optimal coverage.  Successive query vectors are iteratively `edited', and the dense index is built using random projections of a novel, lifted dense vector space. Beyond rigorous theoretical guarantees, we report on a scalable implementation of this new form of vector database. Extensive experiments establish the empirical success of DISCo, in terms of the best coverage vs. query latency tradeoffs.

Published as a conference paper at ICLR 2026
A DENSE SUBSET INDEX FOR COLLECTIVE QUERY COVERAGE
Kartik Nair Pritish Chakraborty', Atharva Tambat', Indradyumna Roy', Soumen Chakrabarti', Anirban Dasgupta", Abir De 'ITT Bombay, "Camegie Mellon University, 3ITT Gandhinagar
(pritish, atha rvatambat, indraroyl 5, soumen, abi r0cce.. iitb.ac.in ksnai rêcs. cmu. edu, ani rbandgē att.i.............
ABSTRACT
In traditional information retrieval (IR), corpus items compete with each other to occupy top ranks in response a query. In contrast, in many recent retrieval scenarios such as multi-hop question answering (QA), table QA, or text-toSSLL, items are not self-complete: they must instead collaborate, i.c., information from multiple items must be combined to respond to the query. In the context of modern dense retrieval, this need translates into finding a small collection of corpus items whose contextual word vectors collectively cover the contextual word vectors of the query. The central challenge is to retrieve near-optimal collection of covering items in time that is sublinear in corpus size. By establishing coverage modular objective, we enable successive dense index probes to quickly assemble item collection that achieves near-optimal coverage. Successive query vectors are iteratively 'edited' to account for current coverage, and the dense index is built using random projections of novel, lifted dense vector space. Beyond rigorous theoretical guarantees, we report on scalable implementation of this new form vector database. Extensive experiments establish the empirical success of our method, in terms of the best coverage vs. query latency tradeoff's. Code can be found http:///gttubbboooomscclleeennnn
sub-
INTRODUCTION
In traditional information retrieval (IR), the relevance score of an item (passage or document), given a query, computed independent of other items (Manning et al., 2008), and top- K items presented. The underlying assumption is that relevant item is self-complete, and can satisfy the information need by itself. Therefore, different items are alternatives or competitors. The basic premise that items competitors is invalid for many modern retrieval applications. In multi-hop question answering (QA) setting (Yang et al., 2018), given the query "Which computer scientist from Cla- mart was an editor Algorithmica?" the following Wikipedia passages collaboratively provide the answer competitive comparison of their relevance scores against each other is pointless.
Mohammad T. Hajiaghayi, Computer scientist at the University of Maryland, was recently chosen to serve as editor-in-chief of Algorithmica Algorithmica: Editor's ss foreword; Bernard Chazelle. This special issue of Algorithmica devoted to computational geometry.
Bernard Chazelle: Bernard Chazelle is a French computer scientist. Chazelle was born in Clamart.
Crucially, there may be no single passage with both Clamart and Algorithmica in Thus, iso- lated ranking can mislead (first passage), and reasoning over item subsets is essential for full query coverage. Similar challenges arise knowledge graph QA (Kosten et al., 2023), table QA (Chen et al., 2021; Zhao et al., 2022b; Chen et al., 2025b), and schema retrieval for text-to-SQL. (Li et al., 2023; Lei et al., 2025; Chen et al., 2025a), where evidence spans multiple corpus items. In all these applications, relevance score must be associated with an item subset. not individual items. Imple- mentations often use off-the-shelf vector databases with per-item scoring functions with an inflated
Work done while IIT Bombay

---

Published as a conference paper at ICLR 2026
K, hoping to recall a superset of the corpus items needed, then filter away the rest. This two-stage approach can fall short because of two related reasons: top-scoring items (e.g., multiple biographies of Chazelle) within the budget of K may be redundant, and yet fail to cover all aspects of the query.
Importance of collective query coverage These limitations point to a central lesson: beyond relevance of individual corpus items, retriever should promote item subsets that collectively cover the query. Our goal is to design and implement an efficient algorithm to achieve this end.
Our contributions Given the recent success of dense retrieval (Zhao et al., 2022a) and its use with language models (Lewis et al., 2021), a new formulation for collective first-stage retrieval is crucial, along with scalable algorithm and an implementation recipe of this new form of a vector database. We introduce advances on all three fronts.
Collective retrieval vector bag coverage: We model the query and each corpus item sub- set of a universe of atoms (e.g., words from a vocabulary), mapped into bags of dense embedding vectors via contextual encoder (Reimers al., 2019; Lee et al., 2019). Then, we compute the score of a subset S of items by measuring the extent to which each atom vector q E Q is 'covered' by some atom vector in {X.: : c E S}. This allows us to represent the collective retrieval prob- lem as maximization of facility-location (Cornuejols et al., 1977) style coverage objective, which evaluates the extent of query coverage achieved by the selected subset. Our proposal generalizes Chamfer based MaxSim score (Butt et al., 1998; Khattab et al., 2020; Santhanam et al., 2021; 2022) and is monotone and submodular. As a result, a greedy algorithm -where each iteration adds the document with maximum marginal gain-enjoys an approximation guarantee, while avoiding exponential complexity.
Marginal gain maximization viewed as retrieval: Direct evaluation of marginal gains over all documents infeasible for large corpora, as it scales linearly with corpus size at each selection round. We view this problem as classic retrieval challenge, albeit with a more complex objective: find the item with the highest relevance score, defined as the marginal gain.
ANN retrieval using marginal gain approximation: Efficient retrieval requires fast indexed ac- cess of the corpus items. However, the marginal gain is not directly amenable to indexing the corpus items in a manner that allows sublinear- -imeearr-imeeeeee access to items with the largest marginal utility. To get past this blocker, we first propose a novel 'lifted' or augmented vector representation of query and corpus atoms. Specifically, we encode the evolving coverage of the current set S at each iteration into an augmented query representation, while corpus embeddings remain static. This expresses the marginal gain as sum of hinge functions over dot products of the 'lifted" representations, which, however, still remains difficult to index. Then we design a novel random projection of the lifted representations, yielding form that is finally amenable to indexing. We give an end-to-end proba- bilistic approximation guarantee of the whole method, which we call DISCo (Dense Index for Set Coverage). (Here "dense" means the embedding vectors are dense and not sparse, e.g., in discrete token space.)
Implementation and experiments: We implement DISCO multi vector dense retrieval ar- chitecture optimized for I/O and computational efficiency, and balancing query latency against sub- set selection quality. Experiments across standard benchmarks demonstrate that DISCo achieves superior query coverage at a given rank, with significantly better dhency--uality tradeoffs- exceeding 100x speedups over greedy baselines.
2 PRELIMINARIES
Notation We define [N] = [l,.... NY. and [++ = max (:0) as the ReLU or hinge function. Given a vocabulary of atoms (which can be words, tokens, or other elementary components) V. A query is modeled as a set or sequence of atoms (qI...., qas) C yM Similarly, we write a corpus item (Z1...., IL)
V². We write q. E Rd and T. E R as the contextual dense embeddings vectors of q. and x. If queries and items are sets of atoms, we can convert them to sets of vectors, one per atom, using set transformer (Lee et al., 2019). If queries and items are sequences, a transformer- based language model (Reimers et al., 2019) can convert them to sets of vectors, one per atom. Contextualization lets us represent the query as set of dense embeddings Q = {qI,.... gM J. and similarly the corpus item as X = { { .r.). corpus items C- = [N]. we write X, to denote one corpus item, indexed with c E C. Throughout, we assume ||g|| = | for all q E Q and X.
Given the indices of the
2

---

Published as a conference paper at ICLR 2026
Monotonicity and submodularity Given the set of corpus items {X. C}. we consider query dependent set function F (): :2 + R. For a subset S C C, we denote the marginal gain of beyond S as F(c| S. Q)
Q) F(S, Q). Given query Q, the function F( Q) called monotone F(c S, Q) 2 0 whenever C C and c E S: and, F is called submodular F(c) (S, Q) 2 F(c|T,Q Q) for S, T c and C (Edmonds, 1970).
MaxSim (or Chamfer) score (Khattab et al., 2020; Santhanam et al., 2021; 2022; Dhulipala al.. 2024) MaxSim(Q. Q, X) is a relevance score between query Q and a single document X. Informally. it measures the extent to which a corpus item X "covers' the atoms/words of query Q- For each atom vector q E Q, MaxSim identifies the most similar atom vector in X, then aggregates these maximum similarities across all query atoms. Formally,
MaxSim X) Eqeq max q
Note that multiple query atoms may be covered by single atom in a corpus item. The distance analogue of this similarity is the well-known Chamfer distance (Borgefors, 1988; Butt et al., 1998; Ma et al., 2010; Feng et al., 2025).
Independent top- K retrieval Current late-interaction retrievers, such as ColBERT (Khattab et al., 2020) and its variants (Santhanam al., 2021; 2022), rank documents independently using the MaxSim score (1). Retrieving the top- K items under this scoring is equivalent to solving the opti- mization problem: maxscc.]s] EeEs MaxSim (Q, X2). which simply selects the K documents with the largest individual MaxSim scores. In other words, this optimization reduces to indepen- dently scoring all documents and returning the highest scorers, without accounting for redundancy or interaction among the selected items.
To support efficient search for top-K independent items, ColBERT and its variants design index- ing and pruming techniques tailored to MaxSim. In particular, they employ an inverted file index (IVF) (Douze et al., 2024), where atom/word vectors æ E X. from all corpus item are clustered into centroids. At query time, for each query atom/word vector q Q, the index retrieves candidate corpus items associated with nearby centroids, followed by successive filtering and pruning stages that approximate the final MaxSim score while maintaining efficiency.
Limitations of top-K retrieval for complex queries The top-K K retrieval problem, discussed above, seeks K corpus items from C such that each item individually covers the query Q, indepen- dent of any other item in the top-K K list. However, for a class of complex queries, this approach is suboptimal, can be seen from our running example. No single passage may cover all atoms/words in the query, but multiple passages may cover most query atoms/words and contain enough infor- mation answer the question.
Overview of our approach To tackle the above challenges, we avoid retrieving top-K indepen- dent items based on MaxSim score (1). Instead, we design relevance measure based on soft set coverage. which guides the selection of subset S c C, which can collectively cover the query Q, instead of each covering Q independently. Subsequently, we design an indexing and search mechanism, specifically tailored to maximizing this coverage objective.
PROPOSED APPROACH
We design a coverage-based set utility function F(S, Q), guided by the related Facility Location objective (Cornuejols et al., 1977; Mirchandani et al., 1990; Lin et al., 2009). We first present our objective in the context of retrieval and describe the well-known greedy method (Nemhauser al., 1978), which can maximize F by iteratively searching over the entire corpus set (Xe)- Next, we provide an approximation of the marginal gain F(cl S,Q),, which is amenable for indexing and search. Finally, we describe our multivector inverted file index (IVF) and the associated query-time search procedure, both tailored the coverage-based objective.
3.1 COVERAGE MAXIMIZATION
Objective Let (Xe E C} be a large collection of corpus items. We seek maximize coverage objective function F(S, Q), which quantifies how well the set S collectively covers the atom em- beddings q E Q. Given a query Q, for each atom q E Q, we first compute the maximum similarity q attains with any atom across the corpus items in S and then aggregate over all q Q. Formally,
3

---

Published as a conference paper at ICLR 2026
write set utility F(S, Q) and coverage-based retrieval objective as:
F(S.Q) = Σ max X
q TTa; a;;
maximiie F(S, Q) such that [S| S K. SCe
(2)
QEQ
In the optimization for top-K retrieval task, viz., maxscciss= =K Eees MaxSim (Q, X.), it is the outer sum, independently carried over S, which can introduce redundancy, potentially returning
multiple documents that cover the same query atom/s. In contrast, F(S, Q) (2) does not give additive credit for multiple document items redundantly covering the same query atom.
Monotonicity, submodularity and greedy maximization From the extensive literature on submodular functions (Cornuejols et al., 1977; Lin et al., 2009; Krause et al., 2014), is easy to establish that F(S, Q) is monotone and submodular. Therefore, we can obtain an approximate solution of the maximization prob- lem (2), using a greedy algorithm (Nemhauser et al., 1978). Having computed a set Sk at iteration k < K, this algorithm iteratively selects the item having index с that has the highest marginal gain F(c) S, Q) at each step (Algorithm 1). While not guaranteed to find the true optimal set S" = arg maasses F(S, Q), it is guaranteed to find solution that within constant factor of (1 - 1/e) x 63% of the optimal solution. In practice, it is frequently found much closer to optimal.
Algorithm Greedy algorithm to solve (2).
1: Initialize So 0
2: for k = l.....KK K do
3: Ca = arg Sa. F(c] Se-1, Q)
4: Sa S
5: return Sk
Bottlenecks with greedy algorithm Despite its theoretical appeal, the greedy algorithm is pro- hibitively expensive for large corpora, it requires @(C)) evaluations of the marginal gain T
F(X ((x1)=1,,Q) Q) per iteration (line 3 of Algorithm 1). For the MS-MARCO corpus (IC) ~ 8.8 mil- lion passages), selecting just K 10 corpus items requires 88 million marginal gain computations. Even at a speed of one millisecond per computation, this retrieval process would take over 24 hours for single query, which is prohibitive.
3.2 BRIEF DISCUSSION OF RELATED WORK
Existing variants of greedy selection For atomic (i.e., non-embedded) items, the scalabil- ity of set cover has been extensively studied (Cormode et al., 2010). Existing alternatives such as Lazy Greedy (Minoux, 2005), Stochastic Greedy (Mirzasoleiman et al., 2015), and Lazier-than-lazy Greedy (Mirzasoleiman et al., 2015) offer partial efficiency gains. Lazy Greedy reduces the number of evaluations by maintaining a heap but still relies on exhaustive scoring. Stochastic Greedy and sazier-than-lazy Greedy prune the corpus uniformly at random in each it- eration, in a query-agnostic manner that degrades utility. As result, these works do not provide a desirable trade off between efficiency and utility.
Diversity in information retrieval Submodular set reward functions have been proposed in the In- formation Retrieval community since at least 1998, motivated by diversity (Bennett et al., 2008) and subtopic coverage (Zhai et al., 2003). These objectives are usually implemented as reranking stage, after the small subset of candidates has already been selected using a scalable first-stage retriever. For reranking, max marginal relevance (Carbonell et al., 1998), multi-armed bandits (Radlinski et al., 2008), determinantal point processes (Kulesza, 2012a; Chen et al., 2017), query reformulation (San- tos et al., 2010), etc., are used. Hence, these approaches focus scoring function computation at the reranking stage. These reranking efforts are vulnerable to loss of recall in the first-stage. We contrast these approaches with ours, and provide further discussion of related work in Appendix E.
3.3 RETRIEVAL-ORIENT APPROXIMATION OF MARGINAL GAIN
Marginal gain maximization from the viewpoint of ANN retrieval To address the above bot- tlenecks, need method to efficiently retrieve the candidates with high marginal gain, in query dependent manner. In line with traditional IR, we view the task of maximizing the marginal gain as "retrieving the corpus item with the largest relevance score F(c Sx-1. Q)" each iteration k. This requires us to design a retrieval model tailored to the relevance score F(c Sk-1. Q), along with compatible indexing and search techniques. However, there two key challenges:
(1) Unlike dot droduct or cosine similarity, the marginal gain F(c S Q) bears a complex re- lationship between Q and X., which is not readily supported by standard indexing models.
4

---

Published as a conference paper at ICLR 2026
(2) For each iteration k. the subset S₁ depends heavily on the query Q. This poses a challenge for indexing, which should ideally employ query- ageyssgg,,, one-time preprocessing.
To this end, we approximate the marginal gain F(cl SS, Q). to make it amenable to design ap- proximate nearest neighbor (ANN) retrieval model. We perform this approximation in two steps: (I) We provide alternative representation of F(c S, Q) using the dot products of two augmented vectors, one depending on the query and other on corpus items. (II) We design a method, based on random projections, to build scalable ANN data structure.
Marginal gain computation using vector augmentation We strategically rewrite the marginal gain F(c) S, Q) as follows:!
Proposition 1. Given the coverage objective F(S, Q) defined in Eq. (2), the marginal gain is: P[c|S,Q) =
q x max max q xo WES x'E..
max
xc
QEQ
The above formula reveals that the total marginal gain of a new corpus item e the sum, over all query atom embeddings q E Q, of the new score contribution (q x)) that exceeds the best score already achieved for that atom by the current set S.
Designing indexing and search techniques for any relevance measure requires expressing the score as a similarity between precomputable corpus representations and a query representation that is carpus-agnostic. However, in the second term inside the hinge of Eq. (3), the corpus token em- beddings x' are coupled with S. which itself depends on the query Q through previously se- lected items. To isolate x' from S and Q, reformulate this term follows. We observe that max.es eax q' x' = F(S, q) denotes the set coverage value for a singleton set with atom alone. If we define the augmented representations of the query and corpus tokens
is :- ( (SS, q)] E RR++, a = x;; -1] E R then we express Eq. (3) as a dot product between these two augmented vectors in lifted vector space:
(4)
F(e| (S
Σ
max
(q x FSS, g)
Σ max xEX,
[ x
(5)
#EX.
qEQ
qEQ
Here, we transfer the dependency of F on S into the query and obtain state-dependent representa- tion ds. Consequently, the corpus token representation øg becomes agnostic S and Q.
Random projection for hinge-ANN The last hurdle we face is the non-linearity of the hinge function, [+] in Eq. (5), which prevents direct use of standard ANN retrieval. To address this challenge, we approximate [9g c]+ using dot product of two vectors, obtained by projecting qs and on to random hyperplanes. The key insight is to use randomized feature map that, with high probability, mimics the behavior of the hinge function applied to dot product between two vectors.
Let u, e E Rd+1 be two vectors (e.g., u 9s and = R); and w E Rd+1 be a random vector drawn from standard multivariate normal distribution, i.e., ~ (O, I4+1). We define a feature map +. Rd+1 + (2d++) as follows:
(w) & [u; sign(wTu) u] //2.
(6)
Then, we can express |u TuTer u]4 as follows.
Theorem 2. Given any two vectors u, v E RR let w be a random hyperplane w ~ NN0 I441), and 4w be the transformation defined in Eq. (6). Then, we have the following result:
&w @w(u) (w(v) = [uTv]+ v]+
with probubility p 2 0.5.
(7)
Proof sketch Note that Pw (u) T (w) = uu" TuTo v or 0, based on whether sign(w = sign (w Tv)
or not.
From Charikar (2002), we can show that probability of this condition is p 1
arccoss( u T 1 |-|||
TTe or p = 1 arccos( [ [|
We use the sign of T u to argue that p > 0.5.
While the above relationship holds with p Z 1/2, we can draw more random hyperplanes w, and perform aggregation of (w) o Tw. (v) to obtain more accurate estimate of [u T] This gives us our approximation result as follows.
itd. Theorem 3. Suppose (wi...., [R) be R random hyperplanes with w, N(1,, Ia+1). Given the state-det -eeeeddeenndett representation for each query token qs := [q; F(S,)) q)) and the query agnostic
Proofs of technical results are Appendix
5

---

Published as a conference paper at ICLR 2026
ANNSi-kth approsmmaia
dx.
ANNS1
(es)
ds 4F.. (..((ds) (ds)..... (dx)
neanest naighbor search
65.
ANNS2
33 Sj (es)
Query execution
ANNS3
= 8
(4)
Indaxingg
Preprocess
Corpus (R [C])
& 9,, (Re)..... (Ro)
cussen (f.) ce [q]; B)
cee
controkds O Obe 9.
Posting list for each cluster with
dooument iDs (c)
Index R
Figure 1: DISCo block diagram. Random vectors {w, : P E [R]} are sampled. Corpus items fIe C (C1} mapped to vectors & (á.) for each A sub-index is built for each In it, we cluster (Lw, (t.) c [C]} into B clusters with centroids {orr b [B]]. Each centroid associated with a posting list containing document IDs {c]. Query execution proceeds in K rounds, while the retrieved item set grows from So = Ø to SK as output. Each round executes an approximate nearest neighbor search, labeled ANNSI ANNSK. Each ANNSI: round consults all R indices and chooses the next item e₁ in (CC) time.
representation of each corpus token 2 == [z; - as defined in Eq. (4), let the randomized function Gwin be defined as:
(C
Σ max max Pw, pw.(ās) D ww.
rE(R) wEX.
QEQ
Then, for any & 8, 8 C C and Q {g}, a positive probability 8 > 0 and R log(1Q1/6), will have Gwi. (c (, = Fc S) with probability atleast
I 3]+ Therefore, we draw mul- tiple samples of w, and compute an empirical maxima of the dot product between the projected vectors which approximate [ +. Then obtain the required probability using union bound.
Proof sketch We note that max t Dw. (qs) Tw.
We observe that the number of tokens |Q] < 32 which is common scenario in applications then we need only R = 8 hyperplanes to ensure F'c Q) with probabil- ity at least 1 - 8 = 0.875. If the query were
Algorithm 2 Greedy algorithm based on proposed approximation
I: Initialize So 0. wT. WR ~ N(0 Ia),
that GwaR (c; 8, Q)
2: for k 1.... K do
a = arg max (c;
shorter, say, Q < 16, the success probability would increase to 1 - 8 0.94. (The union bound is likely pessimistic in practice.) Note that the RHS of Eq. (8) closely resembles the MaxSim score in Eq. (I), which is amenable to indexing and search. In the next section, we develop indexing and search methods tailored to Gwi.R
4: S + Uct
5: return Sx
Approximation guarantee In Algorithm 2, we replace the marginal gain in line 3 of Algorithm with our approximation (w Sk Q). In line of Algorithm 2, we obtain an element e such that F(c| S Q) with probability at least 1 6. This algorithm can be shown to enjoy opti- mality guarantee (in expectation) of (1 - 1/c - 8), which is very close to Algorithm 1, even with small value of R = 8 as discussed above.
Theorem 4 (Approximation guarantee of Algorithm 2). Let Sx be the set of K corpus items selected by Algorithm 2, and let S* be the optimal set for F, i.e. S E arg max SISK F(S, Q). Given 8 e (0, 1), if we set the number of random projection vectors 2 l)/()
Ewaa [F(SK, [)5 2 (1 1/e 6) (F(".Q))
3.4 INDEXING AND RETRIEVAL
We complete the presentation of our system, DISCO, by designing an ANN index to implement the search for argmax, Gwi.n (c. S5-1, Q) in every round, building upon the best practices from the ColBERT family of nelti- ANN methods: representing each item set of token embeddings) (Khattab et al., 2020), storing them compactly via centroid-residual en- coding (Santhanam et al., 2021), and accelerating candidate filtering through centroid-first prun-
multivector (a

---

Published as a conference paper at ICLR 2026
ing (Santhanam et al., 2022). However, significant modifications and enhancements are needed to support our collective objective, lifted vector space, mutating queries and multiple projections. A block diagram of DISCo is shown in Figure 1.
Indexing Our indexing step is based on multivector IVF, adapted from Santhanam et al. (2022, PLAID), but tailored to maximizing the relevance score measured in terms of Gw (0, -. Q)- Algorithm summarizes the DISCO indexer. Corpus atom vectors are augmented in step 4, which will support query-dependent, per-round coverage subtraction (- (S, q) in Eq. (5)), while remain- ing query-agnostic. It projection vectors are sampled in step 6. For each projection vector, feature maps ww (2) are computed in step 7. To prepare the IVF index, the feature maps are clustered to obtain a set of centroids in step 9. Each
(.) then represented by its nearest centroid o and a compact residual code A produced by a Quantizer (Santhanam al., 2021; 2022) to reduce the number of bits needed per dimension. For each sample in- dex r [R]. we return (I) the projection vector Wy. (2) cluster centroids (==1
Algorithm DISCO indexnng stage.
1: Input: Corpus embeddings (Xo for E Heecs #hyperplanes R: #clusters B; Quantizer (see text)
2: Output: Inverted index Invind forward index FwdInd centroids {0r,-)m for E [R] 3: (nvind Fwdlld +- Ø Vr
4: Augment: ã <- [æe -1] for all æ E CE
(3) inverted lists Invind and (4) forward index F (w mapping every document c to its sequence of (b" A) codes across
5: for 1 to do
6: Random sample: w, ~ ~NO0 Ia+11
7: Project and prepare postings:
8: 2 {(Ww, (ā), c) f E Xe, E CJ (6)
atoms.
9: Cluster: {o t- kmeans( ww ((v,,(())) (ā)}. B)
Retrieval Algorithm shows how the in-
10:
for each (z,c) E
do
dex prepared thus far is used to respond to
11:
b'+- argming I| 06. (nearest centroid} Quantizer(2= o)
a query. Query processing proceeds in K greedy rounds. In each round, each replica
12:
13:
Insert into indices:
14:
Invind (b) Invind (b*) U {c}
E [R] contributes candidate items (docu-
15:
(wdInn (c) + FwdInd (c) (b" A)
ments). These are merged and pruned. We progressively refine candidates through six pruning stages, employing graded approximations Eq. (8) and ultimately converging toward the "gold standard" Eq. (5). Surviving candidates get their scores more accurately calculated by access- ing their residuals and the cluster centroids. A final reranking is performed using the 'true' scores to select the candidate with the best marginal score for the current round. Then the next round commences. We elaborate on some salient steps of Algorithm below.
16:
return ((w>, 1 Invina FwdInd (r)) )R
-Replica-level coarse filtering: For each round k and each projection r, for each query atom vector q, we compute qs. then the vector & (Âs), and use it to probe InvInd to collect some corpus items. We compute the union of these item candidate sets over all query atoms, providing the roughest approximation to Eq. (8).
Replica-level centroid pruning: To refine the initial candidate pools Cy.o, we assign coarse relevance scores using query-centrov similarities. For each document item e E Cr,o, the forward index (rd provides the atom centroids associated with c, and the score of i re-estimated as shows in step 11. This step moves us one step closer to Eq. (8) by aggregating across query tokens, while still omitting the max over replicas and utilizing centroids rather than the true corpus token embeddings. Following PLAID (Santhanam et al., 2022), centroids with scores below 7 are pruned. Each replica thus retains a refined set C,, of n candidates.
Replica Pooling: We collect all the corpus items in each refined set for each replica into C₁, i.e.,
C. + U Cr,
Fine Fime-grained fitrrninn
The score of each corpus item c Cj refined
Σ max max rE(Mt oEFwdlud(r)
T Pww (qs) o,
QEQ
which pools information from all replicas and approximates Eq. (8) better, while still being centroid- based. The pool is then pruned to retain roughly n/4 candidates, denoted Cg. for the final stage.
Residual scoring: At this stage, we access residuals A from forward indices FwdInd to recon- struct document items and score them more accurately. For each candidate E C2, we obtain set of reconstructed token embeddings T. { = A + o} where (o, A) E FwdInd(")()) serving as an approximation to the original X
7

---

Published as a conference paper at ICLR 2026
The marginal gain of c is refined as Eqeo [ max Pw- [ a. which closely mirrors Eq. (8) while still
Algorithm 4 DISCO query processing steps.
1: Inputs: Query Q, projections WI:R, centroids {our).
indices ((Invnnd Fwd][nd()))] for be re(R
operating compressed rather than full- precision embeddings. The candidates are reranked accordingly, and the top n' items
Hyperparameters т, n, n''
3: Output: Selected subset S - of size K
4: Initialize S. < 0: initialize query embedding qs
retained in C3.
5: for rounds k to K do
Full- Full-prrcision scoring+selectionn is small enough that we can now compute the exact marginal gain to the coverage ob- jective F(c| S. Q) (5) for each surviving E C3. The gain is evaluated using the full atom vectors in Xe, without centroid residual approximations. Item c with the largest gain is accumulated to form Sk from Sk-1. The query representation is up- dated as Ôs < {s in preparation for the next round.
C3
for replicas r = 1 to do
7:
Replica-level coarse filtering ba + argmaxx tw, os., (closest centroid)
8:
Cr 4 Uge In
10:
# Replica-level centroid pruning Pw. (qs) o, for
11:
Compute Σ
max
r DE (FFudIad())()))
every corpus item in filtered set: E Cr.
12:
Discard items with scores <T
13:
Retain top into Cr,1
14:
Replica Pooling: C1 C1+ U
15:
# #Fine-grained filtering
16:
Compute Mqeq max max
Dw, (qs) To,
4 EXPERIMENTS
rE|R] (e
for E C1 and retain top n/4 into C2
We provide a comprehensive evaluation of DISCo using seven real datasets and show that DISCO trades off between accuracy and efficiency better than several baselines, with striking improvements in efficiency. For details, see Appendices H and I.
17:
# Residual scoring
18:
For each c compute T. f A o
where (o, A) (wdInd!") (c)
19:
Compute Cs consisting of top-n' items from
EgeQ max maxa ET, (w. EΛ
20:
Full-precision scoringtselection
21:
Ce f arg max,ecs F(c| S.Q).
Datasets We perform experiments with seven large-scale datasets, viz.
Se t S U (c+)
22:
Update state-dependent query representation @s
(1) MS-Marco, (2) HotpotQA and
23:
return Sx
(3) Fever, from the BEIR (Thakur
et al., 2021) benchmark; and, (4) Pooled, (5) Technology. (6) Writing and (7) Science from the LoTTE (Santhanam et al., 2021) benchmark. Among them, we report results on the first four datasets in the main and rest in Appendix H. Appendix G contains details about these datasets. Since Exact Greedy is prohibitively expensive, we use NFCorpus, relatively smaller dataset from BEIR, to empirically evaluate the correctness of our theoretical results in one experiment.
Baselines We compare DISCO against seven competitive baselines, viz., (1) Exact Greedy (Nembauser al.. 1978), (2) Lazy Greedy (Minoux, 2005), (3) Stochastic Greedy (Mirzasoleiman ct al., 2015). (4) Lazier-than- than-errtta-lazy Greedy (Mirzasoleiman et al., 2015), (5) PLAID (Santhanam et al., 2022), (6) MUVERA (Dhulipala et al., 2024) and (7) WARP (Scheerer et al., 2025) Among these, the first four methods target monotone submodular maximization, while the last three- three-collected collected from the information retrieval (IR) domain-focus on indexing followed by independent top-K re- trieval based on the MaxSim score in Eq. (1).
Evaluation setting, coverage and efficiency Each dataset consists of a query set Q and corpus items C. We compute the contextual word embeddings q and æ for query and corpus atoms/tokens, using bast-base-uneased (Devlin et al., 2018).
Our primary evaluation focus is the attained coverage F(SK, Q), where Sx is the retrieved subset of size K. As motivation, fast ramp-up of coverage at small ranks is critical economize energy on ALM-based downstream reasoners and response generators. We measure coverage averaged over queries, Fx k = EQee F(Sx. Q)/12) Moreover, given method M and K, we measure the efficiency of M as Exxect Greedy. 11/ tM,K, where t Gready, 110 is the per-query time for Exact Greedy to retrieve S10, and t is the per-query retrieval time of M to retrieve K items. We expect inverse relationship between coverage and efficiency, and wish to identify methods with the best tradeoff.
Traditional MAP, MRR, NDCG In some datasets such HotpotQA, test gold sets with |Sgota 2 are identified. All these items are needed to infer the response. In such cases, we can directly study the ranks at which these gold items appear. To condense these ranks to single number, we can look
8

---

Published as a conference paper at ICLR 2026
DISCo
Exact Greedy MUVERA
Lazy Greedy WARP
Stochastic Greedy
Lazier-than-lazy Greedy
PLAID
Avg F(Sx:
28
25
25
26
20
24
20
20
10
10a 10
10
10a
10
10
10a
10a
10
10a
10
Efficiency
Efficiency
Efficiency
Efficiency +
(a) MS-Marco
(b) HotporQA
(c) Fever
(d) Pooled
Figure 2: Trade off between efficiency and average coverage objective of DISCO and state-of-the- art baselines on four datasets: (a) MS-Marco, (b) HotporQA, (c) Fever, and (d) Pooled. DISCO
achieves the best trade-off, matching greedy baselines in coverage while being impressively faster (> 100X in some cases), while consistently outperforming IR baselines in terms of average coverage objective. Efficiency is in log-scale. Upper right corner is the best quadrant.
at the last rank, or, for more robust aggregation over queries, use recall-sensitive measure such as MAP. MRR is inappropriate, because it cares only about the first relevant rank, and, for larger ggotal, even NDCG will not care about recalling all gold items. Additional performance measures are discussed Appendix I.1.
In all experiments, we choose K = 10. Both Stochastic Greedy and Lazier-than-lazy Greedy restrict their search on a subset C' of corpus items selected uniformly at random, with |C"| |C] log(1/e")) We chose e' = 0.5. More details are in Table 3, Figure 4 and Appendix H.7.
4.1 RESULTS
Trade-off between coverage and efficiency Figure 2 shows the trade-off between average cover- age objective FR and the efficiency with respect to Exact Greedy, obtained by varying the subset size K. We make the following observations: (1) DISCO trades off between the mean coverage value k and the average query time more effectively than all the baselines. (2) DISCo is signif- icantly more efficient than the variants of the greedy algorithm, viz., Exact Greedy, Lazy Greedy, Stochastic Greedy and Lazier tazy Greedy. In the MS-Marea dataset, DISCo at least 100x faster than these variants. (3) IR baselines, egg., PLAID, MUVERA and WARP are highly efficient, owing to their indexing and scalable search pipeline. PLAID shows the best performance among these IR methods, due to their multivector approach, while MUVERA performs the worst with their single vector approach. (4) Stochastic Greedy and Lazier-than than-lazy Greedy show poor trade-off due to query agnostic randomized pruning.
DISCO
Exact Geeedy MUVERA
Lazy Groady
Stochastic Greedy
Lanier tham Jazy Greedy
WARP
PLAID
Method
Error(F (F()
MAP (f)
Number of Queries
2000
Exact Greedy
0.69
0.83
Lazy Greedy
0.69
0.83
Stochastic Greedy
2.77
0.19
azzier-than-ee Greedy
3.09
0.14
1000
PLAID
1.30
0.81
MUVERA
3.55
0.49
WARP
1.51
0.77
5
DISCO
0.68
0.84
Rank of Last Relevant Ttem Retrieved Figure 4: Histogram of the rank of the last ([Syaal- th) true relevant item, retrieved for queries in HotpoiQA dataset. DISCo retrieves almost all items within 2 (sometimes 3) rounds, similar to de- terministic greedy variants.
Table 3: Comparison of DISCo with baselines on
gold labels of HotpotQA ([Sgoua = 2), in terms of
Error( F) = Eoso. (Sppauus Q) F(5K, Q) and Mean Average Precision (MAP). Green (Blue) shows the (second) best performer.
with
Does F(S,Q) reward Sgola? We evaluate the suitability of the coverage objective F(S,Q) in relation to the annotated ground-truth relevant items Sgold in HotpotQA. In the first eval- uation, we report on two metrics: (1) Error(F)) This is defined as the average deviation between the coverages on the gold set Syold and the retrieved set Sx with K = 2, i.e, Error(F) Ege [F Q) F(S2, Q). (2) Mean Average Precision (MAP): We com- pute MAP ranked list of retrieved items, using rank as the selection order for greedy methods and MaxSim ranks for IR basclines. In Table 3, we summarize the results. We make the following observations: (1) DISCO achieves the lowest Error F) indicating that the coverage of the retrieved

---

Published as a conference paper at ICLR 2026
sets closely approximates that of the gold set. It also achieves the highest MAP, indicating strong alignment of its computed subset with the gold annotations. While these numbers are comparable to Exact Greedy and Lazy Greedy, the efficiency of DISCo is significantly better (see: Figure 2). (2) Stochastic Greedy and Lazier-than-lazy Greedy perform worst among all methods, owing to their query-agnoste random pruning strategy.
In the second evaluation, we analyze the ranking of the last relevant item across methods by plotting histogram of the position of the last gold retrieved item. A low value of the rank is better as implies that the all items in Sgold is retrieved within a small cutoff value of K. Figure 4 shows the results: DISCo more frequently retrieves all the gold documents within the top 2-3 positions, similar to Exact Greedy and Lazy Greedy, whereas IR methods such as MUVERA, PLAID, and WARP more frequently place the last relevant item at lower ranks.
Exarl Grewdy
#sampho R=1
thommphow R=2
DESCo
Late Pool, u 10
Latn Pool ar 20
gaamples Re3
#sumples Red
#ramples RmG
Late Pool,
Late Pool,
Avg F(S
25
Avg F(SK
28
25
24
24
20
23
22
2
4
6
10
2
4
6
8
10
500
1000
250
500
750
K
Efficiency
Efficiency
Figure 5: Coverage with approximate marginal gain.
Figure 6: Ablation study: Early vs Late pooling. (left: MS-Marco, right: Pooled)
(left: NFCorpus, right: Writing)
Quality of approximate marginal gain Here, we assess the quality of Ww,.nc,, S, Q). our pro- posed approximation of the marginal gain F(e| SS, () in Eq. (8). To this aim, we run Algorithm 2 and compare the corresponding coverage values against that of Exact Greedy algorithm. Figure summarizes the results for different numbers of hyperplanes R. We make the following observations. (1) Approximation quality improves with larger values of R. pushing the coverage trajectory upward. (2) Even with smaller value of R. 5. the coverage from Gwi. matches with Exact Greedy.
Ablation on early vs late pooling A natural question whether the replica-level early pooling in Step 14 of Algorithm 4 is all necessary. An easier alternative of DISCo is late pooling. Here, we process R projected queries @w, (Îs) independently, each returning its own top-n' candidates. These are then merged and reranked to retrieve the item with the highest marginal gain, bypass- ing the intermediate fine-grained filtering stage. Figure 6 summarizes the results. Compared to late pooling, our current early pooling approach is superior both in terms of retrieval efficiency and the value of the final coverage objective. Early pooling approximates the pooled objective ( T more faithfully, ensuring that the candidate set bet- ter aligns with the marginal gains defined by Eq. (8). This early aggregation allows the method to discard low-scoring candidates earlier, reducing unnecessary final score computations while retain- ing documents that contribute most to the true coverage objective.
Egeo max
5 CONCLUSION
Our work introduces a novel framework for collective retrieval, which explicitly seeks to optimize for coverage of query atom vectors by subsets of corpus items. Coverage maximization can be solved in greedy algorithm. However, here, marginal gain computation across the entire corpus is compu- tationally expensive. To tackle this, at each iteration, we construct augmented vector representations for both query and corpus items. Then, we apply a randomized projection method and represent the marginal gain in amenable form for ANN retrieval. This allows us to develop a practical, scalable method for sublinear-time retrieval of high-coverage item subsets. Experiments demonstrate that our method trades off between coverage and efficiency more effectively than the baselines. Future work could explore alternative similarity functions, richer representations of query-document intcractions, adaptive subset selection strategies, weighted coverage, and dynamic updates.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
This work raises no specific ethical concerns. We use only publicly available datasets under their respective licenses and introduce human-subject data. Our contribution is an algorithmic method that improves collective-coverac retrieval over open-source corpora.
REPRODUCIBILITY STATEMENT
We have ensured that our results are fully reproducible. We release: (1) complete source code; (2) configuration files specifying all hyperparameters (e.g.. number of random hyperplanes R. subset size K, pruning thresholds IVF cluster count B, quantizer settings, maximum candidates per stage, and reranking cutoffs);; (3) scripts to build indices; (4) detailed environment spees; (5) random seeds; and (6) scripts to generate all plots. We provide detailed derivations and complete proofs of all theoretical results in the appendix.
REFERENCES
Paul N. Bennett, Ben Carterette, Olivier Chapelle, and Thorsten Joachims. Beyond binary relevance: preferences, diversity, and set-level judgments. SIGIR Forum, 42(2):53-58, November 2008. ISSN 0163-5840. doi: (9.11455148055661488888 1480506 1480516.
URL https: pestps://l / htt//dii.orrggg or./10.1145///
Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang, Semantic parsing Freebase from question-answer pairs. In David Yarowsky, Timothy Baldwin, Anna Korhonen, Karen Livescu, and Steven Bethard (eds.), Proceedings of the 2013 Conference Empirical Methods in Natural Language Processing, pp. 1533-1544, Seattle, Washington, USA, October 2013. Association for Computational Linguistics. URL https: http:///aaaaahooo.....o org D1////1311111111
Gunilla Borgefors. Hicrarchical chamfer matching: A parametric edge matching algorithm. IEEE Transactions Pattern Analysis and Machine Intelligence, 10(6):849-865, 1988.
Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social influ- in nearly optimal time. In SODA, pp. 946-957, 00669957222 2014.
M Akmal Butt and Petros Maragos. Optimum design chamfer distance transforms. IEEE Trans- actions Image Processing, 7(10):1477-1484 1998.
Stefan Büttcher, Charles LAA Clarke, and Gordon Cormack. Implementing and evaluating search engines, 2016.
Jaime Carbonell and Jade Goldstein. The use of mmr, diversity-based 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. ACM, 1998. URL http: ccttsseereeeeeeeeeee ist psu. eesueedu/ce htttt//arbceee1199 1ww.is.uuee..... html.
Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the Thiry- Fourth Annual ACM Symposium on Theory of Computing, STOC '02, pp. 388,388, New York, NY, USA, 2002. Association for Computing Machinery. ISBN 1581 134959, doi: 10.1145/509907.. 509999. URL https: /tt.//oiiio/////// wwwpi.oog/o.... 1ttog///..111//0011000 /0044//5599... 509965.
Laming Chen, Guoxin Zhang, and Hanning Zhou. Improving the diversity of top-n recoommeecmniiiiion via determinantal point process. CoRR, abs/1709.051355, 2017. URL httpt:tpp/aaii....
abs/ 0bss/100 /19.9 05135.
Peter Baile Chen, Fabian Wenz, Yi Zhang, Devin Yang, Justin Choi, Nesime Tatbul, Michael Ca- farella, Çağatay Demiralp, and Michael Stonebraker. Beaver: An enterprise benchmark for text- to-sql, 2025a. URL hwtph:tp/////...t...tt
:/appsis///rxivv.// /aaxivv..v.v. org/ htt//bbs/4409 02038.
Peter Baile Chen, Yi Zhang, and Dan Roth. Is table retrieval solved problem? exploring join-aware multi-table retrieval. In ACL Conference, 2025b. URL https: /ttp///rxvvv/////////////////vvv orgooorggoo abs/ /240//240 2404. 09889.
11

---

Published as a conference paper at ICLR 2026
Wenhu Chen, Ming- tion answering over tables and text, 2021. URL https: /tt::///xxxii arriv. org/ htt:/bb//200000 10439.
Ming-Wei Wei Chang, Eva Schlinger, William Wang. and William W. Cohen. Open ques-
Zhiyu Chen, Wenhu Chen, Charese Smiley, Sameena Shah, lana Borova, Dylan Langdon, Reema Moussa, Matt Beane, Ting-Hao Huang, Bryan Routledge, and William Yang Wang. FinQA: A dataset of numerical reasoning over financial data. In EMNLP 2021, 2022. URL https:
/ //aaxii..rg/aas///........a /2109. 00122.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. International Conference on Learning Representations (ICLR), 2020.
Graham Cormode, Howard Karloff, and Anthony Wirth. Set cover algorithms for very large datasets. In Proceedings of the 19th ACM International Conference Information and Knowl- edge Management, CIKM '10, pp. 479-488, New York, NY, USA, 2010. Association for Com- puting Machinery. ISBN 978 1500300995 doi: 10.1145//871437.1877500 URL https:
// //doi.org//00 10. 11
Gerard Cornuejols, Marshall Fisher, and George L Nemhauser. On the uncapacitated location prob- lem. In Annals of Discrete Mathematics, volume pp. 163-177. Elsevier, 1977.
Jacob Devlin, Ming-Wes Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 1800048000 2018.
Laxman Dhulipala, Majid Hadian, Rajesh Jayaram, Jason Lee, and Vahab Mirrokni. Muvera: multi- vector retrieval via fixed dimensional encodings. arXiv preprint arXiv:2405. 2024.
Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre- Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library. arXiv preprint arXiv:2401.08288/ 2024.
Mohnish Dubey, Debayan Banerjee, Debanjan Chaudhuri, and Jens Lehmann. EARL: Joint entity and relation linking for question answering over knowledge graphs, 2018 URL https:// arxiv. org/ abs / 11011.1111 03825.
S Durga, Rishabh Iyer, Ganesh Ramakrishnan, and Abir De. Training data subset selection for gression with controlled generalization error. In International Conference on Machine Learning, pp. 9202 9212. PMLR, 2021.
Jack Edmonds. Submodular functions, matroids, and certain polyhedra, combinatorial structures and their applications, guy, h. hanani, n. sauer, and j. schonheim, eds. New York, pp. 69-87, 1970.
Michael D Ekstrand, Graham McDonald, Amifa Raj, and Isaac Johnson. Overview of the trec 2022 fair ranking track. arXiv preprint arXiv:2300.00555. 2023.
Dan Feldman. Core-sets: Updated survey. In Sampling Techniques for Supervised or Unsupervised Tasks, pp. 23-44. Springer, 2020.
Ying Feng and Piotr Indyk. Even faster algorithm for the chamfer distance. arXiv preprint arXiv:2505.08957, 2025.
Thibault Formal, Benjamin Piwowarski, and Stéphane Clinchant. Splade: Sparse lexical and pansion model for first stage ranking. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development Information Retrieval, pp. 2288 2292, 2021.
Satoru Fujishige. Submodular functions and optimization, volume 58, Elsevier, 2005.
Jennifer A Gillenwater, Alex Kulesza, Emily Fox, and Ben Taskar. Expectation-maxiiizatioo for learning determinantal point processes. Advances in Neural Information Processing Systems, 27: 3149-3157, 2014.
Clinton Gormley and Zachary Tong. Elasticsearch: the definitive guide: a distributed real-time search and analytics engine." O' ReRllly Media, Inc.", 2015.
12

---

Published as a conference paper at ICLR 2026
Otis Gospodnetic, Erik Hatcher, and Michael McCandless, Lucene in action. Simon and Schuster, 2010.
Alkis Gotovos, Hamed Hassani, and Andreas Krause. Sampling from probabilistic submod- ular models. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL https: htttps://proceeedngge. neurips httpc//ppeeeeeee/ppeeeeeeeeeeeee ftt.es/pappee//1s//// file/
112--a .ddf.
Amit Goyal, Wei Lu, and Laks V.S. Lakshmanan. CELF++: Optimizing the greedy algorithm for influence maximization in social networks. In WWW (Companion Volume), pp. 47-48, 2011.
Jiafeng Guo, Yinqiong Cai, Yixing Fan, Fei Sun, Ruqing Zhang, and Xueqi Cheng. Semantic models for the first-stage retrieval: A comprehensive review. ACM Trans. Inf. Syst., 40(4), March 2022. ISSN 1046-8188, doi: 10.1145/3486250.
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming-Wei Chang. REALM: Retrieval- augmented language model pre-training, 2020. URL httppp//aaxxv..r.ggg. abs/20b2...0.
08909.
Sariel Har-Peled and Soham Mazumdar. coresets for k-means and k-median clustering. In Proceedings of the shirty-sixth annual ACM symposium Theory of computing, pp. 291-300, 2004.
Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. Constructing multi-hop qa dataset for comprehensive evaluation of reasoning steps. arXiv preprint arXiv:20/1.01 1.01060, 2020.
Rishabh lyer and Jeffrey Bilmes. Submodular Point Processes with Applications to Machine learn- ing. In Guy Lebanon and S. V. N. Vishwanathan (eds.), Proceedings of the Eighteenth Interna- tional Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pp. 388-397, San Diego, California, USA, 09-12 May 2015. PMLR. URL https: pptppeeiciggg.....//e/./........ mlr r..r. presspressss...... v38/ /ii//reel.... html.
Prateek Jain, Sudheendra Vijayanarasimhan, and Kristen Grauman. Hashing hyperplane queries to near points with applications to large-scale active learning. Advances in Neural Information Processing Systems, 23, 2010.
Jegelka and J. Bilmes. Submodularity beyond submodular energies: coupling edges graph cuts. pp. 1897-1904, Piscataway, NJ, USA, June 2011. IEEE.
George Baatogiaani--MMimaraan and Georgia Koutrika. survey on deep learning approaches for text-to-SQL. The VLDB Journal, 32(4):905-936 January 2023. ISSN 0866-8888. doi: 1001 s00778-022-007776-8 URL https:ttpt... /ww.. wrg/10.../....oo.... 00000//500700 -007-0776 6-78.
Vishal Kaushal, Ganesh Ramakrishnan, and Rishabh Iyer. Submodlib: A submodular optimization library. arXiv preprint 17Xiv:2202.10680, 2022.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of inffuence through social network. In KDD, pp. 137-146, 2003.
Omar Khattab and Matei Zaharia. Colbert: Efficient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pp. 39-48, 2020.
Omar Khattab, Christopher Potts, and Matei Zaharia. Baleen: Robust multi-hop reasoning at scale via condensed retrieval. Advances in Neural Information Processing Systems, 34:27670-27882. 2021.
Krishnateja Killamsetty, Durga Sivasubramanian, Baharan Mirzasoleiman, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad-match: A gradient matching based data subset selection for efficient learning. arXiv preprint 103.v:2103.00/223 2021a.
13

---

Published as a conference paper at ICLR 2026
Krishnateja Killamsetty, Durga Subramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: A generalization based data selection framework for efficient and robust learning. In AAAI, 2021b.
To Eun Kim and Fernando Diaz. Towards fair RAG: On the impact of fair ranking in retrieval- augmented generation, 2025. URL https: / aaaaiiiivv... http://b/////../11a.... http:///ww.....or///////00......
Catherine Kosten, Philippe Cudré-Mauroux, and Kurt Stockinger. Spider4sparql: A complex bench- mark for evaluating knowledge graph question answering systems. In 2023 IEEE International Conference on Big Data (BigData), pp. 5272-5281. IHEE, December 2023. doi: 10.1 109/ 20t.:a09990442..13330.3333 2023. 10886182.
URL http: /txp/xxcdo www.ddo.....oooooo wtgg/0...0 1109/ /11100/////////0/0.....
Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability, 3(71-104):
3, 2014.
Alex Kulesza. Determinantal point processes for machine learning. Foundations and Trends@ in Machine Learning, 5(2-3):123-2866 2012a. ISSN 1935-8245, doi: 10.1561/22000000444 URL http: /xxx doi org/ /00 www.1/1512200004//0
Alex Kulesza. Determinantal point processes for machine learning. Foundations and Trends@ in Machine Learning, 5(2-3):123-286 2012b. ISSN 1935-8245. doi: 10.1561/2200000044, URL
http::/dde doi.dii.... ottp////....///..0//.0010
Vishwajeet Kumar, Jaydeep Sen, Bhawna Chelani, and Soumen Chakrabarti. Graph representa- tion of tables+text and compact subgraph retrieval for qa tasks. In Advances in Information Retrieval:
47th European Conference on Information Retrieval, ECIR 2025, Lucca, Italy, April 6-10, 2025, Proceedings, Part I, pp. 164-180, Berlin, Heidelherg, 2025. Springer- Springer-Verlag. ISBN 978-3-033-88807--9 doi: 10. 00.1007/978-3-08 1--------1-87---11111 URL https:: /ooi org/10. 1007/978
Dahyun Lee, Yongrae Jo, Haeju Park, and Moontae Lee. Shifting from ranking to set selection for retrieval augmented generation. ACL Conference, pp. 17606 17619, Vienna, Austria, July 2025. Association for Computational Linguisties. ISBN 7779-8-99176-51-44 2025 lel..a.l-oong8611 URL https: https: https/////aaaatoloog...
doi: 10. 18.13v3/vv1/ 2020g//222..222 acls-acl---- acl--ong............o 861/
Jinhyuk Lee, Zhuyun Dai, Sai Meher Karthik Duddu, Tao Lei, Iftekhar Naim, Ming- Wei Chang, and Vincent Zhao Rethinking the role of token retrieval in multi-vector retrieval. Advances in Neural Information Processing Systems, 36:15384-15405 2023.
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: framework for aatention-baasee permutation-invariae neural networks. In Interna- tional conference on machine learning, pp. 3744-3753. PMLR, 2019.
Fangyu Lei, Jixuan Chen, Yuxiao Ye, Ruisheng Cao, Dongchan Shin, Hongjin Su, Zhaoqing Suo, Hongcheng Gao, Wenjing Hu, Pengcheng Yin, Victor Zhong, Caiming Xiong, Ruoxi Sun, Qian Liu, Sida Wang. and Tao Yu. Spider 2.0: Evaluating language models on real-world enterprise text-to-SQL workflows. In ICLR, 2025. URL ht: http:://axxivvvve abs/aba//a0 /2e.../11.... 07763.
Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Na- talie Glance. Cost-effective outbreak detection in networks. In KDD, pp. 4204224-44 2007.
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmented generation for knowledge-intensive NLP tasks, 2021. URL https: www.xii..oggaaaa 2005. 110001....1....
Jinyang Li, Binyuan Hui, Ge Qu, Jiaxi Yang, Binhua Li, Bowen Li, Bailin Wang, Bowen Qin, Rongyu Cao, Ruiying Geng, Nan Huo, Xuanhe Zhou, Chenhao Ma, Guoliang Li, Kevin C. C. Chang, Fei Huang. Reynold Cheng, and Yongbin Li. Can Ilm already serve database interface? a big bench for large-scale database grounded text-to-sqls, 2023. URL https: //axxiv.org/aas/////
03111.
14

---

Published as a conference paper at ICLR 2026
Rui Li, Quanyu Dai, Zeyu Zhang, Xu Chen, Zhenhua Dong, and Ji-Rong Wen. Knowtrace: Boot- strapping iterative retrieval-augmmentd generation with structured knowledge tracing, 2025. URL
https: arxiv org/ abs 2505 20245.
Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. Proceed- ings of the 49th annual meeting of the association for compulational linguistics: human language technologies. pp. 510-520, 2011.
Hui Lin, Jeff Bilmes, and Shasha Xie. Graph-based submodular selection for extractive summariza- tion. In 2009 IEEE Workshop Automalic Speech Recognition Understanding, pp. 381-386. IEEE, 2009.
Hao Liu, Zhengren Wang, Xi Chen, Zhiyu Li, Feiyu Xiong, Qinhan Yu, and Wentao Zhang. Hoprag: Multi-hop reasoning for logie-aware retrieval aaggraet generation, 2025a. URL https://
arxiv. org.v.orr/aae abs 2202 12442.
Nelson F. Liu. Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts, 2023. URL https: /ttw/vaxvvv//.////////ee/////atv org/ als///b/////// 122223300000 03172.
Xinyu Liu, Shuyu Shen, Boyan Li, Peixian Ma, Runzhi Jiang, Yuxin Zhang, Ju Fan, Guoliang Li, Nan Tang, and Yuyu Luo. A survey of text-to-sql in the era of Ilms: Where we, and where we going? IEEE Transactions on Knowledge and Data Engineering, 2025b.
Tianyang Ma, Xingwei Yang, and Longin Jan Latecki. Boosting chamfer matching by learning chamfer distance normalization. In European Conference on Computer Vision, pp. 450-463. Springer, 2010.
Yu A Malkov and Dmitry Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824 836, 2018.
Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, Cambridge, UK, 2008. ISBN 0521865719.
Alexander H. Miller, Adam Fisch, Jesse Dodge, Amir-Hossee Karimi, Antoine Bordes, and Jason Weston. Key-value memory networks for directly reading documents. CoRR, abs/1606.03 126, 2016. URL http: /ttp:////xiivvviii wwwpavv..rg/aaaaaooeeeeeeos /1css/16000 1666.66660 C3126.
Michel Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques: Proceedings of the 8th IFIP Conference on Optimization Techniques Würzburg, September 5-9, 1977, pp. 234-243, Springer, 2005.
Pitu B Mirchandani and Richard L Francis. Discrete location theory. 1990.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In Proc. ICMI, 2020.
Marco Morik, Ashudeep Singh, Jessica Hong, and Thorsten Joachims. Controlling fairness and bias in dynamic learning-to-rank. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '20, pp. 429-438, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 4503450811 doi: 10.1145/ 3397271.3400 100. URL ht http::://ooooooooo /0. http:////...1111137711.11111
Byunggook Na. Jisoo Mok, Hyeokjun Choe, and Sungroh Yoon. Accelerating neural architecture search via proxy data. CoRR, abs/2106.04784, 2021. URL $106.04784
Hariharan Narayanan. Submodular functions and electrical networks, volume 54. Elsevier, 1997.
15

---

Published as a conference paper at ICLR 2026
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions Mathematical programming, 14(1):265-29) 294, 1978.
Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. Learning diverse rankings with multi- armed bandits. In Proceedings of the 25th International Conference on Machine Learning, ICML "08, pp. 784-791, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 9781605582054. doi: 10.1145/130155..13902. URL https:t////.. http::://dci..og// or..1...1/////////..........1111 010115561390255
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1-67, 2020.
Ori Ram, Yoav Levine, Itay Dalmedigos, Dor Muhlgay, Amnon Shashua, Kevin -cowon and Yoav Shoham. In-context atrieval-augmentt language models, 2023. URL https:// a arxiv. arxiv.org/an abs 22002.30.00000002 00083.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. arXiv preprint arXiv: /908. 10084, 2019.
Keshav Santhanam, Omar Khattab, Jon Saad-Falcon Christopher Potts, and Matei Zaharia. Colbertv2: Effective and efficient retrieval via lightweight late interaction. arXiv preprint arXiv:2112.01488, 2021.
Keshav Santhanam, Omar Khattab, Christopher Potts, and Matei Zaharia. Plaid: an efficient en- gine for late interaction retrieval. In Proceedings of the 31st ACM International Conference Information & Knowledge Management, pp. 1747-1756, 2022.
Rodrygo L.T. Santos, Craig Macdonald, and Iadh Ounis. Exploiting query reformulations for web search result diversification. In Proceedings of the 19th International Conference on World Wide Web, WWW '10, pp. 881-890, New York, NY, USA, 2010. Association for Com- puting Machinery. ISBN 9781605587998. doi: 11445/11772690.7777888 URL https: 17727700..
//doi.org/10.
Apoorv Saxena, Aditay Tripathi, and Partha Talukdar. Improving multi-hop question answering over knowledge graphs using knowledge base embeddings. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault (eds.), Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 4498-4507, Online, July 2020. Association for Computational URL https://aclantte http://aaaaaatooooooo/oo org/
Linguistics. doi: 10. 1/225///112020acclam 2020. acl.main.mm....... 412/.
Jan Luca Scheerer, Matei Zaharia, Christopher Potts, Gustavo Alonso, and Omar Khattab. Warp: An efficient engine for multi-vector retrieval. In Proceedings of the 48th International ACM SIGIR Conference on Research and Development Information Retrieval, pp. 2504-2512, 2025.
Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subra- manya, Andrija Antonijevic, Dax Pryce, David Kaczynski, Shane Williams, Siddarth Golla- pudi, Varun Sivashankar, Neel Karia, Aditi Singh, Shikhar Jaiswal, Neelam Mahapatro, Philip Adams, Bryan Tower, and Yash Patel. DiskANN: Graph-structured indices for scalable, fast, fresh and filtered approximate nearest neighbor search, 2023. URL https:ttp///o /ttp::///iteee /tt//gtttuu thub. com/ Microsoft/DD SKANN.
Ashudeep Singh and Thorsten Joachims. Fairness of exposure in rankings. arXiv preprint arXiv:1802.07281. 2018. URL
abspg//bss/10// 07281.
Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heung- Yeung Shum, and Jian Guo. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph. In ICLR, 2024. URL https: /aaaaaaavvoo///// org/ abs/ 2307. 07697.
Youze Tang, Yanchen Shi. and Xiaokui Xiao. Influence maximization in near-linear time: A mar- tingale approach. In SIGMOD, pp. 135-11554, 2015.
16

---

Published as a conference paper at ICLR 2026
Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. Beir: A heterogenous benchmark for zero-shot evaluation information retrieval models. arXiv preprint 0eXii:2200400663, 2021.
Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. MuSiQue: Multi- hop questions via single-hop question composition. Transactions of the Association for Compu- futional Linguistics, 10:539-554, 2022.
Sebastian Tschiatschek, Josip Djolonga, and Andreas Krause. Learning probabilistic submodular diversity models via noise contrastive estimation. In Artificial Intelligence and Statistics, pp- 770-779. PMLR, 2016.
Sebastian Tschiatschek, Aytunc Sahin, and Andreas Krause. Differentiable submodular maximiza- tion. arXiv preprint (rXXvv:803.01785 2018.
Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson. RAT-
SQL: Relation-aware schema encoding and linking for text-to-sql parsers. In ACL 2020, 2021.
URL https::///............tt /tt///axivvv//// org/ abs/ 1911. 04942.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Learning, pp. 1954-1963, 2015.
Orion Weller, Michael Boratko, Iftekhar Naim, and Jinhyuk Lec. On the theoretical limitations of embedding- retrieval. arXiv preprint arXiv:2508.2 2025.
Haolun Wu, Yansen Zhang, Chen Ma. Fuyuan Lyu, Bowei He, Bhaskar Mitra, and Xue Liu. Result diversification in search and recommendation: A survey, 2024. URL https:: http:::///axxv.xir///// abs /2122 444.
Diji Yang, Jinmeng Rao, Kezhen Chen, Xiaoyuan Guo, Yawen Zhang, Jie Yang, and Yi Zhang. Im- rag: Multi-round retrieval -ugmeneted generation through learning inner monologues, 2024. URL
https: //t:://axxite ivv.v org/ alss 2405. 13021.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpotQA: dataset for diverse, explainable multi-hop question answering. In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun ichi Tsujii (eds.), Proceed- ings of the 2018 Conference on Empirical Methods Natural Language Processing, pp. 2369- 2380, Brussels, Belgium, October-Novemboo 2018. Association for Computational Linguistics. doi: 1/188111/ URL htttts://cccaattatit http///acaaathohoooo -rg/D18-1259/
/
HongChien Yu, Chenyan Xiong. and Jamie Callan. Improving query representations for dense re- trieval with pseudo relevance feedback. CoRR, abs/2108. 2021. URL htt.t::ttaaaatttt org/ org/abs// 221.2.1..2 13454.
gennereaatnnnnnennnntnnttiioo Tian Yu, Shaolei Zhang, and Yang Feng. Auto-rag: rettooommuusttttiivvalaaaaannng generation for http://awxxw...gaa/a/o////
large language models, 2024. URL
Meike Zehlike, Ke Yang, and Julia Stoyanovich. Fairness in ranking, part i: Score-based ranking. ACM Computing Surveys, 55(6):1-36, 2022.
Cheng Xiang Zhai, William W. Cohen, and John Lafferty. Beyond independent relevance: methods and evaluation metrics for subtopic retrieval. In Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval, SIGIR '03, pp. 10-17, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581 136463. doi: 10. 10.1145550 00.1145/860435.00 00444440043...004400 URL https://p// / doi org 10. 4 004555/86433 860440
Wayne Xin Zhao, Jing Liu, Ruiyang Ren, and Ji-Rong Wen. Dense text retrieval based on pretrained language models: A survey, arXiv preprint arXiv:2211.14876 2022a. URL https: /arxiv..
org/abs/22 2221 14876.
Yilum Zhao, Yunxiang Li. Chenying Li, and Rui Zhang. MultiHientt: Numerical reasoning multi hierarchical tabular and textual data, 2022b. URL httpt:t/aaxiii......m//// wttpl/v..rrg/b////2/000 01347.
17

---

Published as a conference paper at ICLR 2026
Yilun Zhao, Yunxiang Li. Chenying Li, and Rui Zhang. MultiHiertt: Numerical reasoning multi hierarchical tabular and textual data. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computa- tional Linguistics (Volume I: Long Pupers). pp. 6588-6600, Dublin, Ireland, May 2022c. As- sociation for Computational Linguistics. doi:
(/t.///////2222allllll 154..454. URL https: //aclanthologys .rgg wwt. 202./0222222222 aww.long...1111111
Tianyi Zhou, Shengjie Wang, and Jeffrey Bilmes. Curriculum learning by dynamic instance hard- ness. Advances Neural Information Processing Systems, 33:8602-8613 2020.
Tianyi Zhou, Shengjie Wang, and Jeff Bilmes. Curriculum learning by optimizing learning dynam- ics. In International Conference Artificial Intelligence and Statistics, pp. 433-441. PMLR, 2021.
18

---

Published as a conference paper at ICLR 2026
A Dense Subset Index for Collective Query Coverage (Appendix)
A BROADER IMPACT
We have presented DISCO, an indexing system for collective scoring of subsets of corpus items in response to query. This stands in contrast to traditional retrieval, where items compete against each other to occupy top-K positions. Applications that use traditional retrieval, yet need collective coverage, often inflate K with the hope of including corpus items in optimal query cover. Replacing that approach with DISCO may reduce query processing cost and carbon footprint, as well as "lost in the middle" (Liu al., 2023) distractions for downstream LLMM reasoning and generation modules, resulting in better end task performance well saved computations.
B LIMITATIONS
We have demonstrated that DISCo is novel and performant method for collaborative subset trieval. However, there are avenues for improvement. We outline these below for future exploration.
Fairness. Our proposed coverage objective does account for notions of fairness, e-g. group fairness or individual fairness (Zehlike et al., 2022). For benchmarks where fairness a factor, such as (Ekstrand al., 2023), collaborative and fair retrieval a challenging and promising avenue for future work.
Diversity. As of now, have focused only on coverage maximization. We do incorporate diversity explicitly in the model However, one can subtract a self-similarity tern among the corpus tokens from the coverage objective obtain a diversity encouraged coverage optimization.
Evolving corpora. DISCO is not currently designed to handle evolving corpora. In all datasets, the corpus is fixed, and indexing done once, with no further updates. Handling changing corpus sets would be an interesting follow-up.
Addressing these limitations will improve the real-world readiness and deployment capability of DISCO.
C LLM USAGE
We used an LLM strictly and only for (1) ancillary writing support for correcting grammar, sug- gesting alternative phrasing, and (2) very occasionally, literature search. No LLM was used to generate ideas, design experiments, analyze data, implement algorithms, produce results. Any model-suggested wording, URL, or citation was reviewed and further revised by the authors.
D FURTHER MOTIVATING SCENARIOS
D.1 MULTI-HOP QA
We gave an example of collective passage retrieval for multihop QA in Section 1. In recent years, retrieval is often followed by large language model (LLM) that reads and encodes the retrieved passages, then decodes the answer in other words, such systems implement retrieval augmented generation (RAG) (Guu et al., 2020: Lewis et al., 2021; Ram et al., 2023). It has been reported that the end-to-end performance of the RAG search system is sensitive to the position of the answer- bearing passages in the LLM's input context (Liu et al., 2023). Adding irrelevant passages in the context can also be deleterious, leading to incorrect answers. Therefore, high recall of all passages needed to infer the answer, within tight budget K, may enhance downstream generation. This realization is gaining ground in the NLP community. One recent response has been to resort to an L.MM-based solution to subset selection, based verbal instruction (Lee al., 2025).
D.2 KNOWLEDGE GRAPH QA
QA over KGs like Wikidata take forms: semantic interpretation (Berant et al., 2013), where natural language question is translated into a structured query, and subgraph retrieval and answer generation (Saxena et al., 2020; Sun al., 2024). To enable L.LMs to deal with billion-node graphs,
19

---

Published as a conference paper at ICLR 2026
Austria
Tesla
SpaceX
birthPlacs
founder
founder
Nikola Tesla
Elon Musk
birthPlace
Pretoria, SA
Figure 7: Example of KGQA taken from Dubey et al. (2018), for the query "where was the founder of Tesla and SpaceX born?" Observe that there two text matches with Tesla, one leading to 'Austria' as the (incorrect) answer, but the correct answer node must be close to both Tesla and SpaceX. If edges visualized "passages', collective retrieval system must score highly the right subgraph, but not the left one.
subgraph retrieval is critical step in the latter approach. As Figure 7 shows, the goal is retrieve a subgraph that collectively contains the evidence of partial match with the question, and evidence in favor and answer node(s) edge(s). Allowing nodes edges to compete at matching the whole question would be misguided.
In the table below, the aggregate contractual principal amount loans an nonaccrual status andior more than 90 days due /which excludes loans carried at zero fair value and considered uncollectible) exceeds the related fair value primarily because the regularly purchases loans, such as distressed loans, at values significantly below the principal amounts:
millions)
of
2016
2015
Performing loans and long-term receivables
Aggregate contractual principal excess of fair value Loans on nonaccrual status and/or more than days past due
$ 478
5 1,330
Aggregate contractual principal excess value Aggregate fair value loans nonaccrual status and/or more than days past due
8.101
9.600
2,138
2,391
The table below presents information about our funding sources.
December
in millions
2018
2017
Deposits
Collateralized financings:
Repurchase aggrements
78.723
13%
84.718
14%
loaned
secured financings
21,433
Total collateral ized financings
111,964
18%
124,299
20%
Unsecured short-term borrowings
40,502
46,922
8%
Unsecured long-term borrowings
224,149
36%
217,687
36%
Total shareholders equity
90,185
14%
82,243
13%
Total funding sources
$625,057
100%
$609,755
100%
Question: What is the sum of securities es loaned in excess of fair value in 2015 (in millions)?
2017 and aggregate contractual principal
Figure 8: Example of table QA taken from Kumar et al. (2025). Note that the question has poor match coverage by any single table element, but there is small collection S of table elements that collectively cover large (colored) spans of the question. Current practice linearizes such tables into text for LLMs, polluting the match scores with much extraneous noise from irrelevant parts of the table.
D.3 TABLE QA
Another motivation comes from QA the domain textual tables (Chen et al., 2022; Zhao et al., 2022c; Kumar et al., 2025), such as appear in documents for human consumption. As Figure illustrates, attempting to match the whole question against the whole table would result in weak and noisy scores. In contrast, recognizing that certain spans in the question covered by certain coherent table elements (that are also spatially related) results in retrieving values from cells, from which answers be reasoned out.
20

---

Published as a conference paper at ICLR 2026
Natural Language Question:
Desired SQU:
For the with gylinders, which model has the largest horsepower?
SELECT T1.model
FROM car nanenanees AS T1 J0IN cars_ pars_data AS T2
Schema:
ON T1.nake 12.1d
cars_ __ddaaaa
WHERE c2.cylinders
ORDER BY T2-horsepower DESC LIMIT
cyltiders
edispl
horsepmeer
wed girt
year
car names
model list
cap manners
Question Column linking (unknoww))
id
sodel
make
soddee iol
salcur
social
maker
full nura
country
Question Table linking [unknown)
Column Column foreign keys (known)
Figure 9: Example of tex12sql taken from Wang et al. (2021). Schema retrieval involves mapping question spans schema elements (table and column names), after which SQL can be generated.
D.4
SCHEMA RETRIEVAL FOR TEXT2SQL
Text2sql a form semantic interpretation where the target database relational (Katsogiannis- Meimarakis et al., 2023). As with text QA, KGQA and table QA, LLMs have gained use as semantic translators and interpreters also for text2sql (L.iu et al., 2025b). Enterprise schema can contain thousands of tables and tens of thousands of columns. The schema can be represented as graph where nodes represent tables and their columns (Wang et al., 2021), with grimary-key-foree seyyfforegnn-eyy and joinability relations connecting column nodes. Providing the full schema along with the natural language question as context does not only tax GPU usage in modern decoder-only LLMs, but also risks the LLM not being able sift the schema for the relevant parts (Liu al., 2023). As shown in Figure 9, tables and columns have to be selected to collectively cover specific spans in the question. Once again, individual schema elements are poor matches for the question, and it would be incorrect to pit them for relevance against each other. Unlike in passage retrieval, the total schema size may be small enough to formulate schema subgraph retrieval mixed integer linear program (Chen et al., 2025b), but this again clearly demonstrates the importance of collective scoring.
E EXTENDED DISCUSSION OF RELATED WORK
Our work is related submodular functions, data subset selection, ANN search, etc. In the follow- ing, we first contrast approaches to diversity in information retrieval to our method, and then briefly review and provide an extended discussion on related work.
E.1 HoW OUR METHOD DIFFERS FROM DIVERSIFICATION IN IR
In continuation to the discussion in Section 3.2, note that focus is coverage in the first stage itself, where we design indexing and retrieval method tailored specifically for coverage max- imization. Note that, submodular maximization has been widely used since 1978, but work focus on designing ANN retriever for coverage based submodular maximization. Therefore, our work focus indexing and search, whereas these existing works, albeit related, focus suitable submodular scoring function computation and the application of greedy variants to maximize it. Ex- tensive search reveals a paucity on direct first-stage dense retrievers that optimize a query-coverage objective. A notable exception is in the use of pseudo-relevanee feedback in dense retrieval to im- prove facet/subtopic coverage (Yu et al., 2021) like key-value memory networks (Miller et al., 2016), they also perform multi-round dense query modification, but there are no formal coverage guarantees.
E.2 SUBMODULAR FUNCTIONS
Submodular functions are functions that satisfy the property of diminishing return- a list of classic readings (Fujishige, 2005; Narayanan, 1997; Edmonds, 1970) provides a comprehensive discussion. They are discrete analogue of concave functions. They are used in wide variety of applications. e.g., information cascade in social media (Kempe et al., 2003; Tang et al., 2015; Leskovec et al., 2007; Goyal et al., 2011; Borgs et al., 2014) 4), document summarization (Lin et al., 2011), product recom- mendation (Tschiatschek et al., 2016; 2018), image processing (Jegelka et al., 201 1), probablistic modeling (Gillenwater et al., 2014; Kulesza, 2012b; Gotovos et al., 2015; Iyer et al., 2015), etc.
E.3 DATA SUBSET SELECTION
Our work is connected to traditional data subset selection problem, where the goal is to select data subset from large set. It has several applications, e.g., active learning (Wei et al., 2015), data
21

---

Published as a conference paper at ICLR 2026
efficient learning (Mirzasoleiman et al., 2020; Killamsetty al., 2021a; Durga al., 2021) for training, etc. In active learning the goal is to obtain the labels of a unlabeled data, so that the model trained with those subset of labeled data, generalizes well (Wei et al., 2015). In data efficient training, we are given full labeled data and the goal is go select a subset of training data, so that can achieve fast training with minimal accuracy loss (Killamsetty et al., 2021b;a; Durga al., 2021). They typically frame it as joint optimization of parameter and subset selection, where the subset selection problem is often submodular or approximately submodular. Another line of works adopt different heuristics for data subset selection, e.g. entropy guided data subset selection (Na et al., 2021), use of another proxy model (Coleman et al., 2020). Zhou et al. (2020; 2021) provide adaptive subset selection based on curriculum learning. Our work is also related to coreset selection, where the goal is to select some subset (with or without weights) that is representative of the entire set (Feldman, 2020; Mirzasoleiman et al., 2020; Har- Har-Peled et al., 2004). Our work aims to select subset of items from a large set of items in an information retricval setting, where the corpus is fixed for different queries. This allows us to perform one time preprocessing of corpus items, whose cost is amortized over large number of queries. The above applications, however, do not operate on this setting and therefore, they cannot ANN algorithm for such selection.
E.4 APPROXIMATE NEAREST NEIGHBOR (ANN) SEARCH
In a nutshell, we seek to design an ANN method for marginal gain maximization within the frame- work of the greedy algorithm. Classical information retrieval systems used bag of words, which used token-id level matching, followed by an inverted index with TF-IDF or BM25 term weighting. Lucene (Gospodnetic et al., 2010) and Elastic search (Gormley et al., 2015) use similar techniques. Subsequently, neural models have been developed to represent tokens or atoms using contextual representations e.g., BERT (Devlin al., 2018), T5 (Raffel et al., 2020), etc. Documents can be represented as both single vector and multivectors of token representations. Such representations key to dense vector retrieval, HNSW (Malkov al., 2018; Simhadri al., 2023), IVF (Douze et al., 2024), LSH (Charikar, 2002). Khattab et al. (2020); Santhanam et al. (2021; 2022) and our current method use multivector-bee based indexing using IVF. DiskANN and LSH used single vector- based indexing and retrieval. Our random projection method uses some technical results from LSH (Charikar, 2002: Jain et al., 2010).
In contrast to the above dense retrieval, sparse retrieval uses tokenized representations to build in- verted index. Recently Formal et al. (2021) also proposed token expansion method for enhanced sparse retrieval. As shown in the recent paper (Weller et al., 2025), multivector representations often results in enhanced performance as compared to single vector representations.
The single-round retrieval of REALM (Guu et al., 2020) and RAG (Lewis et al., 2021) soon gave way to multi-round RAG (Yang et al., 2024; Yu al., 2024), sometimes with filtered retrieved items progressively padded with the query (Khattab et al., 2021), and later with more sophisticated planners extracting structured information from retrieved passages (Li et al., 2025; Liu et al., 2025a). Despite the superficial similarity of multi-rount retrieval, there critical differences between these and DISCo. While DISCo iteratively targets query coverage, effectively canceling out parts of the query (which remains a turning multi-hop queries into a series of exploratory document-to-docunet expansions.
vector) already covered, these are query expansion techniques,
E.5 DIVERSITY AND FAIRNESS IN SELECTION AND RANKING
Another community that needs to score item subsets rather than individual items is concerned with the diversity and fairness of the returned responses. The need for diversity was first felt in the retrieval community, in the face of near-duplicate documents that (necessarily) had similar relevance to the query (Wu et al., 2024), but inspection of one document obviated the need to inspect the other.
Early methods like max marginal relevance (Carbonell et al., 1998) chose the next item based on a combination of its relevance to the query and dissimilarity to items already selected. Other tech- niques (Singh et al., 2018) involved solving relaxed integer linear programs with N22 variables, where N is the number of items in the corpus, so these cannot easily be applied as a first-stage ranking system (Guo et al., 2022).
User attention to the top-K rank positions has been instrumented by search engine providers and found to steeply decrease with rank. A closely related concern to diversity is faimess, in the face
22

---

Published as a conference paper at ICLR 2026
of such steep attention discounts, i.e., ensuring that user attention to item is proportional to some intrinsic utility of the item for a query, or that user exposure of any designated group does not vary excessively across groups (Morik et al., 2020; Kim et al., 2025). These concerns are quite distinct from our coverage motive.
We note that diversity and fairness may incidentally favor query coverage, but these are very unre- liable indirect mechanisms. It is possible to maximize diversity and relevance, yet fail to provide collective coverage of the query.
23

---

Published as a conference paper at ICLR 2026
F PROOFS OF TECHNICAL RESULTS
F.I F(.9) Q) IS MONOTONE SUBMODULAR
Theorem 5 (Monotonicity and submodularity). The set function F(S, Q) is monotone and submod- ular.
Proof
From Proposition I, we observe:
F[c|S,00 = Σ
max q
max max q x' WES x'EX,
(10)
QE
Clearly the marginal gain F(c|S,Q) 0, which proves that F(S, Q) is monotone in S.
Now suppose C T, then we have:
max max x' < max max x WES x.E
(11)
NET T'E,
Σ max aEX,
q x
max max q WES E'E
x')
Σ
max
q To x
max max q TTxt WET 2'EX..
(12)
wEX,
QEQ
qEQ
From the formula of marginal again in Eq. (10), we have: F(S,Q) F(T.Q).
F.2 PROOF OF PROPOSITION I
Proposition
Given the coverage objective F(S, Q) defined in Eq. (2), the marginal gain is:
F(c| S, Q) = Σ
max
x
max wES x m'EX
max q TTal x'
(13)
qEQ
Proof
We assume that S to prove that:
= =( Q) F(S,Q)
Σ
max
qxx
Σ
max qTx x
(14)
@EUncS-(e)
Xx qEQ
4EQ
Σ
max uESUfe)
max mEX,
max WES
max x
4EQ
x))
Σ
max
max q xr max .EEx
max q x: -max max WES
max q x (EX,,
WES
mEX,
EEQ
Letting ma q T x and b = max.es (maxx q Tx), we apply the identity max(a, b) b max(O, b) the term inside the summation:
max q T x )
Σ max 00, max q QEQ
x max wES
x
Using the notation
[2]+
max (0, z) for the positive part of arrive the compact final form:
max q T x xEX;
max wES
max TTx)
(15)
QEQ
F.3 PROOFS FOR RANDOM HYPERPLANE APPROXIMATION
Theorem 2. Given any two vectors u, v E RR++1 lee w be random hyperplane w ~ N I441), and w be the transformation defined Eq. (6). Then, we have the following result:
@w()) (w(v) = [u w]+ with probability p 2 0.5.
(16)
Proof We show that: p = 1 - cos
0.5. The equality here is tight, when [TTTl ol 0. We shall make of the well known result when is sampled from spherically
[ ||||||||]]
>
24

---

Then, for any e & S. S C and Q = {g}. a positive probability > 0 and R 2 (o(())/5)), we Published as a conference paper at ICLR 2026
symmetric distribution (Charikar, 2002):
P(sign(w w u) sign(w v)) = cos -1
u w
(17)
|
|
where, sign: - (-1, +1} is the sign function.
Let - (w) 1 (w) = (x v sign(wT u) sign(w' (n) u v)
Case 1: u u O. This also implies angle between and v is less than 17/2.
In this case, [u v++ = uvv. v. Meanwhile, 8 = u iff sign(w' T u) = sign(w' T v) and otherwise.
Pr(s [++++++ = Pr(s = u TT)
(18)
F(sign(w' Tw) = (ign(wTo))
(19)
1
u
cos
(20)
||uu| ||l||
2 2
(Acute angle between u and v)
(21)
Case 2: u To < O. This also implies angle between u and v is more than 7/2.
In this case, (u e+++ O. Meanwhile, 0 if sign(wT Tu) sign (w Tv) and u
otherwise.
Pr(s [u [+++) Pr(s 0)
(22)
P'(sign(w"' (w wwu) u) -iignww'' u)))
(23)
1
T v
cos
(24)
||z/|| ||م|||
π
1 (Obtuse angle between and v)
(25)
2
Case 3: u² O: In that case, 0 [u w]+ with probability one.
Combining these cases, the probability that = [u u is 2 1.- Furthermore, note that is always & [u.uv v)].
Theorem 3. Suppose (Wi...., WRR be R random hyperplanes with w, itd. N Ia+1). Given the dependeen representation for each query token ÿs ;= [q, F(S, q) and the query agnostic representation of each corpus token = -xx;- [x;-1] as defined in Eq. (4), let the randomized function Gwin be defined as:
Gw,,(c,,()) EnEq m max
(w.( T @ww- (3)
(26)
will have Gwia S, Q) F(c S, Q), with probability atleast - 6.
Proof
This relies on Theorem 2.
Given a fixed (augmented) token Øs. let के be the (augmented) token that maximizes 7 a (where these are (d + 1-dimennsional augmented vectors). Then, we can write:
Pw. (qs) Pw. (z) = -1 x]+ with probability p 2 2
(27)
Eq. (27) implies that:
[ x]+ with probability 1
max P ww. (9)) &w. (x) max max
(28)
x
2
Note that [ is the maximum value of the approximation. Hence,
Tw (qs) o 4w. (.) <
x] for all a [
(29)
We note that Eq. (29) implies that:
max Pw. (ğs) +
max max 93 3)+ with probability =1 =
(30)
x.
25

---

Published as a conference paper at ICLR 2026
Thus for R. sampled hyperplanes, the event that maximum of the above approximations gives the correct value is the same as the event that atleast one of R augmentations giving the correct value. Hence, we have:
max max (qs)
T Pw. (z) = -99 x
(31)
rE[R] #EX,
Br E [
max max (qs) xx x.
Dw: (
[9s 2)
(32)
Hence we have
Pr max max (9s) rE]R] mex.
T
Dw. (x)
[ x
II rE[R]
1 Pr
max (qs) T Pw, (3) 1175 [0]++ æEX.
- 1
11
21
1
= 2
(33)
Finally, applying the union bound over all query tokens in Q. the probability that all tokens are correctly approximated is 2 - 1Q122 Setting - 1Q1/2" 2 1-6 8 gives us the condition R 2 log(1Q1/6).
This leads to the following corollary.
Corollary 6. For a given set of items S and query Q, let Gwi. S, Q) be defined as in The- orem 3 with R 1og()Q)/8). Let eg = arg max (G (e' (1S, (), then for the coverage function F,
F(ea [5,Q)= max F((|S,Q) w.p. 1 1 e'Ecys
(34)
Proof Let e: be a document that maximizes the marginal, i.e. F(c" [S max F(c') S, Q). Then, from Theorem 3, (c' () = F(c" S, Q) with probabil- ity 1 8.
We use the fact that Gwiin is bounded above by F, which means that for any document E C S, (eln(e) S, Q) I F(c Q) s F(c" [S (S,
As Gwii (ca |S, Q) max Gwiie (c' Q) 2 Gw (c" (,, the above two conditions imply that the bound becomes tight with probability atleast 1 1- ó, Lee. F(eal S, Q) = F(c (, max,ecvs F(c' [ S.Q).
F.4 PROOF OF APPROXIMATE GREEDY GUARANTEE
Theorem 4. Let SK be the set of K corpus items selected by Algorithm 2, and let S be the optimal sel for F, i.e., 8 arg maxg F(S, Q). Given å E (0, 1}, if we set the number of random projection vectors R > log()Q1/8),
E [F(SK. Q)1 2 (1 - 1/e- -)- F(S" ,Q).
(35)
Proof For notational simplicity we shall drop the subscript of the expectation. Let the set of documents selected at each iteration of the algorithm be S₁ for k I....,K. K. Let Sk+1 Sş [cx+1). Greedy choice is C*+1. From Lemma 7, we have:
Σ S
F(a Sk, Q) F(S* Q) - F(Ss, Q)
(36)
Combining this with Lemma 7:
(F(S" E [F(ck+1 Sk, Q) Sx] 01 ( ())S")Q)-0 F
(37)
Since F F(S+11, Q) F(St. Q) + F(c++1 Sy, Q). we can rewrite this as:
1-6 1--1-)
E [F Q) - F(Sx+11)) [k] S (1- K
(F(S Q) F(S,, Q))
(38)
26

---

Published as a conference paper at ICLR 2026
We make the following observation, as Su { and S1:.., Sk. ...k are defined sequentially. Thus,
for a random variable X, E|X] = E So] = E.. ... .. [k] s...... |1]] So]. Now we can write
[F Q) - F F(5x) SK-1] - 1 1 - (F(S", Q) -((
(39)
K
One more round of taking expectation gives us:
E FF(S", ,)- F(Sk) 1 SK
(40)
1-6
< E
1
(F(5-)))F((x-.00)) |S
K
(41)
s <(1 1
) (F(S", QQ) F(Sk-2: Q))
1-8
8) 2
(42)
K
By unrolling up to So.
1- 1-
[[F(S", Q) - F(SK, Q)1 S
(F(S", -FSO Q))
(43)
K
1 =(1
1- 8 K
,))",Q)
(44)
K
Rearranging terms,
1- 10-11-10)
1- 18) K
E [F((SK,Q)] 2
F(S", ,Q)
(45)
2 1 (1-6-0-6)) Q))",Q)
(46)
(1- 1/e - 8)F(S"
(47)
The last inequality uses the fact that e
e- (1-8) < 1/e + 5. This completes the proof.
Lemma 7. Let Ck+1 = arg max, S. GwI. (c; Sx, Q), i.e. the item returned by the approximate
greedy algorüthm 2 in the wth round for inclusion into Sy to form Sk+1. Then, the expected marginal gain at each step satisfies:
(1 (1-5)
E [F(CE++1] SE, Ss)
Σ
F(a|Sk.Q Q)
(48)
RES-
Proof Let C be the document maximizing the marginal gain F(-1S, Q) in C\ Sr. Our Approx- greedy algorithm 2 chooses ct+1 = arg max Gwi. (c' Sk,, Q). Therefore, using Corollary 6, we e'EC/S
have
F(cu+1| 1Sa Q) = F(e++1 Sk, Q) w.p. 2 1 - 8 E [[ Se, Q) [Sy] 2 (1 - F)) Sp, Q)
(49)
(50)
By the definition of ck+ for any a E S* \ Se:
F(T++1 S4, Q)= 2 F(a Sk. Q)
(51)
Therefore:
F(e441| |8,, 1)
1
Σ
F(a| Se, Q)
(52)
5" \
St
aEs* S8a
2 K
Σ
F(a Sr. Q)
(53)
aES*/S
Combining these inequalities:
E [F(ckHI|SA () St] 2 (1- Σ
F(alSt. Q),
(54)
K
a
which completes the proof.
27

---

Published as a conference paper at ICLR 2026
G ADDITIONAL DETAILS ABOUT THE EXPERIMENTS
In this section, we provide the necessary details about the experiments. Our code is already uploaded in supplementary material.
G.1 DATASETS
We evaluate on two widely used IR suites:
BEIR (Thakur et al., 2021)
Long-Tail Mail Topic-stratified Evaluation (LoTTE) (Santhanam et al., 2021)
BEIR. BEIR comprises heterogeneous retrieval tasks spanning multiple domains. We use the
following large-corpus subsets:
Dataset
(Test) Queries
#Documents
[@: (1
Brief Description
[
MS-Marco
43
8.84M
1.00
Pussage retrieval from web search queries (Bing) Multi-hop QA requiring evidence across documents Claim verification with Wikipedia evidence
HorporQA
7,405
5.23M
1.00
Fever
6,666
5.42M
0.12
Table 10: BEIR subsets used and their statistics. The fraction column is the proportion of queries with [gooa((Q)
LOTTE. LoTTE targets out-of-domain generalization with six topic-stratified corpora constructed from Stack Exchange communities. Each corpus provides two query sets (search and forum); we the forum queries derived from question titles.
Dataset
Test Queries
#Documents
[[Q: [spm()]=11]
Subtopics (examples)
[
Lifestyle
2,000
119K
0.90
Cooking, Sports, Travel Gaming, Anime, Movies Math, Physics, Biology
Recreation
2,000
167K
0.78
Science
2,017
1.7M
0.92
Technology
2,004
639K
0.95
Apple, Android, UNIX, Security English (writing, usage) Union of all above topics
Writing
2,000
200K
0.95
Pooled
10,025
2.8M
0.90
Table 11: LoTTE dataset. The fraction column is the proportion of queries with Soala (Q]) 1.
G.2 INDEXING STATISTICS
In Table 12, we provide statistics on index construction and memory consumption for each of the indexing based methods. We note that the memory consumption reported for DISCo is higher than for other methods due to the construction of R 8 different replica indices, each housing corpus vectors that have been augmented to approximate the maximum marginal gain.
Dataset
PLAID
MUVERA
WARP
DISCO
MS-Marco
GB
88 GB
GB
285 GB
HotpotQA
12 GB
52
48 GB
172 GB
Fever
17 GB
GB
87 GB
240 GB
Pooled
GB
GB
70
160 GB
Science
5,9 GB
18 GB
47 GB
88 GB
Technology
2.6 GB
6,4 GB
GB
38.9 GB
Writing
0.7 GB
2.1 GB
3.5 GB
11 GB
Table 12: Index memory consumption across methods and datasets, in gigabytes (GB).
G.3 IMPLEMENTATION DETAILS
Embedding model We use transformer models trained on standard IR tasks for embedding the queries and corpus document. In particular, we use the embedding model from PLAID (Khattab et al., 2020), which is a BERT-base model finetuned of a 12-layer transformer encoder with an output dimension of 768, followed by a línear layer that projects the output embeddings down 128 dimensions. The architecture employs WordPiece
the MS-Marco dataset. The model consists
28

---

Published as a conference paper at ICLR 2026
tokenization the raw text to generate token IDs. Following the ColBERT recipe, we L2-normalize the embeddings, and also mask out stop words in the corpus documents.
Retrieval Engine We adapt implementation starting with PLAID engine (Santhanam et al., 2022) to maximize the approximate marginal gain Gwar which ultimately maximizes the coverage objective (2). Note that query in parallel the R replica indices in order to speed up the pipeline. We expand on this below.
Next, we describe the pertinent details of our indexing and retrieval implementation.
Embedding Storage: The mode of embedding access depends on corpus size. For smaller corpora we support in-memory storage, which is faster, while larger corpora use disk-based mode. Embeddings are serialized during indexing in batch.no. chunk_no. pk1 format, ensuring no embedding is duplicated across chunks. Embeddings are dumped to disk as part of the indexing process, and are then loaded either once (1) wholly in memory for memory mode, or (2) on during search on immediate need basis in disk mode. By immediate need basis, it is meant that we iterate over the pickle files and retrieve only the requisite corpus token embeddings.
Augmentation: We sample It random hyperplanes and store each in its own file to prevent ran- dom corruption. When indexing. we generate R different folders, containing index data correspond- ing to the given hyperplane. The augmentation process takes batch of corpus token embeddings, a hyperplane, and returns embeddings which are to be indexed only by the corresponding indexing process (out of R such processes). The search procedure follows suit, in that query token embed- dings are augmented on-the-fly and then passed on to the corresponding index for retrieval. Note that the data returned from the augmented indices is pooled as part of an earlier stage. The final results are returned using the non-augmented index corresponding to the given dataset.
Parallelization: We query the R replica indices in parallel, in order to speed up our pipeline. In the case of DISCO, we choose multi martii-hrreaiig as our preferred form of parallel processing. It is known that the global interpreter lock (GIL), a data structure used to prevent parallel processing, is active in base Python installs. This limits the parallel capability of our program. However, note that in this setup no inter-process communication is required, and due to disk I/O being the chief bottleneck, we found Python's 's turtid- to be faster than Python's 's multiprocessing module in our experiments.
In the case of late pooling, we resort to using the multiprccsssing module, as no internal edits of the engine code are required.
Quantization: For quantization of the embeddings, we require that the number of embedding di- mensions be such that number of quantization bits per dimension x number of dimensions is a mul- tiple of 8 (so that the quantized vectors can be stored in bytes). As our embedding models produce 128-dimensional vectors by default, the augmentation procedure described in Section 3 would result in 129-dimensional vectors. To ensure compatibility with quantization, we take the first 127 dimen- sions of the embedding, which has a negligible impact on performance. For a fair comparison, we use the 127 dimensional embeddings for all methods (by truncation or setting the last dimensions to zero). We set 2 bits per dimension for quantization. We generate It = 8 replica indices. The quantization method is the same as PLAID.
Coverage Scoring: We perform exact scoring using efficient tensor ops. We make use of the following property: max f max(maxs f, f fc)) for the coverage value per token q. Thus, we can efficiently update and compute the vector [F(S, 4)) This unreduced/partaally computed MaxSim score can be used for coverage scoring for our baselines, well as for computing the augmented representations [qslqEQ, which is simply the concatenation of the query embeddings with the above vector.
Hy perepaaaaeeeers While indexing, DISCO sets the number of centroids (B in the indexing rou- tine Algorithm 3) for k-means dynamically based on the number of items. k-means is computed on a much smaller subset sampled from the entire corpus before indexing. This sample is also used to estimate the total number of tokens over the entire corpus (, which is the size of the index.
The number of centroids for k-means is chosen as v16 x est. size. However, rather than this exact quantity, we instead the largest power of 2 that is less than or equal to it, considering the bitwidth of the centroid id field. This is also the strategy used by PLAID.
29

---

Published as a conference paper at ICLR 2026
During retrieval (Algorithm 4), we probe one cell per token, and we fix n'' 1. Subsequently, the threshold I is set to 0.5, and the number of documents considered after filtering is 256. These values are based on the values used by PLAID when retrieving n' items.
In our ablations in Section G. we also experiment with the following combinations of hyperparam- eters for DISCO: (n', n), = (10, 256, 0.5), (15, 1024, 0.45).
We also introduce a different variant, termed Late Pool, where each replica is used for end-to-end retrieval, which includes pruning, filtering and obtaining a top-n'. This is followed pooling across all replicas, and the best candidate is chosen out of these. In this case, we test the same combinations of (n', n, n,,), namely (1, 256, 0.5). (10, 256, 0.5), (15, 1024, 0.45).
G.4 BASELINES
We use two classes of baselines (1) Submodular Optimization based solvers (2-4), and (2) Retrieval engines based on MaxSim retrieval.
Exact Greedy (Nemhauser et al., 1978). It performs exhaustive search over the corpus items, by computing the marginal gain F(el --. Q) for each C for each K (line 3, Algorithm 1). In this manner, it builds the solution set over K iterations. The brute-force evaluation of each candidate renders it inefficient for large corpus sets. It serves as a skyline in terms of coverage performance. and is implemented without the use of any solver for this reason.
Lazy Greedy (Minoux, 2005). This is an accelerated variation of Exact Greedy. It builds heap before the first iteration, which allows it to avoid exhaustive search in subsequent iterations. How- ever, it still has to build the heap for each query, resulting in a linear time complexity. It is based on the principle that for submodular functions, the marginal gain of an item can only diminish as the algorithm progresses.
Stochastic Greedy (Mirzasoleiman et al., 2015). It is variant of greedy algorithm which- instead of probing the entire corpus Caanss--iiiiiit uniformly samples a subset C' C C at random to evaluate and select the next candidate. The performance of this algorithm entirely depends on the size of the subset sampled, which is in turn controlled by the e' parameter. e' presents a speed-coverage tradeoff.
Lazier-than- lazy Greedy (Mirzasoleiman et al., 2015). This variant of Exact Greedy combines the benefits of Lazy Greedy and Stochastic Greedy together. It heapifies the randomly selected subset before the first iteration, which speeds up the subsequent selections of K elements. The speed benefit derived may be heavily implementation dependent. In our experience, the submodlib library implements Lazier-than-lazy Greedy with the help of an std: set data structure, whose underlying structure is a red-black tree. This implementation choice results in overhead during execution.
PLAID (Santhanam et al., 2022). Here, the indexing and retrieval methods are designed for inde- pendent top-K retrieval based on MaxSim score in Eq. (I). It offers multi-stage progressive pruning based retrieval, using multi- nulti-vector based IVF (Douze et al., 2024), similar to DISCo. PLAID's re- trieval engine is designed to offer significant speedups over the earlier ColBERT v v1/v2 (Santhanam et al., 2021; Khattab et al.. 2020) style retrievers. It achieves this by clustering corpus passages into a bag of centroids and their corresponding compressed residuals.
Before doing any exact query-corpus token interactions, PLAID performs MaxSim scoring these centroids to obtain a large pool of corpus items, and then prunes them according to a carefully cho- sen pruning threshold. It executes these operations using highly optimized CPU/CUDA runtimes, leading to 42.4x CPU latency drop and 6.6x GPU latency drop.
MUVERA (Dhulipala et al., 2024). It constructs fixedddimensional single vector encodings for Q and X, whose inner product e-approximates the MaxSim score (I), enabling single-vector based ANN for independent retrieval of top-K items. MUVERA generates these encodings by first hashing tokens into buckets, then performing a random projection to bring bucket vectors onto a specified dimension, and finally repeating this random sketch R times and concatenating the vectors. As result, the dimension of the encoding is dFDE = B x dproj X R, where B is the number of buckets, droj is the random projection dimension, and R is the number of repeats. B is obtained by setting the num s i mhash projects ons parameter, which gives us B 2 2 inhash.pro jections.
30

---

Published as a conference paper at ICLR 2026
We observe that the quality of their approximation depends drg.. Their experiments often use
20 = 12, 800. The MUVERA implementation provides an (optional) end-stage projection to control the final dimension size, which we leverage to obtain encodings of dimension 2560. The choices of dimensions and hyperparameters guided by the ablation experiments in their paper.
value of dEDE = 10, 240. In our experiments, we set to dEDE = 2 x 20
WARP (Scheerer et al., 2025). It optimizes a variant of the MaxSim score, enabling the filtering of corpus tokens ær that are highly dissimilar reduction process that yields substantial latency improvements over PLAID. This baseline makes use of finetuned T5 embedding model for its ranking, which we do not change. However, the coverage is computed using the BERT embeddings.
query token q. This is followed by a two-stage
WARP improves over XTR (Lee al.. 2023) by replacing XTR's token residual reconstruction with the following optimizations: (1) Dynamic similarity imputation, with which it estimates the similarity scores of large number of token-token pairs. (2) scoring using compressed residuals and avoiding residual decompression altogether, and (3) reducing the set of candidate passages and per- token final pairs before the last round of pooling. Additionally, the authors provide highly optimized C++ runtimes which contribute to x1x drop in latency.
Next, we describe our choice of submodular optimization solver in detail.
Submodular optimization solver: For the submodular solver baselines, we use the AacilityLocation solver class of the submodlib library (Kaushal et al., 2022). submodlib- based greedy programs adhere to two stage framework. In the first stage, for the given query, a full sweep across the corpus made to obtain pairwise scores for the similarity kernel. In the second stage, call is made to the submodlib API with the choice of optimizer (e.g. Lazy Greedy, Lazier-than-lazy Greedy, Stochastic Greedy), e' and the kernel matrix. Queries are processed in batches of 100 for the similarity computation. We note that the similarity computation contributes to significant speed bottleneck, as seen in Figure 2, and parallelizable algorithm for submodular optimization would be of great interest.
During initial testing, we discovered that the solution sets returned by Lazy Greedy were not matching with our Exact Greedy implementation. Additionally, Lazier-than-lazy Greedy and Stochastic Greedy were unable to perform even upto the level seen in Figure 2. Upon investiga- tion, it was found that their implementation assumes that the kernel matrix is meant to be accessed in a column-majo manner in memory. We fixed this bug by changing to the correct row-major access style. Subsequent tallying of results passed our correctness tests.
G.5 SYSTEM CONFIGURATION
All experiments were performed server with seven 48GB RTX A6000 GPUs. The server has a 96-core 1.5GHz AMD Epyc CPU running Debian13. Exact Greedy tensor operations were performed on GPU, were indexing and retrieval operations PLAID based architectures, such as WARP and DISCO. Greedy variations such as Stochastic Greedy, Lazy Greedy and Lazier-than-lazy Greedy were implemented using the submodlib (Kaushal al., 2022) library, and operations were performed on CPU.
31

---

Published as a conference paper at ICLR 2026
H ADDITIONAL EXPERIMENTS
In this section, we provide results for an extensive variety of additional experiments. Specifically, we provide additional results for the relevance of the coverage objective with respect to gold items, qual- ity of our proposed approximation to marginal gain, the tradeoff between coverage and efficiency with respect Exact Greedy, the need for early pooling in DISCo, and various configurations of the greedy algorithms, Additionally, we provide results on the tradeoff between coverage and the number of iterations K, variation of hyperparameters in DISCo, and set-wise comparison with the Exact Greedy solution.
Exact Greedy
#sumples R=1
#sumples I==
#samples R=3
#samples R=4
#samples R=5
Avg F(SK
22
20
24
15
20
22
10
4
6
10
2
4
6
10
2
6
8
10
K
(a) NFCorpus
(b) Writing
(c) SCIFact
Figure 13: Coverage obtained with our approximate marginal gain formulation under varying num- bers of random hyperplanes R. Our approximation of the marginal gain rapidly approaches the exact marginal gain skyline, with only small number of hyperplanes needed for near-optimal coverage.
H.1 QUALITY OF PROPOSED APPROXIMATION
We provide additional results the assessment of the quality of the marginal gain function Gwi (c. S, Q). Specifically, we compare the Exact Greedy algorithm (exact marginal gain at every iteration) its random ryperplane-augment R. Figure 13 reports the coverage achieved by each configuration. observe that as A increases, the quality of the marginal gain approximation improves and the coverage rapidly approaches that of Exact Greedy, which constitutes the skyline across datasets. Notably, only a modest number of hyperplanes is sufficient to close this gap, thereby justifying the design choice of using limited R in DISCO.
counterpart under varying numbers of hyperplanes
DISCo
Exact Greedy
Laxy Greedy
Stachastic Greedy
Loxier-than-lazy Grendy
MUVERA
WARP
PLAID
Avg F(SK:
25
25
22
22
20
20
20
10"
10a 10
10"
10a
10a
10a
10a 10
Efficiency
Efficiency
Efficiency
(a) Science
(b) Technology
(c) Writing
Figure 14: Analysis of tradeoff between coverage and efficiency on DISCO against state of the art baselines, across additional datasets from the LoTTE benchmark. DISCo continues to report superior coverage-efffcienccy tradeoff compared to the baselines. X-axis is log-scale and upper right corner is the best performing quadrant.
H.2 ENTERAGE-FFFICIRII TRADFOFF
We compare DISCO against the baselines on additional datasets from the LOTTE benchmark in Figure 14. We make the following observations: (1) DISCO continues to trade off between mean coverage and average query time more effectively. (2) For example, in the Technology dataset, DISCO at least 61x faster than the greedy variants, and at least 66x more efficient than them. (3) Exact Greedy and Lazy Greedy continue to dominate coverage, but prohibitively expensive compared to the indexing based methods. (4) Query agnostic randomized pruning continues to affect the performance of Stochastic Greedy and Lazier-than-lazy Greedy.
32

---

Published as a conference paper at ICLR 2026
DISCo
Exact Greedy
Lazy Greedy
Stochustic Greedy
Lazier-than-lazy Greedy
MUVERA
WARP
PLAID
Avg F(SK. Q
28
25
26
24
20
20
10
10
5
10
5
10
K
K
K
(a) MS ASs-Maroo
(b) Fever
(c) HotpotQA
(d) Pooled
25
Av% F(SK.
25
25
22
22
20
20
20
10
10
10
K
K
+
K + (g) Writiing
(c) Science
(f) Technology
Figure 15: Analysis of coverage in terms of the upper bound K on the size of solution set S, i.e., |S| < K. We vary K from 1 to 10. Exact Greedy and Lazy Greedy provide skyline values, while DISCO consistently outperforms all other baselines.
H.3 COVERAGE VS K
Here we analyze the performance of DISCO against the baselines in terms coverage and the value of the upper bound K on the size of the solution set S, We provide results on the MS-Marco, Fever, HotpotQA and Pooled datasets. Note that these results are independent of the time taken by any method. Figure 15 summarizes the results. Our observations datasets, Exact Greedy and Lazy Greedy dominate over the rest of the methods. This is explained by the fact that both methods maximize the exact marginal gain the already chosen items. This is in contrast to Stochastic Greedy and Lazier-than-lazz Greedy, which sample reduced subset of the corpus to evaluate and select the next best element at each iteration. (2) DISCO is consistently the next best performer. It outperforms Stochastic Greedy and Lazier-than-lee -lay Greedy amongst the greedy variations, and also outdoes the other indexing based methods such as PLAID, MUVERA and WARP. (3) PLAID is able to outperform WARP on at least three datasets, despite WARP being an extension of PLAID meant for better performance. We conclude that WARP is optimized for independent top-K retrieval. (4) MUVERA, despite having been developed as an efficient single-vector MIPS approximator to multi-vector search, unable to perform in the collaborative retrieval setting.
as follows. (1) In each of the
the entire corpus set, minus
Pool, n
Pool
F(Sk @
25
25
25
23
24
24
24
23
23
250 500
750 Efficiency +
500
1000
250
500
750
2000 Efficiency +
1000
Efficiency -
Efficiency +
(a) Fever
(b) HotporQA
(c) Technology
(d) Writing
Figure 16: Ablation study to justify the architectural choice of early pooling. DISCO achieves superior coverage-efffiiencc tradcoff against the late pooling basclines.
H.4 ABLATION STUDY ON NEED FOR EARLY POOLING
We provide further results demonstrating the need for early pooling within the DISCO end-to-end retrieval pipeline. In particular, we compare DISCO with its late pooling ablations on the Fever, HotpotQA, Technology, and Writing datasets. Recall that in the late pooling variants, the R pro- jected queries "... (qs) are processed independently via ColBERT, with each replica producing its own top-n' candidates-wif which are merged and reranked according exact marginal gain the
33

---

Published as a conference paper at ICLR 2026
erage objective F(c) Q). Early pooling is the method of choice across all datasets, achieving superior noverage-efficinng tradeoff compared to the ablations. Figure 16 summarizes the results. We observe that among the late pooling baselines, the variant with n' 20 attains the best cover- age, while other curves converge toward this ceiling, but all remain below the performance of early pooling.
DISCo
DISCo (w=100)
DISCo (n==15)
Avg F(Sx Q)
28
26
25
25
23
24
23
27
500
1000
250
500
750
500 Efficiency
1000
250
500
750
Efficiency
->
Efficiency ->
Efficiency -
(a) MS-Marco
(b) Fever
(c) HotpotQA
(d) Pooled
Figure 17: Ablation study on the effect of n' on the performance of DISCO. While higher n' provides absolute gains in coverage, this comes with a drop in efficiency. This result justifies the use of the default setting in our experiments involving DISCO.
H.5 ABLATION STUDY ON VARYING n' FOR DISCO
In this experiment, vary the n' hyperparameter for DISCO-number of top document candidates we retain after the residual scoring step and before the full-precision scoring. We test on four datasets, viz., MS- Mar-Mo,,,, Fever, HotpotQA and Pooled. Figure summarizes the results. It can be observed that the default DISCO (n' = 1) trades off coverage for efficiency. As we increase n', we achieve gains in coverage. In the case Fever and HotpotQA, the default DISCo configuration provides a better coverage-efficiency curve, while in the case of MS-Marco, n' 10 is the better performing outlier.
H.6
GREEDY ALGORITHM VARIATIONS
thaser-thannlazyy Greedy,
Lasicr-thun-lazy Greedy. Stochastic Greedy,
Stochastic Greedy.
Greedy 0.5
Stochustic Greedy é
27
25
25
25
20
20
20
15
3
7
10
3
10
5
10
3
7
10
L'ficiency
Efficiency
Etficiency (c) HotpotQA
Efficiency +
(a) MS-Marco
(b) Fever
(d) Pooled
Avg. F(SK, Q
25
25
25
20
20
20
1 3 5 Efficiency ->
7 10
3
5
7
10
3
10 Efficiency +
5 7
Efficiency + (f) Technology
(c) Science
(g) Writing
Analysis of coverage-efficiency tradeoffs for Lazier-than-lazy Greedy and Stochastic Greedy for varying e'.
Figure 18:
In Figure 18, provide insights into the performance of Lazier-than-lazy Greedy and Stochastic Greedy across varying e'. We find that Stochastic Greedy achieves the best coverage at e' 0.1, followed by method is dominated by the time to compute the similarity kernel, which results in similar efficiency tradeoffs across all methods.
Greedy at e' 0.1. The per-query time taken by each
34

---

Published as a conference paper at ICLR 2026
DI&Co Laxiee-Fhann-aayy Groady
Exact Greody
Lazy Groedy
Stochastic Greedy
Number of Queries
Number of Queries
50
50
25
2
Rank of Last Relevant Item Retrieved
Rank of Last Relevant Item Retrieved
Fever
(h) Science
Figure 19: Histogram of the rank of the last (1S -th) true relevant item
H.7 COVERAGE OBJECTIVE ON GOLD SET OF ITEMS
We extend the experiment on measuring and comparing the coverage objective the given gold set of items with solutions sets obtained by other methods. Specifically, we provide results on the Fever and Science datasets. We operate on those queries which have least two relevant documents the corresponding corpus. The gold set of corpus items for each query is capped at the top two items according to the marginal gain obtained on our coverage function. Figure 19 summarizes the results. We observe that across datasets, PLAID outperforms other methods at gold set retrieval. This is due the fact that the gold sets on these datasets are meant to be used for independent top- K retrieval. HotpotQA is the exception, and this is because it is multi-hop dataset amenable to collaborative retrieval.
I ADDITIONAL EXPERIMENTS DURING REBUTTAL
Here, provide consolidated report of the experiments conducted during the rebuttal, as well as any clarifications about our pipeline and the datasets.
I.1 ADDITIONAL PERFORMANCE MEASURES
In this section, we expand our evaluation in the style of HotpotQA, to two more question-answering style datasets, namely 2WikiMultihopQA (Ho et al., 2020) and Musique (Trivedi et al., 2022). In addition to MAP on the gold labels, we also evaluate the set selection quality using three standard set-overlap metrics. For each query g. let S denote the ground-truth pseudo-relevant set and S,, the size-K set selected by the method under budget K. We report:
Subset Recall K, also called perfect recall fully contains the ground-truth set: S C Sq.K.
the fraction of queries for which the selected set
[stns, [.
Precision@ K, the average proportion of selected items that are relevant:
Recall K, the average proportion of relevant items recovered: [s
Together, these metrics capture both strict containment performance (subset recall K) and standard pveraap-bssed retrieval quality (precision @ K and recall @ K).
Dataset
DISCo
Exact Greedy
Lazy Greedy
PLAID
WARP
2WikiMultiHopOA
0.90
0.91
0.91
0.89
0.82
Musique
0.64
0.66
0.66
0.61
0.50
Table 20: Mean Average Precision (MAP).
Dataset
DISCo
Exact Greedy
Lazy Greedy
PLAID
WARP
2WikiMultiHopQA
0.26
0.27
0.27
0.22
0.19
Musique
0.09
0.10
0.10
0.08
0.06
Table 21: Subset Recall @K: K: fraction of queries where S C Sg
35

---

Published as a conference paper at ICLR 2026
Dataset
DISCo
Exact Greedy
Lazy Greedy
PLAID
WARP
2WikiMultiHopOA
0.34
0.35
0.35
0.32
0.31
Musique
0.23
0.23
0.23
0.20
0.17
( 1
Table 22: Precision @K: K:
Dataset
DISCo
Exact Greedy
Lazy Greedy
PLAID
WARP
2WikiMultiHopQA Musique
0.60
0.61
0.61
0.57
0.55
0.41
0.42
0.42
0.37
0.32
( [5;]
Table 23: @ecall @:
In Tables 20, 21, 22, and 23, we note that DISCo performs closely wrt the greedy baselines and outperforms the IR baselines PLAID and WARP, We also note that per-query basis, DISCo takes 153.86 seconds on 2WikiMultihopQA and 42 seconds on Musique, whereas Exact Greedy takes (89.71 seconds on 2WikiMulthhoQQA and 73 seconds Musique, leading to speedups of 1.23x and 1.73x respectively.
1.2
COVERAGE OF GOLD ITEMSETS FOR QA DATASETS
DISCo Lazicr- lazy Greedy
Exact Groody
Lazy Greedy
Stochastic Greedy
Number of Queries
Number of Queries
2000
5000
1000
4
5
2
3
Rank of Last Relevant Item Retrieved (a) 2WikiMulthhoPAA
Rank of Last Relevant Ttem Retrieved
(b) Musique
Figure 24: Histogram of the rank of the last (|Sgotal-thh -th) true relevant item for the new QA datasets.
Left: 2WikiMulthopQAA. right: Musique.
We analyze the ranking of the last relevant item across all methods by plotting a histogram of the position of the last gold retrieved item. Note that low value of the rank is better then all items in Syold are retrieved within a small cutoff value K. Figure 24 shows the results: DISCO more frequently retrieves all the gold documents within the top 2-3 positions, performing closely wrt Exact Greedy and Lazy Greedy, whereas IR methods such as MUVERA, PLAID, and WARP more frequently place the last relevant item at lower ranks.
I.3 PERFORMANCE ON BRIGHT BENCHMARK
Figure 25 shows the trade-off between average coverage objective FK and the efficiency with re- spect Exact Greedy. These tradeoffs are obtained by varying the subset size K. We note that DISCo achieves the most balanced tradeoff compared the other basclines. DISCo is also vastly more efficient than the greedy baselines (Exact Greedy, Lazy Greedy, etc.). Amongst the IR base- lines, PLAID and WARP compete with each other, with PLAID outperforming WARP on the first two datasets, and WARP doing so on the other two.
1.4 COMPARISON WITH COLBERTV2 AND SPLADE
Figure 26 details the trade-off between average coverage objective F'x and the efficiency with spect to Exact Greedy, on a limited subset of the baselines. The key focus is on DISCo's per- formance in comparison to ColBERTv2 (Santhanam et al., 2021) and SPLADE (Formal et al., 1021). We observe that DISCO provides higher quality tradeoffs compared to both ColBERTv2 and SPLADE. Amongst the other IR baselines, ColBERTv2 and PLAID often perform closely wrt
36

---

Published as a conference paper at ICLR 2026
DISCo
Lazier-than-len Greedy
Lazy Greedy WARP
PLAID
Exact Greedy
MUVERA
Avg F(SK, Q)
22
20
20
20
17
15
15
10" 10- 10" 10" Efficiency
10" 10 10a
10"
10" 10-
10"
10"
10a 10' 10" 10
>
Efficiency
Efficiency >
Efficiency
(a) Biology
(b) Stackoverflow
(c) Sustainable Living
(d) Robotics
Figure 25: Trade off between efficiency and average coverage objective of DISCO and a subset of sfate-of-the-ar baselines on four datasets: (a) Biology, (b) Stackoverflow, (c) Sustainable Living, and (d) Robotics.
datasets were chosen from the Bright benchmark. DISCO achieves the best trade-off in three datasets, and the best coverage in Stackoverflow against the IR baselines, where the next efficient performer is low on coverage. Efficiency is in log-scale. Upper right corner the
best quadrant.
DISCO
MUVERA
WARP
V SPLADE
Exact Greedy
Lazy Greedy
PLAID
Avg F(Sk; Q
25
20
25
20
22
20
10
10"
10
10"
10a
10
10
10a Efficiency +
10
10
10"
10
E'ficiincy
Efficiency +
Efficiency +
(a) MS-Marco
(b) HotpotQA
(c) Fever
(d) Pooled
Figure 26: Trade off between efficiency and average coverage objective of DISCO and subset of the state-of-the-art baselines four datasets: (a) MS-Marco, (b) HotpotQA, (c) Fever, and (d) Pooled. DISCO achieves the most balanced trade-off, and is able to outperform both new baselines: ColBERTv2 and SPLADE. Upper right corner is the best quadrant.
each other, while WARP and SPLADE are the next best performers. Notably, SPLADE is unable to achieve coverage on MS-Marco, which contains the largest corpus out of the four datasets.
1.5 FURTHER CLARIFICATION ON THE GOLD SETS OF HOTPOTQA
Here, reply to the reviewer's concerns about why HotpotQA's gold sets differ from that of the other datasets's.
BEIR (Thakur al., 2021) collects diverse datasets into single retrieval benchmark, eliding fine distinctions in the semantics of their relevant item subsets. HotpotQA (Yang et al., 2018) is a multi- hop question answering dataset, which was absorbed into BEIR in order test zero-shot retrieval. In the original setting, each instance within a split (train/dev/test) contained query, supporting passages (some of which were relevant and some were "distractors"), a list of candidate answers and the gold answer. Each query required reasoning over all the relevant supporting facts to obtain the answer. An example of such a query is "The mulga apple is often eaten by people who genetic research has inferred date of habitation as early as when?". This query requires understanding what a mulga apple is, what kinds of people ate them often according to researchers, and when these apple-eaters inhabited the Earth.
When it was repurposed into the BEIR benchmark, the set of queries was kept as-is, while an in- dependent corpus was constructed using Wikipedia. The multi-hop reasoning nature of the dataset remains even in its IR reformation. This distinguishes from other datasets the BEIR benchmark, such FEVER and MSMarco
1.6 ON HANDLING UPDATES THE CORPUS EFFICIENTLY
The topic of efficient corpus updates has practical significance for a wide variety of indexes and vec- tor databases. Updating classical posting bistd inverted indexes involves complex engi- neering, as outlined Chapter 7 of BCC's text on search engines and information retrieval (Büttcher al., 2016). Clustered-IVF--tyy dense indices be updated for while by inserting modified
37

---

Published as a conference paper at ICLR 2026
postings into their lists facing much the same impediments to posting-list compression lexical inverted indexes-bute over time the stale clustering may cause hotspots and require reclustering. Most relevant system-optimization issues are covered in the classic BCC (Büttcher et al., 2016) text. This question encompasses most dense indexes and is not limited to DISCo, and would be an in- triguing avenue of future work, but it is far beyond the scope of set retrieval from an unchanging corpus, which itself poses significant challenges that our work addresses.
One way of incorporating new insertions the corpus without having perform the entire indexing process from scratch is to perform a virtual insertion during retrieval, i.e. during the replica-level centroid pruning process (Section 3.4). Across each of the r 1 to R replicas of the index, we compute the similarity of the new item c' (using its corresponding embeddings) with the centroids {o b, 1b=1 where the number of clusters. The item e' is assigned to the cluster corresponding to the highest similarity. Thereafter, pruning and subsequent operations can be executed as usual.
The above solution depends on the volume of inserts being executed within a period of time. For a higher volume of insert operations, more suitable data structures need to be employed. One example of such a data structure a log structured merge tree (LSM), which writes updates to a primary memory buffer before flushing all of them to an immutable file in secondary memory. Other engi- neering techniques include batching updates, index versioning and snapshotting.
1.7 ON THE USE OF MAP IN QA-STYLE DATASETS
We have included diseussion this matter in Section after "Evaluation setting, coverage and efficiency". We present an elaboration here.
Of all corpus subsets, there is a gold subset S". Ideally, a set ranking system would return sets S2.... in the order of "improving approximation" to S In practice, a retrieval system will generally rank items, not subsets. Suppose the items are ranked æ ø2..... we include the first K items in the system output, i.c., Sk- = {-I..... zx J. then there is clear motivation for using MAP: the gold target is set, and the system outputs a ranked list.
Note that (although its name includes 'precision' and not 'recall') MAP does take recall into account because averages precision up to the position of the last relevant item from S For downstream "reasoning" applications such as RAG for multi multi-passag passage QA, retrieving the whole of S* is usually mandatory for correctness, possibly by setting K to be sufficiently large. This renders MRR unac- ceptable as an evaluation measure, because MRR is content to track the rank of just the first ranked item from S*. NDCG does not care about recall of all of S either. It is oblivious to loss of recall beyond its top-K K horizon.
One might argue that the differential treatment MAP accords to the relevant items is misplaced for downstream set consumers, in which case, we measure recall and precision at K usual, aver- aged over queries. We could also measure the average (over queries) rank at which S* is completely recalled, or the fraction of queries where succeed at recalling all of S at rank K. These important from the "lost in the middle" perspective.
We feel in our context, where retrieving entire set S is erucial, MAP is more appropriate than both MRR and NDCG. Also of interest is the last rank where a relevant item is recalled, because it is proxy for the (substantial) energy consumed by an LLM when the retrieved subset is presented its context. We also evaluated selection quality using three standard set-overlap metrics as described in Appendix I.1.
1.8 ON THE PERILS OF PSEUDO-LABEL GENERATION
To evaluate using gold labels on non-QA datasets such as MSMarco and Fever, we prompt Qwen2.5- 14B-Instruct LLM to obtain pseudo-labels for these datasets. However, we find that the quality of the labels obtained is not satisfactory, and this leads to a severe degradation in metrics across all methods, not just DISCo. As an example, for the query "Ed Decter only has citizenship in China." from the Fever dataset, the LLM labels passage about the WCHA's Ice Hockey tournament gold item. Ed Decter is an American film director and has no relation to ice hockey. Thus, we avoid the use of pseudo-labels in our work.
38

---

Published as a conference paper at ICLR 2026
1.9 ON DOWNSTREAM TASK EVALUATION (QUESTION- (QUESTION-ANSWERING) ANSWERING)
We agree that it would be useful assess the performance of DISCo on a downstream task such as question answering. To this end, we select two question answering datasets - -WikiMulthhoPQA (Ho al., 2020) (abbreviated 2Wiki) and Musique (Trivedi et al., 2022). We process these datasets for sirst-stage retrieval, second-stage answering as follows.
For each sample present in the train and dev splits of these datasets, we collect the union of the corresponding supporting facts and generate the corpus. In the case of 2Wiki, this leads to 384,771 unique corpus items and for Musique, 84,453 unique items. Next, we mark the gold corpus items for each query as the ground-truth supporting facts used to answer that query. In the case of 2Wiki, we sample 20K queries u.a.r from the combined train and dev splits, while in the case of Musique, we have 22,355 queries. In the first stage, DISCo retrieves the top-K corpus fact-set for each query according to our coverage score. In the second stage, we prompt the Qwen2.5- 55-145 4n-Inust LLM to answer the question given the set of retrieved facts only (i.e., without using world knowledge).
We vary K = 3, 5, 10 across both datasets, and tabulate our results below.
Avg Exact Match (EM)
K = 3
K = 5
K
10
2Wiki Musique
0,43
0.45
0.45
0.10
0.11
0.11
Table 27: Average EM scores for 2WikiMultihopOA and Musique.
Avg F1 Score
K = 3
K = 5
K = 10
2Wiki Musique 0.13
0.44
0.45
0.46
0.15
0.16
Table 28: Average Fl scores for 2WikiMultihopQA and Musique.
We find that with increasing K, the performance of the LLM improves marginally, indicating the difficulty it faces on dealing with the questions present in both datasets. For example, 2Wiki has four different kinds of questions presenting with varying difficulty (see Table 3 in the 2iii paper). On the other hand, all the queries in Musique are of the kind "Which major Russian city borders the body of water in which Saaremaa is located?"' and require multiple hops through the corpus to be answered correctly. As result, while the LLM is able to obtain decent scores on 2Wiki, it is not able to do so on Musique.
Another aspect which adds to the complexity is the fact that the L.MM is expected to answer in free-form. No list of candidate answers is given, which renders grounding of the LLM difficult.
I.10 ON THE CONVERGENCE OF APPROXIMATION OF MARGINAL GAIN AND TRUE GREEDY GAIN
We provide an estimate of the error between the true marginal gain (from greedy) and our approx- imated marginal gains given number of hyperplanes R, across three datasets. In each of the tables, the first column lists which iteration it we're computing the marginal gain error for. the remain- ing columns, we vary R = 1 to 5 and list the gain error. We find that with modest increase in R, the approximated marginal gain and the true greedy gain converge, as desired.
39

---

Published as a conference paper at ICLR 2026
K K-*K+1
R=1
R=2
R=3
R=4
R=5
1-22
0.32
0.08
0.05
0.00
0.00
2-+3
0.72
0.03
0.27
0.00
0.00
3-+4
0.75
0.04
0.10
0.00
0.00
4-+5
0.77
0.08
0.00
0.00
0.00
5-+6
0.65
0.01
0.00
0.00
0.00
6-47
0.47
0.00
0.00
0.00
0.00
7-8
0.09
0.00
0.00
0.00
0.00
8-49
0.06
0.00
0.00
0.00
0.00
90010
0.05
0.00
0.00
0.00
0.00
Table 29: Marginal gain error for NFCorpus
K K+
R=1
R=2
R=3
R=4
R=5
1-22
0.80
0.38
0.00
0.00
0.00
2-33
0.31
0.31
0.31
0.31
0.02
3-+4
0.65
0.22
0.14
0.18
0.03
4+5
0.26
0.22
0.00
0.00
0.00
5-
0.02
0.03
0.00
0.00
0.00
6-+7
0.13
0.04
0.00
0.00
0.00
7-88
0.01
0.02
0.03
0.00
0.00
8-9
0.14
0.03
0.00
0.00
0.00
9-10
0.16
0.06
0.00
0.00
0.00
Table 30: Marginal gain error for SciFact
K++
R=1
R=2
R=3
R=4
R=5
1-2
0.93
0.24
0.14
0.08
0.00
2-33
0.70
0.00
0.00
0.00
0.00
3-+4
0.15
0.03
0.00
0.01
0.00
4+5
0.03
0.03
0.00
0.01
0.00
5-46
0.02
0.02
0.01
0.02
0.00
6-77
0.01
0.01
0.00
0.00
0.00
7-48
0.03
0.02
0.02
0.00
0.00
8-49
0.03
0.02
0.01
0.01
0.00
900
0.03
0.01
0.00
0.00
0.00
Table 31: Marginal gain enror for Writing
40


Reviews:
[{"review_id": "zWQWGYWHGV", "reviewer": "Reviewer_htMi", "summary": "This paper proposes a novel reformulation of the classical task of information retrieval. While traditional IR is optimized for selecting a single \"best\" document out of a corpus of choices, the authors note that these techniques are ill-suited for modern, reasoning intensive retrieval tasks such as multi-hop question answering. \n\nTo address this challenge, the authors propose to reframe retrieval as a set coverage problem and cast the task of finding the item that maximizes the marginal gain of query coverage as a multi-vector retrieval task. The authors implement their proposed pipeline in a system called DISCo which achieves significantly improved query-latency tradeoff metrics over a host of established retrieval baselines.", "questions": "1. Can you provide more clarification on the \"gold set\" of hotpotqa? Why is this different from the other benchmark datasets used in the experiments section?\n\n2. Can you consider evaluating DISCo on the [Bright Benchmark](https://arxiv.org/pdf/2407.12883) and possibly other related reasoning-intensive retrieval benchmarks?\n\n3. Do existing methods handle updates to the corpus efficiently? How would you assess this limitation of your method in relation to the existing literature?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a novel retrieval algorithm that achieves improved performance on reasoning-intensive retrieval tasks by creatively combining submodular optimization with multi-vector retrieval. While none of the components of the authors' proposed architecture is entirely novel, the combination of these techniques is original and appears to achieve state-of-the-art performance across a number of standard retrieval baselines in this area. The authors' proposed technique is also principled and they also provide a number of theoretical guarantees. The paper is also very well-written and motivates the problem well.", "weaknesses": "1. While the baselines considered in the experiments is quite thorough, the claims in the paper might be better supported by considering additional retrieval benchmarks specifically tailored towards challenging retrieval-intensive tasks, such as the recently introduced [Bright Benchmark](https://arxiv.org/pdf/2407.12883). Evaluating on benchmarks specifically designed for reasoning-intensive tasks (as opposed to more generic retrieval like BEIR) might be a more natural fit for this paper and might help us better understanding the strengths and limitations of the DISCo method. \n\n2. The paper is well-written but I found it a bit hard to understand how all the pieces fit together on a first read through the paper. The authors might want to consider adding a schematic diagram or conceptual figure to aid in communicating their methodology. \n\n3. I think the main body of the paper could benefit from a dedicated section discussing the relevant related work (especially in introducing the baseline methods evaluated later in the experimental section). \n\n4. The authors could also make their theoretical contributions more clear by perhaps introducing informal statements of the theorems they prove instead of relegating all of this content to the appendix (which readers may not read and thus never find).", "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": "3OM3Vdzu23", "reviewer": "Reviewer_qUAz", "summary": "The paper correctly recognizes that many ranking algorithms rank items independently of one another, so that important aspects of query coverage may be missed if only the top K items are retrieved. This is absolutely true and further study on this problem is definitely worthwhile, especially from the perspective of modern dense retrieval.\n\nUnfortunately, this work appears to have been conducted in a bit of a vacuum, without any clear consideration of the huge volume of prior work in this area, especially related work on learning to rank for web search. The section on monotonicity, submodularity, and greedy maximization could have be lifted without change from a paper appearing 10 or more years ago. I included a bunch of examples below.\n\nI also have concerns about the evaluation. For coverage, only HotpotQA has gold labels, which limits the evaluation. However, there are various methods for employing LLMs to generate pseudo-labels. While it's not exactly what you want Ragnarok (https://arxiv.org/abs/2406.16828) can probably be adapted to extract nuggets for coverage.\n\nMAP is very strange measure to use on these collection. NDCG and MRR are more standard.\n\nRodrygo L.T. Santos, Craig Macdonald, and Iadh Ounis. 2010. Exploiting query reformulations for web search result diversification. In Proceedings of the 19th international conference on World wide web (WWW '10). Association for Computing Machinery, New York, NY, USA, 881–890. https://doi.org/10.1145/1772690.1772780\n\nCheng Xiang Zhai, William W. Cohen, and John Lafferty. 2003. Beyond independent relevance: methods and evaluation metrics for subtopic retrieval. In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval (SIGIR '03). Association for Computing Machinery, New York, NY, USA, 10–17. https://doi.org/10.1145/860435.860440\n\nJun Xu, Long Xia, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. 2017. Directly Optimize Diversity Evaluation Measures: A New Approach to Search Result Diversification. ACM Trans. Intell. Syst. Technol. 8, 3, Article 41 (May 2017), 26 pages. https://doi.org/10.1145/2983921\n\nLearning for Search Result Diversification. Yadong Zhu Yanyan Lan Jiafeng Guo Xueqi Cheng Shuzi Niu\n\nThese are just random papers that popped to mind. I think there was some good work by Olivier Chapelle but all I can find is this workshop paper: Paul N. Bennett, Ben Carterette, Olivier Chapelle, and Thorsten Joachims. 2008. Beyond binary relevance: preferences, diversity, and set-level judgments. SIGIR Forum 42, 2 (December 2008), 53–58. https://doi.org/10.1145/1480506.1480516\n\n*Note that the last one is 2008*", "questions": "Can you clarify the connection to past work?\n\nCan you defend the limitations in the evaluation raised in the summary?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The topic is important, and the theory seems correct. I think there are novel aspects, and certainly a version of this paper should be published at some point. \n\nThe focus on efficiency is good to see.", "weaknesses": "What I said in the summary: There's a huge thread of similar work that has been ignored. The evaluation is not appropriate to the problem.", "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": "BFH8MeWdyN", "reviewer": "Reviewer_8Q8D", "summary": "The paper introduces DISCO, a dense retrieval method that selects a subset of documents optimised for query token coverage. Unlike typical top-K retrieval, DISCO selects documents whose embeddings collectively maximise coverage over the query’s token embeddings. The method formalises this as a monotone submodular objective, allowing for a greedy approximation. It then proposes a practical approximation using random projections and a lifted representation, making the approach compatible with ANN search. The authors implement a multi-vector IVF index and show strong empirical performance in terms of coverage and latency on multiple datasets.", "questions": "1. Have you tested DISCO in a full downstream setting, such as QA or claim verification, where it serves as the first-stage retriever? It would be useful to know whether the observed coverage improvements actually lead to gains in final task metrics like accuracy or F1.\n\n2. The current baseline set is helpful, but it would be good to understand how DISCO compares to more recent retrieval methods that consider token-level signals or diversity—such as ColBERTv2, GRIP, or SPLADE-style models. Even a brief discussion of these alternatives would help situate the contribution.\n\n3. The approximation strategy for estimating marginal gains is clearly explained, but it would be helpful to see some empirical check on how closely it matches the true greedy gain. For instance, do the approximated and true gains result in similar document rankings or coverage values?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Clear motivation: The paper addresses limitations of independent ranking in multi-hop and multi-evidence tasks.\n\n2. Sound theoretical foundation: The coverage objective is well-defined, submodular, and optimisable via greedy selection.\n\n3. Efficient approximation: The use of lifted representations and random projections to estimate marginal gains is novel and effective.\n\n4. Strong empirical results: On benchmarks like HotpotQA and FEVER, DISCO demonstrates significant latency gains and higher coverage compared to both greedy and top-K baselines.\n\n5. Implementation quality: The multi-stage index is well engineered and extensively ablated.", "weaknesses": "1. Lack of downstream evaluation: The paper does not assess end-to-end improvements in downstream tasks such as QA or claim verification. All results focus on coverage and latency.\n\n2. Limited comparative breadth: The baseline comparisons could be broadened to include recent token-aware or set-aware retrieval methods.\n\n3. Unvalidated approximation behaviour: While the greedy coverage algorithm has known guarantees, the practical approximation introduced by DISCO is not empirically analysed against true marginal gains.", "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)