Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret

Mustafa Cavus · 2026

Read Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret by Mustafa Cavus (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-11701.txt.

Introduction

Cavus studies why decision trees trained on the same task can disagree, tracing the cause to label noise. Observed labels are one draw from true probabilities, so near-equal trees can grow from the same data. He splits this observational multiplicity into two parts: leaf regret and structural regret. Leaf regret measures prediction wobble inside a fixed leaf from finite-sample noise. Structural regret captures wobble from the tree shape itself changing. Structural regret dominates, at over 15 times the leaf level in some sets.

Catalog record

CREATORMustafa Cavus
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35492
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.11701

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret Mustafa Cavus Abstract Many machine learning tasks admit multiple models that perform almost equally well, a phenomenon known as predictive multiplicity. A fundamental source of this multiplicity is observational multiplicity , which arises from the stochastic nature of label collection: observed training labels represent only a single realization of the underlying ground-truth probabilities. While theoretical frameworks for observational multiplicity have been established for logistic regression, their implications for non-smooth, partition-based models like decision trees remain underexplored. In this paper, we introduce two complementary notions of observational multiplicity for decision tree classifiers: leaf regret and structural regret . Leaf regret quantifies the intrinsic variability of predictions within a fixed leaf due to finite-sample noise, while structural regret captures variability induced by the instability of the learned tree structure itself. We provide a formal decomposition of observational multiplicity into these two components and establish statistical guarantees. Our experimental evaluation across diverse credit risk scoring datasets confirms the near-perfect alignment between our theoretical decomposition and the empirically observed variance. Notably, we find that structural regret is the primary driver of observational multiplicity, accounting for over 15 times the variability of leaf regret in some datasets. Furthermore, we demonstrate that utilizing these regret measures as an abstention mechanism in selective prediction can effectively identify arbitrary regions and improve model safety, elevating recall from 92% to 100% on the most stable sub-populations. These results establish a rigorous framework for quantifying observational multiplicity, aligning with recent advances in algorithmic safety and interpretability. 1 Introduction The deployment of machine learning models in high-stakes domains—such as healthcare, credit scoring, and legal risk assessment—demands not only high prediction performance but also reliable predictions at the individual level. Nevertheless, a growing body of work has demonstrated that many learning problems admit predictive multiplicity : the existence of multiple models that achieve near-identical accuracy while assigning conflicting predictions to the same individual [ 1 , 3 ] . This phenomenon implies that an individual prediction may depend on the arbitrary selection of one model from this set of equally valid alternatives, giving rise to what has been termed predictive arbitrariness [ 4 ] . Such arbitrariness is particularly problematic in high-stakes decision-making, where model outputs must be justifiable not only in aggregate but also at the level of individual decisions. Early explanations of predictive multiplicity primarily emphasized sources of uncertainty arising from model underspecification, including architectural choices and optimization pipelines [ 5 ] . While this line of work has shown that modern machine learning workflows can produce many empirically indistinguishable models, it does not fully account for uncertainty originating from the data-generating process itself. More recently, observational multiplicity has been identified as a fundamental and distinct source of predictive multiplicity [ 2 ] . This phenomenon captures the idea that observed binary labels are stochastic realizations of latent ground-truth probabilities. Consequently, different but equally plausible draws of labels from the same underlying distribution may lead to different trained models. This irreducible label-induced variance is closely related to the notion of dataset multiplicity , which explores how model outcomes vary across all nearby versions of the data under uncertainties like label errors or bias. Despite recent theoretical advances, the implications for non-smooth models like decision trees remain underexplored. Decision trees are notoriously sensitive to data perturbations, behaving similarly to nearest-neighbor classifiers in terms of stability. Classic stability theory highlights this: for example, a tree with v leaves has a defined hypothesis stability \beta_{h} , implying that very small or shallow trees exhibit poor stability compared to deeper structures. This dual nature suggests two distinct sources of predictive multiplicity: label noise within a fixed tree leaf, representing irreducible aleatoric uncertainty , and variation across different tree structures, representing epistemic uncertainty arising from model change. In this work, we bridge this gap by formalizing a decomposition of observational multiplicity into leaf and structural regret, providing a practical framework to distinguish between local prediction noise and global model instability—a distinction crucial for deploying safe, tree-based systems in high-stakes environments. Our primary contribution is the introduction of two complementary notions of regret: • Leaf Regret: Quantifies the intrinsic variability of predictions within a fixed leaf, conditional on a given tree structure, capturing uncertainty due to stochastic label realizations. • Structural Regret: Captures the additional variability induced by randomness in the learned tree structure itself, reflecting instability across equally plausible training label realizations. Through this decomposition, we provide a more granular understanding of how predictive multiplicity propagates in non-smooth models. We establish theoretical guarantees and concentration inequalities for estimating leaf regret, and propose Monte Carlo procedures to approximate structural regret. By leveraging these regret measures, we demonstrate how decision systems can proactively identify individuals for whom the model is “guessing” due to label instability, thereby enabling a more rigorous approach to algorithmic safety. Our framework contributes to the growing literature on algorithmic safety and interpretability by explicitly distinguishing between noise within a structure and instability of the structure in tree-based learning. The remainder of this paper is organized as follows. Section 2 reviews related work. Section 3 presents our methodology and theoretical results. Section 4 reports experimental evaluations. Section 5 discusses implications and limitations, and Section 6 concludes. 2 Related Work The reliability of machine learning models has been increasingly scrutinized through the lens of predictive multiplicity , a phenomenon where multiple models with near-identical aggregate performance assign conflicting predictions to the same individual [ 3 ] . This challenge, often referred to as the Rashomon effect [ 1 ] , poses significant implications for interpretability, fairness, and safety in high-stakes decision-making [ 5 , 4 ] . Modern machine learning pipelines typically fit models through empirical risk minimization, which may return multiple competing models that differ in their individual-level predictions despite achieving the same empirical risk. While traditional approaches viewed this as an optimization or underspecification problem, recent studies have highlighted the ethical concerns of predictive arbitrariness, where an individual’s treatment depends on the arbitrary choice of one optimal model over another from the Rashomon set. A critical and unavoidable source of this arbitrariness is observational multiplicity , which describes the uncertainty arising from the stochastic nature of data collection [ 2 ] . Unlike the optimization-driven multiplicity discussed by D’Amour et al. [ 5 ] , which stems from model underspecification, observational multiplicity considers uncertainty as a byproduct of the data-generating process itself. This distinction is vital: while the Rashomon effect explores the space of equally performing models, observational multiplicity quantifies the unavoidable variability induced by the stochastic realization of training labels. This perspective notes that training labels are often single realizations of underlying ground-truth probabilities; consequently, different but equally plausible draws of labels from the same distribution would lead to different trained models. To quantify this irreducible risk, the measure of regret [ 2 ] is proposed to capture unavoidable variability in individual predictions due to randomness in observed labels. This concept is closely related to the dataset multiplicity problem [ 7 ] , which explores how unreliable data and counterfactual label draws impact predictions. In parallel, probabilistic formulations of multiplicity show that disagreement can persist even when models are calibrated and optimized

Read the complete text