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

arXiv: https://arxiv.org/abs/2604.02554 · HTML: https://mlsanity.com/paper/2604.02554/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RAG robustness and adaptive retrieval, one of 15 directions in Retrieval-augmented generation.
- Builds on 15 of its 36 references that are in the map.
- First posted on arXiv 2 Apr 2026.

## Placed in

- Retrieval-augmented generation / [RAG robustness and adaptive retrieval](https://mlsanity.com/rag/rag-robustness-and-adaptive-retrieval/)

## Builds on (most cited first, 15 of 15)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [M3-Embedding: Multi-Linguality, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation](https://mlsanity.com/paper/2402.03216/) (2024)
- [How Contextual are Contextualized Word Representations? Comparing the Geometry of BERT, ELMo, and GPT-2 Embeddings](https://mlsanity.com/paper/1909.00512/) (2019)
- [ASQA: Factoid Questions Meet Long-Form Answers](https://mlsanity.com/paper/2204.06092/) (2022)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [QAMPARI: An Open-domain Question Answering Benchmark for Questions with Many Answers from Multiple Paragraphs](https://mlsanity.com/paper/2205.12665/) (2022)
- [Conditional Gradient Methods](https://mlsanity.com/paper/2211.14103/) (2022)
- [DF-RAG: Query-Aware Diversity for Retrieval-Augmented Generation](https://mlsanity.com/paper/2601.17212/) (2026)
- [Vector Retrieval with Similarity and Diversity: How Hard Is It?](https://mlsanity.com/paper/2407.04573/) (2024)
- [The Sparse Principal Component of a Constant-rank Matrix](https://mlsanity.com/paper/1312.5891/) (2013)
- [MUSS: Multilevel Subset Selection for Relevance and Diversity](https://mlsanity.com/paper/2503.11126/) (2025)
- [On Densest k-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis](https://mlsanity.com/paper/2410.07388/) (2024)

## Built on by (most cited first, 2 of 2)

- [WARP: Wasserstein-Aligned RAG for Population Opinions](https://mlsanity.com/paper/2608.22859/) (2026)
- [Finding the Right Balance: Relevance and Diversity in LLM Retrieval](https://mlsanity.com/paper/2610.09412/) (2026)

## Abstract (arXiv)

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.