When Does Confidence-Based Cascade Deferral Suffice?
Authors: Wittawat Jitkrittum
Neha Gupta
Aditya Krishna Menon
Harikrishna Narasimhan
Ankit Singh Rawat
Sanjiv Kumar
Venue: NeurIPS 2023 poster (2023)
Keywords: cascades
deferral rules
adaptive computation
model confidence
TL;DR: We identify conditions under which confidence-based cascades may suceed or fail, present a theoretically optimal deferral rule, and study post hoc deferral schemes to improve upon confidence-base deferral.

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.

When Does Confidence-Based Cascade Deferral Suffice?
Wittawat Jitkrittum
Neha Gupta
Aditya Krishna Menon
Harikrishna Narasimhan
Ankit Singh Rawat
Sanjiv Kumar
Google Research, New York
(wittawat, nehagup, adi aditmmkmmnnn, hnarasimhan, ankitsrawat, sanjivk/agoogle.com
Abstract
Cascades are a classical strategy to enable inference cost to vary adaptively across samples, wherein 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 the structure of the cascade c.g., not modelling the errors of downstream models such confidence-basee 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 infidencee-asse 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.
deferral often works remarkably well in practice.
Introduction
Large neural models with several billions of parameters have shown considerable promise in challeng- ing weal-world problems, such as language modelling [57, 58, 3, 59] and image classification [15, 20]. While the quality gains of these models are impressive, they are typically accompanied with a sharp increase in inference time [6. 67]. thus limiting their applicability. Cascades offer one strategy to mitigate this [77, 75, 62, 24], by allowing for faster predictions on "easy" samples. In a nutshell, cascades involve arranging multiple models in 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 's prediction. One may further combine cascades with ensembles trade-off's [22, 80].
to significantly improve accuracy
key ingredient of cascades the choice of deferral rule. The simplest candidate to defer when the current model's s confidence in its prediction is sufficiently low. Popular confidence measures include the maximum predictive probability over all classes [80]. and the entropy of the predictive distribution [31]. Despite being oblivious to the nature of the cascade e.g., not modelling the errors of downstream models such confidence-be deferral works remarkably well in practice [81, 23, 21, 80, 47, 49]. Indeed, it has often been noted that such deferral can perform on-par with
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

more complex modifications to the model training [23, 21, 36). However, the reasons for this success remain unclear; further, is not clear if there are specific practical settings where confidence- deferral may perform poorly [50].
In this paper, we initiate systematic study of the potential limitations of confidence-basedd deferral for cascades. Our findings and contributions are:
(i) We establish novel result characterising the theoretically optimal deferral rule (Proposition 3.1), which for two-model cascade relies on the confidence of both model and model
(ii) In many regular classification tasks where model 2 gives consistent estimate of the true posterior probability, confidence- based deferral is highly competitive. However, we show that in some settings, confidence-basse deferral can be significantly sub-optimal both in theory and practice (54.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 noise, and (3) there is distribution shift between the train and test set.
(iii) Motivated by this, we then study series of post-hoc deferral rules, that seek 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 bonfidence-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
L). and let IP be a distribution over X y. Given training sample S (Zzn yn) In) [N] drawn from IP, multi-class classification seeks classifier h: X + with low misclassification error R(h) = Ply F h(x)). We may parameterise h as hxx) = argmaxyey fy (z) for a scorer f: + R-. In neural models, one expresses fx(x) why ((x) for class weights Wy and embedding function +. It is common to construct probability estimator p: X + A using the softmax transformation, (²)x) x exp(fy(1r).
Fix an instance space X and label space = = [1,
2.1 Cascades and Deferral Rules
Conventional neural models involve a fixed inference cost for any test sample x E 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 [41, 76, 31, 78], stochastic depth [30, 19], network sparsification [44], quantisation [32], pruning [42], and distillation [5, 29, 61]. A complementary strategy is to adaptively lower the inference cost for "easy" samples, while reserving the full cost only for "hard" samples [26, 86, 66, 55, 72, 81, 31, 68, 83, 17, 45, 85, 82).
Cascade models are a classic example of adaptive predictors, which have proven useful in vision tasks such as object detection [77], and have grown increasingly popular in natural language processing [47, 75, 38, 14]. In the vision literature, cascades are often designed for binary classification problems, with lower-level classifiers being used to quickly identify negative samples [4, 84, 63, 10, 13. 70]. A cascade is composed of two components:
collection of base models (typically of non-decreasing inference cost) ii a deferral rule (i.e., a function that decides which model to use for each x E 2).
For any test input, executes the first model, and employs the deferral rulc 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 [74, 36), we focus on a setting where the base models are pre-truined 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 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
simple way to define deferral rule is by thresholding a model's confudence in its prediction.
While there are several means of quantifying and improving such confidence [69, 25, 37, 34], we focus on the maximum predictive probability y(x) = maxy p(y' æ). Specifically, given K trained models, a confidence-based cascade is formed by picking the first model that whose confidence (xx) is sufficiently high [80, 60]. This is made precise in Algorithm I.
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 [80]. In- deed, it has often been noted that such deferral can perform on-par with more complex modifi- cations to the model training [23, 21, 36). How- ever, the reasons for this phenomenon are not unclear there
Algorithm 1 Confidence-based cascades of K classifiers
Input: K 2 classifiers: p())
p(K) : X A thresholds ,(")...,,c ((( E [0. 1]
Input: An input instance x E X
1: for k == 1,2...., K do
well-understood; further, are practical settings where confidence-based cascades are expected to underperform.
2: if maxy Py" (x) (k) then
(k)
3: Predict class 5 argmaxy py (x)
(k)
4: break
To address this, we now formally analyse confidence-based cascades, and explicate their limitations.
5: end if
6: end for
(K) 7: Predict class y = argmax, Py (x)
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-basee deferral (Algorithm I).
3.1 Optimisation Objective
For simplicity, we consider a cascade of K 2 pre-trained classifiers h("), (2(); X yi: our analysis readily generalises to cascades with K > 2 models (see Appendix F). Suppose that the classifiers are based on probability estimators ((1), (2), where for i E (1,2), py (Ir) estimates the probability for class y given x, and h (z) = arg maxy py (z). We do not impose any restrictions on the training procedure or performance of these classifiers. We seek learn a deferral rule r: -> {0, 1) that can decide whether (11 should be used (with r(x) = 0), or (2(2) (with r(x) = =))
(i)
Constrained formulation. 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. Let us assume without loss of generality that (2)) has higher computational cost, and that invoking (2) incurs constant cost > 0. We then seek to find a deferral rule that maximises the predictive accuracy, while invoking (2) sparingly. This can be formulated as the following constrained optimisation problem:
min Pyy # 10 (x), r(x) 0) + Plu 1 (x).
subject to P(r(x)= (1)
for a deferral rate r E [0, 1]. Intuitively, the objective measures the misclassification error only on
samples where the respective classifier's predictions are used; the constraint ensures that 1 (2) is
invoked on at most fraction of samples. It is forwaad to extend this formulation to generic cost-sensitive variants of the predictive accuracy [18]. Equivalent unconstrained risk. Using Lagrangian theory, one may translate (1) into minimizing an cquivalent unconstrained risk. Specifically, under mild distributional assumptions (see e.g., Neyman and Pearson [51]), we can show that for any deferral rate т, there exists deferral cost e 2 0 such that solving (1) is equivalent to minimising the following unconstrained risk:
R(r; (,,,),)))))))))) (2))) = Py + h 0 (x). rzz) 0) + P(y + (z), = 1) c P(r(x) 1). (2)
3

---

Deferral curves and cost-risk curves. As e varies, one may plot the misclassification error of the resulting cascade as function of deferral rate. We will refer to this as the deferral curve. One may similarly compute the cost-risk curve that traces out the optimal cascade risk (2) as a function of c. Both these are equivalent ways of assessing the overall quality of a cascade.
In fact, the two curves have an intimate point-line duality. Any point (T, E)) in deferral curve space where т denotes deferral rate, and E' denotes error can be mapped to the line (c,c.T. + E) c E [0, 1] in cost curve space. Conversely, any point (c, Rt) in cost curve space where e denotes cost, and R denotes risk can be mapped to the line (d, C. d) d [0, 1] in deferral curve space. This is analogous to the correspondence between ROC and cost-risk curves in classification [16]. Following prior work [2, 36], our experiments use deferral curves to compare
methods.
3.2 The Bayes-Optimal Deferral Rule
The Bayes-optimal rule, which minimises the risk R(r; (()), (222)) over all possible deferral rules r: X + {0, 1]. is given below.
Proposition 3.1. Let The (x) = P(y|(z). Then, the Bayes-optimal deferral rule for the risk in (2) is:
(x)) = 1 (x) - (1) >c c),
(3)
(Proof in Appendix A.) Note that for a classifier h, Mh(x) (z) = Ply = h2)]2z) i... the probability that h gives correct prediction for Observe that the randomness here reflects the inherent stochasticity of the labels y for an input æ, i.e., the aleatoric uncertainty [33]. For the purposes of evaluating the
deferral curve, the key quantity is (=) (x) (x) (2)), i.e., the difference in the probability of
correct prediction under each classifier. This is intuitive: it is optimal to defer to h2) if the expected reduction in misclassification error excceds the cost of invoking (2).
The Bayes-optimal deferral rule in (3) is a theoretical construct, which relies on knowledge of the true posterior probability 7j. practice, one 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 axx) = (z)(=) Th2(2) (x) + c. Then, the excess risk an arbitrary is R(r; ((()) R(r"; (1) ( = E. (1(((x) = =) ((((x) < 0)) a(x)]
Intuitively, the above shows that when make deferral decisions that disagree with the Bayes- optimal rule, we are penalised proportional to the difference between the two models' error probability.
3.3 Plug-in Estimators of the Bayes-Optimal Deferral Rule
In practice, may seek to approximate the Bayes-optimal deferral rule r* in (3) with an estimator f. We now present several oracle estimators, which will prove useful in our subsequent analysis.
One-hot oracle. Observe that ny (I) (x)
Eyja [1 y'll. Thus, given test sample (z, v), one may
replace the expectation with the observed label to yield the ideal estimator fl (x) = 1/y/ = v). This results in the rule
for (x) 1 11 113 1ly 1o0 d.
(4)
One intuitive observation is that for high this rule only defers samples with * (z) but (((2) 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 similar reasoning f01. another estimator is given by
f Prub (x) = | (z)
p (x)
(5)
Intuitively Py
(2) (z) (z) can be seen label-dependent correctness score of model on instance

---

Relative confidence. The above oracles rely on the true label y. A more practical plug-estimann is (x) (x) maxy py (x)) which simply uses each model's softmax probabilities. The rationale for this rests upon the assumption that the probability model p(*) is consistent estimate of the true posterior probability so that P(y]z) v (0) (2:) for i [1,2), where (Ir, y) is a labeled example. Thus, (2)))) (2) = IP(h)) = pl (x(0()) = maxy Py (x), resulting in the rule
(1) (x) = max (2) Py (z) max Py (1)
Observe that this deferral decision depends on the confidence of both models, in contrast 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 invoked on every input. Nonetheless, they can inform us about the available headroom to improve confidence-batt based deferral by considering the confidence of the downstream model. As shall be seen in $4, these estimators are useful for deriving objectives to train post hoc deferral rule.
3.4 Relation to Existing Work
The two-model cascade is closely connected to the literature on learning defer expert [46, 48, 9]. Here, the goal is to learn a base classifier (1)) that has the option of invoking an "expert" model (2);; this invocation is controlled by a deferral rule r. Indeed, the risk (2) is a special case of Mozannar and Sontag [48, Equation 21, where the second model is considered be an "expert". Proposition 3.1 is a simple generalisation of Mozannar and Sontag [48, Proposition 21, with the latter assuming c 0. In Appendix F, we generalise Proposition 3.1 to the cascades of K 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 cofidence-basee deferral, which will be empirically demonstrated in $5.2.
4.1 When Does Confidence-Banl Deferral Suffice?
Suppose as before we have probabilistic models g(),p(2) Recall from Algorithm I that for constant c(1) 0, confidence-based deferral employs the rule
Poont (x) maxp (x) < c(u)
Following $3.3, (7) may be regarded as a plug-in estimator for the "population confidence" rule Tcouf (x) [Mnnn(r) < c..). Contrasting this to Proposition 3.1, we have the following:
Lemma 4.1. Assume that for any x. x' XX (1)))()) S Mhos (x') if and only if The (x) - (n)) (x) S
Thaa (x²) - -Taees (x') (i.e., Thas (a:) and (ha)(x)) - Thaes (x:) produce the same ordering over instances
K). Then, the deferral rule Teouf produces the same deferral curve as the Bayes-optimal rule (3).
Lemma 4.1 studies the agreement between the deferral curves of Tconf 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 I's prediction agrees with the relative confidence is model I versus model 2's prediction.
Based on this, now detail some cases where confidence-beed based deferral succeeds fails.
Success mode: expert (2) Lemma 4.1 has one immediate, intuitive consequence: confidence-based deferral is optimal when the downstream model has constant error probability, i.e., Thgg (z) is constant for all x E X. This may happen, e.g., that the labels are deterministic given the inputs, and the second classifier (2) perfectly predicts them. Importantly, note that this is sufficient (but not necessary) condition for the optimality of confidence-barte deferral.
Failure mode: specialist (2. As a converse to the above, one setting where confidence-batt deferral may fail is when when the downstream model is specialist, which performs well only
5

---

Training label:
Loss
Deferral rule
Method label
Comment
1y (x)) 1ly (x))
Mean-squared error
((0) 2 c
Diff-as
Regression
(x) (x)
Mean absolute emoo
g(z) >
Diff-Prab
Regression
max, Pyy (x)
Mcan-squared error
g(z) maxy Pyf (2) >
MaxProb
Regression
Table I: Candidate post-hoe estimators of the oracle rule in (2). We train post-hoe model g(x)) training set {(2,, 2;) 2 so as to predict the label 2. Here, (z, y) E X x y is a labeled example.
particular sub-group of the data (e.g., subset of classes). Intuitively, confidence-based deferral may erroneously forward samples where h22) performs worse than h())
Concretely, suppose there is a data sub-group Xgood C. X where h(2) performs exceptionally well, i.c. (z) & 1 when E Xgood- On the other hand, suppose (2()) does not perform well on Xbad = X X Xgood i.e., (z) 1/L when E Xbad Intuitively, while (1)))) may be relatively low for x E Xbad, it is strongly desirable to not defer such examples, as h(2) performs even worse preferable identify and defer samples x E Xgood.
than 1;; rather,
Failure mode: label noise. Confidence- deferral can fail when there are high levels of label noise. Intuitively, in such settings, confidence-basee deferral may wastefully forward samples where h22)) performs better than (1)), Concretely, suppose that instances
Xbad C X may be mislabeled as one from a different, random class. For x E Xbad, regardless of how the two models 1,4),.e perform, we have (z) (ar) (2))) (x) = 1/L (i.e., the accuracy of classifying these instances is chance level in expectation). Since ()) (e)(2)) (x) is low, confidence-basee deferral will tend to defer such input instance æ. However, this is a sub-optimal decision since model 2 is more computationally expensive, and expected to have the same chance-level performance.
distribution shift. Even when model (222 is an expert model, intuitive setting where confidence-based deferral can fail is if there is distribution shift between the train and test Fl 2) [56]. In such settings, even if p()) 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 disti--iitt samples [52, 28], and the presence of a label skew during training [79, 64). We shall focus on the latter in the sequel.
Failure mode:
4.2 Post-Hoc Estimates of the Deferral Rule
Having established that confidence-baet based deferral may be sub-optimal in certain settings, 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 (3). Recall that this optimal rule has a dependence on the output of h (2);; unfortunately, querying h2(2) defeats the entire purpose of cascades. Thus, our goal is to estimate (3) using only the outputs of p(2)
We summarise number of post-hoc estimators in Table which are directly motivated by the One-hot, Probability, and Relative Contidence Oracle respectively from $3.3. The first to learn when model I is incorrect, and model 2 is correct. For example, given a validation set, suppose we construct samples Syat = {(x,, 2 where (1) = [ly = (22) - 1I = (x;)). Then, we fit
min g: T-RR
((2 g(x;)),
Svatl
(Nu1)) (1) E
where, e.g., is the square loss. The score g(x: may be regarded the confidence in deferring to model 2. Similarly, second approach is to perform regression to predict =! = py (xx) Pb
(1) (z:). directly estimate z; max, p. (I:)) using predictions of the first model.
The third approach
(2)
As shall be seen in $5.2, such post-hoc rules can learn to avoid the failure cases for confidence-basse deferral identified the previous section. However, it is important note that there are some conditions where such rules may not offer benefits over confidence-based deferral.

---

Failure mode: Bayes pl2) Suppose that the model pt2) exactly matches the Sayes-probabilitte i.e., (2)
Py P(y' z). Then, estimating maxy' Py (x) equivalent to estimating maxy PPyy x). However. the goal of model I is precisely to estimate Ply z). Thus, if p() is sufficiently accurate, in the absence of additional information (e.g.. fresh dataset), it is unlikely that one can obtain better estimate of this probability than that provided by p(4) itself. This holds even if the PPy x) is non-deterninistic. and so the second model has non-trivial error.
Failure mode: non non-predie predictable p(²) error. When the model pl outputs not strongly pre- dictable, post-hoe deferral may devolve to regular confidence based deferral. Formally, suppose (2)
we seek to predict = maxy' Py (z), e.g., as in MaxProb. A non-trivial predictor must achieve an average square error smaller than the variance of z, i... [B[[= B[z]) If 2 however not strongly predictable, the estimate will be tantamount to simply using the constant [[[]]. This brings us back to the assumption of model 2 having constant probability of error, i.e., confidence-basee deferral.
4.3 Finite-Sample Analysis for Post-Hoc Deferral Rules
We now formally quantify the gap in performance between the learned post-hoe rule and the Bayes- optimal rule r" [[g (z) c] in Proposition 3.1, where g" (z) (=) (2) 7h000 (z) (z). (z). We
will consider the case where the validation sample Sval is constructed with labels 2("), We pick scorer 9 that minimises the average squared loss [ Σ (xna)ees (z g(x;))² over hypothesis class G. We then construct a deferral rule f(x) = 1 [g(x)) cc.
Lemma 4.2. Let E)) denote the covering number of G with the oc-Rorm Suppose for any g E G. (2 g(x))² < B, (x, 2). Furthermore, let 9 denote the minimizer of the population squared loss E [( - {xx)) over G, where z = 1ly = 12(2) (x)] - 1yy = (z)). Then any E (0, 1), with
probability at least 8 over draw of Sval, the excess risk for i is bounded by
R(f; (1), (1(())) R(r"; (1))))))))
O ( log(1/0) [Svat]
1/2
2 log (ggN(
S 2
Ex [(((x) - o" (x))
+4 44.imm inf
B
va
Approximation error
Estimation ervor
We provide the proof in $A.4. The first term on the right-hand side (RHS) is an irreducible approx- imation error, quantifying the distance between the best possible model in the class to the oracle scoring function. The second and the third terms on RHS quantify total estimation error.
4.4 Relation Existing Work
As noted in $3.4, learning deferral rule for two-model cascade is closely related to existing literature in learning to defer to an expert. This in turn is generalisation of the classical literature on learning to reject [27, 71, which refers classification settings where one is allowed to abstain from predicting on certain inputs. The population risk here is a special case of (2), where (2) (z) is assumed perfectly predict y. The resulting Bayes-optimal classifier known as Chow's rule [11, 60], 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 [53].
In settings where one is allowed to modify the training of (1)), it is possible construct losses that jointly optimise for both (1( and r [1, 12, 60, 73, 8, 21, 36). While effective, these are not applicable our setting involving pre-trained, black-box classifiers. Other variants post-hoe methods have been considered in Narasimhan et al. [49], and implicitly in Trapeznikov and Saligrama [74]; 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 $4.1 by considering the three failure modes in which confidence-based deferral underperforms. For each of these settings,
7

---

0.64
0.75
0.63
Accuracy
Accuracy
Accuracy
0.70
0.60
Confidence Random
0.63
0.65
0.58
Relativee Confidence
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.0
1.0
Deferrol rate
Deferral rate
Deterral rate
(a) Standard ImageNet
(b) 4% non-dog training images
(c) 2% non-dog training images
(100% non-dog training images)
Figure 1: Test accuracy deferral rate of plug-in estimates ($3.3) for the oracle rule. Here, h() is MobileNet V2 trained on all ImageNet classes, and h22) is 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, h22) specialises in classifying different types of dogs. By considering the confidence of (2) (Relative Confidence), one gains accuracy by selectively deferring only dog images.
compute deferral curves that plot the classification accuracy versus the fraction of samples deferred the second model (which implicitly measures the overall compute cost). line with our analysis in 1, post-hoc deferral rules offer better accuracy-cost trade-offs in these settings.
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. this experiment, (!1) is a generalist (i.e., trained on all ImageNet classes), and M(2) is dog specialist trained all images in the dog synset, plus fraction of non-dog training examples, which we vary. There are 119 classes in the dog synset. We use MobileNet V2 [65] as k(O,, and larger EfficientNet BO [71] as (2). For hyperparameter details, see Appendix C.
Figure 1 shows the accuracy of confidence- based deferral (Confidence) and Relative Confidence (Equation (6)) 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 In Figure la, the fraction of non-dog training images is 100% i.e., model
also a generalist trained on all images. In this case, we observe that Relative Confidence offers little gains over Confidence.
However, in Figure lb and Figure 1c, as the fraction of non-dog training images decreases, the non- uniformity of (2)))s 's error probabilities increases i.e., (2) starts specialise dog images. In line with our analysis in $4.1, confidence-based deferral underperforms when model 2's error probability highly non-uniform. That is, being oblivious to the fact that h22) 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
Sinfidence-Based versus Post-Hoc Deferral
From $5.1, may construct better deferral rules by querying model for its confidence. Practically, however, querying model 2 at inference time defeats the entire purpose of cascades. To that end, we now compare confidence-bast 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 1, and demonstrate that post-hoc deferral can significantly outperform confidence-basse deferral. We present more experimental results in Appendix E, where we illustrate post-hoc deferral rules for K > 2 models.
Post hoc model training. For a post-hoc approach to be practical, the overhead from invoking
a post-hoe model must be small relative to the costs of (())) and (2) To this end, in all of the following experiments, the post-hoc model X - R is based on lightweight, three-layer Multi- Layer Perceptron (MLP) that takes as input the probability outputs from model 1. That is, g(x)
(LP(p()(x.) where (x)() E Ar, denotes all probability outputs from model Learning g amounts to learning the MLP as the two base models are fixed. We train y on held-out validation set. For full technical details of the post-hoe model architecture and training, see Appendix C. We
use the objectives described in Table I to train g.
8

---

0.75
0.64
Accuracy
Confidence
Accuracy
Accurecy
0.70
Random
0.63
Entropy
MaxProo
0.65
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.6
0.8
1.0
Deferral
Deferral
Deferral
(a) Standard ImageNet.
(b) 4% non-dog training images.
(c) 2% non-dog training images.
0.58
0.48
Accuraty
0.64
Confidence
Accurazy
MaxProb
0.46
0.62
Dift.01
0.54
Dift-robb
0.60
Entrapy
0.52
0.44
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Deferral rate
Deferral rate
Deferral rate
(d) Standard CIFAR 100.
(c) Label noise on first 10 classes.
Label noise on first 25 classes.
0.55
Accursy
Confidence
Random
Accuracy
0.50
accuracy
0.450
0.425
0.65
MaxProb
Diff 01
0.45
0.400
0.60
Diff-Prob
0.375
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Deterral rate
Deterral rate
Deterral rate
(g) Standard CIFAR 100.
(h) Head classes: 50.
(i) Head classes: 25.
Figure 2: Test accuracy deferral rate of the post-hoc approaches in Table under the three settings described in $4.1: 1) specialist (row 1), 2) label noise (row 2), and 3) distribution shift. Row the fraction of non-dog training images decreases, model 2 becomes dog specialist model. Increase in the non-uniformity 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, is sub-optimal to defer affected inputs since model 2's correctness is also chance level. Being oblivious model 2, confidence- based deferral underperforms. For full details, see $5.2. Row 3: As the skewness of the label distribution increases, 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.
its error probabilities allows post-hoc approaches learn to only defer
Specialist setting. We start with the same ImageNet-Dogg specialist setting used in $5.1. This time, we compare six methods: Confidence, Random, MaxProb, Diff-e1, Diff-Prob, and Entropy. Random is baseline approach that defers either model model 2 random; MaxProb, Diff-01, and Diff ff-frrbb are the post-hoc rules described in Table I; Entropy defers based on the thresholding the entropy of p()) [31, 36), 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: can accurately determine whether the second model is likely to make mistake. Aligning with our analysis, for the generalist setting (Figure 2a), confidence-basee deferral is highly competitive, since (2(2) gives a consistent estimate of Pyy x).
Label noise setting. In this setting, look problem with label noise. We consider CIFAR 100 dataset where training examples from pre-chosen Lnoise E {0, 10, 25} classes are assigned a uniformly drawn label. The case of T.naise 0 corresponds the standard CIFAR 100 problem. We set (1) to be CIFAR ResNet 8 and set (2) to be CIFAR ResNet 14, and train both models on the noisy data. The results are shown in Figure (second row). It is evident that when there is label noise, post-hoc approaches yield higher accuracy than confidence- based rates, aligning with our analysis $4.1. Intuitively, confidence- based deferral tends to forward noisy samples (2), which performs equally poorly, thus leading to waste of deferral budget. By contrast, post-hoc rules can learn to "give up" on samples with extremely low model confidence.
large range of deferral

---

0.70
Accuracy
0.68
Accuracy
Confidence
Random
0.66
Entropy
MaxProb
0.64
Diff-01
0.62
Diff-Prob
0.62
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Deferral rate
Deferral rate
(a) Training performance
(b) Test performance
Figure 3: Training and test accuracy of post-hoc approaches in the ImageNet-Dog specialist setting. Model (EfficientNet B0) is trained with all dog images and 8% of non-dog images. Observe that post-hoc model (i.c., Di Diff-e1) can severely overfit to the training set and fail to generalise.
Distribution shift setting. To simulate distribution shift, consider long-tailed version of CIFAR 100 [40] where there are h E (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 h 100. Both models h()) (CIFAR ResNet 8) and (2) (CIFAR ResNet 56) trained on these long-tailed datasets. At test time, all methods are evaluated on the standard CIFAR 100 balanced test set, resulting in label distribution shift.
We present our results in Figure (third row). Figure 2g. there no distribution shift. 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 decreases from 100 to 50 (Figure 2h) and 25 (Figure 21), there is more distribution shift at test time, and post-hoc approaches (notably Diff-e1) show clearer gains. To elaborate, the two base models are 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 (2) and defer input instances from tail classes.
5.3
On the Generalisation of Post-Hoc Estimators
Despite the benefits of post-hoc approaches demonstrated earlier, care must be taken controlling the capacity of the post-hoc models. We consider the same ImageNet-Dop specialist setting in the top row of Figure 2. Here, model is trained on all dog images, and large fraction of non-dog images (8%). Since model 2 has access to non-trivial fraction of non-dog images, the difference in probability correct prediction 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 despite using feedforward network with two hidden layers of only 64 and 16 units (see Appendix C for details on hyperparameters) to control the capacity the post-hoc model. Thoroughly investigating approaches to increase generalisation of post-hoc models will be 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-ben
deferral.
While we have identified conditions under which confidence-based deferral underperforms (e.g.. specialist setting, label noise). these are not exhaustive. interesting direction for future work 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 also of interest to study the efficacy of more refined confidence measures, such those based on conformal prediction [69]. Finally, while our results have focussed on image classification settings, it would of interest to study analogous trends for natural language processing models.
10

---

References
[1] Peter L.. Bartlett and Marten H. Wegkamp. Classification with a reject option using hinge loss. Journal of Machine Learning Research, 9(59):1823-1840, 2008. URL http::/jmtt..../ org/ papers/vg/bartlen http://baaaeeettt.aaaaem html.
[2] Tolga Bolukbasi, Joseph Wang, Ofer Dekel, and Venkatesh Saligrama. Adaptive neural networks for fast test-time prediction. In International Conference on Machine Learning, 2017.
[3] 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-Von 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. Balean, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[4] 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.
[5] Cristian Bucilă, Rich Caruana, and Alexandru Niculescu-Mizil. Model compression. In Proceedings of the 12th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD) '06, pages 535-541, New York, NY, USA, 2006. ACM.
[6] Alfredo Canziani, Adam Paszke, and Eugenio Culurciello. An analysis of deep neural network models for practical applications. CoRR, abs/1605.07673 2016. URL http://arxiv..r org/abs/ 1605.077 07678.
[7] Yuzhou Cao, Tianchi Cai, Lei Feng, Lihong Gu, Jinjie GU, Bo An, Gang Niu, and Masashi Sugiyama. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 521-534 Curran Associates, Inc., 2022.
[8] Nontawat Charoenphakdee, Zhenghang Cui, Yivan Zhang, and Masashi Sugiyama. Classifi- cation with rejection based on cost-sensitive classification. In Marina Meila and Tong Zhang, editors, Proceedings the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1507-1517. PMLR, 18-24 Jul 2021.
[9] Momammad-Amin Charusaie, Hussein Mozannar, David Sontag, and Samira Samadi. Sample efficient learning of predictors that complement humans. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 2972-3005 PMLR, 17-23 Jul 2022.
[10] 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 s 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.
[11] C. Chow. On optimum recognition and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41-46, 1970. doi: 10.1109/TT.1770.105444
[12] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Boosting with abstention. Advances in Neural Information Processing Systems, 19:1660- 2016.
[13] Giulia DeSalvo, Mehryar Mohri, and Umar Syed. Learning with deep cascades. In Proceedings of the Twenty-Sixhh International Conference on Algorithmic Learning Theory (ALT 2015), 2015.
11

---

[14] 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::/arxxvv.or//aae http.vvv.....aaa///.//..// 10342.
[15] 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://openrev net/ www.wneefforuteeo witprmmmiddiiiccdnii
[16] Chris Drummond and Robert C Holte. Cost curves: An improved method for visualizing classifier performance. Machine learning, 65:95-130, 2006.
[17] Maha Elbayad, Jiatao Gu, Edouard Grave, and Michael Auli. Depth-adaptive transformer. In International Conference on Learning Representations, 2020. URL https://openrrviewwnees forum? SgggkKK.
[18] Charles Elkan. The foundations of cost-sensitive learning. In Proceedings of the 17th Inter- national Joint Conference on Artificial Intelligence Volume 2, IJCAI'01, page 973-978, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. ISBN 1558608 125.
[19] Angela Fan, Edouard Grave, and Armand Joulin. Reducing transformer depth on demand with structured dropout. In International Conference on Learning Representations, 2020. URL
[20] 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 aal/aabb///2// 2ttss//11..3966..
[21] 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 Intellience and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2179-2187, PMLR, 13-15 Apr 2021, URL https:
/ //proceedings.mie mml. pwwps//vsss/e//eeeepepppp mare:e//ss.mmm...ess///3.3.. http://vvveggggadeeeeeee wwwgggaaeeaa.attmm..mm
[22] N. Gareia-Pedraaas, D. Ortiz-Boyer, R. del Castillo-Gomariz, and C. Hervás-Martinez. 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-3210644
[23] 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 Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2151-2159. PMLR, 09-15 Jun 2019.
[24] Hans Graf, Eric Cosatto, Leon Bottou, Igor Dourdanovic, and Vladimir Vapuik. Parallel support vector machines: The cascade svm. Advances in neural information processing systems, 17, 2004.
[25] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In Proceedings the 34th International Conference Machine Learning Volume 70, ICML' 17, page 1321-1330. JMLR.org. 2017.
[26] Y. Han, G. Huang, S. Song. L. Yang. H. Wang, and Y. Wang. Dynamic neural networks: A survey. IEEE Transactions Pattern Analysis & Machine Intelligence, (4tll)eence,44111774336-6--- 44(11):7436-7456 nov 2022. ISSN 1939-3539. doi: 10.1109/TPMM...021.. 1177777777
[27] Kilian Hendrickx, Lorenzo Perini, Dries Van der Plas, Wannes Meert, and Jesse Davis. Machine learning with a reject option: A survey. CoRR, abs/2 1277, 2021.
[28] Dan Hendryeks and Kevin Gimpel. A baseline for detecting misclassified and duitti-disttibuttion examples neural networks. International Conference on Learning Representations, 2017.
URL https wtwppppeeewwweeeeeoooeeeeeeeeeee
12

---

[29] Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in neural network. CoRR, abs/1503.02531, 2015.
[30] 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.
[31] Gao Huang. Danlu Chen, Tianhong Li, Felix Wu, Laurens van der Maaten, and Kilian Wein- berger. Multi-scale dense networks for resource efficient image classification. In International Conference on Leurning Representations, 2018.
[32] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- Vaniv,, and Yoshua Bengio. Quan- tized neural networks: Training neural networks with low precision weights and activations. J. Mach. Learn, Res., 18(1 18(1):6889-6888, jan 2017. ISSN 1532-4435.
[33] Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in ma- chine learning: an introduction to concepts and methods. Machine Learning, 110(3))457- 506, mar 2021. doi: 1211007/11099-02--005555
URL https://doi.org/ 1007%
2F$10994- 021- 3.
[34] 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, NeurlPS' 18, page 5546-551 5557,, Red Hook, NY, USA, 2018. Curran Associates Inc.
[35] Lu Jiang, Di Huang, Mason Liu, and Weilong Yang. Beyond synthetic noise: Deep learning on controlled noisy labels. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. 20. JMLR.org, 2020.
[36] 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
[37] Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for com- puter 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, De- cember 4-9, 2017, Long Beach, CA, USA, pages 5574-5584, URL / Abst html.
[38] Leila Khalili, Yao You, and John Bohannon. Babybear: Cheap inference triage for expensive language models, 2022. URL
11747.
[39] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014.
[40] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[41] Gustav Larsson, Michael Maire, and Gregory Shakhnarovich. Fractalnet: Ultra-deep neural networks without residuals. In ICLR, 2017.
[42] Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. In D. Touret- zky, editor, Advances in Neural Information Processing Systems, volume 2. Morgan- Kaufmann, 1989 URL Utt..tttps:/pproceeedng www.ediiiinnnnninnnneeeeeeeeeee. wwwrips.cc/paper.rr httppppperfllles/pppr/////// /file/ (cs8abbccccopg00d000082222766662
[43] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11))227823244 1998.
[44] 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 814, 2015. doi: 10.11999CVRR.20155229666.
13

---

[45] Weijie Liu, Peng Zhou, Zhe Zhao, Zhiruo Wang, Haotang Deng, and Qi Ju. FastBERT: self-distilling bert with adaptive inference time. In Proceedings of ACL 2020, 2020.
[46] 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 1150-6160, Red Hook, NY, USA, 2018. Curran Associates Inc.
[47] Jonathan Mamou, Oren Pereg, Moshe Wasserblat, and Roy Schwartz. TangoBERT: Reducing in- ference cost by using cascaded architecture, 2022. URL http::t/ta//teee org/ attpaa//////a 2204. 06271.
[48] Hussein Mozannar and David Sontag. Consistent estimators for learning defer 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.
[49] Harikrishna Narasimhan, Wittawat Jitkrittum, Aditya Krishna Menon, Ankit Singh Rawat, and Sanjiv Kumar. Post-hoc estimators for learning to defer to expert. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL
net/ wwtp://eee/o///moeee//// ffr.:oidd=jjgfffftuu
[50] Taman Narayan, Heinrich Jiang, Sen Zhao, and Sanjiv Kumar. Predicting on the edge: Identify- ing where a larger model does better, 2022. URL https://arxiv..rt org/ www.:/g////aaaaaeaeeee abspabb2..e022222
[51] Jerzy Neyman and Egon Sharpe Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231(694-
337, 1933.
[52] Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In 2015 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 427-436, 2015. doi: 10.1 1011
7298640.
[53] 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é-Bue, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2582-2592, 2019.
[54] 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 URL https://doi: https::/d/oiooo./.../o 1145/1102351
159593180S doi: 10. 102351. 11.351111000 102440. 1102430.
[55] Priyadarshini Panda, Abhronil Sengupta, and Kaushik Roy. Conditional deep learning for energy-efficien and enhanced pattern recognition. In Proceedings the 2016 Conference on Design, Automation & Test in Europe, DATE '16, page 475-480, San Jose, CA, USA, 2016. EDA Consortium. ISBN 1783981537062.
[56] Joaquin Cainonero-Candelle Masashi Sugiyama, Anton Schwaighofer, and Neil D. Lawrence. Dataset shift in machine learning. MIT Press, 2009. ISBN 9780262170055.
[57] Alec Radford and Karthik Narasimhan. Improving language understanding by generative pre-training, 2018
[58] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners, 2019.
[59] 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 unified text-to-text transformer. Mach. Learn. Res., 11:140:1-1444 140:67, 2020. URL. http://jmlr. org/ppapers/vea/20007... html.
14

---

[60] Harish G. Ramaswamy, Ambuj Tewari, and Shivani Agarwal. Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statisties, 12(1):530- 554, 2018. doi: 10. (0.1214/17-JJS1388
[61] Ankit Singh Rawat, Manzil Zaheer, Aditya Krishna Menon, Amr Ahmed, and Sanjiv Ku- mar. When in doubt, summon the titans: Efficient inference with large models. CoRR, abs/2110 10. 10305, 2021.
[62] Mohammad Saberian and Nuno Vasconcelos, Boosting algorithms for detector cascade learning. The Journal of Machine Learning Research, 15(1):26692605, 2014.
[63] Mohammad J. Saberian and Nuno Vasconcelos.
Boosting classifier cascades.
In NeurIPS, pages 2047-2055, 2010. 4033- boosting classifierccsscaess
URL http://papers.ning wwwp..cpppppp.rr..eeeeeeppp
[64] Dvir Samuel, Yuval Atzmon, and Gal Chechik. From generalized zero-shot learning to long-tal taigttail with class descriptors. P Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), 2021.
[65] 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 45204 2018.
[66] Simone Scardapane, Michele Scarpiniti, Enzo Baccarelli, and Aurelio Uncini. Why should we add early exits to neural networks? Cognitive Computation,
2020.
[67] Roy Schwartz, Jesse Dodge, Noah A. Smith, and Oren Etzioni. Green AL. CoRR, abs/1907.10597, 2019. URL
wtt.///////............ 10597.
[68] 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.
[69] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 912):371-421, 2008. URL
html.
[70] Matthew Streeter. Approximation algorithmss 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
[71] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. International conference on machine learning, pages 6105-6114 14. PMLR, 2019.
[72] 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.
[73] 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.
[74] 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.
[75] Neeraj Varshney and Chitta Baral. Model cascading: Towards jointly improving efficiency and accuracy of nlp systems. arXiv preprint arXiv:2210.05.. 2022.
15

---

[76] Tom Veniat and Ludovic Denoyer. Learning time/memory-effiee -fffccient deep architectures with budgeted super networks. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3492-3500, 06 2018. doi: D0.1109/CVP..2018.000
[77] P. Viola and M. Jones. Rapid object detection using 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 1-1, 2001. doi: 10.1109/CVPR.200 200.1..0000..9111..
[78] 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 301 8-3026, Los Alamitos, CA, USA, jun 2020. IEEE Computer Society. doi: 10. 10/CC//W555W50000.200 200000 00360. URL
www.cooouterssocciteee. wrwp//ettooro/o..ooo 1109/ w18g/CCRRW55098.... 20275 2020. 00360.
[79] 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. 10.1 10.1109/CDM..202..11.
[80] Xiaofang Wang, Dan Kondratyuk, Eric Christiansen, Kris M. Kitani, Yair Movshovitz-Atiias and Elad Eban. Wisdom committees: An overlooked approach faster and more accurate models. In International Conference on Learning Representations, 2022. URL https:// openreview.co wet.iieww.eeffoooe
[81] 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.
[82] Ji Xin, Rodrigo Nogueira, Yaoliang Yu, and Jimmy Lin. Early exiting BERT for efficient document ranking. Proceedings of SustaiNLP: Workshop on Simple and Efficient Natural Language Processing, pages 83 33.88, Online, November 2020. Association for Computational Linguistics.
[83] Xin, Raphael Tang, Jaejun Lee, Yaoliang Yu, and Jimmy Lin. DeeBERT: Dynamic early exiting for accelerating BERT inference. In Proceedings of the 58th Annual Meet- ing of the Association for Computational Linguistics, pages 2246-2251, Online, July 2020. Association for Computational Linguistics. doi: 10.18653/112000...o acl mel-maan.204. URL
https://aclant Lanthhlloyy org/2020 .ac.o..cll.... Lmmain.
[84] 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
[85] 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-1888 18341. Curran Associates, Inc., 2020.
[86] Shlomo Zilberstein. Using anytime algorithms in intelligent systems. Al Magazine, 17(3):73. Mar. 1996. doi: 160%/amaa 1713. 1713.1232.
16


Reviews:
[{"review_id": "XttfiYWPL0", "reviewer": "Reviewer_UXcD", "summary": "In this paper, the authors study the problem of confidence-based cascade deferral for the classification task. They first proposed the formulation of Bayes optimal deferral rule, which relies on both the base model and its successive model, and then proposed several baselines that works by mimicking the Bayes optimal rule. They further analyzed confidence-based methods and proposed the condition for their consistency. Given the fact that these baselines' computational costs are not acceptable, they turn to propose a post-hoc method guided by the baselines and analyzed its consistency under different conditions. Experimental results validated the performance of the proposed method.", "questions": "Please see the Weaknesses section.", "limitations": "The limitations are adequately analyzed in Appendix G.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The authors studied the optimality condition for cascade deferral rule and show the formulation of the Bayes optimal rule that relies on the confidence score of two models, which takes an intuitive form that implies the limitation of confidence-based deferral. \n\n2. The authors gave several baselines to approximate the Bayes optimal rule, and further proposed the post-hoc versions for them to resolve the computational issues.\n\n3. Theoretical analyses are conducted for both the confidence-based method and post-hoc deferral rule under various conditions.", "weaknesses": "1. Though the connection between this work and learning to defer/ classification with rejection is revealed, it is not thoroughly investigated in my opinion. In fact, learning to defer and classification with rejection are shown to be equivalent to the ordinary multi-class classification problem [1, 2]. In the post-hoc regime, I think it is worth trying to reduce the training of the cascade deferral rule to a multi-class classification problem by setting the maximum confidence of each model as a pseudo posterior probability.\n\n2. As stated in the limitation section, the analyses are conducted on a case-by-case basis, indicating that there is still progress needed to develop a consistent and computationally friendly deferral rule. While the experimental results suggest that the proposed method is comparable, it is still a matter worth addressing. Conducting a finite-sample analysis could significantly alleviate this concern.\n\n[1]. Mohammad-Amin Charusaie, Hussein Mozannar, David A. Sontag, Samira Samadi. Sample Efficient Learning of Predictors that Complement Humans. ICML 2022.\n\n[2]. Yuzhou Cao, Tianchi Cai, Lei Feng, Lihong Gu, Jinjie Gu, Bo An, Gang Niu, Masashi Sugiyama. Generalizing Consistent Multi-Class Classification with Rejection to be Compatible with Arbitrary Losses. NeurIPS 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n> The analyses are conducted on a case-by-case basis. There is still progress needed to develop a consistent and computationally friendly deferral rule.\n\nWe reiterate that by Proposition 3.1, the Bayes-optimal deferral rule is based on thresholding $s^*( x ) = \\eta_{h^{(1)}(x)}(x) - \\eta_{h^{(2)}(x)}(x)$. By Lemma 4.1, confidence based deferral is optimal if $\\eta_{h^{(1)}(x)}(x)$ produces the same order over input instances compared to $s^*( x )$. This one condition characterises the optimality of the confidence based deferral and thus can be seen as a unified (population level) analysis. \n\nThe three cases presented in Section 4.1 (i.e., specialist setting, label noise, distribution shift) are intuitive problem instances where the confidence-based deferral is not optimal. Note that in experiments on all these three settings, the same set of post-hoc approaches and the same training recipe are used (see Section C.2). In all cases, the post-hoc model is a small MLP composed of no more than 100 hidden units. The overhead in the inference cost from calling the post-hoc model is negligible, and thus we believe this approach is computationally-friendly.\n\n\n> Conducting a finite-sample analysis could significantly alleviate this concern.\n\nWe agree with the reviewer that conducting a finite-sample analysis is of interest. As we demonstrate next, **the Diff-01 method readily admits standard generalisation bounds.**\n\n### Finite sample analysis\n\n\nRecall that for given base classifier $h^{(1)}$ and $h^{(2)}$ and deferral cost $c$, the optimal deferral rule takes the form \n$r^*(x) = 1[g^*(x) > c]$,\nwhere\n$g^*(x) = \\eta_{h^{(2)}(x)}(x)-\\eta_{h^{(1)}(x)}(x)$.\nWe seek to approximate this optimal rule by constructing samples $S_{\\rm{val}} := \\{ ( x_i, z_i) \\}$, where the labels $z$ are chosen such that $\\mathbb{E}[ z | x] = g^*(x)$. We then pick a scorer $\\hat{g}$ from a hypothesis class $\\mathcal{G}$ that minimizes the empirical average squared loss on this sample:\n$$\\hat{R}\\_{\\rm sq}(g) \\,= \\frac{1}{| S\\_{\\rm{val}} |} \\sum\\_{( x_i, z_i ) \\in S\\_{\\rm val}} ( z_i - g( x_i ) )^2,$$\nand construct a deferral rule  $\\hat{r}(x) = 1[\\hat{g}(x) > c]$. \n\nWe have the following result.\n\n**Proposition** \nLet $\\mathcal{N}(\\mathcal{G}, \\epsilon)$ denote the covering number for $\\mathcal{G}$ with the $\\infty$-norm.  Suppose for any $g \\in \\mathcal{G}$, the squared loss $(z - g(x))^2 \\leq B, \\forall (x, z)$. \nFix $\\delta \\in (0,1)$. Then  with probability at least $1 - \\delta$ over draw of $S_{\\rm val}$, \n\n$$R(\\hat{r};h^{(1)},h^{(2)}) - R(r^*;h^{(1)},h^{(2)})\n\\leq \n    \\mathbb{E}\\_x [ (\\tilde{g}(x)  -  g^*(x))^2 ]  + \n 4\\cdot\\inf\\_{\\epsilon > 0}\n        \\epsilon + \n        B\\sqrt{\n            \\frac{ 2\\cdot\\mathcal{N}(\\mathcal{G}, \\epsilon) }{|S\\_{\\rm val}|}\n        }\n    +\n    \\mathcal{O} (\\sqrt{\\frac{\\log(1/ \\delta)}{|S\\_{\\rm val}|}})\n$$\n \nIn the above finite-sample bound, the first term on the right-hand side (RHS) is an  approximation error quantifying the distance between the best possible model $\\tilde{g}$ in the class $\\mathcal{G}$ to the optimal function $g^*$. The second and the third terms on RHS can be interpreted as an estimation error.\n\n\n> Though the connection between this work and learning to defer/ classification with rejection is revealed, it is not thoroughly investigated\n\n**The reviewer is completely correct that there are close links between model cascading and learning to defer.** However, as this is not the primary focus of the work, in the interest of space we “deferred” a detailed discussion of this topic to the cited work of [Narasimhan et al., 2022]. We are happy to add citations to the referenced works from the learning to defer literature.\n\n\n"}, {"review_id": "n5DpSaetg4", "reviewer": "Reviewer_kqwH", "summary": "The authors present a theoretical analysis for the Bayes optimal deferral rule for a cascade of K=2 classifiers and a certain population risk.\nBased on this rule, they characterize when confidence deferral rule using exact posterior probabilities is similar to the Bayes optimal deferral rule is some sense.\nBased on their analysis, the authors (informally) discuss cases where (practical) confidence deferral rule may or may not be sufficient, and proposed several post-hoc methods for the latter.\nThe insights and the methods are examined empirically.\n\n\n", "questions": "Please improve the explanation for Lemma 4.1. \nState what you mean in \"the same ordering\" in the main body of the paper and not only in the proof in the appendix.\n\nThe text below Lemma 4.1, and actually in several other places in the paper, needs to be more accurate when you claim optimality of confidence-based deferral rule based on your analysis --- as by saying so, you assume that the classifier's softmax values are exactly the true posterior probabilities, which is obviously not the case in practice [21].\n\nIn Figure 2, first row, how do you explain the fact that plain confidence deferral oftentimes outperforms the two post-hoc methods Diff-01 and Diff-prob? Furthermore, Diff-prob in fact is consistently worse than the other methods in all 3 rows in Figure 2, can you explain why?\n\nA minor comment: In Algorithm 1, when you write predict inside the loop, letting it be followed by a \"break\" command would make the scheme clearer.", "limitations": "  ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I find the paper very interesting and the analysis to be solid.\nThe theory is important and the insights and practical guidance that it provides look useful.", "weaknesses": "The empirical coverage may be somewhat improved, e.g., by using practical datasets without the controlled modifications (such as the dog-specific classifier). I also wonder whether there is some benchmark that can be used for comparing the new post-hoc methods to existing ones. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive feedback, and for recognizing the importance of our theoretical analysis.  We appreciate the reviewer’s comments on the presentation. We will revise accordingly.\n\n\n> The empirical coverage may be somewhat improved, e.g., by using practical datasets without the controlled modifications (such as the dog-specific classifier). \nThanks for the excellent suggestion. **We have confirmed that we obtain similar conclusions on a dataset with realistic label noise.**\n\n\nWe considered the Mini-ImageNet dataset (with noise rate 60%) from Jiang et al., Beyond Synthetic Noise: Deep Learning on Controlled Noisy Labels, ICML ‘20. In the rebuttal PDF, we have included deferral curves for various methods under a cascade of ResNet 10 models with widths 16 (small model) and 64 (large model). As in the body, Diff-01 significantly outperforms Confidence based deferral in this setting.\n\n>   Text below Lemma 4.1: you assume that the classifier's softmax values are exactly the true posterior probabilities, \n\nTo clarify, Lemma 4.1 and text below it **does not** assume that the first model’s softmax probabilities are exactly the true posterior probabilities. Rather, the key assumption is that we accurately estimate the **error probability** of model 1, which is a weaker condition.\n\nIn more detail:\n\nRecall that $h^{(i)}$ denotes the i-th classifier where $i \\in \\\\{1, 2\\\\}$. In line 153, we define $\\eta_{h^{(i)}(x)}(x) := \\mathbb{P}(y=h^{(i)}(x) | x)$. This can be interpreted as the _conditional_ accuracy of the classifier $h^{(i)}$ on an instance $x$. Intuitively, this quantity captures the agreement between the prediction $h^{(i)}$ and that of the Bayes’ classifier $\\mathbb{P}(y | x)$ on $x$. The Bayes optimal deferral rule $r^{*}(x) =\\boldsymbol{1}\\left[\\eta_{h^{(2)}(x)}(x)-\\eta_{h^{(1)}(x)}(x)>c\\right]$ given in Proposition 3.1 means that we should defer $x$ when the relative gain in conditional accuracy is larger than $c$. \n\nLemma 4.1 characterises when confidence-based deferral (i.e., based on only $\\eta_{h^{(1)}(x)}(x)$) is optimal. While measuring the confidence with $\\eta_{h^{(1)}(x)}(x)$ is ideal, in practice, we do not have access to it since it depends on the true conditional distribution $\\mathbb{P}(y | x)$. The commonly used confidence measure  $\\max\\_{y'} p^{(1)}\\_{y'}( x )$ may be regarded as an estimator of  $\\eta\\_{h^{(1)}(x)}(x)$. \n\nA practical interpretation of Proposition 3.1 and Lemma 4.1 would require us to assume that $\\max\\_{y'} p^{(1)}\\_{y'}( x )$ is close to $\\eta_{h^{(1)}(x)}(x) = \\mathbb{P}( y \\neq h^{(1)}( x ) \\mid x )$. In other words, the confidence $\\max\\_{y'} p^{(1)}\\_{y'}( x )$ captures the conditional accuracy. However, this is not the same as stating that the classifier's softmax values are exactly the true posterior probabilities. The latter translates to $p_y^{(1)}(x) = \\mathbb{P}(y | x)$ for $x \\in \\mathcal{X}, y \\in [L]$, a strong condition that we do not assume. In fact, assuming so would have defeated the purpose of forming a cascade, since model 1 alone suffices.\n\n> In Figure 2, first row, how do you explain the fact that plain confidence deferral oftentimes outperforms the two post-hoc methods Diff-01 and Diff-prob\n\nAs described in Section 4.1 (lines 187-195), when $h^{(2)}$ is a specialist, it performs exceptionally well on a data sub-group $\\mathcal{X}_{\\mathrm{good}}$ that it specialises on, and performs poorly on the rest of the data $\\mathcal{X}\\_{\\mathrm{bad}} = \\mathcal{X}  \\setminus \\mathcal{X}\\_{\\mathrm{good}}$. In other words, $\\eta\\_{h^{(2)}(x)}(x)$ is high on instances in $\\mathcal{X}\\_{\\mathrm{good}}$ and low on instances in $\\mathcal{X}\\_{\\mathrm{bad}}$.\n\nA post-hoc deferral rule can perform well by learning to defer $x \\in \\mathcal{X}\\_{\\mathrm{good}}$ to $h^{(2)}$ and defer $x \\in \\mathcal{X}\\_{\\mathrm{bad}}$  to $h^{(1)}$. That is, the post-hoc rule can learn to identify the set of instances $x$’s for which $\\eta\\_{h^{(2)}(x)}(x) - \\eta\\_{h^{(1)}(x)}(x) > c$ (recall the optimal deferral rule in Proposition 3.1).  This is the case in Figure 2(c) where $h^{(2)}$ is a dog specialist model. \n\nHowever, in Figure 2(b), the fraction of non-dog training images for $h^{(2)}$ is 4% (compared to 2% in Figure 2(c)). In this case, $h^{(2)}$ becomes relatively more like a generalist, and  $\\eta\\_{h^{(2)}(x)}(x) - \\eta\\_{h^{(1)}(x)}(x)$ is closer to 0 i.e., less accuracy gap between the two base models. This makes it harder for a post-hoc deferral rule to learn to identify instances to defer. This is why Confidence can be better than post-hoc rules in this case.\n\n\n> Diff-prob in fact is consistently worse than the other methods in all 3 rows in Figure 2, can you explain why\n\nThis is an interesting question. While we don’t have a conclusive answer, our current hypothesis is that it is the strong assumption of Diff-Prob that causes such poor performance. \n\nTo start, recall the Bayes optimal deferral rule from Proposition 3.1: $r^{*}(x)  =\\boldsymbol{1}\\left[\\eta\\_{h^{(2)}(x)}(x)-\\eta_{h^{(1)}(x)}(x)>c\\right]$. Diff-01 is based on the one-hot oracle in (3) derived as a one-sample estimator of $\\eta_{h^{(i)}(x)}( x ) = \\mathbb{E}\\_{y \\mid x}\\left[ \\boldsymbol{1}[y = h^{(i)}(x)] \\right]$. This is a straightforward plug-in estimator of the optimal rule that requires no assumption on how close the i-th model $h^{(i)}$ is to the Bayes classifier $\\mathbb{P}(y|x)$.\n\nBy contrast, Diff-Prob is based on the probability oracle in (4):  $\\hat{r}\\_{{\\rm prob}}(x) = \\boldsymbol{1}\\left[ p_y^{(2)}(x) - p_{y}^{(1)}(x) > c\\right]$. Deriving this rule assumes that $\\mathbb{P}(h^{(i)}(x) = y \\mid x)$ is close to $p_y^{(i)}(x)$ for $i \\in \\{1,2\\}$. This may not hold in practice. \n\n> theoretical analysis for the Bayes optimal deferral rule for a cascade of K=2\n\nWe note that Lemma F.1 presents the optimal deferral rule for cascades of $K>2$ models. This supplements Proposition 3.1 in the main text that characterises the optimal deferral rule for cascades of $K=2$ models.\n"}, {"review_id": "9JrkGfrUHu", "reviewer": "Reviewer_6Hfw", "summary": "This paper systematically investigates why and when the confidence-based deferral rule work, and particularly, identifies cases when it fails. To enable this investigation, they provide a theoretical characterization of the problem and the optimal deferral rule. They also provide a post-hoc solution that can work well in cases when the confidence-based method fails.", "questions": "This deferral rule is about selecting models, while there is also this line of research about selecting samples for the noisy data case. Basically, for the data with noisy labels, one would want to select only the clean ones to do the training, and there are also many confidence-based methods to do this selection. I am wondering how these two lines of research connect with each other, and can you similarly identify cases when the confidence-based method fails in label denoising?\n\nIt would be good if the authors can provide some discussion/ideas about how to identify whether it is good to use the confidence-based method in practice. Basically, is there a unified way to identify the failed cases from the data, instead of checking if the data have the issues related to each failed case?", "limitations": "The authors have addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly written.\nThe paper provides a nice theoretical framework for studying the deferral rule in general.\nThe paper provides lots of useful insights, supported by both theoretical and empirical evidence.\n ", "weaknesses": "The listed conditions about when the confidence-based method fails are not that surprising, this leads one wondering the significance of such a contribution if the findings are already something intuitive that need not proof. Anyhow, this might not count as a weakness, as it is also reassuring that the theory does produce intuitively sensible results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The listed conditions about when the confidence-based method fails are not that surprising. Anyhow, this might not count as a weakness, as it is also reassuring that the theory does produce intuitively sensible results.\n\nWe are glad the reviewer finds the results intuitive. We would like to emphasise that despite cascades being studied in various forms for several decades, there has been limited study of the conditions under which confidence-based cascading suffices as a deferral mechanism. We would hope that by clearly laying out specific conditions under which this technique does not suffice, we can aid practitioners in their decision of whether or not to invest in more complex modelling strategies (e.g., post-hoc approaches). This is particularly true for the case of label noise, which we expect to be encountered in many (though not all) practical settings.\n\n\n> .. for the data with noisy labels, one would want to select only the clean ones to do the training, and there are also many confidence-based methods to do this selection. I am wondering how these two lines of research connect with each other\n\nWe thank the reviewer for mentioning this broadly related topic of noisy label learning. Please note that label denoising is outside the scope of the present work. In our work, we address the setting where the two (or more generally $K > 2$) base models are already trained and fixed. The goals are to investigate the performance of confidence-based deferral, identify conditions under which it can fail, and identify approaches to learn a post-hoc rule to remedy it.  In our experiments with label noise (i.e., second row of Figure 2), we assume that the given base models were trained with label noise without an option of fine-tuning them on clean labels.\n\nWe are happy to provide a connection if the reviewer could please point out which work the reviewer has in mind for confidence-based methods for label denoising.\n\n\n>  how to identify whether it is good to use the confidence-based method in practice… is there a unified way to identify the failed cases from the data, \n\nThis is an interesting and important question. We think that the simplest approach is to use a held-out validation dataset that has the same distribution as the test data, produce deferral curves of both confidence-based deferral and post-hoc deferral approaches, and compare them.\nThe three failure cases identified in our work are for studying sufficient causes that lead to a failure of confidence-based deferral. In practice, for the purpose of deciding whether to deploy confidence-based deferral, there is no need to exactly identify one of the three settings.\n\n\n"}, {"review_id": "VJhi3vKPGT", "reviewer": "Reviewer_V2z7", "summary": "This paper explores the cascade deferral problem, which is an issue in the context of machine learning models arranged in a cascading order, where a decision needs to be made about whether to defer the processing of data from one model to the next in the cascade. The challenge is to optimize the deferral decision to achieve the best trade-off between computational costs and model performance.\n\nPreviously, this problem was often addressed using confidence-based deferral rules. This approach involves deferring data to the next model in the cascade when the first model's confidence in its prediction falls below a certain threshold. However, the paper identifies limitations with the confidence-based deferral method. Specifically, it may underperform in certain settings, such as when the second model in the cascade is a specialist model, or when there's label noise in the training data.\n\nTo overcome these limitations, the authors introduce post-hoc deferral rules. Unlike the confidence-based approach, post-hoc deferral rules use additional information, beyond just the confidence of the first model, to make deferral decisions. These rules are trained and optimized to provide better accuracy-cost trade-offs.\n\nThe authors compare the performance of confidence-based and post-hoc deferral rules under various experimental settings. They use datasets like ImageNet and CIFAR 100, with settings including a specialist model scenario, label noise, and distribution shift. They find that post-hoc deferral significantly outperforms confidence-based deferral in scenarios involving a specialist second model and label noise. However, they also identify potential overfitting issues with post-hoc deferral, highlighting the need for careful capacity control.\n", "questions": "The authors acknowledge that post-hoc models can overfit and struggle to generalize. Could the authors provide some intuitive explanation for the reasoning behind this issue? ", "limitations": "The authors have adequately addressed the limitations", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Originality**: The paper introduced a post-hoc deferral scheme that utilizes a Bayes-optimal deferral rule. In particular, it addresses issues not resolved by the traditional confidence-based deferral methods.\n\n**Quality**: The authors effectively utilize mathematical proofs and models to construct and explain their deferral schemes, and they validate these models through extensive experiments on established datasets such as ImageNet and CIFAR 100. \n\n**Clarity**: The paper is well-structured and clearly written. The paper's theoretical concepts are explained with clarity and are substantiated with illustrative figures, while the experimental design and results are presented in detail.\n\n**Significance**: The research addressed a critical limitation in the commonly used confidence-based deferral schemes. Confidence-based methods, while widely used, tend to underperform in certain situations such as in specialist settings or when there is label noise. This research introduces and investigates the efficacy of post-hoc deferral models as a solution to this problem, offering a more optimal and efficient method of deferral. The paper's analysis of the limitations of the confidence-based methods and the demonstration of how the post-hoc deferral models overcome these issues are essential for further research in this area.", "weaknesses": "**Limited Dataset and Task Diversity**: The empirical results of this paper are primarily based on two datasets: CIFAR-100 and ImageNet. Additionally, the experiments were conducted on image classification tasks only. Expanding the scope of datasets and including other tasks, such as object detection, segmentation, or even venturing into different domains like natural language processing or audio processing, could have provided a more comprehensive evaluation of the post-hoc deferral models.\n\n**Generalizability**: The authors point out that post-hoc models can overfit and fail to generalize well, even when controlling the capacity of the model.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for carefully reviewing our work, and for the complete summary which we agree with. \n\n>  The empirical results of this paper are primarily based on two datasets: CIFAR-100 and ImageNet. Additionally, the experiments were conducted on image classification tasks only.\n\nIn the present work, we aim to illustrate when confidence-based deferral can fail with classification  problems. The Bayes optimal deferral rule we derive in Proposition 3.1 and subsequent analyses all start from the risk in Eq (1), which is based on the 0-1 loss. Specifically, the risk of a deferral rule $r$ can be written as\n\n$$ R(r; h^{(1)}, h^{(2)}) = \\text{const.} + \\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]. $$\n\nNote that the risk depends on 0-1 losses of the two base models $h^{(1)}, h^{(2)}$. **For other tasks, one can simply replace these base losses to other appropriate losses (e.g., log loss for language models) and the Bayes optimal rule can be derived.** We plan to include results on NLP classification tasks in the revised version. Please note that we have added results on Mini-ImageNet to the PDF as part of this rebuttal. Please see the response to Reviewer kqwH for details.\n\n\n>  The authors point out that post-hoc models can overfit and fail to generalize well, even when controlling the capacity of the model. Could the authors provide some intuitive explanation for the reasoning behind this issue?\n\nThe studied post-hoc approaches are not without limitations. It can be hard for a small post-hoc model to reliably predict the confidence or confidence difference of much larger models (underfitting). The overfitting case arises especially in (but not limited to) the generalist setting. In this setting, the two base models $h^{(1)}, h^{(2)}$ perform roughly equally well, and there is no obvious set of instances that should be deferred to either of them. In this case, the learned post-hoc deferral model may fail to generalise. This is in contrast to, say, the specialist setting where there is a clear set of instances that should be deferred to $h^{(2)}$ (i.e., the data sub-group that model 2 specialises on).\n"}, {"review_id": "hIHycGXUcr", "reviewer": "Reviewer_ahRx", "summary": "The paper consists of 2 parts. Part 1 contains theoretical analysis of when confidence-based deferral rules for cascades of 2 or more models succeed or fail, based on a proposed risk function (equation (1) in section 3) presenting a tradeoff between accuracy and computational cost of invoking subsequent models. Part 2 proposes new deferral rules that are more sophisticated than existing confidence-based deferral rules using a machine-learned postdoc model. Experiments attempt to justify claims made in part 1 and to show that posthoc-based deferral rules produce better results than others.", "questions": "I need to be able to see that the paper has an objective and that every section is consistent towards that objective. At the moment, the three sections 3, 4 and 5 do not appear to be completely aligned with each other. If you could convince me where I am wrong in the Weaknesses section above, and show me some form of consistency throughout the paper, I will change my opinion.\nIt is unclear to me whether the constant cost $c$ on line 117 in (1) is to be treated as constant or not. It appears to be constant at first (and it makes sense to do so from a practical point of view). But then in section 4.1, $c$ seems to be treated as a variable that can be optimised away. What is the point of having an accuracy-deferral curve for $r^*$ over $c$ if $c$ is constant?", "limitations": "There is no societal negative impact from the paper.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper provides a number of edge cases, both good and bad, together with good explanations on those edge cases.\nReferences to previous works are excellent. However, I cannot claim my expertise in this area.", "weaknesses": "I have found a few places that appear rather puzzling in the followings:\n\n1. Lemma 4.1 line 176: it is unclear what authors mean by \"produce the same ordering over instances x\". The lack of a precise formula makes it unnecessarily difficult to follow the proof for lemma 4.1 and to verify the proof, because I did not know what end result to expect. Eventually I understood what that term meant after carefully checking the appendix. But it was via a few definitions in the proof in the appendix, but not in the lemma statement itself. The statement definitely needs revising.\n\n2. Section 4.1 seems to have a technical flaw in reasoning, despite that Lemma 4.1 appears to be correct. Consider functions $R1(c, c^{(1)}) = R(r_{conf} | c, c^{(1)})$ and $R2(c) = R(r^* | c)$. Lemma 4.1. shows a condition when the accuracy-deferral curve of $r^*$ matches with that of $r_{conf}$. But that is an analysis with respect to accuracy, not risk $R(\\cdot)$ defined in (1). For a given $c$, for example $c$ represents a trade off between accuracy and inference speed, $R2(c)$ is constant but Lemma 4.1 does not guarantee that the lowest value of $R1(c, c^{(1)})$ over $c^{(1)}$ cannot go lower than $R2(c)$. To me, it only makes sense if we assume that the algorithm sees $c$ as a variable and we consider $c^*, R^* = \\[arg\\]min_c{R2(c)}$ instead. However, in such cases there are 2 issues: (1) Lemma 4.1 still does not guarantee that across all possible $(c, c^{(1)})$ pairs, the only time when $R1 = R^*$ is when $c=c^*$, and (2) if $c$ is a variable then how do you take practical considerations like inference speed into the analysis?\nWhile the subsequent success/failure cases in 4.2 seem intuitive to me, I just don't see how Lemma 4.1 can be used to convincingly explain them.\n\n3. The general idea proposed in 4.2 is somewhat weak as well. In order to make a deferral rule for a cascade of 2 models to work better, you need to create a third model, i.e. the posthoc model g(x)? Wouldn't that incur an additional computational cost, meaning the risk function in (1) has to be redefined? I do not see any quantisation of that effect in the experiments.\nIn addition, wouldn't introducing g(x) also mean that you have given a bit of training power to complement model 1 and 2, whereas the general setting of the paper is to treat model 1 and 2 as pre-trained blackboxes not to be tampered with (e.g. line 244-246)? \n\n4. Section 5 presents all results in terms of accuracy-deferral curves. However, I cannot see any curve or any piece of information at all mentioning the risk $R(\\cdot)$ in (1). This is puzzling. On one hand, sections 3 and 4 discuss minimising risk in (1) which can be seen as a tradeoff between accuracy and computational cost. On the other hand, all experiments only present information related to accuracy. I am not sure how those results can completely justify sections 3 and 4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Section 4.1 seems to have a technical flaw in reasoning, despite that Lemma 4.1 appears to be correct… Section 5 presents all results in terms of accuracy-deferral curves… I cannot see any curve or any piece of information at all mentioning the risk $R(\\cdot)$ in (1)\n\n**There appears to be a misunderstanding which we’d like to clarify**. We believe the reviewer’s doubt arises since:\nSection 3 considers the cascade _risk_ (Equation 1) at a fixed _cost parameter_ $c$\nSection 4 and 5 considers the cascade _accuracy_ at a fixed _deferral rate_ $\\tau$, as noted in L126 and L177\n\nThese respectively yield cost-risk curves (as $c$ is varied) and deferral curves (as $\\tau$ is varied). These are _equivalent_ ways of assessing the overall quality of a cascade (see below), and so we use them interchangeably. [This is analogous to the equivalence between ROC and cost curves in classification.] Following prior work (Bolukbasi et al., 2017), (Kag et al., 2023), our experiments use deferral curves to compare methods. We will make this clearer.\n\nIn more detail:\n\nSection 4 seeks to identify when confidence-based deferral produces the “best” possible cascade. By “best”, we mean the cascade which achieves the _best possible deferral curve_, i.e., which achieves maximal accuracy at *all* deferral rates. **Equivalently** (see below), this is the cascade which achieves the best possible _cost-risk curve_, i.e., which achieves minimal risk (1) for *all* cost parameters $c$.\n\nTo make progress, we characterise the “best” cost-risk curve in Proposition 3.1. This shows that to achieve the “best” curve as $c$ varies in $[0, 1]$, we can threshold $s^*( x ) = \\eta\\_{h^{(2)}(x)}(x) - \\eta\\_{h^{(1)}(x)}(x)$ by $c$.\n\nCrucially, there is a **one-to-one correspondence** between the optimal cost-risk and deferral curves. Thus, Proposition 3.1 also characterises the optimal deferral curve, which we reference in Lemma 4.1. To see this correspondence, recall that $\\forall c \\in [0, 1]$, the risk (1) is\n\n$$ R(r; h^{(1)}, h^{(2)}) = \\mathbb{P}(y \\neq h^{(1)}(x), r(x)=0) +\n \\mathbb{P}(y \\neq h^{(2)}(x), r(x)=1) + c \\cdot \\mathbb{P}(r(x)=1). $$\n\nThis captures\n\n$$ (\\text{classification error of the cascade}) + c \\cdot (\\text{deferral rate}). $$\n\nAppealing to the Lagrangian — analogous to the Neyman-Pearson lemma in ROC analysis — $\\exists \\tau \\ge 0$ such that minimising $R(r; h^{(1)}, h^{(2)})$ over $r$ is equivalent to \n\n$$ \\max_{r}  \\quad (\\text{classification accuracy of the cascade}) \\quad \\text{subject to} \\quad  (\\text{deferral rate}) \\leq \\tau. $$\n\nThus, tracing out the optimal cost-risk curve for varying $c$ will trace out the optimal deferral curve for varying $\\tau$.\n\nIn fact, the two curves have an intimate **point-line duality**. Any point $(d_0, e_0)$ in deferral curve space – where $d$ denotes deferral rate, and $e$ denotes error – can be mapped to the line $\\{ (c, c \\cdot d_0 + e_0) : c \\in [0, 1] }$ in cost curve space. Conversely, any point $(c_0, r_0)$ in cost curve space – where $c_0$ denotes cost, and $r_0$ denotes risk – can be mapped to the line $\\{ (d, r_0 - c_0 \\cdot d) : d \\in [0, 1] \\}$ in deferral curve space. This is analogous to the correspondence between ROC and cost-risk curves in classification (Drummond & Holte, “Cost curves: An improved method for visualizing classifier performance”, ‘06). \n\n**We are happy to answer any further queries.** \n\n> What is the point of having an accuracy-deferral curve for $r^*$ over $c$ if $c$ is constant?\n\nOptimising (1) may be cast as a constrained optimisation problem where $c$ (or its re-parameterisation) controls the deferral rate. Changing $c$ changes the constrained optimisation problem. It is thus natural that its solution $r^*$ depends on $c$. Intuitively, varying $c$ allows one to trade off accuracy and inference cost. In practice, one will be operating at a particular point on this trade-off curve, and so there is only one fixed $c$ at inference time.\n\nThe deferral curve helps compare two deferral rules **over all possible choices of the deferral rate**. This is analogous to the use of ROC curves to compare two classifiers over all possible values of relative false positive to false negative cost.\n\n>  cost of the posthoc model g(x)\n\n__Our post-hoc model $g$ is a simple feedforward network and is much smaller than the two base models__. This is described in **Section C.2 (Appendix)** where $g$ has no more than 100 hidden units. In comparison, on the ImageNet problem, we use MobileNet v2 as $h^{(1)}$ (3.5 million parameters), and EfficientNet B0 as $h^{(2)}$ (5.3 million parameters). The cost of invoking $g$ at inference time is negligible with respect to these models. We are happy to add a comment noting this.\n\n\n> [by introducing g(x)] you have given a bit of training power to complement model 1 and 2, whereas the general setting of the paper is to treat model 1 and 2 as pre-trained blackboxes?\n\nWe indeed consider the setting where one cannot modify the models $h^{(1)}$ and $h^{(2)}$. However, exploiting the models’ _outputs_ for further learning is perfectly admissible. \n\nPer L244-246, we are allowed to train a separate post-hoc deferral model $r$. When we use the risk $R(r; h^{(1)}, h^{(2)})$ (see (1)), we optimise for $r$ which is parameterised as thresholding $g(x)$.\n\n\n>  Sections 3, 4 and 5 do not appear to be completely aligned\n\nOur work studies when confidence-based deferral suffices. The logical flow is:\nIn Section 3, we characterise the form of the optimal deferral rule. \nIn Section 4, we identify specific conditions under which confidence-based deferral may disagree with the optimal rule, and study post-hoc deferral approaches in an attempt to address these limitations. \nIn Section 5, we present experiments that verify the above failure modes.\n\n> Meaning of \"produce the same ordering over instances x\"\n\nWe apologise for not being clearer here. Please see the global response.\n"}]

Author rebuttal:
We thank all the reviewers for constructive comments. We will revise our submission accordingly. In what follows, we clarify common points raised by multiple reviewers. *Please note that we have also attached a PDF to this rebuttal.*


> Meaning of “produce the same order” in Lemma 4.1 [Reviewer kqwH, Reviewer ahRx]

**We will make this statement more clear in the revised version.** First, we recall the statement of Lemma 4.1:

__Lemma 4.1__ The deferral rule $r_{\mathrm{conf}}$ produces the same deferral curve as the Bayes-optimal rule (2) __if__ $\eta_{h^{(1)}(x)}(x)$ and $\eta_{h^{(1)}(x)} (x) − \eta_{h^{(2)}(x)} (x)$ produce the same ordering over instances $x \in \mathcal{X}$.

For brevity, we write $\eta_{i}(x)$ for $\eta_{h^{(i)}(x)}(x)$.
* Define real-valued random variables $ z := \eta_{1}(x)$, and $z^* := \eta_{1}(x)-\eta_{2}(x)$ 
where $x \sim \mathbb{P}_{x}$. 
* Let $\gamma_{\alpha},\gamma_{\alpha}^*$ be the $\alpha$-quantile of the distributions of $z$ and $z^*$, respectively. 

By “produce the same ordering over instances $x \in \mathcal{X}$, we precisely mean that for any $x \in \mathcal{X}$ and $\alpha \in [0, 1]$, $\eta_1(x) < \gamma_\alpha \iff \eta_1(x) - \eta_2(x) < \gamma^*_\alpha$. We use this definition in the proof. 



Meta-review: This paper analyzes classifier cascades through the lens of learning-to-defer/reject, studying when the sensible but naive rule of confidence-based deferral would (not) suffice.  Failure modes include when the downstream classifier is a narrow expert and when there is distribution shift.  The reviewers are unanimously in favor of acceptance, agreeing that the work provides a fresh perspective on classifier cascades.  The most significant criticisms are the issue of what is meant by ordering (Reviewer kqwH, Reviewer ahRx) and the practical considerations highlighted by Reviewer ahRx (or rather, the presentation of the issue).  The authors should address these concerns / suggestions in the camera-ready version.
Decision: Accept (poster)