Adaptive Subset Selection with Variable Cardinality

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 229 papers32 conceptsfrozen 2026-10-04

In many real-world decision-making tasks, we are asked to pick a "top-k" list. Whether it is a starting lineup in sports, a set of stock picks for a portfolio, or a committee of winners in an election, the standard approach assumes that the number of items to be selected ($k$) is a fixed, known constant.

However, a growing body of research suggests that this "fixed-cardinality" assumption is a significant bottleneck. In reality, the optimal number of items often depends on the specific context: a tennis match needs exactly two or four players, but a social gathering might be viable with any number between five and ten. As George Varghese and Ashwin Machanavajjhala argue in Scalable Social Coordination using Enmeshed Queries, systems that cannot express these variable constraints fail to optimize for activities that are viable across different scales.

The shift toward variable cardinality treats the size of the subset as a decision variable itself, rather than a pre-defined constraint.

The Problem with Fixed Budgets

Traditional combinatorial optimization and machine learning models typically use heuristics to pick a fixed number of items. For example, in portfolio management, Yu Zheng and Yongxin Yang note in Index Tracking with Cardinality Constraints that forcing a fixed number of stocks prevents a system from naturally balancing the trade-off between tracking accuracy and transaction costs.

Similarly, in ensemble learning, choosing a fixed number of models to vote on an outcome is often suboptimal. James Kotary and Ferdinando Fioretto demonstrate in Differentiable Model Selection for Ensemble Learning that the "ideal" subset of models changes based on the difficulty of the specific input. A simple query might only need one specialized model, while a complex one might require a larger, more diverse committee.

From Rankings to Frontiers

To move beyond fixed-k selection, researchers are reimagining how we "score" items. Instead of a linear ranking where we chop off the list at position $k$, new methods use geometric or threshold-based logic:

  • Pareto Embeddings: Eyke Hüllermeier and Karlson Pfannschmidt propose mapping items into a multi-dimensional space where the selected subset is the "Pareto frontier"—the set of all items that aren't strictly outperformed by others. This allows the subset size to emerge naturally from the data distribution in Learning Choice Functions via Pareto-Embeddings.
  • $\epsilon$-Good Arms: In bandit problems, rather than finding the single best arm, Blake Mason and Robert Nowak focus on identifying all arms that are within a certain quality threshold of the optimum. This approach, detailed in Finding All $\epsilon$-Good Arms in Stochastic Bandits, is essential when the number of high-quality candidates is unknown.
  • Discrepancy Thresholds: In the context of Large Language Model safety, Xiaomin Li and Jingxuan Fan developed RuleAdapter, which dynamically selects safety rules based on which ones show the "maximum discrepancy" for a given prompt, rather than applying a static list of constraints.

Making Variable Selection Differentiable

The primary technical challenge in variable subset selection is that "choosing" is a discrete, non-differentiable operation. To solve this, researchers are integrating combinatorial layers directly into neural networks.

For instance, the e2e-CEL framework uses a "Knapsack Layer" to make the selection of model subsets differentiable. In the realm of Mixed-Integer Linear Programming (MILP), Zhihai Wang and Mingxuan Yuan use reinforcement learning in Learning Cut Selection for Mixed-Integer Linear Programming to decide not just which constraints to add, but exactly how many are needed for a specific problem instance.

Probabilistic Foundations for Sets

Handling variable sizes also requires new probabilistic tools. Traditional Determinantal Point Processes (DPPs) are often used to select diverse subsets, but they frequently struggle when the subset size is not fixed. Chengtao Li and Stefanie Jegelka addressed this in Fast Sampling for Strongly Rayleigh Measures by bridging the gap between fixed-size and variable-size sampling through "symmetric homogenization."

This mathematical groundwork allows for Bayesian Optimization over Sets, where the input to a function is a set of arbitrary size. As Jungtaek Kim and Seungjin Choi demonstrate in Practical Bayesian Optimization over Sets, this enables AI to optimize complex structures like point clouds or chemical molecular sets where the number of elements is itself a critical part of the search space.

Why It Works: Flexibility and Efficiency

The intuition behind this research direction is simple: rigidity is expensive. When we force a system to pick exactly 10 items, we waste computation if only 3 are relevant, and we lose information if 15 are important.

By allowing the cardinality to vary, these models can:

  1. Adapt to Difficulty: Use more resources (items/models/rules) for hard problems and fewer for easy ones.
  2. Ensure Coverage: In multi-objective optimization, Natalie Maus and colleagues show in MOCOBO that finding a small set of solutions can cover a wide spectrum of objectives (like killing diverse bacteria) more effectively than any single "balanced" solution.
  3. Reflect Human Preferences: Social choice theory is evolving to include voting rules where the number of winners is determined by the voters themselves, as explored by Piotr Faliszewski in The Complexity of Multiwinner Voting Rules with Variable Number of Winners.

Ultimately, treating the number of selections as a dynamic property rather than a static constraint allows algorithms to better mirror the fluid nature of real-world decision-making.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 26 papers
  2. Version 1 · 2026-10-04 · 29 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_fixed_cardinality_constraint_b7be9fc3,
  title = {fixed-cardinality constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fixed-cardinality-constraint/rdr_b7be9fc373af40639c2b245603898b2e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_adaptive_subset_selection_with_variable__b7be9fc3_v1,
  title = {Adaptive Subset Selection with Variable Cardinality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-subset-selection-with-variable-cardinality/rdr_b7be9fc373af40639c2b245603898b2e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}