When Does Model Multiplicity Affect Prediction Intervals? A Sharp Phase Transition

Hai Nguyen, Khanh Nguyen, Hung Mai, Luong Doan, Nhung Duong, Phong Ho, Tuan Do
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:4873-4889, 2026.

Abstract

The {Rashomon} effect, the fact that many different models can achieve nearly identical predictive accuracy, has been extensively studied across various domains of machine learning. While modern conformal prediction provides valid intervals for a single model, it remains blind to the inherent arbitrariness of having to select from multiple candidates. This paper bridges this gap by investigating when model multiplicity, or the existence of many near-optimal models, materially widens prediction intervals. We prove a sharp phase transition for ridge regression under {Gaussian} design and introduce *{Rashomon} Prediction Intervals* (RPIs), which bound the range of predictions across the {Rashomon} set and establish a {Rashomon}-Conformal Bridge that provides distribution-free coverage guarantees. A critical tolerance $\varepsilon^\star = \Theta(\sigma^2/p)$ separates two distinct regimes: below it, {Rashomon}-conformal intervals match standard conformal width; above it, model multiplicity dominates, and this scaling is provably minimax optimal. Computationally, exact RPIs are polynomial for convex classes but NP-hard for tree ensembles, with a thin-cap volumetric barrier ruling out sampling-based approximation. Experiments on six UCI benchmarks confirm the phase transition, with all datasets falling in the sub-critical regime at standard tolerances, indicating that model multiplicity is invisible in prediction intervals for typical tabular regression.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-nguyen26c, title = {When Does Model Multiplicity Affect Prediction Intervals? {A} Sharp Phase Transition}, author = {Nguyen, Hai and Nguyen, Khanh and Mai, Hung and Doan, Luong and Duong, Nhung and Ho, Phong and Do, Tuan}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {4873--4889}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/nguyen26c/nguyen26c.pdf}, url = {https://proceedings.mlr.press/v337/nguyen26c.html}, abstract = {The {Rashomon} effect, the fact that many different models can achieve nearly identical predictive accuracy, has been extensively studied across various domains of machine learning. While modern conformal prediction provides valid intervals for a single model, it remains blind to the inherent arbitrariness of having to select from multiple candidates. This paper bridges this gap by investigating when model multiplicity, or the existence of many near-optimal models, materially widens prediction intervals. We prove a sharp phase transition for ridge regression under {Gaussian} design and introduce *{Rashomon} Prediction Intervals* (RPIs), which bound the range of predictions across the {Rashomon} set and establish a {Rashomon}-Conformal Bridge that provides distribution-free coverage guarantees. A critical tolerance $\varepsilon^\star = \Theta(\sigma^2/p)$ separates two distinct regimes: below it, {Rashomon}-conformal intervals match standard conformal width; above it, model multiplicity dominates, and this scaling is provably minimax optimal. Computationally, exact RPIs are polynomial for convex classes but NP-hard for tree ensembles, with a thin-cap volumetric barrier ruling out sampling-based approximation. Experiments on six UCI benchmarks confirm the phase transition, with all datasets falling in the sub-critical regime at standard tolerances, indicating that model multiplicity is invisible in prediction intervals for typical tabular regression.} }
Endnote
%0 Conference Paper %T When Does Model Multiplicity Affect Prediction Intervals? A Sharp Phase Transition %A Hai Nguyen %A Khanh Nguyen %A Hung Mai %A Luong Doan %A Nhung Duong %A Phong Ho %A Tuan Do %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-nguyen26c %I PMLR %P 4873--4889 %U https://proceedings.mlr.press/v337/nguyen26c.html %V 337 %X The {Rashomon} effect, the fact that many different models can achieve nearly identical predictive accuracy, has been extensively studied across various domains of machine learning. While modern conformal prediction provides valid intervals for a single model, it remains blind to the inherent arbitrariness of having to select from multiple candidates. This paper bridges this gap by investigating when model multiplicity, or the existence of many near-optimal models, materially widens prediction intervals. We prove a sharp phase transition for ridge regression under {Gaussian} design and introduce *{Rashomon} Prediction Intervals* (RPIs), which bound the range of predictions across the {Rashomon} set and establish a {Rashomon}-Conformal Bridge that provides distribution-free coverage guarantees. A critical tolerance $\varepsilon^\star = \Theta(\sigma^2/p)$ separates two distinct regimes: below it, {Rashomon}-conformal intervals match standard conformal width; above it, model multiplicity dominates, and this scaling is provably minimax optimal. Computationally, exact RPIs are polynomial for convex classes but NP-hard for tree ensembles, with a thin-cap volumetric barrier ruling out sampling-based approximation. Experiments on six UCI benchmarks confirm the phase transition, with all datasets falling in the sub-critical regime at standard tolerances, indicating that model multiplicity is invisible in prediction intervals for typical tabular regression.
APA
Nguyen, H., Nguyen, K., Mai, H., Doan, L., Duong, N., Ho, P. & Do, T.. (2026). When Does Model Multiplicity Affect Prediction Intervals? A Sharp Phase Transition. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:4873-4889 Available from https://proceedings.mlr.press/v337/nguyen26c.html.

Related Material