Reimagining Meaningful Model Multiplicity

Ira Globus-Harris, Nikhil GargAI4GOOD @ ICML 2026 · OpenReview

TL;DR

Model multiplicity—the existence of many different models with similar overall accuracy—is often seen as a challenge for fairness and a computational headache. This paper reframes multiplicity as a "signal" to be harvested: instead of searching for one "fair" model within a near-optimal set, the authors propose ensembling models that improve performance on specific subgroups. Their approach is computationally efficient, provides better generalization, and proves that a "multicalibrated" predictor can actually outperform any single model found through traditional fairness searches.

What Problem Does This Paper Address?

In machine learning, we often find ourselves in the "Rashomon Effect" territory: for a given dataset, there isn't just one "best" model, but a whole Rashomon set of models that all achieve nearly the same minimum error. However, these models might behave very differently on specific demographic subgroups. One model might be great for Group A but terrible for Group B, while another flips that script.

For researchers interested in algorithmic fairness, this is both an opportunity (maybe a fairer model exists in that set!) and a burden. Current legal and ethical frameworks suggest we have a "duty to search" for these less discriminatory alternatives.

The catch? Searching the Rashomon set is a nightmare. It is often computationally intractable (NP-hard), and even if you find a "fairer" model on your training data, there’s no guarantee that fairness will generalize to new, unseen data. This paper seeks to move past the "search" paradigm toward a more constructive "ensemble" paradigm.

Methods

The authors shift the focus from the Rashomon set to "Meaningful Multiplicity." Instead of looking for models that are globally near-optimal, they look for any model in a hypothesis class $\mathcal{H}$ that outperforms the standard risk minimizer $h^*$ on a specific subgroup $g$.

They introduce three main technical pillars:

  1. Ensembling Techniques: They provide two ways to combine "multiplicitous" models (models that disagree with the baseline but help specific groups):
  2. Decision Lists: Using a "bias bounty" framework to recursively add models to a decision list, ensuring that group-wise errors only ever decrease.
  3. Linear Combinations: Using Ordinary Least Squares (OLS) to find the best weighted combination of models and group indicators.
  4. Multiaccuracy: They prove that if a model is "multiaccurate"—meaning it has no systematic prediction error on any subgroup identifiable by the hypothesis class—then "meaningful multiplicity" effectively vanishes. You can't find another model in $\mathcal{H}$ that beats it on a subgroup.
  5. Multicalibrated Post-processing: For classification tasks where fairness (like equalizing false positive rates) might conflict with accuracy, they suggest a two-step pipeline:
  6. First, learn a multicalibrated predictor (a stronger version of multiaccuracy).
  7. Second, post-process that predictor to meet fairness constraints.

Datasets

This is a theoretical paper focused on proving guarantees, algorithmic complexity, and statistical properties. Consequently, no empirical datasets (like COMPAS, Adult, or synthetic benchmarks) were used for evaluation in this specific manuscript. The results are presented as mathematical proofs and algorithmic frameworks.

Key Insights and Ideas

  • Multiplicity as Suboptimality: The authors argue that if multiplicity exists (i.e., another model beats your "best" model on a subgroup), it’s a sign that your "best" model is actually suboptimal and missing useful signals.
  • Bypassing the Rashomon Set: You don't actually need to construct or search the Rashomon set. By ensembling models that provide "local" improvements, you can build a predictor that lives outside your original hypothesis class $\mathcal{H}$ but performs better than anything inside it.
  • The Power of Multicalibration: The paper’s most striking insight is that a multicalibrated predictor "Pareto dominates" traditional search methods. It essentially finds the best possible trade-off between accuracy and fairness, rendering the expensive search for "less discriminatory alternatives" within a fixed model class unnecessary.
  • Generalization via Adaptive Analysis: By using tools from adaptive data analysis, the authors show that their ensembling methods can handle a large number of subgroups without the usual "overfitting" penalties associated with multiple comparisons.

Key Results

  • Lemma 4.1 & 4.2: These quantify the "gap" to the Bayes optimal predictor. They show that the disagreement between $h^*$ and group-specific models is a direct measure of how much room there is to improve the baseline.
  • Theorem 6.3: Establishes that multiaccuracy (which can be achieved with a polynomial number of queries to a standard learning oracle) is sufficient to eliminate meaningful multiplicity.
  • Corollary 7.9: This is the "mic drop" moment of the paper. It proves that post-processing a multicalibrated predictor yields a classifier on the fairness-accuracy Pareto front that is competitive with (or better than) any model you could possibly find by searching the Rashomon set.

Limitations and Future Work

  • Oracle Dependence: The proposed algorithms rely on having access to a "squared error oracle"—essentially a black box that can solve a standard regression problem for the hypothesis class $\mathcal{H}$. In some very complex or non-convex settings, this oracle itself might be hard to implement.
  • Computational Complexity of Multicalibration: While theoretically efficient (polynomial time), achieving high levels of multicalibration on a vast number of overlapping groups can still be resource-intensive in practice.
  • Theoretical Scope: The paper focuses on binary classification and regression with bounded labels. Extending these "meaningful multiplicity" concepts to multi-class settings or structured outputs remains an open area for future research.
  • Lack of Empirical Validation: As a theoretical submission, the "real-world" performance and the constants hidden in the $O(\cdot)$ notation haven't been tested on messy, high-dimensional datasets yet.

Summary updated

Abstract

Predictive model multiplicity is when multiple models in a hypothesis class $\mathcal{H}$ disagree on their predictions while having similar overall error to the risk minimizer h*. This has substantial implications for algorithmic fairness: if such multiplicity exists, then there may be a model competitive with the risk minimizer of the target hypothesis class which does substantially better in terms of target fairness metrics; some argue that searching for such a less discriminatory model is a legal duty. Standard approaches formalize this via search over a Rashomon set $\mathcal{R}(\mathcal{H})$ of models, but this search is computationally expensive and does not easily provide generalization guarantees. We propose a reframing to ``meaningful" model multiplicity that avoids both obstacles. Rather than asking how to find the most fair model in $\mathcal{R}(\mathcal{H})$, we ask whether any $h \in \mathcal{H}$ can outperform $h*$ on a target group $g$. We provide efficient ensembling techniques over models which witness such multiplicity which simultaneously will outperform $h*$ on all affected groups and with generalization guarantees. We further show that multiaccuracy with respect to $\mathcal{G} \times \mathcal{H}$---efficiently achievable via a polynomial number of oracle calls to $\mathcal{H}$---entirely precludes meaningful multiplicity. Finally, for constraint-based fairness metrics for classification tasks, we show that building a multicalibrated predictor for the label probability $\mathbb{E}[y \vert x]$ and then postprocessing it to satisfy the fairness guarantees will Pareto dominate any approach based on searching the Rashomon set of classifiers.
BibTeX
@inproceedings{globusharris2026reimagining,
  author = {Ira Globus-Harris and Nikhil Garg},
  title = {{Reimagining Meaningful Model Multiplicity}},
  booktitle = {AI4GOOD @ ICML},
  year = {2026},
  url = {https://openreview.net/forum?id=rIEm609OPg},
}
Figure