MUSS: Multilevel subset selection for relevance and diversity

The problem of relevant and diverse subset selection has a wide range of applications, from recommender systems to 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, an efficient 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 percentage points in precision, but is also20 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 prob-ems, and show that our method achieves a constant factor approximation of the optimal objective.Moreover, our analysis also results in a ×2 tighter bound for DGDS compared to the previously known bound. Our code is publicly available at https://github.com/amazon-science/muss