Principled and Scalable Diversity-Aware Retrieval via Cardinality-Constrained Binary Quadratic Programming

Qiheng Lu; Nicholas D. Sidiropoulos

cs.CLApr 2, 2026

Principled and Scalable Diversity-Aware Retrieval via Cardinality-Constrained Binary Quadratic Programming

Authors: Qiheng Lu, Nicholas D. Sidiropoulos

Organizations: University of Virginia Charlottesville, VA 22904, USA

Abstract

Diversity-aware retrieval is essential for Retrieval-Augmented Generation (RAG), yet existing methods lack theoretical guarantees and face scalability issues as the number of retrieved passages $k$ increases. We propose a principled formulation of diversity retrieval as a cardinality-constrained binary quadratic programming (CCBQP), which explicitly balances relevance and semantic diversity through an interpretable trade-off parameter. Inspired by recent advances in combinatorial optimization, we develop a non-convex tight continuous relaxation and a Frank--Wolfe based algorithm with landscape analysis and convergence guarantees. Extensive experiments demonstrate that our method consistently dominates baselines on the relevance-diversity Pareto frontier, while achieving significant speedup.

Figures & tables

Panel of Figure 1 — Figure 1: Relevance-diversity trade-off and efficiency. Relevance-diversity trade-off and computational efficiency on ASQA and QAMPARI across $k\in\{25,50,100\}$ . The left panels show the Pareto frontier of Recall vs. ILAD by modulating the trade-off parameter $\theta\in[0.1,0.9]$ . The right panels report the per-query wall-clock latency (ms). Our algorithm consistently yields superior subset quality and significant speedup.

Method	$\boldsymbol{\theta}$	$\boldsymbol{k=25}$					$\boldsymbol{k=50}$
Method	$\boldsymbol{\theta}$	P	R	F1	R $\geq$ 0.8	F1 $\geq$ 0.5	P	R	F1	R $\geq$ 0.8	F1 $\geq$ 0.5
Top- $k$	—	0.2196	0.2134	0.1824	0.0600	0.1140	0.2032	0.2423	0.1847	0.0770	0.1200
MMR	0.6	0.1777	0.1481	0.1327	0.0340	0.0570	0.1618	0.1692	0.1356	0.0430	0.0660
	0.7	0.1913	0.1899	0.1579	0.0560	0.0880	0.1759	0.2225	0.1650	0.0670	0.0980
	0.8	0.1985	0.2169	0.1738	0.0710	0.1040	0.1849	0.2487	0.1752	0.0860	0.0950
	0.9	0.2220	0.2224	0.1860	0.0680	0.1230	0.1974	0.2477	0.1826	0.0860	0.1100

Table 1: End-to-end generation results on QAMPARI. The downstream LLM generation quality across

k\in\{25,50\}

and

\theta\in\{0.6,0.7,0.8,0.9\}

. P, R, and F1 denote instance-level precision, recall, and F1 score, respectively. R

\geq

0.8 and F1

\geq

0.5 indicate the proportion of queries achieving a recall of at least

0.8

or an F1 score of at least

0.5

. Notably, our algorithm with

\theta=0.9

consistently achieves the highest overall F1 score across both subset sizes.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Method	$\boldsymbol{\theta}$	$\boldsymbol{k=25}$		$\boldsymbol{k=50}$
Method	$\boldsymbol{\theta}$	Recall	Recall=1.0	Recall	Recall=1.0
Top- $k$	—	0.4819	0.2099	0.4746	0.2120
MMR	0.6	0.4136	0.1646	0.4239	0.1614
	0.7	0.4507	0.1867	0.4591	0.1888
	0.8	0.4795	0.2173	0.4789	0.2131
	0.9	0.4947	0.2226	0.4722	0.2120

Appendix

Table 2: End-to-end generation results on ASQA. The downstream LLM generation quality across

k\in\{25,50\}

and

\theta\in\{0.6,0.7,0.8,0.9\}

. Recall=1.0 indicates the proportion of queries achieving a recall of 1.0.

Frank-Wolfe Algorithms

See all 12 papers

Finding the Right Balance: Relevance and Diversity in LLM Retrieval
Oct 7, 2026Guillaume Brouillette, Faustin Kagabo, Usef Faghihi +1Information Retrieval Retrieval-Augmented Generation
Université du Québec à Trois-Rivières, Trois-Rivières, Canada
Retriever Portfolios: A Principled Approach to Adaptive RAG
May 29, 2026Miltiadis Stouras, Vincent Cohen-Addad, Silvio Lattanzi +1Retrieval-Augmented Generation Adaptive RAG
1EPFL · 2Google Research
Know Before You Fetch: Calibrated Retrieval-Budget Allocation for Retrieval-Augmented Generation
Jun 29, 2026Zhe Dong, Fang Qin, Manish Shah +1Retrieval-Augmented Generation Selective Prediction
University of Maine at Presque Isle · Stanford University · Independent Researcher

Oct 7, 2026J/K move · Enter open · S save

Finding the Right Balance: Relevance and Diversity in LLM Retrieval

Guillaume Brouillette, Faustin Kagabo, Usef Faghihi, Nadia Ghazzali

Université du Québec à Trois-Rivières, Trois-Rivières, Canada

Information Retrieval Retrieval-Augmented Generation Evidence Retrieval

Open paper AskPDF arXiv

Retrieval diversification is widely available in retrieval-augmented generation (RAG) frameworks, yet prior studies disagree on whether it improves retrieval and answer quality. We show that its effectiveness varies primarily with candidate-pool redundancy, in a pattern consistent with the number of distinct evidence pieces a query requires. Using controlled near-duplicate injection and production-style overlapping chunking, we find that diversification harms relevance, evidence coverage and answer quality on clean pools, but becomes beneficial on multi-evidence tasks when redundancy causes nearest-neighbor retrieval to select repeated passages. We therefore introduce a query-adaptive rule that diversifies only when the effective number of distinct documents in the nearest-neighbor top-

k

selection falls below the query's evidence requirement. Computed from existing embeddings, the rule captures most of the achievable gain, transfers across datasets and encoders and automatically reduces to nearest-neighbor retrieval for single-evidence queries. We also introduce RNG-Score, a geometric reranker with an exact nearest-neighbor fallback whose margin indicates duplicate structure. Overall, we conclude that diversification should be used selectively, based on observable redundancy and evidence requirements.

Abstract

Frank-Wolfe Algorithms

Explore similar work

Finding the Right Balance: Relevance and Diversity in LLM Retrieval

Retriever Portfolios: A Principled Approach to Adaptive RAG

Know Before You Fetch: Calibrated Retrieval-Budget Allocation for Retrieval-Augmented Generation