# When Does Confidence-Based Cascade Deferral Suffice?

Wittawat Jitkrittum Neha Gupta Aditya Krishna Menon
Harikrishna Narasimhan Ankit Singh Rawat Sanjiv Kumar
{wittawat, nehagup, adityakmenon,
hnarasimhan, ankitsrawat<EMAIL_ADDRESS>
Google Research, USA

###### Abstract

Cascades are a classical strategy to enable inference cost to vary
_adaptively_ across samples, wherein a sequence of classifiers are invoked in
turn. A _deferral rule_ determines whether to invoke the next classifier in
the sequence, or to terminate prediction. One simple deferral rule employs the
_confidence_ of the current classifier, e.g., based on the maximum predicted
softmax probability. Despite being oblivious to the structure of the cascade —
e.g., not modelling the errors of downstream models — such confidence-based
deferral often works remarkably well in practice. In this paper, we seek to
better understand the conditions under which confidence-based deferral may
fail, and when alternate deferral strategies can perform better. We first
present a theoretical characterisation of the optimal deferral rule, which
precisely characterises settings under which confidence-based deferral may
suffer. We then study _post-hoc_ deferral mechanisms, and demonstrate they can
significantly improve upon confidence-based deferral in settings where (i)
downstream models are _specialists_ that only work well on a subset of inputs,
(ii) samples are subject to label noise, and (iii) there is distribution shift
between the train and test set.

###  1 Introduction

Large neural models with several billions of parameters have shown
considerable promise in challenging real-world problems, such as language
modelling (Radford and Narasimhan, 2018; Radford et al., 2019; Brown et al.,
2020; Raffel et al., 2020) and image classification (Dosovitskiy et al., 2021;
Fedus et al., 2021). While the quality gains of these models are impressive,
they are typically accompanied with a sharp increase in inference time
(Canziani et al., 2016; Schwartz et al., 2019), thus limiting their
applicability. _Cascades_ offer one strategy to mitigate this (Viola and
Jones, 2001; Varshney and Baral, 2022; Saberian and Vasconcelos, 2014; Graf et
al., 2004), by allowing for faster predictions on “easy” samples. In a
nutshell, cascades involve arranging multiple models in a sequence of
increasing complexities. For any test input, one iteratively applies the
following recipe, starting with the first model in the sequence: execute the
current model, and employ a _deferral rule_ to determine whether to invoke the
next model, or terminate with the current model’s prediction. One may further
combine cascades with ensembles to significantly improve accuracy-compute
trade-offs (García-Pedrajas et al., 2005; Wang et al., 2022).

A key ingredient of cascades is the choice of deferral rule. The simplest
candidate is to defer when the current model’s _confidence_ in its prediction
is sufficiently low. Popular confidence measures include the maximum
predictive probability over all classes (Wang et al., 2022), and the entropy
of the predictive distribution (Huang et al., 2018). Despite being oblivious
to the nature of the cascade — e.g., not modelling the errors of downstream
models — such _confidence-based deferral_ works remarkably well in practice
(Wang et al., 2018; Geifman and El-Yaniv, 2019; Gangrade et al., 2021; Wang et
al., 2022; Mamou et al., 2022; Narasimhan et al., 2022). Indeed, it has often
been noted that such deferral can perform on-par with more complex
modifications to the model training (Geifman and El-Yaniv, 2019; Gangrade et
al., 2021; Kag et al., 2023). However, the reasons for this success remain
unclear; further, it is not clear if there are specific practical settings
where confidence-based deferral may perform poorly (Narayan et al., 2022).

In this paper, we initiate a systematic study of the potential limitations of
confidence-based deferral for cascades. Our findings and contributions are:

  1. (i)

We establish a novel result characterising the theoretically optimal deferral
rule (Proposition 3.1), which for a two-model cascade relies on the confidence
of both model 1 and model 2.

  2. (ii)

In many regular classification tasks where model 2 gives a consistent estimate
of the true posterior probability, confidence-based deferral is highly
competitive. However, we show that in some settings, confidence-based deferral
can be significantly sub-optimal both in theory and practice (Section 4.1).
This includes when (1) model 2’s error probability is highly non-uniform
across samples, which can happen when model 2 is a _specialist_ model, (2)
labels are subject to noise, and (3) there is distribution shift between the
train and test set.

  3. (iii)

Motivated by this, we then study a series of _post-hoc_ deferral rules, that
seek to mimic the form of the optimal deferral rule (§4.2). We show that post-
hoc deferral can significantly improve upon confidence-based deferral in the
aforementioned settings.

To the best of our knowledge, this is the first work that precisely identifies
specific practical problems settings where confidence-based deferral can be
sub-optimal for cascades. Our findings give insights on when it is appropriate
to deploy a confidence-based cascade model in practice.

###  2 Background and Related Work

Fix an instance space $\mathscr{X}$ and label space
$\mathscr{Y}=[L]\stackrel{{\scriptstyle.}}{{=}}\\{1,2,\ldots,L\\}$, and let
$\mathbb{P}$ be a distribution over $\mathscr{X}\times\mathscr{Y}$. Given a
training sample $S=\\{(x_{n},y_{n})\\}_{n\in[N]}$ drawn from $\mathbb{P}$,
multi-class classification seeks a _classifier_
$h\colon\mathscr{X}\to{\mathscr{Y}}$ with low _misclassification error_
$R(h)=\mathbb{P}(y\neq h(x))$. We may parameterise $h$ as
$h(x)=\operatorname*{argmax}_{{y}^{\prime}\in\mathscr{Y}}f_{{y}^{\prime}}(x)$
for a _scorer_ $f\colon\mathscr{X}\to\mathbb{R}^{L}$. In neural models, one
expresses $f_{y}(x)=w_{y}^{\top}\Phi(x)$ for class weights $w_{y}$ and
embedding function $\Phi$. It is common to construct a _probability estimator_
$p\colon\mathscr{X}\to\Delta^{L}$ using the softmax transformation,
$p_{y}(x)\propto\exp(f_{y}(x))$.

####  2.1 Cascades and Deferral Rules

Conventional neural models involve a fixed inference cost for any test sample
$x\in\mathscr{X}$. For large models, this cost may prove prohibitive. This has
motivated several approaches to _uniformly_ lower the inference cost for _all_
samples, such as architecture modification (Larsson et al., 2017; Veniat and
Denoyer, 2018; Huang et al., 2018; Vu et al., 2020), stochastic depth (Huang
et al., 2016; Fan et al., 2020), network sparsification (Liu et al., 2015),
quantisation (Hubara et al., 2017), pruning (LeCun et al., 1989), and
distillation (Bucilǎ et al., 2006; Hinton et al., 2015; Rawat et al., 2021). A
complementary strategy is to _adaptively_ lower the inference cost for
_“easy”_ samples, while reserving the full cost only for “hard” samples (Han
et al., 2022; Zilberstein, 1996; Scardapane et al., 2020; Panda et al., 2016;
Teerapittayanon et al., 2016; Wang et al., 2018; Huang et al., 2018; Schwartz
et al., 2020; Xin et al., 2020b; Elbayad et al., 2020; Liu et al., 2020; Zhou
et al., 2020; Xin et al., 2020a).

Cascade models are a classic example of adaptive predictors, which have proven
useful in vision tasks such as object detection (Viola and Jones, 2001), and
have grown increasingly popular in natural language processing (Mamou et al.,
2022; Varshney and Baral, 2022; Khalili et al., 2022; Dohan et al., 2022). In
the vision literature, cascades are often designed for binary classification
problems, with lower-level classifiers being used to quickly identify negative
samples (Brubaker et al., 2007; Zhang and Viola, 2008; Saberian and
Vasconcelos, 2010; Chen et al., 2012; DeSalvo et al., 2015; Streeter, 2018). A
cascade is composed of two components:

  1. (i)

a collection of base models (typically of non-decreasing inference cost)

  2. (ii)

a _deferral rule_ (i.e., a function that decides which model to use for each
$x\in\mathscr{X}$).

For any test input, one executes the first model, and employs the deferral
rule to determine whether to terminate with the current model’s prediction, or
to invoke the next model; this procedure is repeated until one terminates, or
reaches the final model in the sequence. Compared to using a single model, the
goal of the cascade is to offer comparable predictive accuracy, but lower
average inference cost.

While the base models and deferral rules may be trained jointly (Trapeznikov
and Saligrama, 2013; Kag et al., 2023), we focus on a setting where the base
models are _pre-trained and fixed_ , and the goal is to train only the
deferral rule. This setting is practically relevant, as it is often desirable
to re-use powerful models that involve expensive training procedures. Indeed,
a salient feature of cascades is their ability to leverage off-the-shelf
models and simply adjust the desired operating point (e.g., the rate at which
we call a large model).

####  2.2 Confidence-based Cascades

A simple way to define a deferral rule is by thresholding a model’s
_confidence_ in its prediction.

Algorithm 1 Confidence-based cascades of $K$ classifiers

0: $K\geq 2$ classifiers:
$p^{(1)},\ldots,p^{(K)}\colon\mathscr{X}\to\Delta^{L}$, thresholds
$c^{(1)},\ldots,c^{(K-1)}\in[0,1]$

0: An input instance $x\in\mathscr{X}$

0:

1: for $k=1,2,\ldots,K-1$ do

2: if $\max_{y^{\prime}}p^{(k)}_{y^{\prime}}(x)>c^{(k)}$ then

3: Predict class
$\hat{y}=\operatorname*{argmax}_{y^{\prime}}p^{(k)}_{y^{\prime}}(x)$

4: end if

5: end for

6: Predict class
$\hat{y}=\operatorname*{argmax}_{y^{\prime}}p^{(K)}_{y^{\prime}}(x)$

While there are several means of quantifying and improving such confidence
(Shafer and Vovk, 2008; Guo et al., 2017; Kendall and Gal, 2017; Jiang et al.,
2018), we focus on the _maximum predictive probability_
$\gamma(x)\stackrel{{\scriptstyle.}}{{=}}\max_{y^{\prime}}p(y^{\prime}\mid
x)$. Specifically, given $K$ trained models, a confidence-based cascade is
formed by picking the first model that whose confidence $\gamma(x)$ is
sufficiently high (Wang et al., 2022; Ramaswamy et al., 2018). This is made
precise in Algorithm 1.

Forming a cascade in this manner is appealing because it does not require
retraining of any models or the deferral rule. Such a post-hoc approach has
been shown to give good trade-off between accuracy and inference cost (Wang et
al., 2022). Indeed, it has often been noted that such deferral can perform on-
par with more complex modifications to the model training (Geifman and El-
Yaniv, 2019; Gangrade et al., 2021; Kag et al., 2023). However, the reasons
for this phenomenon are not well-understood; further, it is unclear if there
are practical settings where confidence-based cascades are expected to
underperform.

To address this, we now formally analyse confidence-based cascades, and
explicate their limitations.

###  3 Optimal Deferral Rules for Cascades

In this section, we derive the oracle (Bayes-optimal) deferral rule, which
will allow us to understand the effectiveness and limitations of confidence-
based deferral (Algorithm 1).

####  3.1 The Bayes-Optimal Deferral Rule

For simplicity, we consider a cascade of $K=2$ pre-trained classifiers
$h^{(1)},h^{(2)}\colon\mathcal{X}\to\mathcal{Y}$; our analysis readily
generalises to cascades with $K>2$ models (see Appendix F). Suppose that the
classifiers are based on probability estimators $p^{(1)},p^{(2)}$, where for
$i\in\\{1,2\\}$, $p_{y^{\prime}}^{(i)}(x)$ estimates the probability for class
$y^{\prime}$ given $x$, and
$h^{(i)}(x)\stackrel{{\scriptstyle.}}{{=}}\arg\max_{y^{\prime}}p_{y^{\prime}}^{(i)}(x)$.
We do not impose any restrictions on the training procedure or performance of
these classifiers. We seek to learn a deferral rule
$r\colon\mathscr{X}\to\\{0,1\\}$ that can decide whether $h^{(1)}$ should be
used (with $r(x)=0$), or $h^{(2)}$ (with $r(x)=1$).

To derive the optimal deferral rule, we must first specify a target metric to
optimise. Recall that cascades offer a suitable balance between average
inference cost, and predictive accuracy. Thus, we consider a weighted average
of these two quantities as our metric. It is straightforward to extend our
analysis to generic cost-sensitive variants of the predictive accuracy (Elkan,
2001).

Concretely, assume without loss of generality that $h^{(2)}$ has higher
computational cost, and that invoking $h^{(2)}$ incurs a constant cost $c>0$.
The population risk for the cascade can be written as

$\displaystyle R(r;h^{(1)},h^{(2)})=\mathbb{P}(y\neq
h^{(1)}(x),r(x)=0)+\mathbb{P}(y\neq
h^{(2)}(x),r(x)=1)+c\cdot\mathbb{P}(r(x)=1).$ (1)

Intuitively, the first two terms measure the misclassification error only on
samples where the respective classifier’s predictions are used. A good
deferral rule ensures this error is small, while also invoking the larger
model sparingly. The _Bayes-optimal_ rule, which minimises
$R(r;h^{(1)},h^{(2)})$ over all possible $r\colon\mathscr{X}\to\\{0,1\\}$, is
given below. (This relates to existing results from distinct lines of work;
see §3.3.)

######  Proposition 3.1.

Let
$\eta_{y^{\prime}}(x)\stackrel{{\scriptstyle.}}{{=}}\mathbb{P}(y^{\prime}|x)$.
Then, the Bayes-optimal deferral rule for the risk in (1) is:

$\displaystyle r^{*}(x)$
$\displaystyle=\boldsymbol{1}\left[\eta_{h^{(2)}(x)}(x)-\eta_{h^{(1)}(x)}(x)>c\right],$
(2)

Proof can be found in Appendix A. Note that for a classifier $h$,
$\eta_{h(x)}(x)=\mathbb{P}(y=h(x)|x)$ i.e., the probability that $h$ gives a
correct prediction for $x$. Observe that the randomness here reflects the
inherent stochasticity of the labels $y$ for an input $x$, i.e., the aleatoric
uncertainty (Hüllermeier and Waegeman, 2021).

We note that it is common to choose the deferral cost $c$ such that
$\mathbb{P}({r}(x)=1)=\tau$ for fixed deferral rate $\tau\in[0,1]$. By varying
$c$, one obtains a _deferral curve_ quantifying the trade-off between accuracy
and deferral. For the purposes of this curve, the key quantity is
$\eta_{h^{(2)}(x)}(x)-\eta_{h^{(1)}(x)}(x)$, i.e., the _difference in the
probability of correct prediction under each classifier_. This is intuitive:
it is optimal to defer to $h^{(2)}$ if the expected reduction in
misclassification error exceeds the cost of invoking $h^{(2)}$.

The Bayes-optimal deferral rule in (2) is a theoretical construct, which
relies on knowledge of the true posterior probability $\eta$. In practice, one
is likely to use an approximation to this rule. To quantify the effect of such
an approximation, we may consider the _excess risk_ or _regret_ of an
arbitrary deferral rule $r$ over $r^{*}$. We have the following.

######  Corollary 3.2.

Let
$\alpha(x)\stackrel{{\scriptstyle.}}{{=}}\eta_{h_{1}(x)}(x)-\eta_{h_{2}(x)}(x)+c$.
Then, the excess risk for an arbitrary $r$ is

$R(r;h^{(1)},h^{(2)})-R(r^{*};h^{(1)},h^{(2)})=\mathbb{E}_{x}[(\boldsymbol{1}(r(x)=1)-\boldsymbol{1}(\alpha(x)<0))\cdot\alpha(x)].$

Intuitively, the above shows that when we make deferral decisions that
disagree with the Bayes-optimal rule, we are penalised proportional to the
difference between the two models’ error probability.

####  3.2 Plug-in Estimators of the Bayes-Optimal Deferral Rule

In practice, we may seek to approximate the Bayes-optimal deferral rule
$r^{*}$ in (2) with an estimator $\hat{r}$. We now present several _oracle
estimators_ , which will prove useful in our subsequent analysis.

##### One-hot oracle

Observe that $\eta_{y^{\prime}}(x)=\mathbb{E}_{y\mid
x}\left[\boldsymbol{1}[y=y^{\prime}]\right]$. Thus, given a test sample
$(x,y)$, one may replace the expectation with the observed label $y$ to yield
the ideal estimator $\hat{\eta}_{y^{\prime}}(x)=\boldsymbol{1}[y^{\prime}=y]$.
This results in the rule

$\displaystyle\hat{r}_{01}(x)$
$\displaystyle\stackrel{{\scriptstyle.}}{{=}}\boldsymbol{1}\left[\boldsymbol{1}[y=h^{(2)}(x)]-\boldsymbol{1}[y=h^{(1)}(x)]>c\right].$
(3)

One intuitive observation is that for high $c$, this rule only defers samples
with $y\neq h^{(1)}(x)$ but $y=h^{(2)}(x)$, i.e., _samples where the first
model is wrong, but the second model is right_. Unfortunately, this rule is
impractical, since it depends on the label $y$. Nonetheless, it serves as an
oracle to help understand what one can gain if we knew exactly whether the
downstream model makes an error.

##### Probability oracle

Following a similar same reasoning as $\hat{r}_{{\rm 01}}$, another estimator
is given by

$\displaystyle\text{ }\hat{r}_{{\rm prob}}(x)$
$\displaystyle\stackrel{{\scriptstyle.}}{{=}}\boldsymbol{1}\left[p_{y}^{(2)}(x)-p_{y}^{(1)}(x)>c\right].$
(4)

Intuitively $p_{y}^{(2)}(x)$ can be seen as a label-dependent correctness
score of model 2 on an instance $x$.

##### Relative confidence

The above oracles rely on the true label $y$. A more practical plug-estimator
is $\hat{\eta}_{h^{(i)}(x)}(x)=\max_{y^{\prime}}p^{(i)}_{y^{\prime}}(x)$,
which simply uses each model’s softmax probabilities. The rationale for this
rests upon the assumption that the probability model $p^{(i)}$ is a consistent
estimate of the true posterior probability so that $\mathbb{P}(y|x)\approx
p_{y}^{(i)}(x)$ for $i\in\\{1,2\\}$, where $(x,y)$ is a labeled example. Thus,
$\eta_{h^{(i)}(x)}(x)=\mathbb{P}(h^{(i)}(x)|x)\approx
p^{(i)}(h^{(i)}(x)|x)=\max_{y^{\prime}}p_{y^{\prime}}^{(i)}(x)$, resulting in
the rule

$\displaystyle\text{ }\hat{r}_{{\rm rel}}(x)$
$\displaystyle\stackrel{{\scriptstyle.}}{{=}}1\left[\max_{y^{\prime\prime}}p_{y^{\prime\prime}}^{(2)}(x)-\max_{y^{\prime}}p_{y^{\prime}}^{(1)}(x)>c\right].$
(5)

Observe that this deferral decision depends on the confidence of _both_
models, in contrast to confidence-based deferral which relies only on the
confidence of the _first_ model.

Note that the above oracles cannot be used directly for adaptive computation,
because the second model is invoked on _every_ input. Nonetheless, they can
inform us about the available headroom to improve over confidence-based
deferral by considering the confidence of the downstream model. As shall be
seen in Section 4, these estimators are useful for deriving objectives to
train a post hoc deferral rule.

####  3.3 Relation to Existing Work

The two-model cascade is closely connected to the literature on _learning to
defer to an expert_ (Madras et al., 2018; Mozannar and Sontag, 2020). Here,
the goal is to learn a base classifier $h^{(1)}$ that has the option of
invoking an “expert” model $h^{(2)}$; this invocation is controlled by a
deferral rule $r$. Indeed, the risk (1) is a special case of Mozannar and
Sontag (2020, Equation 2), where the second model is considered to be an
“expert”. Proposition 3.1 is a simple generalisation of Mozannar and Sontag
(2020, Proposition 2), with the latter assuming $c=0$. In Appendix F, we
generalise Proposition 3.1 to the cascades of $K>2$ models.

###  4 From Confidence-Based to Post-Hoc Deferral

Having presented the optimal deferral rule in Proposition 3.1, we now use it
to explicate some failure modes for confidence-based deferral, which will be
empirically demonstrated in §5.2.

####  4.1 When Does Confidence-Based Deferral Suffice?

Suppose as before we have probabilistic models $p^{(1)},p^{(2)}$. Recall from
Algorithm 1 that for constant $c^{(1)}>0$, confidence-based deferral employs
the rule

$\hat{r}_{\rm
conf}(x)=\boldsymbol{1}\left[\max_{y^{\prime}}p^{(1)}_{y^{\prime}}(x)<c^{(1)}\right].$
(6)

Following §3.2, (6) may be regarded as a plug-in estimator for the “population
confidence” rule $r_{\rm
conf}(x)\stackrel{{\scriptstyle.}}{{=}}\boldsymbol{1}\left[\eta_{h^{(1)}}(x)<c^{(1)}\right]$.
Contrasting this to Proposition 3.1, we have the following:

######  Lemma 4.1.

The deferral rule $r_{\rm conf}$ produces the same _deferral curve_ as the
Bayes-optimal rule (2) if $\eta_{h^{(1)}}(x)$ and
$\eta_{h^{(1)}}(x)-\eta_{h^{(2)}}(x)$ produce the same ordering over instances
$x\in\mathscr{X}$.

Lemma 4.1 studies the agreement between the _deferral curves_ of $r_{\rm
conf}$ and the Bayes-optimal solution, which eliminates the need for
committing to a specific cost $c^{(1)}$. The lemma has an intuitive
interpretation: population confidence-based deferral is optimal if and only if
the _absolute_ confidence in model 1’s prediction agrees with the _relative_
confidence is model 1 versus model 2’s prediction.

Based on this, we now detail some cases where confidence-based deferral
succeeds or fails.

##### Success mode: expert $h^{(2)}$

Lemma 4.1 has one immediate, intuitive consequence: _confidence-based deferral
is optimal when the downstream model has a constant error probability_ , i.e.,
$\eta_{h_{2}(x)}(x)$ is a constant for all $x\in\mathscr{X}$. This may happen,
e.g., if that the labels are deterministic given the inputs, and the second
classifier $h^{(2)}$ perfectly predicts them. Importantly, note that this is a
sufficient (but _not_ necessary) condition for the optimality of confidence-
based deferral.

##### Failure mode: specialist $h^{(2)}$

As a converse to the above, one setting where confidence-based deferral may
fail is when when the downstream model is a _specialist_ , which performs well
only on a particular sub-group of the data (e.g., a subset of classes).
Intuitively, confidence-based deferral may _erroneously forward samples where
$h^{(2)}$ performs worse than $h^{(1)}$_.

Concretely, suppose there is a data sub-group $\mathscr{X}_{\rm
good}\subset\mathscr{X}$ where $h^{(2)}$ performs exceptionally well, i.e.,
$\eta_{h^{(2)}(x)}\approx 1$ when $x\in\mathscr{X}_{\rm good}$. On the other
hand, suppose $h^{(2)}$ does not perform well on $\mathscr{X}_{\rm
bad}\stackrel{{\scriptstyle.}}{{=}}\mathscr{X}\setminus\mathscr{X}_{\rm
good}$, i.e., $\eta_{h^{(2)}(x)}\approx 1/L$ when $x\in\mathscr{X}_{\rm bad}$.
Intuitively, while $\eta_{h^{(1)}(x)}$ may be relatively low for
$x\in\mathscr{X}_{\rm bad}$, it is strongly desirable to _not_ defer such
examples, as $h^{(2)}$ performs even worse than $h^{(1)}$; rather, it is
preferable to identify and defer samples $x\in\mathscr{X}_{\rm good}$.

##### Failure mode: label noise

Confidence-based deferral can fail when there are high levels of label noise.
Intuitively, in such settings, confidence-based deferral may _wastefully
forward samples where $h^{(2)}$ performs no better than $h^{(1)}$_.
Concretely, suppose that instances $x\in\mathscr{X}_{\rm
bad}\subset\mathscr{X}$ may be mislabeled as one from a different, random
class. For $x\in\mathscr{X}_{\rm bad}$, regardless of how the two models
$h^{(1)},h^{(2)}$ perform, we have
$\eta_{h^{(1)}(x)}(x),\eta_{h^{(2)}(x)}(x)=1/L$ (i.e., the accuracy of
classifying these instances is chance level in expectation). Since
$\eta_{h^{(1)}(x)}(x)$ is low, confidence-based deferral will tend to defer
such input instance $x$. However, this is a sub-optimal decision since model 2
is more computationally expensive, and expected to have the same chance-level
performance.

##### Failure mode: distribution shift

Even when model $h^{(2)}$ is an expert model, an intuitive setting where
confidence-based deferral can fail is if there is _distribution shift_ between
the train and test $\mathbb{P}(y\mid x)$ (Quinonero-Candela et al., 2009). In
such settings, even if $p^{(1)}$ produces reasonable estimates of the
_training_ class-probability, these may translate poorly to the test set.
There are numerous examples of confidence degradation under such shifts, such
as the presence of _out-of-distribution_ samples (Nguyen et al., 2015;
Hendrycks and Gimpel, 2017), and the presence of a _label skew_ during
training (Wallace and Dahabreh, 2012; Samuel et al., 2021). We shall focus on
the latter in the sequel.

Training label $z$ | Loss | Deferral rule | Method label |  Comment
---|---|---|---|---
$1[y=h^{(2)}(x)]-1[y=h^{(1)}(x)]$ | Mean-squared error | $g(x)>c$ | Diff-01 |  Regression
$p^{(2)}_{y}(x)-p^{(1)}_{y}(x)$ | Mean absolute error | $g(x)>c$ | Diff-Prob |  Regression
$\max_{y^{\prime}}p^{(2)}_{y^{\prime}}(x)$ | Mean-squared error | $g(x)-\max_{y^{\prime}}p^{(1)}_{y^{\prime}}(x)>c$ | MaxProb |  Regression

Table 1: Candidate post-hoc estimators of the oracle rule in (1). We train a
post-hoc model $g(x)$ on a training set $\\{(x_{i},z_{i})\\}_{i=1}^{n}$ so as
to predict the label $z$. Here, $(x,y)\in\mathscr{X}\times\mathscr{Y}$ is a
labeled example.

####  4.2 Post-Hoc Estimates of the Deferral Rule

Having established that confidence-based deferral may be sub-optimal in
certain settings, we now consider the viability of deferral rules that are
_learned_ in a post-hoc manner. Compared to confidence-based deferral, such
rules aim to explicitly account for _both_ the confidence of model 1 and 2,
and thus avoid the failure cases identified above.

The key idea behind such post-hoc rules is to directly mimic the optimal
deferral rule in (2). Recall that this optimal rule has a dependence on the
output of $h^{(2)}$; unfortunately, querying $h^{(2)}$ defeats the entire
purpose of cascades. Thus, our goal is to estimate (2) using only the outputs
of $p^{(1)}$.

We summarise a number of post-hoc estimators in Table 1, which are directly
motivated by the One-hot, Probability, and Relative Confidence Oracle
respectively from Section 3.2. The first is to learn when model 1 is
incorrect, and model 2 is correct. For example, given a validation set,
suppose we construct samples
$S_{\rm{val}}\stackrel{{\scriptstyle.}}{{=}}\\{(x_{i},z^{(1)}_{i}\\}$, where
$z_{i}^{(1)}=1[y\neq h^{(2)}(x_{i})]-1[y=h^{(1)}(x_{i})]$. Then, we fit

$\min_{g\colon\mathscr{X}\to\mathbb{R}}\frac{1}{|S_{\rm{val}}|}\sum_{(x_{i},z^{(1)}_{i})\in
S_{\rm val}}\ell(z^{(1)}_{i},g(x_{i})),$

where, e.g., $\ell$ is the square loss. The score $g(x)$ may be regarded as
the confidence in deferring to model 2. Similarly, a second approach is to
perform regression to predict
$z^{(2)}_{i}=p_{y}^{(2)}(x_{i})-p_{y}^{(1)}(x_{i})$. The third approach is to
directly estimate $z^{(3)}_{i}=\max_{y^{\prime}}p^{(2)}_{y^{\prime}}(x_{i})$
using predictions of the first model.

As shall be seen in §5.2, such post-hoc rules can learn to avoid the failure
cases for confidence-based deferral identified in the previous section.
However, it is important to note that there are some conditions where such
rules may not offer benefits over confidence-based deferral.

##### Failure mode: Bayes $p^{(2)}$

Suppose that the model $p^{(2)}$ exactly matches the Bayes-probabilities,
i.e., $p^{(2)}_{y^{\prime}}(x)=\mathbb{P}(y^{\prime}\mid x)$. Then, estimating
$\max_{y^{\prime}}p^{(2)}_{y^{\prime}}(x)$ is equivalent to estimating
$\max_{y^{\prime}}\mathbb{P}(y^{\prime}\mid x)$. However, the goal of model 1
is _precisely_ to estimate $\mathbb{P}(y\mid x)$. Thus, if $p^{(1)}$ is
sufficiently accurate, in the absence of additional information (e.g., a fresh
dataset), it is unlikely that one can obtain a better estimate of this
probability than that provided by $p^{(1)}$ itself. This holds even if the
$\mathbb{P}(y\mid x)$ is non-deterministic, and so the second model has non-
trivial error.

##### Failure mode: non-predictable $p^{(2)}$ error

When the model $p^{(2)}$’s outputs are not strongly predictable, post-hoc
deferral may devolve to regular confidence-based deferral. Formally, suppose
we seek to predict
$z\stackrel{{\scriptstyle.}}{{=}}\max_{y^{\prime}}p^{(2)}_{y^{\prime}}(x)$,
e.g., as in MaxProb. A non-trivial predictor must achieve an average square
error smaller than the variance of $z$, i.e.,
$\mathbb{E}[(z-\mathbb{E}[z])^{2}]$. If $z$ is however not strongly
predictable, the estimate will be tantamount to simply using the constant
$\mathbb{E}[z]$. This brings us back to the assumption of model 2 having a
constant probability of error, i.e., confidence-based deferral.

####  4.3 Relation to Existing Work

As noted in Section 3.3, learning a deferral rule for a two-model cascade is
closely related to existing literature in learning to defer to an expert. This
in turn is a generalisation of the classical literature on _learning to
reject_ (Hendrickx et al., 2021), which refers to classification settings
where one is allowed to abstain from predicting on certain inputs. The
population risk here is a special case of (1), where $h^{(2)}(x)$ is assumed
to perfectly predict $y$. The resulting Bayes-optimal classifier is known as
Chow’s rule (Chow, 1970; Ramaswamy et al., 2018), and exactly coincides with
the deferral rule in Lemma 4.1. Plug-in estimates of this rule are thus
analogous to confidence-based deferral, and have been shown to be similarly
effective (Ni et al., 2019).

In settings where one is allowed to modify the training of $h^{(1)}$, it is
possible to construct losses that jointly optimise for both $h^{(1)}$ and $r$
(Bartlett and Wegkamp, 2008; Cortes et al., 2016; Ramaswamy et al., 2018;
Thulasidasan et al., 2019; Charoenphakdee et al., 2021; Gangrade et al., 2021;
Kag et al., 2023). While effective, these are not applicable in our setting
involving pre-trained, black-box classifiers. Other variants of post-hoc
methods have been considered in Narasimhan et al. (2022), and implicitly in
Trapeznikov and Saligrama (2013); however, here we more carefully study the
different possible ways of constructing these methods, and highlight when they
may fail to improve over confidence-based deferral.

###  5 Experimental Illustration

In this section, we provide empirical evidence to support our analysis in
Section 4.1 by considering the three failure modes in which confidence-based
deferral underperforms. For each of these settings, we compute _deferral
curves_ that plot the classification accuracy versus the fraction of samples
deferred to the second model (which implicitly measures the overall compute
cost). In line with our analysis in Section 4.1, post-hoc deferral rules offer
better accuracy-cost trade-offs in these settings.

(a) Standard ImageNet
(100% non-dog training images) (b) 4% non-dog training images

(c) 2% non-dog training images

Figure 1: Test accuracy vs deferral rate of plug-in estimates (Section 3.2)
for the oracle rule. Here, $h^{(1)}$ is a MobileNet V2 trained on all ImageNet
classes, and $h^{(2)}$ is a dog specialist trained on all images in the dog
synset plus a fraction of non-dog training examples, which we vary. As the
fraction decreases, $h^{(2)}$ specialises in classifying different types of
dogs. By considering the confidence of $h^{(2)}$ (Relative Confidence), one
gains accuracy by selectively deferring only dog images.

####  5.1 Confidence-Based versus Oracle Deferral

We begin by illustrating the benefit of considering confidence of the second
model when constructing a deferral rule. In this experiment, $h^{(1)}$ is a
generalist (i.e., trained on all ImageNet classes), and $h^{(2)}$ is a dog
specialist trained on all images in the dog synset, plus a fraction of non-dog
training examples, which we vary. There are 119 classes in the dog synset. We
use MobileNet V2 (Sandler et al., 2018) as $h^{(1)}$, and a larger
EfficientNet B0 (Tan and Le, 2019) as $h^{(2)}$. For hyperparameter details,
see Appendix C.

Figure 1 shows the accuracy of confidence-based deferral (Confidence) and
Relative Confidence (Equation 5) on the standard ImageNet test set as a
function of the deferral rate. We realise different deferral rates by varying
the value of the deferral threshold $c$. In Figure 1a, the fraction of non-dog
training images is 100% i.e., model 2 is also a generalist trained on all
images. In this case, we observe that Relative Confidence offers little gains
over Confidence.

However, in Figure 1b and Figure 1c, as the fraction of non-dog training
images decreases, the non-uniformity of $h^{(2)}$’s error probabilities
increases i.e., $h^{(2)}$ starts to specialise to dog images. In line with our
analysis in Section 4.1, confidence-based deferral underperforms when model
2’s error probability is highly non-uniform. That is, being oblivious to the
fact that $h^{(2)}$ specialises in dog images, confidence-based deferral may
erroneously defer non-dog images to it. By contrast, accounting for model 2’s
confidence, as done by Relative Confidence, shows significant gains.

####  5.2 Confidence-Based versus Post-Hoc Deferral

From §5.1, one may construct better deferral rules by querying model 2 for its
confidence. Practically, however, querying model 2 at inference time defeats
the entire purpose of cascades. To that end, we now compare confidence-based
deferral and the post-hoc estimators (Table 1), which do _not_ need to invoke
model 2 at inference time. We consider each of the settings from Section 4.1,
and demonstrate that post-hoc deferral can significantly outperform
confidence-based deferral. We present more experimental results in Appendix E,
where we illustrate post-hoc deferral rules for $K>2$ models.

##### Post hoc model training

In all of the following experiments, the post-hoc model
$g\colon\mathscr{X}\to\mathbb{R}$ is based on a lightweight, three-layer
Multi-Layer Perceptron (MLP) that takes as input the probability outputs from
model 1. That is, $g(x)=\mathrm{MLP}(p^{(1)}(x))$ where
$p^{(1)}(x)\in\Delta_{L}$ denotes all probability outputs from model 1.
Learning $g$ amounts to learning the MLP as the two base models are fixed. We
train $g$ on a held-out validation set. For full technical details of the
post-hoc model architecture and training, see Appendix C. We use the
objectives described in Table 1 to train $g$.

(a) Standard ImageNet. (b) 4% non-dog training images.

(c) 2% non-dog training images.

(d) Standard CIFAR 100. (e) Label noise on first 10 classes.

(f) Label noise on first 25 classes.

(g) Standard CIFAR 100. (h) Head classes: 50.

(i) Head classes: 25.

Figure 2: Test accuracy vs deferral rate of the post-hoc approaches in Table 1
under the three settings described in Section 4.1: 1) specialist (row 1), 2)
label noise (row 2), and 3) distribution shift. Row 1: As the fraction of non-
dog training images decreases, model 2 becomes a dog specialist model.
Increase in the non-uniformity in its error probabilities allows post-hoc
approaches to learn to only defer dog images. Row 2: As label noise increases,
the difference in the probability of correct prediction under each model
becomes zero (i.e., probability tends to chance level). Thus, it is sub-
optimal to defer affected inputs since model 2’s correctness is also at chance
level. Being oblivious to model 2, confidence-based deferral underperforms.
For full details, see Section 5.2. Row 3: As the skewness of the label
distribution increases, so does the difference in the probability of correct
prediction under each model (recall the optimal rule in Proposition 3.1), and
it becomes necessary to account for model 2’s probability of correct
prediction when deferring. Hence, confidence-based deferral underperforms.

##### Specialist setting

We start with the same ImageNet-Dog specialist setting used in Section 5.1.
This time, we compare six methods: Confidence, Random, MaxProb, Diff-01, Diff-
Prob, and Entropy. Random is a baseline approach that defers to either model 1
or model 2 at random; MaxProb, Diff-01, and Diff-Prob are the post-hoc rules
described in Table 1; Entropy defers based on the thresholding the entropy of
$p^{(1)}$ (Huang et al., 2018; Kag et al., 2023), as opposed to the maximum
probability.

Results for this setting are presented in Figure 2 (first row). We see that
there are gains from post-hoc deferral, especially in the low deferral regime:
it can accurately determine whether the second model is likely to make a
mistake. Aligning with our analysis, for the generalist setting (Figure 2a),
confidence-based deferral is highly competitive, since $h^{(2)}$ gives a
consistent estimate of $\mathbb{P}(y\mid x)$.

##### Label noise setting

In this setting, we look at a problem with label noise. We consider CIFAR 100
dataset where training examples from pre-chosen $L_{\rm
noise}\in\\{0,10,25\\}$ classes are assigned a uniformly drawn label. The case
of $L_{\rm noise}=0$ corresponds to the standard CIFAR 100 problem. We set
$h^{(1)}$ to be CIFAR ResNet 8 and set $h^{(2)}$ to be CIFAR ResNet 14, and
train both models on the noisy data. The results are shown in Figure 2 (second
row). It is evident that when there is label noise, post-hoc approaches yield
higher accuracy than confidence-based on a large range of deferral rates,
aligning with our analysis in Section 4.1. Intuitively, confidence-based
deferral tends to forward noisy samples to $h^{(2)}$, which performs equally
poorly, thus leading to a waste of deferral budget. By contrast, post-hoc
rules can learn to “give up” on samples with extremely low model 1 confidence.

##### Distribution shift setting

To simulate distribution shift, we consider a long-tailed version of CIFAR 100
(Krizhevsky et al., 2009) where there are $h\in{100,50,25}$ head classes, and
$100-h$ tail classes. Each head class has 500 training images, and each tail
class has 50 training images. The standard CIFAR 100 dataset corresponds to
$h=100$. Both models $h^{(1)}$ (CIFAR ResNet 8) and $h^{(2)}$ (CIFAR ResNet
56) are trained on these long-tailed datasets. At test time, all methods are
evaluated on the standard CIFAR 100 balanced test set, resulting in a label
distribution shift.

We present our results in Figure 2 (third row). In Figure 2g, there is no
distribution shift. As in the case of the specialist setting, there is little
to no gain from post-hoc approaches in this case since both models are
sufficiently accurate. As $h$ decreases from 100 to 50 (Figure 2h) and 25
(Figure 2i), there is more distribution shift at test time, and post-hoc
approaches (notably Diff-01) show clearer gains. To elaborate, the two base
models are of different sizes and respond to the distribution shift
differently, with CIFAR ResNet 56 being able to better handle tail classes
overall. Diff-01 is able to identify the superior performance of $h^{(2)}$ and
defer input instances from tail classes.

(a) Training performance (b) Test performance

Figure 3: Training and test accuracy of post-hoc approaches in the ImageNet-
Dog specialist setting. Model 2 (EfficientNet B0) is trained with all dog
images and 8% of non-dog images. Observe that a post-hoc model (i.e., Diff-01)
can severely overfit to the training set and fail to generalise.

####  5.3 On the Generalisation of Post-Hoc Estimators

Despite the benefits of post-hoc approaches as demonstrated earlier, care must
be taken in controlling the capacity of the post-hoc models. We consider the
same ImageNet-Dog specialist setting as in the top row of Figure 2. Here,
model 2 is trained on all dog images, and a large fraction of non-dog images
(8%).

Since model 2 has access to a non-trivial fraction of non-dog images, the
difference in the probability of correct prediction of the two models is less
predictable. We report deferral curves on both training and test splits in
Figure 3. Indeed, we observe that the post-hoc method Diff-01 can overfit, and
fail to generalise. Note that this is despite using a feedforward network with
two hidden layers of only 64 and 16 units (see Appendix C for details on
hyperparameters) to control the capacity of the post-hoc model. Thoroughly
investigating approaches to increase generalisation of post-hoc models will be
an interesting topic for future study.

###  6 Conclusion and Future Work

The Bayes-optimal deferral rule we present suggests that key to optimally
defer is to identify when the first model is wrong and the second is right.
Based on this result, we then study a number of estimators (Table 1) to
construct trainable post hoc deferral rules, and show that they can improve
upon the commonly used confidence-based deferral.

While we have identified conditions under which confidence-based deferral
underperforms (e.g., specialist setting, label noise), these are not
exhaustive. An interesting direction for future work is to design post-hoc
deferral schemes attuned for settings involving other forms of distribution
shift, such as the presence of out-of-distribution samples. It is also of
interest to study the efficacy of more refined confidence measures, such as
those based on conformal prediction (Shafer and Vovk, 2008). Finally, while
our results have focussed on image classification settings, it would be of
interest to study analogous trends for natural language processing models.

### References

  * Bartlett and Wegkamp [2008] Peter L. Bartlett and Marten H. Wegkamp.  Classification with a reject option using a hinge loss.  _Journal of Machine Learning Research_ , 9(59):1823–1840, 2008.  URL http://jmlr.org/papers/v9/bartlett08a.html.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc., 2020.
  * Brubaker et al. [2007] S. Charles Brubaker, Jianxin Wu, Jie Sun, Matthew D. Mullin, and James M. Rehg.  On the design of cascades of boosted ensembles for face detection.  _International Journal of Computer Vision_ , 77:65–86, 2007\.
  * Bucilǎ et al. [2006] Cristian Bucilǎ, Rich Caruana, and Alexandru Niculescu-Mizil.  Model compression.  In _Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’06, pages 535–541, New York, NY, USA, 2006. ACM.
  * Canziani et al. [2016] Alfredo Canziani, Adam Paszke, and Eugenio Culurciello.  An analysis of deep neural network models for practical applications.  _CoRR_ , abs/1605.07678, 2016.  URL http://arxiv.org/abs/1605.07678.
  * Charoenphakdee et al. [2021] Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama.  Classification with rejection based on cost-sensitive classification.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 1507–1517. PMLR, 18–24 Jul 2021.
  * Chen et al. [2012] Minmin Chen, Zhixiang Xu, Kilian Weinberger, Olivier Chapelle, and Dor Kedem.  Classifier cascade for minimizing feature evaluation cost.  In Neil D. Lawrence and Mark Girolami, editors, _Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics_ , volume 22 of _Proceedings of Machine Learning Research_ , pages 218–226, La Palma, Canary Islands, 21–23 Apr 2012. PMLR.
  * Chow [1970] C. Chow.  On optimum recognition error and reject tradeoff.  _IEEE Transactions on Information Theory_ , 16(1):41–46, 1970.  doi: 10.1109/TIT.1970.1054406.
  * Cortes et al. [2016] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri.  Boosting with abstention.  _Advances in Neural Information Processing Systems_ , 29:1660–1668, 2016.
  * DeSalvo et al. [2015] Giulia DeSalvo, Mehryar Mohri, and Umar Syed.  Learning with deep cascades.  In _Proceedings of the Twenty-Sixth International Conference on Algorithmic Learning Theory (ALT 2015)_ , 2015.
  * Dohan et al. [2022] David Dohan, Winnie Xu, Aitor Lewkowycz, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif A. Saurous, Jascha Sohl-dickstein, Kevin Murphy, and Charles Sutton.  Language model cascades, 2022.  URL https://arxiv.org/abs/2207.10342.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=YicbFdNTTy.
  * Elbayad et al. [2020] Maha Elbayad, Jiatao Gu, Edouard Grave, and Michael Auli.  Depth-adaptive transformer.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=SJg7KhVKPH.
  * Elkan [2001] Charles Elkan.  The foundations of cost-sensitive learning.  In _Proceedings of the 17th International Joint Conference on Artificial Intelligence - Volume 2_ , IJCAI’01, page 973–978, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.  ISBN 1558608125.
  * Fan et al. [2020] Angela Fan, Edouard Grave, and Armand Joulin.  Reducing transformer depth on demand with structured dropout.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=SylO2yStDr.
  * Fedus et al. [2021] William Fedus, Barret Zoph, and Noam Shazeer.  Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity.  _CoRR_ , abs/2101.03961, 2021.  URL https://arxiv.org/abs/2101.03961.
  * Gangrade et al. [2021] Aditya Gangrade, Anil Kag, and Venkatesh Saligrama.  Selective classification via one-sided prediction.  In Arindam Banerjee and Kenji Fukumizu, editors, _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 2179–2187. PMLR, 13–15 Apr 2021.  URL https://proceedings.mlr.press/v130/gangrade21a.html.
  * García-Pedrajas et al. [2005] N. García-Pedrajas, D. Ortiz-Boyer, R. del Castillo-Gomariz, and C. Hervás-Martínez.  Cascade ensembles.  In Joan Cabestany, Alberto Prieto, and Francisco Sandoval, editors, _Computational Intelligence and Bioinspired Systems_ , pages 598–603, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.  ISBN 978-3-540-32106-4.
  * Geifman and El-Yaniv [2019] Yonatan Geifman and Ran El-Yaniv.  SelectiveNet: A deep neural network with an integrated reject option.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 2151–2159. PMLR, 09–15 Jun 2019.
  * Graf et al. [2004] Hans Graf, Eric Cosatto, Leon Bottou, Igor Dourdanovic, and Vladimir Vapnik.  Parallel support vector machines: The cascade svm.  _Advances in neural information processing systems_ , 17, 2004.
  * Guo et al. [2017] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger.  On calibration of modern neural networks.  In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17, page 1321–1330. JMLR.org, 2017.
  * Han et al. [2022] Y. Han, G. Huang, S. Song, L. Yang, H. Wang, and Y. Wang.  Dynamic neural networks: A survey.  _IEEE Transactions on Pattern Analysis & Machine Intelligence_, 44(11):7436–7456, nov 2022.  ISSN 1939-3539.  doi: 10.1109/TPAMI.2021.3117837.
  * Hendrickx et al. [2021] Kilian Hendrickx, Lorenzo Perini, Dries Van der Plas, Wannes Meert, and Jesse Davis.  Machine learning with a reject option: A survey.  _CoRR_ , abs/2107.11277, 2021.
  * Hendrycks and Gimpel [2017] Dan Hendrycks and Kevin Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  In _International Conference on Learning Representations_ , 2017.  URL https://openreview.net/forum?id=Hkg4TI9xl.
  * Hinton et al. [2015] Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean.  Distilling the knowledge in a neural network.  _CoRR_ , abs/1503.02531, 2015.
  * Huang et al. [2016] Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q. Weinberger.  Deep networks with stochastic depth.  In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, _Computer Vision – ECCV 2016_ , pages 646–661, Cham, 2016. Springer International Publishing.  ISBN 978-3-319-46493-0.
  * Huang et al. [2018] Gao Huang, Danlu Chen, Tianhong Li, Felix Wu, Laurens van der Maaten, and Kilian Weinberger.  Multi-scale dense networks for resource efficient image classification.  In _International Conference on Learning Representations_ , 2018.
  * Hubara et al. [2017] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio.  Quantized neural networks: Training neural networks with low precision weights and activations.  _J. Mach. Learn. Res._ , 18(1):6869–6898, jan 2017.  ISSN 1532-4435.
  * Hüllermeier and Waegeman [2021] Eyke Hüllermeier and Willem Waegeman.  Aleatoric and epistemic uncertainty in machine learning: an introduction to concepts and methods.  _Machine Learning_ , 110(3):457–506, mar 2021\.  doi: 10.1007/s10994-021-05946-3.  URL https://doi.org/10.1007%2Fs10994-021-05946-3.
  * Jiang et al. [2018] Heinrich Jiang, Been Kim, Melody Y. Guan, and Maya Gupta.  To trust or not to trust a classifier.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NeurIPS’18, page 5546–5557, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Kag et al. [2023] Anil Kag, Igor Fedorov, Aditya Gangrade, Paul Whatmough, and Venkatesh Saligrama.  Efficient edge inference by selective query.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=jpR98ZdIm2q.
  * Kendall and Gal [2017] Alex Kendall and Yarin Gal.  What uncertainties do we need in bayesian deep learning for computer vision?  In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 5574–5584, 2017.  URL https://proceedings.neurips.cc/paper/2017/hash/2650d6089a6d640c5e85b2b88265dc2b-Abstract.html.
  * Khalili et al. [2022] Leila Khalili, Yao You, and John Bohannon.  Babybear: Cheap inference triage for expensive language models, 2022.  URL https://arxiv.org/abs/2205.11747.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Larsson et al. [2017] Gustav Larsson, Michael Maire, and Gregory Shakhnarovich.  Fractalnet: Ultra-deep neural networks without residuals.  In _ICLR_ , 2017.
  * LeCun et al. [1989] Yann LeCun, John Denker, and Sara Solla.  Optimal brain damage.  In D. Touretzky, editor, _Advances in Neural Information Processing Systems_ , volume 2. Morgan-Kaufmann, 1989.  URL https://proceedings.neurips.cc/paper_files/paper/1989/file/6c9882bbac1c7093bd25041881277658-Paper.pdf.
  * LeCun et al. [1998] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Liu et al. [2015] Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Marianna Penksy.  Sparse convolutional neural networks.  In _2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 806–814, 2015.  doi: 10.1109/CVPR.2015.7298681.
  * Liu et al. [2020] Weijie Liu, Peng Zhou, Zhe Zhao, Zhiruo Wang, Haotang Deng, and Qi Ju.  FastBERT: a self-distilling bert with adaptive inference time.  In _Proceedings of ACL 2020_ , 2020.
  * Madras et al. [2018] David Madras, Toniann Pitassi, and Richard Zemel.  Predict responsibly: Improving fairness and accuracy by learning to defer.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NeurIPS’18, page 6150–6160, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Mamou et al. [2022] Jonathan Mamou, Oren Pereg, Moshe Wasserblat, and Roy Schwartz.  TangoBERT: Reducing inference cost by using cascaded architecture, 2022\.  URL http://arxiv.org/abs/2204.06271.
  * Mozannar and Sontag [2020] Hussein Mozannar and David Sontag.  Consistent estimators for learning to defer to an expert.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 7076–7087. PMLR, 13–18 Jul 2020.
  * Narasimhan et al. [2022] Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya Krishna Menon, Ankit Singh Rawat, and Sanjiv Kumar.  Post-hoc estimators for learning to defer to an expert.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=_jg6Sf6tuF7.
  * Narayan et al. [2022] Taman Narayan, Heinrich Jiang, Sen Zhao, and Sanjiv Kumar.  Predicting on the edge: Identifying where a larger model does better, 2022\.  URL https://arxiv.org/abs/2202.07652.
  * Nguyen et al. [2015] Anh Nguyen, Jason Yosinski, and Jeff Clune.  Deep neural networks are easily fooled: High confidence predictions for unrecognizable images.  In _2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 427–436, 2015.  doi: 10.1109/CVPR.2015.7298640.
  * Ni et al. [2019] Chenri Ni, Nontawat Charoenphakdee, Junya Honda, and Masashi Sugiyama.  On the calibration of multiclass classification with rejection.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 2582–2592, 2019.
  * Niculescu-Mizil and Caruana [2005] Alexandru Niculescu-Mizil and Rich Caruana.  Predicting good probabilities with supervised learning.  In _Proceedings of the 22nd International Conference on Machine Learning_ , ICML ’05, page 625–632, New York, NY, USA, 2005. Association for Computing Machinery.  ISBN 1595931805.  doi: 10.1145/1102351.1102430.  URL https://doi.org/10.1145/1102351.1102430.
  * Panda et al. [2016] Priyadarshini Panda, Abhronil Sengupta, and Kaushik Roy.  Conditional deep learning for energy-efficient and enhanced pattern recognition.  In _Proceedings of the 2016 Conference on Design, Automation & Test in Europe_, DATE ’16, page 475–480, San Jose, CA, USA, 2016. EDA Consortium.  ISBN 9783981537062.
  * Quinonero-Candela et al. [2009] Joaquin Quinonero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D. Lawrence.  _Dataset shift in machine learning_.  MIT Press, 2009.  ISBN 9780262170055.
  * Radford and Narasimhan [2018] Alec Radford and Karthik Narasimhan.  Improving language understanding by generative pre-training, 2018.
  * Radford et al. [2019] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners, 2019.
  * Raffel et al. [2020] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21:140:1–140:67, 2020.  URL http://jmlr.org/papers/v21/20-074.html.
  * Ramaswamy et al. [2018] Harish G. Ramaswamy, Ambuj Tewari, and Shivani Agarwal.  Consistent algorithms for multiclass classification with an abstain option.  _Electronic Journal of Statistics_ , 12(1):530 – 554, 2018.  doi: 10.1214/17-EJS1388.
  * Rawat et al. [2021] Ankit Singh Rawat, Manzil Zaheer, Aditya Krishna Menon, Amr Ahmed, and Sanjiv Kumar.  When in doubt, summon the titans: Efficient inference with large models, 2021.
  * Saberian and Vasconcelos [2014] Mohammad Saberian and Nuno Vasconcelos.  Boosting algorithms for detector cascade learning.  _The Journal of Machine Learning Research_ , 15(1):2569–2605, 2014.
  * Saberian and Vasconcelos [2010] Mohammad J. Saberian and Nuno Vasconcelos.  Boosting classifier cascades.  In _NeurIPS_ , pages 2047–2055, 2010.  URL http://papers.nips.cc/paper/4033-boosting-classifier-cascades.
  * Samuel et al. [2021] Dvir Samuel, Yuval Atzmon, and Gal Chechik.  From generalized zero-shot learning to long-tail with class descriptors.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , 2021.
  * Sandler et al. [2018] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4510–4520, 2018.
  * Scardapane et al. [2020] Simone Scardapane, Michele Scarpiniti, Enzo Baccarelli, and Aurelio Uncini.  Why should we add early exits to neural networks?  _Cognitive Computation_ , 12:954–966, 2020.
  * Schwartz et al. [2019] Roy Schwartz, Jesse Dodge, Noah A. Smith, and Oren Etzioni.  Green AI.  _CoRR_ , abs/1907.10597, 2019.  URL http://arxiv.org/abs/1907.10597.
  * Schwartz et al. [2020] Roy Schwartz, Gabriel Stanovsky, Swabha Swayamdipta, Jesse Dodge, and Noah A. Smith.  The right tool for the job: Matching model and instance complexities.  In _Proc. of ACL_ , 2020.
  * Shafer and Vovk [2008] Glenn Shafer and Vladimir Vovk.  A tutorial on conformal prediction.  _Journal of Machine Learning Research_ , 9(12):371–421, 2008.  URL http://jmlr.org/papers/v9/shafer08a.html.
  * Streeter [2018] Matthew Streeter.  Approximation algorithms for cascading prediction models.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 4752–4760. PMLR, 10–15 Jul 2018.
  * Tan and Le [2019] Mingxing Tan and Quoc Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  In _International conference on machine learning_ , pages 6105–6114. PMLR, 2019.
  * Teerapittayanon et al. [2016] Surat Teerapittayanon, Bradley McDanel, and H. T. Kung.  Branchynet: Fast inference via early exiting from deep neural networks.  In _23rd International Conference on Pattern Recognition, ICPR 2016, Cancún, Mexico, December 4-8, 2016_ , pages 2464–2469. IEEE, 2016\.
  * Thulasidasan et al. [2019] Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff Bilmes, Gopinath Chennupati, and Jamal Mohd-Yusof.  Combating label noise in deep learning using abstention.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 6234–6243, Long Beach, California, USA, 09–15 Jun 2019. PMLR.
  * Trapeznikov and Saligrama [2013] Kirill Trapeznikov and Venkatesh Saligrama.  Supervised sequential classification under budget constraints.  In Carlos M. Carvalho and Pradeep Ravikumar, editors, _Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics_ , volume 31 of _Proceedings of Machine Learning Research_ , pages 581–589, Scottsdale, Arizona, USA, 29 Apr–01 May 2013\. PMLR.
  * Varshney and Baral [2022] Neeraj Varshney and Chitta Baral.  Model cascading: Towards jointly improving efficiency and accuracy of nlp systems.  _arXiv preprint arXiv:2210.05528_ , 2022.
  * Veniat and Denoyer [2018] Tom Veniat and Ludovic Denoyer.  Learning time/memory-efficient deep architectures with budgeted super networks.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 3492–3500, 06 2018.  doi: 10.1109/CVPR.2018.00368.
  * Viola and Jones [2001] P. Viola and M. Jones.  Rapid object detection using a boosted cascade of simple features.  In _Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001_ , volume 1, pages I–I, 2001\.  doi: 10.1109/CVPR.2001.990517.
  * Vu et al. [2020] T. Vu, M. Eder, T. Price, and J. Frahm.  Any-width networks.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , pages 3018–3026, Los Alamitos, CA, USA, jun 2020\. IEEE Computer Society.  doi: 10.1109/CVPRW50498.2020.00360.  URL https://doi.ieeecomputersociety.org/10.1109/CVPRW50498.2020.00360.
  * Wallace and Dahabreh [2012] Byron C. Wallace and Issa J. Dahabreh.  Class probability estimates are unreliable for imbalanced data (and how to fix them).  In _2012 IEEE 12th International Conference on Data Mining_ , pages 695–704, 2012.  doi: 10.1109/ICDM.2012.115.
  * Wang et al. [2022] Xiaofang Wang, Dan Kondratyuk, Eric Christiansen, Kris M. Kitani, Yair Movshovitz-Attias, and Elad Eban.  Wisdom of committees: An overlooked approach to faster and more accurate models.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=MvO2t0vbs4-.
  * Wang et al. [2018] Xin Wang, Yujia Luo, Daniel Crankshaw, Alexey Tumanov, Fisher Yu, and Joseph E. Gonzalez.  IDK cascades: Fast deep learning by learning not to overthink.  In Amir Globerson and Ricardo Silva, editors, _Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018_ , pages 580–590. AUAI Press, 2018.
  * Xin et al. [2020a] Ji Xin, Rodrigo Nogueira, Yaoliang Yu, and Jimmy Lin.  Early exiting BERT for efficient document ranking.  In _Proceedings of SustaiNLP: Workshop on Simple and Efficient Natural Language Processing_ , pages 83–88, Online, November 2020a. Association for Computational Linguistics.
  * Xin et al. [2020b] Ji Xin, Raphael Tang, Jaejun Lee, Yaoliang Yu, and Jimmy Lin.  DeeBERT: Dynamic early exiting for accelerating BERT inference.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2246–2251, Online, July 2020b. Association for Computational Linguistics.  doi: 10.18653/v1/2020.acl-main.204.  URL https://aclanthology.org/2020.acl-main.204.
  * Zhang and Viola [2008] Cha Zhang and Paul Viola.  Multiple-instance pruning for learning efficient cascade detectors.  In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, _Advances in Neural Information Processing Systems_ , volume 20. Curran Associates, Inc., 2008.
  * Zhou et al. [2020] Wangchunshu Zhou, Canwen Xu, Tao Ge, Julian McAuley, Ke Xu, and Furu Wei.  BERT loses patience: Fast and robust inference with early exit.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 18330–18341. Curran Associates, Inc., 2020.
  * Zilberstein [1996] Shlomo Zilberstein.  Using anytime algorithms in intelligent systems.  _AI Magazine_ , 17(3):73, Mar. 1996.  doi: 10.1609/aimag.v17i3.1232.

##

When Does Confidence-Based Cascade Deferral Suffice?

Appendix

###  Appendix A Proofs

####  A.1 Proof of Proposition 3.1

###### Proof of Proposition 3.1.

The risk in (1) can be written as

$\displaystyle R(r;h^{(1)},h^{(2)})$ $\displaystyle=\mathbb{P}(y\neq
h^{(1)}(x),r(x)=0)+\mathbb{P}(y\neq
h^{(2)}(x),r(x)=1)+c\cdot\mathbb{P}(r(x)=1)$
$\displaystyle=\mathbb{E}\left[1[y\neq h^{(1)}(x)]\cdot 1[r(x)=0]+1[y\neq
h^{(2)}(x)]\cdot 1[r(x)=1]+c1[r(x)=1]\right]$
$\displaystyle=\mathbb{E}\left[1[y\neq
h^{(1)}(x)]\cdot\left(1-1[r(x)=1]\right)+1[y\neq h^{(2)}(x)]\cdot
1[r(x)=1]+c1[r(x)=1]\right]$ $\displaystyle=\mathbb{P}(y\neq
h^{(1)}(x))+\mathbb{E}\left[-1[y\neq h^{(1)}(x)]\cdot 1[r(x)=1]+1[y\neq
h^{(2)}(x)]\cdot 1[r(x)=1]+c1[r(x)=1]\right]$ $\displaystyle=\mathbb{P}(y\neq
h^{(1)}(x))+\mathbb{E}_{x}1[r(x)=1]\mathbb{E}_{y|x}\left[1[y\neq
h^{(2)}(x)]-1[y\neq h^{(1)}(x)]+c\right]$ $\displaystyle=\mathbb{P}(y\neq
h^{(1)}(x))+\mathbb{E}_{x}1[r(x)=1]\mathbb{E}_{y|x}\left[1[y=h^{(1)}(x)]-1[y=h^{(2)}(x)]+c\right]$
$\displaystyle=\mathbb{P}(y\neq
h^{(1)}(x))+\mathbb{E}_{x}1[r(x)=1]\cdot\left[\eta_{h^{(1)}(x)}(x)-\eta_{h^{(2)}(x)}(x)+c\right],$

where we define
$\eta_{y^{\prime}}(x)\stackrel{{\scriptstyle.}}{{=}}\mathbb{P}(y=y^{\prime}\mid
x)$. Thus, it is optimal to defer when

$\displaystyle r(x)=1$
$\displaystyle\iff\eta_{h^{(1)}(x)}(x)-\eta_{h^{(2)}(x)}(x)+c<0$
$\displaystyle\iff\eta_{h^{(2)}(x)}(x)-\eta_{h^{(1)}(x)}(x)>c.$

∎

####  A.2 Proof of Corollary 3.2

###### Proof of Corollary 3.2.

For fixed $h^{(1)},h^{(2)}$, we have already computed the Bayes-optimal
rejector $r^{*}$. Let
$\alpha(x)\stackrel{{\scriptstyle.}}{{=}}\eta_{h^{(1)}(x)}(x)-\eta_{h^{(2)}(x)}(x)+c$.
Plugging $r^{*}$ into the risk results in Bayes-risk

$\displaystyle R(r^{*};h^{(1)},h^{(2)})$ $\displaystyle=\mathbb{P}(y\neq
h^{(1)}(x))+\mathbb{E}_{x}1\left[r^{*}(x)=1\right]\cdot\alpha(x).$

The excess risk for an arbitrary $r$ is thus

$\displaystyle R(r;h^{(1)},h^{(2)})-R(r^{*};h^{(1)},h^{(2)})$
$\displaystyle=\mathbb{E}_{x}\left[1\left[r(x)=1\right]-1\left[\alpha(x)<0\right]\right]\cdot\alpha(x).$

∎

####  A.3 Proof of Lemma 4.1

We start with Lemma A.1 which will help prove Lemma 4.1.

######  Lemma A.1.

Given two base classifiers $h^{(1)},h^{(2)}\colon\mathscr{X}\to[L]$, two
deferral rules $r_{1},r_{2}:\mathscr{X}\to\\{0,1\\}$ yield the same accuracy
for the cascade if and only if
$\mathbb{E}\left(r_{1}(x)\beta(x)\right)=\mathbb{E}\left(r_{2}(x)\beta(x)\right)$,
where
$\beta(x)\stackrel{{\scriptstyle.}}{{=}}\eta_{h^{(2)}(x)}(x)-\eta_{h^{(1)}(x)}(x)$.

###### Proof.

For a deferral rule $r$, by definition, the accuracy is given by

$\displaystyle A(r)$
$\displaystyle=\mathbb{E}_{(x,y)}\left[\boldsymbol{1}[h^{(1)}(x)=y]\cdot(1-r(x))+\boldsymbol{1}[h^{(2)}(x)=y]\cdot
r(x)\right]$
$\displaystyle=\mathbb{P}(h^{(1)}(x)=y)+\mathbb{E}\left[r(x)\cdot\left(\boldsymbol{1}[h^{(2)}(x)=y]-\boldsymbol{1}[h^{(1)}(x)=y]\right)\right]$
$\displaystyle=\mathbb{P}(h^{(1)}(x)=y)+\mathbb{E}_{x}r(x)\mathbb{E}_{y|x}\left[\boldsymbol{1}[h^{(2)}(x)=y]-\boldsymbol{1}[h^{(1)}(x)=y]\right]$
$\displaystyle=\mathbb{P}(h^{(1)}(x)=y)+\mathbb{E}_{x}r(x)\cdot\left(\eta_{h^{(2)}(x)}(x)-\eta_{h^{(1)}(x)}(x)\right).$

Given two deferral rules $r_{1},r_{2}$,
$A(r_{1})=A(r_{2})\iff\mathbb{E}\left(r_{1}(x)\beta(x)\right)=\mathbb{E}\left(r_{2}(x)\beta(x)\right)$
where
$\beta(x)\stackrel{{\scriptstyle.}}{{=}}\eta_{h^{(2)}(x)}(x)-\eta_{h^{(1)}(x)}(x)$.
∎

We are ready to prove Lemma 4.1.

###### Proof of Lemma 4.1.

Recall the confidence-based deferral rule and the Bayes-optimal rule are
respectively

$\displaystyle r_{\mathrm{conf}}(x)$
$\displaystyle=\boldsymbol{1}\left[\eta_{h^{(1)}(x)}(x)<c^{\prime}\right],$
$\displaystyle r^{*}(x)$
$\displaystyle=\boldsymbol{1}\left[\eta_{h^{(1)}(x)}(x)-\eta_{h^{(2)}(x)}(x)<c\right].$

For brevity, we use $\eta_{i}(x)$ and $\eta_{h^{(i)}(x)}(x)$ interchangeably.
Define real-valued random variables
$z\stackrel{{\scriptstyle.}}{{=}}\eta_{1}(x)$, and
$z^{*}\stackrel{{\scriptstyle.}}{{=}}\eta_{1}(x)-\eta_{2}(x)$ where
$x\sim\mathbb{P}_{x}$. Let
$\rho(c^{\prime})\stackrel{{\scriptstyle.}}{{=}}\mathbb{E}\left(\boldsymbol{1}\left[\eta_{1}(x)<c^{\prime}\right]\right)=\mathbb{P}\left(\eta_{1}(x)<c^{\prime}\right)$
be the deferral rate of the confidence-based deferral rule with threshold
$c^{\prime}$. Similarly, define
$\rho^{*}(c)\stackrel{{\scriptstyle.}}{{=}}\mathbb{E}(\boldsymbol{1}\left[\eta_{1}(x)-\eta_{2}(x)<c\right]).$
Let $\gamma_{\alpha},\gamma_{\alpha}^{*}$ be the $\alpha$-quantile of the
distributions of $z$ and $z^{*}$, respectively. By definition,
$\rho(\gamma_{\alpha})=\rho^{*}(\gamma_{\alpha}^{*})=\alpha$.

Let $A(r,c^{\prime})$ denote the accuracy of the cascade with the deferral
rule $r$ and the deferral threshold $c^{\prime}$. Formally, the deferral curve
of $r_{\mathrm{conf}}$ is the set of deferral rate-accuracy tuples
$\\{(\rho(c^{\prime}),A(r_{\mathrm{conf}},c^{\prime}))\mid
c^{\prime}\in[0,1]\\}$. The same deferral curve may be generated with
$\\{(\alpha,A(r_{\mathrm{conf}},\gamma_{\alpha}))\mid\alpha\in[0,1]\\}$.
Similarly, for the Bayes-optimal rule, the deferral curve is defined as
$\\{(\alpha,A(r^{*},\gamma_{\alpha}^{*})\mid\alpha\in[0,1]\\}$.

To show that the two deferral rules produce the same deferral curve, we show
that $A(r_{\mathrm{conf}},\gamma_{\alpha})=A(r^{*},\gamma_{\alpha}^{*})$ for
any $\alpha\in[0,1]$. By Lemma A.1, this is equivalent to showing that

$\displaystyle\mathbb{E}\left(\boldsymbol{1}[\eta_{1}(x)<\gamma_{\alpha}]\cdot\beta(x)\right)$
$\displaystyle=\mathbb{E}\left(\boldsymbol{1}[\eta_{1}(x)-\eta_{2}(x)<\gamma_{\alpha}^{*}]\cdot\beta(x)\right),$
(7)

where $\beta(x)\stackrel{{\scriptstyle.}}{{=}}\eta_{2}(x)-\eta_{1}(x)$.

Suppose that $\eta_{1}(x)$ and $\eta_{1}(x)-\eta_{2}(x)$ produce the same
ordering over instances $x\in\mathscr{X}$. This means that for any
$x\in\mathscr{X}$ and $\alpha\in[0,1]$,
$\eta_{1}(x)<\gamma_{\alpha}\iff\eta_{1}(x)-\eta_{2}(x)<\gamma_{\alpha}^{*}$.
Thus, (7) holds. ∎

###  Appendix B Amount of Compute Used for Experiments

There are two types of models involved in all experiments: (1) base
classifiers (i.e., $h^{(1)}$ and $h^{(2)}$), and (2) post-hoc model. For post-
hoc model training and evaluation, we use one Nvidia V100 GPU. As discussed in
Section C.2, our post-hoc model is only a small MLP model with only two hidden
layers. In each experiment reported in the main text, training one post-hoc
model for 20 epochs only takes a few minutes. For training and evaluating a
post-hoc model, a GPU is not needed.

For training of base classifiers, the amount of compute varies depending on
the dataset and model architecture. This is summarized in the following table.
In the following table, a GPU always refers to an Nvidia V100 GPU, and a TPU
always refers to a Google Cloud TPU v3.111Google Cloud TPU v3:
https://cloud.google.com/tpu/docs/system-architecture-tpu-vm.

Dataset | Model | Devices |  Approximate Training Time
---|---|---|---
CIFAR 100 | CIFAR ResNet 8 |  $8\times$ GPUs |  12m (batch size: 1024, 256 epochs)
CIFAR 100 | CIFAR ResNet 14 |  $8\times$ GPUs |  20m (batch size: 1024, 256 epochs)
CIFAR 100 | CIFAR ResNet 56 |  $8\times$ GPUs |  20m (batch size: 1024, 256 epochs)
ImageNet | MobileNet V2 |  $8\times$ TPUs |  7h (batch size: 64, 90 epochs)
ImageNet | EfficientNet B0 |  $8\times$ TPUs |  4h (batch size: 1024, 90 epochs)

###  Appendix C Experimental Setup: Hyper-parameters

####  C.1 Training of Models in a Cascade

We describe hyperparameters we used for training all base models (i.e.,
$h^{(1)}$ and $h^{(2)}$). In the following table, BS denotes batch size, and
schedule refers to learning rate schedule.

Dataset | Model | LR | Schedule | Epochs | BS
---|---|---|---|---|---
Standard ImageNet | MobileNet V2 | 0.05 | anneal | 90 | 64
| EfficientNet B0 | 0.1 | cosine | 90 | 1024
ImageNet Dog (specialist) | EfficientNet B0 | 0.1 | cosine | 90 | 512
CIFAR 100 | CIFAR ResNet 8 | 1.0 | anneal | 256 | 1024
| CIFAR ResNet 14 | 1.0 | anneal | 256 | 1024
| CIFAR ResNet 56 | 1.0 | anneal | 256 | 1024

We use SGD with momentum as the optimisation algorithm for all models. For
annealing schedule, the specified learning rate (LR) is the initial rate,
which is then decayed by a factor of ten after each epoch in a specified list.
For CIFAR100, these epochs are 15, 96, 192 and 224. For ImageNet, these epochs
are 5, 30, 60, and 80. In the above table, CIFAR 100 includes the standard
CIFAR 100 classification problem, CIFAR 100 with label noise, and CIFAR 100
with distribution shift as discussed in Figure 2.

####  C.2 Training of Post-hoc Deferral Rules

All post-hoc models $g\colon\mathscr{X}\to\mathbb{R}$ we consider are based on
a lightweight Multi-Layer Perceptron (MLP) that takes as input a small set of
features constructed from probability outputs from model 1. More precisely,
let $p^{(1)}(x)\in\Delta_{L}$ denote all probability outputs from model 1 for
an $L$-class classification problem. Let $v(p^{(1)}(x))\in\mathbb{R}^{D}$ be a
list of features extracted from the probability outputs. In all experiments,
the post-hoc model is $g(x)=\mathrm{MLP}(v(p^{(1)}(x)))$ with $v$ producing
$D=L+11$ features. These features are

  1. 1.

The entropy of $p^{(1)}(x)$.

  2. 2.

Top 10 highest probability values of $p^{(1)}(x)$.

  3. 3.

One-hot encoding of $\arg\max_{y^{\prime}}p^{(1)}_{y^{\prime}}$ (i.e., an
$L$-dimensional binary vector).

For the MLP, let $\mathrm{FC}_{K}$ denote a fully connected layer with $K$
output units without an activation. Let $\mathrm{FC}_{K,f}$ denote a fully
connected layer with $K$ output units with $f$ as the activation. In all
experiments involving post-hoc rules, we use

$\displaystyle
g(x)=(\mathrm{FC}_{1}\circ\mathrm{FC}_{2^{4},\mathrm{ReLU}}\circ\mathrm{FC}_{2^{6},\mathrm{ReLU}}\circ
v\circ p^{(1)})(x),$

where ReLU denotes the Rectified Linear Unit. Note that both the MLP and the
set of input features to $g$ are small. We found that a post-hoc model can
easily overfit to its training set. Controlling its capacity helps mitigate
this issue.

To train $g$, we use Adam [Kingma and Ba, 2014] as the optimisation algorithm
with a constant learning rate of 0.0007 and batch size 128. For CIFAR 100
experiments, we use a held-out set of size 5000 as the training set. For
ImageNet experiments, we use an held-out set of size 10000. We train for 20
epochs. Further, an L2 regularization of weights in each layer in the MLP is
also added to the training objective. We set the regularization weight to
0.001.

###  Appendix D Calibration Analysis

(a) MobileNet V2 and EfficientNet B0 on ImageNet. (b) MobileNet V2 and dog
specialist EfficientNet B0 on ImageNet.

Figure 4: Calibration plots visualising the empirical probability of the event
$h_{1}(x)\neq y\land h_{2}(x)=y$, i.e., the first model predicts incorrectly
and the second model predicts correctly. In settings where confidence-based
deferral performs poorly, the first model’s confidence is a poor predictor of
whether the second model makes a correct prediction: the likelihood of this
event tends to be systematically _over-estimated_.

To further study the performance of confidence-based deferral, Figure 4
presents _calibration plots_ [Niculescu-Mizil and Caruana, 2005, Guo et al.,
2017]. These ideally visualise $\mathbb{P}(y\neq h^{(1)}(x)\land
y=h^{(2)}(x)\mid x\in\mathscr{X}_{q})$ for $q\in[0,1]$, where
$\mathscr{X}_{q}\stackrel{{\scriptstyle.}}{{=}}\\{x\in\mathscr{X}\colon\max_{y^{\prime}}p^{(1)}_{y^{\prime}}(x)=q\\}$
is the set of samples where model 1’s confidence equals $q$. In practice, we
discretise $q$ into $10$ buckets.

These plots reveal that, as expected, model 1’s confidence may be a poor
predictor of when model 1 is wrong but model 2 is right: indeed, it
systematically _over-estimates_ this probability, and thus may result in
erroneously forwarding samples to the second model. This suggests using post-
hoc estimates of when model 1 is wrong, but model 2 is right.

We remark here that in a different context, Narayan et al. [2022] showed that
certain cascades of pre-trained language models may be amenable to confidence-
based deferral: the confidence of the small model can predict samples where
the small model is wrong, but the large model is correct. In this work, we
focus on image classification settings. Generalising our analysis to natural
langauge processing models will be an interesting topic for future study.

###  Appendix E Additional Experimental Results

In this section, we present more experimental results to support our analysis
in Section 4.

####  E.1 When Model 2 is Highly Accurate

Figure 5: Test accuracy vs deferral rate of post-hoc deferral rules (in Table
1) when the second model is highly accurate. We observe that confidence-based
deferral is competitive in this setting.

To illustrate that confidence-based deferral is optimal when the second model
has a constant error probability, we train an MLP model as $h^{(1)}$ and a
CIFAR ResNet 56 as $h^{(2)}$ on the MNIST dataset [LeCun et al., 1998], a well
known 10-class classification problem. The MLP has one hidden layer composed
of two hidden units with a ReLU activation, and a fully connected layer with
no activation function to produce 10 logit scores (for 10 classes). Figure 5
presents our results.

####  E.2 Oracle Curves

Figure 6: Test accuracy vs deferral rate of different plug-in estimates for
the oracle deferral rule in (2) (see Section 3.2). The first model is trained
on all ImageNet classes and the second model specialises on dog classes (i.e.,
and hence has non-uniform errors). In this case, accounting for the label
probability of $h^{(2)}$ (as done by the oracle approaches) can theoretically
improve upon confidence-based deferral.

In this section, we illustrate different plug-in estimates for the oracle
deferral rule in (2) (see Section 3.2). We consider two base models: MobileNet
V2 [Sandler et al., 2018] and EfficientNet B0 [Tan and Le, 2019] as $h^{(1)}$
and $h^{(2)}$, which are trained independently on ImageNet. The second model
is trained on a subset of ImageNet dataset containing only “dog” synset (i.e.,
a dog specialist model). Figure 6 illustrates the performance of confidence-
based deferral along with different plug-in estimates for the oracle deferral
rule.

We see that in this specialist setting, confidence-based deferral is sub-
optimal, with a considerable gap to the oracle curves; this is expected, since
here $\mathbb{P}(y=h^{(2)}(x))$ is highly variable for different $x$. In
particular, $\mathbb{P}(y=h^{(2)}(x))\sim 1$ for dog images, but
$\mathbb{P}(y=h^{(2)}(x))\sim\frac{1}{L-\text{\\#non-dog classes}}$ for other
images. There are 119 classes in the dog synset. Note that all Oracle curves
are theoretical constructs that rely on the true label $y$. They serve as an
upper bound on the performance what we could achieve when we learn post-hoc
deferral rules to imitate them.

####  E.3 Confidence of a Dog-Specialist Model

In this section, we report confidence of the two base models we use in the
ImageNet dog-specialist setting in Figure 6. Recall that $p^{(1)}$ is
MobileNet V2 [Sandler et al., 2018] trained on the full ImageNet dataset (1000
classes), and $p^{(2)}$ is EfficientNet B0 [Tan and Le, 2019] trained only on
the dog synset from ImageNet (119 classes). We show empirical distributions of
$\max_{y^{\prime}}p^{(1)}_{y^{\prime}}(x),\max_{y^{\prime}}p^{(2)}_{y^{\prime}}(x),\max_{y^{\prime\prime}}p^{(2)}_{y^{\prime\prime}}(x)-\max_{y^{\prime}}p^{(1)}_{y^{\prime}}(x),p^{(2)}_{y}(x)-p^{(1)}_{y}(x)$,
and $p^{(2)}_{y}(x)-p^{(1)}_{y}(x)$ in Figure 7, grouped by the category of
each input image (Dog or Non-Dog). These statistics are computed on the test
set of ImageNet dataset, containing 50000 images.

Figure 7: Confidence on ImageNet test set of $p^{(1)}$ (MobileNet V2 trained
on the full ImageNet training set), and $p^{(2)}$ (EfficientNet B0 trained
only on the dog synset).

We observe from the distribution of $\max_{y^{\prime}}p^{(2)}_{y^{\prime}}(x)$
that the specialist EfficientNet B0 is confident on dog images. To the
specialist, non-dog images are out of distribution and so
$\max_{y^{\prime}}p^{(2)}_{y^{\prime}}(x)$ is not a reliable estimate of the
confidence. That is, $p^{(2)}$ can be highly confident on non-dog images. As a
result, a deferral rule based on Relative Confidence
($\max_{y^{\prime\prime}}p^{(2)}_{y^{\prime\prime}}(x)-\max_{y^{\prime}}p^{(1)}_{y^{\prime}}(x)$)
may erroneously route non-dog images to the second model. Thus, for training a
post-hoc model, it is important to consider model 2’s probability of the true
label (i.e., $p_{y}^{(2)}(x)$), which is low when $(x,y)$ is a labeled image
outside the dog synset.

Figure 8: Confidence of MobileNet V2 (trained on the full ImageNet training
set) versus confidence of EfficientNet B0 (trained only on the dog synset).

We further show a scatter plot of confidence of both models in Figure 8. We
observe that there is no clear relationship between
$\max_{y^{\prime}}p^{(1)}_{y^{\prime}}(x)$ and
$\max_{y^{\prime}}p^{(2)}_{y^{\prime}}(x)$.

###  Appendix F Extension to Multi-Model Cascades

One may readily employ post-hoc deferral rules to train multi-model cascades.
Given $K$ classifiers $h^{(1)},\ldots,h^{(K)}$, a simple recipe is to train
$K-1$ deferral rules, with the $k$th rule trained to predict whether or not
$h^{(k)}$ should defer to $h^{(k+1)}$. Each of these individual rules may be
trained with any of the objectives detailed in Table 1. At inference time, one
may invoke these rules sequentially to determine a suitable termination point.

In Figure 9, we present results for a 3-model cascade in the label noise
setting. As with the 2-model case, post-hoc deferral improves significantly
over confidence-based deferral, owing to the latter wastefully deferring on
noisy samples that no model can correctly predict. Here, the relative
inference cost is computed as the relative cost compared to always querying
the large model.

Figure 9: Test accuracy versus deferral rate for a 3-model cascade of
ResNet-8, ResNet-14, ResNet-32 . Results are on CIFAR-100 with targetted noise
on the first 25 classes. As with the 2-model cascade, post-hoc deferral
improves significantly over confidence-based deferral. Here, the relative
inference cost is computed as the relative cost compared to always querying
the large model.

The above can be seen as a particular implementation of the following
generalisation of Proposition 3.1. Suppose we have $K$ classifiers
$h^{(1)},\ldots,h^{(K)}$, with inference costs
$c^{(1)},\ldots,c^{(K)}\in[0,1]$. We assume without loss of generality that
$0=c^{(1)}\leq c^{(2)}\leq\ldots\leq c^{(K)}$, i.e., the costs reflect the
_excess_ cost over querying the first model.

Now consider learning a _selector_ $s\colon\mathscr{X}\to[K]$ that determines
which of the $K$ classifiers is used to make a prediction for
$x\in\mathscr{X}$. Our goal in picking such a selector is to minimise the
standard misclassification accuracy under the chosen classifier, plus an
appropriate inference cost penalty:

$R(s;h^{(1)},\ldots,h^{(K)})\stackrel{{\scriptstyle.}}{{=}}\mathbb{P}(y\neq
h^{(s(x))}(x))+\mathbb{E}{}{[c^{(s(x))}]}.$ (8)

We have the following, which is easily seen to generalise Proposition 3.1.

######  Lemma F.1.

The optimal selector for (8) is given by

$s^{*}(x)=\underset{k\in[K]}{\operatorname*{argmin}}\,\mathbb{P}{(y\neq
h^{(k)}(x))}+c^{(k)}.$ (9)

###### Proof of Lemma F.1.

Observe that

$\displaystyle R(s;{h}^{(1)},\ldots,h^{(K)})$ $\displaystyle=\mathbb{P}(y\neq
h^{(s(x))}(x))+\lambda\cdot\mathbb{E}{}{c^{(s(x))}}$
$\displaystyle=\mathbb{E}_{x}{\mathbb{E}_{y\mid x}{1(y\neq
h^{(s(x))}(x))}+\lambda\cdot c^{(s(x))}}.$

Now suppose we minimise $s$ without any capacity restriction. We may perform
this minimisation pointwise: for any fixed $x\in\mathscr{X}$, the optimal
prediction is thus

$\displaystyle s^{*}(x)$
$\displaystyle=\underset{k\in[K]}{\operatorname*{argmin}}\,\mathbb{E}_{y\mid
x}{1(y\neq h^{(k)}(x))}+\lambda\cdot c^{(k)}.$

∎

When $K=2$, we exactly arrive at Proposition 3.1. For $K>2$, the optimal
selection is the classifier with the best balance between misclassification
error and inference cost.

Lemma F.1 may be seen as a restatement of Trapeznikov and Saligrama [2013,
Theorem 1], which established the Bayes-optimal classifiers for a sequential
classification setting, where each classifier is allowed to invoke a “reject”
option to defer predictions to the next element in the sequence. This
equivalently packs together a standard classifier $h^{(k)}$ and deferral rule
$r^{(k)}$ into a new classifier $\bar{h}^{(k)}$.

###  Appendix G Limitations

In this work, we have identified problem settings where confidence-based
deferral can be sub-optimal. These problem settings are 1. specialist setting,
2. label noise, and 3. distribution shift (see Figure 2 for experimental
results in these settings). These problem settings are not exhaustive.
Identifying other conditions under which confidence-based deferral performs
poorly is an interesting direction for future work. Another interesting topic
worth investigating is finite-sample behaviors of cascades, both with
confidence-based deferral and with post hoc rules.


# Hypertree shrinking
avoiding low degree vertices

Karolína Hylasová 1,2 Tomáš Kaiser 1,3

###### Abstract

The shrinking operation converts a hypergraph into a graph by choosing, from
each hyperedge, two endvertices of a corresponding graph edge. A hypertree is
a hypergraph which can be shrunk to a tree on the same vertex set. Klimošová
and Thomassé [J. Combin. Theory Ser. B 156 (2022), 250–293] proved (as a tool
to obtain their main result on edge-decompositions of graphs into paths of
equal length) that any rank $3$ hypertree $T$ can be shrunk to a tree where
the degree of each vertex is at least $1/100$ times its degree in $T$. We
prove a stronger and a more general bound, replacing the constant $1/100$ with
$1/2k$ when the rank is $k$. In place of entropy compression (used by
Klimošová and Thomassé), we use a hypergraph orientation lemma combined with a
characterisation of edge-coloured graphs admitting rainbow spanning trees.

11footnotetext: Department of Mathematics and European Centre of Excellence
NTIS (New Technologies for the Information Society), University of West
Bohemia, Pilsen, Czech Republic.22footnotetext: E-mail:
<EMAIL_ADDRESS>E-mail<EMAIL_ADDRESS>
##  1 Introduction

It is well known that each graph has an associated matroid. Lorea [5] extended
this association from graphs to hypergraphs; the bases of the matroid
associated with a hypergraph $H^{\prime}$ are the hypertrees in $H^{\prime}$,
i.e., subhypergraphs of $H^{\prime}$ satisfying the following definition. (We
refer to Section 2 for any other necessary definitions.)

A hypergraph $H$ is a _hypertree_ if it is possible to choose two vertices
from each hyperedge in such a way that the chosen pairs, viewed as edges of a
graph on vertex set $V(H)$, form a tree. An equivalent definition may be given
in terms of a Hall-type condition (cf. [3, Theorem 2.2]). The equivalence was
proved by Lovász [6].

The above operation that produces a graph from a hypergraph by choosing a pair
of vertices in each hyperedge will be called _shrinking_. Thus, a hypertree is
a hypergraph which can be shrunk to a tree.

Klimošová and Thomassé [4] derived a result on hypertree shrinking that
preserves vertex degree up to a constant factor, and used it as one of the
tools needed to obtain their main result about decompositions of 3-edge-
connected graphs into paths of equal length. Their lemma on shrinking [4,
Lemma 22] is as follows:

######  Lemma 1.

Let $H$ be a hypertree with hyperedges of size at most three. It is possible
to shrink $H$ to a tree $T$ such that for every vertex $v$ of $H$,

$d_{T}(v)\geq\frac{d_{H}(v)}{100}.$

Lemma 1 is proved using entropy compression, the method devised to prove an
algorithmic version of the Lovász Local Lemma [7].

In this paper, we use a different method to strengthen Lemma 1 in two ways:
first, our version ensures a stronger degree bound, and second, it applies to
hypergraphs with arbitrary size of the hyperedges. In addition, the proof is
conceptually simpler. We prove:

######  Theorem 2.

Let $H$ be a hypertree with hyperedges of size at most $k$. It is possible to
shrink $H$ to a tree $T$ such that for every vertex $v$ of $H$,

$d_{T}(v)\geq\frac{d_{H}(v)}{2k}.$

##  2 Preliminaries

We review some of the basic definitions on hypergraphs. A hypergraph is a pair
$H=(V,E),$ where $V$ is a finite set and $E$ is a set of subsets of $V$. The
elements of $V$ are the vertices of $H$ and the elements of $E$ are the
hyperedges of $H.$

The _rank_ of a hypergraph $H$ is the maximum size of a hyperedge of $H$. If
all hyperedges of $H$ have size exactly $k$, then $H$ is _$k$ -uniform_. The
number of hyperedges of $H$ containing a vertex $v\in V$ is the degree of $v$
and is denoted by $d_{H}(v).$

A hypergraph is _simple_ if it does not contain _loops_ (i.e., hyperedges of
size 1) nor repeated hyperedges (distinct hyperedges with identical vertex
sets). All the hypergraphs discussed in this paper will be simple (and we will
henceforth drop this adjective). A hypergraph is connected if for every
nonempty proper subset $X$ of its vertex set, there is a hyperedge
intersecting both $X$ and its complement.

It will be useful in our argument to consider directed hypergraphs, consisting
of a set of hyperarcs on a finite vertex set. A _hyperarc_ is a hyperedge $e$
together with a designated _head_. The other vertices of $e$ are called the
_tails_ of $e$.

The indegree of vertex $v$ in a directed hypergraph $\vec{H}$, denoted by
$d_{\vec{H}}^{IN}(v)$, is the number of hyperarcs whose head is $v$.
Similarly, the outdegree of $v$ (denoted by $d_{\vec{H}}^{OUT}(v)$) is the
number of hyperarcs in which $v$ is a tail. Observe that a hyperarc of size
$k$ contributes to the indegree of exactly one vertex and to the outdegree of
$k-1$ vertices.

##  3 Tools

In the proof of Theorem 2, we will need two main tools. The first one is an
orientation lemma for hypergraphs with lower bounds on the indegrees. The
second one is a characterisation of edge-coloured graphs admitting rainbow
spanning trees, described in the last few paragraphs of this section.
Throughout this section we define $\sum_{v\in X}f(v)$ as $f(X).$

We begin with the topic of hypergraph orientation. A result of Frank, Királyi
and Királyi [2, Lemma 3.3] gives a necessary and sufficient condition for the
existence of an orientation of a hypergraph with prescribed indegrees. We use
it in an equivalent formulation from [1].

######  Lemma 3 ([2]).

Let $H=(V,E)$ be a hypergraph and let $f:V\rightarrow\mathbb{Z}^{+}$ be a
mapping of the vertex set $V$ of $H$ into the set of non-negative integers.
Then there is an orientation $\vec{H}$ of $H$ such that
$d^{IN}_{\vec{H}}(v)=f(v)$ for every $v\in V$ if and only if

  1. (i)

$f(V)=e(H),$

  2. (ii)

$f(F)\geq e(F)$ for every $F\subseteq V,$

where $e(F)$ denotes the number of hyperedges in the subset $F\subseteq V$ and
$e(H)$ is the number of all hyperedges in $H$.

What we actually need is a sufficient condition for the existence of an
orientation where the indegree of each vertex satisfies a given lower bound.
This is similar to [1, Lemma 3], except that upper bounds are prescribed in
the latter lemma.111It may seem that in [1], Lemma 3 is formulated for
$d^{OUT}_{\vec{H}}(v)$ rather than $d^{IN}_{\vec{H}}(v)$; this is not the case
since the definitions used in [1] exchange the notions of outdegree and
indegree. For hypergraphs (as opposed to graphs), a version with lower bounds
does not seem to be a trivial consequence of one with upper bounds, but it
turns out to be possible to follow the proof from [1] with suitable
modifications. Below, we give the proof in full detail to make this paper
self-contained.

######  Lemma 4.

Let $H=(V,E)$ be a hypergraph and let $f:V\rightarrow\mathbb{Z}^{+}$ be a
mapping of the vertex set $V$ of $H$ into the set of non-negative integers.
Assume that for every $F\subseteq V$,

$f(F)\leq e^{*}(F),$ (1)

where $e^{*}(F)$ denotes the number of hyperedges incident with $F$. Then
there is an orientation $\vec{H}$ of $H$ such that

$d^{IN}_{\vec{H}}(v)\geq f(v)$ (2)

for every $v\in V.$

###### Proof.

Let $g:V\rightarrow\mathbb{Z}^{+}$ be a mapping such that

  1. (i)

$g(F)\leq e^{*}(F)$ for every $F\subseteq V,$

  2. (ii)

$g(v)\geq f(v)$ for every $v\in V,$

  3. (iii)

$g(V)$ is the maximum among all functions that satisfy (i) and (ii).

We will verify properties (i) and (ii) of Lemma 3 for the function $g$. In
other words, we will show that

$g(V)=e^{*}(H)=e(H),$ (3)

where $e(H)$ denotes the number of hyperedges of the hypergraph $H$, and that
$g(F)\geq e(F)$ for every $F\subseteq V.$ Then, by Lemma 3, there is an
orientation $\vec{H}$ of $H$ for which $d^{IN}_{\vec{H}}(v)=g(v)\geq f(v)$ for
every $v\in V.$

Let $X\subseteq V$ be a set with maximum cardinality for which
$g(X)=e^{*}(X).$ Firstly, we want to show that $V\backslash X$ does not
contain any vertex $w$ with the function $g(w)$ equal to the degree of $w$ in
the hypergraph $H.$

It is possible that $X$ is an empty set. If $X=V$ then we are done, so assume
that $|X|<|V|.$ If $w$ is a vertex in $V\backslash X$ for which
$g(w)=d_{H}(v),$ then by the maximality of $|X|$ we obtain

$\displaystyle\begin{split}g(X\cup\\{w\\})&<e^{*}(X\cup\\{w\\})\leq
e^{*}(X)+e^{*}(\\{w\\})=\\\
&=g(X)+d_{H}(w)=g(X)+g(w)=g(X\cup\\{w\\}),\end{split}$

which is a contradiction. Therefore $V\backslash X$ contains no such vertex
$w.$

Furthermore, we will prove that there exists a function $h(v)$ which satisfies
properties (i) and (ii), but for every vertex $v\in V$ it holds that
$h(v)>g(v)$ which contradicts the maximality of $g(V).$

Let $z$ be a vertex in $V\backslash X$ and let $h:v\rightarrow\mathbb{Z}^{+}$
be a mapping such that $h(v)=g(v)$ for all $v\in V\backslash\\{z\\}$ and
$h(z)=g(z)+1.$ Suppose that there exists a subset $F\subseteq V$ such that
$h(F)>e^{*}(F).$ Then $z\in F$ and

$e^{*}(F)\geq g(F)=h(F)-1>e^{*}(F)-1,$

which implies that $g(F)=e^{*}(F).$ But by the maximality of $|X|$ and because
$F$ is not contained in $X,$ as $z\in F$ and $z\in V\backslash X,$ we get that

$\displaystyle\begin{split}g(F\cup X)&=g(F)+g(X)-g(F\cap X)\geq\hskip
18.49411pt\\\ &\geq e^{*}(F)+e^{*}(X)-e^{*}(F\cap X)\geq e^{*}(F\cup
X)>g(F\cup X),\end{split}$ (4)

which is again a contradiction.222We would like to mention that in the
corresponding part of the proof in [1], the inequality analogous to (4) is
slightly incomplete, but this does not affect the validity of the subsequent
arguments.

Therefore, for all subsets $F\subseteq V$ it holds that $h(F)\leq e^{*}(F).$
Also for every vertex $v\in V$ it is true that $h(v)\geq g(v)\geq f(v),$ so
the function $h$ satisfies properties (i) and (ii). However, $h(V)=g(V)+1,$
i.e. $h(V)>g(V)$ which is a contradiction with the maximality of $g(V).$
Hence, property (i) from Lemma 3 holds.

Let $F^{\prime}=V\backslash F$ for every $F\subseteq V.$ We know that
$g(V)=e(H)$ and it is also true that

$g(V)-g(F)=e(H)-g(F)$

Therefore,

$e(H)-g(F)=g(F^{\prime})\leq e^{*}(F^{\prime})=e(H)-g(F).$

From this we get that $g(F)\geq e(F)$ for every $F\subseteq V,$ i.e., property
(ii) from Lemma 3 holds as well. ∎

The second main tool which we will use to prove Theorem 2 is a necessary and
sufficient condition for an edge-coloured graph to contain a rainbow spanning
tree.

Let $G$ be a graph with a (not necessarily proper) edge colouring. A subgraph
of $G$ is _rainbow_ if it does not contain two edges with the same color. The
following necessary and sufficient condition for the existence of a rainbow
spanning tree has been derived in [9] and, independently, in [8, Section
41.1a].

######  Theorem 5 ([9]).

Let $G$ be a (possibly improperly) edge-coloured graph of order $n$. There
exists a rainbow spanning tree of $G$ if and only if

$\begin{split}&\textrm{for any set of $r$ colours $(0\leq r\leq n-2)$, the
removal of all edges coloured}\\\ &\textrm{with these $r$ colours from $G$
results in a graph with at most $r+1$}\\\ &\textrm{components.}\end{split}$
(5)

Observe that the case $r=0$ of condition (5) corresponds to $G$ being
connected.

##  4 Shrinking hypertrees

In this section, we prove Theorem 2. We begin with an application of Lemma 4
concerning a specific lower bound for the indegrees in an orientation of a
hypergraph.

######  Lemma 6.

Let $H=(V,E)$ be a hypergraph of rank at most $k$. There exists an orientation
$\vec{H}$ of $H$ in which

$d^{IN}_{\vec{H}}(v)\geq\left\lfloor\frac{d_{H}(v)}{k}\right\rfloor$

for every vertex $v\in V.$

###### Proof.

We apply Lemma 4 with $f(v)=\lfloor d_{H}(v)/k\rfloor$. For a set $F\subseteq
V$ of vertices of $H$, we verify condition (1). Clearly,

$\sum_{v\in F}f(v)\leq\sum_{v\in F}\frac{d_{H}(v)}{k}.$ (6)

Each hyperedge $e$ of $H$ contributes at most $1$ to the degree of a specific
vertex $v$, and since $|e|\leq k$, its total contribution to the right hand
side of (6) is at most $k\cdot\frac{1}{k}=1$. It follows that the right hand
side is at most $e^{*}(F)$, i.e., (1) holds. ∎

Let $H$ be a hypertree of rank $k$, and let $\vec{H}$ be the orientation from
Lemma 6. We construct an edge-coloured graph $G(\vec{H})$ on the vertex set of
$\vec{H}$ by the following rule: for each hyperarc $\vec{e}$ of $\vec{H}$, add
to $G$ a star whose center is the head of $e$ and whose leaves are the tails
of $e$. Furthermore, all the edges of this star have the same colour, which
differs from the colours used for the other stars.

We claim that $G(\vec{H})$ has a rainbow spanning tree. To prove this, we need
to verify condition (5) of Theorem 5. Consider first a simple variant of the
above construction: let the graph $G_{H}$ be obtained by adding, for each
hyperedge $e$ of $H$, a complete graph on the vertex set of $e$. Observe that
since $H$ is a hypertree, $G_{H}$ has a rainbow spanning tree. Consequently,
condition (5) holds for $G_{H}$.

Now in the construction of $G(\vec{H})$, we used stars in place of the
complete subgraphs. It is, however, easy to see that this replacement has no
effect on the validity of condition (5): indeed, if instead of each complete
subgraph we take any connected subgraph on the same vertex set, then their
union has the same number of components in each case, and so the validity of
condition (5) remains without change.

Thus, $G(\vec{H})$ has a rainbow spanning tree $T^{\prime}$ as well. Note that
for each hyperedge $e$ of $H$, $T^{\prime}$ has one edge $e^{\prime}$
corresponding to $e$, namely the edge selected from the star corresponding to
an orientation $\vec{e}$ of $e$. Moreover, the head of $\vec{e}$ is one of the
endvertices of $e^{\prime}$.

By the above, if $v$ is a vertex of $H$, then the degree of $v$ in
$T^{\prime}$ is at least the indegree of $v$ in $\vec{H}$ — that is, at least
$\lfloor d_{H}(v)/k\rfloor$. If $d_{H}(v)\geq k$, then we have

$d_{T^{\prime}}(v)\geq\frac{d_{H}(v)}{2k}$ (7)

since, clearly, $\left\lfloor x\right\rfloor\geq x/2$ for all real $x\geq 1$.
On the other hand, if $d_{H}(v)<k$, then (7) holds as well, because the right
hand side is smaller than $1/2$ while the degree of $v$ in the tree
$T^{\prime}$ is at least $1$. Thus, (7) holds for all vertices, and we have
found the required shrinking of $H$. This concludes the proof of Theorem 2.

## References

  * [1] Y. Caro and A. Hansberg  “Degrees in oriented hypergraphs and Ramsey $p$-chromatic number”  In _The Electronic Journal of Combinatorics_ 19, 2012, pp. P16
  * [2] A. Frank, T. Király and Z. Király  “On the orientation of graphs and hypergraphs”  In _Discrete Applied Mathematics_ 131, 2003, pp. 385–400
  * [3] A. Frank, T. Király and M. Kriesell  “On decomposing a hypergraph into $k$ connected sub-hypergraphs”  In _Discrete Applied Mathematics_ 131, 2003, pp. 373–383
  * [4] T. Klimošová and S. Thomassé  “Edge-partitioning 3-edge-connected graphs into paths”  In _Journal of Combinatorial Theory, Series B_ 156, 2022, pp. 250–293
  * [5] M. Lorea  “Hypergraphes et matroides”  In _Cahiers du Centre d’études de recherche operationelle_ 17, 1975, pp. 289–291
  * [6] L. Lovász  “A generalization of Kőnig’s theorem”  In _Acta Mathematica Academiae Scientiarum Hungaricae_ 21, 1970, pp. 443–446
  * [7] R.. Moser and G. Tardos  “A constructive proof of the general Lovász local lemma”  In _Journal of the ACM_ 57, 2010, pp. Art. 11pp. 1–15
  * [8] A. Schrijver  “Combinatorial Optimization”  Springer, 2003
  * [9] K. Suzuki  “A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph”  In _Graphs and Combinatorics_ 22, 2006, pp. 261–269