# MUSS: Multilevel Subset Selection for Relevance and Diversity

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RAG pipeline design and evaluation, one of 15 directions in Retrieval-augmented generation.
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 14 Mar 2025.

## Placed in

- Retrieval-augmented generation / [RAG pipeline design and evaluation](https://mlsanity.com/rag/rag-pipeline-design-and-evaluation/)

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

- [Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering](https://mlsanity.com/paper/1809.02789/) (2018)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [SummEval: Re-evaluating Summarization Evaluation](https://mlsanity.com/paper/2007.12626/) (2020)
- [Recommender Systems with Generative Retrieval](https://mlsanity.com/paper/2305.05065/) (2023)
- [Effective Diversity in Population Based Reinforcement Learning](https://mlsanity.com/paper/2002.00632/) (2020)
- [Diverse Trajectory Forecasting with Determinantal Point Processes](https://mlsanity.com/paper/1907.04967/) (2019)
- [Differentiable Quality Diversity](https://mlsanity.com/paper/2106.03894/) (2021)
- [D2 Pruning: Message Passing for Balancing Diversity and Difficulty in Data Pruning](https://mlsanity.com/paper/2310.07931/) (2023)
- [A Review of Modern Recommender Systems Using Generative Models (Gen-RecSys)](https://mlsanity.com/paper/2404.00579/) (2024)
- [Clustering and Ranking: Diversity-preserved Instruction Selection through Expert-aligned Quality Estimation](https://mlsanity.com/paper/2402.18191/) (2024)
- [Diversity in Machine Learning](https://mlsanity.com/paper/1807.01477/) (2018)
- [Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search](https://mlsanity.com/paper/2006.07593/) (2020)
- [GDPP: Learning Diverse Generations Using Determinantal Point Process](https://mlsanity.com/paper/1812.00068/) (2018)
- [Automated Evaluation of Retrieval-Augmented Language Models with Task-Specific Exam Generation](https://mlsanity.com/paper/2405.13622/) (2024)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Exact sampling of determinantal point processes with sublinear time preprocessing](https://mlsanity.com/paper/1905.13476/) (2019)
- [Enhancing Recommendation Diversity by Re-ranking with Large Language Models](https://mlsanity.com/paper/2401.11506/) (2024)
- [The Power of Randomization: Distributed Submodular Maximization on Massive Datasets](https://mlsanity.com/paper/1502.02606/) (2015)
- [Efficient Sampling for k-Determinantal Point Processes](https://mlsanity.com/paper/1509.01618/) (2015)
- [Relevance meets Diversity: A User-Centric Framework for Knowledge Exploration through Recommendations](https://mlsanity.com/paper/2408.03772/) (2024)
- [Better RAG using Relevant Information Gain](https://mlsanity.com/paper/2407.12101/) (2024)
- [Exact Sampling from Determinantal Point Processes](https://mlsanity.com/paper/1609.06840/) (2016)
- [kNN-Embed: Locally Smoothed Embedding Mixtures For Multi-interest Candidate Retrieval](https://mlsanity.com/paper/2205.06205/) (2022)
- [Tackling Neural Architecture Search With Quality Diversity Optimization](https://mlsanity.com/paper/2208.00204/) (2022)
- [Distributed Maximization of Submodular plus Diversity Functions for Multi-label Feature Selection on Huge Datasets](https://mlsanity.com/paper/1903.08351/) (2019)

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

- [Principled and Scalable Diversity-Aware Retrieval via Cardinality-Constrained Binary Quadratic Programming](https://mlsanity.com/paper/2604.02554/) (2026)
- [WARP: Wasserstein-Aligned RAG for Population Opinions](https://mlsanity.com/paper/2608.22859/) (2026)

## Abstract (arXiv)

The problem of relevant and diverse subset selection has a wide range of applications, including recommender systems and retrieval-augmented generation (RAG). For example, in recommender systems, one is interested in selecting relevant items, while providing a diversified recommendation. Constrained subset selection problem is NP-hard, and popular approaches such as Maximum Marginal Relevance (MMR) are based on greedy selection. Many real-world applications involve large data, but the original MMR work did not consider distributed selection. This limitation was later addressed by a method called DGDS which allows for a distributed setting using random data partitioning. Here, we exploit structure in the data to further improve both scalability and performance on the target application. We propose MUSS, a novel method that uses a multilevel approach to relevant and diverse selection. In a recommender system application, our method can not only improve the performance up to 4 percent points in precision, but is also 20 to 80 times faster. Our method is also capable of outperforming baselines on RAG-based question answering accuracy. We present a novel theoretical approach for analyzing this type of problems, and show that our method achieves a constant factor approximation of the optimal objective. Moreover, our analysis also resulted in a × 2 tighter bound for DGDS compared to previously known bound. Our code is publicly available at https://github.com/amazon-science/muss.