Dynamic Cardinality for Subset Selection

27 concepts27 papers2 proposals

When we ask an algorithm to make a choice, we often force it into a rigid mold: "Give me the top $k$ items." Whether selecting the top 5 products to recommend, the top 10 features for a predictive model, or a fixed-size committee of representatives, the number of items to be selected ($k$) is almost always treated as a predefined constant.

This is the fixed-cardinality constraint. It is computationally convenient because sorting a list of scores and truncating at $k$ is trivial. However, it introduces a fundamental mismatch with reality. If an e-commerce platform forces a top-3 recommendation list, but a user only has 1 high-quality match, the system injects 2 pieces of irrelevant noise. Conversely, if 10 items are excellent matches, the system discards 7 valuable options. As noted by [Robert Istvan Busa-Fekete] et al. in Top-k Selection based on Adaptive Sampling of Noisy Preferences, this rigid quota limits applicability in dynamic environments where the inclusion threshold should depend on candidate quality rather than an arbitrary cap.

To build more intelligent systems, a growing body of research focuses on dynamic cardinality—allowing algorithms to decide not just which items to select, but how many.

The Core Mechanisms of Variable Selection

How do we break the fixed-cardinality constraint without causing a combinatorial explosion? Researchers have converged on three primary strategies.

1. Relative Thresholding and Discrepancy Bars

Instead of fixing the count, we can fix a quality or discrepancy bar and let the subset size adjust naturally.

In multi-armed bandits, traditional algorithms focus on finding the single best arm or a fixed set of $k$ arms. [Blake Mason] et al. shift this paradigm in Finding All $\epsilon$-Good Arms in Stochastic Bandits by designing algorithms that identify every candidate meeting a relative performance bar, allowing the sample size and subset size to adapt to the true distribution of high-quality options.

A similar intuition applies to large language model (LLM) alignment. When training safety reward models, evaluating response pairs against a massive, static list of safety rules is computationally wasteful and rigid. To solve this, [Xiaomin Li] et al. (RuleAdapter: Dynamic Rules for training Safety Reward Models in RLHF) and [Jingxuan Fan] et al. (Data-adaptive Safety Rules for Training Reward Models) introduce mechanisms that dynamically adjust the number of active rules based on a discrepancy threshold. By focusing only on rules where the model responses show significant disagreement, the subset of evaluation criteria scales naturally with the complexity of the prompt.

2. Joint Learning of Content and Cardinality

Can a neural network learn to output both a set of items and its optimal size simultaneously?

[Hamid Rezatofighi] et al. address this in Joint Learning of Set Cardinality and State Distribution by leveraging Finite Set Statistics (FISST). Instead of relying on manual heuristics or fixed thresholds to cut off predictions, their framework jointly estimates the cardinality distribution and the item attributes within a single loss function.

Traditional Top-k:  [Input] ---> [Score Items] ---> [Sort & Take Fixed k]
Joint Learning:     [Input] ---> [Neural Net]  ---> [Predict Cardinality c]
                                               ---> [Predict c Best Items]

This joint optimization is incredibly powerful in combinatorial search. Mixed-Integer Linear Programming (MILP) solvers rely on adding auxiliary constraints, called "cutting planes," to tighten search spaces. Adding too few cuts makes the solver slow; adding too many overwhelms it. Rather than using static heuristics for the quantity of cuts, [Zhihai Wang] et al. (Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model) and [Jie Wang] et al. (Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming) utilize hierarchical sequence-to-sequence models. These models treat cut selection as a dynamic process, predicting the optimal selection ratio and application order tailored to each unique problem instance.

3. Geometric and Pareto Frontiers

Another elegant approach maps items into a multi-dimensional space where the optimal subset emerges as a geometric property rather than a numerical rank.

[Eyke Hüllermeier] et al. introduce this concept in Learning Choice Functions via Pareto-Embeddings. By mapping objects into a latent space where the chosen subset corresponds to the "Pareto frontier"—the points that are not strictly outperformed by any others across all dimensions—the size of the selected subset becomes entirely dynamic, dictated by the geometric distribution of the options.

Dimension 2 ^
            |  * (Pareto Frontier Point)
            |    \
            |     * (Pareto Frontier Point)
            |       \
            |   o    * (Pareto Frontier Point)
            |
            +--------------------------> Dimension 1
            (The size of the subset is naturally determined 
             by the shape of the frontier, not a fixed k)

In multi-objective optimization, when objectives are fundamentally incompatible, [Natalie Maus] et al. demonstrate that instead of pre-specifying a set size to cover trade-offs, algorithms can jointly optimize both the solution set and its cardinality (Covering Multiple Objectives with a Small Set of Solutions Using Bayesian Optimization). This ensures the framework finds the absolute minimum number of solutions required for full coverage.

Why Traditional Frameworks Struggle

If dynamic cardinality is so intuitive, why has the fixed-$k$ assumption persisted for so long? The answer lies in the mathematical guarantees that break down when subset sizes fluctuate.

  • Exploration-Exploitation Tradeoffs: In multi-armed bandits, standard multi-play frameworks assume a fixed number of actions per round ([Claire Tomlin] et al., Budget-Constrained Multi-Armed Bandits With Multiple Plays). When the subset size can vary, managing the budget and learning rate becomes significantly more complex. As [Aadirupa Saha] et al. explore in Battle of Bandits, allowing a learner to dynamically adjust the subset size based on current uncertainty could optimize this tradeoff, but it requires entirely new theoretical foundations.
  • Probabilistic Complexity: Modeling subsets probabilistically is notoriously difficult. As [Yujia Shen] points out in A Tractable Probabilistic Model for Subset Selection, moving away from a fixed-cardinality assumption typically forces researchers to use complex model mixtures, adding significant computational overhead.
  • Axiomatic Consistency: Even in social choice theory, axiomatic frameworks for committee selection traditionally assume a fixed committee size. [Patrick Lederer] et al. note in Refined Characterizations of Approval-Based Committee Scoring Rules that this limitation prevents researchers from understanding how voting rules behave when the number of seats changes, making it difficult to enforce fairness and consistency across different election scales.

By moving beyond fixed-cardinality constraints, modern machine learning models are transitioning from rigid filters into adaptive decision-makers—learning not just what to choose, but how much information the context demands.

Key Foundational Work

Top-k Selection based on Adaptive Sampling of Noisy Preferences (2013) — contributed 1 concept elements to this direction.
Evolutionary multiobjective optimization for selecting members of an ensemble streamflow forecasting model (2013) — contributed 1 concept elements to this direction.
Length-Lex Ordering for Set CSPs (2006) — contributed 1 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_fixed_cardinality_constraint_b7be9fc3_v2,
  title = {fixed-cardinality constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fixed-cardinality-constraint/rdr_b7be9fc373af40639c2b245603898b2e/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake