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

# Multistage Defer Trees for Hybrid Interpretability: If at First You Can’t Succeed, Tree Again
Source: [https://arxiv.org/html/2606.30995](https://arxiv.org/html/2606.30995)
Zakk Heile Department of Computer Science Duke University Durham, USA zakk\.heile@duke\.edu &Hayden McTavish11footnotemark:1 Department of Computer Science Duke University Durham, USA hayden\.mctavish@duke\.edu &Margo Seltzer Department of Computer Science University of British Columbia Vancouver, Canada mseltzer@cs\.ubc\.ca &Cynthia Rudin Department of Computer Science Duke University Durham, USA cynthia@cs\.duke\.edu

###### Abstract

Recent work has shown that well\-optimized individual decision trees can match complex black box models in some settings, primarily in noisy domains\. For the remaining settings, however, complex ensembled compositions of trees often achieve higher accuracy at the cost of interpretability, leaving practitioners with difficult modeling decisions along an accuracy\-interpretability tradeoff\. Ideally, we would like to classify as much of the data as possible with one or a small number of trees, achieving interpretability for most samples while maintaining state\-of\-the\-art accuracy\. We introduce Multistage Defer Trees: a sequence of sparse decision trees that each make predictions for most samples, while deferring a small proportion to the next tree in the sequence or, ultimately, to a black box\. We demonstrate that we can train this model class to match the performance of complex tree\-based ensembles while routing most samples through only one or a small number of sparse decision trees\. We discuss a range of techniques for training these models while maintaining simplicity\. Our method expands the accuracy–interpretability frontier in settings where single\-tree methods remain insufficient, demonstrating that even when complex models are necessary, they need not be fully opaque\.

## 1Introduction

A central challenge in interpretable machine learning is to construct interpretable models that match state\-of\-the\-art predictive performance\. Well\-optimized simple models, such as optimal sparse trees, can achieve this goal in certain settings, such as when the data is generated by noisy processes\[[65](https://arxiv.org/html/2606.30995#bib.bib48),[64](https://arxiv.org/html/2606.30995#bib.bib47),[9](https://arxiv.org/html/2606.30995#bib.bib49)\]\. In such cases, the accuracy\-interpretability gap is not observed\. Still, there remains such a gap in datasets falling outside of this regime\.

One proposed direction to navigate the accuracy\-interpretability gap is to use a hybrid\- or partially\-interpretable model\[[70](https://arxiv.org/html/2606.30995#bib.bib2),[71](https://arxiv.org/html/2606.30995#bib.bib1),[57](https://arxiv.org/html/2606.30995#bib.bib3),[23](https://arxiv.org/html/2606.30995#bib.bib4),[26](https://arxiv.org/html/2606.30995#bib.bib44),[35](https://arxiv.org/html/2606.30995#bib.bib52)\]\. The goal is to learn a simple interpretable model that, for each sample, either makes a prediction for that sample or defers to a black box’s prediction\. By specifying the proportion of samples classified by a black box \(the deferral rate\), users can navigate a tradeoff between matching black box accuracy and keeping decisions interpretable for more samples\. While hybrid\-interpretable models provide a smooth way to navigate compromises between accuracy and interpretability, existing methods often struggle to maintain black box accuracy without deferring the vast majority of samples\.

![Refer to caption](https://arxiv.org/html/2606.30995v1/x1.png)Figure 1:Example of an MDT on the Bike dataset\. The model consists of two stages, each with bounded depth\. Two leaves in the first stage defer to the second stage, and three leaves in the second stage defer to a black box \(here, an XGBoost model\)\. The interpretable component has 13 leaves\.We present a tree\-based hybrid\-interpretable model that minimizes deferral rate while matching the performance of more complex ensembles\. To learn this model, we iteratively focus on subsets of the data where simple models provably cannot perform as well as a black box model\. This leads to a new model class,*Multistage Defer Trees \(MDTs\)*, where each tree can either make a prediction or defer to the next stage; the final stage may then defer some samples to a black box model if required\.

To train MDTs, we introduce an alternating optimization procedure in which the deferred\-to model evolves with each stage of the MDT\. As this process unfolds, the set of deferred points decreases monotonically, and the later stages and fallback model become increasingly specialized to those points\. This allows the model to defer only on a small fraction of inputs while maintaining high accuracy\. When the fallback is a sparse model \(i\.e\., a single decision tree or EBM\[[37](https://arxiv.org/html/2606.30995#bib.bib111)\]\), even these deferral cases remain interpretable; when the fallback is a black box, performance can be matched with minimal reliance on that model\. Crucially, because deferred points are confined to a tightly constrained region of the feature space, the fallback model can be compressed, producing simpler but equivalent representations of even complex ensembles\.

Our contributions are as follows\.

- •We introduce Multistage Defer Trees \(MDTs\), a new model class that allocates complexity adaptively, based on the difficulty of different regions of the feature space\.
- •We develop an iterative algorithm for training MDTs that successively narrows the deferral region, while borrowing strength from surrounding regions, to learn specialized trees that generalize well\.
- •We provide algorithms to compress MDTs into sparse single\-tree or rule\-list representations and extend this framework to compress the fallback model when it is a tree or tree ensemble\.
- •We demonstrate improved accuracy–deferral–sparsity trade\-offs where such trade\-offs exist\.

## 2Related Work

##### Hybrid Approaches

Wang \[[71](https://arxiv.org/html/2606.30995#bib.bib1)\]introduces hybrid models for interpretability: an interpretable rule set or linear model makes predictions on some of the data, while deferring to fixed black box predictions on the remaining data\. This allows users to navigate a tradeoff between the model accuracy and the amount of samples using interpretable model predictions\. This framework, in turn, connects to work in deferral models\[[38](https://arxiv.org/html/2606.30995#bib.bib12),[47](https://arxiv.org/html/2606.30995#bib.bib13)\], rejection learning\[[13](https://arxiv.org/html/2606.30995#bib.bib17),[62](https://arxiv.org/html/2606.30995#bib.bib54)\], selective classification\[[19](https://arxiv.org/html/2606.30995#bib.bib24)\], and abstention\-based learning\[[63](https://arxiv.org/html/2606.30995#bib.bib55),[25](https://arxiv.org/html/2606.30995#bib.bib23)\]\. Hybrid models have primarily been applied to simple rule set models or linear models\[[26](https://arxiv.org/html/2606.30995#bib.bib44),[23](https://arxiv.org/html/2606.30995#bib.bib4),[71](https://arxiv.org/html/2606.30995#bib.bib1),[57](https://arxiv.org/html/2606.30995#bib.bib3),[70](https://arxiv.org/html/2606.30995#bib.bib2)\]\. One recent work explores a gradient\-based method to learn a complex \(100\-1000 leaves\) decision tree, which defers to a black box based on computing the proximity to the decision boundary\[[35](https://arxiv.org/html/2606.30995#bib.bib52)\]; by contrast, our work learns a sparser sequence of trees that directly defer where the black box is most helpful, and iteratively reduces this deferral region\.

##### Decision Tree Optimization

Decision trees are classically optimized with highly scalable greedy algorithms\[[10](https://arxiv.org/html/2606.30995#bib.bib20),[58](https://arxiv.org/html/2606.30995#bib.bib29)\]\. Such algorithms can be ideal for popular ensembles of many trees\[[11](https://arxiv.org/html/2606.30995#bib.bib18),[12](https://arxiv.org/html/2606.30995#bib.bib11)\]\. More recent work, however, has revisited the use of less scalable, higher quality individual tree algorithms, to reduce the need for this level of model complexity and to allow use of a single well\-performing sparse tree classifier for domains where interpretability is needed\. In recent years, global optimization of individual trees has become reasonably tractable for bounded depth and sparsity\[[1](https://arxiv.org/html/2606.30995#bib.bib28),[30](https://arxiv.org/html/2606.30995#bib.bib33),[17](https://arxiv.org/html/2606.30995#bib.bib21),[36](https://arxiv.org/html/2606.30995#bib.bib42),[43](https://arxiv.org/html/2606.30995#bib.bib34),brița2025optimal,[6](https://arxiv.org/html/2606.30995#bib.bib26),[68](https://arxiv.org/html/2606.30995#bib.bib27)\]\. This problem is nevertheless NP\-hard and does struggle to scale to cases with many features\. Recent work sacrifices global optimality in exchange for improved scalability and runtime while maintaining performance close to optimal\[[3](https://arxiv.org/html/2606.30995#bib.bib37),[7](https://arxiv.org/html/2606.30995#bib.bib32),[32](https://arxiv.org/html/2606.30995#bib.bib39)\]\. Other approaches add anytime behavior, allowing early termination with high\-quality solutions\[[33](https://arxiv.org/html/2606.30995#bib.bib30),[16](https://arxiv.org/html/2606.30995#bib.bib31),[34](https://arxiv.org/html/2606.30995#bib.bib40)\]\.

We fit a small sequence of trees that nearly matches the performance of a significantly more complex ensemble\. Because MDTs rely on only a few sparse trees, we can afford to optimize each component tree more carefully than in standard greedy tree induction while still requiring the overall procedure to scale\. Given this need for both higher\-quality component trees and scalability, we use a version of the polynomial\-time LicketySPLIT algorithm fromBabbaret al\.\[[3](https://arxiv.org/html/2606.30995#bib.bib37)\], which we modify to support sample weights and deferral; our theory provides guarantees achievable when each component tree is exactly optimal with respect to misclassification error, deferral rate, and tree complexity\. Many near\-optimal decision tree algorithms, including LicketySPLIT, operate on binarized features, which are often constructed using ThresholdGuessing\[[44](https://arxiv.org/html/2606.30995#bib.bib9)\]; we use the same binarization method\.

##### Compressing Tree Ensembles

Vidal and Schiffer \[[69](https://arxiv.org/html/2606.30995#bib.bib5)\]present an algorithm to find the sparsest single decision tree with identical 0\-1 predictive behaviour to a given tree\-based ensemble \(though not necessarily identical predicted probabilities\)\. They additionally provide practical relaxations to allow for faster computation \(removing the certificate that the tree is the sparsest equivalent form\) or sparser representations \(providing extra pruning in areas with no support in the training data\)\.Sagi and Rokach \[[59](https://arxiv.org/html/2606.30995#bib.bib10)\]translate an XGBoost tree ensemble\[[12](https://arxiv.org/html/2606.30995#bib.bib11)\]to a single tree, with some approximation loss\.McTavishet al\.\[[44](https://arxiv.org/html/2606.30995#bib.bib9)\]take a slightly different approach to learn a single tree when provided with a tree\-based ensemble, using the ensemble’s predictions to provide heuristic pruning of the search space for an otherwise globally optimal tree\. All three methods afford more interpretable single tree alternatives when provided with an ensemble model, though to guarantee matching performance with that ensemble, these approaches often find trees with many more leaves than is ideal for interpretability\.

In the hybrid component of our own algorithm, we incorporate information from a black box model in a fundamentally different way than the above approaches\. Our goal is not to match the black box model’s predictions exactly, nor to accelerate an optimal tree search; instead our goal is to use the black box to resolve subspaces of the data for which interpretable algorithms cannot find an accurate simple model; this allows us to find models that are transparent on much of the data, without sacrificing meaningful accuracy relative to the black box\. While we discuss several useful properties when the black box is a tree\-based ensemble, our approach inherits the more general\-purpose properties of hybrid models and can work with any black box model, since all we need for training is to retrain the model and obtain its prediction vector on the dataset\.

Once we have identified the set of points for which we defer to a black box, if our black box is a tree ensemble it is possible to apply any of these compression methods, focusing on the subset of data for which our model defers \(or even to apply approximate compression methods, such as the method proposed byDevoset al\.\[[18](https://arxiv.org/html/2606.30995#bib.bib6)\]\)\. This can further improve the interpretability of the tree, while simplifying the scope of the task to only those subspaces for which we know we need to use compression rather than learning a simple model\.

## 3Methodology

##### Notation\.

Let𝒳⊆ℝp\\mathcal\{X\}\\subseteq\\mathbb\{R\}^\{p\}denote an input space withppfeatures and let𝒴=\{0,1\}\\mathcal\{Y\}=\\\{0,1\\\}denote the label space\. Training data is denoted as𝒟=\{\(xi,yi\)\}i=1N⊆𝒳×𝒴\\mathcal\{D\}=\\\{\(x\_\{i\},y\_\{i\}\)\\\}\_\{i=1\}^\{N\}\\subseteq\\mathcal\{X\}\\times\\mathcal\{Y\}\. When this data is weighted, we denote the dataset as𝒟w\\mathcal\{D\}^\{w\}for weight vectorw∈ℝ≥0Nw\\in\\mathbb\{R\}\_\{\\geq 0\}^\{N\}\. We write𝟙​\{⋅\}\\mathds\{1\}\\\{\\cdot\\\}for the indicator function\. For a binary decision treeTT, let\|T\|\|T\|denote its number of leaves, and letT​\(x\)T\(x\)denote the label predicted byTTfor inputxx\.

A standard binary decision tree recursively partitions𝒳\\mathcal\{X\}by internal boolean split nodes and assigns a prediction at each leaf\. We generalize this object by allowing a leaf to output either a class label or a specialdeferaction, indicating that prediction should be deferred to a subsequent model\.

###### Definition 1\(Defer tree\)\.

A*defer tree*TTis a binary tree whose leaves are labeled by elements of𝒴∪\{defer\}\\mathcal\{Y\}\\cup\\\{\\mathrm\{defer\}\\\}\. For some fallback model B, the prediction of a defer tree is:

y^T,B​\(x\)=\{T​\(x\),if​T​\(x\)≠defer,B​\(x\),otherwise\.\\hat\{y\}\_\{T,B\}\(x\)=\\begin\{cases\}T\(x\),&\\text\{if \}T\(x\)\\neq\\mathrm\{defer\},\\\\\[4\.0pt\] B\(x\),&\\text\{otherwise\}\.\\end\{cases\}

For a fixed fallback modelBB, we can train a single defer treeTTby optimizing the objectiveℒT,B\\mathcal\{L\}\_\{T,B\}defined by

ℒT,B​\(𝒟w,τ,η\)=τ​\(\|T\|−1\)\+∑i=1Nwi​\(𝟙​\{y^T,B​\(xi\)≠yi\}\+η​𝟙​\{T​\(xi\)=defer\}\),\\mathcal\{L\}\_\{T,B\}\(\\mathcal\{D\}^\{w\},\\tau,\\eta\)=\\tau\\,\(\|T\|\-1\)\+\\sum\_\{i=1\}^\{N\}w\_\{i\}\\,\(\\mathds\{1\}\\\{\\hat\{y\}\_\{T,B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\mathds\{1\}\\\{\{\{T\}\(x\_\{i\}\)=\\mathrm\{defer\}\}\\\}\),where the hyperparameterτ\\taupenalizes the number of splits in the tree,η\\etapenalizes deferrals to a black box modelBB, andwwdenotes the sample weights for dataset𝒟\\mathcal\{D\}\. We optimize this objective using a modified version of LicketySPLIT\[[3](https://arxiv.org/html/2606.30995#bib.bib37)\]; details are given in Appendix[D\.2](https://arxiv.org/html/2606.30995#A4.SS2)\.

A single defer tree can improve accuracy over a fully interpretable model by deferring difficult samples to a black box\. However, those deferred samples are exactly where the original problem remains unresolved\. On that subset, we are still relying on a black box, and we would like to recover interpretability there as well\. It may seem natural to simply grow the tree further on that region, but if the original defer tree is already optimal, this is no longer possible\. An optimal defer tree comes with a certificate that rules out further improvement: any attempt to replace a deferral with an interpretable prediction must increase the objective\. In particular, matching the black box’s accuracy on the deferred subproblems would require a complexity increase whose leaf penalty outweighs the savings from eliminating deferral \(formalized in Proposition[2](https://arxiv.org/html/2606.30995#Thmproposition2)in the appendix\)\.

To overcome this limitation, we move beyond a single tree and introduce a sequential model that allows further improvement on the deferred region of a single defer tree\.

###### Definition 2\(Multistage defer tree\)\.

A*multistage defer tree*\(MDT\) of lengthKKis an ordered sequence

T1:k=\(T1,…,TK\),T\_\{1:k\}=\(T\_\{1\},\\dots,T\_\{K\}\),where eachTi:𝒳→𝒴∪\{defer\}T\_\{i\}:\\mathcal\{X\}\\to\\mathcal\{Y\}\\cup\\\{\\mathrm\{defer\}\\\}fori=1,…,Ki=1,\\dots,Kis a defer tree\. For some fallback modelB:𝒳→𝒴B:\\mathcal\{X\}\\to\\mathcal\{Y\}, the prediction of the MDT is

y^T1:k;B​\(x\)=\{T1​\(x\),if​T1​\(x\)≠defer,y^T2:k,B​\(x\),otherwise\.\\hat\{y\}\_\{T\_\{1:k\};B\}\(x\)=\\begin\{cases\}T\_\{1\}\(x\),&\\text\{if \}T\_\{1\}\(x\)\\neq\\mathrm\{defer\},\\\\\[4\.0pt\] \\hat\{y\}\_\{T\_\{2:k\},B\}\(x\),&\\text\{otherwise\}\.\\end\{cases\}

An MDT routes each input through a sequence of defer trees, where each stage either predicts immediately or defers to the next stage\. It also affords interpretability benefits relative to other tree\-based ensembles\. As discussed in[Theorem 1](https://arxiv.org/html/2606.30995#Thmtheorem1)below, our multistage defer trees can be represented compactly as a rule list\. This is significantly smaller than the rule list representations of other ensembles, such as random forests or boosted trees, where even the number of literals in a single antecedent can grow with the sum of depths across all trees \(see[3](https://arxiv.org/html/2606.30995#Thmproposition3)in the appendix\)\.

###### Theorem 1\(Rule\-list representation of MDTs\)\.

An MDT withKKstages admits a rule\-list representation, in which each non\-deferral leaf in any stage contributes exactly one antecedent\. Consequently, if stagejjhasnjn\_\{j\}non\-deferral leaves, the total number of antecedents is∑j=1Knj\\sum\_\{j=1\}^\{K\}n\_\{j\}\.

Because of Theorem[1](https://arxiv.org/html/2606.30995#Thmtheorem1), we can define a simple objective for MDTs that corresponds to an upper bound on the rule list deferral objective inFerryet al\.\[[23](https://arxiv.org/html/2606.30995#bib.bib4)\]applied to the rule list form of the MDT \(we discuss our relation to existing objectives in Appendix[E](https://arxiv.org/html/2606.30995#A5)\)\.

For a given MDT\(T1,…,Tk\)\(T\_\{1\},\\ldots,T\_\{k\}\)and fallback modelBB, let its objectiveℒT1:k,B\\mathcal\{L\}\_\{T\_\{1:k\},B\}be:

ℒT1:k,B​\(𝒟w,τ,η\)=τ​∑j=1k\(\|Tj\|−1\)\+∑i=1Nwi​\(𝟙​\{y^T1:k,B​\(xi\)≠yi\}\+η​𝟙​\{T1:k​\(xi\)=defer\}\),\\mathcal\{L\}\_\{T\_\{1:k\},B\}\(\\mathcal\{D\}^\{w\},\\tau,\\eta\)=\\tau\\sum\_\{j=1\}^\{k\}\\bigl\(\|T\_\{j\}\|\-1\\bigr\)\+\\sum\_\{i=1\}^\{N\}w\_\{i\}\\,\(\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{1:k,B\}\(x\_\{i\}\)\\neq y\_\{i\}\}\\\}\+\\eta\\mathds\{1\}\\\{\{\{T\_\{1:k\}\}\(x\_\{i\}\)=\\mathrm\{defer\}\}\\\}\),
whereT1:k​\(x\)\{T\}\_\{1:k\}\(x\)denotes the output of the sequence of trees\(T1,…,Tk\)\(T\_\{1\},\\dots,T\_\{k\}\)\.

### 3\.1Training Multistage Defer Trees

When optimizing our MDT objectiveℒT1:k,B\\mathcal\{L\}\_\{T\_\{1:k\},B\}, we can expand the structure from the top down, training a defer tree at each stage on the remaining deferred region with our single defer tree objectiveℒT,B\\mathcal\{L\}\_\{T,B\}\. When we do so, Proposition[1](https://arxiv.org/html/2606.30995#Thmproposition1)shows that we monotonically decrease the objective defined above\.

###### Proposition 1\(Top\-down improvement\)\.

Consider an iterative procedure where we train a single defer tree on the samples that have not been in previous stages\. Define weights for stagejjthat zero out all samples that are not deferred by that stage:

wi\(j\):=wi\(j−1\)​𝟙​\{Tj−1​\(xi\)=defer\},wi\(1\):=wi\.w^\{\(j\)\}\_\{i\}:=w\_\{i\}^\{\(j\-1\)\}\\mathds\{1\}\\\{T\_\{j\-1\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\},\\quad w^\{\(1\)\}\_\{i\}:=w\_\{i\}\.
LetΔj\\Delta\_\{j\}be how much we improve on the objective of the deferred dataset𝒟w\(j\)\\mathcal\{D\}^\{w^\{\(j\)\}\}with defer treeTjT\_\{j\}, relative to deferring to a black boxBB:

Δj=Ldefer,B​\(𝒟w\(j\),τ,η\)−LTj,B​\(𝒟w\(j\),τ,η\)\.\\Delta\_\{j\}=L\_\{\\mathrm\{defer\},B\}\(\\mathcal\{D\}^\{w^\{\(j\)\}\},\\tau,\\eta\)\-L\_\{T\_\{j\},B\}\(\\mathcal\{D\}^\{w^\{\(j\)\}\},\\tau,\\eta\)\.
With this iterative procedure, the total improvement of the model relative to the black box is the sum of improvements of each single defer tree relative to deferral\.

ℒT1:k,B​\(𝒟w,τ,η\)=Ldefer,B​\(𝒟w,τ,η\)−∑j=1kΔj\.\\mathcal\{L\}\_\{T\_\{1:k\},B\}\(\\mathcal\{D\}^\{w\},\\tau,\\eta\)=L\_\{\\mathrm\{defer\},B\}\(\\mathcal\{D\}^\{w\},\\tau,\\eta\)\-\\sum\_\{j=1\}^\{k\}\\Delta\_\{j\}\.

While Proposition[1](https://arxiv.org/html/2606.30995#Thmproposition1)motivates our approach, there is a risk of a hybrid model deferring to the black box primarily in regions where the black box has overfit\. Consider subregions of the space where a black box’s performance is especially high due to sample bias\. These are also regions where it will be difficult for a simple model to match that performance, so a hybrid model is likely to defer in this case, leading to high test error in deferral cases\.

Even for a single defer tree, the black\-box component generalization can be a substantial issue\. Table[2](https://arxiv.org/html/2606.30995#A7.T2)in the appendix shows that the test error of a black box in the deferred region can be more than an order of magnitude higher than the test error of the simple model in the non\-deferred region\. To address this, we also need to leverage the rest of the data to improve generalization\.

We can continue to refine an MDT without inducing overfitting by reweighting the training distribution: non\-deferred points are downweighted based on their distance to the deferred region, rather than assigning them no weight\. At a high level, we will accomplish this via an alternating optimization procedure that iteratively 1\) trains both a black box and a defer tree on a dataset and 2\) trains a black box and a defer tree on a weighted dataset that places more importance on deferred points\.

Let𝒟k−1⊆𝒳\\mathcal\{D\}\_\{k\-1\}\\subseteq\\mathcal\{X\}denote the set of deferred points after stagek−1k\-1\. For any samplexi∉𝒟k−1x\_\{i\}\\not\\in\\mathcal\{D\}\_\{k\-1\}, letdefer\_distT1:k−1​\(xi\)\\textrm\{defer\\\_dist\}\_\{T\_\{1:k\-1\}\}\(x\_\{i\}\)denote theℓ1\\ell\_\{1\}\-norm \(taken in quantile space, more information in Appendix[C](https://arxiv.org/html/2606.30995#A3)\) of the minimal change toxix\_\{i\}such that it would be deferred byT1:k\-1T\_\{\\textrm\{1:k\-1\}\}\. Using this distance, we define training weightswiw\_\{i\}for the next iteration \(on the first iteration, all weights are 1\)\.

wi=\{1,if​xi∈𝒟k−1\(1−μ\)​\(1\+defer\_distT1:k\-1​\(xi\)\)−γ,if​xi∉𝒟k−1\.w\_\{i\}\\;=\\;\\begin\{cases\}1,&\\text\{if \}x\_\{i\}\\in\\mathcal\{D\}\_\{k\-1\}\\\\\[6\.0pt\] \(1\-\\mu\)\\,\(1\+\\textrm\{defer\\\_dist\}\_\{T\_\{\\textrm\{\{1:k\-1\}\}\}\}\(x\_\{i\}\)\)^\{\-\\gamma\},&\\text\{if \}x\_\{i\}\\notin\\mathcal\{D\}\_\{k\-1\}\.\\end\{cases\}Here,μ∈\[0,1\]\\mu\\in\[0,1\]controls how much we uniformly scale down the weights of the non\-deferred region, whileγ≥0\\gamma\\geq 0controls how strongly the weights decay with distance from the deferred region\. Whenγ=0\\gamma=0, this reduces to assigning weight1−μ1\-\\muto each non\-deferred point\.μ=1\\mu=1places weight solely on the deferred points\.

Algorithm 1Top\-down MDT training0:Data

\(X,Xbinarized,y\)\(X,X\_\{\\textrm\{binarized\}\},y\)with

X∈ℝN×pX\\in\\mathbb\{R\}^\{N\\times p\}and

Xbinarized∈\{0,1\}N×qX\_\{\\textrm\{binarized\}\}\\in\\\{0,1\\\}^\{N\\times q\}, depth

dd,

τ\\tau,

η\\eta,

μ≥0\\mu\\geq 0, boolean flag rescale\_tau, maximum number of tree stages

KmaxK\_\{\\max\},

γ≥0\\gamma\\geq 0
1:

𝒯interp←\[\]\\mathcal\{T\}\_\{\\textrm\{interp\}\}\\leftarrow\[\\ \]
2:

D←\{1,…,N\}D\\leftarrow\\\{1,\\dots,N\\\}
3:terminated\_early

←\\leftarrowfalse

4:

w←𝟏w\\leftarrow\\mathbf\{1\}
5:for

k=1,…,Kmaxk=1,\\dots,K\_\{\\max\}do

6:\{Iteratively construct the MDT, one stage at a time\}

7:

B←FitFallbackModel​\(X,y,w\)B\\leftarrow\\textsc\{FitFallbackModel\}\(X,y,w\)\{Train fallback model for current stage\}

8:

Tk←FitDeferTree​\(Xbinarized,y,B​\(X\),w,τ,η,d\)T\_\{k\}\\leftarrow\\textsc\{FitDeferTree\}\(X\_\{\\textrm\{binarized\}\},y,B\(X\),w,\\tau,\\eta,d\)
9:\{Train defer tree for current stage; method described in Algorithms[17](https://arxiv.org/html/2606.30995#alg17)and[18](https://arxiv.org/html/2606.30995#alg18)\}

10:

Dnew←\{i∈D:Tk​\(xi\)=defer\}D\_\{\\mathrm\{new\}\}\\leftarrow\\\{i\\in D:T\_\{k\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}
11:if

Dnew=DD\_\{\\mathrm\{new\}\}=Dor

Dnew=∅D\_\{\\mathrm\{new\}\}=\\varnothingthen

12:terminated\_early

←\\leftarrowtrue

13:break\{Stop if deferred set does not shrink\}

14:endif

15:

D←DnewD\\leftarrow D\_\{\\mathrm\{new\}\}
16:

𝒯interp←𝒯interp\+\[Tk\]\\mathcal\{T\}\_\{\\textrm\{interp\}\}\\leftarrow\\mathcal\{T\}\_\{\\textrm\{interp\}\}\+\[T\_\{k\}\]
17:

Xbinarized←Filtersplits​\(Xbinarized,𝒯interp\)X\_\{\\textrm\{binarized\}\}\\leftarrow\\textsc\{Filtersplits\}\(X\_\{\\textrm\{binarized\}\},\\mathcal\{T\}\_\{\\textrm\{interp\}\}\)
18:\{Remove binary splits that do not differentiate deferred regions, discussed in[subsection 3\.2](https://arxiv.org/html/2606.30995#S3.SS2)\}

19:

w←GetWeights​\(X,D,γ,μ,𝒯interp\)w\\leftarrow\\textsc\{GetWeights\}\(X,D,\\gamma,\\mu,\\mathcal\{T\}\_\{\\textrm\{interp\}\}\)
20:\{Distance\-based weights, down\-weighting non\-deferred points, discussed in[subsection 3\.2](https://arxiv.org/html/2606.30995#S3.SS2)\}

21:

τ←τ⋅∑i=1NwiN\\tau\\leftarrow\\tau\\cdot\\dfrac\{\\sum\_\{i=1\}^\{N\}w\_\{i\}\}\{N\}ifrescale\_tauelse

τ\\tau
22:endfor

23:ifnotterminated\_earlyand

D≠∅D\\neq\\varnothingthen

24:\{Final reweighting and retraining of fallback\}

25:

w←GetWeights​\(X,D,γ,μ\)w\\leftarrow\\textsc\{GetWeights\}\(X,D,\\gamma,\\mu\)
26:

B←FitFallbackModel​\(X,y,w\)B\\leftarrow\\textsc\{FitFallbackModel\}\(X,y,w\)
27:endif

28:return

𝒯interp\+\[B\]\\mathcal\{T\_\{\\textrm\{interp\}\}\}\+\[B\]

Algorithm[1](https://arxiv.org/html/2606.30995#alg1)describes our approach to allow the fallback model and the next defer tree to iteratively update together\. At each stage, we fit a fallback modelBBand a defer tree on the full dataset using the current weights \(lines 7\-9\), where the weights are all 1 for the first pass \(line 4\)\. We then update core information for future iterations\. We then update the active deferred setDDto the subset of points that are still deferred \(lines 10\-15\)\. If we decreased the size of the deferred set, we then add the tree to the sequence \(line 16\) and move to the next stage\. To prepare for the next stage, we first filter out any splits that are provably irrelevant to our remaining deferral region \(line 17\)\. We then compute weights based on distances to the feasible deferred region \(line 19\), and optionally update the leaf penaltyτ\\tau\(line 21\)\.

The procedure terminates whenDDbecomes empty or stops decreasing in size \(lines 10\-15\)\. If the loop reachesKmaxK\_\{\\max\}without early termination andDDis still nonempty \(an iteration limit\), we perform one final update of the fallback model using the latest weights \(lines 23\-27\), since the previous fallback model was trained on the previous set of weights\. In Appendix[D](https://arxiv.org/html/2606.30995#A4), we also describe early stopping criteria based on model complexity \(e\.g\., per\-stage size, equivalent rule list size, or equivalent single\-tree size\), along with efficient online updates to enforce these constraints\.

For brevity, we defer additional theoretical results to Appendix[A](https://arxiv.org/html/2606.30995#A1)\. For instance, we show that the distance\-based weights arise as a Gibbs distribution minimizing an entropy\-regularized objective\.

### 3\.2Feasible Region Tracking

Algorithm[1](https://arxiv.org/html/2606.30995#alg1)specifies the high\-level training procedure, but efficiently implementing lines 10, 12, and 25 requires viewing the deferral region geometrically as a union of axis\-aligned hyperrectangles\.

LetΛkdefer\\Lambda\_\{k\}^\{\\text\{defer\}\}denote the set of defer leaves of treekk\. Each defer leafλ∈Λkdefer\\lambda\\in\\Lambda\_\{k\}^\{\\text\{defer\}\}corresponds to an axis\-aligned hyperrectangle in feature space \(a defer subregion\), denotedR​\(λ\)R\(\\lambda\)\. The total deferral region after stagekkcan be written as a set of defer subregions in the following way:

𝒮k:=\(\{⋂t=1kR\(λt\)\|\(λ1,…,λk\)∈Λ1defer×⋯×Λkdefer\}\)∖\{∅\}\.\\mathcal\{S\}\_\{k\}:=\\left\(\\left\\\{\\bigcap\_\{t=1\}^\{k\}R\(\\lambda\_\{t\}\)\\;\\middle\|\\;\(\\lambda\_\{1\},\\dots,\\lambda\_\{k\}\)\\in\\Lambda\_\{1\}^\{\\mathrm\{defer\}\}\\times\\cdots\\times\\Lambda\_\{k\}^\{\\mathrm\{defer\}\}\\right\\\}\\right\)\\setminus\\\{\\emptyset\\\}\.
We refer to each element⋂t=1kR​\(λt\)\\bigcap\_\{t=1\}^\{k\}R\(\\lambda\_\{t\}\)in the set𝒮k\\mathcal\{S\}\_\{k\}as a*defer subregion*\. Each such subregion remains an axis\-aligned hyperrectangle, since intersections of axis\-aligned hyperrectangles preserve this structure\. Many such subregions may be empty \(infeasible\), e\.g\.,a​g​e≤20age\\leq 20in one stage anda​g​e\>25age\>25in another; we detect and discard these cases\.

Because our iterative procedure refines only the set of subregions that defer, we can update this set iteratively\. Suppose𝒮k−1\\mathcal\{S\}\_\{k\-1\}is the set of defer subregions forT1​⋯​Tk−1T\_\{1\}\\cdots T\_\{k\-1\}; then we can update it to be the set of defer subregions forT1​⋯​TkT\_\{1\}\\cdots T\_\{k\}via pairwise intersections between the existing defer subregions and the defer subregions ofTkT\_\{k\}:

Sk←\{s∩R​\(λk\)\|s∈Sk−1,λk∈Λkdefer\}∖\{∅\}\.S\_\{k\}\\leftarrow\\left\\\{\\,s\\cap R\(\\lambda\_\{k\}\)\\;\\middle\|\\;s\\in S\_\{k\-1\},\\ \\lambda\_\{k\}\\in\\Lambda\_\{k\}^\{\\mathrm\{defer\}\}\\right\\\}\\setminus\\\{\\emptyset\\\}\.
Once we have𝒮k\\mathcal\{S\}\_\{k\}, we can iterate over its elements to compute the distance from each point to each deferred subregion, and use the minimum such distance to measure how far the point is from being deferred\. Likewise, for each columnjjofXbinarizedX\_\{\\text\{binarized\}\}, we can discard it if its value is fixed across all feasible subregions; that is, the corresponding binarized predicate has the same truth value for every possible point in every subregion in𝒮k\\mathcal\{S\}\_\{k\}\. Concretely, we map columnjjto its corresponding split\(f≤ν\)\(f\\leq\\nu\)via its metadata, and discard it if either∀s∈𝒮k,ImpliesTrue​\(s,f,ν\)\\forall s\\in\\mathcal\{S\}\_\{k\},\\ \\textsc\{ImpliesTrue\}\(s,f,\\nu\)or∀s∈𝒮k,ImpliesFalse​\(s,f,ν\)\\forall s\\in\\mathcal\{S\}\_\{k\},\\ \\textsc\{ImpliesFalse\}\(s,f,\\nu\)\(methods provided in[B](https://arxiv.org/html/2606.30995#A2)\)\. Appendix[D](https://arxiv.org/html/2606.30995#A4)presents a version of Algorithm[1](https://arxiv.org/html/2606.30995#alg1)with these changes to improve efficiency\.

Feasible region tracking can also be used to compress the resulting MDT\. In Appendix[B](https://arxiv.org/html/2606.30995#A2), we provide an algorithm to compress the MDT into a single defer tree\. We recursively expand each defer leaf by substituting the next\-stage tree, while tracking the corresponding subregion of the feature space that we are in\. If a split is guaranteed to evaluate the same way throughout this region \(i\.e\., always True or always False\), we can replace the node with the corresponding child\. We also provide algorithms to further simplify the MDT when redundant splits remain; this has the effect of shortening the rules used in a MDT’s rule\-list representation\. We can apply either of these techniques to each tree in a tree ensemble, using the set of subregions in which that tree may be evaluated\.

## 4Experiments

We compare our MDTs and the defer tree method to state\-of\-the\-art tree ensembles \(XGBoost\[[12](https://arxiv.org/html/2606.30995#bib.bib11)\], Random Forest\[[11](https://arxiv.org/html/2606.30995#bib.bib18)\]\), sparse additive tree models \(FIGS\[[66](https://arxiv.org/html/2606.30995#bib.bib51)\]\), and existing hybrid interpretable baselines \(HyRS\[[71](https://arxiv.org/html/2606.30995#bib.bib1),[70](https://arxiv.org/html/2606.30995#bib.bib2)\], Pre\- and Post\- CORELS\[[23](https://arxiv.org/html/2606.30995#bib.bib4)\]\) on a wide range of datasets\. We also implemented the hybrid interpretable model fromFrostet al\.\[[26](https://arxiv.org/html/2606.30995#bib.bib44)\], and refer to the method as FLMM\. Lastly, we add a logistic regression baseline, which defers when the estimated probability is close to 0\.5\. Our key questions are as follows\. \(1\) Can MDTs provide black\-box comparable accuracy for a small deferral rate? \(2\) How do MDT deferral rates and accuracy compare to existing deferral methods? \(3\) How complex are state\-of\-the\-art MDTs?

Table 1:Test accuracy \(mean±\\pmstandard error across five train/test splits\) across representative datasets\. Bold indicates the best mean accuracy in each row\. Underlining indicates methods whose mean accuracy is within1\.961\.96standard errors of the best method, corresponding to overlap with the best method’s 95% confidence interval\.To answer these questions, we need to determine the best configurations for hybrid interpretable models subject to a particular constraint on test deferral rate\. To do so, we adopt a semi\-supervised approach: for each train/test split and maximum deferral ratecc, we choose the hyperparameter that maximizes the average validation accuracy, while deferring on at mostccproportion of the test set\. Note that deferral is independent of labels, so this is fully semi\-supervised\.

In Appendix[G](https://arxiv.org/html/2606.30995#A7)\(Tables[6](https://arxiv.org/html/2606.30995#A7.T6)and[3](https://arxiv.org/html/2606.30995#A7.T3)\), we show that the gap between train and test deferral rates is always small, suggesting that a fully supervised selection procedure would yield nearly identical results\. Indeed, we show this is the case in the appendix \([Figure 5](https://arxiv.org/html/2606.30995#A7.F5)\)\. Additional information on our experiment setup is in Appendix[F](https://arxiv.org/html/2606.30995#A6); all results are averaged across five train/test splits\.

To answer question \(1\), Table[1](https://arxiv.org/html/2606.30995#S4.T1)reports test accuracy across datasets\. MDT\+XGB \(with at most 25% deferral\) is consistently competitive even with the strongest black box baselines: it is frequently closer to state\-of\-the\-art performance than random forests and almost always within the 95% confidence interval of the best method\. Furthermore, it outperforms the sparse ensemble model FIGS on nearly all datasets\. MDT also outperforms a single tree, non\-deferral ablation, demonstrating that the multistage training and deferral is core to MDT’s success\.

![Refer to caption](https://arxiv.org/html/2606.30995v1/x2.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x3.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x4.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x5.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x6.png)

Figure 2:Test accuracy \(mean±\\pmstandard deviation\) as a function of deferral rate across datasets\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x7.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x8.png)

Figure 3:CDF of deferral thresholds required to have accuracy within2\.0%2\.0\\%of XGBoost\. Each curve shows the fraction of datasets for which a method achieves this accuracy within a given deferral rate\.To answer question \(2\), we compare MDTs to other hybrid\-interpretable models in Figures[2](https://arxiv.org/html/2606.30995#S4.F2)and[3](https://arxiv.org/html/2606.30995#S4.F3)\. In Figure[2](https://arxiv.org/html/2606.30995#S4.F2), we compare hybrid\-interpretable models on datasets where the accuracy\-interpretability tradeoff is high \(a single tree is\>2%\>2\\%less accurate than a black box\)\.

On all four datasets, MDT\+XGB consistently outperforms all other baselines\. On California, MDT\+XGB matches the mean accuracy of XGBoost at 25% deferral, a level that no competing method achieves within the same deferral budget\. Figure[3](https://arxiv.org/html/2606.30995#S4.F3)shows the deferral rate required to achieve accuracy within2\.0%2\.0\\%of XGBoost across all 24 datasets \(the full list of datasets is in Appendix[F](https://arxiv.org/html/2606.30995#A6)\)\. At around40%40\\%deferral, our MDT\+XGB method can come within this amount of XGBoost for all datasets\. No existing method can match this without deferring the majority of the time\.

![Refer to caption](https://arxiv.org/html/2606.30995v1/new_main_figs/cdf_vs_xgb_mean_splits_eps_0.02.png)\(a\)Fraction of datasets within2\.0%2\.0\\%of XGBoost as a function of the average number of split decisions encountered by a test sample in the interpretable portion of MDT\+XGB\.
\(b\)Compression ratios \(mean across splits\) for splits to evaluate a deferred test sample and leaves of the final MDT XGBoost relative to the original XGBoost fallback\. A 95% confidence interval on the difference \(MDT−XGB\\text\{MDT\}\-\\text\{XGB\}\) in test deferred region accuracy shows they are indistinguishable\. Full table in Table[4](https://arxiv.org/html/2606.30995#A7.T4)\(Appendix\)\.

Figure 4:To answer question \(3\), Figure[4\(a\)](https://arxiv.org/html/2606.30995#S4.F4.sf1)shows the fraction of datasets that achieve accuracy within2\.0%2\.0\\%of XGBoost as a function of the average number of split decisions encountered by a test sample while passing through the interpretable portion of the MDT\. This average path\-length constraint is enforced analogously to the deferral constraint\. At 50% deferral, no dataset requires more than an average of 7\.5 split decisions per sample to reach near\-XGBoost performance, and the vast majority reach this threshold with at most an average of 5\.5 split decisions per sample\. Since MDTs only need to use a black\-box component for a small proportion of samples, the black\-box representations they learn are naturally more compressed\. Figure[4\(b\)](https://arxiv.org/html/2606.30995#S4.F4.sf2)compares the distribution of the number of splits needed to evaluate samples that are deferred, either by \(a\) using the final fallback XGBoost model or \(b\) using the best XGBoost model for the whole dataset\. Both \(a\) and \(b\) are trained with the same hyperparameter configuration, but approach \(a\) is trained using a weighting that emphasizes deferred points\. The number of splits required to classify a sample is greatly reduced\.

## 5Conclusion

We introduce Multistage Defer Trees, a model class that adaptively allocates complexity by routing inputs through a sequence of sparse decision trees before deferring to a black\-box model\. Our training procedure progressively refines the defer region, combining distance\-based weighting, which allows the model to borrow strength from nearby points, with compression techniques that track and simplify defer subregions\. MDTs demonstrate that accuracy and interpretability need not be traded off globally, substantially improving the accuracy\-deferral frontier\. Future work could explore using multiple fallback models, possibly from different model classes\.

## References

- \[1\]G\. Aglin, S\. Nijssen, and P\. Schaus\(2020\)Learning optimal decision trees using caching branch\-and\-bound search\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.34,pp\. 3146–3153\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[2\]D\. Aha\(1991\)Tic\-Tac\-Toe Endgame\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5688JCited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px23.1.1)\.
- \[3\]V\. Babbar, H\. McTavish, C\. Rudin, and M\. Seltzer\(2025\)Near\-optimal decision trees in a SPLIT second\.InInternational Conference on Machine Learning,Cited by:[§D\.2](https://arxiv.org/html/2606.30995#A4.SS2.p1.1),[Appendix E](https://arxiv.org/html/2606.30995#A5.p3.3),[Appendix E](https://arxiv.org/html/2606.30995#A5.p8.4),[§F\.3\.4](https://arxiv.org/html/2606.30995#A6.SS3.SSS4.Px1.p1.1),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p2.1),[§3](https://arxiv.org/html/2606.30995#S3.SS0.SSS0.Px1.p3.8)\.
- \[4\]M\. Bao, A\. Zhou, A\. S\. Zottola, B\. Brubach, S\. Desmarais, S\. A\. Horowitz, K\. Lum, and S\. Venkatasubramanian\(2021\)It’s compaslicated: the messy relationship between rai datasets and algorithmic fairness benchmarks\.InProceedings of the Thirty\-Fifth Conference on Neural Information Processing Systems \(NeurIPS\),Note:Datasets and Benchmarks Track \(Round 1\)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px7.1.1)\.
- \[5\]B\. Becker and R\. Kohavi\(1996\)Adult\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5XW20Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px2.1.1)\.
- \[6\]D\. Bertsimas and J\. Dunn\(2017\)Optimal classification trees\.Machine Learning106,pp\. 1039–1082\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[7\]G\. Blanc, J\. Lange, C\. Pabbaraju, C\. Sullivan, L\. Tan, and M\. Tiwari\(2024\)Harnessing the power of choices in decision tree learning\.Advances in Neural Information Processing Systems36\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[8\]R\. Bock\(2004\)MAGIC Gamma Telescope\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C52C8BCited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px15.1.1)\.
- \[9\]Z\. Boner, H\. Chen, L\. Semenova, R\. Parr, and C\. Rudin\(2024\)Using noise to infer aspects of simplicity without learning\.InAdvances In Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2606.30995#S1.p1.1)\.
- \[10\]L\. Breiman, J\. H\. Friedman, R\. A\. Olshen, and C\. J\. Stone\(1984\)Classification and regression trees\. wadsworth & brooks\.Cole Advanced books & software Pacific Grove, CA\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[11\]L\. Breiman\(2001\)Random forests\.Machine Learning45,pp\. 5–32\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1),[§4](https://arxiv.org/html/2606.30995#S4.p1.1)\.
- \[12\]T\. Chen and C\. Guestrin\(2016\)Xgboost: A Scalable Tree Boosting System\.InProceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 785–794\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px3.p1.1),[§4](https://arxiv.org/html/2606.30995#S4.p1.1)\.
- \[13\]C\. Chow\(2003\)On optimum recognition error and reject tradeoff\.IEEE Transactions on information theory16\(1\),pp\. 41–46\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1)\.
- \[14\]P\. Cortez and A\. M\. G\. Silva\(2008\)Using data mining to predict secondary school student performance\.External Links:[Link](https://api.semanticscholar.org/CorpusID:16621299)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px22.1.1)\.
- \[15\]P\. Cortez\(2008\)Student Performance\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5TG7TCited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px22.1.1)\.
- \[16\]E\. Demirović, E\. Hebrard, and L\. Jean\(2023\)Blossom: an anytime algorithm for computing optimal decision trees\.InInternational Conference on Machine Learning,pp\. 7533–7562\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[17\]E\. Demirović, A\. Lukina, E\. Hebrard, J\. Chan, J\. Bailey, C\. Leckie, K\. Ramamohanarao, and P\. J\. Stuckey\(2022\)Murtree: optimal decision trees via dynamic programming and search\.Journal of Machine Learning Research23\(26\),pp\. 1–47\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[18\]L\. Devos, T\. Martens, D\. C\. Oruc, W\. Meert, H\. Blockeel, and J\. Davis\(2025\)Compressing tree ensembles through level\-wise optimization and pruning\.InForty\-second International Conference on Machine Learning,Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px3.p3.1)\.
- \[19\]R\. El\-Yanivet al\.\(2010\)On the foundations of noise\-free selective classification\.\.Journal of Machine Learning Research11\(5\)\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1)\.
- \[20\]N\. Erickson, L\. Purucker, A\. Tschalzev, D\. Holzmüller, P\. M\. Desai, D\. Salinas, and F\. Hutter\(2025\)TabArena: a living benchmark for machine learning on tabular data\.External Links:2506\.16791,[Link](https://arxiv.org/abs/2506.16791)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px6.1.1)\.
- \[21\]H\. Fanaee\-T and J\. Gama\(2013\)Event labeling combining ensemble detectors and background knowledge\.Progress in Artificial Intelligence2,pp\. 113 – 127\.External Links:[Link](https://api.semanticscholar.org/CorpusID:256282956)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px4.1.1)\.
- \[22\]H\. Fanaee\-T\(2013\)Bike Sharing\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5W894Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px4.1.1)\.
- \[23\]J\. Ferry, G\. Laberge, and U\. Aïvodji\(2023\)Learning hybrid interpretable models: theory, taxonomy, and methods\.arXiv preprint arXiv:2303\.04437\.Cited by:[Appendix E](https://arxiv.org/html/2606.30995#A5.p6.2),[§1](https://arxiv.org/html/2606.30995#S1.p2.1),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1),[§3](https://arxiv.org/html/2606.30995#S3.SS0.SSS0.Px1.p7.1),[§4](https://arxiv.org/html/2606.30995#S4.p1.1)\.
- \[24\]FICO\(2018\)Home equity line of credit \(heloc\) dataset\.FICO\.Note:FICO Explainable Machine Learning ChallengeExternal Links:[Link](https://community.fico.com/s/explainable-machine-learning-challenge)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px12.1.1)\.
- \[25\]Y\. Freund, R\. E\. Schapire, Y\. Singer, and M\. K\. Warmuth\(1997\)Using and combining predictors that specialize\.InProceedings of the twenty\-ninth annual ACM symposium on Theory of computing,pp\. 334–343\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1)\.
- \[26\]N\. Frost, Z\. Lipton, Y\. Mansour, and M\. Moshkovitz\(2024\)Partially interpretable models with guarantees on coverage and accuracy\.InInternational conference on algorithmic learning theory,pp\. 590–613\.Cited by:[§F\.3\.5](https://arxiv.org/html/2606.30995#A6.SS3.SSS5.Px2.p2.2),[§1](https://arxiv.org/html/2606.30995#S1.p2.1),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2606.30995#S4.p1.1)\.
- \[27\]I\. Guyon, L\. Sun\-Hosoya, M\. Boullé, H\. J\. Escalante, S\. Escalera, Z\. Liu, D\. Jajetic, B\. Ray, M\. Saeed, M\. Sebag, A\. Statnikov, W\. Tu, and E\. Viegas\(2019\)Analysis of the automl challenge series 2015\-2018\.InAutoML,Springer series on Challenges in Machine Learning\.External Links:[Link](https://www.automl.org/wp-content/uploads/2018/09/chapter10-challenge.pdf)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px13.1.1)\.
- \[28\]Z\. Heile, H\. McTavish, V\. Babbar, M\. Seltzer, and C\. Rudin\(2026\)From rashomon theory to PRAXIS: efficient decision tree rashomon sets\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=Sgwd0l1u2V)Cited by:[§D\.2](https://arxiv.org/html/2606.30995#A4.SS2.p1.1)\.
- \[29\]M\. Hopkins, E\. Reeber, G\. Forman, and J\. Suermondt\(1999\)Spambase\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C53G6XCited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px21.1.1)\.
- \[30\]X\. Hu, C\. Rudin, and M\. Seltzer\(2019\)Optimal sparse decision trees\.InAdvances in Neural Information Processing Systems,Vol\.32,pp\. 7265–7273\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[31\]\(2017\)In\-Vehicle Coupon Recommendation\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5GS4PCited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px8.1.1)\.
- \[32\]H\. Kiossou, P\. Schaus, S\. Nijssen, and G\. Aglin\(2024\)Efficient lookahead decision trees\.InInternational Symposium on Intelligent Data Analysis,pp\. 133–144\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[33\]H\. Kiossou, P\. Schaus, S\. Nijssen, and V\. R\. Houndji\(2022\)Time constrained dl8\.5 using limited discrepancy search\.InJoint European Conference on Machine Learning and Knowledge Discovery in Databases,pp\. 443–459\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[34\]H\. S\. Kiossou, S\. Nijssen, and P\. Schaus\(2025\)A generic complete anytime beam search for optimal decision tree\.arXiv preprint arXiv:2508\.06064\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[35\]Y\. Li, S\. Qi, L\. Cui, C\. Xing, L\. Zhang, and X\. Wang\(2026\)Interpret when possible: a tree\-based hybrid framework for interpretable classification\.Big Data Mining and Analytics9\(1\),pp\. 263–283\.External Links:[Link](https://www.sciopen.com/article/10.26599/BDMA.2025.9020055),[Document](https://dx.doi.org/10.26599/BDMA.2025.9020055)Cited by:[§1](https://arxiv.org/html/2606.30995#S1.p2.1),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1)\.
- \[36\]J\. Lin, C\. Zhong, D\. Hu, C\. Rudin, and M\. Seltzer\(2020\)Generalized and scalable optimal sparse decision trees\.InInternational Conference on Machine Learning,pp\. 6150–6160\.Cited by:[Appendix E](https://arxiv.org/html/2606.30995#A5.p3.3),[Appendix E](https://arxiv.org/html/2606.30995#A5.p8.4),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[37\]Y\. Lou, R\. Caruana, J\. Gehrke, and G\. Hooker\(2013\)Accurate intelligible models with pairwise interactions\.Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining\.External Links:[Link](https://api.semanticscholar.org/CorpusID:11246170)Cited by:[Figure 15](https://arxiv.org/html/2606.30995#A7.F15),[Figure 15](https://arxiv.org/html/2606.30995#A7.F15.3.2),[§1](https://arxiv.org/html/2606.30995#S1.p4.1)\.
- \[38\]D\. Madras, T\. Pitassi, and R\. Zemel\(2018\)Predict responsibly: improving fairness and accuracy by learning to defer\.Advances in neural information processing systems31\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1)\.
- \[39\]P\. N\. Malani, J\. Kullgren, and E\. Solway\(2019\)National poll on healthy aging \(npha\), united states, april 2017\.Inter\-university Consortium for Political and Social Research\.Note:DistributorExternal Links:[Document](https://dx.doi.org/10.3886/ICPSR37305.v1),[Link](https://doi.org/10.3886/ICPSR37305.v1)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px3.1.1)\.
- \[40\]G\. A\. Marcoulides\(2005\)Discovering knowledge in data: an introduction to data mining\.Wiley\.Note:Churn datasetCited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px6.1.1)\.
- \[41\]A\. Mathur, M\. Podila, K\. Kulkarni, Q\. Niyaz, and A\. Y\. Javaid\(2021\)Poster: naticusdroid: a malware detection framework for android using native and custom\.External Links:[Link](https://api.semanticscholar.org/CorpusID:232063483)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px11.1.1)\.
- \[42\]A\. Mathur\(2021\)NATICUSdroid \(Android Permissions\)\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5FS64Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px11.1.1)\.
- \[43\]R\. Mazumder, X\. Meng, and H\. Wang\(2022\-17–23 Jul\)Quant\-BnB: a scalable branch\-and\-bound method for optimal decision trees with continuous features\.InInternational Conference on Machine Learning,Vol\.162,pp\. 15255–15277\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[44\]H\. McTavish, C\. Zhong, R\. Achermann, I\. Karimalis, J\. Chen, C\. Rudin, and M\. Seltzer\(2022\)Fast sparse decision tree optimization via reference ensembles\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.36,pp\. 9604–9613\.Cited by:[Appendix E](https://arxiv.org/html/2606.30995#A5.p3.3),[Appendix E](https://arxiv.org/html/2606.30995#A5.p8.4),[§F\.3\.4](https://arxiv.org/html/2606.30995#A6.SS3.SSS4.Px1.p2.4),[§F\.3\.5](https://arxiv.org/html/2606.30995#A6.SS3.SSS5.Px4.p3.2),[§F\.3\.5](https://arxiv.org/html/2606.30995#A6.SS3.SSS5.Px5.p2.2),[§F\.3\.5](https://arxiv.org/html/2606.30995#A6.SS3.SSS5.Px6.p1.7),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p2.1),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px3.p1.1)\.
- \[45\]R\. Mohammad and L\. McCluskey\(2012\)Phishing Websites\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C51W2XCited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px17.1.1)\.
- \[46\]R\. M\. A\. Mohammad, F\. A\. Thabtah, and L\. Mccluskey\(2012\)An assessment of features related to phishing websites using an automated technique\.2012 International Conference for Internet Technology and Secured Transactions,pp\. 492–497\.External Links:[Link](https://api.semanticscholar.org/CorpusID:5716727)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px17.1.1)\.
- \[47\]H\. Mozannar and D\. Sontag\(2020\)Consistent estimators for learning to defer to an expert\.InInternational conference on machine learning,pp\. 7076–7087\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1)\.
- \[48\]\(2017\)National Poll on Healthy Aging \(NPHA\)\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.3886/ICPSR37305\.v1Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px3.1.1)\.
- \[49\]OpenML\(2018\)Jasmine dataset\.OpenML\.Note:OpenML Dataset ID 41143; dataset from the ChaLearn Automatic Machine Learning \(AutoML\) ChallengeExternal Links:[Link](https://www.openml.org/d/41143)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px13.1.1)\.
- \[50\]OpenML\(2018\)Madeline dataset\.OpenML\.Note:OpenML Dataset ID 41144; dataset from the ChaLearn Automatic Machine Learning \(AutoML\) ChallengeExternal Links:[Link](https://www.openml.org/d/41144)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px14.1.1)\.
- \[51\]OpenML\(2019\)Diamonds dataset\.OpenML\.Note:OpenML Dataset ID 42225; dataset containing prices and attributes of nearly 54,000 diamondsExternal Links:[Link](https://www.openml.org/d/42225)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px10.1.1)\.
- \[52\]OpenML\(2022\)Abalone dataset\.OpenML\.Note:OpenML Dataset ID 44956; dataset for predicting abalone age from physical measurementsExternal Links:[Link](https://www.openml.org/d/44956)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px1.1.1)\.
- \[53\]OpenML\(2022\)California dataset\.OpenML\.Note:OpenML Dataset ID 44090; dataset used in the tabular data benchmark and derived from the California Housing datasetExternal Links:[Link](https://www.openml.org/d/44090)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px5.1.1)\.
- \[54\]OpenML\(2022\)Pol dataset\.OpenML\.Note:OpenML Dataset ID 44082; dataset used in the tabular data benchmark and derived from a binarized version of the original regression datasetExternal Links:[Link](https://www.openml.org/d/44082)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px18.1.1)\.
- \[55\]OpenML\(2022\)RL dataset\.OpenML\.Note:OpenML Dataset ID 43949; dataset used in the tabular data benchmark and derived from the ChaLearn AutoML ChallengeExternal Links:[Link](https://www.openml.org/d/43949)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px19.1.1)\.
- \[56\]OpenML\(2025\)Wine dataset\.OpenML\.Note:OpenML Dataset ID 47041External Links:[Link](https://www.openml.org/d/47041)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px24.1.1)\.
- \[57\]D\. Pan, T\. Wang, and S\. Hara\(2020\)Interpretable companions for black\-box models\.InInternational conference on artificial intelligence and statistics,pp\. 2444–2454\.Cited by:[§1](https://arxiv.org/html/2606.30995#S1.p2.1),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1)\.
- \[58\]J\. R\. Quinlan\(1986\)Induction of decision trees\.Machine learning1\(1\),pp\. 81–106\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[59\]O\. Sagi and L\. Rokach\(2021\)Approximating xgboost with an interpretable decision tree\.Information Sciences572,pp\. 522–542\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px3.p1.1)\.
- \[60\]C\. Sakar and Y\. Kastro\(2018\)Online Shoppers Purchasing Intention Dataset\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5F88QCited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px20.1.1)\.
- \[61\]C\. O\. Sakar, S\. O\. Polat, M\. Katircioglu, and Y\. Kastro\(2018\)Real\-time prediction of online shoppers’ purchasing intention using multilayer perceptron and lstm recurrent neural networks\.Neural Computing and Applications31,pp\. 6893 – 6908\.External Links:[Link](https://api.semanticscholar.org/CorpusID:13682776)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px20.1.1)\.
- \[62\]C\. M\. Santos\-Pereira and A\. M\. Pires\(2005\)On optimal reject rules and roc curves\.Pattern Recognition Letters26\(7\),pp\. 943–952\.External Links:ISSN 0167\-8655,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.patrec.2004.09.042),[Link](https://www.sciencedirect.com/science/article/pii/S0167865504002892)Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1)\.
- \[63\]R\. E\. Schapire and Y\. Singer\(1998\)Improved boosting algorithms using confidence\-rated predictions\.InProceedings of the Eleventh Annual Conference on Computational Learning Theory,COLT’ 98,New York, NY, USA,pp\. 80–91\.External Links:ISBN 1581130570,[Link](https://doi.org/10.1145/279943.279960),[Document](https://dx.doi.org/10.1145/279943.279960)Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1)\.
- \[64\]L\. Semenova, H\. Chen, R\. Parr, and C\. Rudin\(2023\)A path to simpler models starts with noise\.Advances in Neural Information Processing Systems36\.Cited by:[§1](https://arxiv.org/html/2606.30995#S1.p1.1)\.
- \[65\]L\. Semenova, C\. Rudin, and R\. Parr\(2022\)On the existence of simpler machine learning models\.In2022 ACM Conference on Fairness, Accountability, and Transparency,pp\. 1827–1858\.Cited by:[§1](https://arxiv.org/html/2606.30995#S1.p1.1)\.
- \[66\]Y\. S\. Tan, C\. Singh, K\. Nasseri, A\. Agarwal, J\. Duncan, O\. Ronen, M\. Epland, A\. Kornblith, and B\. Yu\(2025\)Fast interpretable greedy\-tree sums\.Proceedings of the National Academy of Sciences122\(7\),pp\. e2310151122\.External Links:[Document](https://dx.doi.org/10.1073/pnas.2310151122)Cited by:[§4](https://arxiv.org/html/2606.30995#S4.p1.1)\.
- \[67\]S\. Thrun\(1991\)The monk”s problems\-a performance comparison of different learning algorithms, cmu\-cs\-91\-197, sch\.External Links:[Link](https://api.semanticscholar.org/CorpusID:59699060)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px16.1.1)\.
- \[68\]S\. Verwer and Y\. Zhang\(2019\)Learning optimal classification trees using a binary linear program formulation\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.33,pp\. 1625–1632\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px2.p1.1)\.
- \[69\]T\. Vidal and M\. Schiffer\(2020\)Born\-again tree ensembles\.InInternational conference on machine learning,pp\. 9743–9753\.Cited by:[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px3.p1.1)\.
- \[70\]T\. Wang and Q\. Lin\(2021\-01\)Hybrid predictive models: when an interpretable model collaborates with a black\-box model\.J\. Mach\. Learn\. Res\.22\(1\)\.External Links:ISSN 1532\-4435Cited by:[§1](https://arxiv.org/html/2606.30995#S1.p2.1),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2606.30995#S4.p1.1)\.
- \[71\]T\. Wang\(2019\)Gaining no or low\-cost transparency with interpretable partial substitute\.InInternational Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2606.30995#S1.p2.1),[§2](https://arxiv.org/html/2606.30995#S2.SS0.SSS0.Px1.p1.1),[§4](https://arxiv.org/html/2606.30995#S4.p1.1)\.
- \[72\]J\. Wnek\(1993\)MONK’s Problems\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5R30RCited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px16.1.1)\.
- \[73\]I\. Yeh and C\. Lien\(2009\)The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients\.Expert Syst\. Appl\.36,pp\. 2473–2480\.External Links:[Link](https://api.semanticscholar.org/CorpusID:15696161)Cited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px9.1.1)\.
- \[74\]I\. Yeh\(2009\)Default of Credit Card Clients\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C55S3HCited by:[§F\.2](https://arxiv.org/html/2606.30995#A6.SS2.SSS0.Px9.1.1)\.

## Appendix Contents

## Appendix AProofs

See[1](https://arxiv.org/html/2606.30995#Thmproposition1)

###### Proof\.

For each stagejj, define the set of samples that reach stagejjas

Dj:=\{i:T1​\(xi\)=⋯=Tj−1​\(xi\)=defer\},D\_\{j\}:=\\\{i:T\_\{1\}\(x\_\{i\}\)=\\cdots=T\_\{j\-1\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\},withD1=\{1,…,N\}D\_\{1\}=\\\{1,\\ldots,N\\\}\.

Making the weight update

wi\(j\)=wi​𝟙​\{i∈Dj\}\.w\_\{i\}^\{\(j\)\}=w\_\{i\}\\mathds\{1\}\\\{i\\in D\_\{j\}\\\}\.
The all\-defer baseline has decision tree objective

Ldefer,B​\(𝒟w,τ,η\)=∑i=1Nwi​\(𝟙​\{B​\(xi\)≠yi\}\+η\),L\_\{\\mathrm\{defer\},B\}\(\\mathcal\{D\}^\{w\},\\tau,\\eta\)=\\sum\_\{i=1\}^\{N\}w\_\{i\}\\Bigl\(\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\Bigr\),
Now consider the contribution of a single stagejjon the samples that reach it\. On the weighted dataset𝒟w\(j\)\\mathcal\{D\}^\{w^\{\(j\)\}\}, the single\-tree defer objective is

LTj,B​\(𝒟w\(j\),τ,η\)=τ​\(\|Tj\|−1\)\+∑i=1Nwi\(j\)​\(𝟙​\{y^Tj,B​\(xi\)≠yi\}\+η​𝟙​\{Tj​\(xi\)=defer\}\)\.L\_\{T\_\{j\},B\}\(\\mathcal\{D\}^\{w^\{\(j\)\}\},\\tau,\\eta\)=\\tau\(\|T\_\{j\}\|\-1\)\+\\sum\_\{i=1\}^\{N\}w\_\{i\}^\{\(j\)\}\\Bigl\(\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{j\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\mathds\{1\}\\\{T\_\{j\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\)\.The all\-defer tree \(a single defer leaf\) on the same weighted dataset has objective

Ldefer,B​\(𝒟w\(j\),τ,η\)=∑i=1Nwi\(j\)​\(𝟙​\{B​\(xi\)≠yi\}\+η\)\.L\_\{\\mathrm\{defer\},B\}\(\\mathcal\{D\}^\{w^\{\(j\)\}\},\\tau,\\eta\)=\\sum\_\{i=1\}^\{N\}w\_\{i\}^\{\(j\)\}\\Bigl\(\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\Bigr\)\.Therefore,

Δj=Ldefer,B​\(𝒟w\(j\),τ,η\)−LTj,B​\(𝒟w\(j\),τ,η\)\\Delta\_\{j\}=L\_\{\\mathrm\{defer\},B\}\(\\mathcal\{D\}^\{w^\{\(j\)\}\},\\tau,\\eta\)\-L\_\{T\_\{j\},B\}\(\\mathcal\{D\}^\{w^\{\(j\)\}\},\\tau,\\eta\)equals

−τ​\(\|Tj\|−1\)\+∑i=1Nwi\(j\)​\[𝟙​\{B​\(xi\)≠yi\}\+η−𝟙​\{y^Tj,B​\(xi\)≠yi\}−η​𝟙​\{Tj​\(xi\)=defer\}\]\.\-\\tau\(\|T\_\{j\}\|\-1\)\+\\sum\_\{i=1\}^\{N\}w\_\{i\}^\{\(j\)\}\\Bigl\[\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{j\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\eta\\mathds\{1\}\\\{T\_\{j\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\]\.
Now sum the expression forΔj\\Delta\_\{j\}overj=1,…,kj=1,\\ldots,k:

∑j=1kΔj=−τ​∑j=1k\(\|Tj\|−1\)\+∑j=1k∑i=1Nwi\(j\)​\[𝟙​\{B​\(xi\)≠yi\}\+η−𝟙​\{y^Tj,B​\(xi\)≠yi\}−η​𝟙​\{Tj​\(xi\)=defer\}\]\.\\sum\_\{j=1\}^\{k\}\\Delta\_\{j\}=\-\\tau\\sum\_\{j=1\}^\{k\}\(\|T\_\{j\}\|\-1\)\+\\sum\_\{j=1\}^\{k\}\\sum\_\{i=1\}^\{N\}w\_\{i\}^\{\(j\)\}\\Bigl\[\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{j\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\eta\\mathds\{1\}\\\{T\_\{j\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\]\.
Using

wi\(j\)=wi​𝟙​\{T1​\(xi\)=⋯=Tj−1​\(xi\)=defer\},w\_\{i\}^\{\(j\)\}=w\_\{i\}\\mathds\{1\}\\\{T\_\{1\}\(x\_\{i\}\)=\\cdots=T\_\{j\-1\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\},we can rewrite the double sum sample\-by\-sample:

∑j=1k∑i=1Nwi\(j\)​\[𝟙​\{B​\(xi\)≠yi\}\+η−𝟙​\{y^Tj,B​\(xi\)≠yi\}−η​𝟙​\{Tj​\(xi\)=defer\}\]\\sum\_\{j=1\}^\{k\}\\sum\_\{i=1\}^\{N\}w\_\{i\}^\{\(j\)\}\\Bigl\[\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{j\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\eta\\mathds\{1\}\\\{T\_\{j\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\]=∑i=1Nwi∑j=1k𝟙\{T1\(xi\)=⋯=Tj−1\(xi\)=defer\}\[𝟙\{B\(xi\)≠yi\}\+η\\displaystyle=\\sum\_\{i=1\}^\{N\}w\_\{i\}\\sum\_\{j=1\}^\{k\}\\mathds\{1\}\\\{T\_\{1\}\(x\_\{i\}\)=\\cdots=T\_\{j\-1\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigl\[\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta−𝟙\{y^Tj,B\(xi\)≠yi\}−η𝟙\{Tj\(xi\)=defer\}\]\.\\displaystyle\\hskip 65\.00009pt\-\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{j\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\eta\\mathds\{1\}\\\{T\_\{j\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\]\.
Fix a sampleii\. Letrir\_\{i\}be the first stage that predicts a label:

ri:=min⁡\{j:Tj​\(xi\)≠defer\},r\_\{i\}:=\\min\\\{j:T\_\{j\}\(x\_\{i\}\)\\neq\\mathrm\{defer\}\\\},if such a stage exists\. If no such stage exists, setri=k\+1r\_\{i\}=k\+1\.

There are 3 cases: \(1\.1, 1\.2, and 2\.1\)\.

Case 1\.1:j<ri≤kj<r\_\{i\}\\leq k\. Here, sampleiireaches stagejjbut it still defers\.

Therefore,Tj​\(xi\)=deferT\_\{j\}\(x\_\{i\}\)=\\mathrm\{defer\}, so the prediction used in the loss of training the single defer tree isy^Tj,B​\(xi\)=B​\(xi\)\\hat\{y\}\_\{T\_\{j\},B\}\(x\_\{i\}\)=B\(x\_\{i\}\)\. Also,𝟙​\{Tj​\(xi\)=defer\}=1\\mathds\{1\}\\\{T\_\{j\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}=1\. So, the bracket becomes

𝟙​\{B​\(xi\)≠yi\}\+η−𝟙​\{B​\(xi\)≠yi\}−η=0\.\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\eta=0\.
So every stage before the first predicting stage contributes nothing to the improvement in the objective for that sample\. Intuitively, beforerir\_\{i\}, the model is still doing exactly what the all defer tree does: defers toBBand pays the penalty\.

Case 1\.2:j=ri≤kj=r\_\{i\}\\leq k\. The tree predicts\.

We knowTri​\(xi\)≠deferT\_\{r\_\{i\}\}\(x\_\{i\}\)\\neq\\mathrm\{defer\}and𝟙​\{Tri​\(xi\)=defer\}=0\\mathds\{1\}\\\{T\_\{r\_\{i\}\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}=0\. This is the first stage for which we make a prediction for this sample, soy^Tri,B​\(xi\)=y^T1:k,B​\(xi\)\\hat\{y\}\_\{T\_\{r\_\{i\}\},B\}\(x\_\{i\}\)=\\hat\{y\}\_\{T\_\{1:k\},B\}\(x\_\{i\}\)\.

Therefore, the bracket becomes

𝟙​\{B​\(xi\)≠yi\}\+η−𝟙​\{y^T1:k,B​\(xi\)≠yi\}\.\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{1:k\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\.
Since the full MDT does not defer on this sample, we also know𝟙​\{T^1:k​\(xi\)=defer\}=0\.\\mathds\{1\}\\\{\\hat\{T\}\_\{1:k\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}=0\.

Appending this zero term will become useful later in the proof\.

𝟙​\{B​\(xi\)≠yi\}\+η−\(𝟙​\{y^T1:k,B​\(xi\)≠yi\}\+η​𝟙​\{T^1:k​\(xi\)=defer\}\)\.\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\Bigl\(\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{1:k\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\mathds\{1\}\\\{\\hat\{T\}\_\{1:k\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\)\.
Case 2\.1:ri=k\+1r\_\{i\}=k\+1\. Here, the MDT defers to the black box\. No stage predicts\. The sample is deferred by every stage\.

Writing the consequences of this formally:

T1​\(xi\)=T2​\(xi\)=⋯=Tk​\(xi\)=defer\.T\_\{1\}\(x\_\{i\}\)=T\_\{2\}\(x\_\{i\}\)=\\cdots=T\_\{k\}\(x\_\{i\}\)=\\mathrm\{defer\}\.
For everyj≤kj\\leq k

y^Tj,B​\(xi\)=B​\(xi\)\\hat\{y\}\_\{T\_\{j\},B\}\(x\_\{i\}\)=B\(x\_\{i\}\)
and

𝟙​\{Tj​\(xi\)=defer\}=1\.\\mathds\{1\}\\\{T\_\{j\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}=1\.
Therefore, every bracket is

𝟙​\{B​\(xi\)≠yi\}\+η−𝟙​\{B​\(xi\)≠yi\}−η=0\.\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\eta=0\.
Now, with the three cases solved, we can look back at the double sum\.

∑j=1k∑i=1Nwi\(j\)​\[𝟙​\{B​\(xi\)≠yi\}\+η−𝟙​\{y^Tj,B​\(xi\)≠yi\}−η​𝟙​\{Tj​\(xi\)=defer\}\]\\sum\_\{j=1\}^\{k\}\\sum\_\{i=1\}^\{N\}w\_\{i\}^\{\(j\)\}\\Bigl\[\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{j\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\eta\\mathds\{1\}\\\{T\_\{j\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\]=∑i=1Nwi∑j=1k𝟙\{T1\(xi\)=⋯=Tj−1\(xi\)=defer\}\[𝟙\{B\(xi\)≠yi\}\+η\\displaystyle=\\sum\_\{i=1\}^\{N\}w\_\{i\}\\sum\_\{j=1\}^\{k\}\\mathds\{1\}\\\{T\_\{1\}\(x\_\{i\}\)=\\cdots=T\_\{j\-1\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigl\[\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta−𝟙\{y^Tj,B\(xi\)≠yi\}−η𝟙\{Tj\(xi\)=defer\}\]\.\\displaystyle\\hskip 65\.00009pt\-\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{j\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\eta\\mathds\{1\}\\\{T\_\{j\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\]\.
We now claim thatSiS\_\{i\}is the entire inner sum over stagesj=1,…,kj=1,\\ldots,kfor one sampleii:

Si=𝟙​\{B​\(xi\)≠yi\}\+η−\(𝟙​\{y^T1:k,B​\(xi\)≠yi\}\+η​𝟙​\{T^1:k​\(xi\)=defer\}\)\.S\_\{i\}=\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\Bigl\(\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{1:k\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\mathds\{1\}\\\{\\hat\{T\}\_\{1:k\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\)\.
Recall we showed that at most onejjis nonzero for a fixed sampleii\. Ifri=k\+1r\_\{i\}=k\+1, every stage defers, so all terms are zero\. We appended the zero term in Case 1\.2 to give us this expression\. The other two cases were evaluated to 0\.SiS\_\{i\}is precisely the sum of all of them, which simplifies to just Case 1\.2\.

Continuing, the double sum is

=∑i=1Nwi​Si,=\\sum\_\{i=1\}^\{N\}w\_\{i\}S\_\{i\},
=∑i=1Nwi​\[𝟙​\{B​\(xi\)≠yi\}\+η−𝟙​\{y^T1:k,B​\(xi\)≠yi\}−η​𝟙​\{T^1:k​\(xi\)=defer\}\]\.=\\sum\_\{i=1\}^\{N\}w\_\{i\}\\Bigl\[\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{1:k\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\eta\\mathds\{1\}\\\{\\hat\{T\}\_\{1:k\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\]\.
Now plug this back into the sum over improvements,

∑j=1kΔj=−τ​∑j=1k\(\|Tj\|−1\)\+∑i=1Nwi​Si\.\\sum\_\{j=1\}^\{k\}\\Delta\_\{j\}=\-\\tau\\sum\_\{j=1\}^\{k\}\(\|T\_\{j\}\|\-1\)\+\\sum\_\{i=1\}^\{N\}w\_\{i\}S\_\{i\}\.
∑j=1kΔj=−τ​∑j=1k\(\|Tj\|−1\)\+∑i=1Nwi​\[𝟙​\{B​\(xi\)≠yi\}\+η−𝟙​\{y^T1:k,B​\(xi\)≠yi\}−η​𝟙​\{T^1:k​\(xi\)=defer\}\]\.\\sum\_\{j=1\}^\{k\}\\Delta\_\{j\}=\-\\tau\\sum\_\{j=1\}^\{k\}\(\|T\_\{j\}\|\-1\)\+\\sum\_\{i=1\}^\{N\}w\_\{i\}\\Bigl\[\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\-\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{1:k\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\eta\\mathds\{1\}\\\{\\hat\{T\}\_\{1:k\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\]\.
Rearranging,

∑j=1kΔj\\displaystyle\\sum\_\{j=1\}^\{k\}\\Delta\_\{j\}=\[∑i=1Nwi​\(𝟙​\{B​\(xi\)≠yi\}\+η\)\]\\displaystyle=\\left\[\\sum\_\{i=1\}^\{N\}w\_\{i\}\\bigl\(\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\bigr\)\\right\]−\[τ​∑j=1k\(\|Tj\|−1\)\+∑i=1Nwi​\(𝟙​\{y^T1:k,B​\(xi\)≠yi\}\+η​𝟙​\{T^1:k​\(xi\)=defer\}\)\]\.\\displaystyle\\quad\-\\left\[\\tau\\sum\_\{j=1\}^\{k\}\(\|T\_\{j\}\|\-1\)\+\\sum\_\{i=1\}^\{N\}w\_\{i\}\\Bigl\(\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{1:k\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\mathds\{1\}\\\{\\hat\{T\}\_\{1:k\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\)\\right\]\.The second bracket is exactly the MDT objective:

ℒT1:k,B​\(𝒟w,τ,η\)=τ​∑j=1k\(\|Tj\|−1\)\+∑i=1Nwi​\(𝟙​\{y^T1:k,B​\(xi\)≠yi\}\+η​𝟙​\{T^1:k​\(xi\)=defer\}\)\.\\mathcal\{L\}\_\{T\_\{1:k\},B\}\(\\mathcal\{D\}^\{w\},\\tau,\\eta\)=\\tau\\sum\_\{j=1\}^\{k\}\(\|T\_\{j\}\|\-1\)\+\\sum\_\{i=1\}^\{N\}w\_\{i\}\\Bigl\(\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{1:k\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\mathds\{1\}\\\{\\hat\{T\}\_\{1:k\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\Bigr\)\.
Likewise, the first term is the defer leaf objective\.

Ldefer,B​\(𝒟w,τ,η\)=∑iwi​\(𝟙​\{B​\(xi\)≠yi\}\+η\)\.L\_\{\\mathrm\{defer\},B\}\(\\mathcal\{D\}^\{w\},\\tau,\\eta\)=\\sum\_\{i\}w\_\{i\}\(\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\)\.
These two facts establish what we wanted to show\.

∎

Proposition[2](https://arxiv.org/html/2606.30995#Thmproposition2)establishes the relationship between sparsity, accuracy, and deferral for sparse decision trees of unbounded depth\. Consequently, the same claim holds when the model class is restricted to decision trees of any fixed bounded depthdd\.

###### Proposition 2\(Accuracy\-deferral trade\-off\)\.

LetT∗T^\{\*\}be an optimal defer tree and letvvbe a defer leaf\. DefineSv=\{i:xi​reaches​v\}S\_\{v\}=\\\{i:x\_\{i\}\\text\{ reaches \}v\\\}\.

For any decision treeUUused to replacevv, define

Δ​\(U\)=∑i∈Sv𝟙​\{U​\(xi\)≠yi\}−∑i∈Sv𝟙​\{B​\(xi\)≠yi\}\.\\Delta\(U\)=\\sum\_\{i\\in S\_\{v\}\}\\mathds\{1\}\\\{U\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\sum\_\{i\\in S\_\{v\}\}\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\.Then

Δ​\(U\)≥η​\|Sv\|−τ​\(\|U\|−1\)\.\\Delta\(U\)\\;\\geq\\;\\eta\\,\|S\_\{v\}\|\\;\-\\;\\tau\\bigl\(\|U\|\-1\\bigr\)\.LetU​\(xi\)U\(x\_\{i\}\)In particular, ifU​\(xi\)=B​\(xi\)U\(x\_\{i\}\)=B\(x\_\{i\}\)for alli∈Svi\\in S\_\{v\}, then

\|U\|≥1\+η​\|Sv\|τ\.\|U\|\\;\\geq\\;1\+\\frac\{\\eta\\,\|S\_\{v\}\|\}\{\\tau\}\.

###### Proof\.

We first note that whenever an optimal defer tree places a defer leafvvat a subproblem, then this choice must be at least as good \(in objective\) as both replacingvvwith a majority prediction and replacingvvwith a subtree rooted at that subproblem, regardless of whether the subtree itself contains defer leaves\.

The proof is an exchange argument from the optimality ofT∗T^\{\*\}\.

The defer\-tree objective when referencing a base model with predictionsB​\(xi\)B\(x\_\{i\}\)is:

Ldefer​\(T\)=τ​\(\|T\|−1\)\+∑i=1NℓT​\(i\),L\_\{\\mathrm\{defer\}\}\(T\)=\\tau\\bigl\(\|T\|\-1\\bigr\)\+\\sum\_\{i=1\}^\{N\}\\ell\_\{T\}\(i\),
where

ℓT​\(i\)=𝟙​\{T​\(xi\)∈Y,T​\(xi\)≠yi\}\+𝟙​\{T​\(xi\)=defer,B​\(xi\)≠yi\}\+η​1​\{T​\(xi\)=defer\}\.\\ell\_\{T\}\(i\)=\\mathds\{1\}\\\{T\(x\_\{i\}\)\\in Y,\\;T\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\mathds\{1\}\\\{T\(x\_\{i\}\)=\\mathrm\{defer\},\\;B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\,\\mathbf\{\\mathds\{1\}\}\\\{T\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\.
Take any decision treeUU, and form a new defer treeT′T^\{\\prime\}by replacing the defer leafvvinT∗T^\{\*\}withUU\.

Then, one leaf is removed, and\|U\|\|U\|are added\.

\|T′\|=\|T∗\|−1\+\|U\|,\|T^\{\\prime\}\|=\|T^\{\*\}\|\-1\+\|U\|,
\|T′\|−\|T∗\|=\|U\|−1\.\|T^\{\\prime\}\|\-\|T^\{\*\}\|=\|U\|\-1\.
For everyi∉Svi\\notin S\_\{v\}, the prediction path is unchanged, so the loss is unchanged\.

For everyi∈Svi\\in S\_\{v\}, it had previously faced a penalty of𝟙​\{B​\(xi\)≠yi\}\+η\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta, because it was deferred\. Now, it faces a cost of𝟙​\{U​\(xi\)≠yi\}\\mathds\{1\}\\\{U\(x\_\{i\}\)\\neq y\_\{i\}\\\}\.

Therefore,

Ldefer​\(T′\)−Ldefer​\(T∗\)=τ​\(\|U\|−1\)\+∑i∈Sv𝟙​\{U​\(xi\)≠yi\}−∑i∈Sv\(𝟙​\{B​\(xi\)≠yi\}\+η\)\.L\_\{\\mathrm\{defer\}\}\(T^\{\\prime\}\)\-L\_\{\\mathrm\{defer\}\}\(T^\{\*\}\)=\\tau\\bigl\(\|U\|\-1\\bigr\)\+\\sum\_\{i\\in S\_\{v\}\}\\mathds\{1\}\\\{U\(x\_\{i\}\)\\neq y\_\{i\}\\\}\-\\sum\_\{i\\in S\_\{v\}\}\\bigl\(\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\bigr\)\.
BecauseLdefer​\(T′\)−Ldefer​\(T∗\)≥0L\_\{\\mathrm\{defer\}\}\(T^\{\\prime\}\)\-L\_\{\\mathrm\{defer\}\}\(T^\{\*\}\)\\geq 0, we get that

Δ​\(U\)≥η​\|Sv\|−τ​\(\|U\|−1\)\.\\Delta\(U\)\\geq\\eta\|S\_\{v\}\|\-\\tau\\bigl\(\|U\|\-1\\bigr\)\.
A corollary of this is ifU​\(xi\)=B​\(xi\)U\(x\_\{i\}\)=B\(x\_\{i\}\), for alli∈Svi\\in S\_\{v\}, then clearly

∑i∈Sv𝟙​\{U​\(xi\)≠yi\}=∑i∈Sv𝟙​\{B​\(xi\)≠yi\}\.\\sum\_\{i\\in S\_\{v\}\}\\mathds\{1\}\\\{U\(x\_\{i\}\)\\neq y\_\{i\}\\\}=\\sum\_\{i\\in S\_\{v\}\}\\mathds\{1\}\\\{B\(x\_\{i\}\)\\neq y\_\{i\}\\\}\.
Given thatΔ​\(U\)=0\\Delta\(U\)=0, we get0≥η​\|Sv\|−τ​\(\|U\|−1\)0\\geq\\eta\|S\_\{v\}\|\-\\tau\\bigl\(\|U\|\-1\\bigr\)\.

Equivalently,

\|U\|≥1\+η​\|Sv\|τ\.\|U\|\\geq 1\+\\frac\{\\eta\|S\_\{v\}\|\}\{\\tau\}\.
∎

See[1](https://arxiv.org/html/2606.30995#Thmtheorem1)

###### Proof\.

We will use either\|Tj\|\|T\_\{j\}\|orℓj\\ell\_\{j\}interchangeably to denote the number of leaves in stagejj, anddjd\_\{j\}to denote the number of deferral leaves, not to be confused with the depth budget of each tree, which isdd\.

In stagejj, each leaf corresponds to a unique root\-to\-leaf path, and hence to a conjunction of split conditions\. For each non\-deferral leafκ\\kappain stagejj, letAκA\_\{\\kappa\}denote the conjunction of conditions along its path, and letyκ∈\{0,1\}y\_\{\\kappa\}\\in\\\{0,1\\\}be its prediction\.

We construct a rule list by concatenatingKKsections, one for each stage\. In sectionjj, we include one antecedent \(and the corresponding prediction\) for each non\-deferral leafκ\\kappaof stagejj:

if​Aκ​then predict​yκ\.\\text\{if \}A\_\{\\kappa\}\\text\{ then predict \}y\_\{\\kappa\}\.
Note thatAκA\_\{\\kappa\}, the conjunction of conditions along a root\-to\-leaf path in a single\-stage tree, contains at mostddconditions, since each tree has depth at mostdd\.

Because the leaves of a decision tree partition the input space, and each later stage operates only on the deferred region, the stages cover disjoint parts of the input space\. Within a stage, there is no interaction between antecedents, so they may be listed in any order without ambiguity\. While the choice of ordering may simplify individual antecedent conditions, it does not change the total number of rules\.

We claim this rule list is equivalent to the MDT\. Consider any inputxx\. In the MDT,xxis first evaluated at stage11\. If it reaches a non\-deferral leaf, the MDT outputs the corresponding prediction and halts\. In the rule list, exactly the antecedent corresponding to that leaf is satisfied \(and the consequent is the label of that leaf\), so the first matching rule produces the same output\.

If insteadxxreaches a deferral leaf at stage11, then no antecedent from section11is satisfied, since that section contains only non\-deferral leaves\. The evaluation proceeds to section22, mirroring the MDT’s transition to stage22\. Repeating this argument inductively, the antecedent that is satisfied corresponds exactly to the non\-deferral leaf reached byxxin the MDT, and outputs the same prediction\.

Thus, the rule list is equivalent to the MDT\.

Finally, in stagejj, there areℓj−dj\\ell\_\{j\}\-d\_\{j\}non\-deferral leaves, each contributing exactly one antecedent\. Summing over all stages yields the total number of antecedents:

∑j=1K\(ℓj−dj\)\.\\sum\_\{j=1\}^\{K\}\(\\ell\_\{j\}\-d\_\{j\}\)\.
∎

###### Corollary 1\(MDTs do not have wide rules\)\.

Let a rule list be defined over conjunctions of feature queries, where each satisfied rule must immediately output a leaf prediction\. Then, for any MDT composed ofmmdefer trees each of depthdd, every rule in the equivalent rule\-list representation of the interpretable component has at mostddliterals\.

###### Proof\.

This follows direction from the construction discussed in[Theorem 1](https://arxiv.org/html/2606.30995#Thmtheorem1), which uses paths in each tree as rules, each of which must be of depth at mostdd\. ∎

###### Proposition 3\(Majority\-vote ensembles have wide rules\)\.

Let a rule list be defined over any conjunction of feature queries in a dataset, such that the true branch must be classified immediately with a leaf\. Then there exist binary decision treesT1,…,TmT\_\{1\},\\dots,T\_\{m\}, each of depthdd, such that the classifier defined by their majority vote cannot be represented by an equivalent rule list unless some rule queriesΩ​\(m​d\)\\Omega\(md\)literals\.

###### Proof\.

Let each tree compute an XOR overddbinary features, and suppose that the feature sets used by different trees are disjoint\. Assume that all feature value combinations are possible\. For an XOR overddfeatures, no subset of features can determine the tree’s predictions\.

Now consider any rule in an equivalent rule list whose condition is satisfied by at least one input, and that assigns a label\. Let us consider using that rule as the first rule\. Since the rule must classify the affected points immediately, its conjunction must be sufficient to determine the majority\-vote prediction for every completion of the unqueried features\.

To force the majority vote, the rule must determine the outputs of at least⌈m/2⌉\\lceil m/2\\rceiltrees \(for the even case, we assume ties can be broken arbitrarily\)\. Because the trees use disjoint feature sets, determining the output of each such XOR tree requires querying allddof its features\. Hence, the rule must contain at least

d​\(⌈m2⌉\)=Ω​\(m​d\)d\\left\(\\left\\lceil\\frac\{m\}\{2\}\\right\\rceil\\right\)=\\Omega\(md\)literals\.

∎

As we show in the next theorem, the distance\-based weighting rule admits an entropy\-regularized variational interpretation\. Among all distributions, the normalized weights best balance the expected distance to being deferred and the amount of deviation from uniform \(according toγ\\gamma\)\.

###### Proposition 4\(Gibbs form of distance\-based weights\)\.

For each training data pointii, takeci:=log⁡\(1\+Di\)c\_\{i\}:=\\log\(1\+D\_\{i\}\)and letuube the uniform distribution over the training data points\.

The following objective \(withγ\>0\)\\gamma\>0\)has a unique minimizer \(over all distributionsqqon the training data points\) given byqi∝\(1\+Di\)−γq\_\{i\}\\propto\(1\+D\_\{i\}\)^\{\-\\gamma\}\.

𝒥​\(q\)=𝔼q​\[ci\]\+1γ​KL​\(q∥u\)\\mathcal\{J\}\(q\)=\\mathbb\{E\}\_\{q\}\[c\_\{i\}\]\+\\frac\{1\}\{\\gamma\}\\mathrm\{KL\}\(q\\\|u\)

###### Proof\.

Plugging in definitions,

𝒥​\(q\)=∑i=1Nqi​ci\+1γ​∑i=1Nqi​log⁡qiui\.\\mathcal\{J\}\(q\)=\\sum\_\{i=1\}^\{N\}q\_\{i\}c\_\{i\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{N\}q\_\{i\}\\log\\frac\{q\_\{i\}\}\{u\_\{i\}\}\.
Becauseui=1/Nu\_\{i\}=1/N,

log⁡qiui=log⁡qi−log⁡\(1/N\)=log⁡qi\+log⁡N\.\\log\\frac\{q\_\{i\}\}\{u\_\{i\}\}=\\log q\_\{i\}\-\\log\(1/N\)=\\log q\_\{i\}\+\\log N\.
This yields

𝒥​\(q\)=∑i=1Nqi​ci\+1γ​∑i=1Nqi​log⁡qi\+1γ​∑i=1Nqi​log⁡N=∑i=1Nqi​ci\+1γ​∑i=1Nqi​log⁡qi\+1γ​log⁡N\.\\mathcal\{J\}\(q\)=\\sum\_\{i=1\}^\{N\}q\_\{i\}c\_\{i\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{N\}q\_\{i\}\\log q\_\{i\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{N\}q\_\{i\}\\log N=\\sum\_\{i=1\}^\{N\}q\_\{i\}c\_\{i\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{N\}q\_\{i\}\\log q\_\{i\}\+\\frac\{1\}\{\\gamma\}\\log N\.
The third term is constant w\.r\.tqq, so we just need to optimize

∑i=1Nqi​ci\+1γ​∑i=1Nqi​log⁡qi,\\sum\_\{i=1\}^\{N\}q\_\{i\}c\_\{i\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{N\}q\_\{i\}\\log q\_\{i\},subject toqqbeing a probability distribution\.

We form the Lagrangian:

L​\(q,λ\)=∑i=1Nqi​ci\+1γ​∑i=1Nqi​log⁡qi\+λ​\(∑i=1Nqi−1\)\.L\(q,\\lambda\)=\\sum\_\{i=1\}^\{N\}q\_\{i\}c\_\{i\}\+\\frac\{1\}\{\\gamma\}\\sum\_\{i=1\}^\{N\}q\_\{i\}\\log q\_\{i\}\+\\lambda\\left\(\\sum\_\{i=1\}^\{N\}q\_\{i\}\-1\\right\)\.
Becausedd​qi​\(qi​log⁡qi\)=log⁡qi\+1\\frac\{d\}\{dq\_\{i\}\}\(q\_\{i\}\\log q\_\{i\}\)=\\log q\_\{i\}\+1, we get

∂L∂qi=ci\+1γ​\(log⁡qi\+1\)\+λ\.\\frac\{\\partial L\}\{\\partial q\_\{i\}\}=c\_\{i\}\+\\frac\{1\}\{\\gamma\}\(\\log q\_\{i\}\+1\)\+\\lambda\.
For an interior minimizer \(assume noqi=0q\_\{i\}=0\), this is 0\.

ci\+1γ​\(log⁡qi\+1\)\+λ=0\.c\_\{i\}\+\\frac\{1\}\{\\gamma\}\(\\log q\_\{i\}\+1\)\+\\lambda=0\.
Writing equivalent forms,

ci\+1γ​\(log⁡qi\+1\)\+λ=0\.c\_\{i\}\+\\frac\{1\}\{\\gamma\}\(\\log q\_\{i\}\+1\)\+\\lambda=0\.
log⁡qi=−γ​ci−1−γ​λ\.\\log q\_\{i\}=\-\\gamma c\_\{i\}\-1\-\\gamma\\lambda\.
qi=exp⁡\(−1−γ​λ\)​exp⁡\(−γ​ci\)\.q\_\{i\}=\\exp\(\-1\-\\gamma\\lambda\)\\exp\(\-\\gamma c\_\{i\}\)\.
Becauseexp⁡\(−1−γ​λ\)\\exp\(\-1\-\\gamma\\lambda\)does not depend onii, we knowqi∝e−γ​ci=e−γ​ci=e−γ​log⁡\(1\+Di\)=\(1\+Di\)−γ\.q\_\{i\}\\propto e^\{\-\\gamma c\_\{i\}\}=e^\{\-\\gamma c\_\{i\}\}=e^\{\-\\gamma\\log\(1\+D\_\{i\}\)\}=\(1\+D\_\{i\}\)^\{\-\\gamma\}\.

Therefore,

qi∝\(1\+Di\)−γ\.q\_\{i\}\\propto\(1\+D\_\{i\}\)^\{\-\\gamma\}\.
Normalizing, as we know thatqqis a probability distribution,

qi=\(1\+Di\)−γ∑j=1n\(1\+Dj\)−γ\.q\_\{i\}=\\frac\{\(1\+D\_\{i\}\)^\{\-\\gamma\}\}\{\\sum\_\{j=1\}^\{n\}\(1\+D\_\{j\}\)^\{\-\\gamma\}\}\.
We have found the only critical point in the interior \(qi\>0q\_\{i\}\>0\)\. We can show that it is both a minimizer and unique by strict convexity\. We have the sum of a linear function \(which is convex\) and the negative entropy component is strictly convex \(with0​log⁡0:=00\\log 0:=0\)\. Sinceγ\>0\\gamma\>0, the sum is strictly convex\. This suffices to show that the minimizer is unique and that it is an interior critical point\.

∎

###### Proposition 5\(Size of the uncompressed single tree representation\)\.

Let an MDT chain be given by

T1→T2→⋯→TK→W,T\_\{1\}\\to T\_\{2\}\\to\\cdots\\to T\_\{K\}\\to W,where for each stagejj,TjT\_\{j\}hasℓj\\ell\_\{j\}leaves, of whichdjd\_\{j\}are deferral leaves, and letWWbe a fallback model \(such as a single\-tree representation of a black box\) withℓW\\ell\_\{W\}leaves and no deferral leaves\. Then the uncompressed single\-tree representation of the chain has

∑j=1K\(∏i=1j−1di\)​\(ℓj−dj\)\+\(∏i=1Kdi\)​ℓW\\sum\_\{j=1\}^\{K\}\\left\(\\prod\_\{i=1\}^\{j\-1\}d\_\{i\}\\right\)\(\\ell\_\{j\}\-d\_\{j\}\)\+\\left\(\\prod\_\{i=1\}^\{K\}d\_\{i\}\\right\)\\ell\_\{W\}leaves\.

###### Proof\.

A copy ofTjT\_\{j\}appears only when the input has been deferred through all earlier stagesT1,…,Tj−1T\_\{1\},\\dots,T\_\{j\-1\}\.

The treeT1T\_\{1\}appears once\. Each deferral leaf ofT1T\_\{1\}is replaced by a copy ofT2T\_\{2\}, so there ared1d\_\{1\}copies ofT2T\_\{2\}\. Each deferral leaf of each copy ofT2T\_\{2\}is replaced by a copy ofT3T\_\{3\}, so there ared1​d2d\_\{1\}d\_\{2\}copies ofT3T\_\{3\}\.

Continuing inductively, the number of copies ofTjT\_\{j\}in the expanded tree is

∏i=1j−1di,\\prod\_\{i=1\}^\{j\-1\}d\_\{i\},with the convention that this product equals11whenj=1j=1\.

Each copy ofTjT\_\{j\}contributesℓj−dj\\ell\_\{j\}\-d\_\{j\}final \(non\-deferral\) leaves, since itsdjd\_\{j\}deferral leaves are replaced by the root of the next stage\. Therefore, the total number of final leaves contributed by all copies ofTjT\_\{j\}is

\(∏i=1j−1di\)​\(ℓj−dj\)\.\\left\(\\prod\_\{i=1\}^\{j\-1\}d\_\{i\}\\right\)\(\\ell\_\{j\}\-d\_\{j\}\)\.
Summing over all stagesj=1,…,Kj=1,\\dots,K, the total number of final leaves contributed by the MDT stages is

∑j=1K\(∏i=1j−1di\)​\(ℓj−dj\)\.\\sum\_\{j=1\}^\{K\}\\left\(\\prod\_\{i=1\}^\{j\-1\}d\_\{i\}\\right\)\(\\ell\_\{j\}\-d\_\{j\}\)\.
IfdK≠0d\_\{K\}\\neq 0, the remaining deferral leaves of stageKKare replaced by copies ofWW\. The number of copies ofTKT\_\{K\}is∏i=1K−1di\\prod\_\{i=1\}^\{K\-1\}d\_\{i\}, and each such copy hasdKd\_\{K\}deferral leaves, so the total number of copies ofWWis

\(∏i=1K−1di\)​dK=∏i=1Kdi\.\\left\(\\prod\_\{i=1\}^\{K\-1\}d\_\{i\}\\right\)d\_\{K\}=\\prod\_\{i=1\}^\{K\}d\_\{i\}\.
SinceWWhasℓW\\ell\_\{W\}leaves and no deferral leaves, the total number of final leaves contributed by all copies ofWWis

\(∏i=1Kdi\)​ℓW\.\\left\(\\prod\_\{i=1\}^\{K\}d\_\{i\}\\right\)\\ell\_\{W\}\.
Adding the disjoint contributions yields the total number of leaves in the uncompressed tree:

∑j=1K\(∏i=1j−1di\)​\(ℓj−dj\)\+\(∏i=1Kdi\)​ℓW\.\\sum\_\{j=1\}^\{K\}\\left\(\\prod\_\{i=1\}^\{j\-1\}d\_\{i\}\\right\)\(\\ell\_\{j\}\-d\_\{j\}\)\+\\left\(\\prod\_\{i=1\}^\{K\}d\_\{i\}\\right\)\\ell\_\{W\}\.
∎

To exclude the contribution ofWW, one may setdK=0d\_\{K\}=0\. Alternatively, one may setℓW=1\\ell\_\{W\}=1; they are equivalent\.

###### Proposition 6\(Online update for uncompressed subchain size\)\.

Let an MDT subchain be given by

TKlower→TKlower\+1→⋯→TKupper→W,T\_\{K\_\{\\mathrm\{lower\}\}\}\\to T\_\{K\_\{\\mathrm\{lower\}\}\+1\}\\to\\cdots\\to T\_\{K\_\{\\mathrm\{upper\}\}\}\\to W,where for each stagejj,TjT\_\{j\}hasℓj\\ell\_\{j\}leaves, of whichdjd\_\{j\}are deferral leaves, and letWWbe a fallback model withℓW\\ell\_\{W\}leaves and no deferral leaves\. Definepj:=ℓj−djp\_\{j\}:=\\ell\_\{j\}\-d\_\{j\}\.

Then the number of leaves in the uncompressed single\-tree representation of this subchain is

GW​\(a,b\)=∑j=ab\(∏i=aj−1di\)​pj\+\(∏i=abdi\)​ℓW,G\_\{W\}\(a,b\)=\\sum\_\{j=a\}^\{b\}\\left\(\\prod\_\{i=a\}^\{j\-1\}d\_\{i\}\\right\)p\_\{j\}\\;\+\\;\\left\(\\prod\_\{i=a\}^\{b\}d\_\{i\}\\right\)\\ell\_\{W\},wherea=Klowera=K\_\{\\mathrm\{lower\}\}andb=Kupperb=K\_\{\\mathrm\{upper\}\}\.

Moreover, for anyb\+1≤Kupperb\+1\\leq K\_\{\\mathrm\{upper\}\}\(i\.e\. whenever stageTb\+1T\_\{b\+1\}exists with total leaf countℓb\+1\\ell\_\{b\+1\}, deferral leaf countdb\+1d\_\{b\+1\}, andW′W^\{\\prime\}is the new fallback model\), this quantity satisfies the following recurrence:

\(Top\-down\)GW′​\(a,b\+1\)\\displaystyle\\text\{\(Top\-down\)\}\\quad G\_\{W^\{\\prime\}\}\(a,b\+1\)=GW​\(a,b\)\+\(∏i=abdi\)​\[pb\+1\+db\+1​ℓW′−ℓW\],\\displaystyle=G\_\{W\}\(a,b\)\+\\left\(\\prod\_\{i=a\}^\{b\}d\_\{i\}\\right\)\\bigl\[p\_\{b\+1\}\+d\_\{b\+1\}\\ell\_\{W^\{\\prime\}\}\-\\ell\_\{W\}\\bigr\],whereW′W^\{\\prime\}denotes the retrained fallback model after extending the chain\.

###### Proof\.

The expression forGW​\(a,b\)G\_\{W\}\(a,b\)follows from the same counting argument as for the full chain\. A copy ofTjT\_\{j\}appears only when the input has been deferred through all earlier stagesTa,…,Tj−1T\_\{a\},\\dots,T\_\{j\-1\}, yielding∏i=aj−1di\\prod\_\{i=a\}^\{j\-1\}d\_\{i\}copies\. Each copy contributespj=ℓj−djp\_\{j\}=\\ell\_\{j\}\-d\_\{j\}final leaves, since deferral leaves are replaced by the next stage\. The final deferrals from stagebbproduce∏i=abdi\\prod\_\{i=a\}^\{b\}d\_\{i\}copies ofWW, each contributingℓW\\ell\_\{W\}leaves\.

For the recurrence, extending the chain by appendingTb\+1T\_\{b\+1\}and retraining the fallback model toW′W^\{\\prime\}yields

GW′​\(a,b\+1\)=∑j=ab\+1\(∏i=aj−1di\)​pj\+\(∏i=ab\+1di\)​ℓW′\.G\_\{W^\{\\prime\}\}\(a,b\+1\)=\\sum\_\{j=a\}^\{b\+1\}\\left\(\\prod\_\{i=a\}^\{j\-1\}d\_\{i\}\\right\)p\_\{j\}\+\\left\(\\prod\_\{i=a\}^\{b\+1\}d\_\{i\}\\right\)\\ell\_\{W^\{\\prime\}\}\.Separating thej=b\+1j=b\+1term,

=∑j=ab\(∏i=aj−1di\)​pj\+\(∏i=abdi\)​pb\+1\+\(∏i=ab\+1di\)​ℓW′\.=\\sum\_\{j=a\}^\{b\}\\left\(\\prod\_\{i=a\}^\{j\-1\}d\_\{i\}\\right\)p\_\{j\}\+\\left\(\\prod\_\{i=a\}^\{b\}d\_\{i\}\\right\)p\_\{b\+1\}\+\\left\(\\prod\_\{i=a\}^\{b\+1\}d\_\{i\}\\right\)\\ell\_\{W^\{\\prime\}\}\.Using the definition ofGW​\(a,b\)G\_\{W\}\(a,b\),

GW​\(a,b\)=∑j=ab\(∏i=aj−1di\)​pj\+\(∏i=abdi\)​ℓW,G\_\{W\}\(a,b\)=\\sum\_\{j=a\}^\{b\}\\left\(\\prod\_\{i=a\}^\{j\-1\}d\_\{i\}\\right\)p\_\{j\}\+\\left\(\\prod\_\{i=a\}^\{b\}d\_\{i\}\\right\)\\ell\_\{W\},we subtract and add appropriately to obtain

GW′​\(a,b\+1\)=GW​\(a,b\)−\(∏i=abdi\)​ℓW\+\(∏i=abdi\)​pb\+1\+\(∏i=ab\+1di\)​ℓW′\.G\_\{W^\{\\prime\}\}\(a,b\+1\)=G\_\{W\}\(a,b\)\-\\left\(\\prod\_\{i=a\}^\{b\}d\_\{i\}\\right\)\\ell\_\{W\}\+\\left\(\\prod\_\{i=a\}^\{b\}d\_\{i\}\\right\)p\_\{b\+1\}\+\\left\(\\prod\_\{i=a\}^\{b\+1\}d\_\{i\}\\right\)\\ell\_\{W^\{\\prime\}\}\.Factoring∏i=abdi\\prod\_\{i=a\}^\{b\}d\_\{i\}and using

∏i=ab\+1di=\(∏i=abdi\)​db\+1,\\prod\_\{i=a\}^\{b\+1\}d\_\{i\}=\\left\(\\prod\_\{i=a\}^\{b\}d\_\{i\}\\right\)d\_\{b\+1\},gives

GW′​\(a,b\+1\)=GW​\(a,b\)\+\(∏i=abdi\)​\[pb\+1\+db\+1​ℓW′−ℓW\]\.G\_\{W^\{\\prime\}\}\(a,b\+1\)=G\_\{W\}\(a,b\)\+\\left\(\\prod\_\{i=a\}^\{b\}d\_\{i\}\\right\)\\bigl\[p\_\{b\+1\}\+d\_\{b\+1\}\\ell\_\{W^\{\\prime\}\}\-\\ell\_\{W\}\\bigr\]\.
This establishes the desired recurrence\. ∎

In our algorithm, takingℓW=ℓW′=1\\ell\_\{W\}=\\ell\_\{W^\{\\prime\}\}=1\(counting the leaves of deferring to the black box, but not the black box complexity\) is helpful in online updates for early stopping\.

At each stage, we update this quantity using the top\-down recurrence, treating each current deferral path as contributing one leaf\. This yields an incremental update of the form

G←G\+\(∏i=abdi\)​\(ℓb\+1−1\),G\\leftarrow G\+\\left\(\\prod\_\{i=a\}^\{b\}d\_\{i\}\\right\)\(\\ell\_\{b\+1\}\-1\),which can be computed efficiently using running quantities that are already maintained for other early\-stopping criteria based on the sequential model complexity\. If this estimate exceeds a specified leaf budget, we terminate training early\.

## Appendix BCompression Details

### B\.1Subregion Representation

A subregionssis represented by two kinds of constraints\. For each numerical or ordinal featureff, the subregion may store an interval

xf∈\(ℓf,uf\],x\_\{f\}\\in\(\\ell\_\{f\},u\_\{f\}\],where absent bounds are interpreted as\(−∞,∞\]\(\-\\infty,\\infty\]\. For each one\-hot categorical groupgg\(of sizemgm\_\{g\}\), the subregion stores a vector

ag∈\{−1,0,1\}mg,a\_\{g\}\\in\\\{\-1,0,1\\\}^\{m\_\{g\}\},whereag​h=1a\_\{gh\}=1means categoryhhis forced to be active,ag​h=−1a\_\{gh\}=\-1means categoryhhis ruled out, andag​h=0a\_\{gh\}=0means its status is still unknown\. We use these constraints to determine whether a split is already implied by the current subregion, and to refine the subregion when a new branch literal is added\. For instance, we know that no category can be ruled out, and that there cannot be more than 1 active category\.

### B\.2Basic Methods

##### AddLiteral\.

TheAddLiteralroutine refines a subregionssby incorporating a new branching constraintℓ=\(f,ν,b\)\\ell=\(f,\\nu,b\)\. This is done in two steps\. For continuous or ordinal variables,TightenNumericalBoundsupdates the interval for featureffby intersecting it with the constraint induced by the branch\. For categorical variables,DeduceCategoricalImplicationsupdates any categorical group constraints implied by this literal\. Together, these operations produce a new subregions′s^\{\\prime\}that represents the intersection of the original region with the branch condition\.

Algorithm 2AddLiteral\(s,ℓ\)\(s,\\ell\)0:Subregion

ss, literal

ℓ=\(f,ν,b\)\\ell=\(f,\\nu,b\), where

b=trueb=\\texttt\{true\}denotes

f≤νf\\leq\\nu
0:Refined subregion

s′s^\{\\prime\}
1:

s′←TightenNumericalBounds​\(s,ℓ\)s^\{\\prime\}\\leftarrow\\textsc\{TightenNumericalBounds\}\(s,\\ell\)
2:

s′←DeduceCategoricalImplications​\(s′,ℓ\)s^\{\\prime\}\\leftarrow\\textsc\{DeduceCategoricalImplications\}\(s^\{\\prime\},\\ell\)
3:return

s′s^\{\\prime\}

##### TightenNumericalBounds\.

This routine updates the interval constraint for a numerical \(or ordinal\) featureff\. If the literal corresponds to taking the True branch \(f≤νf\\leq\\nu\), the upper bound is tightened tomin⁡\{uf,ν\}\\min\\\{u\_\{f\},\\nu\\\}\. If the literal corresponds to the False branch \(f\>νf\>\\nu\), the lower bound is tightened tomax⁡\{ℓf,ν\}\\max\\\{\\ell\_\{f\},\\nu\\\}\.

Algorithm 3TightenNumericalBounds\(s,\(f,ν,b\)\)\(s,\(f,\\nu,b\)\)0:Subregion

ss, literal

\(f,ν,b\)\(f,\\nu,b\)
0:Subregion with updated numerical interval for

ff
1:

s′←Copy​\(s\)s^\{\\prime\}\\leftarrow\\textsc\{Copy\}\(s\)
2:

\(ℓf,uf\]←s′\.bounds​\(f\)\(\\ell\_\{f\},u\_\{f\}\]\\leftarrow s^\{\\prime\}\.\\mathrm\{bounds\}\(f\), using

\(−∞,∞\]\(\-\\infty,\\infty\]if absent

3:if

b=trueb=\\texttt\{true\}then

4:

uf←min⁡\{uf,ν\}u\_\{f\}\\leftarrow\\min\\\{u\_\{f\},\\nu\\\}
5:else

6:

ℓf←max⁡\{ℓf,ν\}\\ell\_\{f\}\\leftarrow\\max\\\{\\ell\_\{f\},\\nu\\\}
7:endif

8:

s′\.bounds​\(f\)←\(ℓf,uf\]s^\{\\prime\}\.\\mathrm\{bounds\}\(f\)\\leftarrow\(\\ell\_\{f\},u\_\{f\}\]
9:return

s′s^\{\\prime\}

##### DeduceCategoricalImplications\.

This routine handles the case where features are part of a one\-hot categorical group\. For binary decision trees, split thresholds of the formf≤νf\\leq\\nuforce the feature to be0, whilef\>νf\>\\nuforces it to be11\. We encode this by setting the corresponding entry in the group vector to−1\-1\(inactive\) or11\(active\), respectively\.

Multiple categories may be inactive \(ruled out, set to−1\-1\), but at most one category can be active \(set to11\)\. If any entry is set to11, all other entries in the group must be set to−1\-1\. Conversely, if all but one entry are−1\-1, the remaining entry must be11, since exactly one category must be active\.

Algorithm 4DeduceCategoricalImplications\(s,\(f,ν,b\)\)\(s,\(f,\\nu,b\)\)0:Subregion

ss, literal

\(f,ν,b\)\(f,\\nu,b\)
0:Subregion with updated categorical constraints

1:

s′←Copy​\(s\)s^\{\\prime\}\\leftarrow\\textsc\{Copy\}\(s\)
2:if

ffis not a one\-hot categorical featurethen

3:return

s′s^\{\\prime\}
4:endif

5:if

ν\\nuis not a binary split thresholdthen

6:return

s′s^\{\\prime\}
7:endif

8:Let

ggbe the categorical group containing feature

ff
9:Let

hhbe the position of feature

ffwithin group

gg
10:Initialize

ag∈\{−1,0,1\}mga\_\{g\}\\in\\\{\-1,0,1\\\}^\{m\_\{g\}\}to all zeros if absent

11:if

b=trueb=\\texttt\{true\}then

12:

ag​h←−1a\_\{gh\}\\leftarrow\-1\{

f≤νf\\leq\\numeans this one\-hot feature is inactive, consider

ν=12\\nu=\\frac\{1\}\{2\}\}

13:else

14:

ag​h←1a\_\{gh\}\\leftarrow 1\{

f\>νf\>\\numeans this one\-hot feature is active, consider

ν=12\\nu=\\frac\{1\}\{2\}\}

15:endif

16:ifthere exists

hhsuch that

ag​h=1a\_\{gh\}=1then

17:Set

ag​r←−1a\_\{gr\}\\leftarrow\-1for all

r≠hr\\neq h
18:elseifexactly one entry

hhhas

ag​h=0a\_\{gh\}=0then

19:

ag​h←1a\_\{gh\}\\leftarrow 1
20:endif

21:return

s′s^\{\\prime\}

##### ImpliesTrue\.

The routineImpliesTruedetermines whether a split conditionf≤νf\\leq\\nuis guaranteed to hold for all possible points in the subregionss\. For numerical features, this occurs when the upper bound of the interval satisfiesuf≤νu\_\{f\}\\leq\\nu, meaning every feasible point lies on the True side\. For categorical features,f≤νf\\leq\\nucorresponds to the feature being0\. Thus, if the categorical status is−1\-1\(meaning the feature is forced to be0\), the condition is always true\. Otherwise, it is either always forced to be11, or we do not know, so the outcome is not implied, and the routine returns false\.

Algorithm 5ImpliesTrue\(s,f,ν\)\(s,f,\\nu\)0:Subregion

ss, split

f≤νf\\leq\\nu
0:Whether any hypothetical point in

sssatisfies

f≤νf\\leq\\nu
1:

\(ℓf,uf\]←s\.bounds​\(f\)\(\\ell\_\{f\},u\_\{f\}\]\\leftarrow s\.\\mathrm\{bounds\}\(f\), using

\(−∞,∞\]\(\-\\infty,\\infty\]if absent

2:if

uf≤νu\_\{f\}\\leq\\nuthen

3:returntrue

4:endif

5:if

ffis a one\-hot categorical feature and

ν\\nuis a binary split thresholdthen

6:Let

ag​ha\_\{gh\}be the status of feature

ffin its categorical group

7:if

ag​h=−1a\_\{gh\}=\-1then

8:returntrue

9:endif

10:endif

11:returnfalse

##### ImpliesFalse\.

The routineImpliesFalsedetermines whether a split conditionf≤νf\\leq\\nuis guaranteed to fail for all possible points in the subregionss\. For numerical features, this occurs when the lower bound satisfiesℓf≥ν\\ell\_\{f\}\\geq\\nu, meaning all feasible points lie strictly on the False side\. For categorical features,f≤νf\\leq\\nuis always false precisely when the feature equals11\.

Algorithm 6ImpliesFalse\(s,f,ν\)\(s,f,\\nu\)0:Subregion

ss, split

f≤νf\\leq\\nu
0:Whether any hypothetical point in

sssatisfies

f\>νf\>\\nu
1:

\(ℓf,uf\]←s\.bounds​\(f\)\(\\ell\_\{f\},u\_\{f\}\]\\leftarrow s\.\\mathrm\{bounds\}\(f\), using

\(−∞,∞\]\(\-\\infty,\\infty\]if absent

2:if

ℓf≥ν\\ell\_\{f\}\\geq\\nuthen

3:returntrue

4:endif

5:if

ffis a one\-hot categorical feature and

ν\\nuis a binary split thresholdthen

6:Let

ag​ha\_\{gh\}be the status of feature

ffin its categorical group

7:if

ag​h=1a\_\{gh\}=1then

8:returntrue

9:endif

10:endif

11:returnfalse

### B\.3Compression into a Single Defer Tree

A compressed single\-tree representation can substantially reduce root\-to\-leaf path lengths by specializing later\-stage trees to the particular subregion in which they are evaluated\. For example, a later\-stage split such asage≤23\\texttt\{age\}\\leq 23may help distinguish inputs in subregions with18<age≤2518<\\texttt\{age\}\\leq 25andage\>25\\texttt\{age\}\>25, but is redundant for any path already restricted toage≤18\\texttt\{age\}\\leq 18; when unrolling the MDT into a single tree, such splits can be pruned along the branches where they have no effect\. On a high level, we will do this by putting the tree of stagei\+1i\+1in the defer leaves of stageii, simplifying it, and repeating once we reach the new defer leaves\.

Algorithm[7](https://arxiv.org/html/2606.30995#alg7)constructs a compressed*single\-tree representation*of the full MDT by recursively expanding the staged decision process into one tree\.

Algorithm 7BuildCompressedSingleTree\(v,k,s,R1,…,RK\)\(v,k,s,R\_\{1\},\\dots,R\_\{K\}\)0:Node

vv, stage index

kk, subregion

ss, stage roots

R1,…,RKR\_\{1\},\\dots,R\_\{K\}
0:Compressed subtree rooted at

vvunder subregion

ss
1:if

vvis a leafthen

2:if

v\.a​c​t​i​o​n≠deferv\.action\\neq\\texttt\{defer\}then

3:returnleaf with action

v\.a​c​t​i​o​nv\.action
4:endif

5:

k′←k\+1k^\{\\prime\}\\leftarrow k\+1
6:if

k′≤Kk^\{\\prime\}\\leq Kthen

7:return

BuildCompressedSingleTree​\(Rk′,k′,s,R1,…,RK\)\\textsc\{BuildCompressedSingleTree\}\(R\_\{k^\{\\prime\}\},k^\{\\prime\},s,R\_\{1\},\\dots,R\_\{K\}\)
8:endif

9:returnleaf with actionblack\_box

10:endif

11:

f←v\.f​e​a​t​u​r​ef\\leftarrow v\.feature
12:

ν←v\.t​h​r​e​s​h​o​l​d\\nu\\leftarrow v\.threshold
13:if

ImpliesTrue​\(s,f,ν\)\\textsc\{ImpliesTrue\}\(s,f,\\nu\)then

14:return

BuildCompressedSingleTree\(v\.left,k,s,R1,…,RK\)\\textsc\{BuildCompressedSingleTree\}\(v\.left,k,s,R\_\{1\},\\dots,R\_\{K\}\)
15:endif

16:if

ImpliesFalse​\(s,f,ν\)\\textsc\{ImpliesFalse\}\(s,f,\\nu\)then

17:return

BuildCompressedSingleTree\(v\.right,k,s,R1,…,RK\)\\textsc\{BuildCompressedSingleTree\}\(v\.right,k,s,R\_\{1\},\\dots,R\_\{K\}\)
18:endif

19:

sL←AddLiteral​\(s,\(f,ν,true\)\)s\_\{L\}\\leftarrow\\textsc\{AddLiteral\}\(s,\(f,\\nu,\\texttt\{true\}\)\)
20:

sR←AddLiteral​\(s,\(f,ν,false\)\)s\_\{R\}\\leftarrow\\textsc\{AddLiteral\}\(s,\(f,\\nu,\\texttt\{false\}\)\)
21:

uL←BuildCompressedSingleTree\(v\.left,k,sL,R1,…,RK\)u\_\{L\}\\leftarrow\\textsc\{BuildCompressedSingleTree\}\(v\.left,k,s\_\{L\},R\_\{1\},\\dots,R\_\{K\}\)
22:

uR←BuildCompressedSingleTree\(v\.right,k,sR,R1,…,RK\)u\_\{R\}\\leftarrow\\textsc\{BuildCompressedSingleTree\}\(v\.right,k,s\_\{R\},R\_\{1\},\\dots,R\_\{K\}\)
23:returninternal node with split

\(f,ν\)\(f,\\nu\), left child

uLu\_\{L\}, right child

uRu\_\{R\}

The procedure takes as input a nodevvfrom stagekk, along with a subregionssdescribing the set of inputs that may reach this node\. The subregionssencodes all constraints accumulated along the path taken so far, potentially across multiple stages\.

Ifvvis a leaf, there are two cases\. If the leaf corresponds to a terminal prediction \(i\.e\., notdefer\), then the prediction is returned directly\. If the leaf corresponds todefer, then we transition to the next stage: we recurse on the root of stagek\+1k\+1with the same subregionss\. If no further stages remain, we return ablack\_boxleaf, representing the final fallback model\.

Ifvvis an internal node with split\(f,ν\)\(f,\\nu\), we again leverage the subregionssto simplify the structure\. Ifssprovably implies that all possible inputs would satisfy the split \(i\.e\., always take the True branch\), then we recurse only on the left child\. Similarly, ifssimplies the False branch, we recurse only on the right child\. In either case, the split can be removed because it does not affect any possible point in the subregion\.

Otherwise, the split is ambiguous underss, and both branches must be explored\. We construct refined subregionssLs\_\{L\}andsRs\_\{R\}by adding the corresponding literal toss\(whether we are supposing we take the True or False branch\), thereby capturing the additional constraint imposed by each branch\. The algorithm then recursively builds the left and right subtrees under these refined subregions and returns a new internal node with these children\.

### B\.4Sequential Compression

In this section, we show how to \(possibly\) further compress a sequential representation of the MDT\. Because the points outside the defer region are downweighted, it is somewhat unlikely that there exist splits in the MDT that provably do not separate any possible pair of points in the defer region; however, it is still possible\. We note that compression of the sequential representation is exactly the compression done to reduce the number of literals in the rules of the rule list representation\.

Algorithm[8](https://arxiv.org/html/2606.30995#alg8)simplifies a tree relative to a set of possible incoming subregions𝒮\\mathcal\{S\}\(i\.e\., multiple defer leaves may lead to it, not just one\)\. Intuitively, compared to constructing a single tree from the MDT, we must evaluate each split with respect to all subregions simultaneously, rather than a single input region\.

Algorithm 8SimplifySequential\(v,𝒮\)\(v,\\mathcal\{S\}\)0:Node

vv, incoming set of subregions

𝒮\\mathcal\{S\}
0:Compressed subtree rooted at

vv
1:if

vvis a leafthen

2:returnleaf with action

v\.a​c​t​i​o​nv\.action
3:endif

4:

f←v\.f​e​a​t​u​r​ef\\leftarrow v\.feature
5:

τ←v\.t​h​r​e​s​h​o​l​d\\tau\\leftarrow v\.threshold
6:

a​l​l​\_​t​r​u​e←trueall\\\_true\\leftarrow\\texttt\{true\}
7:

a​l​l​\_​f​a​l​s​e←trueall\\\_false\\leftarrow\\texttt\{true\}
8:for all

s∈𝒮s\\in\\mathcal\{S\}do

9:ifnot

ImpliesTrue​\(s,f,τ\)\\textsc\{ImpliesTrue\}\(s,f,\\tau\)then

10:

a​l​l​\_​t​r​u​e←falseall\\\_true\\leftarrow\\texttt\{false\}
11:endif

12:ifnot

ImpliesFalse​\(s,f,τ\)\\textsc\{ImpliesFalse\}\(s,f,\\tau\)then

13:

a​l​l​\_​f​a​l​s​e←falseall\\\_false\\leftarrow\\texttt\{false\}
14:endif

15:endfor

16:if

a​l​l​\_​t​r​u​eall\\\_truethen

17:return

SimplifySequential\(v\.left,𝒮\)\\textsc\{SimplifySequential\}\(v\.left,\\mathcal\{S\}\)
18:endif

19:if

a​l​l​\_​f​a​l​s​eall\\\_falsethen

20:return

SimplifySequential\(v\.right,𝒮\)\\textsc\{SimplifySequential\}\(v\.right,\\mathcal\{S\}\)
21:endif

22:

𝒮L←\[\]\\mathcal\{S\}\_\{L\}\\leftarrow\[\\ \]
23:

𝒮R←\[\]\\mathcal\{S\}\_\{R\}\\leftarrow\[\\ \]
24:for all

s∈𝒮s\\in\\mathcal\{S\}do

25:ifnot

ImpliesFalse​\(s,f,τ\)\\textsc\{ImpliesFalse\}\(s,f,\\tau\)then

26:

s′←TightenNumericalBounds​\(s,\(f,τ,true\)\)s^\{\\prime\}\\leftarrow\\textsc\{TightenNumericalBounds\}\(s,\(f,\\tau,\\texttt\{true\}\)\)
27:

s′←DeduceCategoricalImplications​\(s′,\(f,τ,true\)\)s^\{\\prime\}\\leftarrow\\textsc\{DeduceCategoricalImplications\}\(s^\{\\prime\},\(f,\\tau,\\texttt\{true\}\)\)
28:append

s′s^\{\\prime\}to

𝒮L\\mathcal\{S\}\_\{L\}
29:endif

30:ifnot

ImpliesTrue​\(s,f,τ\)\\textsc\{ImpliesTrue\}\(s,f,\\tau\)then

31:

s′←TightenNumericalBounds​\(s,\(f,τ,false\)\)s^\{\\prime\}\\leftarrow\\textsc\{TightenNumericalBounds\}\(s,\(f,\\tau,\\texttt\{false\}\)\)
32:

s′←DeduceCategoricalImplications​\(s′,\(f,τ,false\)\)s^\{\\prime\}\\leftarrow\\textsc\{DeduceCategoricalImplications\}\(s^\{\\prime\},\(f,\\tau,\\texttt\{false\}\)\)
33:append

s′s^\{\\prime\}to

𝒮R\\mathcal\{S\}\_\{R\}
34:endif

35:endfor

36:

uL←SimplifySequential\(v\.left,𝒮L\)u\_\{L\}\\leftarrow\\textsc\{SimplifySequential\}\(v\.left,\\mathcal\{S\}\_\{L\}\)
37:

uR←SimplifySequential\(v\.right,𝒮R\)u\_\{R\}\\leftarrow\\textsc\{SimplifySequential\}\(v\.right,\\mathcal\{S\}\_\{R\}\)
38:returninternal node with split

\(f,τ\)\(f,\\tau\), left child

uLu\_\{L\}, right child

uRu\_\{R\}

The procedure is recursive and begins at the root node\. For each subregions∈𝒮s\\in\\mathcal\{S\}, we determine whether the split always routes every possible input consistent withss\(not just training samples, but any hypothetical point that satisfies the subregion constraints\) to the True branch, the False branch, or whether the outcome is ambiguous \(lines 8–15\)\. If and only if every subregion is guaranteed to take the True branch, thenall\_trueis set to True\. Similarly, if and only if every subregion is guaranteed to take the False branch, thenall\_falseis set to True\. In either of these cases, the split can be pruned, and we recurse on the corresponding child\. Otherwise, the split cannot be removed, and we must recurse on both branches\.

In lines 24–34, we construct two \(potentially overlapping\) collections of subregions before recursing:

𝒮L=\{s≤:s∈𝒮,s​does not provably imply​f\>t,s≤​is​s​refined with​f≤t\},\\mathcal\{S\}\_\{L\}=\\left\\\{\\,s^\{\\leq\}\\;:\\;s\\in\\mathcal\{S\},\\;s\\text\{ does not provably imply \}f\>t,\\;s^\{\\leq\}\\text\{ is \}s\\text\{ refined with \}f\\leq t\\right\\\},𝒮R=\{s\>:s∈𝒮,s​does not provably imply​f≤t,s\>​is​s​refined with​f\>t\}\.\\mathcal\{S\}\_\{R\}=\\left\\\{\\,s^\{\>\}\\;:\\;s\\in\\mathcal\{S\},\\;s\\text\{ does not provably imply \}f\\leq t,\\;s^\{\>\}\\text\{ is \}s\\text\{ refined with \}f\>t\\right\\\}\.
Each collection is formed by selecting subregions that are compatible with the corresponding branch and refining them with the constraint induced by the split\. Subregions that already contradict a branch are excluded from that side\.

These two collections are not disjoint\. Any subregionssthat does not imply either outcome will appear in both sets \(after being refined by the respective branch on which we recurse\)\.

Algorithm[8](https://arxiv.org/html/2606.30995#alg8)simplifies a tree as much as we provably can in this traversal when given a set of subregions that the tree will be used on\. However, we still need to shrink this set of subregions before simplifying the next tree in the MDT\.

Algorithm 9Build compressed stage trees0:Stage roots

R1,…,RKR\_\{1\},\\dots,R\_\{K\}
0:Compressed stage roots

R~1,…,R~K\\widetilde\{R\}\_\{1\},\\dots,\\widetilde\{R\}\_\{K\}
1:

𝒮←\[\]\\mathcal\{S\}\\leftarrow\[\\ \]
2:

ℛ~←\[\]\\widetilde\{\\mathcal\{R\}\}\\leftarrow\[\\ \]
3:for

k=1,…,Kk=1,\\dots,Kdo

4:

R~k←SimplifySequential​\(Rk,𝒮\)\\widetilde\{R\}\_\{k\}\\leftarrow\\textsc\{SimplifySequential\}\(R\_\{k\},\\mathcal\{S\}\)
5:append

R~k\\widetilde\{R\}\_\{k\}to

ℛ~\\widetilde\{\\mathcal\{R\}\}
6:

𝒫←CollectPathsToAction​\(R~k,defer\)\\mathcal\{P\}\\leftarrow\\textsc\{CollectPathsToAction\}\(\\widetilde\{R\}\_\{k\},\\texttt\{defer\}\)
7:

𝒮←ExtendSubregionsWithFeasiblePaths​\(𝒮,𝒫\)\\mathcal\{S\}\\leftarrow\\textsc\{ExtendSubregionsWithFeasiblePaths\}\(\\mathcal\{S\},\\mathcal\{P\}\)
8:endfor

9:return

ℛ~\\widetilde\{\\mathcal\{R\}\}

Algorithm[9](https://arxiv.org/html/2606.30995#alg9)performs this update iteratively across stages\. At stagekk, after simplifying the treeRkR\_\{k\}intoR~k\\widetilde\{R\}\_\{k\}, we identify all root\-to\-leaf paths that result in adeferdecision\. Each such pathp∈𝒫p\\in\\mathcal\{P\}corresponds to a conjunction of literals describing a region of the input space that will be deferred by the current stage\. To construct the subregions for the next stage, we combine the incoming subregions𝒮\\mathcal\{S\}with these defer paths\. Concretely, Algorithm[10](https://arxiv.org/html/2606.30995#alg10)forms a Cartesian product between𝒮\\mathcal\{S\}and𝒫\\mathcal\{P\}: for each subregions∈𝒮s\\in\\mathcal\{S\}and each defer pathp∈𝒫p\\in\\mathcal\{P\}, we attempt to extendssby sequentially incorporating the literals alongpp\. This process can be viewed as intersecting the region represented bysswith the region defined by the pathpp\. By adding one literal at a time, we allow for early termination\. A contradiction occurs if a literal violates the existing numerical bounds of the subregion or is incompatible with previously deduced categorical constraints\. If any such violation occurs, the extended subregion is discarded\. Otherwise, we tighten the numerical bounds and propagate any implied categorical constraints, producing a refined subregioncc\.

The resulting set𝒮n​e​x​t\\mathcal\{S\}\_\{next\}therefore consists precisely of those subregions that are simultaneously: \(i\) reachable under the previous stages \(captured by𝒮\\mathcal\{S\}\), and \(ii\) routed to deferral by the current stage \(captured by𝒫\\mathcal\{P\}\)\.

Algorithm 10ExtendSubregionsWithFeasiblePaths\(𝒮,𝒫\)\(\\mathcal\{S\},\\mathcal\{P\}\)0:Incoming subregions

𝒮\\mathcal\{S\}, defer paths

𝒫\\mathcal\{P\}
0:Next\-stage incoming subregions

1:

𝒮n​e​x​t←\[\]\\mathcal\{S\}\_\{next\}\\leftarrow\[\\ \]
2:for all

s∈𝒮s\\in\\mathcal\{S\}do

3:for all

p∈𝒫p\\in\\mathcal\{P\}do

4:

c←sc\\leftarrow s
5:

f​e​a​s​i​b​l​e←truefeasible\\leftarrow\\texttt\{true\}
6:for allliteral

ℓ∈p\\ell\\in pdo

7:if

ViolatesNumericBounds​\(c,ℓ\)\\textsc\{ViolatesNumericBounds\}\(c,\\ell\)then

8:

f​e​a​s​i​b​l​e←falsefeasible\\leftarrow\\texttt\{false\}
9:break

10:endif

11:if

ViolatesCategoricalConstraints​\(c,ℓ\)\\textsc\{ViolatesCategoricalConstraints\}\(c,\\ell\)then

12:

f​e​a​s​i​b​l​e←falsefeasible\\leftarrow\\texttt\{false\}
13:break

14:endif

15:

c←TightenNumericalBounds​\(c,ℓ\)c\\leftarrow\\textsc\{TightenNumericalBounds\}\(c,\\ell\)
16:

c←DeduceCategoricalImplications​\(c,ℓ\)c\\leftarrow\\textsc\{DeduceCategoricalImplications\}\(c,\\ell\)
17:endfor

18:if

f​e​a​s​i​b​l​efeasiblethen

19:append

ccto

𝒮n​e​x​t\\mathcal\{S\}\_\{next\}
20:endif

21:endfor

22:endfor

23:return

𝒮n​e​x​t\\mathcal\{S\}\_\{next\}

### B\.5Trivial Extensions

After recursively simplifying the left and right subtrees of a split, we may encounter a situation where both children reduce to identical leaf nodes with the same action\. In this case, the split no longer affects the prediction for any input and can be safely removed\. We refer to such splits as trivial extensions and perform this pruning as a post\-order traversal at the end of any compression scheme\.

Algorithm 11PruneTrivialExtensions\(v\)\(v\)0:Node

vv
0:Tree rooted at

vvwith trivial extensions removed

1:if

vvis a leafthen

2:returnleaf with action

v\.a​c​t​i​o​nv\.action
3:endif

4:

uL←PruneTrivialExtensions\(v\.left\)u\_\{L\}\\leftarrow\\textsc\{PruneTrivialExtensions\}\(v\.left\)
5:

uR←PruneTrivialExtensions\(v\.right\)u\_\{R\}\\leftarrow\\textsc\{PruneTrivialExtensions\}\(v\.right\)
6:if

uLu\_\{L\}and

uRu\_\{R\}are leaves and

uL\.a​c​t​i​o​n=uR\.a​c​t​i​o​nu\_\{L\}\.action=u\_\{R\}\.actionthen

7:returnleaf with action

uL\.a​c​t​i​o​nu\_\{L\}\.action
8:endif

9:returninternal node with split

\(v\.f​e​a​t​u​r​e,v\.t​h​r​e​s​h​o​l​d\)\(v\.feature,v\.threshold\), left child

uLu\_\{L\}, right child

uRu\_\{R\}

## Appendix CDistance to Deferred Region

Each feasible subregions∈𝒮k−1s\\in\\mathcal\{S\}\_\{k\-1\}stores the constraints induced by the current deferred region\. Let𝒥num​\(s\)\\mathcal\{J\}\_\{\\mathrm\{num\}\}\(s\)denote the set of continuous \(or ordinal\) features that have been constrained in subregionss, and let𝒥cat​\(s\)\\mathcal\{J\}\_\{\\mathrm\{cat\}\}\(s\)denote the set of categorical feature groups that have been constrained\. For eachj∈𝒥num​\(s\)j\\in\\mathcal\{J\}\_\{\\mathrm\{num\}\}\(s\), let\(ℓs​j,us​j\]\(\\ell\_\{sj\},u\_\{sj\}\]denote the interval induced by subregionss\. For eachj∈𝒥cat​\(s\)j\\in\\mathcal\{J\}\_\{\\mathrm\{cat\}\}\(s\), letAs​jA\_\{sj\}denote the set of categories consistent \(allowed by\) with subregionss\. Additional details on handling categorical variables are provided in[Appendix B](https://arxiv.org/html/2606.30995#A2)\. At a high level, for a one\-hot encoded categorical group, a subregion may rule out a category via a False split, leave it unconstrained, or identify it as active either through a True split or by eliminating all other categories\. The categories which are consistent with the subregion are exactly the categories that are not ruled out by the subregion\.

We first map each continuous or ordinal feature into its empirical quantile coordinate so that distances across coordinates are on a common scale\. Since features may be discrete, we use the mid\-rank empirical CDF, assigning each valuevvthe quantile

zj​\(v\)=\#​\{Xj<v\}\+12​\#​\{Xj=v\}N\.z\_\{j\}\(v\)=\\frac\{\\\#\\\{X\_\{j\}<v\\\}\+\\tfrac\{1\}\{2\}\\\#\\\{X\_\{j\}=v\\\}\}\{N\}\.
Because interval endpoints may not coincide with observed feature values \(e\.g\., midpoints\), we evaluate endpoint quantiles by snapping to the nearest realized value that remains within the interval\. Specifically, define

z¯j​\(t\)=inf\{zj​\(v\):v\>t,v∈supp​\(Xj\)\},z¯j​\(t\)=sup\{zj​\(v\):v≤t,v∈supp​\(Xj\)\}\.\\underline\{z\}\_\{j\}\(t\)=\\inf\\\{z\_\{j\}\(v\):v\>t,\\ v\\in\\mathrm\{supp\}\(X\_\{j\}\)\\\},\\qquad\\overline\{z\}\_\{j\}\(t\)=\\sup\\\{z\_\{j\}\(v\):v\\leq t,\\ v\\in\\mathrm\{supp\}\(X\_\{j\}\)\\\}\.
Then, for each training pointxix\_\{i\}that is not deferred, define its distance to the current deferred region by

defer\_distT1:k\-1​\(xi\)=mins∈𝒮k−1⁡\(∑j∈𝒥num​\(s\)dj\(s\)​\(xi\)\+∑j∈𝒥cat​\(s\)dj\(s\)​\(xi\)\)\.\\textrm\{defer\\\_dist\}\_\{T\_\{\\textrm\{\{1:k\-1\}\}\}\}\(x\_\{i\}\)=\\min\_\{s\\in\\mathcal\{S\}\_\{k\-1\}\}\\left\(\\sum\_\{j\\in\\mathcal\{J\}\_\{\\mathrm\{num\}\}\(s\)\}d\_\{j\}^\{\(s\)\}\(x\_\{i\}\)\+\\sum\_\{j\\in\\mathcal\{J\}\_\{\\mathrm\{cat\}\}\(s\)\}d\_\{j\}^\{\(s\)\}\(x\_\{i\}\)\\right\)\.
For continuous \(or ordinal\) featuresj∈𝒥num​\(s\)j\\in\\mathcal\{J\}\_\{\\mathrm\{num\}\}\(s\), we measure distance in quantile space as

dj\(s\)​\(xi\)=max⁡\{z¯j​\(ℓs​j\)−zj​\(xi​j\),0\}\+max⁡\{zj​\(xi​j\)−z¯j​\(us​j\),0\}\.d\_\{j\}^\{\(s\)\}\(x\_\{i\}\)=\\max\\\{\\underline\{z\}\_\{j\}\(\\ell\_\{sj\}\)\-z\_\{j\}\(x\_\{ij\}\),0\\\}\+\\max\\\{z\_\{j\}\(x\_\{ij\}\)\-\\overline\{z\}\_\{j\}\(u\_\{sj\}\),0\\\}\.
For categorical featuresj∈𝒥cat​\(s\)j\\in\\mathcal\{J\}\_\{\\mathrm\{cat\}\}\(s\), letci​jc\_\{ij\}denote the category of pointxix\_\{i\}on featurejj\. We define

dj\(s\)​\(xi\)=\{0,ci​j∈As​j,12,ci​j∉As​j\.d\_\{j\}^\{\(s\)\}\(x\_\{i\}\)=\\begin\{cases\}0,&c\_\{ij\}\\in A\_\{sj\},\\\\\[4\.0pt\] \\tfrac\{1\}\{2\},&c\_\{ij\}\\notin A\_\{sj\}\.\\end\{cases\}
This choice is consistent with treating a binary feature as continuous under the mid\-rank empirical CDF, where a mismatch incurs a quantile distance of12\\tfrac\{1\}\{2\}; we extend this to general categorical features\.

Unconstrained features \(i\.e\.,j∉𝒥num​\(s\)∪𝒥cat​\(s\)j\\notin\\mathcal\{J\}\_\{\\mathrm\{num\}\}\(s\)\\cup\\mathcal\{J\}\_\{\\mathrm\{cat\}\}\(s\)\) contribute zero distance as no value for them will change what leaf you are in\.

Using these distances, we convert eachdefer\_distT1:k\-1​\(xi\)\\textrm\{defer\\\_dist\}\_\{T\_\{\\textrm\{\{1:k\-1\}\}\}\}\(x\_\{i\}\)into a similarity score

\(1\+defer\_distT1:k\-1​\(xi\)\)−γ\.\(1\+\\textrm\{defer\\\_dist\}\_\{T\_\{\\textrm\{\{1:k\-1\}\}\}\}\(x\_\{i\}\)\)^\{\-\\gamma\}\.
Let𝒟k−1⊆𝒳\\mathcal\{D\}\_\{k\-1\}\\subseteq\\mathcal\{X\}denote the set of deferred points after stagek−1k\-1\. We define training weightswiw\_\{i\}for the next iteration \(on the first iteration, all weights are 1\)\.

wi=\{1,if​xi∈𝒟k−1\(1−μ\)​\(1\+defer\_distT1:k\-1​\(xi\)\)−γ,if​xi∉𝒟k−1w\_\{i\}\\;=\\;\\begin\{cases\}1,&\\text\{if \}x\_\{i\}\\in\\mathcal\{D\}\_\{k\-1\}\\\\\[6\.0pt\] \(1\-\\mu\)\\,\(1\+\\textrm\{defer\\\_dist\}\_\{T\_\{\\textrm\{\{1:k\-1\}\}\}\}\(x\_\{i\}\)\)^\{\-\\gamma\},&\\text\{if \}x\_\{i\}\\notin\\mathcal\{D\}\_\{k\-1\}\\end\{cases\}
Whenγ=0\\gamma=0, this reduces to assigning a uniform weight of1−μ1\-\\muto each non\-deferred point and a weight of11to each deferred point\.

## Appendix DFull Algorithm

### D\.1MDT Algorithm

Algorithm[12](https://arxiv.org/html/2606.30995#alg12)presents the full version of our algorithm\. There are two additions relative to the algorithm presented in the main paper\. The first is that we update the set of subregions𝒮\\mathcal\{S\}\(lines 4, 21, 22, 28\) and pass it into ourFilterSplitsandGetWeightsso it does not have to be recomputed from scratch each iteration\. The second is that we additionally support early termination of training if the model complexity becomes too large\. This is measured in 3 ways: \(i\) a stage of the tree has too many leaves, \(ii\) the sum of leaves across stages becomes too large, or \(iii\) the number of leaves in the naïve representation of an MDT as a single tree becomes too large\. \(iii\) takes advantage of a recurrence derived in Proposition[6](https://arxiv.org/html/2606.30995#Thmproposition6)\. Given that we have already computed that tree, we choose to add it to MDT anyway, stopping after that\.

Algorithm 12Top\-down MDT training with feasible\-region tracking0:Data

\(X,Xbinarized,y\)\(X,X\_\{\\mathrm\{binarized\}\},y\)with

X∈ℝN×pX\\in\\mathbb\{R\}^\{N\\times p\}and

Xbinarized∈\{0,1\}N×qX\_\{\\mathrm\{binarized\}\}\\in\\\{0,1\\\}^\{N\\times q\}, depth

dd,

τ\\tau,

η\\eta,

μ≥0\\mu\\geq 0, boolean flag

rescale​\_​tau\\mathrm\{rescale\\\_tau\}, maximum number of stages

KmaxK\_\{\\max\},

γ≥0\\gamma\\geq 0, optional budgets

Lstage,Ltotal,LexpandedL\_\{\\mathrm\{stage\}\},L\_\{\\mathrm\{total\}\},L\_\{\\mathrm\{expanded\}\}
0:MDT stages and fallback model

1:

B←FitFallbackModel​\(X,y,𝟏\)B\\leftarrow\\textsc\{FitFallbackModel\}\(X,y,\\mathbf\{1\}\)
2:

𝒯interp←\[\]\\mathcal\{T\}\_\{\\mathrm\{interp\}\}\\leftarrow\[\\ \]
3:

D←\{1,…,N\}D\\leftarrow\\\{1,\\dots,N\\\}
4:

𝒮←\{s∅\}\\mathcal\{S\}\\leftarrow\\\{s\_\{\\emptyset\}\\\}\{Initial unconstrained subregion\}

5:

Π←1\\Pi\\leftarrow 1\{Running product of deferral leaves\}

6:

G←1G\\leftarrow 1\{Expanded\-leaf count with fallback counted as one leaf\}

7:for

k=1,…,Kmaxk=1,\\dots,K\_\{\\max\}do

8:if

k=1k=1then

9:

Tk←FitDeferTree​\(Xbinarized,y,B​\(X\),𝟏,τ,η,d\)T\_\{k\}\\leftarrow\\textsc\{FitDeferTree\}\(X\_\{\\mathrm\{binarized\}\},y,B\(X\),\\mathbf\{1\},\\tau,\\eta,d\)
10:else

11:

Xfiltered←FilterSplits​\(Xbinarized,𝒮\)X\_\{\\mathrm\{filtered\}\}\\leftarrow\\textsc\{FilterSplits\}\(X\_\{\\mathrm\{binarized\}\},\\mathcal\{S\}\)
12:

w←GetWeights​\(X,D,𝒮,γ,μ\)w\\leftarrow\\textsc\{GetWeights\}\(X,D,\\mathcal\{S\},\\gamma,\\mu\)
13:

B←FitFallbackModel​\(X,y,w\)B\\leftarrow\\textsc\{FitFallbackModel\}\(X,y,w\)
14:

τk←τ⋅∑i=1NwiN\\tau\_\{k\}\\leftarrow\\tau\\cdot\\frac\{\\sum\_\{i=1\}^\{N\}w\_\{i\}\}\{N\}if

rescale​\_​tau\\mathrm\{rescale\\\_tau\}else

τ\\tau
15:

Tk←FitDeferTree​\(Xfiltered,y,B​\(X\),w,τk,η,d\)T\_\{k\}\\leftarrow\\textsc\{FitDeferTree\}\(X\_\{\\mathrm\{filtered\}\},y,B\(X\),w,\\tau\_\{k\},\\eta,d\)
16:endif

17:

𝒯interp←𝒯interp\+\[Tk\]\\mathcal\{T\}\_\{\\mathrm\{interp\}\}\\leftarrow\\mathcal\{T\}\_\{\\mathrm\{interp\}\}\+\[T\_\{k\}\]
18:

ℓk←NumLeaves​\(Tk\)\\ell\_\{k\}\\leftarrow\\textsc\{NumLeaves\}\(T\_\{k\}\)
19:

dk←NumDeferLeaves​\(Tk\)d\_\{k\}\\leftarrow\\textsc\{NumDeferLeaves\}\(T\_\{k\}\)
20:

Dnew←\{i∈D:Tk​\(xi\)=defer\}D\_\{\\mathrm\{new\}\}\\leftarrow\\\{i\\in D:T\_\{k\}\(x\_\{i\}\)=\\texttt\{defer\}\\\}
21:

𝒫←CollectPathsToAction​\(Tk,defer\)\\mathcal\{P\}\\leftarrow\\textsc\{CollectPathsToAction\}\(T\_\{k\},\\texttt\{defer\}\)
22:

𝒮new←ExtendSubregionsWithFeasiblePaths​\(𝒮,𝒫\)\\mathcal\{S\}\_\{\\mathrm\{new\}\}\\leftarrow\\textsc\{ExtendSubregionsWithFeasiblePaths\}\(\\mathcal\{S\},\\mathcal\{P\}\)
23:

\(should\_stop,G,Π\)←ShouldStopTraining​\(D,Dnew,ℓk,dk,𝒯interp,G,Π,Lstage,Ltotal,Lexpanded\)\(\\texttt\{should\\\_stop\},G,\\Pi\)\\leftarrow\\textsc\{ShouldStopTraining\}\(D,D\_\{\\mathrm\{new\}\},\\ell\_\{k\},d\_\{k\},\\mathcal\{T\}\_\{\\mathrm\{interp\}\},G,\\Pi,L\_\{\\mathrm\{stage\}\},L\_\{\\mathrm\{total\}\},L\_\{\\mathrm\{expanded\}\}\)
24:ifshould\_stopthen

25:break

26:endif

27:

D←DnewD\\leftarrow D\_\{\\mathrm\{new\}\}
28:

𝒮←𝒮new\\mathcal\{S\}\\leftarrow\\mathcal\{S\}\_\{\\mathrm\{new\}\}
29:endfor

30:if

D≠∅D\\neq\\varnothingthen

31:

w←GetWeights​\(X,D,𝒮,γ,μ\)w\\leftarrow\\textsc\{GetWeights\}\(X,D,\\mathcal\{S\},\\gamma,\\mu\)
32:

B←FitFallbackModel​\(X,y,w\)B\\leftarrow\\textsc\{FitFallbackModel\}\(X,y,w\)
33:endif

34:return

𝒯interp\+\[B\]\\mathcal\{T\}\_\{\\mathrm\{interp\}\}\+\[B\]

Algorithm[13](https://arxiv.org/html/2606.30995#alg13)includes the aforementioned stopping criteria\. It terminates training if the deferred set becomes empty, fails to shrink, or if any complexity budget is exceeded\. The expanded tree size is tracked online using a recurrence, allowing early stopping without constructing a single tree representation\.

Algorithm 13ShouldStopTraining\(D,Dnew,ℓk,dk,𝒯interp,G,Π,Lstage,Ltotal,Lexpanded\)\(D,D\_\{\\mathrm\{new\}\},\\ell\_\{k\},d\_\{k\},\\mathcal\{T\}\_\{\\mathrm\{interp\}\},G,\\Pi,L\_\{\\mathrm\{stage\}\},L\_\{\\mathrm\{total\}\},L\_\{\\mathrm\{expanded\}\}\)0:Previous deferred set

DD, new deferred set

DnewD\_\{\\mathrm\{new\}\}, current tree leaf count

ℓk\\ell\_\{k\}, current defer\-leaf count

dkd\_\{k\}, current stage list

𝒯interp\\mathcal\{T\}\_\{\\mathrm\{interp\}\}, running expanded count

GG, running defer\-product

Π\\Pi, optional budgets

Lstage,Ltotal,LexpandedL\_\{\\mathrm\{stage\}\},L\_\{\\mathrm\{total\}\},L\_\{\\mathrm\{expanded\}\}
0:Booleanshould\_stop, updated

GG, updated

Π\\Pi
1:if

Dnew=∅D\_\{\\mathrm\{new\}\}=\\varnothingthen

2:return

\(true,G,Π\)\(\\textbf\{true\},G,\\Pi\)\{No points remain deferred\}

3:endif

4:if

Dnew=DD\_\{\\mathrm\{new\}\}=Dthen

5:return

\(true,G,Π\)\(\\textbf\{true\},G,\\Pi\)\{Deferred set did not shrink\}

6:endif

7:if

LexpandedL\_\{\\mathrm\{expanded\}\}is specifiedthen

8:

G←G\+Π​\(ℓk−1\)G\\leftarrow G\+\\Pi\(\\ell\_\{k\}\-1\)
9:

Π←Π​dk\\Pi\\leftarrow\\Pi d\_\{k\}
10:endif

11:if

LstageL\_\{\\mathrm\{stage\}\}is specified and

ℓk\>Lstage\\ell\_\{k\}\>L\_\{\\mathrm\{stage\}\}then

12:return

\(true,G,Π\)\(\\textbf\{true\},G,\\Pi\)\{Current stage exceeds per\-tree budget\}

13:endif

14:if

LtotalL\_\{\\mathrm\{total\}\}is specified and

∑T∈𝒯interp\|T\|\>Ltotal\\sum\_\{T\\in\\mathcal\{T\}\_\{\\mathrm\{interp\}\}\}\|T\|\>L\_\{\\mathrm\{total\}\}then

15:return

\(true,G,Π\)\(\\textbf\{true\},G,\\Pi\)\{Sequential model exceeds total leaf budget\}

16:endif

17:if

LexpandedL\_\{\\mathrm\{expanded\}\}is specified and

G\>LexpandedG\>L\_\{\\mathrm\{expanded\}\}then

18:return

\(true,G,Π\)\(\\textbf\{true\},G,\\Pi\)\{Expanded single\-tree representation exceeds budget\}

19:endif

20:return

\(false,G,Π\)\(\\textbf\{false\},G,\\Pi\)

Algorithm[14](https://arxiv.org/html/2606.30995#alg14)removes binary features that do not distinguish between feasible deferred subregions\. A feature is discarded if it is provably always true or always false across all subregions \(note that we can’t discard a feature if it is provably true on half of the subregions and provably false on the others\)\. This has the added bonus of reducing the search space, which is beneficial for near\-optimal decision tree algorithms\. We implement this by storing, for each column, a string representation of the split \(e\.g\.,age<=25\), which we parse to recover the feature and threshold\. The column itself in the binarized dataset includes which samples satisfy the split\.

Algorithm 14FilterSplits\(Xbinarized,𝒮\)\(X\_\{\\mathrm\{binarized\}\},\\mathcal\{S\}\)0:Binarized feature matrix

XbinarizedX\_\{\\mathrm\{binarized\}\}, feasible deferred subregions

𝒮\\mathcal\{S\}
0:Filtered binarized feature matrix

1:

I←\[\]I\\leftarrow\[\\ \]
2:for

j=1,…,qj=1,\\dots,qdo

3:Get the split

\(f≤ν\)\(f\\leq\\nu\)from the metadata associated with column

jj
4:

all\_true←true\\texttt\{all\\\_true\}\\leftarrow\\textbf\{true\}
5:

all\_false←true\\texttt\{all\\\_false\}\\leftarrow\\textbf\{true\}
6:for all

s∈𝒮s\\in\\mathcal\{S\}do

7:ifnot

ImpliesTrue​\(s,f,ν\)\\textsc\{ImpliesTrue\}\(s,f,\\nu\)then

8:

all\_true←false\\texttt\{all\\\_true\}\\leftarrow\\textbf\{false\}
9:endif

10:ifnot

ImpliesFalse​\(s,f,ν\)\\textsc\{ImpliesFalse\}\(s,f,\\nu\)then

11:

all\_false←false\\texttt\{all\\\_false\}\\leftarrow\\textbf\{false\}
12:endif

13:endfor

14:ifnotall\_trueand notall\_falsethen

15:append

jjto

II
16:endif

17:endfor

18:return

Xbinarized​\[:,I\]X\_\{\\mathrm\{binarized\}\}\[:,I\]

Algorithm[15](https://arxiv.org/html/2606.30995#alg15)assigns weights based on distance to the deferred region\. Deferred points receive full weight, while non\-deferred points are down\-weighted according to their proximity to the nearest feasible subregion\. This emphasizes points near the deferral boundary during training\.

Algorithm 15GetWeights\(X,D,𝒮,γ,μ\)\(X,D,\\mathcal\{S\},\\gamma,\\mu\)0:Data

XX, current deferred index set

DD, feasible deferred subregions

𝒮\\mathcal\{S\}, decay parameter

γ\\gamma, non\-deferred downweighting parameter

μ\\mu
0:Weight vector

w∈ℝ≥0Nw\\in\\mathbb\{R\}\_\{\\geq 0\}^\{N\}
1:for

i=1,…,Ni=1,\\dots,Ndo

2:if

i∈Di\\in Dthen

3:

wi←1w\_\{i\}\\leftarrow 1
4:else

5:

Δi←mins∈𝒮⁡DistanceToSubregion​\(xi,s\)\\Delta\_\{i\}\\leftarrow\\min\_\{s\\in\\mathcal\{S\}\}\\textsc\{DistanceToSubregion\}\(x\_\{i\},s\)
6:

wi←\(1−μ\)​\(1\+Δi\)−γw\_\{i\}\\leftarrow\(1\-\\mu\)\(1\+\\Delta\_\{i\}\)^\{\-\\gamma\}
7:endif

8:endfor

9:return

ww

Algorithm[16](https://arxiv.org/html/2606.30995#alg16)computes the distance from a point to a subregion by summing per\-feature deviations\. Numerical features are measured in quantile space, while categorical features incur a fixed penalty of12\\frac\{1\}\{2\}if the subregion does not allow the category that the point is in \(i\.e, the path to the subregion took a split of false on that category\)\. Unconstrained features contribute zero\.

Algorithm 16DistanceToSubregion\(xi,s\)\(x\_\{i\},s\)0:Point

xix\_\{i\}, feasible subregion

ss
0:Distance from

xix\_\{i\}to

ss
1:

Δ←0\\Delta\\leftarrow 0
2:for allnumerical or ordinal features

j∈𝒥num​\(s\)j\\in\\mathcal\{J\}\_\{\\mathrm\{num\}\}\(s\)do

3:Let

\(ℓs​j,us​j\]\(\\ell\_\{sj\},u\_\{sj\}\]be the interval for feature

jjin

ss
4:

Δ←Δ\+max⁡\{z¯j​\(ℓs​j\)−zj​\(xi​j\),0\}\+max⁡\{zj​\(xi​j\)−z¯j​\(us​j\),0\}\\Delta\\leftarrow\\Delta\+\\max\\\{\\underline\{z\}\_\{j\}\(\\ell\_\{sj\}\)\-z\_\{j\}\(x\_\{ij\}\),0\\\}\+\\max\\\{z\_\{j\}\(x\_\{ij\}\)\-\\overline\{z\}\_\{j\}\(u\_\{sj\}\),0\\\}
5:endfor

6:for allcategorical groups

j∈𝒥cat​\(s\)j\\in\\mathcal\{J\}\_\{\\mathrm\{cat\}\}\(s\)do

7:Let

As​jA\_\{sj\}be the set of categories allowed by

ss
8:Let

ci​jc\_\{ij\}be the category of

xix\_\{i\}in group

jj
9:if

ci​j∉As​jc\_\{ij\}\\notin A\_\{sj\}then

10:

Δ←Δ\+12\\Delta\\leftarrow\\Delta\+\\frac\{1\}\{2\}
11:endif

12:endfor

13:return

Δ\\Delta

### D\.2Defer Tree Algorithm

In Algorithm[17](https://arxiv.org/html/2606.30995#alg17)construct each defer tree using a recursive, top\-down procedure that jointly optimizes over prediction and deferral decisions\. This algorithm uses the same heuristics to select splits as are used in the LicketySPLIT algorithm of\[[3](https://arxiv.org/html/2606.30995#bib.bib37)\]\. Our implementation extends the efficient C\+\+ codebase ofHeileet al\.\[[28](https://arxiv.org/html/2606.30995#bib.bib112)\], which implements a modified version of LicketySPLIT\. Their algorithm considers an unweighted dataset and builds standard decision trees \(without deferral\)\. Our changes lie in supporting weights and deferral, thus optimizing a different objective\. We solve the optimization problem using a per\-leaf penalty, which is equivalent to optimizing a per\-split penalty, since the number of leaves in a decision tree is always exactly one more than the number of splits, differing only by an additive constantτ\\tau\.

At any node, we consider three possible leaf actions: predicting class0, predicting class11, or deferring to the fallback model\. Each action is assigned an objective value that combines a fixed leaf penaltyτ\\tauwith a weighted misclassification cost\.

At a high level, we will recursively consider every possible split\. We query a greedy method to build a subtree on the left and right child of every split, and choose the split that minimizes our objective under greedy completions\. After choosing this split, we recurse on the left and right children of this split, and repeat\.

Algorithm 17FitDeferTree\(Xbinarized,y,r,w,τ,η,d\)\(X\_\{\\mathrm\{binarized\}\},y,r,w,\\tau,\\eta,d\)0:Binarized data

XbinarizedX\_\{\\mathrm\{binarized\}\}, labels

yy, fallback predictions

rr, weights

ww, leaf penalty

τ\\tau, defer penalty

η\\eta, depth budget

dd
0:A defer tree

TT
1:

A←\{1,…,N\}A\\leftarrow\\\{1,\\dots,N\\\}
2:

\(T,C\)←BuildDeferTree​\(A,d\)\(T,C\)\\leftarrow\\textsc\{BuildDeferTree\}\(A,d\)
3:return

TT

Algorithm 18BuildDeferTree\(A,d\)\(A,d\)0:Index set

AA, remaining depth

dd
0:A pair

\(T,C\)\(T,C\), where

TTis a defer subtree on

AAand

CCis its objective value

1:

WA←∑i∈AwiW\_\{A\}\\leftarrow\\sum\_\{i\\in A\}w\_\{i\}
2:

C0←τ\+∑i∈Awi​𝟏​\{yi=1\}C\_\{0\}\\leftarrow\\tau\+\\sum\_\{i\\in A\}w\_\{i\}\\mathbf\{1\}\\\{y\_\{i\}=1\\\}
3:

C1←τ\+∑i∈Awi​𝟏​\{yi=0\}C\_\{1\}\\leftarrow\\tau\+\\sum\_\{i\\in A\}w\_\{i\}\\mathbf\{1\}\\\{y\_\{i\}=0\\\}
4:

Cdefer←τ\+∑i∈Awi​𝟏​\{ri≠yi\}\+η​WAC\_\{\\mathrm\{defer\}\}\\leftarrow\\tau\+\\sum\_\{i\\in A\}w\_\{i\}\\mathbf\{1\}\\\{r\_\{i\}\\neq y\_\{i\}\\\}\+\\eta W\_\{A\}
5:

\(Cleaf,aleaf\)←min⁡\{\(C0,0\),\(C1,1\),\(Cdefer,defer\)\}\(C\_\{\\mathrm\{leaf\}\},a\_\{\\mathrm\{leaf\}\}\)\\leftarrow\\min\\\{\(C\_\{0\},0\),\(C\_\{1\},1\),\(C\_\{\\mathrm\{defer\}\},\\texttt\{defer\}\)\\\}
6:if

d=0d=0or

\|A\|≤1\|A\|\\leq 1then

7:return

\(leaf with action​aleaf,Cleaf\)\(\\text\{leaf with action \}a\_\{\\mathrm\{leaf\}\},C\_\{\\mathrm\{leaf\}\}\)
8:endif

9:

f⋆←⊥f^\{\\star\}\\leftarrow\\bot
10:

C⋆←∞C^\{\\star\}\\leftarrow\\infty
11:for

f=1,…,qf=1,\\dots,qdo

12:

AL←\{i∈A:Xbinarized,i​f=1\}A\_\{L\}\\leftarrow\\\{i\\in A:X\_\{\\mathrm\{binarized\},if\}=1\\\}
13:

AR←\{i∈A:Xbinarized,i​f=0\}A\_\{R\}\\leftarrow\\\{i\\in A:X\_\{\\mathrm\{binarized\},if\}=0\\\}
14:if

AL=∅A\_\{L\}=\\varnothingor

AR=∅A\_\{R\}=\\varnothingthen

15:continue

16:endif

17:

\(T~L,C~L\)←Greedy​\(AL,d−1\)\(\\widetilde\{T\}\_\{L\},\\widetilde\{C\}\_\{L\}\)\\leftarrow\\textsc\{Greedy\}\(A\_\{L\},d\-1\)
18:

\(T~R,C~R\)←Greedy​\(AR,d−1\)\(\\widetilde\{T\}\_\{R\},\\widetilde\{C\}\_\{R\}\)\\leftarrow\\textsc\{Greedy\}\(A\_\{R\},d\-1\)
19:

Cf←C~L\+C~RC\_\{f\}\\leftarrow\\widetilde\{C\}\_\{L\}\+\\widetilde\{C\}\_\{R\}
20:if

Cf<C⋆C\_\{f\}<C^\{\\star\}then

21:

C⋆←CfC^\{\\star\}\\leftarrow C\_\{f\}
22:

f⋆←ff^\{\\star\}\\leftarrow f
23:endif

24:endfor

25:if

f⋆=⊥f^\{\\star\}=\\botthen

26:return

\(leaf with action​aleaf,Cleaf\)\(\\text\{leaf with action \}a\_\{\\mathrm\{leaf\}\},C\_\{\\mathrm\{leaf\}\}\)
27:endif

28:

AL⋆←\{i∈A:Xbinarized,i​f⋆=1\}A\_\{L\}^\{\\star\}\\leftarrow\\\{i\\in A:X\_\{\\mathrm\{binarized\},if^\{\\star\}\}=1\\\}
29:

AR⋆←\{i∈A:Xbinarized,i​f⋆=0\}A\_\{R\}^\{\\star\}\\leftarrow\\\{i\\in A:X\_\{\\mathrm\{binarized\},if^\{\\star\}\}=0\\\}
30:

\(TL,CL\)←BuildDeferTree​\(AL⋆,d−1\)\(T\_\{L\},C\_\{L\}\)\\leftarrow\\textsc\{BuildDeferTree\}\(A\_\{L\}^\{\\star\},d\-1\)
31:

\(TR,CR\)←BuildDeferTree​\(AR⋆,d−1\)\(T\_\{R\},C\_\{R\}\)\\leftarrow\\textsc\{BuildDeferTree\}\(A\_\{R\}^\{\\star\},d\-1\)
32:

Csplit←CL\+CRC\_\{\\mathrm\{split\}\}\\leftarrow C\_\{L\}\+C\_\{R\}
33:if

Cleaf≤CsplitC\_\{\\mathrm\{leaf\}\}\\leq C\_\{\\mathrm\{split\}\}then

34:return

\(leaf with action​aleaf,Cleaf\)\(\\text\{leaf with action \}a\_\{\\mathrm\{leaf\}\},C\_\{\\mathrm\{leaf\}\}\)
35:endif

36:Get the non\-binarized feature

forigf\_\{\\mathrm\{orig\}\}and threshold

ν\\nu\(in

≤ν\\leq\\nu\) from the metadata of column

f⋆f^\{\\star\}
37:

T←T\\leftarrowinternal node with

T\.feature=forigT\.\\texttt\{feature\}=f\_\{\\mathrm\{orig\}\},

T\.threshold=νT\.\\texttt\{threshold\}=\\nu, left child

TLT\_\{L\}, and right child

TRT\_\{R\}
38:return

\(T,Csplit\)\(T,C\_\{\\mathrm\{split\}\}\)

The greedy subroutine \(Algorithm[19](https://arxiv.org/html/2606.30995#alg19)\) follows a very similar structure: it considers all splits and chooses the one that minimizes the weighted label entropy of the resulting partition \(we minimize this quantity in Algorithm[20](https://arxiv.org/html/2606.30995#alg20)\)\.

Algorithm 19Greedy\(A,d\)\(A,d\)0:Index set

AA, remaining depth

dd
0:A pair

\(T,C\)\(T,C\), where

TTis a greedy defer subtree on

AAand

CCis its objective value

1:

WA←∑i∈AwiW\_\{A\}\\leftarrow\\sum\_\{i\\in A\}w\_\{i\}
2:

C0←τ\+∑i∈Awi​𝟏​\{yi=1\}C\_\{0\}\\leftarrow\\tau\+\\sum\_\{i\\in A\}w\_\{i\}\\mathbf\{1\}\\\{y\_\{i\}=1\\\}
3:

C1←τ\+∑i∈Awi​𝟏​\{yi=0\}C\_\{1\}\\leftarrow\\tau\+\\sum\_\{i\\in A\}w\_\{i\}\\mathbf\{1\}\\\{y\_\{i\}=0\\\}
4:

Cdefer←τ\+∑i∈Awi​𝟏​\{ri≠yi\}\+η​WAC\_\{\\mathrm\{defer\}\}\\leftarrow\\tau\+\\sum\_\{i\\in A\}w\_\{i\}\\mathbf\{1\}\\\{r\_\{i\}\\neq y\_\{i\}\\\}\+\\eta W\_\{A\}
5:

\(Cleaf,aleaf\)←min⁡\{\(C0,0\),\(C1,1\),\(Cdefer,defer\)\}\(C\_\{\\mathrm\{leaf\}\},a\_\{\\mathrm\{leaf\}\}\)\\leftarrow\\min\\\{\(C\_\{0\},0\),\(C\_\{1\},1\),\(C\_\{\\mathrm\{defer\}\},\\texttt\{defer\}\)\\\}
6:if

d=0d=0or

\|A\|≤1\|A\|\\leq 1then

7:return

\(leaf with action​aleaf,Cleaf\)\(\\text\{leaf with action \}a\_\{\\mathrm\{leaf\}\},C\_\{\\mathrm\{leaf\}\}\)
8:endif

9:

f⋆←BestEntropySplit​\(A\)f^\{\\star\}\\leftarrow\\textsc\{BestEntropySplit\}\(A\)
10:if

f⋆=⊥f^\{\\star\}=\\botthen

11:return

\(leaf with action​aleaf,Cleaf\)\(\\text\{leaf with action \}a\_\{\\mathrm\{leaf\}\},C\_\{\\mathrm\{leaf\}\}\)
12:endif

13:

AL⋆←\{i∈A:Xbinarized,i​f⋆=1\}A\_\{L\}^\{\\star\}\\leftarrow\\\{i\\in A:X\_\{\\mathrm\{binarized\},if^\{\\star\}\}=1\\\}
14:

AR⋆←\{i∈A:Xbinarized,i​f⋆=0\}A\_\{R\}^\{\\star\}\\leftarrow\\\{i\\in A:X\_\{\\mathrm\{binarized\},if^\{\\star\}\}=0\\\}
15:if

AL⋆=∅A\_\{L\}^\{\\star\}=\\varnothingor

AR⋆=∅A\_\{R\}^\{\\star\}=\\varnothingthen

16:return

\(leaf with action​aleaf,Cleaf\)\(\\text\{leaf with action \}a\_\{\\mathrm\{leaf\}\},C\_\{\\mathrm\{leaf\}\}\)
17:endif

18:

\(TL,CL\)←Greedy​\(AL⋆,d−1\)\(T\_\{L\},C\_\{L\}\)\\leftarrow\\textsc\{Greedy\}\(A\_\{L\}^\{\\star\},d\-1\)
19:

\(TR,CR\)←Greedy​\(AR⋆,d−1\)\(T\_\{R\},C\_\{R\}\)\\leftarrow\\textsc\{Greedy\}\(A\_\{R\}^\{\\star\},d\-1\)
20:

Csplit←CL\+CRC\_\{\\mathrm\{split\}\}\\leftarrow C\_\{L\}\+C\_\{R\}
21:if

Cleaf≤CsplitC\_\{\\mathrm\{leaf\}\}\\leq C\_\{\\mathrm\{split\}\}then

22:return

\(leaf with action​aleaf,Cleaf\)\(\\text\{leaf with action \}a\_\{\\mathrm\{leaf\}\},C\_\{\\mathrm\{leaf\}\}\)
23:endif

24:

T←T\\leftarrowinternal node splitting on

Xbinarized,f⋆=1X\_\{\\mathrm\{binarized\},f^\{\\star\}\}=1, with left child

TLT\_\{L\}and right child

TRT\_\{R\}
25:return

\(T,Csplit\)\(T,C\_\{\\mathrm\{split\}\}\)

Algorithm[20](https://arxiv.org/html/2606.30995#alg20)selects splits by minimizing the weighted label entropy of the resulting partition\. This focuses on separating the labels rather than directly optimizing the defer\-aware objective\. As this is the standard heuristic in greedy decision tree algorithms, we adopt it here\.

Algorithm 20BestEntropySplit\(A\)\(A\)0:Index set

AA
0:Feature index

f⋆f^\{\\star\}minimizing weighted entropy \(or

⊥\\botif none valid\)

1:

f⋆←⊥f^\{\\star\}\\leftarrow\\bot
2:

H⋆←∞H^\{\\star\}\\leftarrow\\infty
3:for

f=1,…,qf=1,\\dots,qdo

4:

AL←\{i∈A:Xbinarized,i​f=1\}A\_\{L\}\\leftarrow\\\{i\\in A:X\_\{\\mathrm\{binarized\},if\}=1\\\}
5:

AR←\{i∈A:Xbinarized,i​f=0\}A\_\{R\}\\leftarrow\\\{i\\in A:X\_\{\\mathrm\{binarized\},if\}=0\\\}
6:if

AL=∅A\_\{L\}=\\varnothingor

AR=∅A\_\{R\}=\\varnothingthen

7:continue

8:endif

9:

WL←∑i∈ALwiW\_\{L\}\\leftarrow\\sum\_\{i\\in A\_\{L\}\}w\_\{i\}
10:

WR←∑i∈ARwiW\_\{R\}\\leftarrow\\sum\_\{i\\in A\_\{R\}\}w\_\{i\}
11:

W←WL\+WRW\\leftarrow W\_\{L\}\+W\_\{R\}
12:if

W=0W=0then

13:continue

14:endif

15:

pL←\{∑i∈ALwi​yiWL,WL\>00,otherwisep\_\{L\}\\leftarrow\\begin\{cases\}\\dfrac\{\\sum\_\{i\\in A\_\{L\}\}w\_\{i\}y\_\{i\}\}\{W\_\{L\}\},&W\_\{L\}\>0\\\\ 0,&\\text\{otherwise\}\\end\{cases\}
16:

pR←\{∑i∈ARwi​yiWR,WR\>00,otherwisep\_\{R\}\\leftarrow\\begin\{cases\}\\dfrac\{\\sum\_\{i\\in A\_\{R\}\}w\_\{i\}y\_\{i\}\}\{W\_\{R\}\},&W\_\{R\}\>0\\\\ 0,&\\text\{otherwise\}\\end\{cases\}
17:

HL←\{−pL​log⁡pL−\(1−pL\)​log⁡\(1−pL\),pL∈\(0,1\)0,otherwiseH\_\{L\}\\leftarrow\\begin\{cases\}\-p\_\{L\}\\log p\_\{L\}\-\(1\-p\_\{L\}\)\\log\(1\-p\_\{L\}\),&p\_\{L\}\\in\(0,1\)\\\\ 0,&\\text\{otherwise\}\\end\{cases\}
18:

HR←\{−pR​log⁡pR−\(1−pR\)​log⁡\(1−pR\),pR∈\(0,1\)0,otherwiseH\_\{R\}\\leftarrow\\begin\{cases\}\-p\_\{R\}\\log p\_\{R\}\-\(1\-p\_\{R\}\)\\log\(1\-p\_\{R\}\),&p\_\{R\}\\in\(0,1\)\\\\ 0,&\\text\{otherwise\}\\end\{cases\}
19:

Hf←WLW​HL\+WRW​HRH\_\{f\}\\leftarrow\\dfrac\{W\_\{L\}\}\{W\}H\_\{L\}\+\\dfrac\{W\_\{R\}\}\{W\}H\_\{R\}
20:if

Hf<H⋆H\_\{f\}<H^\{\\star\}then

21:

H⋆←HfH^\{\\star\}\\leftarrow H\_\{f\}
22:

f⋆←ff^\{\\star\}\\leftarrow f
23:endif

24:endfor

25:return

f⋆f^\{\\star\}

### D\.3Improving Optimization with Backfitting

The MDT training procedure constructs the model as a sequence of defer trees that are trained with respect to a temporary black box fallback model \(Algorithms[1](https://arxiv.org/html/2606.30995#alg1)and[12](https://arxiv.org/html/2606.30995#alg12)\)\. At the first stage, we trainT1T\_\{1\}to either predict or defer to an initial fallback modelB1B\_\{1\}\. After this stage identifies a remaining deferred region, we reweight the data toward that region, train a new fallbackB2B\_\{2\}, and then trainT2T\_\{2\}to either predict or defer toB2B\_\{2\}\. Continuing this process, we trainTiT\_\{i\}to defer toBiB\_\{i\}, but in the final model,TiT\_\{i\}does not necessarily defer toBiB\_\{i\}\. For instance, if there are 4 trees in the MDT,T1T\_\{1\}defers to another MDT, not a black box\.

Therefore, once full MDT has been constructed, it may be beneficial to retrain stagejjto defer to the entire suffixTj\+1:K;BT\_\{j\+1:K\};B\. This motivates the following procedure: choose a component of the MDT, hold the rest of the model fixed, and retrain that component against the suffix that follows it\. As we are optimizing using near\-optimal algorithms, it will also be helpful to have an acceptance step to accept the new defer tree only if it is better in the objective that the algorithm tried to optimize\.

The backward pass \(Algorithm[21](https://arxiv.org/html/2606.30995#alg21)\) starts from the final fallback model and moves upstream through the MDT, retraining each stage conditioned on the rest of it\. We then visit stages in reverse order \(optionally starting with the fallback model\) doing exactly that\. In contrast, the forward pass \(Algorithm[22](https://arxiv.org/html/2606.30995#alg22)\) does exactly the same thing but it starts from the first stage\. We put these together in an alternating approach \(Algorithm[23](https://arxiv.org/html/2606.30995#alg23)\)\. It combines these two sweeps in the following update order:B,TK,TK−1,…,T1,T2,T3,…,TK,…B,\\ T\_\{K\},T\_\{K\-1\},\\ldots,T\_\{1\},\\ T\_\{2\},T\_\{3\},\\ldots,T\_\{K\},\\ldots\. The results of using this approach are shown in[Figure 14](https://arxiv.org/html/2606.30995#A7.F14)\. In short, backfitting gives clear improvements on some datasets, such as Tictactoe, where revisiting stages may help capture higher\-order interactions, but it degrades performance on several others\.

Algorithm 21BackwardPass: Backfitting MDT stages in reverse order0:Data

\(X,Xbinarized,y\)\(X,X\_\{\\mathrm\{binarized\}\},y\), MDT stages

𝒯interp=\[T1,…,TK\]\\mathcal\{T\}\_\{\\mathrm\{interp\}\}=\[T\_\{1\},\\dots,T\_\{K\}\], fallback model

BB, depth

dd,

τ\\tau,

η\\eta,

μ≥0\\mu\\geq 0,

γ≥0\\gamma\\geq 0, boolean flag

rescale​\_​tau\\mathrm\{rescale\\\_tau\}, endpoints

jstartj\_\{\\mathrm\{start\}\}and

jendj\_\{\\mathrm\{end\}\}
0:Updated MDT stages and fallback model

1:for

j=jstart,jstart−1,…,jendj=j\_\{\\mathrm\{start\}\},j\_\{\\mathrm\{start\}\}\-1,\\dots,j\_\{\\mathrm\{end\}\}do

2:

Dj−1←\{i:T1​\(xi\)=⋯=Tj−1​\(xi\)=defer\}D\_\{j\-1\}\\leftarrow\\\{i:T\_\{1\}\(x\_\{i\}\)=\\cdots=T\_\{j\-1\}\(x\_\{i\}\)=\\texttt\{defer\}\\\}
3:

𝒮j−1←GetDeferredSubregions​\(T1:j−1\)\\mathcal\{S\}\_\{j\-1\}\\leftarrow\\textsc\{GetDeferredSubregions\}\(T\_\{1:j\-1\}\)
4:

w←GetWeights​\(X,Dj−1,𝒮j−1,γ,μ,T1:j−1\)w\\leftarrow\\textsc\{GetWeights\}\(X,D\_\{j\-1\},\\mathcal\{S\}\_\{j\-1\},\\gamma,\\mu,T\_\{1:j\-1\}\)
5:

y^suffix←y^Tj\+1:K,B​\(X\)\\widehat\{y\}^\{\\mathrm\{suffix\}\}\\leftarrow\\widehat\{y\}\_\{T\_\{j\+1:K\},B\}\(X\)
6:

τj←τ⋅∑i=1NwiN\\tau\_\{j\}\\leftarrow\\tau\\cdot\\frac\{\\sum\_\{i=1\}^\{N\}w\_\{i\}\}\{N\}if

rescale​\_​tau\\mathrm\{rescale\\\_tau\}else

τ\\tau
7:

Xfiltered←FilterSplits​\(Xbinarized,𝒮j−1\)X\_\{\\mathrm\{filtered\}\}\\leftarrow\\textsc\{FilterSplits\}\(X\_\{\\mathrm\{binarized\}\},\\mathcal\{S\}\_\{j\-1\}\)
8:

T~j←FitDeferTree​\(Xfiltered,y,y^suffix,w,τj,η,d\)\\widetilde\{T\}\_\{j\}\\leftarrow\\textsc\{FitDeferTree\}\(X\_\{\\mathrm\{filtered\}\},y,\\widehat\{y\}^\{\\mathrm\{suffix\}\},w,\\tau\_\{j\},\\eta,d\)
9:

Lold←LTj,Tj\+1:K;B​\(Dw,τj,η\)L\_\{\\mathrm\{old\}\}\\leftarrow L\_\{T\_\{j\},T\_\{j\+1:K\};B\}\(D^\{w\},\\tau\_\{j\},\\eta\)
10:

Lnew←LT~j,Tj\+1:K;B​\(Dw,τj,η\)L\_\{\\mathrm\{new\}\}\\leftarrow L\_\{\\widetilde\{T\}\_\{j\},T\_\{j\+1:K\};B\}\(D^\{w\},\\tau\_\{j\},\\eta\)
11:if

Lnew≤LoldL\_\{\\mathrm\{new\}\}\\leq L\_\{\\mathrm\{old\}\}then

12:

Tj←T~jT\_\{j\}\\leftarrow\\widetilde\{T\}\_\{j\}
13:endif

14:endfor

15:return

\[T1,…,TK\]\+\[B\]\[T\_\{1\},\\dots,T\_\{K\}\]\+\[B\]

Algorithm 22ForwardPass: Backfitting MDT stages in forward order0:Data

\(X,Xbinarized,y\)\(X,X\_\{\\mathrm\{binarized\}\},y\), MDT stages

𝒯interp=\[T1,…,TK\]\\mathcal\{T\}\_\{\\mathrm\{interp\}\}=\[T\_\{1\},\\dots,T\_\{K\}\], fallback model

BB, depth

dd,

τ\\tau,

η\\eta,

μ≥0\\mu\\geq 0,

γ≥0\\gamma\\geq 0, boolean flag

rescale​\_​tau\\mathrm\{rescale\\\_tau\}, endpoints

jstartj\_\{\\mathrm\{start\}\}and

jendj\_\{\\mathrm\{end\}\}
0:Updated MDT stages and fallback model

1:for

j=jstart,jstart\+1,…,jendj=j\_\{\\mathrm\{start\}\},j\_\{\\mathrm\{start\}\}\+1,\\dots,j\_\{\\mathrm\{end\}\}do

2:

Dj−1←\{i:T1​\(xi\)=⋯=Tj−1​\(xi\)=defer\}D\_\{j\-1\}\\leftarrow\\\{i:T\_\{1\}\(x\_\{i\}\)=\\cdots=T\_\{j\-1\}\(x\_\{i\}\)=\\texttt\{defer\}\\\}
3:

𝒮j−1←GetDeferredSubregions​\(T1:j−1\)\\mathcal\{S\}\_\{j\-1\}\\leftarrow\\textsc\{GetDeferredSubregions\}\(T\_\{1:j\-1\}\)
4:

w←GetWeights​\(X,Dj−1,𝒮j−1,γ,μ,T1:j−1\)w\\leftarrow\\textsc\{GetWeights\}\(X,D\_\{j\-1\},\\mathcal\{S\}\_\{j\-1\},\\gamma,\\mu,T\_\{1:j\-1\}\)
5:

y^suffix←y^Tj\+1:K,B​\(X\)\\widehat\{y\}^\{\\mathrm\{suffix\}\}\\leftarrow\\widehat\{y\}\_\{T\_\{j\+1:K\},B\}\(X\)
6:

τj←τ⋅∑i=1NwiN\\tau\_\{j\}\\leftarrow\\tau\\cdot\\frac\{\\sum\_\{i=1\}^\{N\}w\_\{i\}\}\{N\}if

rescale​\_​tau\\mathrm\{rescale\\\_tau\}else

τ\\tau
7:

Xfiltered←FilterSplits​\(Xbinarized,𝒮j−1\)X\_\{\\mathrm\{filtered\}\}\\leftarrow\\textsc\{FilterSplits\}\(X\_\{\\mathrm\{binarized\}\},\\mathcal\{S\}\_\{j\-1\}\)
8:

T~j←FitDeferTree​\(Xfiltered,y,y^suffix,w,τj,η,d\)\\widetilde\{T\}\_\{j\}\\leftarrow\\textsc\{FitDeferTree\}\(X\_\{\\mathrm\{filtered\}\},y,\\widehat\{y\}^\{\\mathrm\{suffix\}\},w,\\tau\_\{j\},\\eta,d\)
9:

Lold←LTj,Tj\+1:K;B​\(Dw,τj,η\)L\_\{\\mathrm\{old\}\}\\leftarrow L\_\{T\_\{j\},T\_\{j\+1:K\};B\}\(D^\{w\},\\tau\_\{j\},\\eta\)
10:

Lnew←LT~j,Tj\+1:K;B​\(Dw,τj,η\)L\_\{\\mathrm\{new\}\}\\leftarrow L\_\{\\widetilde\{T\}\_\{j\},T\_\{j\+1:K\};B\}\(D^\{w\},\\tau\_\{j\},\\eta\)
11:if

Lnew≤LoldL\_\{\\mathrm\{new\}\}\\leq L\_\{\\mathrm\{old\}\}then

12:

Tj←T~jT\_\{j\}\\leftarrow\\widetilde\{T\}\_\{j\}
13:endif

14:endfor

15:return

\[T1,…,TK\]\+\[B\]\[T\_\{1\},\\dots,T\_\{K\}\]\+\[B\]

Algorithm 23Backfitting for MDTs0:Data

\(X,Xbinarized,y\)\(X,X\_\{\\mathrm\{binarized\}\},y\), MDT stages

𝒯interp=\[T1,…,TK\]\\mathcal\{T\}\_\{\\mathrm\{interp\}\}=\[T\_\{1\},\\dots,T\_\{K\}\], fallback model

BB, number of sweeps

MM, depth

dd,

τ\\tau,

η\\eta,

μ≥0\\mu\\geq 0,

γ≥0\\gamma\\geq 0, boolean flag

rescale​\_​tau\\mathrm\{rescale\\\_tau\}
0:Updated MDT stages and fallback model

1:for

m=1,…,Mm=1,\\dots,Mdo

2:

DK←\{i:T1​\(xi\)=⋯=TK​\(xi\)=defer\}D\_\{K\}\\leftarrow\\\{i:T\_\{1\}\(x\_\{i\}\)=\\cdots=T\_\{K\}\(x\_\{i\}\)=\\texttt\{defer\}\\\}
3:

𝒮K←GetDeferredSubregions​\(T1:K\)\\mathcal\{S\}\_\{K\}\\leftarrow\\textsc\{GetDeferredSubregions\}\(T\_\{1:K\}\)
4:

w←GetWeights​\(X,DK,𝒮K,γ,μ,T1:K\)w\\leftarrow\\textsc\{GetWeights\}\(X,D\_\{K\},\\mathcal\{S\}\_\{K\},\\gamma,\\mu,T\_\{1:K\}\)
5:

B←FitFallbackModel​\(X,y,w\)B\\leftarrow\\textsc\{FitFallbackModel\}\(X,y,w\)
6:

𝒯interp\+\[B\]←BackwardPass​\(X,Xbinarized,y,𝒯interp,B,d,τ,η,μ,γ,rescale​\_​tau,K,1\)\\mathcal\{T\}\_\{\\mathrm\{interp\}\}\+\[B\]\\leftarrow\\textsc\{BackwardPass\}\(X,X\_\{\\mathrm\{binarized\}\},y,\\mathcal\{T\}\_\{\\mathrm\{interp\}\},B,d,\\tau,\\eta,\\mu,\\gamma,\\mathrm\{rescale\\\_tau\},K,1\)
7:

𝒯interp\+\[B\]←ForwardPass​\(X,Xbinarized,y,𝒯interp,B,d,τ,η,μ,γ,rescale​\_​tau,2,K\)\\mathcal\{T\}\_\{\\mathrm\{interp\}\}\+\[B\]\\leftarrow\\textsc\{ForwardPass\}\(X,X\_\{\\mathrm\{binarized\}\},y,\\mathcal\{T\}\_\{\\mathrm\{interp\}\},B,d,\\tau,\\eta,\\mu,\\gamma,\\mathrm\{rescale\\\_tau\},2,K\)
8:endfor

9:return

𝒯interp\+\[B\]\\mathcal\{T\}\_\{\\mathrm\{interp\}\}\+\[B\]

## Appendix ETraining Objectives

Learning a sparse decision tree is commonly formulated as minimizing a regularized empirical risk of the form

1N​∑i=1N𝟙​\{T​\(xi\)≠yi\}\+λ​\|T\|,\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\mathds\{1\}\\\{T\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\lambda\|T\|,
where\|T\|\|T\|is the number of leaves in the tree\[[36](https://arxiv.org/html/2606.30995#bib.bib42),[44](https://arxiv.org/html/2606.30995#bib.bib9),[3](https://arxiv.org/html/2606.30995#bib.bib37)\]\. For binary trees, the number of internal split nodes is always\|T\|−1\|T\|\-1\. Therefore, minimizing a penalty on leaves is equivalent, up to an additive constantλ\\lambda, to minimizing a penalty on split nodes:

1N​∑i=1N𝟙​\{T​\(xi\)≠yi\}\+λ​\|T\|=1N​∑i=1N𝟙​\{T​\(xi\)≠yi\}\+λ​\(\|T\|−1\)\+λ\.\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\mathds\{1\}\\\{T\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\lambda\|T\|=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\mathds\{1\}\\\{T\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\lambda\(\|T\|\-1\)\+\\lambda\.
Since the two objectives differ only by a constant term, they have the same set of minimizers\. We choose to work with the number of splits for a reason that will become clear in the MDT objective\.

Hybrid interpretable rule\-list models instead optimize an objective that balances the error of the full hybrid system, the complexity of the interpretable rule list, and the amount of deferral to a black\-box model\. In the notation ofFerryet al\.\[[23](https://arxiv.org/html/2606.30995#bib.bib4)\], for a rule listrrand black boxBB, this objective has the form

L^𝒟​\(B,r\)N\+λ​\|r\|\+β​\|𝒟∖𝒟r\|N,\\frac\{\\widehat\{L\}\_\{\\mathcal\{D\}\}\(B,r\)\}\{N\}\+\\lambda\|r\|\+\\beta\\frac\{\|\\mathcal\{D\}\\setminus\\mathcal\{D\}\_\{r\}\|\}\{N\},whereL^𝒟​\(B,r\)\\widehat\{L\}\_\{\\mathcal\{D\}\}\(B,r\)is the empirical error of the full hybrid model,\|r\|\|r\|is the number of rules, and𝒟r\\mathcal\{D\}\_\{r\}is the subset of samples captured by the rule list\. Equivalently,\|𝒟∖𝒟r\|/N\|\\mathcal\{D\}\\setminus\\mathcal\{D\}\_\{r\}\|/Nis the empirical deferral rate\.

Our single defer tree objective combines these two perspectives\. It is a sparse decision tree objective combined with a soft penalty for deferral:

ℒT,B​\(𝒟w,τ,η\)=τ​\(\|T\|−1\)\+∑i=1Nwi​\(𝟙​\{y^T,B​\(xi\)≠yi\}\+η​𝟙​\{T​\(xi\)=defer\}\)\.\\mathcal\{L\}\_\{T,B\}\(\\mathcal\{D\}^\{w\},\\tau,\\eta\)=\\tau\(\|T\|\-1\)\+\\sum\_\{i=1\}^\{N\}w\_\{i\}\\left\(\\mathds\{1\}\\\{\\hat\{y\}\_\{T,B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\mathds\{1\}\\\{T\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\right\)\.
When all weights arewi=1w\_\{i\}=1andη=0\\eta=0, we recover the same loss \(except we do not normalize by the dataset sizeNN\) as\[[36](https://arxiv.org/html/2606.30995#bib.bib42),[44](https://arxiv.org/html/2606.30995#bib.bib9),[3](https://arxiv.org/html/2606.30995#bib.bib37)\], withτ=λ​N\\tau=\\lambda N\.

The MDT objective is then the natural extension of the single defer\-tree objective: it penalizes the predictions and deferral rate after routing through all stages of the MDT\.

ℒT1:k,B​\(𝒟w,τ,η\)=τ​∑j=1k\(\|Tj\|−1\)\+∑i=1Nwi​\(𝟙​\{y^T1:k,B​\(xi\)≠yi\}\+η​𝟙​\{T1:k​\(xi\)=defer\}\)\.\\mathcal\{L\}\_\{T\_\{1:k\},B\}\(\\mathcal\{D\}^\{w\},\\tau,\\eta\)=\\tau\\sum\_\{j=1\}^\{k\}\(\|T\_\{j\}\|\-1\)\+\\sum\_\{i=1\}^\{N\}w\_\{i\}\\left\(\\mathds\{1\}\\\{\\hat\{y\}\_\{T\_\{1:k\},B\}\(x\_\{i\}\)\\neq y\_\{i\}\\\}\+\\eta\\mathds\{1\}\\\{T\_\{1:k\}\(x\_\{i\}\)=\\mathrm\{defer\}\\\}\\right\)\.Whenk=1k=1, this reduces exactly to the single defer\-tree objective\. For MDTs, it is more natural to regularize the number of splits rather than leaves because if there was a stage with a single defer leaf, regularizing by the number of leaves would increase the MDT objective, though nothing was changed about the predictions or the amount that the MDT deferred\.

Finally, Theorem[1](https://arxiv.org/html/2606.30995#Thmtheorem1)shows that any MDT has an associated rule\-list representation with

\|rMDT\|=∑j=1k\(\|Tj\|−dj\),\|r\_\{\\mathrm\{MDT\}\}\|=\\sum\_\{j=1\}^\{k\}\(\|T\_\{j\}\|\-d\_\{j\}\),where\|Tj\|\|T\_\{j\}\|is the number of leaves of stagejjanddjd\_\{j\}is the number of deferral leaves in that stage\. Assume the MDT has a non\-zero deferral rate to the fallback model: this means that every stage defers\. Sincedj≥1d\_\{j\}\\geq 1,

∑j=1k\(\|Tj\|−dj\)≤∑j=1k\(\|Tj\|−1\)\\sum\_\{j=1\}^\{k\}\(\|T\_\{j\}\|\-d\_\{j\}\)\\leq\\sum\_\{j=1\}^\{k\}\(\|T\_\{j\}\|\-1\)Therefore, the MDT split penalty upper bounds the rule\-list sparsity penalty of the corresponding rule\-list representation\.

## Appendix FExperiment Setup

### F\.1Machines

All experiments were performed on an institutional computing cluster\. Each experiment was executed on a single compute node equipped with an AMD EPYC 9554 processor \(2\.75 GHz\), with 64 physical cores\. Resources were restricted to 1 CPU core and 50 GB of RAM\.

### F\.2Datasets

We provide a description of all datasets used in this work and the binary classification task we chose\.

For all datasets, we remove rows containing missing values and one\-hot encode all categorical variables\.

##### Abalone\[[52](https://arxiv.org/html/2606.30995#bib.bib110)\]\(4,177 samples\)

Predict whether an abalone is male based on its physical measurements\.

##### Adult\[[5](https://arxiv.org/html/2606.30995#bib.bib56)\]\(48,842 samples\)

Predict whether an individual earns more than $50,000 per year based on demographic and occupational attributes\.

##### Aging\[[48](https://arxiv.org/html/2606.30995#bib.bib57),[39](https://arxiv.org/html/2606.30995#bib.bib58)\]\(714 samples\)

Predict whether an individual has visited at least two doctors\.

##### Bike\[[21](https://arxiv.org/html/2606.30995#bib.bib61),[22](https://arxiv.org/html/2606.30995#bib.bib62)\]\(17,379 samples\)

Predict whether bike rental demand exceeds the median\.

##### California\[[53](https://arxiv.org/html/2606.30995#bib.bib109)\]\(20,634 samples\)

Predict whether the provided binary target variablepriceis true\.

##### Churn\[[20](https://arxiv.org/html/2606.30995#bib.bib66),[40](https://arxiv.org/html/2606.30995#bib.bib67)\]\(5,000 samples\)

Predict whether a customer will churn\.

##### Compas\[[4](https://arxiv.org/html/2606.30995#bib.bib68)\]\(4,966 samples\)

Predict whether a defendant will recidivate within two years\.

##### Coupon\[[31](https://arxiv.org/html/2606.30995#bib.bib108)\]\(108 samples\)

Predict whether an individual accepts a recommended coupon\.

##### Credit\[[74](https://arxiv.org/html/2606.30995#bib.bib70),[73](https://arxiv.org/html/2606.30995#bib.bib71)\]\(30,000 samples\)

Predict whether a client will default on their credit card payment in the following month\.

##### Diamonds\[[51](https://arxiv.org/html/2606.30995#bib.bib107)\]\(53,940 samples\)

Predict whether a diamond belongs to cut category 2 based on its physical attributes\.

##### Droid\[[42](https://arxiv.org/html/2606.30995#bib.bib73),[41](https://arxiv.org/html/2606.30995#bib.bib74)\]\(29,332 samples\)

Predict whether an Android application is malicious\.

##### Heloc\[[24](https://arxiv.org/html/2606.30995#bib.bib79)\]\(2,502 samples\)

Predict whether an individual is high\- or low\-risk for a home equity line of credit\.

##### Jasmine\[[49](https://arxiv.org/html/2606.30995#bib.bib85),[27](https://arxiv.org/html/2606.30995#bib.bib64)\]\(2,984 samples\)

Binary classification using the provided target column\.

##### Madeline\[[50](https://arxiv.org/html/2606.30995#bib.bib86)\]\(3,140 samples\)

Binary classification using the provided target column\.

##### Magic\[[8](https://arxiv.org/html/2606.30995#bib.bib88)\]\(19,020 samples\)

Predict whether a Cherenkov telescope image corresponds to a gamma ray or background noise\.

##### Monk2\[[67](https://arxiv.org/html/2606.30995#bib.bib89),[72](https://arxiv.org/html/2606.30995#bib.bib90)\]\(601 samples\)

Predict the logical rule where the label is 1 if exactly two of six attributes take value 1\.

##### Phishing\[[45](https://arxiv.org/html/2606.30995#bib.bib94),[46](https://arxiv.org/html/2606.30995#bib.bib95)\]\(11,055 samples\)

Predict whether a website is phishing or legitimate\.

##### Pol\[[54](https://arxiv.org/html/2606.30995#bib.bib106)\]\(10,082 samples\)

Binary classification using the provided target column\.

##### Rl\[[55](https://arxiv.org/html/2606.30995#bib.bib105)\]\(4,970 samples\)

Binary classification using the provided target column\.

##### Shopping\[[60](https://arxiv.org/html/2606.30995#bib.bib97),[61](https://arxiv.org/html/2606.30995#bib.bib98)\]\(12,330 samples\)

Predict whether an online shopping session ends in a purchase\.

##### Spambase\[[29](https://arxiv.org/html/2606.30995#bib.bib99)\]\(4,601 samples\)

Predict whether an email is spam\.

##### Student\[[15](https://arxiv.org/html/2606.30995#bib.bib100),[14](https://arxiv.org/html/2606.30995#bib.bib101)\]\(649 samples\)

Predict whether a student passes a course \(final grade≥10\\geq 10\)\.

##### Tic\-Tac\-Toe\[[2](https://arxiv.org/html/2606.30995#bib.bib103)\]\(958 samples\)

Predict whether a player has won given a terminal board configuration\.

##### Wine\[[56](https://arxiv.org/html/2606.30995#bib.bib104)\]\(6,497 samples\)

Predict whether wine quality is at least 7\.

### F\.3Hyperparameter Selection

All cross\-validation was done with 3 folds\. Any results reported are averaged across 5 train/test splits\.

#### F\.3\.1Black Boxes:

##### Random Forest\.

Random Forest hyperparameters were tuned with Optuna using a 12\-hour timeout per train/test split:

nestimators\\displaystyle n\_\{\\text\{estimators\}\}∈\{100,200,…,1200\},\\displaystyle\\in\\\{00,00,\\ldots,200\\\},max\_depth∈\[2,32\],\\displaystyle\\in\[2,2\],min\_samples\_split∈\[2,40\],\\displaystyle\\in\[2,0\],min\_samples\_leaf∈\[1,20\],\\displaystyle\\in\[1,0\],max\_features∈\{p,log2⁡\(p\),α​p:α∈\[0\.1,1\.0\]\},\\displaystyle\\in\\\{\\sqrt\{p\},\\log\_\{2\}\(p\),\\alpha p:\\alpha\\in\[1,0\]\\\},bootstrap∈\{True,False\},\\displaystyle\\in\\\{\\text\{True\},\\text\{False\}\\\},class\_weight∈\{None,balanced,balanced\_subsample\}\.\\displaystyle\\in\\\{\\text\{None\},\\text\{balanced\},\\text\{balanced\\\_subsample\}\\\}\.

##### XGBoost\.

XGBoost hyperparameters were tuned with Optuna using a 12\-hour timeout per train/test split:

nestimators\\displaystyle n\_\{\\text\{estimators\}\}∈\{100,200,…,1200\},\\displaystyle\\in\\\{00,00,\\ldots,200\\\},max\_depth∈\[2,12\],\\displaystyle\\in\[2,2\],learning\_rate∈\[10−3,3⋅10−1\]​on a log scale,\\displaystyle\\in\[0^\{\-3\},3\\cdot 0^\{\-1\}\]\\text\{ on a log scale\},min\_child\_weight∈\[10−2,20\]​on a log scale,\\displaystyle\\in\[0^\{\-2\},0\]\\text\{ on a log scale\},subsample∈\[0\.5,1\.0\],\\displaystyle\\in\[5,0\],colsample\_bytree∈\[0\.5,1\.0\],\\displaystyle\\in\[5,0\],γ\\displaystyle\\gamma∈\[10−8,10\]​on a log scale,\\displaystyle\\in\[0^\{\-8\},0\]\\text\{ on a log scale\},αreg\\displaystyle\\alpha\_\{\\text\{reg\}\}∈\[10−8,10\]​on a log scale,\\displaystyle\\in\[0^\{\-8\},0\]\\text\{ on a log scale\},λreg\\displaystyle\\lambda\_\{\\text\{reg\}\}∈\[10−8,10\]​on a log scale\.\\displaystyle\\in\[0^\{\-8\},0\]\\text\{ on a log scale\}\.

#### F\.3\.2Additive Models with Pairwise Interactions

##### Explainable Boosting Machine \(EBM\)\.

EBM hyperparameters were tuned with Optuna using a 12\-hour timeout per train/test split and 5\-fold cross\-validation:

interactions∈\[0,50\],\\displaystyle\\in\[0,0\],learning\_rate∈\[10−3,5⋅10−2\]​on a log scale,\\displaystyle\\in\[0^\{\-3\},5\\cdot 0^\{\-2\}\]\\text\{ on a log scale\},max\_rounds∈\{200,400,…,5000\},\\displaystyle\\in\\\{00,00,\\ldots,000\\\},max\_bins∈\{64,128,256,512,1024\},\\displaystyle\\in\\\{4,28,56,12,024\\\},max\_interaction\_bins∈\{16,32,64,128\},\\displaystyle\\in\\\{6,2,4,28\\\},min\_samples\_leaf∈\[2,50\],\\displaystyle\\in\[2,0\],max\_leaves∈\[2,5\],\\displaystyle\\in\[2,5\],outer\_bags∈\{4,8,12,16\},\\displaystyle\\in\\\{4,8,2,6\\\},validation\_size∈\{0\.10,0\.15,0\.20\},\\displaystyle\\in\\\{10,15,20\\\},early\_stopping\_rounds∈\{50,100,200\},\\displaystyle\\in\\\{0,00,00\\\},early\_stopping\_tolerance∈\[10−6,10−3\]​on a log scale\.\\displaystyle\\in\[0^\{\-6\},0^\{\-3\}\]\\text\{ on a log scale\}\.

#### F\.3\.3Sparse Ensembles

##### FIGS\.

FIGS hyperparameters were tuned with Optuna using a 12\-hour timeout per train/test split\. The following search space was used:

max\_rules∈\[4,64\],\\displaystyle\\in\[4,4\],max\_trees∈\[2,20\],\\displaystyle\\in\[2,0\],max\_depth∈\[2,12\],\\displaystyle\\in\[2,2\],max\_features∈\{None,p,log2⁡\(p\)\},\\displaystyle\\in\\\{\\text\{None\},\\sqrt\{p\},\\log\_\{2\}\(p\)\\\},min\_impurity\_decrease∈\[10−8,10−4\]​on a log scale\.\\displaystyle\\in\[0^\{\-8\},0^\{\-4\}\]\\text\{ on a log scale\}\.The interpretability constraintsmax\_rules≤64\\text\{max\\\_rules\}\\leq 64,max\_trees≤20\\text\{max\\\_trees\}\\leq 20, andmax\_depth≤12\\text\{max\\\_depth\}\\leq 12were always enforced\.

#### F\.3\.4Interpretable Models

##### SingleTree\.

For a single decision tree algorithm, we used our DeferTree algorithm withη=109\\eta=10^\{9\}to ensure no deferral \(we also verified this on all results reported\)\. This corresponds to a version of the near\-optimal decision tree algorithm LicketySPLIT\[[3](https://arxiv.org/html/2606.30995#bib.bib37)\]\.

λ\\displaystyle\\lambda∈\{10−5,5⋅10−5,10−4,5⋅10−4,10−3,5⋅10−3,10−2\},\\displaystyle\\in\\\{0^\{\-5\},5\\cdot 0^\{\-5\},0^\{\-4\},5\\cdot 0^\{\-4\},0^\{\-3\},5\\cdot 0^\{\-3\},0^\{\-2\}\\\},We fixed a depth budget of1010, usingλ\\lambdato grow a sparser tree\. This method requires a binarized dataset\. We binarized the dataset with ThresholdGuessing\[[44](https://arxiv.org/html/2606.30995#bib.bib9)\], usingnestimators=150n\_\{\\text\{estimators\}\}=150andmax\_depth=2\\text\{max\\\_depth\}=2\.

#### F\.3\.5Hybrid Models

##### HyRS\.

For HyRS, we tuned

nrules∈\{5000\},\\displaystyle\\in\\\{000\\\},supp∈\{5,20\},\\displaystyle\\in\\\{5,0\\\},maxlen∈\{2,3\},\\displaystyle\\in\\\{2,3\\\},α\\displaystyle\\alpha∈\{10−4,10−3,10−2\},\\displaystyle\\in\\\{0^\{\-4\},0^\{\-3\},0^\{\-2\}\\\},β\\displaystyle\\beta∈\{0\.01,0\.05,0\.10,0\.15,0\.25,0\.50\},\\displaystyle\\in\\\{01,05,10,15,25,50\\\},niter∈\{5000\}\.\\displaystyle\\in\\\{000\\\}\.Non\-binary numeric features were binarized using1010quantile levels\. We used their provided Random Forest rule mining approach\.

##### FLMM\.

For FLMM, we tuned

rmax\\displaystyle r\_\{\\max\}∈\{1,2,3\},\\displaystyle\\in\\\{1,2,3\\\},ℓ\\displaystyle\\ell∈\{0\.01,0\.02,0\.05,0\.1,0\.2\},\\displaystyle\\in\\\{01,02,05,1,2\\\},s\\displaystyle s∈\{0\.5,0\.6,0\.7,0\.8,0\.9,1\.0\},\\displaystyle\\in\\\{5,6,7,8,9,0\\\},min\_support\_frac∈\{0\.005,0\.01,0\.02\}\.\\displaystyle\\in\\\{005,01,02\\\}\.
We could not find an exact description of the rule mining done in\[[26](https://arxiv.org/html/2606.30995#bib.bib44)\], except thatrmaxr\_\{\\max\}was tuned in\{1,2,3\}\\\{1,2,3\\\}\. Therefore, we use the following procedure\.

Non\-binary numeric features were binarized using1010quantile levels\. Then, candidate rules were exhaustively enumerated as all conjunctions of between11andrmaxr\_\{\\max\}binary indicators\. Any rule whose support was below

max⁡\(1,⌈min\_support\_frac⋅n⌉\)\\max\\\!\\left\(1,\\left\\lceil\\text\{min\\\_support\\\_frac\}\\cdot n\\right\\rceil\\right\)was discarded\. For each remaining conjunction, the predicted label was chosen as the majority class among covered samples\. Duplicate rules inducing identical coverage and prediction behavior were removed\.

##### HybridCORELS\-POST\.

For the HybridCORELS\-POST variant, we tuned

c\\displaystyle c∈\{0\.001,0\.01,0\.1\},\\displaystyle\\in\\\{001,01,1\\\},min\_coverage∈\{0\.1,0\.25,0\.5,0\.75,0\.9\},\\displaystyle\\in\\\{1,25,5,75,9\\\},max\_card∈\{1,2\},\\displaystyle\\in\\\{1,2\\\},min\_support∈\{1,5\},\\displaystyle\\in\\\{1,5\\\},n\_rules∈\{300\},\\displaystyle\\in\\\{00\\\},

##### HybridCORELS\-PRE\.

For the HybridCORELS\-PRE variant, we tuned

c\\displaystyle c∈\{0\.001,0\.01,0\.1\},\\displaystyle\\in\\\{001,01,1\\\},min\_coverage∈\{0\.1,0\.25,0\.5,0\.75,0\.9\},\\displaystyle\\in\\\{1,25,5,75,9\\\},max\_card∈\{1,2\},\\displaystyle\\in\\\{1,2\\\},min\_support∈\{5\},\\displaystyle\\in\\\{5\\\},n\_rules∈\{300\},\\displaystyle\\in\\\{00\\\},α\\displaystyle\\alpha∈\{0,5,10\}\.\\displaystyle\\in\\\{0,5,0\\\}\.
For both optimal methods \(HybridCORELS PRE and POST\), we set a time limit of 10 minutes per hyperparameter to fit the rule list\. This does not include training the black box or performing rule mining\.

For the HybridCORELS variants, we first binarized the dataset with ThresholdGuessing\[[44](https://arxiv.org/html/2606.30995#bib.bib9)\], usingnestimators=150n\_\{\\text\{estimators\}\}=150andmax\_depth=2\\text\{max\\\_depth\}=2\. We then used their provided rule mining method on these binary features, which uses FPGrowth\. Because the HybridCORELS implementation exposes prediction through apredictmethod that accepts only the already rule\-mined dataset, the fallback XGBoost model was required to operate on this same mined feature space\. As such, we retuned the XGBoost model for each hyperparameter combination for HybridCORELS, because the HybridCORELS hyperparameters can change the rule mining and thus what XGBoost is trained on\. Aside from that, the method of choosing hyperparameters is discussed in[subsection F\.4](https://arxiv.org/html/2606.30995#A6.SS4)\.

##### DeferTree\.

For our DeferTree, we tuned

λ\\displaystyle\\lambda∈\{10−5,5⋅10−5,10−4,5⋅10−4,10−3,5⋅10−3,10−2\},\\displaystyle\\in\\\{0^\{\-5\},5\\cdot 0^\{\-5\},0^\{\-4\},5\\cdot 0^\{\-4\},0^\{\-3\},5\\cdot 0^\{\-3\},0^\{\-2\}\\\},η\\displaystyle\\eta∈\{0\.001,0\.005,0\.01,0\.05,0\.1,0\.3,0\.6,0\.8,1\.0,109\}\.\\displaystyle\\in\\\{001,005,01,05,1,3,6,8,0,0^\{9\}\\\}\.
This method requires a binarized dataset\. We binarized the dataset with ThresholdGuessing\[[44](https://arxiv.org/html/2606.30995#bib.bib9)\], usingnestimators=150n\_\{\\text\{estimators\}\}=150andmax\_depth=2\\text\{max\\\_depth\}=2\.

##### MDT\.

For our MDT, we tuned

λ\\displaystyle\\lambda∈\{10−5,5⋅10−5,10−4,5⋅10−4,10−3,5⋅10−3,10−2\},\\displaystyle\\in\\\{0^\{\-5\},5\\cdot 0^\{\-5\},0^\{\-4\},5\\cdot 0^\{\-4\},0^\{\-3\},5\\cdot 0^\{\-3\},0^\{\-2\}\\\},η\\displaystyle\\eta∈\{0\.001,0\.005,0\.01,0\.05,0\.1,0\.3,0\.6,0\.8,1\.0\},\\displaystyle\\in\\\{001,005,01,05,1,3,6,8,0\\\},rescale\_tau∈\{0,1\},\\displaystyle\\in\\\{0,1\\\},c\\displaystyle c∈\{0,0\.2,0\.5,1\.0\},\\displaystyle\\in\\\{0,2,5,0\\\},γ\\displaystyle\\gamma∈\{0,1,2,4,8\},\\displaystyle\\in\\\{0,1,2,4,8\\\},The fixed settings were depth budget1010, maximum stages66, maximum total stage leaves500500, maximum leaves in an uncompressed single tree10610^\{6\}, and maximum leaves per tree129129\. In practice, we do not hit depth 10 or anywhere near these limits \(shown in Figure[4\(a\)](https://arxiv.org/html/2606.30995#S4.F4.sf1)\); these are upper bounds that would only prune very undesired hyperparameters\. In our algorithm, the calls to fit a DeferTree require a binarized dataset\. We binarized the dataset with ThresholdGuessing\[[44](https://arxiv.org/html/2606.30995#bib.bib9)\], usingnestimators=150n\_\{\\text\{estimators\}\}=150andmax\_depth=2\\text\{max\\\_depth\}=2\.

### F\.4Cross Validation Procedure

For hybrid interpretable models with fallback black boxes, hyperparameter selection was performed separately for each dataset train/test split\. For a given train/test split, we constructed a table whose rows corresponded to hybrid\-model hyperparameter combinations and whose columns stored the average validation accuracy, average validation deferral rate, test accuracy, and test deferral rate\.

To populate this table, we first created three subtrain/validation partitions from the training set\. For each subtrain partition, we independently tuned an XGBoost model over the ranges described earlier using an inner 3\-fold cross\-validation procedure restricted to that subtrain partition\. After selecting the best XGBoost hyperparameters for that subtrain partition, we fixed that XGBoost model and evaluated every hyperparameter combination in the hybrid interpretable grid using the associated validation split\. Repeating this process across the three subtrain/validation partitions yielded an average validation accuracy and average validation deferral rate for each hybrid hyperparameter configuration\.

Next, we tuned XGBoost once more on the entire training set using the same XGBoost search procedure\. The resulting XGBoost model was then used as the fallback model for every hybrid hyperparameter configuration trained on the full training set, producing a corresponding test accuracy and test deferral rate\.

Given this matrix for a dataset train/test split, if we wished to select the best model subject to at mostx%x\\%test deferral, we first filtered out all hyperparameter configurations whose test deferral exceeded the threshold\. Among the remaining configurations, we selected the one with the highest average validation accuracy\. We then reported the corresponding test accuracy and test deferral for that configuration\. We note that the former \(the test accuracy\) had not been looked at before then, and was not used to choose any hyperparameters\. This entire procedure was repeated independently across the five train/test splits for each dataset\.

## Appendix GExperimental Results

Table 2:Test error comparison between the DeferTree non\-deferred and deferred regions\. The deferred regions consistently exhibit substantially higher test error, motivating that our recursive approach with adaptive weights could reduce the amount we rely on the black box with little change in accuracy\. All values are mean±\\pmstandard deviation across 5 splits\.In[Figure 5](https://arxiv.org/html/2606.30995#A7.F5), we compare the semi\-supervised hyperparameter selection procedure to a variant that uses training deferral rate as a proxy for test deferral rate\. We utilized this semi\-supervised procedure for all methods, and here we compare this approach to using the train deferral rate for MDT\+XGB\. For each target deferral levelxx, we choose the hyperparameters with the highest average validation accuracy among those with deferral rate at mostxx, where deferral is measured on the test set for MDT\+XGB and on the training set for MDT\+XGB Train\. After selecting hyperparameters separately for each of the five train/test splits, we plot the average test accuracy against the average test deferral rate of the selected models\. Across datasets, the two curves are nearly indistinguishable: using training deferral is sometimes slightly better and sometimes slightly worse, but it usually selects models with essentially the same test accuracy–deferral tradeoff\. The only clear degradation occurs on Coupon, which has only 108 total samples after removing missing values, so little weight should be placed on that outlier\. Overall, these results suggest that training deferral rate is an acceptable practical proxy for test deferral rate when selecting MDT\+XGB hyperparameters\.

![Refer to caption](https://arxiv.org/html/2606.30995v1/x9.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x10.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x11.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x12.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x13.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x14.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x15.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x16.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x17.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x18.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x19.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x20.png)

Figure 5:Comparison between MDT\+XGB hyperparameter selection using test deferral rate and selection using training deferral rate\.Table 3:Mean and standard deviation across train/test splits of the absolute difference between train and test defer rates, along with the train and test defer rates themselves, for MDT\+XGB models selected under a 25% test defer\-rate cutoff\.Table 4:Compression ratios \(mean±\\pmstandard deviation across splits\) for splits to evaluate a deferred test sample and leaves of the final compressed MDT XGBoost relative to the original XGBoost fallback\. A 95% confidence interval on the difference \(MDT−XGB\\text\{MDT\}\-\\text\{XGB\}\) in test deferred region accuracy shows they are indistinguishable\. In some settings, the MDT’s XGBoost has higher mean accuracy\. In other cases, it has lower mean accuracy\. However, the confidence intervals almost always contain 0\. This shows that we can obtain meaningful compression on the black box without any loss in accuracy\. Hyperparameters were selected according to maximum validation accuracy without exceeding 25% test deferral for a train\-test split\. To compute confidence intervals, we concatenate the deferred\-sample correctness indicators across all train/test splits and apply bootstrap resampling to the pooled vector of deferred samples\.Table 5:Runtime statistics of the chosen hyperparameters \(best validation accuracy with under 25% test deferral\) across datasets\. Mean±\\pmstandard deviation across 5 train/test splits is shown\.Table 6:Mean and standard deviation across train/test splits of the absolute difference between train and test defer rates, along with the train and test defer rates themselves, for MDT\+XGB models selected under a 10% test defer\-rate cutoff\.Table 7:Test accuracy \(mean±\\pmstandard deviation\) across all datasets\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x21.png)Figure 6:Comparison between selecting hyperparameters for MDTs using a budget on the total number of leaves versus a budget on the mean number of split decisions required to evaluate a sample\. The curves are closely but not exactly aligned\. A rule of thumb is that a total of 50 leaves corresponds to a mean of approximately 7 split evaluations per sample\. This is much better than a full depth 7 tree, which has 128 leaves\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x22.png)Figure 7:Legend for the accuracy\-deferral trade\-off plots on the following pages\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x23.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x24.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x25.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x26.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x27.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x28.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x29.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x30.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x31.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x32.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x33.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x34.png)

Figure 8:Deferral\-accuracy trade\-offs for all datasets\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x35.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x36.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x37.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x38.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x39.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x40.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x41.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x42.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x43.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x44.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x45.png)
![Refer to caption](https://arxiv.org/html/2606.30995v1/x46.png)

Figure 9:Deferral\-accuracy trade\-offs for all datasets, continued\.### G\.1Ablations

![Refer to caption](https://arxiv.org/html/2606.30995v1/x47.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x48.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x49.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x50.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x51.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x52.png)

Figure 10:Results of our MDT algorithm compared to just using our DeferTree algorithm\. Here, we also show results for MDT\+SingleTree, which uses a single decision tree algorithm as fallback instead of XGBoost\. When the deferral rate is 0, DeferTree\+XGB turns into a near\-optimal decision tree algorithm\. We see that MDT\+SingleTree is able to provide a much better, fully interpretable model than a near\-optimal tree in most cases\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x53.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x54.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x55.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x56.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x57.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x58.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x59.png)

Figure 11:Results of our MDT algorithm compared to just using our DeferTree algorithm \(continued\)\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x60.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x61.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x62.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x63.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x64.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x65.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x66.png)

Figure 12:Ablation on the impacts of rescalingτ\\taufor later stages of the MDT\. The booleanrescale\_tauis set to 0 for theαdefer=0\\alpha\_\{\\text\{defer\}\}=0method\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x67.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x68.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x69.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x70.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x71.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x72.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x73.png)

Figure 13:Ablation on the distance\-based reweighting via tuningγ\\gammaor settingγ=0\\gamma=0\.Table 8:Ablation of using in\-sample black\-box predictions versus out\-of\-fold predictions when training the defer model\. Using leave\-one\-out style out\-of\-fold predictions does not improve performance and slightly worsens accuracy on most datasets\. Results show average test accuracy \(±\\pmstandard deviation\) under a 50% test deferral constraint during hyperparameter selection\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x74.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x75.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x76.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x77.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x78.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x79.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x80.png)

Figure 14:Comparison of MDT\+XGB and MDT\+XGB with backfitting across selected datasets\. Each plot shows test accuracy as a function of the deferral rate\. Backfitting gives clear improvements on some datasets, such as Tictactoe, where revisiting stages may help capture higher\-order interactions, but it degrades performance on several others\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x81.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x82.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x83.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x84.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x85.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x86.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x87.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x88.png)

![Refer to caption](https://arxiv.org/html/2606.30995v1/x89.png)

Figure 15:Comparison of MDT\+XGB and MDT\+EBM across selected datasets\. MDT\+EBM uses an Explainable Boosting Machine\[[37](https://arxiv.org/html/2606.30995#bib.bib111)\]as the fallback model, providing a more interpretable alternative to XGBoost\. For some datasets, this amount of fallback complexity is sufficient, and MDT\+EBM closely matches MDT\+XGB\. For other datasets, most notably Bike and Phishing, the EBM fallback is not expressive enough to recover the same accuracy–deferral tradeoff as MDT\+XGB\.

## Appendix HExamples of MDTs

![Refer to caption](https://arxiv.org/html/2606.30995v1/x90.png)\(a\)MDT stage 1
![Refer to caption](https://arxiv.org/html/2606.30995v1/x91.png)\(b\)MDT stage 2
![Refer to caption](https://arxiv.org/html/2606.30995v1/x92.png)\(c\)Compressed single\-tree representation

Figure 16:Compressed MDT stages and corresponding compressed single\-tree representation for Churn\.![Refer to caption](https://arxiv.org/html/2606.30995v1/x93.png)\(a\)MDT stage 1
![Refer to caption](https://arxiv.org/html/2606.30995v1/x94.png)\(b\)MDT stage 2
![Refer to caption](https://arxiv.org/html/2606.30995v1/x95.png)\(c\)MDT stage 3
![Refer to caption](https://arxiv.org/html/2606.30995v1/x96.png)\(d\)Compressed single\-tree representation

Figure 17:Compressed MDT stages and corresponding compressed single\-tree representation for Phishing\.Rule Bankr1r\_\{1\}prefix\_suffix\>0\\texttt\{prefix\\\_suffix\}\>0↦1\\mapsto 1r2r\_\{2\}url\_of\_anchor≤−0\.5\\texttt\{url\\\_of\\\_anchor\}\\leq\-0\.5↦0\\mapsto 0r3r\_\{3\}sslfinal\_state\>0\.5∧web\_traffic≤−0\.5\\texttt\{sslfinal\\\_state\}\>0\.5\\wedge\\texttt\{web\\\_traffic\}\\leq\-0\.5↦1\\mapsto 1r4r\_\{4\}sslfinal\_state\>0\.5∧web\_traffic\>0\.5\\texttt\{sslfinal\\\_state\}\>0\.5\\wedge\\texttt\{web\\\_traffic\}\>0\.5∧links\_in\_tags\>−0\.5\\wedge\\ \\texttt\{links\\\_in\\\_tags\}\>\-0\.5↦1\\mapsto 1r5r\_\{5\}sslfinal\_state\>0\.5∧web\_traffic\>0\.5\\texttt\{sslfinal\\\_state\}\>0\.5\\wedge\\texttt\{web\\\_traffic\}\>0\.5∧sfh\>−0\.5\\wedge\\ \\texttt\{sfh\}\>\-0\.5↦1\\mapsto 1r6r\_\{6\}sslfinal\_state\>0\.5∧sfh≤−0\.5\\texttt\{sslfinal\\\_state\}\>0\.5\\wedge\\texttt\{sfh\}\\leq\-0\.5∧url\_of\_anchor\>0\.5\\wedge\\ \\texttt\{url\\\_of\\\_anchor\}\>0\.5↦1\\mapsto 1r7r\_\{7\}sslfinal\_state\>0\.5∧sfh\>−0\.5\\texttt\{sslfinal\\\_state\}\>0\.5\\wedge\\texttt\{sfh\}\>\-0\.5∧dnsrecord\>0\\wedge\\ \\texttt\{dnsrecord\}\>0↦1\\mapsto 1r8r\_\{8\}sslfinal\_state\>−0\.5∧sslfinal\_state≤0\.5\\texttt\{sslfinal\\\_state\}\>\-0\.5\\wedge\\texttt\{sslfinal\\\_state\}\\leq 0\.5∧having\_sub\_domain≤0\.5\\wedge\\ \\texttt\{having\\\_sub\\\_domain\}\\leq 0\.5↦0\\mapsto 0r9r\_\{9\}sslfinal\_state\>0\.5∧url\_of\_anchor\>0\.5\\texttt\{sslfinal\\\_state\}\>0\.5\\wedge\\texttt\{url\\\_of\\\_anchor\}\>0\.5↦1\\mapsto 1Sequential Rule ListFigure 18:Phishing Rule List Representation\.