Towards Anytime Classification in Early-Exit Architectures by Enforcing Conditional Monotonicity
Authors: Metod Jazbec
James Urquhart Allingham
Dan Zhang
Eric Nalisnick
Venue: NeurIPS 2023 poster (2023)
Keywords: anytime algorithms
early-exit neural networks
conditional monotonicity
anytime uncertainty
TL;DR: We improve anytime properties of early-exit neural networks by using product-of-experts ensembles.

Abstract: Modern predictive models are often deployed to environments in which computational budgets are dynamic. Anytime algorithms  are well-suited to such environments as, at any point during computation, they can output a prediction whose quality is a function of computation time. Early-exit neural networks have garnered attention in the context of anytime computation due to their capability to provide intermediate predictions at various stages throughout the network. However, we demonstrate that current early-exit networks are not directly applicable to anytime settings, as the quality of predictions for individual data points is not guaranteed to improve with longer computation. To address this shortcoming, we propose an elegant post-hoc modification, based on the Product-of-Experts, that encourages an early-exit network to become gradually confident. This gives our deep models the property of *conditional monotonicity* in the prediction quality---an essential building block towards truly anytime predictive modeling using early-exit architectures. Our empirical results on standard image-classification tasks demonstrate that such behaviors can be achieved while preserving competitive accuracy on average.

Towards Anytime Classification in Early-Exit Architectures by Enforcing Conditional Monotonicity
Metod Jazbec UvA-Bosch Delta Lab University of Amsterdam
James Urquhart Allingham University of Cambridge jua230cam. ac uk
w.jjzbecouua..l ml
Dan Zhang
Eric Nalisnick
Bosch Center for Al & University of Tübingen dan, zhang20de bosch. com
UvA-Bosch Delta Lab University of Amsterdam e. t. w.naaiisnii ck@uva. ialisvickuuva nl
Abstract
Modern predictive models are often deployed to environments in which compu- tational budgets are dynamic. Anytime algorithms are well-suited such envi- ronments as, at any point during computation, they can output a prediction whose quality is function of computation time. Early-exit neural networks have garnered attention the context of anytime computation due to their capability to provide intermediate predictions at various stages throughout the network. However, demonstrate that current early-exit networks are not directly applicable to anytime settings, as the quality of predictions for individual data points is not guaranteed to improve with longer computation. To address this shortcoming, we propose an elegant post-hoc modification, based the Product-offExpertt that encourages early-exit network to become gradually confident. This gives our deep models the property of conditional monotonicity in the prediction quality-an essential step- ping stone towards truly anytime predictive modeling using carly-exit architectures. Our empirical results standard mage-classiffcation tasks demonstrate that such behaviors can be achieved while preserving competitive accuracy average.
Introduction
When deployed in the wild, predictive models are often subject to dynamic constraints their com- putation. Consider a vision system for an autonomous vehicle: the same system should perform well in busy urban environments and on deserted rural roads. Yet the former environment often requires quick decision makinng unlike the latter. Hence, it would be beneficial for our models to be allowed to 'think' long as its environment allows. Deploying models to cnoource-constrainc devices has similar demands. For example, there are roughly 25, 000 different computing configurations of Android devices (Yu et al., 2019], and developers often need to balance poor experience in low-resource settings with under-performance in high-resource settings.
Anytime algorithms can ease, if not resolve, these issues brought about by dynamic constraints on computations. An algorithm called anytime if can quickly produce an approximate solution and subsequently employ additional resources, if available, to incrementally decrease the approximation emorr [Dean and Boddy, 1988, Zilberstein, 1996]. Anytime computation especially valuable when resources can fluctuate during test time. Returning the example of mobile devices, anytime
We give complete definition in Section 2.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

algorithm would be able to gracefully adapt to the computational budget of whatever class of device finds itself on: low pwrfforrrning devices will depend on intermediate (but still good) solutions, while high-perrfie tigh-performin devices can exploit the model's 's maximum abilities.
Early-exit neural networks (EENNs) [TTerrapittayanon al., 2016] have attracted attention as anytime predictors, due to their architecture that can generate predictions at multiple depths [Huang et al., 2018J. However, as we demonstrate, EENNS do not exhibit anytime behavior. Specifically, current EENNS do not possess conditional monotonicity, meaning that the prediction quality for individual data points can deteriorate with longer computation at test time. This lack of monotonicity leads to a decoupling of computation time and output quality- that is decisively not anytime.
In this work, we improve EENNs' ability to perform anytime predictive modeling. We propose lightweight transformation that strongly encourages monotonicity in EENNS' output probabilities as they evolve with network depth. Our method is based on prdduct-of-Experrt formulation [Hinton, 1999] and exploits the fact that a product of probability distributions approximates an 'and' operation. Thus by taking the product over all early-exits computed thus-far, the aggregated predictive distribution is gradually refined over time (exits) to have a non-increasing support. This transformation has an inductive bias that encourages anytime uncertainty: the first exits produce high- entropy predictive distributions-
to their large support-and the EENN becomes progressively confident each additional exit (by decreasing the support and reallocating probability).
In our experiments, we demonstrate across a range of vision classification tasks that our method leads significant improvements in conditional monotonicity in variety of backhone models without re-training. Moreover, our transformation preserves the original model's average accuracy and even improves it in some cases (e.g. CIFAR-100). Thus our work allows the large pool of efficient architectures to be endowed with better anytime properties, all with minimal implementation overhead.
2 Background & Setting of Interest
Data Our primary focus is multi-class classification. 2 Let X' S Rd denote the feature space, and let y denote the label space, which we assume to be a categorical encoding of multiple (K) classes. E X' denotes a feature vector, and y E y denotes the class (1 of K). We assume x and y/ are realizations of the random variables x and y with the (unknown) data distribution y(x,y) = p(y|x) p(x). The training data sample is D {(In. 3n) ) Our experiments focus on vision tasks in which x is a natural image; in the appendix, we also report results on natural language.
Early-Exit Neural Networks: Model and Training Our model of interest is the early-exit neural network [Terrapittayannn et al., 2016] (EENN). For given data-point æ. an EENN defines M total models p(y x æ. Φm: 6m.) m = 1, ...., M,, where om. denotes the parameters for the mth classifier head and 9m are the parameters of the backbone architecture. Each set of parameters Om contains the parameters of all previous models: 0, 02 C ... C 0v.- Due to this nested construction, each model can be thought of as a preliminary 'exit' to the full architecture defined by ON- This enables the network's computation to be "short-circuited" and terminated early exit m, without evaluating later models. Training EENNS is usually done by fitting all exits simultaneously:
N
M
e "ibl...,,M...... ......................... PN: D) = Σ
Σ VIX
Wm log yn xx= = In. Pm: Pm)
(1)
where Wm E R++ are weights that control the degree which each exit is trained. The weights are most often set to be uniform across all exits. For notational brevity, we will denote p - y = x, Φmn 0m)) as Pm (y) æ) henceforth.
Setting of Interest At test time, there are various ways to exploit the advantages of an EENN For example, computation could be halted if input is deemed sufficiently easy such that weaker model (c.g. P1 or P2) can already make an accurate prediction, thus accelcrating inference time. Such efficient computation has been the central focus of the EENNs's literature thus far [Matsubara et al., 2023] and is sometimes referred to as budgeted batch classification [Huang et al., 2018].
"See Appendix B.6 for discussion of anytime regression.

---

However, in this work we focus exclusively on the related, yet distinct, anytime setting motivated in the Introduction. We assume computation is terminated when the current environment cannot support computing and evaluating the (m + 1)th model. These constraints originate solely from the environment, meaning the user or model developer has no control over them. We assume the model will continue to run until it either receives such an external signal to halt or the final-i.e., 1/th-moell is computed [Grubb and Bagnell, 2012]. Furthermore, in line with previous literature on anytime algorithms [Huang et al., 2018, Hu et al., 2019], we assume the model sees one data point at a time when deployed, i.e., the batch size is one at test time.
Anytime Predictive Models To have the potential to be called 'anytime,' an algorithm must produce a sequence of intermediate solutions. the case of classification, an anytime predictive model must hence output series of probability distributions over 3 with the goal of forming better and better approximations of the true conditional data distribution p x). Specifically, we are interested in the evolution of the conditional error for given æ E X, defined here as et <x(x) := Dpp(y æ) Pt (y æ)) where D denotes a suitable distance or divergence (e.g., KL- divergence total-variation), and pı represents model's predictive distribution after computing for time E Rzo. In addition to conditional, i.e. instance-level error we can also consider the evolution of a marginal error defined as & := Ex-p(x)) [=)] For the remainder of this section, we will use e, to refer to both versions of the error and revisit their difference in Section 3. Since this paper focuses on anytime EENNs, 3 we use the early-exit index m as the time index t.
Properties of Anytime Models Zilberstein [1996] enumerates properties that an algorithm should possess to be anytime. Below we summarize Zilberstein [1996]'s points that are relevant to predictive modeling with EENNs, ordering them in hierarchy of necessity:
1. Interruptibilit: The most basic requirement is that the model can be stopped and produce answer at any time. Traditional neural networks do not satisfy interruptibility since they produce a single output after evaluating all layers. However, EENNs do by returning the softmax probabilities for the mth model if the (m + 1)th model has not been computed yet.
2. Monotonicity: The quality of the intermediate solutions should not decrease with computa- tion time. Or equivalently, expending more compute time should guarantee performance does not degrade. For EENNs, monotonicity is achieved if the error cm is non- oonincreasing across carly-cxits: E1 2 ... 2 EM-
3. Consistency: The quality of the intermediate solutions should be correlated with computation time. For EENNs, consistency is of most concern when the amount of computation varies across sub-models. For example, if computing the (m fm++1 1 1t model requires evaluating 10x more residual blocks than the mith model required, then consistent architecture should produce a roughly 10x better solution (6m-1 R 1m))
4. Diminishing Returns: The difference in quality between consecutive solutions is gradu- ally decreasing, with the largest jumps occurring early, e.g. (e1 10 f2) >> (<M--1 - < Monotonicity and consistency need to be satisfied in order for this stronger property to be guaranteed.
For traditional EENN (trained with Equation 1), property #1 is satisfied by construction (by the presence of early-exits). Property #2 is not explicitly encouraged by the typical EENN architecture or training objective. Hence, we begin the next section by investigating if current EENNS demonstrate any signs of monotonicity. Properties #3 and #4 are left to future work since, as we will demonstrate, achieving property #2 non-trivial and is thus the focus of the remainder of this paper.
Estimating Anytime Properties The error sequence {fm J is essential for studying the anytime properties of EENNS. We can equivalently consider the evolution of prediction quality measures 7m and aim for a model that exhibits increasing quality, i.e., 7/m S 7m Vm. For the remainder of the paper, we will work with the notion of prediction quality unless otherwise stated. Observe that each 7'm (and equivalently, em) is always unknown, as it depends on the unknown data distribution p (y x). Consequently, we must rely on estimates 9m. In the presence of a labeled hold-out dataset, we can use ground-trute labels y E y and consider the correctness of the prediction as our estimator:
'While EENNs are the focus of our work. they are not the only model class that can be used for anytime prediction. In theory, any model that yields sequence of predictions could be considered.
3

---

Im (x) := larg max, Pm (y) z)) yy] where [-] is the Iverson bracket." 4 However, such an estimator provides a crude signal (0 or 1) on a conditional level (per data point). As such, it is not congruent with conditional monotonicity or consistency. Due to this, we focus primarily on the probability of the ground-truth class 52, (a: := Pm (y" a:) when examining anytime properties at the conditional level. Finally, estimating marginal prediction quality (error) requires access to pxx). Following common practice, we approximate Bx)p(x) by averaging over the hold-out dataset. Averaging fm (a) and mm (x) corresponds to the test accuracy and the average ground moundt probability the mith exit, respectively.
3 Checking for Monotonicity in Early-Exit Neural Networks
In this section, we take a closer look at state-of-the -fe------th-rrt early-exit neural networks and their mono- tonicity, key property of anytime models. Our results show that EENNs are marginally monotone but lack conditional monotonicity in the prediction quality. For ease of presentation, we focus here on particular EENN (Multi-Scale Dense Net (MSDNet); Huang et al. [2018] 8)) and dataset (CIFAR-100) Section 6 shows that this observation generalizes across other EENNS and datasets.
Marginal Monotonicity The left plot of Figure I reports MSDNet's test accuracy (blue) on CIFAR- 100 as function of the early exits. Accuracy has been the primary focus in the anytime EENN literature [Huang et al., 2018, Hu et al., 2019], and as expected, it increases at each early exit m. Thus MSDNet clearly exhibits marginal monotonicity: monotonicity on average over the test set. The same figure also shows that the average ground-truth probability (orange) increases at each m, meaning that MSDNet demonstrates marginal monotonicity this related quantity as well.
Conditional Monotonicity Yet for real-time decision-makinn systems, such as autonomous driving, it is usually not enough to have marginal monotonieity. Rather, we want conditional monotonicity: that our predictive model will improve instep with computation for every input. If conditional monotonicity achieved, then marginal monotonicity is also guaranteed. However, the converse is not true, making conditional monotonicity the stronger property.
To check if MSDNet demonstrates conditional monotonicity, examine the middle plot of Figure 1. Here we plot the probability of the true label, i.e., 7P, (æ)) as a function of the early exits for 10 randomly sampled test points (again from CIFAR-100), We see that-despite MSDNet being marginally monotonic-it is quite unstable in the probabilities it produces per exit. For example, the purple line exhibits confidence in the correct answer (~ 75%) at the second exit, drops near zero by the fourth exit, becomes confident again (~ 80%) at exits 5 and 6, and finally falls to near zero again at the last exit. Thus MSDNet clearly does not exhibit the stronger form of monotonicity.
We next quantify the degree to which MSDNet is violating conditional monotonicity, First, we define the maximum decrease in the ground-truth probability as MPD> (a) == maxm'>> { mmxx(52 (æ)
2h (xx), {)}. }. For various thresholds E [0, 1), we count how many test instances exhibit probability decrease that exceeds the given threshold: Nr Σ |MPD* (ax,) 2 r). The results are depicted in the right panel of Figure 1. We see that for ~ 25% of test points, the ground-truth probability decreases by at least 0.5 some exit. In a separate analysis (see Appendix 1.1.)), when examining the correctness of prediction measure %/ (x)). we find that ~ 30% of test examples exhibit decreasing trajectories across early exits. 5 A similar finding was reported by Kaya et al. [2019]. Both observations demonstrate that MSDNet, a state-of-the-a EENN, does not exhibit conditional monotonicity nor is it close to achieving it.
4 Transformations for Conditional Monotonicity
In light of the aforementioned challenges with current EENNs in the anytime setting, we explore potential lightweight modifications that could encourage, or even enforce, conditional monotonicity. We first suggest strong baseline for encouraging monotonicity, taking inspiration from Zilberstein [1996]. We then introduce our primary methodology, which is based on product ensembles.
'The Iverson bracket [cond] is cond is true and otherwise.
'This implies that the model incorrectly classifies the data point after correctly predicting it at some of the earlier exits; 4 (æ) = and &5, (æ) = for some m' m.

---

of Test Samples (1)
y Probability
1.0
73
MSDNet
0.70
Monotone Oracle
0.5
Test Accuracy Avg. y Prob.
0.0
1
7
2
7
0.01
0.10
0.20
0.33
0.50
Early Exit
Early Exit
Max y Prob. Decrease
Figure 1: Multi-Scale Dense Network (MSDNet; Huang et al. [2018]) results the test set of CIFAR- 100. Left: test accuracy and average ground-truth probability at each early exit, the two measures of marginal monotonicity we study in this work. Middle: ground-truth probability trajectories (i.e., (6% (x)) (+)))= for random test data points. Right: aggregation analysis on conditional mono- tonicity for MSDNet. Specifically, we compute the maximum decrease in ground-trute probability for each test data point and then plot the percentage of test examples where the drop exceeds various thresholds. A red dashed line denotes the performance of oracle model with perfect conditional monotonicity, i.e., none of the data points exhibit any decrease in the ground-truth probability.
4.1 Caching Anytime Predictors
As noted by Zilberstein [1996], conditional monotonicity can be encouraged by caching the best prediction made so far and returning it (instead of the latest prediction). Yet this requires the ability to measure the prediction quality of intermediate results. While previously introduced quantities, such ground-truth probability 1. (æ), can serve examine anytime properties before deploying the model, their reliance on the true label y renders them unsuitable for measuring prediction quality at test time. As a proxy, we propose using the EENN's internal measure of confidence. We found that simply using the softmax confidence performs well in practice. At an exit m, we compute C'(mm x) := maxy Pm ())x) and overwrite the cache if C(py. x) < C(pm, x), where j is the exit index of the currently cached prediction. We call this approach Caching Anytime (CA) and consider it (strong) baseline. While CA is rather straightforward, it has been thus far overlooked in the anytime EENN literature, as the standard approach is to return the latest prediction [Huang et al., 2018, Hu et al., 2019]. Note that if the anytime model displays conditional monotonicity to begin with, applying CA has no effect since the most recent prediction always at least as good as the cached one.
4.2 Product Anytime Predictors
Our proposed method for achieving conditional monotonicity EENNS is motivated by the following idealized construction.
Guaranteed Conditional Monotonicity via Hard Product-of-Experts Consider an EENN whose sub-classifiers produce 'hard' one-vs-rest probabilities: each class has either probability 0 or 1 (before normalization). Now define the predictive distribution at the mth exit to be a Product-of--B of-peerrss [Hinton, 1999] (PoE) ensemble involving the current and all preceding exits:
PII. (y]x)) = Zm II [f(()), > "h Zm
Σ [ > >b]
(2)
x)
where b is threshold parameter, [-] is an Iverson bracket, f(()) E RK represents a vector of logits at ēth exit, and w, + are ensemble weights. Assuming that a class y is in the support of the final classifier for a given æ, i.c. PH.M (y x) > 0, then such model is guaranteed to be monotone in the probability of y::
PIL. (y) x) S PIL.+11 (y x)) V m.
(3)
The formal proof can be found in Appendix A. Consequently, if the true class y" is in the final support, an EENN with this construction is conditionally monotonic in the ground-tre -tuth probability 46 (x) (as defined in Section 2).
The intuition behind this construction is that at each exit, the newly computed ensemble member casts a binary vote for each class. If class has received vote at every exit thus far, then remains the support of mm m. (y æ). Otherwise, the label drops out of the support and never re-enters. At each
5

---

exit, the set of candidate labels can only either remain the same or be reduced, thus concentrating probability in a non-increasing subset of classes. This construction also has an underconfidence bias: the probability of all labels starts small due to many labels being in the support at the earliest exits. Consequently, the model encouraged to exhibit high uncertainty early on and then to become progressively confident at subsequent exits.
Practical Relaxation using ReLU Although the above construction provides perfect conditional monotonicity (for labels in the final support), often results in a considerable decrease in marginal accuracy (see Appendix B.2). This is not surprising since the predictions. At every exit, all in-support labels have equal probability, and thus the model must select a label from the support at random in order to generate a prediction. The support often large, especially at the early exits, and in turn the model devolves random guessing.
probabilities result in 'blunt'
To overeome this limitation, first notice that using 0 probabilities is equivalent using Heaviside function to map logits to probabilities." In turn, we propose to relax the parameterization, replacing the Heaviside with the ReLU activation function. The ReLU has the nice property that preserves the rank of the 'surviving' logits while still 'nullifying' classes with low logits. Yet this relaxation comes at a price: using ReLUs allows conditional monotonicity to be violated. However, as we will show in Section 6, the violations are rare and well worth the improvements in accuracy. Moreover, the number of violations can be controlled by applying an upper limit to the logits, as detailed in Appendix B.8.
Therefore our final Product Anytime (PA) method for conditional monotonicity is written as:
PrA.m (3 =
Zm II max (fi(z)y. 0)"r Zm =
1
Σ II max (fi(z))' 0)
(4)
where max(:,) returns the maximum of the two arguments. We the ensemble weights to W; i/M since we expect later experts to be stronger predictors. Note that PA'S predictive distribution may degenerate into a zero distribution such that PrA.m (y xx) = 0, Vy y. This occurs when the ensemble's 's experts have non-overlapping support and are thus unable to arrive at consensus prediction. a prediction is required, we fall back on the softmax predictive distribution based on the logits of the classifier at the current exit.
Learning and Post-Hoc Application Equa-
tion 4 can be used for training an EENN di-
1/ Probability
rectly via the negative log-likelihooai However, one can also take pre-trained EENNs (e.g., as open-sourced by the original authors) and apply Equation 4 post-hoc. For this post-hoc applica- tion, the EENN's 's logits are input into Equation 4 rather than into the usual softmax transfor- mation. As we will demonstrate in the experi- ments, post-hoe application endows the model with conditional monotonicity without any sub- stantial degradation the original model's ac- curacy. In cases such as CIFAR-100 we find that our method actually improves the accuracy of the pre-trained model. The only metric we find to be sensitive training from scratch post-hoc application is confidence calibration, with the former providing better calibration properties. This result will be demonstrated in Figure 6. Thus, we currently recommend using our method via post-hoc application, as it requires minimal implementation overhead (about three lines of code) and allows the user to easily toggle between anytime and traditional behavior.
0.5
0.0
6
Figure 2: Ground-truth probability trajectories (i.e., ( (x)) ) for 10 random test data points after applying our PA method. For comparison, MSD- Net's trajectories from Figure are reproduced in the background.
For a visualization of how our host-hoc PA affects probability trajectories, see Figure 2. PA manages to rectify the backbone EENN's non-monotone behavior to large extent. As concrete example of how this can help with anytime predictions, we can consider again the scenario of Android
'In the most widely used softmax parameterization of the categorical likelihood, the exponential function is used when transforming logits into probabilities.

---

phones introduced in Section 1. Deploying the original MSDNet might result in certain data points receiving inferior predictions on a higher-spec device compared to device with limited computational capabilities. However, if we apply our PA to an MSDNet, such inconsistencies become far less likely due to the model's monotonic behavior.
5 Related work
Anytime Algorithms [Dean and Boddy, 1988, Zilberstein, 1996] have long been studied outside the context of neural networks. For instance, Wellman and Liu [1994] considered Bayesian networks in anytime settings, while Grubb and Bagnell [2012] proposed an anytime Ada-Boost algorithm [Bishop, 2007] and also studied Haar-like features [ [Viola and Jones, 2001] for anytime object detection. More recently, modern neural networks have been used in models with only marginal anytime properties (Huang al., 201 8, Hu et al., 2019, Liu et al., 2022]. Our research improves upon this work by bringing these models a step closer to having per-data-point anytime prediction, a much stronger form of anytime computation.
Early-Eat Exit Neural Networks [Teerapittayanon et al., 2016, Yang et al., 2020, Han et al., 2022a] have been investigated for applications in computer vision [Huang al., 2018, Kaya et al., 2019] and natural language processing [Schwartz et al., 2020, Schuster et al., 2021, I, Xu and McAuley, 2023]. A wide variety of backbone architectures has been explored, encompassing recurrent neural networks [Graves, 2016], convolutional networks [Huang et al., 2018], and transformers [Wang et al., 2021] I. Furthermore, ensembling of EENNs intermediate predictions has been considered [Qendro et al., 2021, Wolczyk et al., 2021, Meronen et al., 2023), primarily to enhance their uncertainty quantification capabilities. Our objective is to leverage the recent advancements in early-exit networks and make them suitable for true (conditional) anytime predictive modeling.
Related to critique of current EENNs, Kaya et al. [2019] and Wolczyk et al. [2021] also observed that prediction quality can decline at later exits, calling the phenomenon 'overthinking. These works address the problem via methods for early termination. Our work aims to impose monotonicity on the ground-trum -ouund-truthpg probabilities, which eliminates 'overthinking' by definition. We further examine the connection to Kaya al. [2019] and Wolczyk al. [2021] in Appendix B.5.
Product-off Expeers [Hinton, 1999, 2002] ensembles have been extensively studied in the generative modeling domain due to their ability to yield sharper distributions compared to Mixture-of-Fxpeeee ensembles [Wu and Goodman, 2018, Huang et al., 2022]. However, in the supervised setting, PoE ensembles have received relatively little attention [Pignat et al., 2022]. PoE is often applied only post-hoc, likely due to training difficulties [Cao and Fleet, 2014, Watson and Morimoto, 2022].
6 Experiments
We conduct two sets of experiments." 7 First, in Section 6.1, we verify that our method (PA) maintains strong average performance while significantly improving conditional monotonicity in ofate-of-the-an art EENNs making them more suitable for the anytime prediction task. To check that our findings generalize across data modalities, we also conduct NLP experiments and present the results in Appendix B.4. In the second set of experiments, detailed in Section 6.2, we move beyond prediction quality and shift focus monotonicity's effect uncertainty quantification in the anytime setting. Lastly, we point out some limitations in Section 6.3.
Datasets We consider CIFAR-10, CIFAR-100 [Krizhevsky et al., 2009], and ILSVRC 2012 (Ima- geNet; Deng al. [2009]). The CIFAR datasets each contain 50k training and 10k test images, while ImageNet is larger dataset with 1.2M training and 50k test instances. The three datasets consist of 10, 100, and 1000 classes, respectively.
Baselines We use four state-of-the-art EENNs as baselines and backbone architectures. The first the Multi-Scale Dense Network (MSDNet: Huang al. [2018]), which consists of stacked convolutional blocks. To maximize performance at each early-exit, the authors introduce: (1) feature maps on multiple scales, ensuring that coarse-level features are available all throughout the network,
Our code is publicly available at https: / http://gttthbccce http:////...ee///aaaaaaaaaaaaaaa
7

---

CIFAR-10
CIFAR-100
ImageNet
0.98
0.80
0:97
0.84
0.75
Test Accuracy (1)
0:96
0.20
0.65
0.91
baseline
MSDNNet
0.90
PA (ours)
0.60
IMTA
0.61
DVIT
0.89
Early Exit
Figure 3: Test accuracy on the CIFAR and ImageNet datasets, Our PA method maintains competitive performance compared to the baseline models. For each model and dataset, we use the same number of early exits as proposed by the authors. We plot the average accuracy from n = 3 independent runs. To enhance the readability of the plot, we omit the error bars here well as the results of the L.2W model and report them in Appendix B.11.
and (2) dense connectivity to prevent earlier classifiers from negatively impacting later ones. The second baseline is the IMTA network [Li et al., 2019], which shares MSDNet's architecture but is trained with regularization that improves collaboration across the classifiers of each exit. The third baseline is the L2W model [Han et al.. 2022b], which enhances MSDNet by learning to weight easy and hard samples differently at each exit during training. The intuition is that easier samples should contribute more the fitting of earlier exits, while harder samples should be more influential for later exits. Lastly, we consider the Dynamic Vision Transformer (DViT; Wang et al. [2021]), which composed of stacked transformer networks that differ in the number of patches into which they divide input image. We report results for the T2T-VTT-12 instantiation of DVIT. During testing, all baselines employ softmax parameterization for their categorical likelihood and solely rely on the most recent prediction at each early exit.
6.1 Anytime Prediction with Conditional Monotonicity
Test Accuracy We first verify that post-hoe application of our PA transformation preserves the original model's test accuracy. Maintaining test accuracy is essential, as simply examining conditional monotonicity in isolation does not provide complete picture. For instance, model that predicts ground-truth probability of zero at every exit would exhibit perfect conditional monotonicity while being useless in practice. Figure 3 reports accuracy per exit for the three backbones models, comparing the original model (-) to our proposals PA (- -) and CA (...). We find that our monotonicity methods do not significantly degrade test accuracy any case. some instances, such as the MSDNet results on CIFAR- 100 (middle, blue), our PA even improves accuracy. Comparing our proposals, PA tends to outperform CA accuracy, although the advantage is often slight.
Conditional Monotonicity Next, we quantify the degree to which each model is conditionally monotonic, again using the maximum probability decrease metric (MPD') ") used in Figure 1 (right.. Figure reports the percentage of test cases that exhibit a drop the ground-truth probability at any exit. Firstly. we see that CA and PA drastically improve monotonicity in all cases. Moreover, PA is clearly superior to CA for CIFAR- 100 and ImageNet. On CIFAR-10, 10, PA and CA perform on par for smaller decrease thresholds, with PA outperforming CA again for larger thresholds. Notably, ImageNet, our PA method does not exhibit a drop in ground-truth probability larger than 0.01 for any test example for all three models.
From the results in Figures and 4, one might wonder a simpler change to the backbone EENN could lead to similar improvements in conditional monotonicity as our PA. To test this, we looked at 'vanilla' early-exit ensembles where predictive distributions from different exits are combined using either mixture-of-expert (MoE) product-of-experts (PoE), see Appendix B.2 for the results. While using ensembles heneficial, is insufficient to achieve improvements in monotonicity similar to those of PA. This highlights the importance of the activation function (that maps logits

---

CIFAR-10
CIFAR-100
ImageNet
% of Test Samples (L)
baseline
MSDNe
PA (ouns)
IMTA
DVIT
10
10P
0.0
0.1
0.2
0.3
0.4
0.0
0.3 0.5
0.1
0.2
0.3
0.4
0.5
Max Ground-Truie (y*) Probability Decrease
Figure 4: The % of test examples with ground-truth probability drop exceeding particular threshold. Our PA significantly improves the conditional monotonicity of ground-truth probabilities across various datasets and backbone models. To better illustrate the different behavior of various methods, log scale used for the y-axis. We report average monotonicity together with one standard deviation based on 3 independent runs. For DVIT [Wang al., 2021]. we unable to perform multiple independent runs, and report the results for various models instantiations instead, see Appendix B. 1. Note that for PA, the monotonicity eurves ImageNet (almost perfectly) overlap at y 0 for all backhone models considered. We also report results for the L.2W model in Appendix B.11, which are largely the same for MSDNet.
to probabilities) when it comes to achieving more monotone behavior. We additionally explored calibrating the backbone EENN would be enough to make the underlying model monotone. While post-hoc calibrating every exit does help with monotonicity, it does not perform as well as PA; see Appendix B.9.
Monotonicity in Correctness Our PA approach yields close to perfect conditional monotonicity when considering probability the estimator of prediction quality. Yet it also worth checking other estimators are monotonic, such as the correctness of the prediction, i.e., 4 (z). For correctness, we observe similar improvements in conditional monotonicity; see Appendix B.1.2 for detailed analysis. For example, on CIFAR-106 100, MSDNet 'forgets' the correct answer in ~ 30% of test cases, whereas applying post-hoc PA reduces these monotonicity violations to 13% of cases.
6.2 Anytime Uncertainty
We also examine the uncertainty quantification abilities of these anytime models. Again con- sider Figure 2, the probability trajectories ob- tained from post-hoc PA. The probabilities start low at first few exits, indicating high uncertainty in the early stages of anytime evaluation. The left plot of Figure further supports this insight, showing that the average entropy of the PA pre- dictive distributions is high and reduces at each early exit. Lastly, in the right plot, we present the average size of conformal sets" each exit. The set size reflects the model's predictive un- certainty, with larger sets indicating more uncer- tainty. Thus we see that PA is best at uncertainty quantification: it is quite uncertain at the earli- est exits (set size of ~ 11) 1) but grows twice as confident by the last exit (set size of ~ 4). CA and regular MSDNet keep a relatively constant size by comparison, only varying between
12.5
Entropy
10.0
Conformal
2
Early Exit
Early Exit
Figure 5: Uncertainty measures for the MSDNett model on the CIFAR-100. Left: average test tropy of (categorical) predictive distributions for each early exit. Right: mean size of conformal sets at each exit point. To obtain conformal scores, we used Regularized Adaptive Predictive Sets algo- rithm [RAPS; Angelopoulos et al., 2021]. 20% of test examples were used hold-out to caleu- late conformal quantiles at each early exit.
*Conformal sets are prediction sets over y that are marginally guaranteed to contain the ground --uttthh label (without making any assumptions on the underlying data distribution). For more on conformal sets, see Shafer and Vovk [2008].

---

11 and 7.5. Hence, the monotonicity properties of PA result in an appealing link between uncertainty and computation time; and we term this property as anytime uncertainty. This is an appropriate inductive bias for anytime predictive models since, intuitively, making quicker decisions should entail a higher level of uncertainty. Lastly, in Appendix B.7, we present results of conditional level experiments where we find that our PA yields significantly more monotone (i.e., non-increasing) uncertainty patterns.
6.3 Limitations
Label Sets with Small Cardinality We observe that PA's performance in terms of conditional monotonicity improves as the number of classes |)|| increases. For instance, PA yields fully monotone trajectories on ImageNet, but not for datasets with smaller number of classes like CIFAR-10, where Appendix
we detect small violations. This finding is further supported by our NL.P experiments B.4, where | is smaller compared to the image classification datasets considered in this section. Based on this finding, we recommend using the CA approach over PA for scenarios in which |J] 5.
Calibration Gap Due to its aforementioned un- derconfidence bias, post-hoc PA generates poorly calibrated probabilities during the initial exits, as illustrated in the left plot of Figure 6. Yet this is pri- marily observed in expected calibration error (ECE) and related metrics. It disappears when considering some alternative metrics to ECE, as shown in the right plot of Figure 12. Finetuning with PA as an optimization objective, as opposed to applying it post-hoc, closes the calibration gap in most cases, albeit at some cost to accuracy and monotonicity. See Figure (right) for conerete examples of how PA with finetuning affects ground-truth probability trajectories. addition, we experimented with adap- tive thresholding in PA, using different thresholds b for distinct data points, rather than employing 0 for all data points as with ReLU, and found that it can also be beneficial in terms of calibration. For more details on finetuning and adaptive thresholding, as well as a discussion on the relevance of ECE-like metrics in the anytime setting, see Appendix B.3.
ECE (4)
PA with Finetuning
(A-FT)oum))
3 Probability
0.8
04
0.0
0.0
2
6
Early Exit
Early Exit
Figure 6: Calibration analysis for MSDNet on CIFAR-100. Left: expected calibration er- ror (ECE) during anytime evaluation. Right: Ground-truth probability trajectories for 10 random test data points after applying our PA with finetuning (PA-FT) method. For compari- son, MSDNet's trajectories from Figure are reproduced in the background.
7 Conclusion
We have demonstrated that expending more time during prediction in current early-exit neural networks can lead to reduced prediction quality, rendering these models unsuitable for direct ap- plication in anytime settings. To address this issue, we proposed a post-hoe modification based on Product-of-Fxxpee Expertss--tttssseoo and showed through empirical and theoretical analysis that it greatly improves conditional monotonicity with respect to prediction quality over time while preserving competitive overall performance.
In future work, we aim to further improve EENNs by imbuing them with other critical anytime properties, such as diminishing returns and consistency. Moreover, it would be interesting to study the impact of monotonicity in other settings, such as budgeted batch classification. We report some preliminary results in Appendix 10 finding the monotonicity to be less beneficial there compared to the anytime setting, which was the focus of our work. We also plan to delve deeper into the concept of anytime uncertainty. Although we have (briefly) touched upon it in this study, we believe more comprehensive and formal definition is necessary for the development of robust and reliable anytime models.
10

---

Acknowledgments and Disclosure of Funding
We thank Alexander Timans and Rajeev Verma for helpful discussions. We are also grateful to the anonymous reviewers who helped improve work with their constructive feedback. MJ and EN are generously supported by the Bosch Center for Artificial Intelligence. JUA acknowledges funding from the EPSRC, the Michael E. Fisher Studentship in Machine Learning, and the Qualcomm Innovation Fellowship.
References
J. U. Allingham and E. Nalisnick. A Product of Experts Approach to Early-Exit Ensembles. Technical report, 2022.
A. N. Angelopoulos, S. Bates, M. I. Jordan, and J. Malik. Uncertainty sets for image classifiers using conformal prediction. In 9th International Conference on Learning Representationss ICLR, 2021.
J. Antorán, J. U. Allingham, and J. M. Hermández-Lobato Depth uncertainty in neural networks. In Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, 2020.
C. M. Bishop. Puttern recognition and machine learning, 5th Edition. Information science and statistics. Springer, 2007. ISBN 9780387310732.
Y. Cao and J. Fleet. Generalized product of experts for automatic and principled fusion of gaussian process predictions. CoRR, 2014. URL http://arxiv org/ hts///bs//// 1410. 7827.
E. Daxberger, A. Kristiadi, A. Immer, R. Eschenhagen, M. Bauer, and P. Hennig. Laplace redux effortless bayesian deep learning. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems, 2021.
T. L. Dean and M. S. Boddy. An analysis of time-dependent planning. Proceedings of the 7th National Conference Artificial Intelligence. AAAI Press / The MIT Press, 1988.
J. Deng, W. Dong, R. Socher, Li, K. Li, and L. Fei-Fei. Imagenet: A large-scale hierarchical image database. In JEEE Computer Society Conference Computer Vision and Pattern Recognition (CVPR), 2009.
A. Graves. Adaptive computation time for recurrent neural networks. CoRR, 2016. URL http: //arxiv. org/ abs/1603. 08983.
A. Grubb and D. Bagnell. Speedboost: Anytime prediction with uniform near-optimality. In Proceedings of the Fiffeenth International Conference on Artificial Intelligence and Statistics, AISTATS, 2012.
C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning, ICML, 2017.
Y. Han, G. Huang, S. Song, L. Yang, H. Wang, and Y. Wang. Dynamic neural networks: A survey. IEEE Trans. Pattern Anal. Mach. Intell., 2022a.
Y. Han, Y. Pu, Z. Lai, C. Wang, S. Song, J. Cao, W. Huang, C. Deng, and G. Huang. Learning weight samples for dynamic early-exiting networks. In Computer Vision ECCV. Springer, 2022b.
G. E. Hinton. Products of experts. Technical report, 1999.
G. E. Hinton. 2002.
Training products of experts by minimizing contrastive divergence. Neural Comput.,
H. Hu, D. Dey, M. Hebert, and J. A. Bagnell. Learning anytime predictions in neural networks via adaptive loss balancing. The Thirty-Thirl Conference on Artificial Intelligence, AAAL AAAI Press, 2019.
11

---

G. Huang, D. Chen, T. Li, F. Wu, L. van der Maaten, and K. Q. Weinberger. Multi-scale dense networks for resource efficient image classification. In 6th International Conference on Learning Representations, ICI.R, 2018.
X. Huang, A. Mallya, T. Wang, and M. Liu. Multimodal conditional image synthesis with product-of- experts gans. In Computer Vision ECCV. Springer, 2022.
Y. Kaya, Hong, and T. Dumitras. Shallow-deep networks: Understanding and mitigating network overthinking. In Proceedings of the 36th International Conference on Machine Learning, ICML. PMLR, 2019.
I. D. Kivlichan, Z. Lin, J. 7. Liu, and L.. Vasserman. Measuring and improving model- collaboration using uncertainty estimation. CoRR, 2021. URL httppss//aaxxiv..oggga////////// 04212.
A. Krizhevsky, G. Hinton, et Learning multiple layers of features from tiny images. 2009.
B. Lakshminarayanann A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, 2017.
H. Li, H. Zhang, X. Qi, R. Yang, and G. Huang. Improved techniques for training adaptive deep networks. In IEEE/CVF International Conference on Computer Vision, ICCV. IEEE, 2019.
Z. Liu, Z. Xu, H. Wang, T. Darelll and E. Shelhamer. Anytime dense prediction with confidence adaptivity. The Tenth International Conference on Learning Representations, ICLR, 2022.
Y. Matsubara, M. Levorato, and F. Restuccia. Split computing and early exiting for deep learning applications: Survey and research challenges. ACM Comput. Surv., 2023.
L. Meronen, M. Trapp. A. Pilzer, L. Yang, and A. Solin. Fixing overconfidence in dynamic neural networks. CORR, 2023. doi: 10.485550ar2xi.2332..6666 arXiv. arXiv.2302.000 2302 06359.
URL https://ēoi. org/10. 48550/
E. Pignat, J. Silvério, and S. Calinon. Learning from demonstration using products of experts: Applications to manipulation and task prioritization. Int. J. Robotics Res., 2022.
L. Qendro, Campbell, P. Liò, and C. Mascolo. Early exit ensembles for uncertainty quantification. In Machine Leurning for Health, MLAH NeurlPS 2021, Proceedings of Machine Learning Research, PMLR, 2021.
Schuster, A. Fisch, T. S. Jaakkola, and R. Barzilay. Consistent accelerated inference via confident adaptive transformers. In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, EMNLP, 2021.
R. Schwartz, G. Stanovsky, S. Swayamdipta, Dodge, and N. Smith. The right tool for the job: Matching model and instance complexities. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL, 2020.
G. Shafer and Vovk. tutorial on conformal prediction. Mach. Learn. Res., 2008
Teerapitaayanon, McDanel, and H. T. Kung. Branchynet: Fast inference via early exiting from deep neural networks. In 23rd International Conference on Pattern Recognition, ICPR. IEEE, 2016.
A. Viola and M. Jones. Rapid object detection using a boosted cascade of simple features. In 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2001.
Y. Wang, Huang, S. Song, Z. Huang, and G. Huang. Not all images are worth 16x16 words: Dy- namic transformers for efficient image recognition. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, 2021.
C. Watson and T. K. Morimoto. Learning nor-parametric models in real time via online generalized product of experts. IEEE Robotics Autom. Lett., 2022.
12

---

M. P. Wellman and C. Liu. State-space abstraction for anytime evaluation of probabilistic networks. In UAI '94 Proceedings of the Tenth Annual Conference on Uncertainty in Artificial Intelligence. 1994.
M. Wolezyk, B. Wojeik, K. Balazy, I. T. Podolak, J. Tabor, M. Smieja, and T. Trzcinski. Zero time waste: Recycling predictions in early exit neural networks. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, 2021.
M. Wu and N. D. Goodman. Multimodal generative models for scalable supprl--uperrvieed learn- ing. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, 2018.
C. Xu and J. J. McAuley, A survey on dynamic neural networks for natural language processing, In Findings of the Association for Computational Linguistics: EACL, 2023.
L. Yang, Y. Han, X. Chen, S. Song, J. Dai, and G. Huang. Resolution adaptive networks for efficient inference. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR, 2020.
J. Yu, L. Yang, N. Xu, J. Yang, and T. S. Huang. Slimmable neural networks. In 7th International Conference on Learning Representations, ICLR, 2019.
S. Zilberstein. Using anytime algorithms in intelligent systems. Al Magazine, 1996.
13

---

The Appendix is structured as follows:
We provide proof of conditional guarantees in EENNS for (hard) PoE in Appendix A.
We present conditional monotonicity results using alternative estimators performance quality Nm in Appendix B.1.
We conduct an ablation study for our PA model in Appendix B.2.
We propose two modifications to PA that help with reducing the calibration gap in Appendix B.3.
We report results of NLP experiments in Appendix B.4.
We delve into the connections between conditional monotonicity and previously introduced concepts in EENNs literature in Appendix B.5.
We discuss anytime regression and deep ensembles in Appendix B.6.
We present conditional monotonicity results using uncertainty measures Appendix B.7.
We propose technique for controlling the violations of conditional monotonicity in PA in Appendix B.8.
We study the impact of calibration the conditional monotonicity in Appendix B.9. We provide budgeted batch classification results in Appendix B.
We provide additional plots Appendix B.1
A Theoretical Results
In the following, we provide a proof for conditional monotonicity of (hard) Product-of-Experts ensembles presented in Section 4.2.
Proposition. Let PILm (y x>) represent the Product-og Experts ensemble of the first m early-exits. Furthermore, let E y denote any class that is present in the support of the full-NN product distribution, iee, Pu,M (y) xt) > O. Under the assumption that the Heaviside activation function is used map logits to probabilities in each pm (y x), it follows that:
PII.m (yl x)) S pr (y) x))
for every early-exit m and for every input x.
Proof. Using the definition of the PoE ensemble and that of the Heaviside activation function, the predictive likelihood at the mtth early exit can be written as
PII.m (y [ = Zm II [f((x), > b]th Zm
Σ II > b]
VEiL...., K)
where fe(x) E R denotes vector of logits at the i-th early-exit, b represents a chosen threshold, and wt R$ represent ensemble weights. Since assume that class is in the support of the full NN ensemble, i.e., PH.M (y x) > 0, follows that
m+11
II [1()) > 1=1
II [1<))>>)]] =1 =1 Vm M,.., 1. ==1
M
then remains show that the normalization constant non-increasing, i.e., Zm 2 7m+11 Vm. To this end observe that [sm+1 (
b] Wm++ E {00,1}, Vy V, using which we proceed as m
Zm Σ II [f/ > 0
M'((I...,R K)i=1
Σ II [f(())y > >b) uh [fm+1( > b] 7m++>
Wm+1
V'E(L....]K i=1
where Zm = Zm+1 if [fm+1(0)y umt1 = 14 E y and Zm > Zm+t otherwise.
14

---

B Additional Experiments
B.1
Conditional Monotonicity
In the main paper, the ground-truth probability was our focus when studying conditional monotonicity in early-exit networks. Here, we supplement these findings with additional results, utilizing alternative estimators of prediction quality 7m.
B.1.1 Full-Model Prediction Probability
Suppose only an unlabeled hold-out dataset is available. In that case, the anytime properties of EENNs can still be investigated by relying on the full model prediction y := arg maxy PM (y xx) instead of y". Naturally, the merit of this alternative hinges on the underlying model being accurate in most cases. Furthermore, besides serving as substitute for the ground-truth probability in the absence of labeled dataset, the evolution of the full-model prediction probability can be used as stand-alone measure of how well early-exits in an EENN approximate the full model.
In Figure 7, we present conditional monotonicity results using V probability as the prediction quality measure. Similar the results presented in Section 6.1 for y probability, we conclude that our PA outperforms both the baseline models and CA approach across all datasets considered.
CIFAR-10
CIFAR-I0U
ImageNet
% of Test Samples (L)
baseline
MSDNet
(ours)
10a
CA
DWT
10P
0
0.1
0.3
0.
0.0
0.1
0.2
0.3
0.1
0.5
0.0
0.1
0.2
0.3
0.5
Max Full-Model Prediction (i) Probability Decrease
Figure 7: The percentage of test examples with a full-model prediction probability drop exceeding a specified threshold. PA significantly improves the conditional monotonicity properties of ground ground-truth probabilities across various datasets and backbone models. To better illustrate the different behavior of various methods, a log scale is used for y-axis. We report average monotonicity together with one standard deviation based on n = independent runs. For DVIT [Wang et al., 2021], we were unable to perform multiple independent runs and report the results for various model instantiations instead; see Appendix I.
B.1.2 Correctness of Prediction
We next shift our focus to the correctness of prediction an estimator of performance quality. Recall from Section 2 its definition: (x) := [arg max, Pm (y x) = y²]. a binary measure that can only take on the values of 0 or 1, and thus provides a less nuanced signal about the evolution of the performance quality compared to probability- interval (0, 1].
measures that evolve more continuously in
To aggregate the results of the conditional monotonicity analysis, we consider the following two quantities:
7mono: the percentage of test data points that exhibit fully monotone trajectories in the correctness of the prediction, i.c. % (z) < 4 (æ), Vm. This implies that if the model managed to arrive at the correct prediction at the mith exit, it will not forget it at later exits.
An oracle model with perfect conditional monotonicity will result in %mams = 100%.
Vezeoi the number of points for which the EENN model is wrong at all exits. This is used to account for trivial solutions of the monotonicity desideratum: 3 (ax) 0, Vm. Naturally, the smaller the %ooo. the better.
15

---

Table 1: Aggregated results of conditional monotonicity analysis based on correctness of prediction as performance quality measure. MSDNet [Huang al., 2018) 8] used as a backbone model for PA and CA for the results reported here. See Section 1.1.2 for definition of Mmooo and V2w.-
CIFAR-10
CIFAR-100
ImageNet
% mono (1)
Tozero (4)
% mono (t)
Tozero (4)
7mmooo (t)
Tozero (4)
MSDNet
91.8
3.6
70.8
12.6
84.9
20.4
PA (ours)
96.2
4.6
87.2
16.4
93.5
24.1
CA
97.8
5.5
90.8
18.6
94.5
25.6
Results are displayed in Table 1. Comparing our PA model against the MSDNet baseline, we observe significant improvement in terms of the percentage of test data points that exhibit perfect conditional monotonicity, i.e., Xmonno However, this improvement comes at cost, as fewer points have a correct prediction for least one exit. Despite this trade-off, the magnitude of improvement in %mono is larger compared to the degradation of Uzero across all datasets considered, which demonstrates that our PA method improves the conditional monotonicity of T. (a:) non-trivial manner.
Although the Caching Anytime (CA) method outperforms PA in terms of omomo across all datasets, is worth noting that a considerable portion of CA's outperformance can be attributed trivial solutions (i.e., 2h, (z) = O, Vm), which is reflected by CA's poor performance in terms of %zero. Furthermore, the fact that neither CA nor PA fully achieves conditional monotonicity in prediction correctness (i.e., Vmonoo = 100) highlights that there is still potential for further improvement in endowing EENNS with conditional monotonicity.
B.2 Product Anytime (PA) Ablations
To better understand the role of different components our proposed PA method, we conduct several ablations and present the results in Figure 8. In accordance with the theoretical results we presented in Section 4.2, we observe that the PoE ensemble combined with the Heaviside activation (-) yields model that exhibits complete conditional monotonicity in the full model prediction (i.e., y) probability." However, this combination also leads a model with inferior performance terms of overall test accuracy (see left plot). As mentioned, this occurs because the model assigns an equal probability to all classes in its support. The ReL.U activation resolves this issue by performing on with Heaviside in terms of monotonicity and on par with exponential, i.e., softmax, in terms of accuracy, thus combining the best of both worlds.
Test Accuracy (1)
Conditional Monotonicity
Conditional Monotonicity
% of Test Samples (U)
% of Test Samples (L)
0.75
10
10
0.71
Pol
No Ens.
ReLU expomential Heaviside
MoF
10
0.025
3
6
0.0
0.2
0.3
0.5
0.0 0.1
0.2
0.1
0.5
Early Exit
Max 9 Probability Decrease
Max Probability Decrease
Figure 8: Test accuracy and conditional monotonicity properties of various PA model instantiations for the CIFAR- 100 dataset using MSDNet a backbone. Specifically, we vary (1) the type of activation function for mapping logits to probabilities and (2) the type of ensembling. Our proposed PA method uses ReLU activation function with product ensembling (-) and is the only method to perform well in terms of both accuracy and monotonicity.
Note that J == arg max, Par (y) x:) is by definition part of the support of the final classifier pm.a (unless it degenerates to a zero distribution). However, this is not necessarily the case for y", which is the reason for a slight violation of conditional monotonicity in the PoE-Heavisidd model, as in the right plot of Figure 8.
16

---

Delving deeper into the ReLU activation function and examining various ensembling styles, we also observe Figure 8 that Mixture-of Eexture-of-Experts with ReLU (MoE-ReLU; ...) demonstrates performance comparable to our proposed PA (PoE-ReLLU; -) in terms of both overall accuracy and conditional monotonicity. The MoF predictive distribution the mth exit is defined as:
(ff(())y)
PMoE.m (v|x) =
wi Ps ()) Ps (v)x)
Eye(l..... (f((())))
where a IK + -22 represents a chosen activation function, such as ReLU, and we utilize uniform weights 1/m. Given this observation, one might question why we prefer PoE over MoE our final model. The rationale for this decision is two-fold. First, the proof presented in Appendix A, which serves the inspiration for method, is only valid when PoE ensembling is employed. Second, unlike the bosed model, the MoE-based model does not exhibit anytime uncertainty. Instead, it demonstrates constant underconfidence across all exits, illustrated in Figure 9. Considering these factors, we find PoE to be superior to MoE for anytime prediction purposes and incorporate it into final proposed solution.
Avg. Max Class Probabiiltty
1.0
0.8
PCC (L)
MSDNet
PoE-ReLU
0.6
McE-ReLU
No ReLU
0.4
0.2
0.0
Early Exit
Early Exit
Figure 9: Expected Calibration Error (ECE: left) and average maximum class probability over the test dataset (right) for various instantiations of our PA model using the MSDNet model as backbone on the CIFAR-100. Only product ensembling (PoE) gives rise to a model that gets progressively more confident with more early exits, exemplified by decreasing ECE and increasing magnitude of probability. On the contrary, mixture ensembles (MoE) result in constant underconfidence.
Early-Exit Ensembles Baselines MoE-exponential (-..) and PoE-exponential (-) can also be interpreted as early-exit ensemble baselines for our PA approach. Instead of relying only on the current predictive distributions (as we do when reporting backbone EENNs results in Section 6), we ensemble distributions across all exits to and including the current one. However, it is clear from Figure that ensembling softmax predictions is insufficient for achieving conditional monotonicity, as both approaches significantly underperform compared to our PA. This underscores the importance of the activation function that maps logits to probabilities for improving monotonicity properties in EENNs. In Figure 10, verify that these findings hold on the ImageNet dataset well, where again find that our PA is the only configuration that performs well both in terms of marginal accuracy and conditional monotonicity.
Sigmoid Activation Function So far, we have discussed why the ReLU function preferred over the Heaviside or exponential (softmax) functions for transforming logits into probabilities in our setting. We also considered the sigmoid activation function; however, upon further examination, we identified two drawbacks that make it less suitable in our context. Firstly, the sigmoid function lacks the "nullifying" effect of ReLU. As a result, the support for classes diminishes more slowly, and we do not observe the same anytime uncertainty behavior we do with ReLU (see Section 6.2). Secondly, logits with larger values all map to the same value, approximately 1, under the sigmoid function. This can negatively impact accuracy, as it does not preserve the ranking. Figure 11 illustrates the results using the sigmoid activation function for the CIFAR-100 100 dataset with MSDNet as a backbone: our choice of ReLU clearly outperforms the sigmoid activation.
17

---

Test Accuracy (1)
Conditional Monotonicity
Conditional Monotonicity
Test Samples ())
5% Test Samples (J)
101
10
0.65
0.60
PoE
exporentaal Heaviside
No Ens.
100
10"
Moli
1
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
02
0.3
0.4
0.5
Early Exit
Max @ Probability Decrease
Max y" Probability Decrease
Test accuracy and conditional monotonicity properties of various PA model instantiations for the ImageNet dataset using MSDNet as backbone. Our PA (-) is the only method to perform well in terms of both accuracy and monotonicity. Note that the monotonicity curves for ReLU and Heaviside activation functions (almost perfectly) overlap at y =
Figure 10:
% of Test Samples ())
Aocuracy (1)
0.75
0.6
0.70
10
ECE (L)
0..5
0.4
0.65
baseline Sigmoid
109
0.60
0.2
0.1
0.4
Early Exit
Max Ground Trantd-Truthha (y") Prob. Decrease
Early Exit
Figure 11: Test accuracy, conditional monotonicity and ECE results for MSDNet model (-) CIFAR-100 dataset. Using sigmoid activation function (-) hurts both accuracy as well as calibration.
Hence, utilize ReLU activation in our proposed PA
B.3 Closing the Calibration Gap
Here outline two modifications proposed PA method aimed at reducing the calibration gap reported in Section 6.3.
B.3.1 Adaptive Thresholds
RCF (4)
OC AUROC 0.5% (1)
We first introduce an extension of our Product Anytime (PA) method, which enables navigating the monotonicity-caliraa
0.90
trade-off scenar- ios when a hold-out validation dataset is avail- able.
0.4
0.55
MSDNa
0.2
(ourss)
FA--T (oum)
Recall that ReLU is used as an activation func- tion in PA to map logits probabilities. This implies that 0 is used as a threshold, determining which classes 'survive' and get propagated fur- ther, and which do not. However, is arguably an arbitrary threshold, and one could consider another positive constant 6 E I++ instead. It is important note that the choice of directly influences the size of the support of the predic- tive likelihood. As illustrated Figure 13, larger value of 5 results in smaller number of classes with positive probability (as expected). This larger threshold does also lead to reduc- tion the coverage of PA'S predictive sets with respect to the ground ground-truth class. However, the
0.50
2
Early Exit
Early Exit
Figure 12: Calibration analysis for MSDNet on CIFAR-100. Left: expected calibration error (ECE) during anytime evaluation. Right: Oracle- Collaborative AUROC with 0.5% deferral |OC AU- ROC; Kivlichan et al., 2021], which simulates realistic scenario of algorihh collabora- tion by measuring the performance of a classifier when is able defer some examples an oracle, based on its maximum class probability.
18

---

1.00
0.76
10
PA S" Coverage
0.98
Test Test Accuracy (t)
0.74
PA Set Size
0.96
30
0.72
PA Threshold
0.94
0.70
20
0.92
0.68
10
0.90
0.66
0.88
1
2
3
6
2
2
3
7
Early Exit
Figure 13: Static threshold analysis for PA using MSDNet backbone on CIFAR-100 dataset.
PA'S predictive set is defined as: (Z..) == {y E / PrA. (y æn.) > 0}. Right: Average size of PA's predictive at each exit. As expected, increasing leads smaller sets. Middle: (Empirical) Coverage of ground-truth class at each exit: Cy := 2n LVm E 8m (xx)] Niet- As b increases, it becomes more likely for the true class y" to fall outside of the support giving rise a smaller coverage. Left: The marginal test accuracy at each exit is shown as the threshold parameter b varies.
Increasing negatively affects accuracy, though the impact is minor for smaller values of b.
decrease in coverage does not significantly af- fect the overall accuracy of the model, as shown the far right plot.
Expanding on this concept, one can also consider udaptive thresholding: rather than using the same threshold value for all data points, the model could dynamically adjust the threshold in the activation function based on the current example. Ideally, when the model is confident in its prediction, a higher value of b employed, resulting in smaller predictive sets. Conversely, when faced with a more challenging example, lower threshold is utilized to capture the model's uncertainty.
Switching to ReLU with adaptive thresholding, the predictive likelihood at ith exit (before ensembling) is given by:
max
Pt (y|z)=
Event... max (((()))))))))))))))))
where 7 BR - +R+ maps the vector of logits ((x) E R to non-negative threshold." 10
Here, we consider threshold functions of the form (f(x)) = C P. po (f(x)) where pe : RK + [0, 1] is model that estimates the probability of the datapoint being classified correctly, and C is constant that ensures the outputs of 7 have a similar magnitude to that of logits. To estimate C and vi, rely the hold-out validation dataset. Specifically,
fit binary logistic regression model using labels yh. == [0,. = v Additionally, we only use the K = 3 largest logits as input to the regression model, as have empirically found that excluding the rest does not significantly impact the performance. To find C, we perform a simple grid search and select the value that yields the best trade-off on the validation dataset. We fit thresholding model only the first exit and then reuse it at later exits, as this approach yielded satisfactory performance for the purposes of our analysis. It is likely that fitting separate thresholding model each exit would lead to further performance benefits.
monotonicity-calibratiii
In Figure 14, we observe that PA with adaptive thresholding still improves baseline in terms of monotonicity (middle plot, note the log-scale of y-axis). Although the adaptive thresholding approach demonstrates worse monotonicity when compared to the PA algorithm with static threshold (i.e.,
т 0). it outperforms the PA method in terms of calibration, as measured by the Expected Calibration Error (ECE). To further elucidate the influence of addpttie thresholding, Figure 15 presents the ground- truth probability trajectories for a random selection of test data points. In general, it is apparent
IIn general, 7 could depend on the datapoint æ itself; however, since we desire an efficient model (to avoid adding excessive overhead during inference time), we opt for a more lightweight option based on the processed input, ie., logits.
19

---

% of Test Samples (U)
Test Accuracy (1)
0.70
BCB (L)
0.4
0.66
0.3
MSDNet
10
0.2
0.62
PA (Adapt Thres)
2
0.0
0.1
02
03
0.4
0.5
2
7
Early Exit
Max y" Probability Decrease
Early Exit
Figure 14: Results for CIFAR-100 using MSDNet the backbone model. We that adaptive thresholding can be effective reducing PA's calibration gap, though at some cost to both test accuracy and conditional monotonicity. Note that the baseline results in this figure differ slightly from those in Figures and 4, as less data (90%) was used to fit the model, with a portion of the training dataset (10%) used to fit the thresholding model
MSDNet
PA
PA (Adapt Thres)
Ground- Ground-Truth Truth Probability
1.0
0.6
0.2
0.0
6
Farly Exit
Figure 15: Ground-truth probability trajectories (i.e., { (x)) m=1) for 10 random test CIFAR-100 100 data points using MSDNet as backbone. Both instantiations of PA yield more monotone ground- truth probability trajectories.
that adaptive thresholding method, albeit at some expense to both conditional monotonicity and overall accuracy.
effective strategy for improving the calibration of the PA
B.3.2 PA Finetuning
The post-hoc nature our proposed PA method is attractive due its minimal implementation overhead. However, as mentioned in Section 6.3, it seems to adversely affect calibration, according to ECE-like metrics, when compared to baseline models. This discrepancy might be due mismatch between the objectives during training and testing in the PA method. To examine this hypothesis, we consider training our model using the PA predictive likelihood (as given by Equation 4) and assess its effect on calibration.
Given the product structure and the non-smooth activation function (ReLU) employed in PA's likelihood, the training can be quite challenging. To enhance the stability of the training process, we introduce two modifications. Firstly, instead of training the model from scratch, we begin by training with a standard EENN objective (see Equation 1) with a softmax likelihood and then finetune the model using the PA likelihood the end. 11 Secondly, we substitute the ReLU activation function with Softplus function 12 which we found aids in stabilizing the model's 's convergence during training. Consequently, we also utilize Softplus to map logits to (unnormalized) probabilities during testing. Moreover, we found that using ensemble weights
is more effective for models finetuned
We train with EENN objective for first 2/3 epochs and with objective for the last 1/3 of epochs. Softplus is smooth approximation of the ReLU function: Softplus(2) == log(1 + exp
20

---

CIFAR-10
% of Test Samples (U)
Test Accuracy (1)
10'
0.92
ECE (L)
0.91
0.2
0.90
10
0.89
0.0
CIFAR-100
% of Test Samples (U)
Test Test Accuracy (1)
0.6
10'
BCE (L)
0.70
MSDNet
PA
10
0.2
0.65
PA Finetune
0.0
0.1
0.2
0.3
0.1
0.5
ImageNet
of Test Test Samples ())
Test Accuracy (1)
0.70
0.65
10a
ECE
0.4
0.60
PA
MSDNet
0.2
PA Finetune
0.55
0
0.0
0.1
022
03
0.4
0.5
5
Early Exit
Max y" Probability Decrease
Early Exit
Figure 16: Results for various image classification datasets using MSDNet the backbone model. We see that finetuning with PA (as opposed to only applying it post-hoc) can be effective in reducing PA's calibration gap, though some cost both test accuracy and conditional monotonicity.
with the PA objective, as opposed to our default choice of wm = m/M presented in the main paper for post-hoc PA.
The results are presented in Figure 16. Focusing initially on (marginal) test accuracy (right), we note that PA training (-) has slight negative impact on performance, particularly when contrasted with the post-hoc PA (-). Similarly, it underperforms post-hoc PA in terms of conditional monotonicity (middle), but it considerably surpasses the baseline MSDNet model (-). When considering ECE, becomes clear that fine-tuning with PA leads to significant improvements over post-hoe PA, thus substantiating our hypothesis that the calibration gap mainly arises from the discrepancy between train-time and test-time objectives. On the CIFAR-100 dataset, PA with finetuning even outperforms the baseline MSDNet in terms of ECE.
Based on these observations, we conclude that integrating during the training of EENNs is an effective strategy for bridging the calibration gap, though it incurs a minor cost in terms of overall accuracy and conditional monotonicity. We note that these costs could be mitigated (or ideally, completely eliminated) through further stabilization of product training. As such, we view this as promising avenue for future research.
B.3.3 Relevance of ECE in Anytime Prediction Setting
In Section 6.3, we pointed out poor Expected Calibration Error (ECE) in the initial exits as one of the limitations our proposed PA method. is important to note, however, that no decision the anytime setting is based on model (or prediction) confidence, i.e., max, Pm (y xz). This contrasts with the budgeted batch classification setting [Huang et al., 2018], where the decision on when to exit could be based on the model confidence. Thus, believe that our PA potentially undermining
21

---

model confidence, as evident by poor ECE in the earlier exits, is not a limitation that would seriously impact the merit of our solution. Especially since we focus solely on the anytime setting, where, we would argue, non-monotone behavior in terms of performance quality is much more serious issue.
However, it is true that model/prediction confidence, i.e. maxy Pm (u m)) could be useful in the anytime scenario as a proxy for model uncertainty. This allows the model-when prompted by its environment make a prediction-to also offer an estimate of uncertainty alongside that prediction. However, given that our PA potentially adversely affects model confidence in earlier exits, we caution against its use. Instead, we recommend alternative measures of uncertainty that better align with our model, such as the conformal set size (c.f., Section 6.2).
B.4 NLP Experiments
In this section, conduct NLP experiments with the aim of demonstrating that our proposed ap- proaches for adapting EENNs for anytime inference are generalizable across different data modalities.
Specifically, we employ early-exit model from Schwartz et al. [2020], in which the BERT model adapted for accelerated inference. The considered datasets are (1) IMDB, binary sentiment classification dataset; (2) AG, news topic identification dataset with | 4; and (3) SNLI where the objective is to predict whether a hypothesis sentence agrees with, contradicts, or is neutral in relation to premise sentence (|>) 3). We adhere to the same data preprocessing and model training procedures as outlined in Schwartz et al. [2020].
To account for the smaller number of classes in these NLP datasets, we shift logits for (small) constant prior to applying ReLU activation function. Henee the PA likelihood at mth exit has the form (before applying product ensembling):
Pm (y a)) max (x) 1/C, 0)"
where C' represents the cardinality of y. This helps with reducing the possibility of PA collapsing to a zero distribution.
The results are depicted Figure 17. Similar to our image classification experiments discussed in Section 6.1, we find that our proposed modifications yield comparable overall accuracy, as shown in the left plot. Considering conditional monotonicity (middle plot), at least one of our two suggested methods outperforms the baseline model on every dataset. However, the degree of improvement in monotonicity is considerably smaller in comparison to our image classification experiments, with the PA model even failing to yield consistent improvement on certain datasets, such as IMDB. We attribute this not to the change in data modality, but rather to the fewer number of classes in the NLP datasets used in this section as compared to the image datasets used Section 6.1.
IMDB
Test Accuracy (f)
0.90
% of Test Samples (L)
% Test Samples (L)
AG
10
101
SNLI
0.85
0.80
baseline PA (ours)
109
100
0.1
0.2
0.3
0.5
0.0
0.2
0.3
0.4 0.5
Early Exit
Max y Probability Decrease
Max 9 Probability Decrease
Figure 17: NLP experiments results using the BERT model from Schwartz et al. [2020] as the backbone. Despite the findings being qualitatively similar to those presented in Figures 3 and 4 for image classification datasets, the enhancement in terms of conditional monotonicity provided by our proposed methods is less pronounced for the NLP classification tasks considered this section.
22

---

B.5 Overthinking and Hindsight Improvability
In this section, we delve deeper into concepts that have been previously introduced in EENN literature and that share connection with the idea of conditional monotonicity, which is the focus our study,
In Kaya et al. [2019], the authors discovered that EENNS, for some data points, yield correct predictions early on but then produce incorrect results later exits phenomenon they term overthinking. Consequently. the authors noted that early-exiting in deep neural networks is not only beneficial for speeding up inference but sometimes To measure overthinking, they considered the difference in performance between an oracle model that exits the first exit with the correct answer!4 and the performance of the full EENN pM (y xc). In the anytime setting, we desire a model with the lowest overthinking measure, i.e., 0, as this indicates that evaluating more layers in the early-exit network does not negatively impact performance.
lead to improved overall test accuracy.
In Figure 18, we present the results of the overthinking analysis for the MSDNet [Huang et al., 2018] model. We observe that both of our proposed methods significantly improve in terms of the overthinking measure (left), making them more applicable anytime scenarios.
Overthinking Measure (U)
0.90
0.80
MSDNet
Oracle Model Accuracy
Full Model Accuracy
0:12
PA (ours)
0.85
0.75
CA
0.08
0.80
0.70
0.05
0.25
0.65
0.03
0.00
0.20
0.60
CIFAR100
ImageNel
CIFAR1OO
ImageNet
CIFARIOO
ImageNNt
Figure 18: Overthinking analysis based Kaya et al. [2019] using the MSDNet model. Our methods substantially improve upon the baseline MSDNet in terms of the overthinking measure (left), making them more suitable for anytime setting. However, most of these improvements can be attributed to a decrease the theoretical performance of the oracle model (middle) rather than to the improvement of the full EENN performance (right). For more detailed explanation of the quantities depicted, please refer to Section B.5.
We also note that a decrease in the overthinking measure can result from either (1) a reduction in the (theoretical) performance the oracle model or (2) an improvement in the (actual) performance of the full EENN. As can be seen in Figure 18 (middle and right), our proposed modifications mainly improve the overthinking measure through (1). To explore this further, in Figure 19 we plot the number of test points that the model learned, i.e., correctly predicted for the first time, and the number of points that the model forgot, i.e., incorrectly predicted for the first time, at each early exit. Both PA and CA show a clear strength in minimizing forgetting, although they do so at the cost of diminishing baseline model's ability learn correct predictions. These results indicate that there is further room for improvement in the adaptation of EENNS for anytime computation, the ideal model would minimize forgetting without compromising its learning abilities.
45, (x:) and 5e (2) some m' > m. ""Such model cannot be implemented in practice, as it requires access ground-truth values. Nevertheless. it is interesting study way better understand the upper bound the achievable performance of the underlying model.
Ussng notation introduced Section this implies:
"TThese observations are consistent with the analysis presented in Section B.1.2 where used correctness of prediction measure for conditional monotonicity
23

---

Hindsight Improvability (L)
80
% Test Samples (L)
Test Test Accuracy (f)
(ours)
0.70
CA
0.2
0.60
0.1
Early Exit
Max y" Probability Decrease
Early Exit
Figure 20: Results for CIFAR-100 using 7 Waste (ZTW; Wolezyk et al. [2021]) model. Applying our PA method ZTW model leads to large improvements in terms of conditional monotonicity (middle) and hindsight improvability (right), while only causing minor decrease in marginal accuracy (left).
Learn (1)
Forget (1)
10
MSDNet
FA (ours)
% of Tost Tost Samples
CA
Early Exit
Early Exit
Figure Learn-vs-forget analysis the CIFAR-IOM dataset using the MSDNet model. Specifically, plot the number of data points that are correctly classified for the first time (left) and the number of data points that are incorrectly predicted for the first time (right) at each early exit. We observe that our modifications help the model 'forget" less, though this comes with minor trade-off in the model's s ability to 'learn'.
In follow-up study by Wolezyk al. [2021], the hindsight improvability (HI) measure is introduced. For each early exit, this measure takes into account the set of incorrectly predicted points and computes the percentage of those that were accurately predicted at any of the previous exits. In an anytime setting, an ideal model would consistently exhibit HI measure of O. As evidenced by the results in Figure 20, our post-hoe modifications substantially enhance the measure (right plot) while only causing minor negative impact overall accuracy (left plot). Similar to the overthinking measure, the observation that HI for our proposed methods suggests potential for further improvements.
24

---

B.6 Deep Ensembles and Regression
Although we have presented our results for classification with early-exit neural networks, we can easily extend them to handle generic deep ensembles and regression settings.
Deep Ensembles While applying our method to deep ensembles might seem strange since they have no implicit ordering as in the case of early-exit NNs, we note that ensembles are often evaluated sequentially low resource settings where there is not enough memory to evaluate all of the ensemble members concurrently. In such settings, there is an implicit, if arbitrary, ordering, and we may still require anytime properties so that we can stop evaluating additional ensemble members at any point. Therefore, we can apply both Product Anytime and Caching Anytime-4 as in Section 4-to to deep ensembles, where pm (y) a)) now represents the m-th ensemble member, rather than the mn-the early exit. An earlier version of this work [Allingham and Nalisnick, 2022] focused product anytime in the deep ensembles case. However, in that work, the focus was also on training from scratch consider in this work. Training from scratch is challenging due
rather than the post-hoc setting to, among other things, 16 instabilities caused by the Product-of-Experts and the bounded support of the likelihoods. Thus, the PA results from Allingham and Nalisnick [2022] are worse in terms of predictive performance than the standard ensemble baseline. Note that our theoretical results in Appendix A also apply in the deep ensembles case." !7 Figure 21 shows qualitative results for anytime ensembles applied to a simple classification task. As expected, the support shrinks as we add more multiplicands to the product.
Figure 21: Evolution of the support for each 4-classes ( a spiral-arm classification task with 5-member anytime ensemble, 1 to 5 (left to right) members included in the prediction.
Regression Product Anytime can be applied to regression by using uniform likelihood at each early-exit (or ensemble member)
Pm (y ær) [amm bm)
which results a product likelihood
Pram (y) x)) U(amaxx bmin)
where amax m {am }) and 6min = m (6mm)) }). That is. the lower and upper bounds of the product are, respectively, the maximum-lower and minimum-upper bounds of the multiplicands. As we add more multiplicands, the width of the product density can only get smaller or stay the same, and thus the probability of the modal prediction Pi:m (i x) can only increase stay the same, in the classification case. Figure 22 shows qualitative results for anytime ensembles applied to a simple regression task. We see that the order of evaluation is unimportant. Firstly, as expected, the final result is the same, and in both cases, the support size always decreases or is unchanged. Secondly, the fit has almost converged within a few evaluations, and the last few multiplicands tend to have smaller effects. Note that the prediction bounds cover the data well even for the poorer early fits. Finally, note that there no support outside of the training data range- we consider this data as out-of-distribution.
For example, Allingham and Nalisnick [2022] use a mixture the product and individual likelihoods as their loss function to encourage the individual ensemble members to fit the data well. However, they use the standard softmax likelihood with an exponential activation function for the individual ensemble members, which conflicts with the Heaviside activations in the product likelihood and results in reduced performance.
We note that Allingham and Nalisnick [2022] neglect an important property required for monotonicity of the modal probability: p.. (y x) must be uniform in addition to having finite support. Le., in the classification setting, the activation function used map logits to probabilities must be the Heaviside function.
25

---

Figure 22: Evolution of the the product support and mode (-) for the simple Id [Antorán al., 2020] regression task with 5-member anytime ensemble, to 5 (left to right) members included the prediction. In each column the support of the multiplicand to be included in the next column's product are shown The top and bottom show different arbitrary orderings of the ensemble members.
B.7 Anytime Uncertainty: Conditional Monotonicity
In Section 6.2, we presented the results of uncertainty experiments where observed that, marginally, our PA model demonstrates an anytime uncertainty pattern: the model starts with high uncertainty early and then progressively becomes more confident at later exits.
In this section, we supplement these experiments with an analysis at the conditional level. Specif- ically, for a given æ X, we compute the uncertainty (for instance, entropy) at each early exit: [ Following the approach we used in Section 3 for performance quality sequences, we define a maximun increase in uncertainty MUI(x): == maXm'>> { max(Um/ (x)) Un (z).
Next, for range of suitably chosen thresholds т E R20, we compute the number of test instances that exhibit uncertainty increase surpassing given threshold N, := =,,, [MUI(x,.) 2 r]. Note that monotone oracle model would exhibit entirely non-increasing uncertainty trajectories, meaning
Nr = 0, VT.
% of Tost Samples (
CIFAR-10
CIFAR-100
ImageNet
10a
baseline
PA (ours)
101
CA
10a
0
0.0
0.4
0.6
0.8
1.0
0.0
0.2
0.6
0.8
1.0
0.0
0.4
0.6
0.8
1.0
Figure 23: Conditional monotonicity using entropy as an uncertainty measure and MSDNet model as backbone. To better illustrate the different behavior of various methods, log scale is used for the y-axis. Our PA exhibits a significantly more monotone behavior compared to the baseline MSDNet [Huang et al., 2018] model.
The results for entropy and conformal set size are depicted in Figures 23 and 24, respectively. We observe that an EENN like MSDNet exhibits non-monotone behavior also in its uncertainty estimates across different exits. This means that there are data points where the model starts with high confidence the initial exits becomes less certain in subsequent stages. Such a trend problematic in the anytime setting, similar to the issues of non-monotonicity in performance quality (c.f., Section 3). It suggests that the model expends additional computational resources only to diminish its confidence in its response. Reassuringly, our PA aids in ensuring monotonicity not only
26

---

in terms of performance quality (e.g.. ground ground-truth probability) but also in its uncertainty estimates (e.g,, conformal size) as evident in Figures 24 and 23.
% of Test Test Samples (1)
CIFAR-10 10
CIFAR-100
ImageNet
baseline
10a
(ours)
10a
Figure 24: Conditional monotonicity using conformal set size as uncertainty measure and MSDNet model as a backbone. To better illustrate the different behavior of various methods, a log scale used for the y-axis. Same as in Figure 5, we used Regularized Adaptive Predictive Sets algorithm [RAPS; Angelopoulos et al., 2021] to compute conformal scores. 20% of test examples were used as hold-out set to calculate conformal quantiles at each early exit. Our PA exhibits a significantly more monotone behavior compared to the baseline MSDNet [Huang al., 2018] model.
B.8 Controlling the Violations of Conditional Monotonicity
In Section 4.2, we introduced our Product Anytime (PA) method. It relies on the ReLU activation function map logits (unnormalized) probabilities, which unfortunately compromises the strong conditional monotonicity guarantees that are present when using the Heaviside activation function.
In this section, propose technique that allows for more nuanced control of violations of conditional guarantees. To illustrate this, observe first that ReLU and Heaviside are specific cases of the following activation function:
axx) = Co max (min(ni b), 0)
(6)
where C. max 1, 1/6). Notice how limo a(x) ReLU(z) and lim a(x)
Hcaviside(zr). Therefore, by adjusting the clipping threshold b. we can navigate the accuracy-
monotonicity trade-off needed. This is demonstrated on the CIFAR-10 dataset in Figure 25.
% of Test Samples (L)
Test Test Accuracy (1)
Test Samples
b
0.8
1.5
1.0
0.4
100
0.2
0.0
6
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.
0.4
0.5
Early Exit
Max y" Probability Decrease
Max Probability Decrease
Figure 25: Test accuracy (left) and conditional monotonicity (middle and right) on CIFAR-10 dataset for various instantiations of the PA model with the MSDNet backbone. We vary the clipping threshold b used in the activation function when mapping logits to probabilities. When b is close to O, the activation function approximates the Heaviside function, resulting in more monotone behavior, although this comes with decrease in (marginal) accuracy. As b is increased, the activation function moves closer ReLUU, leading to more violations of monotonicity, also enhancing accuracy.
27

---

B.9 Impact of Calibration on Conditional Monotonicity
In this section, we study whether monotonicity could achieved by calibrating the underlying EENN rather than employing our proposed PA. To answer this, conducted an experiment where we calibrated MSDNet and analyzed its effect on monotonicity. For the calibration, we utilized three standard techniques: temperature scaling [Guo et al., 2017], deep ensembles [Lakshminarayanaa) et al., 2017], and last-layer Laplace [Daxberger et al., 2021] In Figure 26, we present results for MSDNet CIFAR-100. While all three approaches lead better calibration in terms of ECE (right plot), our PA significantly outperforms them conditional monotonicity (middle plot). Moreover, all three baselines are (arguably) more complex compared our PA: temperature scaling requires validation data, deep ensemble has M-times more parameters (M being the ensemble size), and Laplace is significantly slower compared to PA since we need test-time sampling estimate the predictive posterior at each exit.
However, simply improving calibration might not be expected improve monotonicity. Thus, in Figure 26, we also provide results for combining the above uncertainty calibration techniques with our CA baseline. We see that this combination provides further improvements w.r.t. monotonicity the improved calibration allows for better caching of the correct prediction. However, the monotonicity of these complicated. This demonstrates that monotonicity can not be achieved via calibration alone and further underlines the value of our proposed approach.
methods still underperforms compared to PA despite being more
Test Accuracy (1)
0.775
% of Test Te'Teet Samples (L)
102
0.6
baseline
0.750
PA
101
ECE (L)
Laplace
0.725
DE(5)
0.700
Temp
0.675
10
CA
0.1
0.5
Early Exit
Max Ground-Trume (y") Prob. Decrease
Early Exit
Figure 26: Comparison of our PA with calibrated baselines using MSDNet backbone CIFAR- 100 dataset. For calibration, we use last-layer Laplace, deep ensembles with M 5, and temperature scaling, Additionally, we consider both caching (-) and non-caching (- -) versions of calibrated baselines. None of the considered calibrated baselines outperforms our PA in terms of monotonicity (middle), despite being more complex. The blue and purple solid lines overlap in the accuracy plot (leff), indicating that the temperature scaling does not affect accuracy for the non-cached version, as expected.
B.10 Budgeted Batch Classification
In this section, we conduct budgeted batch classification experiment using MSDNet [Huang et al., 2018] as the backbone. In budgeted batch classification, limited amount of compute is available to classify a batch of datapoints. The goal is to design a model that can allocate resources smartly between easy and hard examples to maximize the overall performance, such accuracy.
The results are shown in Figure 27. Since MSDNet outperforms our PA at most computational budgets, we conclude that the monotonicity is less beneficial in budgeted batch classification. However, as seen on CIFAR datasets, the non-monotonicity of MSDNet is also concerning in this setting for larger values of FLOPs, MSDNet performance starts to drop, while PA keeps monotonically increasing and surpasses MSDNet. Based on these results, we suggest "turning on" our PA only for anytime prediction and recommend that the user sticks to the original EENN in the budgeted batch classification. However, this certainly warrants further investigation (as seen by the performance benefits of our PA on CIFAR for larger FLOPs).
28

---

CIFAR-10
CIFAR-100
ImageNet
Test Accuracy (1)
725
70.0
MSDNet
67.5
MSDNet
MSDNet
PA
PA
PA
90
0.06
FLOPs [1e9]
Figure 27: Budgeted batch classification results for the MSDNet model. To measure the available computational resources, we use FLOPs. Lower FLOPs will encourage the model to rely more on initial exits, while larger number of FLOPs will encourage the model to propagate more points to the later exits. Our PA modification proves to be less beneficial in this setting, as seen by its inferior performance compared MSDNet for most of the computational budgets.
B.11 Additional Plots
Here, we provide additional results that were omitted in Section 6. to enhance the readability of the plots there. Specifically, in Figure 28, we include test accuracy results, along with their respective error bars, for the MSDNet [Huang et al., 2018] and IMTA [Li et al., 2019] models. In Figures 31 and 32, we present results for the L2W model [Han al., 2022b]. We observe that our findings also generalize to this EENN our PA preserves the marginal accuracy while significantly improving conditional monotonicity across all considered datasets.
As for the DVIT [Wang et al., 2021] model, our attempts to train this model from scratch using the published 18 were unsuccessful. Hence, resorted to working with the pre-trained models provided by the authors. They only published a single pre-trained model for each model version, and result, instead of presenting results for independent runs with varying random seeds, display the results for all provided DViT model instantiations in Figure 29 and 30.
CIFAR-10
CIFAR-100
ImageNet
0.76
0.73
Test Accuracy (1)
0.70
0.92
0.72
0.68
0.91
0.68
0.66
0.62
baseline
0.64
PA (ours)
0.60
MSDNet
0.89
0.62
CA
0.58
IMTA
6
7
3
Early Exit
Figure 28: Test accuracy on the CIFAR and ImageNet datasets. Our PA method maintains a competitive performance compared to the baseline models. For each model and dataset, we use the same number of early exits as proposed by the authors. We plot the average accuracy from a independent runs.
29

---

CIFAR-I0
CIFAR-100
ImageNet
Tost Accuracy (f)
0,985
0.0
0.80
0.980
0.88
0.755
0.75
DVT DVT.T2t.yat14
0.86
baseline
DVT DVV..Dei.son small
PA (ours)
DVT_Tatviij12
0.4
0.70
CA
2
Early Exit
Figure 29; Test accuracy on the CIFAR and ImageNet datasets for various instantiations of DVIT model [Wang et al., 2021].
CIFAR-10
CIFAR-100
ImageNet
% of Test Samples les (1)
DVT_T2CviL.
(ours)
Deit small
107
CA
10P
0.4
0.0
0.3
0.5
0.1
0.3
0.4
Max Ground- Truth (y") Probability Decrease
The % of test examples with ground-truth probability drop exceeding a particular threshold for various instantiations of DVTT model [Wang et al., 2021]. Our PA significantly improves the conditional monotonicity of ground-truth probabilities across various datasets and backbone models. To better illustrate the different behavior various methods, a log scale used for the y-axis.
Figure 30:
CIFAR-10
CIFAR-100
ImageNet
0.750
0.750
Test Accuracy (f)
0:93
0.700
0.700
0.91
0.675
0.90
0.650
baseline
PA (ours)
0.60
CA
12W
0.625
2
3
2
2
Early Exit
Figure 31: Test accuracy on the CIFAR and ImageNet datasets for L2W model [Han et al., 2022b]. We plot the average accuracy from n 3 independent runs.
30

---

CIFAR-10
CIFAR-100
ImageNet
% of Tost Samples (L)
12W
10
baseline
10P
(ours)
0.0
0.1
0.2
0.3
04
0.5
0.0
0.1
0.2
033
04
0.5
0.0
0.1
0.2
0.3
0.4
0.5
Max Ground-Truth (y*) Probability Decrease
Figure 32: The test examples with a ground-truth probability drop exceeding a particular threshold for L2W model [Han et al., 2022b]. Results averaged over = 3 independent runs. To better illustrate the different behavior various methods, a log scale is used for the y-axis.
31


Reviews:
[{"review_id": "cmGngf7dtY", "reviewer": "Reviewer_6rYn", "summary": "This paper proposes a post-hoc modification of early-exit neural networks. Specifically, the authors focus on the conditional monotonicity out of four properties presented in a prior work. A training-based method is also proposed to improve the model confidence.", "questions": "Please address concerns in weaknesses.\n\n--- post rebuttal\n\nI appreciate the authors' active responses during the author-reviewer discussion period. Most of my concerns have been solved, however, the main concern on the necessity of (conditional) monotonicity for EENNs is still not yet solved. Hence, I increase my rating, but not by much.\n\nIn my opinion, when proposing a new metric, the metric itself should either 1) be meaningful by itself or 2) have a strong positive correlation with the main goal. The monotonicity is not meaningful by itself (a model producing a constant output has the perfect monotonicity, which is not useful in practice) and the correlation with the overall performance (accuracy) is not so significant. To provide successful cases as examples, ECE in confidence calibration is crucial when considering the reliability of model outputs, and forgetting in continual learning has a positive correlation with the average accuracy.\n\nRegarding the scalability, the monotonicity measure seems scalable, but ECE is not for the proposed method. To me, confidence calibration is one of the most important topic in deep learning for a successful deployment to the real world applications, so non-scalable ECE is my major concern. In short, increasing the monotonicity leads to slightly improve the overall accuracy, while significantly deteriorating confidence calibration in the large-scale experiment on ImageNet.\n\nHowever, given that conditional monotonicity is important (and given that ECE is somewhat problematic), I agree that the post-hoc method proposed by the authors is simple yet effective in terms of the proposed monotonicity metric.", "limitations": "Nothing special.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The proposed method based on product-of-experts improves conditional monotonicity and its effectiveness is also supported by theoretical results.", "weaknesses": "- Some writing is somewhat verbose/redundant. For example, while properties of anytime models take a considerable amount of space, they are not that meaningful at last.\n\n- Plots on \"% of Test Samples vs. Max y* Prob. Decrease\" should be described in a better way, in that what it means and why do we care about it.\n\n- As addressed in Fig. 5, the proposed method results in hurting model confidence. It is good to see that fine-tuning with the proposed learning objective can improve this, but it makes the point of this work distracted; recall that this paper means to propose a post-hoc method.\n\n- How PA Finetune is done is not explained enough.\n\n- I am not sure if we really need to care about monotonicity. Enforcing to have monotonicity might be harmful, as shown in some curves in Fig. 2. Instead, assuming that the model is calibrated well, we could rely on the confidence of intermediate result and exit early regardless of the time budget for the best performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and help in improving our paper. \n\n> Some writing is somewhat verbose/redundant. For example, while properties of anytime models take a considerable amount of space, they are not that meaningful at last.\n\nWhile we focus exclusively on the monotonicity property, we have included a discussion on other relevant anytime desiderata (i.e., consistency and diminishing returns) to outline promising directions for future research. One of our goals in this work was to highlight that the field has largely neglected these desiderata. If you disagree with this inclusion, we are prepared to relocate the information to the Appendix. \n\nPlease let us know if you identified any other instances of redundant writing. We would be happy to address these issues.  \n\n> Plots on \"% of Test Samples vs. Max y* Prob. Decrease\" should be described in a better way, in that what it means and why do we care about it.\n\nConcerning the question, \"why do we care about it,\" this plot is designed to capture the percentage of test datapoints that display non-monotone trajectories in performance quality. A non-monotone performance trajectory signifies that the model's performance deteriorates with more evaluated exits, a behavior that stands in contradiction to the monotonicity desideratum outlined in Section 2 (see Properties of Anytime Models). Thus, this plot enables us to compare different models with respect to their monotonicity. Specifically, models with lower monotonicity curves (i.e., closer to y=0) are more effective at utilizing additional computational budget to refine their predictions.\n\nAlso, we would politely point out two paragraphs on lines 150-166 and the caption of Figure 1, where we tried to explain our conditional monotonicity plots in detail. Should you have concrete suggestions on enhancing the description of this plot further, we will gladly integrate those into the camera-ready version.\n\n> As addressed in Fig. 5, the proposed method results in hurting model confidence. It is good to see that fine-tuning with the proposed learning objective can improve this, but it makes the point of this work distracted; recall that this paper means to propose a post-hoc method.\n\nPlease refer to the *Calibration Gap* section in the global rebuttal above. We must also respectfully disagree with the statement that the fine-tuning \"distracts from the point of our work.\" We view the post-hoc nature of PA as a highly desirable property, allowing our method to be easily compatible with most existing early-exit NNs. Thus, we have emphasized the post-hoc version of PA in the main paper. However, recognizing that preserving calibration can be important in some applications, we have also proposed a fine-tuning version that helps close the post-hoc approach's calibration gap.\n\n> How PA Finetune is done is not explained enough.\n\nDue to space constraints, this didn't make it into the main text. However, we intend to incorporate it using the extra page allocated for the camera-ready. Moreover, we would like to draw your attention to Appendix B.3.2, where the PA finetuning is explained in detail. If you have specific suggestions for enhancing our description of the fine-tuning approach, we would be more than happy to incorporate them.\n\n> I am not sure if we really need to care about monotonicity\n\nWe must respectfully disagree on this point. Monotonicity, as a key property of anytime models, was introduced by Zilberstein in 1996 [1]. This seminal work, which has garnered over 1000 citations since its publication, has motivated most of the modern anytime models [2, 3]. **All other reviewers recognized the value of monotonicity.**\n\n> Enforcing to have monotonicity might be harmful, as shown in some curves in Fig. 2\n\nWhile our PA method may slightly decrease marginal accuracy in some instances (CIFAR-10 DViT, ImageNet DViT, ImageNet IMTA), we emphasize that the performance drop is rather marginal (amounting to less than 1%), and that this is the exception not the rule. Considering that a lack of monotonicity can be detrimental in the anytime setting (since more computation is not guaranteed to improve performance), such minor decline in marginal performance (i.e., < 1%) is in our opinion an acceptable trade-off for a significantly more monotone model.\n\n> Instead, assuming that the model is calibrated well, we could rely on the confidence of intermediate result and exit early regardless of the time budget for the best performance.\n\nPlease refer to the *Monotonicity via Calibration* section in the global rebuttal above. Moreover, your comment regarding the strategy of relying \"on the confidence of intermediate result and exiting early regardless of the time budget for optimal performance\" may be related to our Caching Anytime (CA) baseline (c.f. Section 4.1). In CA, the most confident prediction up to that point is cached and returned when prompted by the environment (instead of the latest prediction). While this approach is indeed a viable alternative to our PA method for enhancing monotonicity, our experimental results show that it falls short of PA in terms of both marginal accuracy (Figure 2) and conditional monotonicity (Figure 3) in most cases.\n\n> **Rating:** 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility \n\nBased on your score of 3, it appears that you perceive a technical flaw, weak evaluation, or inadequate reproducibility in our work. **We would sincerely appreciate further elaboration on these concerns, as we are confident that any such concerns can be addressed in this rebuttal period**.\n\n[1] Zilberstein, S., 1996. Using anytime algorithms in intelligent systems. *AI magazine*\n\n[2] Grubb, A., et al., 2012. Speedboost: Anytime prediction with uniform near-optimality. *AISTATS*\n\n[3] Huang, G., et al., 2017. Multi-scale dense networks for resource efficient image classification. *ICLR*"}, {"review_id": "LzMvNmY4ne", "reviewer": "Reviewer_G2Sm", "summary": "The paper first reviews the definition & key properties of anytime models (Zilberstein, 1996) and argues to focus on equipping the EENNs with conditional monotonicity (in addition to their built-in interruptibility, Sec 2). The paper then verifies that existing EENNs lack this critical property (Fig 1), proposes the PoE-based post-hoc modification with ReLU relaxation to encourage conditional monotonicity (Sec 4.2), and validates its accuracy (Fig 2), monotonicity (Fig 3) and uncertainty (Fig 4) on CIFAR-10/100 and ImageNet with MSDNet, IMTA and DViT. The paper also presents results on ablations (Sec B.2), calibration gap (adaptive thresholding & fine-tuning, Sec B.3), NLP (Sec B.4), ensembling, regression (Sec B.6) and different degrees of ReLU relaxation (Sec B.8).", "questions": "- Are $w_i$ and $b_i$ in Eq 4 learnable during fine-tuning? Why or why not?", "limitations": "The authors have reasonably addressed the paper’s limitations in Sec 6.3.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "+ [Originality] The paper novelly modifies the PoE formulation to achieve conditional monotonicity, making it sufficiently and advantageously different from existing works e.g. (Wolczyk et al., 2021).\n+ [Clarity] The paper is well written and easy to follow. All figures are well made and the appendix is very informative.\n+ [Quality] The paper is of good quality, with the proposed method relatively well motivated and designed, and the empirical evaluation (including results in the appendix) relatively comprehensive, although further improvements can be made (see Weaknesses).\n+ [Significance] Given the importance of the topic, even though the results are not necessarily perfect (but decent enough), I think this work is reasonably promising and could aid/inspire future research.", "weaknesses": "- [Evaluation] \n1) Given the criticality of the relaxation/approximation of the Heaviside function, it’s highly desirable to see more thorough analyses of and comparisons between different approximations, e.g. sigmoid (seemingly much more logical than ReLU), clipped ReLU, learnable Padé approximation [1], etc., in addition to Sec B.8.\n2) The exponent $i/M$ of the proposed PA method (Eq 4) is clearly a powerful inductive bias ensuring the network starts with low confidence, which should deserve more analyses such as: (a) How do the baselines perform when equipped with this simple feature or corresponding adjustments on the softmax temperature? (b) How does $i/M$ compare to other progressions or constant exponents? (c) Does $i/M$ adversely limit the confidence on simpler test samples such that e.g. early exits become ineffective?\n\n[1] Padé Activation Units: End-to-end Learning of Flexible Activation Functions in Deep Networks, ICLR, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your feedback and help in improving our work. \n\n> Given the criticality of the relaxation/approximation of the Heaviside function, it’s highly desirable to see more thorough analyses of and comparisons between different approximations, e.g. sigmoid …\n\nWe fully agree with your observation on the importance of the activation function. We would politely draw your attention to Appendix B.2 where we compare our choice of ReLU against Heaviside and exponential (which corresponds to softmax), as well as to Appendix B.8 where we report the results for clipped ReLU (even though we do not call it such in the current version, we will update this in the next version of our manuscript).\n\nYour suggestion regarding the sigmoid function is appreciated. Initially, we also considered it a viable option; however, upon further examination, we found it to have two drawbacks that make it less applicable in our context. Firstly, the sigmoid function lacks the \"nullifying\" effect of ReLU. Consequently, the support of classes diminishes more slowly, and we do not observe the same anytime uncertainty behaviour as we do with ReLU (c.f. Section 6.2). Secondly, logits with larger values all map to the same value, approximately 1, under the sigmoid function. This can negatively impact accuracy, as it does not preserve the ranking. Figure R.2 (see attached PDF) illustrates the results using the sigmoid activation function for the CIFAR-100 dataset with MSDNet as a backbone: **our choice of ReLU clearly outperforms sigmoid activation**. We will prepare an Appendix section in the camera-ready version and include these results there. Thank you for your suggestion.\n\nWe want to underscore at this point that our use of activation functions deviates from their traditional usage within the deep learning literature. In the context of our work, when we refer to activation functions, we are discussing the function that maps logits to probabilities in the final layer of the network. Conventionally, however, an activation function refers to the non-linearity that dictates which neurons are propagated between layers. This distinction may not have been sufficiently clear in the current version of our manuscript. We appreciate your observation and will correct this in the camera-ready version.\n\nRegarding PAU activation [1]: thanks for pointing out this work; we were unaware of it before. However, based on our understanding, this activation has trainable parameters that are usually fitted with the rest of the NNs’ parameters. As such, it is not entirely compatible with our post-hoc approach. Related to the previous paragraph, it also seems PAU is used more as a non-linearity between layers rather than a function that maps logits to probabilities in the final layer. That being said, it's plausible that PAU might be a suitable choice for the activation function in our fine-tuning approach (see Appendix B.3.2). We plan to investigate this possibility in our future work.\n\n> 2a) How do the baselines perform when equipped with this simple feature or corresponding adjustments on the softmax temperature?\n\nWe tried finding the optimal temperature for the baseline model (MSDNet), see *Monotonicity via Calibration* section in the global rebuttal above. In short, temperature scaling helps with the calibration of the baseline model. However, it still significantly underperforms our PA when it comes to achieving monotonicity. \n\n> 2b) How does $i/M$  compare to other progressions or constant exponents? \n\n> Are $w_i$ and $b_i$ in Eq 4 learnable during fine-tuning? Why or why not?\n\nWe experimented with various coefficient schemes, such as:\n\n- $w_i = 1$\n- $w_i =$ np.linspace(1, L/2)[i]\n- learn $w_i$ during fine-tuning, similar to ZTW paper [2]\n\n**However, we found that none of these alternative weights consistently outperformed our choice of $w_i=i/M$** across different datasets and backbone models, both in terms of marginal accuracy and conditional monotonicity. In the camera-ready version of our paper, we will include a separate section in the Appendix detailing this ablation study on the selection of $w_i$.\n\n> 2c) Does $i/M$  adversely limit the confidence on simpler test samples such that e.g. early exits become ineffective?\n\nIn the anytime setting upon which we're focusing, our method (utilizing $i/M$ coefficients) maintains the marginal accuracy (see Figure 2). As such, we conclude that our method does not render the initial exits ineffective. If your comment is directed towards the efficient/input-dependent inference setting, kindly refer to the *Anytime Prediction vs. Input-dependent/Efficient Inference Setting* section in the global rebuttal above.\n\n[1] Molina, A., et al., 2020. Páde Activation Units: End-to-end Learning of Flexible Activation Functions in Deep Networks. *ICLR*\n\n[2] Wołczyk, M., et al., 2021. Zero time waste: Recycling predictions in early exit neural networks. *NeurIPS*"}, {"review_id": "U5lcy8oPjR", "reviewer": "Reviewer_kJKM", "summary": "The authors propose a new approach, called Product Anytime (PA), for monotonic confidence estimation in early-exit neural networks. Inspired by the Product-of-Experts (PoE) approach, PA takes the normalized confidence with respect to the product of ReLU thresholded prediction logits. The authors show through experiments that PA achieves similar accuracy curves as the original softmax logits, but improves the monotonicity of early-exited prediction confidences.", "questions": "What is the unique advantage of the proposed approach compared to conventional uncertainty estimation algorithms applied in early-exit neural networks?", "limitations": "Yes, the authors have a separate section to discuss the limitations of the proposed technical solution.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The authors tackle a practical and important problem that should be solved in early-exit neural networks.\n2. The intuition of monotonicity from the Product-of-Experts (PoE) makes sense to me.\n3. The provided evaluations are comprehensive and support the claims made in the paper.", "weaknesses": "1. Although I agree with the authors monotonicity is an important property in early-exit NNs. I am not completely convinced whether it is meaningful to design a specialized algorithm to achieve it. My point is, can we use the confidence/uncertainty calibration algorithms [1, 2] in the literature, that seem to produce relatively accurate confidence estimation to replace the proposed algorithm? On one hand, the uncertainty calibration algorithm better reflects the accuracy of the model prediction. At the same time both approaches (uncertainty estimation and the proposed algorithm) can not provide theoretical guarantee as PoE does. I think uncertainty quantification should provide better monotonicity than softmax confidence. On the other hand, uncertainty calibration gives better intuition on which sample should be early exited, since it does not have the \"calibration gap\" issue observed in the proposed PA method.\n2. I am unsure how the proposed algorithm should be used in the practical runtime deployment scenario.\n3. The proposed approach seems to have multiple obvious limitations, such as the zero distribution due to non-overlapping labels among stages, the poor confidence at initial stages, and suboptimal performance for applications with the limited number of classes.\n\n\n[1] Gal, Yarin, and Zoubin Ghahramani. \"Dropout as a Bayesian approximation: Representing model uncertainty in deep learning.\" international conference on machine learning. PMLR, 2016.\n\n[2] Lakshminarayanan, Balaji, Alexander Pritzel, and Charles Blundell. \"Simple and scalable predictive uncertainty estimation using deep ensembles.\" Advances in neural information processing systems 30 (2017).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your time in reviewing our work. We address your concerns below.\n\n> The authors propose [PA] for monotonic confidence estimation\n\nWe would just point out that our model primarily targets monotonicity in the ground-truth class probability, denoted as $p_m(y^* | \\boldsymbol{x})$, and not in prediction confidence, represented as $\\max_y p_m(y | \\boldsymbol{x})$. Nevertheless, we concur that any form of non-monotonicity is troubling. Encouragingly, our PA helps with monotonicity not only when considering performance quality (e.g., ground-truth probability), but also for monotonicity in the uncertainty (e.g., conformal set size, see also Appendix B.7 for a more detailed analysis on this).\n\n> Although I agree with the authors monotonicity is an important property in early-exit NNs. I am not completely convinced whether it is meaningful to design a specialized algorithm to achieve it.\n\n> I am unsure how the proposed algorithm should be used in the practical runtime deployment scenario.\n\nRespectfully, we would disagree that our solution is particularly specialized. The method we propose is entirely post-hoc, meaning it can be readily applied to any pre-trained early-exit neural network. The implementation consists of four lines of Python code:\n\n```python\n# logits: torch tensor with shape (t, C) where t represents index of current exit and C number of classes\n# weight: PoE weights (torch tensor with shape (t,) )\n\nprobs = torch.clamp(logits, min=0) # ReLU activation\nprobs = probs.pow(weights[:, None])  # apply PoE weights\nprobs = torch.prod(probs, dim=0)  # product ensemble\nprobs /= probs.sum()  # normalize\n```\n\n**Thus, any model originally designed for an efficient inference scenario (e.g., MSDNet) can be repurposed for anytime prediction by simply \"turning on\" our post-hoc solution.**\n\nWe hope that with our answer here, we have also addressed your question on the “practical runtime deployment scenario”. If not, please let us know, and we will be happy to provide additional details and clarifications.\n\n> On the other hand, uncertainty calibration gives better intuition on which sample should be early exited \n\nWe would point out that in the anytime setting the “intuition on which sample should be early exited ” is of lesser importance since the environment dictates the exit point, not the user. Please refer to *Anytime Prediction vs. Input-Dependent/Efficient Inference setting* section in the global rebuttal for more.\n\n> My point is, can we use the confidence/uncertainty calibration algorithms [1, 2] in the literature, that seem to produce relatively accurate confidence estimation to replace the proposed algorithm?\n\n> What is the unique advantage of the proposed approach compared to conventional uncertainty estimation algorithms applied in early-exit neural networks?\n\nPlease refer to *Monotonicity via Calibration* section in the global rebuttal above, where we have performed a new experiment based on your questions. If you feel that our answers there inadequately address your concerns, please let us know, and we will be happy to elaborate further.\n\n> The proposed approach seems to have multiple obvious limitations, such as the zero distribution due to non-overlapping labels among stages, the poor confidence at initial stages, and suboptimal performance for applications with the limited number of classes.\n\nPlease refer to the *Calibration Gap section* in the global rebuttal for a longer discussion on “the poor confidence at initial stages”. \n\nRegarding the issue with “zero distribution due to non-overlapping labels among stages” - while we agree that this could be concern, we have not observed many issues with this in our experiments. **The collapse to a zero-distribution was found to occur extremely rarely on the considered datasets**. Specifically, when using MSDNet, we observe this scenario for 3 (out of 10000) test cases for CIFAR-10, and never for CIFAR-100 and ImageNet. Also, in such cases, we provide a concrete suggestion of falling back to softmax probabilities, which we found to work well in practice.\n\nTo counter the issue of suboptimal performance when dealing with a small number of classes (i.e., < 5), we recommend using the Caching Anytime (CA) approach instead of the PA method. Although CA was originally proposed in Zilberstein’s work [1], it has often been overlooked in contemporary anytime literature, where the standard practice has been to return the most recent prediction. We hope our work will reignite interest in the CA approach within the anytime literature. Moreover, poor performance for a small number of classes is common among approaches relying on Product-of-Experts ensemble. In [2] , the authors report the same issue; see their Appendix C.4.\n\n\n\nIf you think we have addressed you concerns sufficiently, we would appreciate you considering raising your score. \n\n[1] Zilberstein, S., 1996. Using anytime algorithms in intelligent systems. *AI magazine*\n\n[2] Wołczyk, M., et al., 2021. Zero time waste: Recycling predictions in early exit neural networks. *NeurIPS*"}, {"review_id": "73nTvDZ0z4", "reviewer": "Reviewer_ne1V", "summary": "This submission focuses on multi-exit early networks, from the perspective of anytime inference that can accommodate varying computational budgets. Such models produce a progressive refinement of the final prediction, offering the opportunity to \"exit-early\", providing a meaningful prediction. The main motivation of this work is to enforce conditional monotonicity on the predictions of successive early-exits, such as the output quality consistently improves as the inference process progresses. The proposed solution adopts the Product-of-Experts formulation and can be applied post-training, to achieve monotonicity on prediction quality as well as prediction uncertainty.", "questions": "In accordance to the discussion in \"Weaknesses\" please clarify:\n1. How does the proposed methodology compare to vanilla early-exit ensembles in terms of both accuracy and uncertainty monotonicity (should be added in Fig.2 analysis).\n2. Is the proposed methodology still relevant if applied on early-exit models trained via the frozen-backbone methodology (i.e. is the behaviour of Fig1-middle still evident in this case; and resolved by the proposed approach)?\n3. Is there a scalability issue when the proposed method is applied on ImageNet? What aspect (sample size, number of classes etc) seem to mostly cause this effect ?\n4. Is the predictive accuracy and uncertainty of early-classifier reduced when applying the proposed methodology at training time ?\n5. Is it indeed beneficial to decrease prediction confidence on shallow classifiers, even when their predictions are correct (e.g. on easier samples) ?\n6. In the case of the IMTA early-exit model, where knowledge distillation is applied, it is expected that the prediction uncertainty of the resulting model will be affected. How does this affect the analysis of Sec.6.2; do the results remain consistent for IMTA models ?", "limitations": "Some limitations are clearly discussed in a dedicated subsection of the paper. Following the above discussion, it may be beneficial to broaden this discussion accordingly.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "-The submission identifies and studies an interesting challenge with early-exit models, in the context of anytime inference, which is often overlooked by relevant literature.\n\n-The papers analysis is wide and insightful, providing numerous empirical results that can motivate further research in the topic. \n\n-The proposed methodology is clearly explained, and experiments are conducted on a range of traditional benchmarks, consistently to the practise of relevant literature.", "weaknesses": "-Certain design choices are not adequately justified and further comparisons/ablations should be included on the main paper. More specifically, it will be beneficial to examine: i) how the proposed methodology would behave in frozen backbone early-exit models and ii) in comparison to simple ensemble between early-exit models that comprises a intuitive baseline.\n\n-Additionally, it is claimed that the proposed approach can also be applied at training time, but this scenario is not adequately evaluated. Would the proposed methodology incur additional error or under-confidence on the  shallower exits (instead of improving the deeper ones) in a quest to achieve the desired monotonicity? And if so how can this be mitigated?\n\n-Figure 2-right may suggest a scalability issue for the proposed approach as the baseline dominates the depth-accuracy trade-off in contrast to other datasets. This limitation should be further investigated.\n\n-The motivation of progressively increasing predictive confidence, may contradict the general benefits of uncertainty estimation in early-exit models (e.g. for input dependent inference). One could argue that uncertainty should ideally be calibrated with the probability of the ground-truth class; rather than penalised on early-classifier even if the provided prediction is correct. \n\n-Finally, the discussion of the results (e.g. on Fig. 2) could benefit from providing some quantitative conclusions on text (e.g. average/median improvement etc.).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your valuable review and many interesting questions.\n\n> how the proposed methodology would behave in frozen backbone early-exit models\n\n> Is the proposed methodology still relevant if applied on early-exit models trained via the frozen-backbone methodology\n\n**Yes, our proposed PA is still relevant when applied to EENNs with frozen-backbone**. For a concrete example, see Appendix B.5, specifically Figure 16, where we present the results using ZTW [1]. ZTW begins with a pretrained backbone, e.g., ResNet, and adds early-exit heads on top of it. During training of the exit heads, the backbone is frozen (see Algorithm 1 in their paper). Figure 16 shows that ZTW is highly non-monotone, corroborating our findings in Section 3. Furthermore, applying our PA to ZTW substantially outperforms the original ZTW in terms of Hindsight Improvability, a metric proposed by the ZTW authors [1] to capture how effectively a model reuses past predictions.\n\nIf by \"frozen backbone early-exit models\" you're referring to something else, please clarify, and we'll discuss further. If there's a specific EENN you're interested in, let us know and we'll do our best to conduct the relevant experiments during the discussion period.\n\n> in comparison to simple ensemble between early-exit models that comprises a intuitive baseline.\n\n> How does the proposed methodology compare to vanilla early-exit ensembles\n\nWe did explore this baseline, though we didn't label it as “early-exit ensembles”. We'll clarify this in the camera-ready. The results are in Appendix B.2, see the MoE-exponential (corresponding to an ensemble of all softmax predictives up-to-and-including the current exit) in Figure 7. **In short, vanilla early-exit ensembles are not sufficient to achieve monotonicity**. \n\nFor now, the results are only available for the CIFAR-100 with MSDNet. If you think it would be beneficial for us to extend these experiments to other datasets and models, we would be happy to do so and include the results in Appendix B.2. We did not to include the early-exit ensembles baseline in Figures 2 & 3, since these plots are already somewhat busy. If you disagree with this choice, we are willing to change it.\n\n> certain design choices are not adequately justified and further comparisons/ablations should be included\n\nPlease let us know if there are any specific additional ablations we should perform. As discussed with reviewer G2Sm, we’ll include a more comprehensive ablation on the activation function as well as on the ensemble weighting scheme in the camera-ready.\n\n> Is the predictive accuracy and uncertainty of early-classifier reduced when applying the proposed method at training time?\n\nDue to space constraints, this didn't make it into the main text. However, we intend to incorporate it using the extra page allocated for the camera-ready. Please see Appendix B.3.2 , where we elaborate in detail on the application of our PA model during training/finetuning. As shown in Figure 12, fine-tuning with PA does slightly compromise both accuracy and monotonicity compared to the post-hoc PA. Nonetheless, it still markedly surpasses the baseline model in terms of monotonicity and largely closes the calibration gap of the post-hoc PA. We perceive this as a promising avenue for future exploration.\n\n> Is there a scalability issue when […] applied on ImageNet?\n\nWe are not entirely sure what you mean by scalability issue here, let us know if we’ve misinterpreted. \n\nIf by scalability issue you mean that our method leads to a decrease marginal accuracy for DViT and IMTA models on ImageNet, we would point out that the performance drop is rather marginal (amounting to less than 1%). Considering that a lack of monotonicity can be detrimental in the anytime setting, we deem such a decline in marginal performance as an acceptable trade-off for a significantly more monotone model.\n\n> Is it indeed beneficial to decrease prediction confidence on shallow classifiers, even when their predictions are correct (e.g. on easier samples) ?\n\n> progressively increasing predictive confidence, may contradict the general benefits of uncertainty estimation in EENNs (e.g. for input dependent inference). \n\nWe agree that decreasing confidence also on easier samples could be problematic in input-dependent inference. However, this application is out of scope of our current paper. Please refer to *Anytime Prediction vs. Input-Dependent/Efficient Inference setting* in the global rebuttal for further discussion.\n\nWe also encourage you to have a look at Appendix B.3.1, where we introduce PA with adaptive thresholding. As shown in Figure 11, this adaptation does not reduce confidence for all data points early on, but rather for the more challenging ones. However, monotonicity is compromised when compared to vanilla PA; see Figure 10. Moreover, it isn’t post-hoc due to the fitting of a thresholding model. For these reasons, the main text prioritizes the original PA. Nonetheless, we believe that adaptive thresholding presents a promising avenue for future work.\n\n> […] uncertainty should ideally be calibrated with the probability of the ground-truth class; rather than penalised […] even if [...] prediction is correct.\n\nWe agree with this concern and have discussed it in Section 6.3 of the paper. Please also refer to *Calibration Gap* in the global rebuttal.\n\n>  How does this affect the analysis of Sec.6.2; […] consistent for IMTA models ?\n\nWe followed your suggestion and have replicated experiment from Section 6.2 using IMTA model. As depicted in Figure R.3 (see attached pdf), the uncertainty results are consistent for this baseline model. \n\n> the discussion  […] could benefit from some quantitative conclusions [...]\n\nWill do!\n\nIf you think we have sufficiently answered your questions, we would appreciate if you would consider increasing your score.\n\n[1] Wołczyk, M., et al., 2021. Zero time waste: Recycling predictions in early exit neural networks. *NeurIPS*"}, {"review_id": "CIoBbRda0v", "reviewer": "Reviewer_NWJy", "summary": "This paper studies an interesting problem of early-exit classification networks when applied to anytime prediction tasks. Specifically, the authors empirically demonstrate that in an early-exit network, the prediction confidence scores of its different exits for the same sample are not monotonically increased. Then the authors propose a method to recalculate the prediction confidence of different exits. This method is shown effective in improving the conditional monotonicity of different exits' predictions.", "questions": "See weakness.", "limitations": "As I stated in the weakness part, the benefits of the obtained better monotonicity are not discussed in depth.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The studied problem is interesting and important;\n2. The proposed method is theoretically guaranteed;\n3. The experiment is comprehensive, covering different architectures and datasets.", "weaknesses": "I have some concerns as follows:\n\n1. The results on CIFAR datasets (Fig. 2 left and middle) are confusing: the IMTA baselines achieved lower/similar accuracy than the MSDNet baseline in Fig. 2. However, IMTA is apparently a stronger method than the original baseline. This makes the results much less convincing to me. Moreover, I did not find the ImageNet results using the proposed PA for MSDNet and IMTA (blue and green dashed lines) in Fig 3 (right). Only DVT results (orange dashed line) are presented. \n\n2. The experiment results in Fig. 4 indeed show that the ground-truth probability trajectories monotonically increase by using the proposed PA. However, **how can such monotonicity improve the anytime prediction task**, is not discussed. Is there any metric that can measure the anytime performance of a model? Now the authors only show us that the overall accuracy can be preserved (or improved a little).\n\n3. It is recommended to conduct experiments on more recent multi-exit models, such as L2W-MSDNet [1].\n\n4. I'm curious whether better monotonicity is beneficial in the budgeted dynamic inference setting (the smooth accuracy-FLOPs curves reported in MSDNet and IMTA papers).\n\n[1] Han, Yizeng, et al. \"Learning to Weight Samples for Dynamic Early-Exiting Networks.\" ECCV 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time and efforts in reviewing our work.\n\n> the authors empirically demonstrate that in an early-exit network, prediction confidence scores [...] for the same sample are not monotonically increased.\n\nWe would point out that our findings indicate the ground-truth class probability, denoted as $p_m(y^* | \\boldsymbol{x})$, exhibits non-monotonic behavior. This means that there are instances where the ground-truth class is more probable in earlier exits than in subsequent ones. We believe that this is even more concerning than non-monotonicity observed in prediction confidence, represented as $\\max_y p_m(y | \\boldsymbol{x})$. Nevertheless, we concur that any form of non-monotonicity is troubling. \n\nFor example, in Appendix B.7 we show that MSDNet is non-monotone also w.r.t. its estimates of uncertainty. Specifically, there are points where the model is highly confident in the initial exits and then becomes less confident later on. As a measure of uncertainty, we have employed entropy and conformal set sizes, but we expect the results to also hold for prediction confidence.\n\nEncouragingly, our PA helps with monotonicity not only when considering performance quality (e.g., ground-truth probability), but also for monotonicity in the uncertainty (e.g., conformal set size).\n\n> IMTA is apparently a stronger method than the original baseline. This makes the results much less convincing to me.\n\n>  It is recommended to conduct experiments [using] L2W-MSDNet\n\nWe share your surprise that IMTA does not clearly outperform MSDNet in our experiments, which seems to contradict the claims in their respective papers. However, it's important to emphasize that we used the code and training scripts exactly as provided by the authors of IMTA (note that the pre-trained models were not published for this model): https://github.com/kalviny/IMTA. Our own attempts to improve the performance of the baseline IMTA model (to match the performance reported in their paper) were unsuccessful.\n\nWe followed your advice and also ran the experiments using L2W model. As shown in Figure R.4 (see attached PDF), our findings remain consistent — **the PA method maintains marginal accuracy while substantially improving conditional monotonicity for L2W**. We will add this baseline to Figures 2 & 3 in the camera-ready version. We believe the inclusion of L2W will make our empirical findings stronger so we would like to thank you for this suggestion. \n\nFor now we have results only for ImageNet model, because, regrettably, the authors of L2W did not release neither training code nor pre-trained models for CIFAR-10/100:  https://github.com/LeapLabTHU/L2W-DEN. We will reach out to them regarding this so that we can, hopefully, include L2W results for all considered datasets in our camera-ready.\n\n> I did not find the ImageNet [PA results] for MSDNet and IMTA [...] in Fig 3 (right).\n\nThe monotonicity curves of the PA method for the MSDNet and IMTA models on ImageNet overlap with the one for the DViT model at y=0. We recognize that the current presentation might lead to confusion, and we appreciate you highlighting this issue. We plan to add a statement to the caption of Figure 3 to clarify this.\n\n>  how can such monotonicity improve the anytime prediction task, is not discussed. \n\n> the benefits of [...] better monotonicity are not discussed in depth.\n\nThe primary argument of our paper is that with our PA method, we can maintain the marginal accuracy while simultaneously ensuring conditional monotonicity. This is crucial in a truly anytime setting (where the stopping time is random and determined by the environment) as it ensures that the performance will not deteriorate with more computational resources. \n\nAs a concrete example of how monotonicity can help with anytime predictions, we can consider again the scenario of Android phones introduced in Section 1 (c.f. lines 21-24 and 29-32). **Deploying the original MSDNet might result in certain data points receiving inferior predictions on a higher-spec device compared to a device with limited computational capabilities**. However, if we apply our PA to an MSDNet, such inconsistencies become far less likely due to the model's monotonic behavior.\n\n>  Is there any metric that can measure the anytime performance of a model?\n\nEstimating the performance of an anytime algorithm in a real-world setting is tricky as there are many potentially important facets of \"performance\" to consider. We believe that the combination of marginal accuracy (Figure 2) and conditional monotonicity (Figure 3) that we focus on in our paper represent some of these facets. Unfortunately, to the best of our knowledge, previous work has almost exclusively focused on marginal accuracy, so this is an underdeveloped area. Nonetheless, we have identified two metrics proposed in the previous work that could potentially be useful for studying anytime models. The first is the \"Overthinking\" metric introduced in [1], which looks at difference in performance between an oracle model that exits at the first exit with the correct answer and the performance of the full model (i.e., final exit). The second, termed \"Hindsight Improvability\" in [2], gauges the efficiency of the early-exit network in leveraging previous predictions. We show that our PA leads to improvements over baseline MSDNet in terms of both of those metrics, see Appendix B.5 for more details.\n\n> I'm curious whether better monotonicity is beneficial in the budgeted dynamic inference setting\n\nPlease refer to the *Anytime Prediction vs. Input-Dependent/Efficient Inference setting* in the global rebuttal.\n\nIf you believe we have adequately addressed your concerns, we would be grateful if you would consider raising your score.\n\n[1] Kaya, Y., et al., 2019, May. Shallow-deep networks: Understanding and mitigating network overthinking. *ICML*\n\n[2] Wołczyk, M., et al., 2021. Zero time waste: Recycling predictions in early exit neural networks. *NeurIPS*"}]

Author rebuttal:
We thank all reviewers for their valuable time and feedback; it’s much appreciated.

We are encouraged that the reviewers found “the paper well written and easy to follow” (G2Sm), thought that “the studied problem is interesting and important” (NWJy), “often overlooked by the relevant literature” (ne1V), and that we  “tackle a practical and important problem that should be solved” (kJKM). Moreover, we are pleased to hear that our proposed method is “well motivated and designed” (G2Sm) and that “its effectiveness is also supported by theoretical results” (6rYn). Importantly, reviewers found the experiments “comprehensive” (NWJy & G2Sm & kJKM), “supporting the claims made in the paper” (kJKM), and “wide and insightful” (ne1V). Finally, we are excited that the reviewers recognized that our work “can motivate further research in the topic” (ne1v) and “could aid/inspire future research” (G2Sm). 

We next address some of the main concerns raised in the reviews.

**Anytime Prediction vs. Input-Dependent/Efficient Inference setting** (kJKM, ne1V, NWJy) 

We make no claims in our paper regarding the use of our model in an input-dependent/efficient inference setting (a.k.a. budgeted batch classification [1]). **Our focus is solely on the anytime scenario**, where the computational budget is unknown or dynamic, and exiting is determined by the environment (cf. “Setting of Interest”, lines 72-81). Since our solution is very lightweight (4 lines of Python code) and can be applied post-hoc, it is easy to “turn on and off”. Hence, the same early-exit model, e.g., MSDNet, can easily be used for either scenario as required. 

One of our main goals is to highlight the distinction between the two settings and their different requirements.  We believe that this is missing in the current literature where the desiderata of anytime setting have been largely overlooked (as evidenced by the highly non-monotone behavior of SOTA ‘anytime’ models, cf. Figure 1)

Reviewer NWJy has suggested that it would be interesting to study the effect of monotonicity in the budgeted batch classification scenario too. This is a great idea, but it is out of the scope of the current paper.  We plan to investigate it in future work.

**Monotonicity via Calibration** (6rYN, kJKM, G2Sm, ne1V)

Some reviewers questioned whether monotonicity could be achieved by calibrating the underlying early-exit NN, rather than employing our proposed PA.  To answer this, we conducted a new experiment where we calibrated MSDNet and analyzed its effect on monotonicity. For the calibration, we utilized three standard techniques: temperature scaling [2], deep ensembles  [3], and last-layer Laplace [4]. 

In Figure R.1 (see attached pdf) we present results for MSDNet on CIFAR-100. While all three approaches lead to better ECE (right plot), our PA significantly outperforms them in conditional monotonicity (middle plot). Moreover, all three baselines are (arguably) more complex compared to our PA: temperature scaling requires validation data, deep ensemble has M-times more parameters (M = ensemble size), and Laplace is significantly slower compared to PA since we need test-time sampling to estimate the predictive posterior at each exit.

However, simply improving calibration might not be expected to improve monotonicity. Thus, in Figure R.1, we also provide results for combining the above uncertainty calibration techniques with our CA baseline, as suggested by reviewer 6rYn. We see that this combination does indeed provide further improvements w.r.t. monotonicity – the improved calibration allows for better caching of the correct prediction. **However, the monotonicity of these caching-and-calibrated methods still underperforms compared to PA, despite being more complicated**. 

We plan to include these results in our paper's camera-ready version, as it neatly demonstrates that monotonicity can not be achieved via calibration alone. This insight further underlines the value of our proposed approach. We thank the reviewers for this suggestion.

**Calibration Gap** (6rYN, kJKM, ne1V) 

Some reviewers raised concerns that our post-hoc method can hurt ECE in earlier exits (c.f. Figure 5). While we share this concern, we would like to emphasize that this potential drawback must be considered alongside the notable advantages of our method. These include the introduction of conditional monotonicity and enhanced uncertainty estimates (c.f. Figure 4, right). Additionally, note that poor ECE early on stems from under-confidence rather than over-confidence. We would argue such inductive bias is appropriate in EENNs, especially in safety-critical scenarios

**Moreover, in addition to pointing out this limitation ourselves, we propose two concrete ways to improve the calibration in earlier exits in the paper**, one based on the training/finetuning with the Product Anytime (PA) objective and one based on using ReLU with adaptive thresholding. We describe both in detail and present their impact on the monotonicity/calibration in Appendix B.3. Both yield very promising results when it comes to closing the calibration gap, albeit at some cost to monotonicity/accuracy. We will also include a description of both approaches in the main text using the additional page in the camera-ready.

Lastly, we believe that our paper is stronger due to our honest discussion of both the pros and cons of the method, which we hope will facilitate future work and easy adoption for practitioners. 

We further address all reviewers' remaining concerns and questions in individual responses.

[1] Huang, G., et al., 2017. Multi-scale dense networks for resource efficient image classification. *ICLR*

[2] Guo, C., et al., 2017, July. On calibration of modern neural networks. *ICML*

[3] Lakshminarayanan, B., et al., 2017. Simple and scalable predictive uncertainty estimation using deep ensembles. *NeurIPS*

[4] Daxberger, E., et al.., 2021. Laplace redux-effortless bayesian deep learning. *NeurIPS*

Meta-review: This paper studies conditional monotonicity for anytime prediction models, where the predicted solution should monotonically improve (i.e. the confidence in the correct answer) through the network. This potentially allows a setting where a "best effort" prediction is made if the prediction the compute is interrupted, or if the same model needs to be deployed in many devices with different capacities. The authors focus on the compute vision domain and MSDNet and first demonstrate that a constrained-free model doesn't satisfy their desired conditional monotonicity. They then propose a solution. First, they discuss a simple solution for guaranteeing monotonicity, but can hurt accuracy. Instead, they propose a relaxed version that still promotes monotonicity and empirically leads to comparable accuracy.

The rebuttal and discussion period were very active with many great interactions and suggestions that the authors stated they will include in the paper. Most reviewers were convinced that the contributions of this work and the extensive analysis and insights are meaningful. The main remaining concerns were around the importance and practicality of monotonicity (kJKM, 6rYn) and around the reduction in ECE (6rYn). While it would have definitely strengthen the paper if the authors could have used their method for obtaining practical gains in instance-wise confidence-based early exiting, studying monotonicity by itself can also be valuable. Also, the comprehensive analysis of the authors which includes also some negative results such as increased ECE should be encouraged. Furthermore, the improved results on other confidence-dependent metrics such as conformal set size are stronger since they rely on stronger finite-set guarantees and more stable than ECE.

The authors should incorporate all the new results and comments from the discussion period into the paper. The scope of the paper should also be more properly defined in order to avoid confusion and false expectations. I would suggest to limit the discussion on early exit models since many recent paper use this term for describing confidence-based exit functionalities. Instead, anytime prediction describes better the examined setting where the the halting criterion is based on the environment instead of the specific instance. This should also alleviate some of the concerns around the practicality of the monotonicity requirement which might or might not be helpful for early exiting, but is more clearly helpful for anytime predictors.
Decision: Accept (poster)