Near-Optimal Decision Trees in a SPLIT Second

Near-Optimal Decision Trees in a SPLIT Second

Speakers: Varun Babbar, Hayden McTavish, Cynthia Rudin, Margo Seltzer

Conference: ICML 2025

YouTube: https://slideslive.com/39044057

Overview

This article delves into the groundbreaking work presented by Varun Babbar and Hayden McTavish at ICML 2025, detailing their paper "Near-Optimal Decision Trees in a SPLIT Second." The talk introduces SPLIT and Re-SPLIT, two novel algorithms designed to revolutionize the construction of interpretable decision trees. At its core, this research addresses a long-standing challenge in machine learning: achieving the high performance of globally optimal decision trees without incurring their prohibitive computational costs, while simultaneously exploring the rich landscape of near-optimal models.

The primary objective of the SPLIT algorithm is to generate decision trees that dramatically outperform traditional greedy methods like CART in terms of objective function minimization, yet are orders of magnitude faster to compute than fully optimal approaches. This speedup, often hundreds of times faster, allows for the rapid deployment and iteration of high-quality, interpretable models. Beyond single trees, the Re-SPLIT algorithm extends this capability to approximate the Rashomon set, which encompasses a multitude of near-optimal models, offering practitioners a diverse portfolio of choices that can be evaluated against criteria beyond mere accuracy, such as alignment with domain knowledge or ethical considerations.

The significance of this work lies in its ability to mitigate, or even avoid, the interpretability-accuracy tradeoff often encountered with complex models, especially for noisy tabular data. By providing near-optimal, transparent models at unprecedented speeds, SPLIT and Re-SPLIT empower researchers and practitioners to leverage the inherent interpretability of decision trees without compromising on predictive performance or computational efficiency. This advancement is particularly crucial in domains where model transparency and the ability to explain predictions are paramount.

Background

▶ Watch: Introduction and TLDR: Near-Optimal Trees in a SPLIT Second (0:00)

Decision trees are a foundational and inherently interpretable model class in machine learning. Their transparency stems from their ability to communicate the entire process from input data to predictions as a simple, intuitive flowchart of yes/no questions. This characteristic makes them invaluable in applications requiring high trust and explainability, such as medical diagnosis, financial risk assessment, and regulatory compliance. However, the construction of high-performing decision trees has historically presented a dilemma between computational feasibility and global optimality.

Prior approaches to decision tree construction generally fall into two categories:

1. Greedy Algorithms (e.g., CART): These methods operate by making the locally optimal split choice at each node based on a heuristic, such as information gain, without considering the global implications of that choice. While incredibly fast to compute, greedy trees are inherently suboptimal. A suboptimal choice made early in the tree construction process can lead to a cascading effect, resulting in a tree with a significantly higher objective (e.g., misclassification loss plus leaf penalty) than what is globally achievable. On an objective-versus-runtime plot, greedy trees occupy the top-left quadrant: very fast but with a large objective value.

1. Optimal Decision Tree Algorithms: These methods aim to find the globally optimal decision tree by exhaustively searching the vast combinatorial space of possible trees. Such approaches guarantee the best possible objective value for a given depth budget. However, their computational complexity is a major bottleneck. For large datasets with many features, finding an optimal tree can take an impractically long time, often requiring the exploration of exponentially growing branches. This is because to ensure global optimality, one must consider all possible splits at each depth, leading to an intractable problem as the tree deepens. On an objective-versus-runtime plot, optimal trees reside in the bottom-right quadrant: minimal objective value but with excessively long runtimes, potentially taking minutes or even hours for moderately sized datasets.

The problem, therefore, is to bridge this significant gap. Researchers are interested in decision trees because optimal decision trees have been shown to approach state-of-the-art performance for noisy tabular data, suggesting that the interpretability-accuracy tradeoff can be mitigated if trees are optimized effectively. Furthermore, the concept of the Rashomon effect—the existence of a multiplicity of near-optimal models on many datasets—highlights the need to not just find one good tree, but to understand and navigate the set of all good trees. The objective function typically optimized is misclassification loss combined with a penalty on the number of leaves, encouraging sparser, more interpretable trees. The work presented in this talk directly addresses the need for algorithms that can rapidly find not just one, but many, high-quality, interpretable decision trees.

Key Findings

▶ Watch: Introducing SPLIT: Bridging the Gap (2:20)

The research introduces two pivotal algorithms, SPLIT and Re-SPLIT, which collectively deliver a paradigm shift in the construction and exploration of decision trees.

The primary finding is that the SPLIT algorithm can generate individual decision trees whose performance is dramatically superior to greedy methods like CART, achieving an objective value almost identical to that of fully optimal methods. Crucially, SPLIT accomplishes this with a computational runtime that is hundreds of times faster than existing state-of-the-art optimal tree algorithms. For instance, on the HELOC dataset, SPLIT and its recursive variant, Lickety-SPLIT, achieved comparable accuracy to the optimal GHOST algorithm while being hundreds to nearly 500 times faster, reducing computation from minutes to mere seconds. This speedup fundamentally changes the feasibility of deploying and iterating on highly interpretable models in real-world applications.

A second key finding is the development of the Re-SPLIT algorithm, which extends SPLIT's principles to efficiently approximate the Rashomon set. The Rashomon set is defined as the collection of all models whose performance falls within an epsilon margin of the globally optimal objective. Re-SPLIT is capable of generating thousands of such sparse, near-optimal decision trees in a fraction of the time required by exact Rashomon set methods, often orders of magnitude faster. Despite this immense speedup, the quality of the approximation is remarkably high. When evaluating the importance of features, Re-SPLIT's approximation of the Rashomon set showed an almost perfect correlation (nearly 1) in ranked variable importances compared to the exact Rashomon set, as measured by metrics like that proposed by Donnelly et al. This demonstrates that Re-SPLIT not only finds many good trees quickly but also faithfully captures the underlying data relationships and model diversity.

These findings collectively demonstrate that it is possible to largely overcome the traditional interpretability-accuracy tradeoff in machine learning for tabular data. By providing algorithms that rapidly produce near-optimal, interpretable models and enable the exploration of model multiplicity, this research opens new avenues for robust, ethical, and transparent AI system development.

Technical Deep Dive

▶ Watch: SPLIT Algorithm Mechanics: Initial Optimal, then Greedy (3:00)

The core challenge in constructing optimal decision trees lies in the combinatorial explosion of choices. For a tree to be truly optimal, every split, starting from the root, must be chosen optimally, given that all subsequent splits will also be optimal. This necessitates bounding or fully establishing the performance of an optimal method on every possible subproblem, which is computationally intractable for all but the smallest datasets.

SPLIT Algorithm: Bridging the Optimality-Speed Gap

The SPLIT algorithm addresses this by introducing a strategic relaxation of global optimality, leveraging an empirical insight: the performance gap between greedy and optimal trees tends to diminish significantly as one descends deeper into the tree. This allows SPLIT to focus computational effort where it matters most – at the initial, high-impact splits.

SPLIT operates in a two-stage process:

1. Initial Lookahead with Greedy Completion: The algorithm begins by identifying the "best choices at the first few stages of the tree," or an optimal prefix. This prefix is determined under the condition that all subsequent subtrees branching from its leaves will be constructed greedily. This significantly reduces the combinatorial search space compared to full optimality, as the intractable "optimal given subsequent optimal behavior" constraint is replaced by a more manageable "optimal given subsequent greedy behavior" constraint. The choice of lookahead depth (the number of initial splits optimized) is crucial here.

1. Post-processing with Optimal Subtree Replacement: Once the initial set of splits (the prefix) and its associated greedy subtrees are established, SPLIT performs a post-processing step. It replaces these initially greedy subtrees with subtrees that are truly optimal, but conditioned on the splits already made in the prefix. This is a critical step because solving several shallower optimal subproblems (e.g., finding optimal depth-3 subtrees for each leaf of a depth-2 prefix) is computationally much easier than solving one deep optimal problem (e.g., finding a single optimal depth-5 tree from scratch). This post-processing guarantees a monotonic improvement in the quality of the solution. The optimal lookahead depth for this strategy is empirically found to be approximately half of the total desired tree depth, plus or minus a term that decays with the number of features ($K$). This two-stage approach results in an exponential speedup, relative to the number of features, compared to a fully optimal method.

Lickety-SPLIT: A Recursive Polynomial-Time Approach

Building upon SPLIT, the authors introduce Lickety-SPLIT, a recursive variant that further refines the trade-off. Instead of a fixed lookahead depth, Lickety-SPLIT employs a recursive strategy:

1. It starts with a lookahead depth of one, finding the single optimal root split conditioned on the rest of the tree being built greedily.
2. During the post-processing phase, instead of simply finding one optimal subtree, it recursively applies the same Lickety-SPLIT approach to each subtree. This means for each branch, it finds the next optimal split conditioned on greedy behavior for the remainder, and so on, until the entire tree is filled out.

This recursive method results in an algorithm that is linear in the number of samples ($N$), quadratic in the number of features ($K$), and quadratic in the total depth ($D$) of the tree. This polynomial time complexity is a significant theoretical and practical improvement over the exponential complexity of traditional optimal tree algorithms, allowing for even faster computation while maintaining near-optimal performance.

Re-SPLIT Algorithm: Approximating the Rashomon Set

The Re-SPLIT algorithm extends the SPLIT paradigm to address the Rashomon effect, aiming to find not just one near-optimal tree, but a large collection of them.

1. Near-Optimal Prefixes: Re-SPLIT begins by identifying not just the optimal prefix, but the set of all near-optimal prefixes (within an $\epsilon$ margin of optimality for the prefix) conditioned on greedy behavior for subsequent subtrees. This initial step yields a collection of diverse prefixes.

1. Cross-Product of Optimal Completions: For each prefix in this collection, Re-SPLIT then performs a post-processing step similar to SPLIT, but with a critical difference. Instead of replacing greedy subtrees with a single optimal subtree, it replaces them with the set of all exact optimal subtrees (or near-optimal subtrees) for that particular, shallower subproblem. Because these are shallower problems, solving for the set of all optimal solutions remains computationally feasible.

1. Explosion of Trees: By taking the cross-product of these sets of optimal completions for each branch of a near-optimal prefix, Re-SPLIT generates a vast number of diverse, well-performing decision trees. Each of these trees shares the property of being relatively well-performing, and together they effectively approximate the true Rashomon set. The computational efficiency comes from breaking down a single, deep, intractable "Rashomon set" problem into many smaller, tractable "Rashomon set" problems for shallower subtrees.

Experimental Setup & Results

▶ Watch: Performance Results: SPLIT vs. GHOST on HELOC (5:00)

The effectiveness of SPLIT and Re-SPLIT was rigorously evaluated across various tabular datasets, with a particular focus on the HELOC dataset. HELOC is a real-world tabular dataset commonly used in credit risk assessment, featuring tens of thousands of examples and 50 to 100 features, making it a representative challenge for decision tree algorithms.

Baselines:

The primary baseline for comparison was GHOST, a state-of-the-art optimal decision tree method that utilizes branch and bound optimization to find globally optimal trees. The researchers also compared their methods against "a bunch of other optimal tree methods," implicitly demonstrating broad applicability and superior performance. Traditional greedy methods like CART served as an implicit lower bound for performance and an upper bound for speed, highlighting the gap SPLIT aims to bridge.

Metrics:

The evaluation focused on several key metrics:

• Training Objective: The value of the objective function (misclassification loss + leaf penalty) on the training data.
• Test Objective: The objective function value on unseen test data, indicating generalization performance.
• Runtime: The computational time required to construct the decision trees.
• Rashomon Set Approximation Quality: For Re-SPLIT, this was assessed by comparing the ranked variable importances within the approximated Rashomon set to those from an exactly computed Rashomon set, using a metric proposed by Donnelly et al.

Headline Results:

1. SPLIT vs. GHOST (Individual Tree Performance):

• Training Objective: SPLIT and Lickety-SPLIT achieved "exactly the same training objective as GHOST," indicating that they closely match the optimal solution's performance on the training data.
• Test Objective: They achieved "almost the same test objective as well," demonstrating excellent generalization performance, nearly on par with globally optimal trees.
• Runtime: This is where SPLIT truly shines. On the HELOC dataset, GHOST took approximately five minutes to find an optimal tree. In stark contrast, SPLIT was "hundreds of times faster," and Lickety-SPLIT was "almost 500 times faster" for achieving the same level of performance. These results were consistent "across all other datasets that we tested."

1. Re-SPLIT vs. Exact Rashomon Set (Multi-Tree Performance):

• Runtime: Re-SPLIT demonstrated a dramatic speedup, being "a couple of orders of magnitude faster than the current state-of-the-art exact Rashomon set" algorithms. This enables the practical generation of thousands of near-optimal models.
• Approximation Quality: Despite the immense speed, the fidelity of Re-SPLIT's approximation of the Rashomon set was exceptionally high. By ranking features based on their importance within each set and correlating these rankings, the researchers found a correlation that was "almost perfect, almost exactly one." This indicates that Re-SPLIT faithfully captures the essential characteristics and diversity of the true Rashomon set, providing a reliable basis for understanding variable importance and model multiplicity.

These experimental results unequivocally demonstrate that SPLIT and Re-SPLIT successfully deliver on their promise: near-optimal decision trees and Rashomon set approximations can be computed in seconds, not minutes or hours, thereby making high-quality, interpretable models accessible for a much broader range of real-world applications.

Practical Implications

▶ Watch: Approximating the Rashomon Set with SPLIT (6:00)

The development of SPLIT and Re-SPLIT carries profound practical implications for a wide array of stakeholders in the machine learning ecosystem, from individual practitioners to large-scale infrastructure teams.

For practitioners and model builders, the most immediate benefit is the ability to rapidly generate highly interpretable decision trees that achieve near-optimal predictive performance. This directly addresses the long-standing interpretability-accuracy tradeoff, particularly for noisy tabular data where decision trees are often preferred for their transparency. Previously, choosing an interpretable model like a decision tree often meant sacrificing some predictive power compared to complex black-box models, or enduring prohibitively long training times for optimal trees. With SPLIT, practitioners can now confidently deploy models that are both performant and fully transparent, allowing for clear communication of decision logic to non-technical stakeholders, regulatory bodies, or end-users. This is especially critical in high-stakes domains like healthcare, finance, and legal systems.

Furthermore, Re-SPLIT's ability to quickly approximate the Rashomon set fundamentally changes how models are selected and understood. Instead of settling for a single "best" model, practitioners can explore a diverse collection of thousands of near-optimal trees. This enables a more holistic model selection process, where criteria beyond just accuracy can be incorporated. For instance, a model builder might choose a tree that aligns better with existing domain knowledge, exhibits more favorable ethical properties (e.g., fairness metrics), or has simpler decision paths, even if another tree has a marginally (within epsilon) better objective score. This capability also provides a more robust understanding of variable importance, as it allows for insights into how feature relevance might vary across different near-optimal explanations, rather than relying on a single model's perspective.

For infrastructure teams and deployers, the significant speedup offered by SPLIT (hundreds of times faster) translates directly into reduced computational costs and faster development cycles. Training complex optimal decision trees previously required substantial compute resources and time. SPLIT and Lickety-SPLIT bring this down to seconds, making it feasible to train and fine-tune decision tree models on large datasets in interactive settings or within tight deployment schedules. This efficiency can lead to quicker experimentation, faster model updates, and a more agile MLOps pipeline for interpretable models.

Tradeoffs and Limitations:

While revolutionary, the algorithms do come with certain considerations. The "near-optimal" nature of SPLIT means it's not strictly guaranteed to find the absolute global optimum, unlike methods like GHOST. However, the experimental results clearly show that the performance gap is negligible for the vast majority of practical applications, especially when weighed against the massive speed advantage.

A recognized area of ongoing research for the authors is to characterize the specific dataset properties under which the algorithms might experience a degradation in accuracy. The talk mentions that "for certain types of data distributions, the gap between our method and a greedy method is arbitrarily large," implying that in some extreme cases, the benefit of post-processing or deeper lookahead depths might vary, or the performance might converge more slowly towards optimal. Understanding these boundary conditions will help practitioners determine when SPLIT is most effective and when alternative approaches or deeper lookahead depths might be warranted. This also includes evaluating when the difference between greedy and optimal trees is minimal, potentially simplifying the required lookahead depth or post-processing effort.

In summary, SPLIT and Re-SPLIT offer a powerful toolkit for building and deploying interpretable AI systems, democratizing access to high-quality decision trees and fostering a deeper, more nuanced understanding of model behavior and selection.

Key Takeaways

• Near-Optimal Performance with Unprecedented Speed: The SPLIT and Lickety-SPLIT algorithms produce decision trees with objective function values almost identical to globally optimal methods, but with runtimes hundreds to nearly 500 times faster (e.g., seconds instead of minutes on HELOC).
• Efficient Rashomon Set Approximation: Re-SPLIT extends this capability to approximate the Rashomon set – the collection of all near-optimal models – orders of magnitude faster than exact methods, providing thousands of diverse, high-performing interpretable trees.
• Mitigating Interpretability-Accuracy Tradeoff: This research demonstrates that for noisy tabular data, it is possible to achieve state-of-the-art predictive performance with inherently interpretable decision trees, effectively bridging the gap between accuracy and transparency.
• Holistic Model Selection and Understanding: Exploring the Rashomon set allows practitioners to select models based on a broader range of criteria (e.g., domain knowledge, ethical alignment, simplicity) beyond just raw accuracy, and to gain a more robust understanding of variable importance across multiple explanations.
• Hybrid Optimization Strategy: The core technical innovation involves combining initial optimal lookahead (for high-impact splits) with efficient greedy completions and recursive post-processing to replace greedy subtrees with optimal ones, leveraging the decreasing gap between greedy and optimal performance deeper in the tree.
• Faithful Approximation: Re-SPLIT's approximation of the Rashomon set maintains exceptional fidelity, with an almost perfect correlation in ranked variable importances compared to exact methods, ensuring that the diversity captured is meaningful.

About the Speaker(s)

The talk was presented by Varun Babbar and Hayden McTavish, who are key contributors to the research. They are part of a research group that includes senior figures Cynthia Rudin and Margo Seltzer, indicating their affiliation with a prominent academic lab known for its work in interpretable machine learning. Cynthia Rudin's lab is specifically mentioned as a source of foundational work on the benefits of exploring the Rashomon set and understanding model multiplicity. While specific titles and affiliations beyond the conference context are not detailed in the transcript, their expertise lies in developing advanced algorithms for optimal and interpretable machine learning models, particularly decision trees.