🤖 machine learning

Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again

This paper introduces Multistage Defer Trees, a hybrid interpretability framework that chains sparse decision trees to classify most samples transparently while deferring difficult cases to subsequent trees or black-box models, thereby achieving state-of-the-art accuracy without sacrificing interpretability for the majority of data.

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

Published 2026-07-01

📖 5 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

The Big Problem: The "Black Box" vs. The "Simple Map"

Imagine you are trying to navigate a city.

The Black Box: This is like a super-smart GPS that knows every shortcut, traffic jam, and construction zone. It gets you to your destination perfectly every time (high accuracy), but it doesn't tell you why it chose that route. It just says, "Turn here." You can't understand its logic.
The Simple Tree: This is like a basic paper map with a few clear rules: "If you see a red light, turn left. If you see a park, go straight." It is easy to understand (interpretable), but it often gets you lost in complex traffic (lower accuracy).

For a long time, data scientists had to choose: Do you want a perfect route you can't understand, or a simple route that might fail?

The New Solution: The "Specialist Team" (Multistage Defer Trees)

The authors propose a new way to drive that gets the best of both worlds. Instead of one driver making all the decisions, they create a relay team of specialists.

Think of it like a triage system in a hospital or a customer service escalation line:

Stage 1 (The Generalist): The first "doctor" (a simple decision tree) looks at the patient (the data).
- If the case is straightforward (e.g., a broken arm), the doctor treats it immediately and sends the patient home. This is interpretable because the rule is simple: "Broken arm = Cast."
- If the case is weird or complicated (e.g., a rare, confusing set of symptoms), the doctor says, "I'm not sure. I'm going to defer this to the next specialist."
Stage 2 (The Specialist): The second doctor receives only the difficult cases that the first doctor couldn't handle. Because they only see the hard stuff, they can be slightly more complex, but they are still a simple tree.
- They solve most of these cases.
- If a case is still too weird for them, they defer it to the next stage.
The Final Stage (The Black Box): If the case is so incredibly complex that even the second specialist is stumped, it finally gets passed to the "Black Box" (the super-smart GPS or AI).

Why This is a Big Deal

The paper claims this method solves three major problems:

1. Most people get a simple explanation.
In this system, 90% (or more) of the data is handled by the first or second simple tree. You get a clear, human-readable rule for almost every decision. You only use the "Black Box" for the tiny fraction of data that is truly impossible to explain simply.

2. The "Black Box" gets smaller and simpler.
Usually, a Black Box has to be huge to handle everything. But here, the Black Box only has to handle the tiny, specific group of "weird" cases that the simple trees couldn't solve.

Analogy: Imagine a library. Usually, you need a massive, chaotic library to find any book. But if you have a simple card catalog that sorts 99% of books into "Fiction" and "Non-Fiction," the "Special Section" only needs to hold the 1% of obscure, weird books. That Special Section can be much smaller and easier to manage.

3. It learns as it goes.
The paper describes a training process where the team learns together.

First, they train the Black Box.
Then, they train the first simple tree to catch the easy stuff and pass the rest to the Black Box.
Then, they train the next simple tree to catch the stuff the first tree missed, and so on.
Crucially, they use a "distance" trick. If a data point is close to being a "hard case," the system gives it extra attention during training, ensuring the simple trees get really good at handling the "borderline" cases so they don't have to pass them to the Black Box.

The Results

The authors tested this on many different datasets (like predicting bike rentals, credit card fraud, or wine quality). They found that:

Their "Team of Trees" was almost as accurate as the giant, complex Black Box models.
However, for the vast majority of predictions, the system used only 1 or 2 simple trees.
This means you get the accuracy of the complex model with the transparency of a simple rulebook for almost everyone.

Summary Metaphor

Imagine a Law Firm:

Old Way: You hire one "Super Lawyer" who knows every law in the universe. They win every case, but you have no idea how they argued it.
New Way (MDT): You hire a team of Junior Associates (Simple Trees).
- They handle 95% of the cases using clear, standard rules.
- If a case is too weird, they pass it to a Senior Partner (the next tree).
- If it's still too weird, they pass it to the Famous Expert (the Black Box).
The Result: You get a clear explanation for 95% of your cases. The Famous Expert only has to work on the 5% of cases that are truly impossible, and because they only see those 5%, their work can be simplified and understood much better than if they had to do everything alone.

The paper concludes that we don't have to choose between being smart and being understandable. We can be both, by letting simple models do the heavy lifting and saving the complex "magic" only for the truly difficult problems.

Technical Summary: Multistage Defer Trees for Hybrid Interpretability

Problem Statement

The central challenge in interpretable machine learning is constructing models that match state-of-the-art predictive performance while remaining transparent. While well-optimized sparse decision trees can achieve this in noisy domains, a significant accuracy-interpretability gap persists in many settings. In these cases, complex ensembles (e.g., Random Forests, XGBoost) are required for high accuracy, but they lack interpretability. Existing hybrid approaches attempt to bridge this gap by using a simple model to predict on most data and deferring difficult samples to a black box. However, current methods often struggle to maintain black-box accuracy without deferring the vast majority of samples, or they fail to recover interpretability for the deferred subset.

Methodology

The authors introduce Multistage Defer Trees (MDTs), a model class that adaptively allocates complexity by routing inputs through a sequence of sparse decision trees before potentially deferring to a black box.

Core Definitions

Defer Tree: A binary tree where leaves are labeled with either a class prediction or a defer action. If a leaf defers, the prediction is passed to a fallback model $B$ .
Multistage Defer Tree (MDT): An ordered sequence of defer trees $(T_1, \dots, T_K)$ . An input $x$ is evaluated by $T_1$ . If $T_1$ predicts, the process stops. If $T_1$ defers, $x$ is passed to $T_2$ , and so on. If all trees defer, the final fallback model $B$ (which can be a black box or a sparse model) makes the prediction.

Training Algorithm

The training procedure employs an iterative, top-down alternating optimization strategy:

Initialization: Start with a fallback model $B$ trained on the full dataset.
Iterative Stage Training: For stage $j$ , train a defer tree $T_j$ on the subset of data deferred by previous stages. The objective function penalizes misclassification, tree complexity (number of splits), and deferrals to the current fallback model.
Fallback Update: After training $T_j$ $T_{j}$ , the deferred set is updated. The fallback model $B$ $B$ is retrained on the full dataset using distance-based weights.
- Deferred points receive full weight.
- Non-deferred points are down-weighted based on their distance to the deferred region (measured in quantile space). This allows the fallback model to "borrow strength" from nearby points, improving generalization in the deferred region and preventing overfitting to specific deferred samples.
Feasible Region Tracking: The algorithm tracks the geometric intersection of defer regions (axis-aligned hyperrectangles) to filter out splits that are irrelevant to the current deferred region, improving efficiency.
Termination: The process stops when the deferred set becomes empty, stops shrinking, or exceeds complexity budgets (e.g., total leaves or expanded single-tree size).

Compression and Representation

A key theoretical contribution is the Rule-List Representation of MDTs. Theorem 1 establishes that an MDT with $K$ stages can be represented as a rule list where each non-deferral leaf in any stage contributes exactly one antecedent. This results in a compact representation significantly smaller than rule lists derived from standard ensembles (like Random Forests), where antecedents can grow with the sum of depths across all trees.

The authors also provide algorithms to compress the MDT into a single defer tree by recursively expanding defer leaves and pruning splits that are guaranteed to evaluate the same way within the specific subregion of the deferred data.

Key Contributions

Model Class: Introduction of Multistage Defer Trees, which adaptively allocate complexity based on the difficulty of different regions of the feature space.
Training Algorithm: Development of an iterative algorithm that successively narrows the deferral region while using distance-based reweighting to improve generalization of the fallback model.
Compression Techniques: Algorithms to compress MDTs into sparse single-tree or rule-list representations, and methods to compress the fallback model (if it is a tree ensemble) specifically for the deferred subset.
Theoretical Guarantees: Proofs regarding the rule-list representation size and the monotonic improvement of the objective function during training.

Experimental Results

The authors evaluated MDTs against state-of-the-art tree ensembles (XGBoost, Random Forest), sparse additive models (FIGS), and existing hybrid baselines (HyRS, CORELS variants) across 24 datasets.

Accuracy vs. Deferral: MDTs consistently matched the performance of complex black-box ensembles (XGBoost) while deferring a small proportion of samples (e.g., $\le 25\%$ ). In many datasets, MDTs achieved accuracy within the 95% confidence interval of the best black-box method with significantly lower deferral rates than competing hybrid models.
Interpretability: The interpretable component of MDTs (the sequence of trees) required very few split decisions per sample (often $\le 5.5$ splits on average) to reach near-black-box performance.
Compression: When the fallback model was a tree ensemble, the authors demonstrated that compressing the fallback specifically for the deferred region resulted in significant reductions in the number of splits and leaves required, without sacrificing accuracy in that region.
Comparison to Baselines: MDTs outperformed single non-deferring trees and existing hybrid methods (like HyRS and FLMM) in the accuracy-deferral trade-off, particularly in regimes where a single tree is insufficient.

Significance and Claims

The paper claims that MDTs expand the accuracy–interpretability frontier. The authors argue that even when complex models are necessary to achieve state-of-the-art accuracy, they need not be fully opaque. By routing the majority of data through a small number of sparse trees and confining the reliance on complex models to a tightly constrained region of the feature space, MDTs allow practitioners to maintain high accuracy while ensuring that most decisions remain interpretable. The method demonstrates that the trade-off between accuracy and interpretability is not necessarily global; it can be managed locally, with complexity allocated only where simple models provably fail.