ArborEnum: Decision Tree Rashomon Sets over Continuous Features
Abstract
The Rashomon effect describes the phenomenon that many models can achieve nearly equivalent performance on the same learning task, with significant ramifications for robustness, feature importance, and customizability. These use cases motivate the computation of Rashomon sets: the set of all models whose regularized loss is near-optimal. Decision trees are one of the few model classes for which Rashomon sets can be fully enumerated, but this computation has always been conditional on a binarization of the original data, either restricting which splits each tree is allowed to make or substantially increasing the complexity of an already difficult combinatorial problem. We introduce the first algorithm that exactly enumerates decision-tree Rashomon sets while exploiting the ordered structure of continuous features. We further develop a relaxation for approximate enumeration and an anytime algorithm that progressively refines the set of candidate thresholds, producing increasingly detailed approximations that converge to the continuous-feature Rashomon set. Experiments show that coarse binarization can miss many trees, important features, and predictive multiplicity; our algorithms achieve orders-of-magnitude speedups over existing enumeration methods, with approximations providing further speedups while maintaining near-perfect recall.
Related
- Largest Rashomon sets of decision trees for robust contextual optimization
- Decision-Tree Surrogates for Weak Counterfactual Explanations in Integer Optimization
- Distributed Continuous-Time Optimization on the Special Orthogonal Group SO(3) over Tree Interaction Graphs
- Dynamic Programming for Value-at-Risk Markov Decision Processes in Continuous Spaces
- New Modelling and Solution Frameworks for Multiple Objectives, Decomposability and Impulsivity in Continuous-time Markov Decision Processes
BibTeX
@misc{heile2026arborenum,
title = {{ArborEnum: Decision Tree Rashomon Sets over Continuous Features}},
author = {Zakk Heile and Hayden McTavish and Margo Seltzer and Cynthia Rudin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.04310},
eprint = {2608.04310},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.04310},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - ArborEnum: Decision Tree Rashomon Sets over Continuous Features
AU - Zakk Heile
AU - Hayden McTavish
AU - Margo Seltzer
AU - Cynthia Rudin
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2608.04310
UR - https://arxiv.org/abs/2608.04310
AB - The Rashomon effect describes the phenomenon that many models can achieve nearly equivalent performance on the same learning task, with significant ramifications for robustness, feature importance, and customizability. These use cases motivate the computation of Rashomon sets: the set of all models whose regularized loss is near-optimal. Decision trees are one of the few model classes for which Rashomon sets can be fully enumerated, but this computation has always been conditional on a binarization of the original data, either restricting which splits each tree is allowed to make or substantially increasing the complexity of an already difficult combinatorial problem. We introduce the first algorithm that exactly enumerates decision-tree Rashomon sets while exploiting the ordered structure of continuous features. We further develop a relaxation for approximate enumeration and an anytime algorithm that progressively refines the set of candidate thresholds, producing increasingly detailed approximations that converge to the continuous-feature Rashomon set. Experiments show that coarse binarization can miss many trees, important features, and predictive multiplicity; our algorithms achieve orders-of-magnitude speedups over existing enumeration methods, with approximations providing further speedups while maintaining near-perfect recall.
ER -