In many real-world tasks, we are not looking for a single "best" item, but rather the best collection of items. Whether it is a news feed, a capsule wardrobe, or a set of demonstrations for a large language model, the value of the collection depends on how the items interact. However, as the number of candidates grows, the number of possible subsets grows exponentially—a phenomenon often called the "combinatorial explosion."
Research in this area focuses on navigating these massive search spaces to find high-quality subsets without evaluating every possible combination.
The Challenge of Combinatorial Explosion
The fundamental difficulty in subset selection is that the utility of a set is rarely just the sum of its parts. As Brafman et al. note, users often have preferences over sets based on properties like diversity or coverage. For example, a film festival lineup needs a variety of genres, not just five copies of the highest-rated movie.
When we move from selecting one item out of $N$ to selecting a subset, the search space jumps from $N$ to $2^N$. López-Sánchez et al. point out that even for moderately sized pools, this makes exhaustive search computationally intractable. This complexity appears across domains:
- Machine Translation: Finding the optimal subset of translation rules to prune low-quality outputs (Imamura et al.).
- In-Context Learning: Choosing the best few-shot examples to prompt a model (Li et al.).
- Database Queries: Identifying "skyline" groups that are not dominated by any other combination of items (Yu et al.).
Exploiting Structure for Efficient Search
To avoid checking every combination, researchers exploit mathematical structures that provide shortcuts to the optimal set.
Submodularity and Diversity
One of the most powerful tools is submodularity, a property of set functions where adding an item to a small set provides more incremental value than adding it to a large set (diminishing returns). Tschiatschek et al. demonstrate that by smoothing these discrete decisions, we can even make submodular maximization differentiable, allowing models to learn utility functions end-to-end.
Hsiao uses iterative submodular optimization to create capsule wardrobes, ensuring that each new garment maximizes the versatility of the existing collection. Similarly, Kulesza et al. use Determinantal Point Processes (DPPs) to model diversity, providing a convex framework to select subsets that are both high-quality and non-redundant.
Bandit Frameworks and Assortment Selection
In recommendation systems, the goal is often to select an "assortment" or menu of items to show a user. Ou et al. and Iyengar et al. frame this as a Multinomial Logit (MNL) Bandit problem. By assuming that item preferences are driven by underlying features (linear utility), the authors break the dependency on the total number of items, allowing algorithms to scale to massive catalogs.
Krishnamurthy et al. extend this to "pure exploration," where the algorithm interactively samples items to identify the best subset (like a spanning tree or matching) with minimal samples.
Scaling to Extreme Search Spaces
As datasets grow to millions of items, even efficient search algorithms can struggle. Recent work introduces hierarchical and partitioning strategies to further reduce complexity.
Rakhlin et al. tackle "extreme" contextual bandits by using an arm hierarchy, reducing the search space from millions of items to a logarithmic scale. In the context of Large Language Models, Wang et al. propose Mixture of Demonstrations (MoD), which partitions the example pool into "experts" to navigate the search space more effectively.
For real-time applications, Purohit et al. introduce the CASE framework, which maintains a shortlist of "challenger" examples. By treating subset selection as a bandit problem, the authors achieve significant speedups and reductions in computational costs without sacrificing the quality of the selected set.
Beyond Item Selection: Teaching and Sampling
The principles of subset selection also apply to how we teach and how we train models. Cakmak et al. show that identifying the most "informative" subset of demonstrations can significantly accelerate how quickly a robot (or a human) learns a new task. In stochastic optimization, Borsos et al. use adaptive mixtures to select minibatches of data, demonstrating that intelligent subset selection can directly reduce variance and speed up model training.
Key Foundational Work
Preferences over Sets (2006) — contributed 1 concept elements to this direction.
Feedback Cleaning of Machine Translation Rules Using Automatic Evaluation (2003) — contributed 1 concept elements to this direction.