ArborEnum algorithm speeds up decision tree Rashomon set enumeration

The Rashomon effect describes a common phenomenon in machine learning: many different models can achieve nearly identical performance on the same task. This has major implications for robustness, feature importance, and model customizability, because a single "best" model might hide alternative solutions that are just as accurate but more appropriate for a specific use case. To explore these alternatives, researchers compute Rashomon sets—the set of all models whose regularized loss is near-optimal. Decision trees are one of the few model classes where exhaustive enumeration is feasible, but prior work required binarizing continuous features, which either restricts the splits a tree can make or dramatically increases an already difficult combinatorial problem.

In a new arXiv paper (2608.04310), Zakk Heile, Hayden McTavish, Margo Seltzer, and Cynthia Rudin introduce ArborEnum, the first algorithm that exactly enumerates decision-tree Rashomon sets while exploiting the ordered structure of continuous features. They also propose a relaxation for approximate enumeration and an anytime algorithm that progressively refines candidate thresholds, converging to the exact continuous-feature set. Experiments show that coarse binarization can miss many trees, important features, and predictive multiplicity. ArborEnum achieves orders-of-magnitude speedups over existing enumeration methods, and its approximate variants offer further speedups while maintaining near-perfect recall, making exhaustive Rashomon analysis practical for real-world datasets.