SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration

Elif Arslan, Jacobus G. M. van der Linden, Serge Hoogendoorn, Marco Rinaldi, Emir Demirović

TL;DR

The paper introduces SORTD, a novel dynamic programming framework that enumerates the "Rashomon set"—the collection of all near-optimal sparse decision trees—in strict order of their performance. By generating the best trees first, SORTD provides true anytime behavior and delivers up to a two-orders-of-magnitude speedup and a ten-fold reduction in memory usage compared to the current state-of-the-art.

What Problem Does This Paper Address?

When training a decision tree, standard algorithms look for the single "best" model that minimizes a loss function. However, real-world datasets often exhibit the Rashomon effect: there are frequently many different tree structures that achieve nearly identical, optimal performance. This collection of approximately equally good models is called the Rashomon set.

Exploring the Rashomon set is incredibly valuable. It allows practitioners to find simpler alternative models, conduct robust variable importance analysis, or select trees that satisfy secondary criteria like fairness or robustness without hard-coding these constraints into the initial training objective.

Unfortunately, because finding even a single optimal tree is NP-hard, enumerating the entire Rashomon set is computationally daunting—the set size can easily exceed $10^{12}$ trees for a simple dataset. Existing state-of-the-art tools (like TreeFARMS) require users to pre-define a strict performance tolerance multiplier. If the multiplier is too large, the system runs out of memory or times out; if it's too small, useful models are missed. Crucially, prior methods do not return trees in any sorted order, meaning you have to wait for the entire search to finish before finding the highest-quality models.

Methods

The authors propose SORTD (Sorted Rashomon Sets of Trees using Dynamic Programming), which flips the search strategy from depth-first to a best-first, lazy enumeration approach.

Key components of the method include:

  • In-Order Generation: SORTD constructs a search tree where each node maintains a sorted list of solutions. It uses a lazy evaluation strategy, computing and returning the next-best tree only when requested.
  • Sorted Cartesian Sums: To build a parent tree, branching nodes combine the best solutions from their left and right child nodes using a priority queue to ensure the combined solutions are also generated in non-decreasing order of their objective value.
  • Specialized Depth-Two Subroutine: To dramatically accelerate the search, SORTD adapts an optimized subroutine that uses precomputed feature frequency counts to instantly evaluate all subtrees of depth two or less, bypassing expensive recursive dataset splits.
  • Flexible Post-Evaluation: Because the trees are generated based on a primary, totally ordered objective (like accuracy), SORTD can pass these trees to a secondary, partially ordered objective (like fairness metrics) to efficiently map out a Pareto-optimal front.

The search tree structure and the mechanics of how next-best solutions are calculated are illustrated below:

Figure 1: Search tree structure. The left-most node is the current search node with its sorted solution list. The middle nodes are branching nodes with features f1 and f2. The right-most is a leaf node.
Figure 2: Next solution calculation in a branching node.

Datasets

The framework was evaluated using:

  • 30 Benchmark Binary Classification Datasets: Standard datasets from the UCI Machine Learning Repository and fairness benchmarks, including well-known sets like COMPAS, FICO, Adult, Bank Marketing, and HTRU2.
  • Regression Benchmarks: Datasets such as Airfoil Self-Noise, Air Quality, and Seoul Bike Sharing Demand were used to demonstrate SORTD's extensibility to regression tasks.

No new datasets were introduced in this paper.

Key Insights and Ideas

  • The Power of "Anytime" Behavior: Because SORTD outputs trees in order of performance, users can terminate the algorithm at any moment (e.g., after finding the top 100 or 1,000 trees) and still be guaranteed that they have the absolute best models available within that budget.
  • Smaller Sets Suffice for Feature Importance: The authors discovered that variable importance rankings (calculated via Leave-One-Feature-Out) stabilize significantly with just the top 100 trees. This means practitioners don't need to waste time generating millions of trees to understand feature behavior.
  • Decoupling Optimization from Constraints: Instead of designing complex, custom optimization algorithms for tricky constraints like demographic parity, SORTD allows users to optimize for accuracy first, and then easily filter the resulting sorted Rashomon set for fair models post-hoc.

Key Results

  • Speedups: SORTD consistently outperformed TreeFARMS across varying tree depths ($d \in \{3, 4, 5\}$), achieving runtimes up to two orders of magnitude faster. For deeper budgets ($d=5$), TreeFARMS frequently timed out (300s limit), while SORTD often finished in under 10 seconds.
  • Memory Efficiency: SORTD maintained a memory footprint below 1 GB for almost all test cases, representing an order-of-magnitude reduction compared to TreeFARMS, which routinely suffered from memory exhaustion on high-dimensional datasets.
  • Dimensionality Scaling: When feature counts exceeded 30, TreeFARMS failed to complete, whereas SORTD scaled gracefully, remaining well below the time limit.

Limitations and Future Work

  • Binary Features Only: The current implementation of SORTD is strictly limited to datasets with binary features. Extending the dynamic programming and frequency-counting subroutines to continuous features remains a challenge.
  • Scalability Ceilings: While SORTD pushes the boundaries of what is practical, the underlying problem is still NP-hard. For exceptionally large depth budgets ($d > 5$) or massive feature spaces, the combinatorial explosion will eventually make full enumeration intractable.

Future work could focus on relaxing the binary feature constraint and exploring heuristic bounds to approximate sorted Rashomon sets for even larger architectures.

Summary updated

Abstract

Sparse decision tree learning provides accurate and interpretable predictive models that are ideal for high-stakes applications by finding the single most accurate tree within a (soft) size limit. Rather than relying on a single "best" tree, Rashomon sets-trees with similar performance but varying structures-can be used to enhance variable importance analysis, enrich explanations, and enable users to choose simpler trees or those that satisfy stakeholder preferences (e.g., fairness) without hard-coding such criteria into the objective function. However, because finding the optimal tree is NP-hard, enumerating the Rashomon set is inherently challenging. Therefore, we introduce SORTD, a novel framework that improves scalability and enumerates trees in the Rashomon set in order of the objective value, thus offering anytime behavior. Our experiments show that SORTD reduces runtime by up to two orders of magnitude compared with the state of the art. Moreover, SORTD can compute Rashomon sets for any separable and totally ordered objective and supports post-evaluating the set using other separable (and partially ordered) objectives. Together, these advances make exploring Rashomon sets more practical in real-world applications.
BibTeX
@inproceedings{arslan2025sorted,
  author = {Elif Arslan and Jacobus G. M. van der Linden and Serge Hoogendoorn and Marco Rinaldi and Emir Demirović},
  title = {{SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=Gibq7Wa7Bq},
}
Figure