🤖 machine learning

ArborEnum: Decision Tree Rashomon Sets over Continuous Features

This paper introduces the first algorithm to exactly enumerate decision-tree Rashomon sets over continuous features by leveraging their ordered structure, alongside approximate and anytime methods that significantly outperform existing binarization-based approaches in speed and accuracy while revealing critical predictive multiplicity.

Original authors: Zakk Heile, Hayden McTavish, Margo Seltzer, Cynthia Rudin

Published 2026-08-06

📖 10 min read🧠 Deep dive

CC BY 4.0

Original authors: Zakk Heile, Hayden McTavish, Margo Seltzer, Cynthia Rudin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, tangled knot of a problem. In the world of computer science, specifically in a field called machine learning, we often ask computers to find the "best" way to make predictions, like guessing if a customer will buy a product or if a patient has a certain condition. For a long time, scientists believed there was usually just one single, perfect answer—a unique "golden model" that was the absolute best. But there's a fascinating twist to this story called the Rashomon effect. Named after a famous movie where four witnesses tell different versions of the same event, this effect describes a reality where many completely different models can perform almost exactly the same. They are all "good enough," but they might use different clues or look at the data in totally different ways.

Why does this matter? Because if you only look for that one "golden" model, you might miss out on a whole crowd of equally good alternatives. Some of those alternatives might be safer, easier to understand, or fairer. To study this, researchers look for a Rashomon set: a collection of all the models that are nearly perfect. The challenge is that finding this set is like trying to count every single grain of sand on a beach. It's a huge, messy job, especially when the data isn't just simple "yes or no" answers (like red or blue) but includes continuous features—numbers that can be anything, like temperature, height, or price, which can be split at millions of different points.

This is where a new study comes in, introducing a clever new tool called ArborEnum. Think of the researchers as explorers trying to map a dense, foggy forest. Before, if they wanted to map the forest, they had to chop it down into neat, square grid squares (a process called binarization) just to make it manageable. But in doing so, they often missed hidden paths, rare trees, and important shortcuts that existed in the wild, continuous landscape. The authors of this paper built a new kind of compass that lets them explore the forest exactly as it is, with all its smooth, continuous curves, without chopping it up first. They found that by ignoring the smoothness of the data, old methods were missing huge chunks of the "good" models. Their new method can list these models much faster—sometimes hundreds of times faster—than before. Even better, they created a "smart" version that starts with a rough sketch of the forest and keeps refining it, getting more detailed the longer you let it run, so you can stop whenever you have enough information. They proved through experiments on real-world data that this approach not only saves time but also finds important features and model variations that the old, grid-based methods completely overlooked.

The Story of the Forest and the Grid

Imagine you are a detective trying to solve a mystery. You have a pile of clues, and you need to build a decision tree—a flowchart of questions—to figure out who did it. Usually, you'd ask questions like, "Is the suspect taller than 6 feet?" or "Is the suspect wearing a hat?" In the old days, computer scientists had to turn every single clue into a simple "yes or no" question before they could start building their tree. If a clue was a number, like "The suspect's height is 5'11"," they had to chop it into buckets: "Is he under 5'6"?" "Is he between 5'6" and 6'0"?" "Is he over 6'0"?"

This chopping process is called binarization. It's like taking a smooth, flowing river and forcing it into a series of square, concrete channels. The problem is, by forcing the water into these rigid boxes, you might miss a tiny, perfect eddy or a hidden current that flows right between the cracks. In the world of machine learning, this means you might miss a perfect way to split the data because your "grid" didn't have a line exactly where the data needed it.

The Rashomon effect is the idea that there isn't just one perfect flowchart. There are dozens, maybe hundreds, of different flowcharts that all solve the mystery with the same high accuracy. Some might use height, others might use weight, and others might use a combination of both. The Rashomon set is the collection of all these equally good flowcharts. Finding this set is super useful because it helps us understand which clues are truly important and which ones are just lucky guesses. If a clue appears in almost every good flowchart, it's probably a real key to the mystery. If it only appears in one, it might just be a fluke.

The Problem with the Old Maps

For a long time, the only way to find this Rashomon set was to use the "concrete channel" method (binarization). Researchers would chop the continuous numbers into a few buckets and then try to find all the good trees. But this had two big problems. First, the search space was already huge; with just 20 binary features, there were already more trees than there are grains of sand on Earth. Second, by chopping the data, they were throwing away information. They might miss a split that happened at a very specific number, like 5.99 inches, because their buckets were only 5.5 and 6.0.

The paper shows that this "coarse" binarization is like trying to find a needle in a haystack by only looking at the top layer of hay. You might find a needle, but you'll miss the ones buried deeper or the ones that are slightly different shapes. The authors found that when they forced data into these rough buckets, they missed many important trees, important features, and the true variety of solutions (predictive multiplicity).

The New Compass: ArborEnum

Enter ArborEnum. The authors built the first algorithm that can explore the "continuous forest" without chopping it up first. Instead of forcing the data into square buckets, ArborEnum respects the natural order of the numbers. It treats the data like a smooth line and looks for the best places to cut it, knowing that there are thousands of possible cut points.

To do this, they used a clever trick. Imagine you are looking for the best spot to cut a rope. You don't need to test every single millimeter. If you know that cutting at 10 inches is bad, and cutting at 11 inches is also bad, you can probably guess that cutting at 10.5 inches won't be great either. The authors developed a way to use these "bounds" to skip over huge sections of the rope that don't need to be tested. They call this pruning. It's like having a map that tells you, "Don't bother looking in this entire valley; the treasure isn't there."

They also introduced a "proxy" system. Think of a proxy as a quick, rough guess. Before doing the hard work of checking every single possibility, the algorithm makes a fast, approximate guess to see if a path is worth exploring. If the guess says "no way," it skips the whole branch. If the guess says "maybe," it digs deeper. This allows the algorithm to run incredibly fast. In their tests, this method was 270 times faster than existing methods on average, and in some cases, it was even more dramatic.

The "Anytime" Feature: A Sketch That Gets Better

One of the coolest parts of ArborEnum is its anytime algorithm. Usually, if you want a perfect map, you have to wait until the computer finishes the whole job. But what if you need an answer now? The anytime version of ArborEnum starts with a very rough sketch of the forest. It might only look at a few key cut points. It gives you a list of good trees based on that rough sketch.

Then, as you let it run longer, it adds more and more cut points to its map. It refines the sketch, filling in the gaps. The more time you give it, the more detailed and accurate the list of trees becomes. Eventually, if you let it run long enough, it finds the exact, perfect list of all the good trees. The best part? You can stop it at any time. If you need an answer in 5 minutes, you get a good approximation. If you have 5 hours, you get a near-perfect answer. The authors found that even with this "rough start," the method recovered nearly all the important trees, and the extra time it took to refine the map was tiny—only about 2.7% more time than running the non-refined version on the final set of points.

What They Found and What It Means

The experiments were run on 20 different real-world datasets, from predicting bike rentals to credit card defaults. The results were clear:

Coarse binarization misses a lot: When they compared the old "chopped" method to the new continuous method, the old method missed many trees and important features. It was like looking at a photo through a foggy window; you could see the general shape, but you missed the details.
Speed is real: The new method was orders of magnitude faster. On one dataset called "Bike," the new optimal method finished 63 times faster than the only other method that could finish at all.
Accuracy is high: Even when using the fast, approximate "proxy" method, they recovered 94.5% to 100% of the trees that the perfect method found. This means you can get almost all the benefits of the Rashomon set without waiting forever.
The "Anytime" approach works: The method that starts rough and gets better proved to be very efficient. It found important features early on, meaning you can get useful insights quickly without waiting for the full computation.

The paper doesn't claim to have solved every problem in machine learning. It doesn't say that continuous features are the only way to do things, or that this method works for every single type of model. But it does show, with solid evidence from experiments, that for decision trees, treating continuous data as continuous is a game-changer. It allows us to see the full picture of the "Rashomon set" without losing our minds (or our computers) to the complexity.

In short, ArborEnum is a new way to explore the landscape of good solutions. It stops us from forcing the world into a grid that doesn't fit, and instead lets us walk the smooth, continuous paths where the real answers often hide. Whether you are a data scientist looking for the best model or just a curious person wondering how computers make decisions, this work suggests that there are more good answers out there than we thought, and we now have a better way to find them.

Technical Summary: ArborEnum

Problem Statement

The Rashomon effect describes the phenomenon where many distinct models achieve nearly equivalent predictive performance on a learning task. Studying Rashomon sets—the collection of all models whose regularized loss is within a prescribed tolerance of the optimal—provides insights into robustness, feature importance, and predictive multiplicity. While decision trees are a primary model class for which Rashomon sets can be enumerated, existing algorithms (e.g., Heile et al. 2026; Xin et al. 2022) are conditional on binary features.

When applied to real-world data containing continuous features, existing methods require coarse binarization (e.g., using empirical quantiles) before enumeration. This approach introduces two critical limitations:

Loss of Information: Coarse binarization can miss important features, high-quality trees, and the true extent of predictive multiplicity present in the continuous-feature Rashomon set.
Scalability Issues: Even with binarization, the search space is enormous. For continuous features, the number of potential cut points can be in the thousands, making exact enumeration computationally intractable with current methods.

The paper addresses the challenge of exactly enumerating decision-tree Rashomon sets over continuous features without relying on pre-defined, coarse binarization, while also providing efficient approximation and anytime algorithms.

Methodology: ArborEnum

The authors introduce ArborEnum (Algorithms for Relaying Bounds for Ordered Rashomon ENUMeration), a framework designed to enumerate Rashomon sets directly over continuous features. The methodology relies on three core components:

1. Continuous Feature Pruning via Threshold Bounds

ArborEnum adapts threshold bounds developed for finding a single optimal tree (Brit,a et al. 2025) to the enumeration setting.

Ordered Structure: Continuous features are treated as ordered blocks of threshold columns. The algorithm exploits the fact that if a threshold $x_j \le \nu$ results in a specific split, thresholds $\nu' > \nu$ create nested or related splits.
Pruning Logic: The algorithm maintains a map of proxy completions (estimated objectives) for evaluated thresholds. If a threshold's proxy-completed objective exceeds the Rashomon budget by a margin $\Delta$ , the algorithm calculates the active-sample distance (the number of samples whose branch assignment changes) to neighboring thresholds.
Interval Pruning: If moving a threshold by $k$ samples changes the proxy objective by at most $k$ , any threshold within a distance less than $\Delta$ from a "failed" threshold is guaranteed to also exceed the budget. This allows the algorithm to prune large intervals of candidate thresholds efficiently, rather than evaluating them individually.

2. Budget-Independent Subgraph Caching

To manage the combinatorial explosion, ArborEnum utilizes a novel caching strategy for the underlying AND/OR graph representation of the Rashomon set:

Canonical Nodes: Instead of caching subgraphs based on the specific budget requested, the algorithm stores a single canonical OR node for each subproblem (defined by the active sample set and remaining depth).
Deferred Extension: This node represents the largest budget for which the subproblem has been solved. If a subsequent request comes with a larger budget, the existing subgraph is extended in place rather than rebuilt. If the request has a smaller budget, the existing graph is used, and the restriction is applied only during solution extraction.
Efficiency: This approach avoids the factorial path duplication and redundant computations seen in previous methods (e.g., TreeFARMS, SORTeD) that treat different budgets as distinct subproblems.

3. Approximation and Anytime Algorithms

Recognizing that exact enumeration may remain expensive for some datasets, the authors propose:

Approximate Enumeration: The framework uses proxy algorithms (such as a modified LicketySNIP, derived from LicketySPLIT) to estimate objectives. These proxies allow for aggressive pruning. If the proxy is optimal over a specific set of thresholds, the method provides theoretical guarantees of recovering a superset of the Rashomon set for that binarization.
Anytime Algorithm (AnytimeArborEnum): This algorithm starts with a coarse set of active thresholds and progressively refines the binarization by adding new thresholds. It incrementally extends the existing AND/OR graph without restarting the computation. As the proxy strength increases or more thresholds are activated, the algorithm converges toward the exact continuous-feature Rashomon set.

Key Contributions

First Exact Enumeration for Continuous Features: ArborEnum is the first algorithm capable of exactly enumerating decision-tree Rashomon sets over continuous features without pre-binarization, leveraging the ordered structure of the data to prune the search space.
Novel Caching Mechanism: The introduction of budget-independent subgraph caching significantly reduces memory usage and runtime by avoiding redundant computations when exploring different budget levels.
Scalable Approximation: The development of LicketySNIP and associated pruning rules allows for approximate enumeration that achieves near-perfect recall (often >99%) with orders-of-magnitude speedups compared to exact methods.
Anytime Convergence: The anytime algorithm provides a flexible workflow where users can obtain useful intermediate results (identifying important features and predictive multiplicity) early, with the option to refine the binarization to convergence as computational resources allow.

Experimental Results

The authors evaluated ArborEnum on 20 datasets with continuous features, comparing it against existing methods (SORTeD, TreeFARMS, PRAXIS, RESPLIT) that require full exhaustive binarization.

Runtime Speedups: ArborEnum achieves orders-of-magnitude speedups. On the Bike dataset, the optimal method finished 63× faster than the only other method (SORTeD) that completed. On other datasets, existing methods often failed to finish within the 100-hour timeout or 128GB memory limit, whereas ArborEnum completed successfully.
Approximation Quality: Using LicketySNIP as a proxy, the method achieves nearly perfect recall (median recall of 1.000 across datasets) while being substantially faster than using an optimal proxy. Even with restricted proxies (LicketySNIP+GR), recall remains high (often >98%).
Impact of Binarization: Experiments demonstrate that coarse binarization misses significant portions of the Rashomon set. As the anytime algorithm refines the threshold set, the number of identified features and the measure of predictive multiplicity (samples with conflicting predictions) converge, often revealing important variables that coarse binarization obscured.
Overhead: The anytime algorithm incurs a median runtime overhead of only 2.7% compared to running the non-anytime algorithm on the final set of thresholds, making it a practical default choice.

Significance and Claims

The paper claims that ArborEnum fundamentally changes the feasibility of studying Rashomon sets for decision trees on continuous data. By eliminating the need for arbitrary, coarse binarization, the method ensures that the resulting set of models reflects the true structure of the data rather than artifacts of discretization.

The authors emphasize that:

Predictive Multiplicity is Underestimated: Coarse binarization can hide the existence of many high-quality, distinct models, leading to an incomplete understanding of feature importance and model robustness.
Scalability is Achievable: Through continuous-feature pruning and budget-independent caching, the computational barrier to exact enumeration is lowered, making it feasible on many datasets where it was previously impossible.
Flexibility is Key: The anytime nature of the algorithm allows practitioners to balance computational cost with solution quality, refining the analysis as time permits without losing previously computed work.

The work positions itself as a necessary step toward fully leveraging the Rashomon effect for interpretability and robustness in real-world machine learning applications involving continuous variables.