Efficient Edge Inference by Selective Query
Authors: Anil Kag
Igor Fedorov
Aditya Gangrade
Paul Whatmough
Venkatesh Saligrama
Venue: ICLR 2023 poster (2023)
Keywords: efficient edge inference
low-capacity model
large scale prediction
dynamic neural networks
adaptive neural networks

Abstract: Edge devices provide inference on predictive tasks to many end-users. However, deploying deep neural networks that achieve state-of-the-art accuracy on these devices is infeasible due to edge resource constraints. Nevertheless, cloud-only processing, the de-facto standard, is also problematic, since uploading large amounts of data imposes severe communication bottlenecks. We propose a novel end-to-end hybrid learning framework that allows the edge to selectively query only those hard examples that the cloud can classify correctly. Our framework optimizes over neural architectures and trains edge predictors and routing models so that the overall accuracy remains high while minimizing the overall latency. Training a hybrid learner is difficult since we lack annotations of hard edge-examples. We introduce a novel proxy supervision in this context and show that our method adapts seamlessly and near optimally across different latency regimes. On the ImageNet dataset, our proposed method deployed on a micro-controller unit exhibits $25\%$ reduction in latency compared to cloud-only processing while suffering no excess loss.

Published as a conference paper at ICLR 2023
EFFICIENT EDGE INFERENCE BY SELECTIVE QUERY
Anil Kag
Igor Fedorov Meta AI
Aditya Gangrade
Boston University anilkagebu.c edu
Carnegie Mellon University
iFedorovemeta.com
sgaagraa2aaddrw andrew cmu , edu
Paul Whatmough"
Venkatesh Saligrama
Qualcomm AI Research
Boston University
pwhatmou& qt i. qualcomm. comm. com
srv@bu. edu
ABSTRACT
Edge devices provide inference predictive tasks many end-users. However, deploying deep neural networks that achieve state-of-the-ar accuracy on these devices is infeasible due edge resource constraints. Nevertheless, cloud-only pro- cessing, the de-facto standard, is also problematic, since uploading large amounts of data imposes severe communication bottlenecks. We propose a novel end-to-end hybrid learning framework that allows the edge to selectively query only those hard examples that the cloud can classify correctly. Our framework optimizes over neural architectures and trains edge predictors and routing models so that the over- all accuracy remains high while minimizing the overall latency. Training a hybrid learner is difficult since we lack annotations of hard edge-examples We introduce a novel proxy supervision in this context and show that our method adapts seamlessly and near optimally across different latency regimes. On the ImageNet dataset, our proposed method deployed on a micro-controlle unit exhibits 25% reduction latency compared to cloud-only processing while suffering no excess loss.
INTRODUCTION
We are in the midst of a mobile and wearable technology revolution with users interacting with personal assistants through speech and image interfaces (Alexa, Apple Siri etc.). To ensure an accurate response, the current industrial practice has been to transmit user queries to the cloud-server, where it can be processed by powerful Deep Neural Networks (DNNs). This is beginning to change (see (Kang et al. 2017 Kumar et al. 2020)) with the advent of high-dimensional speech or image inputs. As this interface gains more traction among users, cloud-side processing encumbers higher latencies due to communication and server bottlenecks. Prior works propose a hybrid system whereby the edge and cloud-server share processing to optimize average latency without degrading accuracy.
Proposed Hybrid Learning Method. Our paper focuses on learning aspects of the hybrid system. We propose an end-to-end framework to systematically train hybrid models optimize average latency under an allowable accuracy-degradatiin constraint. When a user presents query, the hybrid learner (see Fig. D decides whether can respond to it on-device (eg. "Can you recognize me?") or that the query posed is difficult (eg. "Play song I would like from 50's"), and needs deeper cloud-pe pruud-pocessiig.. We emphasize that due to the unpredictable nature (difficulty and timing) of queries coupled with the fact that on-device storage/run-ting footprint is relatively small, hard queries inevitably encumber large latencies as they must be transmitted to the cloud.
Fundamental Learning Problem: What queries cover? While, systems level. communications and device hardware are improving, the overall goal of maximizing on-device processing across users (as way to reduce server/communication loads) in light of unpredictable queries unlikely change. It leads to a fundamental learning problem faced by the hybrid learner. Namely, how to train a base, a router, and the cloud model such that, on average, coverage on-device maximized without sacrificing accuracy. In this context, coverage refers to the fraction of queries inferred by the base model.
Work completed while PW was at Arm Research

---

Published as a conference paper at ICLR 2023
Figure 1: HYBRID MODEL. Cheap base (b) & routing models (r) run on micro-controller. Expensive global
Table 1: Device & Model Characteristics: Edge (STM32F746 MCU), Cloud (V100 GPU), It takes 2000ms to communicate an ImageNet image from the edge to the cloud (see Appendix 4A.2
model (g) runs on cloud. r uses r and features of to decide if g is evaluated or not.
Edge
Cloud
Device Device Characteristics
Model Performance
Radio Tx
Memory StorageAccuragy Size Latency
b
g
(Latency)
MCU 320KB
IMB
51.1%
0.6MB 200ms
GPU
16GB
ITB
79.9%
9.1MB 25ms
Local Prodiction
Cloud Prodiction
Novel Proxy Supervision. Training routing models is difficult because we do not a priori know what examples are hard to classify on edge. More importantly, we only benefit from transmitting those hard-to-learn examples that the cloud model correctly predicts. In this context, we encounter three situations, and depending on the operational regime of the hybrid system, different strategies may be required. To expose these issues, consider an instance-labe pair (I, v). and the three typical possibilities that arise are: (a) Edge and Cloud are both accurate, b(x) = g(z) y; (b) Edge and Cloud are both inaccurate, b(x) F y and g(z) & y; and (c) Edge is inaccurate but Cloud is accurate b(z) * g(x) = y. Our objective is to transmit only those examples satisfying the last condition. It improves coverage by ceasing data transfers when cloud predictions are bound to be incorrect. However, the limited capacity of the router (deployed on the MCU) limits how well one can discern which of these cases are true, and generalization to the test dataset is difficult. As such, the routing would benefit from supervision, and we introduce a novel proxy supervision (see Sec. 2.1) I to learn routing models while accounting for the base and global predictions.
Latency. Coverage has a one-to-one correspondence with average latency, and as such our method can be adopted to maximizes accuracy for any level of coverage (latency), and in doing characterize the entire frontier of coverage-accuracy trade-off.
Contributions. In summary, we list our contributions below.
Novel End-to-Enn Objective. We are the first to propose a novel global objective for hybrid learning that systematically learns all of the components, base, router, global model, and architectures under
overall target eтror or dynamic target latency constraints.
Proxy Supervision. We are the first to provably reduce router learning to binary classification and exploit it for end-to-end training based on novel proxy supervision of routing models. Our method adapts seamlessly and near optimally across different latency regimes (see knee Fig. 2)
Hardware Agnostic. Our method is hardware agnostic and generalizes to any edge device (ranging from micro-controllers to mobile phones), any server/cloud, and any communication scenarios. Our experiments include (a) MCU and GPU (see Sec. B.T. (b) Mobile Devices and GPUs (see Sec. B.I., (c) on the same device (see Sec. 3.2 Appendix|A.II A.IIIII.
SOTA Performance on Benchmark Datasets. We run extensive experiments on benchmark datasets to show that the hybrid design reduces inference latency as well as energy consumption per inference. Our code is available at hhttp:: / http:/gttuuub.ooo com an kagakk/HHbrriiio d_rddorrdddddd_dd_____e
Motivating Example: ImageNet Classification on an MCU. Let us examine large-scale classifica- tion task through the lens of tiny edge device. This scenario will highlight our proposed on-device coverage maximization problem. We emphasize that the methods proposed in this paper generalize any hardware and latencies (see Section 3). Table I displays accuracy and processing latencies on typical edge (MCU) model and cloud model (see Appendix $A.2).. The cloud has GPUs, and its processing speed is 10x relative to MCU processing. In addition, the cloud has a much larger working memory and model storage space compared to the MCU.
Impact of Cloud-Side Bottlenecks. If latency were negligible (either due to communication speed or server occupancy), NB-IoT communication (see Sec. A.2). data transfer to the cloud can take about 2s-about 100x the processing time on a GPU and thus, to reduce communication, one should maximize MCU utiliza- tion for classification. The argument from an energy utilization viewpoint is similar; costs 20x more for transmitting than processing. In general, communication latency is dynamically changing over time. For instance, it could be as large as 10x the typical rate. In this case, we would want the
would simply transfer every query to the cloud. In typical system with
2

---

Published as a conference paper at ICLR 2023
25
30
75
100
125
150
175
200
20
40
80
100
120
140
160
180
Global
Global
75
Insqence Rog Mccurocy(i
Imogence Topt Accurasyy
65-
65-
On-Device
On-Device
Un-Cloud
On-Coout
53
Spil-Camoutation
33-
Selh-Computation
Hybrid Uppar-Bound
Mybrid
Upper-Bound
250
500
750
1000
1250
1500
1750
2000
200
400
600
800
1000
1200
1400
1600
1800
Inference Latency (ms)
Inference Latency (ms)
(a)
(b)
Figure ImagetNet Classification: Accuracy vs Energy/l Latency plot: (a) Constant Communication Latency (2000ms), and (b) Dynamic Communication latency (200, ms.0 It clearly shows that the proposed hybrid model pareto dominates the baselines while getting significantly closer to the upper-bound in hybrid setup.
MCU unit to dynamically adapt its processing so that at fast rates, much of the processing happens on the cloud, and for slow rates, the MCU must still decide what examples process locally.
1.1 PRIOR WORKS WITH EMPIRICAL COMPARISONS ON MCU
We use Table [ as a running example to survey prior works, but our inferences here, seen in Sec. B hold generally. Our goal is to illustrate key differences through this practical scenario. We refer reader to Appendix |A.2 for more ex- perimental details. We consider two com- munication contexts: (a) Fixed but large latency (2000ms); (b) Dynamic Latency: random variable uniformly distributed in the interval [200, 2000]ms.
Table 2: Comparing features our proposal against baseline.
E.-to-E, stands for 'End-to- to-d-o--B Band-to-End', and Arch. for 'Architecture'.
Low Deploy. E.-to-E. Arch. High Latency on Edge Training Search Accuracy
Method
On-Device On-Cloud Split-Comp.
x
X
/
X
X
Dynamic.
x
X
Hybrid
All-Cloud Solution. Here, the edge device transmits all examples to the cloud. It incurs a commu- by the
nication cost in addition to the cloud inference latency. This solution is sub-optimal orange circle with 80% accuracy and inference latency of 2025ms in Figure 2(a). Our goals are: (i) To understand the trade-off between latency and accuracy;
(ii) To compare prior methods by the latency level at which cloud-accuragy is achieved.
All-Edge Solution. While we can leverage various methods (Howard al.) 2019 Hinton al. 2015; Cai et al.) 2020 Kag & Saligrama 2022), MCUnet Lin et al. (2020) is the most suitable deployable model for this conro-controller. All- baseline is blue curve in Figure
The smallest MCUNet model achieves 51.1% accuracy with 200ms inference latency. In contrast, the largest MCUNet model achieves 63.5% accuracy with 1400ms inference latency; models any larger cannot be deployed due to the MCU hardware limitations listed in Table [ Thus, cloud-accuracy is unachievable with an all-edge solution for any latency.
Aplit-Computationn methods. Kang al. (217)) splits the model between the edge and cloud device. More specifically, the initial part of the DNN is stored and exccuted on the edge device. Then, the edge transmits the intermediate features to the cloud, where the remaining computation of the DNN performed. This split takes into account the latency budget and the edge transmission cost. More recent variants al. 2021 Odema et al. 2021) add branch-out stage that allows for classification on the edge device whenever the decision is deemed correct. We employ this method in our
Although Lin al. 2021 improves upon MCUNet, their pre-trained models are not available publicly. Besides, any improvement the edge model would yield improvements in all the hybrid baselines.
3

---

Published as a conference paper at ICLR 2023
comparisons. A fundamental issue is that requiring copies of the same model server/edge severely constrains practical use cases. For instance, in Table model is 9X of MCU model. In this case, we could either use the maximum-siie size edge model and copy it to the server store partial copy of the server model locally. The former leads to topping accuracy at 63.5% (blue-line) at high latency, while the latter is plotted as the red curves in Figure 2 While results improve in the dynamic setting, they are not comparable to the other baselines. This fact is not surprising since the amount of pre- processing gained by having a shared model more than offset by allowing models optimized the edge. Since the MCUs are too small, only a tiny part of the large DNN can be stored/executed on the edge device. The resulting intermediate feature size is larger than the input size. Thus, cloud accuracy can only be achieved by transmitting all examples to the cloud at latency of an all-cloud solution.
Dynamic Neural Network methods are surveyed in (Han et al., 2021 These methods budget more compute for hard instances. It includes (a) cascade-based early exit networks (Park et al.) [0155 Bolukbasi et al. 2017 Wang et al. 2018), where the constituents are independently designed without
feature sharing; and (b) early exit networks (Teerapittayanon et al. 2017 Dai et al. 2020 Li et al.
2019) where classifiers are introduced at intermediate layers. These works generally disregard the severely conturrinnd setting such as in Table [ Within this framework, we experimented with different approaches and found that (Bolukbasi et al. 2017:|Nan & Saligramal [017]] [i et al.) 202T) serves as good baseline. These allow for different models optimized for the base and global, but the routing scheme is designed post-hoe based on classifying locally depending on prediction
uncertainty. This is depicted as green-line in Figure 2
Proposed hybrid method, in contrast to Dynamic Networks, globally optimizes all of the parts (base, router, and cloud) and the purple line in Figure 2 It is evidently close the upper bound, which is derived in Appendix A.2.basee on the practical assumption that the base model is agnostic to what examples are classified by cloud correctly. Prior works including dynamic networks and pplitccomptttionn methods general miss key details, namely, (a) no explicit accounting number of examples required to be covered locally, (b) no supervision for the router, which makes them myopic, and (c) evaluations only on small datasets (see Appendix $A.7 for details), etc.
Selective Classification, Recently, (Liu et al. 2019 Gangrade et al. 202T, Geifman & EI- Yaniv 2019) proposed learning with reject option, wherein model abstains from predicting uncertain instances. Although we obtain a selective classifier by ignoring the global model (see $3.2). we focus on improving the hybrid system, which is different objective compared to this line of research.
2 METHOD
Notation. Let X be a feature space and Y a set of labels. Hybrid design consists of the following:
A base model X + y, deployed on an edge device.
A global model g X > y deployed on the cloud.
A routing model r : X -> {0, 1} deployed on the edge.
We will treat these models as soft classifiers, outputting -ilddimensional scores {6y} and {g and two scores To and 71 for the routing model. The hard output for the base is the top entry b(z)) arg max,, (z), and similarly for g. In this paper, is realized by the a 2-layer DNN with input by (z) this intentionally chosen to have minimal implementation complexity. further admits scalar tuning parameter f,, and assigns x to the global model if r > ro + ,, i.e.
r(z; 1 (ra (x)
+ ro(z))
Varying (Alg. trades-off accuracy and resource usage, and allows us to avoid retraining r at each resource level by locally tuning a router. By default & = 0. The hybrid prediction for an instance æ is ((x) = (1 ((z)) + r(x)g(z).
Evaluation Metrics. Hybrid accuracy is the accuracy of the hybrid predictions, defined as
A(r; b, g) = P()(X) = Y) = P(r(X) = 0, M(X) = Y) + P(r(XX = 1, 1x) = Y). This accuracy is fundamentally traded-off with the coverage of the hybrid models, which is the fraction of instances that are processed by the cheap base model only, i.e.
C(r, b, == P(r(X) = 0).
Modeling Resource Usage. Coverage offers a generic way to model the resource usage of hybrid inference as follows. The resource cost of most models is mainly function of the architecture. We let
4

---

Published as a conference paper at ICLR 2023
denote generic architecture and say that f a if the function f is realizable by the architecture. Then the resource cost of f is denoted R(a). Our hybrid design always executes the base and the router, and the mean resource usage of the hybrid model (r, b. with b E ag and g E ag is R(r, b, g) R, + R(an) + (1 C(r, g))R(ag),
where R, is a small fixed cost of executing r.
This generic structure can model many resources such as energy usage or total FLOPS used. Our paper is mainly concerned with inference latency. To model this, we take R(as) to be the mean time required to execute a base model the edge, and R(ax,) ) to be the sum of the mean computational latency of executing g on the cloud and the mean communication latency of sending examples to the cloud. In the previous example of Table I. these numbers would be 200ms and 2025ms respectively.
Overall Formulation. Let s and Vy be sets of base and global architectures that incorporate implementation restrictions, and @ a target resource usage level. Our objective is
max
max A(r, b. s.t. R(r,b.9) S 0.
(3)
orE.6, Edd r.b
The outer max over (as, (ig) in (3) amounts to an architecture search, while the inner max over (r,, b. g) with fixed architecture corresponds to learning hybrid model.
Below, we describe our method for solving (3). Briefly, we propose to decouple the inner and outer optimization problems in (3) for efficiency. We train hybrid models by empirical risk minimisation (ERM) strategy. Furthermore, in Sec. [3.]] we perform architecture search using fast proxies for the accuracy attainable by given pair of architectures without directly training hybrid models.
2.1 LEARNING HYBRID MODELS
This section trains hybrid models for fixed architectures ab. Cig. i... the inner minimisation problem max A(r, b,g) s.t. R(r, b) S g. r.bbas.gEag
Since architectures are fixed in (4). the resource constraint amounts to a constraint on the hybrid coverage C(r, g). As is standard, we will approach (4) via ERM over a Lagrangian of relaxed losses. However, several design considerations and issues need to be addressed before such an approach is viable. These include: (a) cyclical non-convexity in (4), (b) supervision for the router, and (c) relaxed loss functions. We discuss these below and summarise the overall scheme in Algorithm
Alternating optimisation. Problem 4 has cyclical non-convexity. A given affects the optimal b and g (since these must adapt to the regions assigned by r), and vice-versa. We approach this issue by alternating optimisation.
Algorithm 1 Training Hybrid Models
1: Input: Training data D = ((x', y |
2: Hyper-parameters: Xr, Number of epochs E
3: Initialize: random r pre--triied 8 gg
First, we train global and base models with standard methods. Then, we learn a router r under a coverage penalty. The resulting feeds back into the loss functions of and g, and these get retrained. This cycle may be repeated.
4: for = 1 to E do
5: Randomly Shuffle
6: Generate oracle dataset Da:(b.g) using Eq. 6
7: re arg min, Looming (r, be-1 g
8:
of arg ming Letoball (re, be-1 ,g)
Modularity of training. The scheme allows modularisation by varying which, and to what extent, steps 7,8,9 in Alg are executed. It helps train a cheap routing model to hybridise given pair of pre-trained b and g; in using an sff-tf global model that is too expensive to train. Finally, we can learn each component to different degrees, e.g., we may take many more gradient steps on g than b in any training cycle.
9: b = arg ming Lrage (r b, g.)
10: Return (r gg
Learning Routers via Proxy Supervision. Given a base and global pair (b. g). Eqn. 4 reduces to
max [[ ((()) Y) - ((X) =]]
s.t. B[((X)] s Ce
(5)
where Cg is the coverage needed to ensure R S o. While naive approach is to relax and pursue ERM, we instead reformulate the problem. Observe that (5) demands that
r(X) = { if b(X) Y,g(X) +Y
(() X,g(X) =Y.
5

---

Published as a conference paper at ICLR 2023
Further, while b(X) = (XX) is not differentiated, the coverage constraint promotes r(X) = 0. Thus, the program can be viewed as a supervised learning problem of fitting the routing oracle, i.c.
o(z; b, = l(b(z) * g(z) = y}.
(6)
Indeed, o is the ideal routing without the coverage constraint. For any given (b, g) and dataset D { y"),, we produce the oracle dataset Do.(b.g) == {(x*, ,o(=;; b, g))}. It serves as supervision for the routing model r. This allows to utilise the standard machine learning tools for practically learning good binary functions, thus gaining over approaches that directly relax the objective of (5).
The oracle does not respect the coverage constraint, and we would need to assign some points from the global to base to satisfy the same. From a learnability perspective, we would like the points flipped to the base promote regularity in the dataset. However, this goal is ill-specified, and unlikely to be captured well by simple rules such as ordering points by soft loss of g. We handle this issue indirectly by imposing a coverage penalty while training the routing model and leave it to the penalised optimisation to discover the appropriate regularity.
Focusing competency and loss functions. To improve accuracy while controlling coverage, we focus the capacity of each of the models on the regions relevant to it so, b is biased towards being more accurate on the region r ({0)), and similarly 9 on r ({13). Similarly, for the routing network r, it is more important to match o(x) on the regions where it is 1, since these regions are not captured accurately by the base and thus need the global capacity. We realise this inductive bias by introducing model-dependent weights in each loss function to emphasise the appropriate regions.
Routing Loss consists of two terms, traded off by a hyperparameter Xy. The first penalises deviation of coverage from given target (cov), and the second promotes alignment with o and is biased by the weight Wr (x) = 1 + 2x(z) to preferentially fit o ((13). Below, E denotes a surrogate loss (such as cross entropy), while (+)4 is the ReLU function, i.e., (z)+ max(=, 0). Sums are over training data
of size N. Empirically, we find that A, = yields effective results.
Coauigg (r: Ar cov > -- mo(e)))) + Σ r(l.
Ein(a)
Base Loss and Global Loss are weighted variants of the standard classification loss, biased by the appropriate weights to emphasise the regions assigned to either model by the routing network
(x(x)= = r(r) and Wo (x(x)= = =1+((a)
Crose r, g) = Σ (o(z))(y.bx)))
Cgloba(bb - (o(o))(x.g(o)).
EXPERIMENTS
In this section, first, train hybrid models for exsource-constrainet MCU devices, thus demonstrat- ing the effectiveness of hybrid training. Next, we show that hybrid models can be adapted to resource- rich edge devices such as mobile phones. Next, we probe various aspects of our framework through ab- lations, including (A) validation on other datasets, (B) sensitivity of the solution to small communica- tion latencies, and (C) effectiveness as an abstaining classifier for situations when global model may be unavailable. Finally, we discuss a simple joint architecture search method for finding hybrid archi- tectures with better performance than off-the-shelf architectures (see Appendix A.3 A.4 for details).
Experimental Setup. We focus on the large-scale ImageNet dataset (Russakossy et al., 2015), 5), con- sisting of 1. 1.28M train and 50K validation images. We follow standard data augmentation (mirroring, resize and crop) for training and single crop for testing. We borrow the pre-trained baselines from their public implementations (see Sec. A.6.2). Appendix A.6. lists our hyperparameters settings.
Throughout, we use the largest model in the OFA space (Cai et al. 2020) as our global model and henceforth refer to it as MASS-600M (which needs 600M MACS for evaluation). This model has an accuracy of 80%, and computational latency of about 25ms on V100 GPU. There are three main reasons for using this model. Firstly, this model is SOTA at its required computational budget. Secondly, this model is small enough for training to be tractable under our computational limitations (unlike larger models such as EfficientNet-BB -B7, which needs 37B MACs). Finally, since it is the largest model in our architecture search space, it yields consistent point of comparison across experiments.
To expose gains from the different hybrid components we consider: (a) 'Hybrid-(r'' training routing models with pre-trained base and global model, (b) 'Hybrid((rb)' training routing and base models

---

Published as a conference paper at ICLR 2023
with a pre-trained global model, and (c) "Hybrid- training all three components. Unless explicitly stated, we create models by training routing and base, i.c., 'Hybrid-rb' since training the global model is computationally expensive. We train hybrid models to achieve similar coverage as the oracle. Post-training, we tune the threshold /. to generate r with varying coverage (Alg.
Baseline Algorithms. We investigated prior methods (Kang et al. 2017 Nan & Saligrama 2017 Teerapittayanon et al. (017]] ). and the entropy thresholding.
Bolukbasi et al. [017] Li et al., 2021]]
which we report here, dominates these methods across all datasets. This fact has also been observed in other works (Gangrade et al. 2021 Geifman & El- Yaniv 2019). It is not surprising since they lack
proxy supervision (2nd term Eq. and the routing model does not get instance-level supervision.
Coverage as Proxy. As discussed in Sec. 2 for simplicity, we use coverage as the proxy for communication latency, the major contributor to the inference latency. We explicitly model latency in Sec. 3.1 where we define the latency of the hybrid system as the sum of three latencies: (a) on-device inference, (b) communication for the examples sent to the cloud, and (c) on-cloud inference.
3.1 HYBRID MODELS FOR RESOURCE- LESOTED EDGE DEVICES
In this section, we train hybrid models with off-the-shelff architectures using Algorithm First, we delve into the illustrative experiment in Figure 2 Next, we study a similar problem for a resource-rich edge device, specifically mobile phones, and train hybrid models at various base complexities.
Resource Constrained MCU. Proposed hybrid method with MCUs for ImageNet task near optimal (close to upper bound); realizes 25% latency/energy reduction while maintaining cloud performance, and at accuracy loss of less than 2% realizes 30% latency/energy reduction.
Recall from Sec. that deployed ImageNet classifier on tiny STM32F746 MCU (320KB SR ARAM and MB Flash), the same setting as MCUNets (Lin et al.) 2020). Using their TFLite model (12.79M MACs, 197ms latency, 51.1% % accuracy) as the base, create hybrid model by adding the MASS-66 600 as the global model. We provide additional setup details in the Appendix AA22
Figure 2 shows the accuracy vs latency and energy. Table 3 shows the latency and energy of the hybrid approach against baselines. Deploying hybrid model on an MCU results in following benefits:
Pareto Dominance over on-device model. Hybrid model provides 10% accuracy gains over the best on-device model with similar latency. It achieves the best on-device accuracy with half the latency. Pareto Dominance over other baselines. Hybrid model achieves 5% higher accuracy than the dynamic networks that use the entropy thresholding baseline (see Figure In passing we recall from our earlier discussion that entropy thresholding dominates prior methods in this context. Significant latency reduction to achieve SOTA accuracy: The hybrid model achieves near SoTA accuracy with 25% reduction in latency and energy consumption. Micro-controller Implementation. We deployed base and router on the MCU with negligible (~ 2%)
slowdown (see Appendix A.10 for details).
Although our setup in Figure assumes constant communication latency of 2000ms, we can easily modify to incorporate dynamic communication latency shown in Figure (()). Due to lack of space, we refer the reader Appendix A.13 for the exact formulation.
Resource Constrained Mobile Device. Gains of hybrid method are consistent, near-optimal, and dominate prior methods, across diverse de- vices, including large footprint devices.
Table 3: Hybrid models STM32F746 MCU: Accu- racy achieved by different methods various latency.
Accuracy (%) v/s Resource Usage
To show this, we choose the popular MBV3 (Howard et al. 2019) architectures as the base since they have been heavily deployed on mo- bile devices with resource constraints such as storage and compute. We create hy brid models using the following base models in the MBV3 family: MB V3-48 (2.54M params, 48M MACs), MB 1BV3-143 (4M params, 143M MACs), and MB V- (5.48M params, 215M MACs). We use MASS-600 as the global model and operate the base model at fixed coverage level.
Latency (ms)
200
600
1000
1400
1600
2000
Energy (mJ)
11
53
96
140
161
216
On-Cloud
79.9
On-Device
51.1
60.9
63.5
Entropy
59.9
67.4
74.7
76.93
Hybrid-r Hybrid-rb
61.1
69.5
76.3
78.68
62.0
70.8
77.7
79.3
Hybrid-rbg
62.3
71.2
77.9
79.5
Upper-Boume Bound
62.8
74.7
79.9
79.9
7

---

Published as a conference paper at ICLR 2023
Table 4: Results for hybrid models with base vari- ous coverages. MASS-60X model achieving 80% Topl accuracy is used as global model. Base model be- longs to MBV3 space. Upper bounds (Appendix [ are also reported and nearly match hybrid.
Table 5: Joint evolutionary search for hybrid models base constraints: 75M, 150M, & 225M. Table shows hybrid and base accuracies at different coverages. Up- per bounds are reported in Appendix $A.2 Excess gains represent improved neural-network architecture.
Base
Base
Acc. (%) at Cov.
Base
Base
Acc. (%) at Cov.
Method
Method
MACs
A%c
MACs Acc.(%)
90%
80%
70%
90%
80%
70%
Entropy
70.7
73.3
74.9
Entropy
73.2
75.3
76.8
48M
67.6
Hybrid
71.6
74.6
76.8
74M
70.8
Hybrid
74.0
76.4
78.2
Upper Bnd
72.0
75.2
78.9
Upper Bnd
73.9
77
79.9
Entropy
75.1
76.8
77.6
Entropy
76.1
77.6
78.2
143M
73.3
Hybrid
75.9
77.8
79.0
149M
74.5
Hybrid
76.9
78.5
79.4
Upper Bnd
75.9
78.2
79.9
Upper Bnd
76.6
78.7
79.9
Entropy
77.1
78.3
78.9
Entropy
77.4
78.3
79.1
215M
75.7
Hybrid
77.6
79.0
79.6
225M
76.5
Hybrid
78.3
79.6
80.2
Upper Bnd
77.6
79.1
79.9
Upper Bnd
77.8
79.4
79.9
Table shows the hybrid accuracy at three coverage levels: 90%, 80% and 70%. Hybrid models operating at fixed coverage provide the following benefits:
Up to 70% latency reduction to achieve SOTA. Hybrid model with MBV3-215M base achieves
79.59% (near SOTA) with 70% coverage. It communicates with global model for only 30% inputs. Hybrid models oulperform the entropy thresholding. Hybrid model with MBV3-48M achieves nearly 2% higher accuracy than entropy thresholding baseline.
Hybrid model with a smaller base model achieves performance larger models at various coverage levels. Using MB V3-48M base, the hybrid model exceeds the accuracy of MBV3- 143M at 80% coverage. Similarly, it exceeds the accuracy of MBV3-215M at 70% coverage.
3.2 ABLATIVE EXPERIMENTS.
We refer the reader to Appendix A. for setup and results. Below we summarize our findings.
(A) Other Datasets. We train hybrid models on CIFAR-100 (Krizhevsky 2009) and IMDb MMas ct al. 201T) (reported Appendix), and observe similar gains.
CIFAR-100. We use the efficient version of the Resnet-32 (He et al. 2016 from (Dong & Yang 2019) as the global model (35M MACs, 0.5M params, 67.31% accuracy). Base is tiny pruned Resnet model (2.59M MACs, 0.02M params, 52.56% accuracy). Table 6 shows the performance of
the hybrid models and the entropy thresholding baseline at various coverage levels. It shows that hybrid models provide similar benefits CIFAR- 100 dataset.
(B) Other communication regimes. We train hybrid models in setup with communication delay. This arises when both base and global model reside on same hardware. In such a setup, we use a simpler evaluation metric for inference latency, i.e., hybrid MACs, i.e., the amount of multiply-add operations required execute the hybrid model. We pick up an architecture family and create hybrid model using the smallest and largest architecture. For convenience, we use MobileNetV3 MBB33) (Howard et al. 2019) family. From MBV3, we pick the smallest model (48M MACs, 67.6% accuracy) as the base and largest model (215M MACs, 75.7% accuracy) as global to create the Hybrid-MBV3 model. Figure shows the hybrid model achieves SOTA accu- racy at 30% lower latency than entropy thresholding.
Imageres sust Accuracyy1e)
TEi ingilioe
EnttoyyThreshokiig Hybrid
50
1.00
125
150
175
200
HullippyAlld Opanatioos (Millim
Figure 3: Plot for hybrid MACs accuracy. Base & Global models on same device.
(C) A bstaining classifier. When a global model unavailable, the hybrid system can serve as an ab- staining classifier the device, i.e., it rejects few inputs and provides predictions on the rest. We cre-
8

---

and a Published as a conference paper at ICLR 2023
ate abstaining classifiers with the hybrid setup in the Sec. 3.1 We show the accuracy of the base model at various coverage levels the Table shows that the abstaining base significantly outperforms the base at full coverage and the abstaining classifier from the entropy thresholding baseline, which demonstrates that our method is competitive against prior works on classification with abstention.
Table 7: Abstaining Classifier with hybrid models from Sec. 3.1 Results for hybrid models with base at various coverage levels.
Table 6: Hybrid models for CIFAR- 100 various coverages.
Base Base
Accuracy(%o (6) at Cov.
Base MACS
Base
Accuracy(%) at Cov.
MACs Acc.(%)
Acc.(%)
90%
80%
70%
80% 70%
40%
Base Entropy
Base Entropy
Base Entropy
Entropy
52.56
57.77
59.95
65.1
Hybrid-r
52.56
58.43 61.18
66.9
48M
67.6
73.3
71.7
78.6
75.6
83.4
80.5
Hybrid-rb
52.56
59.32
62.48
67.4
143M
73.3
79.0
77.6
83.9
81.7
88.4
85,4
215M
75.7
81.3
78.6
86.1
82.0
90.1
86.6
(D) Router validation. We evaluate the performance of the router against the oracle supervision and show that the router learnt using the Algorithm gemeralizzs well on the test dataset.
3.3 JOINT NEURAL ARCHITECTURE SEARCH FOR HYBRID MODELS.
This section proposes a joint neural architecture search (NAS) scheme to resolve the outer max problem of B). NAS methods are strongly dependent two aspects
Architecture Search Space. Our method is designed for implementation on Marked Architecture Search Space (MASS).
a set of architectures s/ such that each architecture a af associated with known set of canonical parameters 0,, which are known to be representative of the models under this architecture. That is, for most tasks, fine-tuning O,, returns a good model with this architecture. Such search spaces have been proposed by. for instance, Cai et al. (2200) and Yu et al. (2019). We use Cai et al. (0200) as search space as it contains a range of architectures of varying capacities.
Proxy Score Function. Given a pair of base and global architectures (as, ag), search process requires access to the value of the program (4). The score function estimates the accuracy of the hybrid model under a given resource constraint. Since training hybrid model using these architectures would be slow, we use the proposed oracle supervision as proxy for the router. Thus, the routing oracle o(,, Oks, 0tg) in conjunction with the canonical parameters (0., On,)) serves as an efficient proxy score function for evaluating the architecture pair (org Ogy).
Search Algorithm. Given these above two components, NAS reduces combinatorial optimization and can be approached by any standard heuristic. Due to its simplicity and prevalence, we use simple evolutionary algorithm for this (e.g Elsken al. 2019 Liu et 202T) yield a concrete method. Algorithm summarizes the search scheme (see Appendix A.3 for details).
Empirical Validation. We evaluate the proposed architecture search scheme against the off -he- architectures in Table as well as Appendix A..4 It shows that evolutionary search yields higher accuracy hybrid models than off-the-shelf classifiers.
CONCLUSION
We proposed novel hybrid design where an edge-device selectively queries the cloud only those hard instances that the cloud can classify correctly to optimize accuracy under latency and edge-device constraints. We propose an end-to-end method to train neural architectures, base predictors, and routing models. We use novel proxy supervision for training routing models. We show that our method adapts seamlessly and near optimally across different latency regimes. Empirically, on the large-scale ImageNet c classification dataset, our proposed method, deployed on an MCU, exhibits a 25% reduction in latency compared cloud-only processing while suffering no excess classification loss.
ACKNOWLEDGMENNTS
This research supported by Army Research Office Grant W911NF2110246 the National Science Foundation grants CCF-2007350 and CCF-1955981, AFRL Contract no. gift from ARM Corporation.

---

Published as a conference paper at ICLR 2023
REFERENCES
Tolga Bolukbasi, Joseph Wang, Ofer Dekel, and Venkatesh Saligrama. Adaptive neural networks for efficient inference. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 527-536. JMLR. org, 2017.
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once for all: Train one network and specialize it for efficient deployment. In International Conference on Learning Representations, 2020. Utttt:::: http::p::/aa....ooo//p////////// wttp:/tggg//oooeeee www99.9999.....
Min Chen, Yiming Miao, Yixue Hao, and Kai Hwang. Narrow band internet of things. IEEE Access, 5:20557-20577, 2017. doi: 10.1 10 2017.75188..
Xin Dai, Xiangnan Kong, and Tian Guo. EPNer: Learning to Exit with Flexible Multi-Branch Nenwork, pp. 234-244. Association for Computing Machinery, New York, NY, USA, 2020. ISBN
9781450368599. URL httpss://oo.. org/ 10. 11..1......11111111111
3411973,
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, abs/1810.04800 2018. URL
/ttt://arxiv/ org/
htbgg/abs/ http///ss///111 /1100.1110000000 04805
Terrance Vries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout, arXiv preprint 17xiv: 2017.
Xuanyi Dong and Yi Yang. Network pruning via transformable architecture search. In Neural Information Processing Systems (NeurIPS), 2019.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 20(1):1997-2117, 2019.
Aditya Gangrade, Anil Kag, and Venkatesh Saligrama. Selective classification via one-sided prediction. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th In- ternational Conference Artificial Intelligence and Statisties, volume 130 of Proceedings of Machine Learning Research, pp. 2179-2187. PMLR, 13-15 Apr 2021. URL https html
Yonatan Geifman and Ran Elniv..v. Selectivenet: deep neural network with an integrated reject option. In International Conference on Machine Learning, pp. 2151-2159, 2019.
Yizeng Han, Gao Huang, Shiji Song, Le Yang, Honghui Wang, and Yulin Wang. Dynamic neural networks: A survey, 2021.
K. He, X. Zhang, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016. doi: 10.1 10.100/C22..
S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv: 103.0555,. 2015.
Andrew Howard, Mark Sandler, Grace Chu, Liang-Chich Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang. Vijay Vasudevan, Quoc V. Le. and Hartwig Adam. Searching for mobilenetv3. CORR, hts/1995.02244, 2019. pollatttp://axxiv.oort www./oog.//aaa.aa.oooo.....sseea wttp://////r//......222.22.
905. 02244
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
Anil Kag and Venkatesh Saligrama. Time adaptive recurrent neural network. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 15149-15158, June 2021.
Anil Kag and Venkatesh Saligrama. Condensing cnns with partial differential equations. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 610-619, June 2022.
10

---

Published as a conference paper at ICLR 2023
Anil Kag. Ziming Zhang. and Venkatesh Saligrama. Rnns incrementally evolving equilibrium manifold: A panacea for vanishing and exploding gradients? In International Conference on Learn- ing Representations, 2020. httthhttt///poet
nnt/ www.:ewwweee//oourrreee wtt.orrmniddyyyyopdoaa...
Yiping Kang, Johann Hauswald, Cao Gao, Austin Rovinski, Trevor Mudge, Jason Mars, and Lingjia Tang. Neurosurgeon: Collaborative intelligence between the cloud and mobile edge. SIGPLAN Not., 52())))))))666 apr 2017. ISSN 1362-1340. doi: 10. 00.1145/09333363003377
https
11..144433333333377668888 3037698
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Rajath Kumar, Mike Rodehorst, Joe Wang, Jiacheng Gu, and Brian Kulis. Building robust word-lever wakeword verification network. In INTERSPEECH, 2020.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. ALBERT: A lite BERT for self-supervised learning of language representations. CoRR, abs/1909. 2019. URL http: org/ abs 1909. 11942
Hao Li, Hong Zhang, Xiaojuan Qi, Ruigang Yang, and Gao Huang. Improved techniques for training adaptive deep networks, 2019.
Min Li, Yu Li, Ye Tian, Li Jiang, and Qiang Xu. Appealnet: An efficient and highly-accurate edge/cloud collaborative architecture for dnn inference, 2021.
Lin, Wei-Ming Chen, Yujun Lin, John Cohn, Chuang Gan, and Song Han. Mcunet: Tiny deep learning on iot devices. arXiv preprint arXiv:2007. 10319, 2020.
Lin, Wei-Ming Chen, Han Cai, Chuang Gan, and Song Han. Mcunetv2: Memory-efficient patch- based inference for tiny deep learning, In Annual Conference Neural Information Processing Systems (NeurIPS), 2021.
Yuqiao Liu, Yanan Sun, Bing Xue, Mengjie Zhang, Gary G Yen, and Kay Chen Tan. A survey on evolutionary neural architecture search. IEEE Trunsactions on Neural Networks and Learning Systems, 2021.
Ziyin Liu, Zhikang Wang, Paul Liang, Russ Salakhutdinov, Louis-Philippe Morency, and Masahito Ueda. Deep gamblers: Learning to abstain with portfolio theory. In Advances in Neural Information Processing Systems, pp. 10622-10632, 2019.
Andrew I.. Maas, Raymond F. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 142-150. Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL http: //www. www.wa.cwwb.coo wwg.:/lwwwor...ee.oooooooooooo.o
www.tottoooooooooooooooooooooooo ant www.thhoooy//P1111000
Feng Nan and Venkatesh Saligrama. Adaptive classification for prediction under a budget. In Advances in Neural Information Processing Systems. pp. 4727-4737, 2017.
Mohanad Odema, Nafuu Rashid, Berken Utku Demirel, and Mohammad Abdullah AI Faruque. Lens: Layer distribution enabled neural architecture search in edge-cloud hierarchies. In 2021 58th ACM/IEE Design Automation Conference (DAC), pp. 403-408, 2021. doi: 10. (0.1109/AC18074, 2021 4021.9586259.
Eunhyeok Park, Dongyoung Kim, Soobeom Kim, Yong-Deok Kim, Gunhee Kim, Sungroh Yoon, and Sungjoo Yoo. Big/little deep neural network for ultra low power inference. In 2015 International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), pp. 124-132,
2015. doi: 10. LLLL19/CODDESSS2201155535
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115 2015. doi: 10.1007/s 1263-015-0816.y..

---

Published as a conference paper at ICLR 2023
Mingxing Tan and Quoe Le. EfficientNet: Rethinking model scaling for convolutional neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6105-6114 14, Long Beach, California, USA, 09-15 Jun 2019. PMLR. http //proceedings.. ml wrw.s wttpttn.tttttttt 9a.
Surat Teerapittayanon, Bradley McDanel, and H. T. Kung. Branchynet: Fast inference via early exiting from deep neural networks, 2017.
Xin Wang, Yujia Luo, Daniel Crankshaw, Alexey Tumanov, Fisher Yu, and Joseph E. Gonzalez. Idk cascades: Fast deep learning by learning not to overthink, 2018.
Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. In Proceedings of the AAAI Conference Artificial Intelligence, 2021.
Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang. Slimmable neural networks. In International Conference on Learning Representations 2019. URL /ttppttpp///oeeeeee.ee net 2ett/Eorumm1..cHHgMMMMAAC
12

---

Published as a conference paper at ICLR 2023
A APPENDIX
A.1 DATASET DETAILS
Imagenet Russakovsky et al. 2015). This is the popular image classification dataset consisting of 1000 classes. It has nearly 1.28M training and 150K validation images. A typical image in this dataset has 224 x 224 x pixels. We follow standard data augmentation (mirroring, resize and crop to shape 224 x 224) for training and single crop for testing. Following earlier works (Howard et al. (0119) Cai et al. 2020), we report the results on the validation set.
CIFAR-100 Krizhevsky (2009). This is 100 way image classification dataset consisting of images with 32 x 32 x 3 pixels. It has 50K train and 10K test images. We follow standard data augmentation used earlier works He et al. (2016); Huang al. (017). In addition, we use the cut-out De Vries& & Taylor with the standard window size of 8.
(standard gaussian normalization/mirroiin haaari/oommmrorinnsiiiitnggn
IMDb Maas et al. (2011). This is sentiment classification dataset with two classes (positive and negative). It consists of raw text of movic reviews. There are 25K train and 25K test data points. We borrow text parsers and tokenizers from the models available in the HuggingFace library.
A.2 ILLUSTRATIVE EXAMPLE DETAILS
Edge and Cloud devices. We use a V100 GPU the cloud device. has 16GB VRAM and the server associated with this GPU has ITB storage. We use STM32F746 ARM Cortex-M7 MCU as the edge device. has 320KB SRAM and IMB Flash storage.
On-Cloud Baseline. We use the MASS-600 Cai et al. (2200) as the global model in this experiment. achieves 79.9% Topl accuracy on the Imagenet dataset. This model has a computational footprint of 595M MACs. As per our benchmarking, the inference latency of this model on a V100 GPU is 25ms.
On-Device Baselines. Lin et al. (020) have explored deploying tiny MCUNet models the
STM32F746 MCU. We borrowed their pre-trained MCUNet models from their github repository F
There are three different models with varying inference latencies and accuracies, namely: (a) model-A A (12M MACs, 0.6M parameters, 200ms latency, 51.1% % accuracy), (b) model-B --B (8 1MM MACs, 0.74M parameters, 1075ms latency, 60.9% accuracy), and (c) model-C (170M MACs, 1,4M parameters, 1400ms latency, 63.5% accuracy). We use the smalled model, i.c., model-A as the base model in training the hybrid model. This model has the least latency as well as the least accuracy among the three models. Note that this model has the input resolution of 96 x 96 x 3 and as result the input size becomes nearly 28KB.
While we are aware of the updated version of MCUNet, i.e., MCUNetV2 (Lin et al. 2021). we point out that MCUNeIV2 models are not publicly available for us to include in the empirical evaluation. Besides, our hybrid framework is completely agnostic to what the base and global model choices are. One can use any base and global model in the above setup and observe the relative gap between various baselines.
Energy Profile Base Model Execution and Communication Cost. We assume that the MCU device operates at 200MHz clock speed and is connected to 3.6V power supply. It has an active mode current characteristics of 72μA per MHz. Thus, it consumes = 3.6 72 x 200 = 51.84 mW (i.e. mili Joules per second) energy in active mode. As result, the energy consumed by the base model (200ms latency) on this edge device = 51.84 x 0.2 = 10.368 mili Joules. Similar calculation yield the energy consumption the on-device models: model-B (60mJ) and model-C. (80mJ).
We use the NB-IoT Then et al. 2017) communication protocol with 110kbps transmission rate and a transmission current characteristics of 30mA. Thus, it consumes 30 3.6 108 mili Joules per second in transmission mode. Let us calculate the time taken to transfer the input image from the
"htps//huggingface.co
"https//www.st.com hhanp://gituub.cm/miibaaaaa http://hhhh..oommommmaaaaaaaaa/a
13

---

Published as a conference paper at ICLR 2023
base model on the edge device the global model on cloud. The base model input has size 28KB and the transmission rate is 1 110kbps. Thus, it takes = 110 the edge device to the cloud. As result, the energy consumed by the edge device in transmitting this
28-8 seconds to transfer this image from
image is = 108 * 2 = 216mJ.
Split- ColiitCommutttionn Baseline. We use this term to refer methods Kang et al. (2017): Teerapittayanon et al. (2017) wherein the initial part of the global model executes on-device while the remaining executes on-cloud. The initial network allows for an early exit classifier for easy examples. Split into early layers results in high communication cost but split in later layers results in higher base computation latency, making ineffective in the edge-cloud setup.
We trained the Branchy Teerapittayanon et al. (2017) method to represent this baseline. We create an exit classifier after the first MBConv layer in the global model and train such an exit classifier. This split results in spending 48M MACs in the base computation and then features are transferred to the global model in case the exit classifier sends the example further layers. Note that in this case the feature cost is more than twice the input size and thus, this baseline suffers much worse from the communication delay than others. This method can always ditch the processing on the edge and send all examples to the cloud, thus achieving global accuracy with same latency and energy consumption as the on-cloud solution.
NAS+Partite Baseline. We use this baseline to represent methods such LENSOdema et al. (202T) that extend split-computatin by performing a neural architecture search to find the best split under the communication delay constraint. To be consistent with evolutionary search experiments, we use the MASS to find the best split with the communication latency mentioned earlier. This search space contains architectures ranging from small to large across diverse target accuracies.
Dynamic Neural Networks. This baseline refers to various recent methods Nan & Saligrama (2017 Bolukbasi al. (2017); [Li et al.] (202T) that propose dynamic computation and includes base-model based entropy or margin threshoding.
Hybrid Model training. We use the MCUNet model-A as the base model and the MASS-600 the global model. We train the hybrid models using these base and global architecture pairs. Let e be the coverage of the base model, i.e. fraction of examples are inferred on the base and 1 fraction of examples are sent to the global model. At c = 100%, we obtain the on-device performance. Although hybrid models trivially achieve on-cloud performance by sending all examples the global model, i.e. at = 0%, our hybrid training procedure obtains the on-cloud solution at with less communication. Let & denote the inference latency on the edge (in this case it is 200ms), while fg denote the inference latency the cloud (in this case it is the sum of communication cost and inference latency of the global model, i.e. 2000 + 25 = 2025ms). Thus, we can write the inference latency of the hybrid model coverage follows:
Hybrid Lateney @c é, + (1 (1-c)e,
Similarly, using we can compute the energy consumption for the hybrid inference as follows:
Hybrid Energy @c = 14h + (1 - c)/²g
where ie and Mg are the edge device energy consumption for on-device and on-cloud inference. In this case, μy 10.37mJ and M9 216mJ.
Upper Bound. Let us develop an upper-bound on achievable accuracy as function of latency. Recall from Table that communication latency dominates processing time. Also recall the notion of coverage, which denotes the fraction of examples locally processed. Note that there is one-to-one correspondence between coverage and latency of the hybrid system. Suppose ats Og denotes base accuracy and cloud accuracy. The base predictor predicts (1 as) fraction incorrectly, and among these suppose we make the reasonable assumption that the router is agnostic to which those are correctly classified at the cloud. Then upper bound on the target hybrid accuracy is given by the expression:
Hybrid Acc@c < min 0g 1--a Obb
ab
* (1 (1- c) + as. {
Notice that c = 0, c= 1, we recover global and base accuracies, and c = as is the cut-off point, namely cloud accuracy is achieved at the latency associated with the coverage
Intuition on the Upper Bound. The expression ca2 + (1 - c)a, is an underestimate of the best possible accuracy operationally, one see this by the fact that this is achieved simply by abstaining
14

---

Published as a conference paper at ICLR 2023
randomly the rate c. Quantitatively, note that cas + (1 c)a, - ag under the natural assumption
that ag 2 at,, and further that cas, + (1 c)a, as + (1 (ag ab) I ab + I-an (ag ab). upper bound in detail:
Let us explain
Let e 2 at. If the router were perfect, then it would assign every point that the base model gets
correct to the base this gives accuracy of on an as fraction of inputs.
Qs points are assigned. Here, we make the assumption that since the router small and cannot model the accuracy of the global model perfectly, it randomly spreads these points across the base global models. In this case, to get overall coverage to the base (in which case it get none of these points wrong), and (1 c)/(1 0g) of the remaining points to the global. We will now upper bound the accuracy of the global model on these remaining points.
Now we need to consider how the remaining
c, it must assign a fraction of (c- abd) aus) of these remaining points
Here we use second assumption - that every point that the base gets right also gotten right by the global model. This is to good approximation, mainly due the strong capacity difference between the models.
This means that the conditional accuracy of the global model on the points that the base gets wrong is severly depressed in particular, this is at most 1-as, points. The global gets ag-V correct. We remove the ag that the base gets right get that there are (Og o6) N points that the global gets right and the base doesn't. Now normalise by the
a (imagine that there were N >> 1 test
(1 0g N points that the base got wrong).
This gives us the overall accuracy
(c-as)
1-c
0g a6
on 1 1+ 0mb)
1-aa
1 a6b 1 0tb
which is exactly our upper bound (well, this, or agg, whichever is smaller, since the global dominates the base and so we can never get more than ay accuracy).
To sum up, the upper bound arises under the assumptions that the global model strictly dominates the base model, and that conditionally on the base model getting query point wrong, the router unable meaningfully discriminate between whether the global model gets queries right or wrong.
A.3 JOINT NEURAL ARCHITECTURE SEARCH FOR HYBRID MODELS.
Algorithm Evolutionary Joint Architecture Search
1: Input: Data D ((x', yf ) Architecture Search Space s (e.g. Cai et al. 2020
2: syper-parameters: Number of generations G, Resource Constraint y
3: Hyper-parameters: Number of popular architecture pairs NPpop.
4: Hyper-parameters: Number of popular parent architecture pairs Npar:
5: Initialize: Set of popular architecture pairs Ppup {oo. { within constraints
6: for = to G do
7: Ppar < N highest score (Eq. pairs from Rpop
# Obtain the parent set Ppur
8: Peai + (1
# Initialize children set Reaidd
9: for n 1 to Npop do
Randomly pick (at, at) from Spar (ar ax 4 Mutate (ai, a²)
# Pick base & global pair
11:
# Add mutations on width, depth, etc.
12:
Compute the oracle og for fag , 0am if R(og Nagg,0as ( > to then GOTO
# Compute proxy oracle supervision
# Repeat if constraint not satisfied
14:
Add (ag", ;ag) to Rahild
Add as promising child pair Add children to popular set
Spop Ppur SanUSSuue UnDttild
16:
Return Slpp
# Return promising architecture pairs
This section proposes a joint neural architecture search (NAS) scheme to resolve the outer max problem of (3). NAS methods are strongly dependent on two aspects
A favourable architecture space which contains range of architectures of varying capacities, and Fast scoring proxies that produce estimates of the overall accuracy of the best model realized by a given architecture without training the same (which would be very slow).
Given these two, NAS problems can be reduced to combinatorial optimisation and approached by any standard heuristic. In case, will define favourable property of the architecture space and
15

---

Published as a conference paper at ICLR 2023
then proxy scores for accuracy at a given resource consumption. These are plugged into simple evolutionary search to yield a concrete method.
Architecture Search Space. Our method is designed for implementation on Marked Architecture Search Space (MASS). It is a set of architectures of such that cach architecture a E a/ is associated with known set of canonical parameters Aa. which are known to be representative of the models under this architecture. That is, for most tasks, fine-tuning 8, returns a good model with this architecture. Such search spaces have been proposed by, for instance, Cai al. (2020) and Yu et al. (011)).
Proxy Score Function. We denote the value of program 4 for given pair of architectures old; Og as A(as, agi g). It requires (slow) maximisation over b E ab. g É agg, as well as training a router to attain the resource constraint. Below, we describe how to construct fast viable estimates for a MASS.
Substitute for optimisation over g). MASS gives canonical models O₂ for each architecture a. Since these represent the actual performance, we take the simple approach of using the base model i = O,, and ğ = 0a, to compute scores. This the main reason we invoke the MASS concept itself.
Substitute for optimisation over To quickly approximate the result of training over we use the routing oracle o to design a constraint-aware score.
Suppose we are given a pair of models b, g. Let (, g) and C, g) be the empirical accuracy and coverage of the oracle model (0b.g: b, g). C, 2 Ce then o can serve as the appropriate oracle. On the other hand, if C. Cg. we observe that we can increase the coverage of this hybrid model by simply taking subset of o ((1}) of relative size C. Co, and flipping their assignment to O.
Importantly, which points are flipped this way is irrelevant when it comes to determining the resulting accuracy indeed, from the perspective of o, switching the label of any point from 1 to 0 incurs the same error. Further, the accuracy that results is an upper bound on the optimal accuracy of hybrid system satisfying the resource constraints. This gives the following proxy score for given b.g:
(b gi e) == (b, g) (C. Cb. g))
Overall Score. Plugging the canonical models into the above we get the score S(ap, Og's 2) S, (6... iag; Co),
(8) which is effective under the assumptions that the architectures admit canonical models as above, and that the oracle accuracy Ao induces the same ordering base-global pairs as the routing optimisation.
Search Algorithm. Finally, we have a scoring function and a space in hand, and so can instantiate a search algorithm. Due to its simplicity and prevalance, we propose using evolutionary algorithm for this (e.g [Elsen et al. 2019 Liu et al. 2021). Algorithm 2 summarizes the search scheme.
A.4 EMPIRICAL VALIDATION FOR NEURAL ARCHITECTURE SEARCH OVER HYBRID SYSTEMS
End-to-end optimization across Edge/Cloud neural architectures, predictors, and routing models achieves 80% latency reduction with an Edge model 1/ 1/hth the size of Cloud model.
So far, we have trained hybrid models using off-the-shell architectures not tuned to maximize hybrid performance. Here, we search for optimised base and global pairs using the proposed evolutionary search Algorithm 2 We use the OFA space (Cai et al. 2020) as our MASS. We constrain the search to operate at fixed base MACs and coverage level 70% (on average, only 30% may be queried). Recall that coverage is a surrogate for latency in high communication latency regime. After finding base and global pairs from the evolutionary search, we create hybrid models with the newly found architectures. We perform this experiment for three edge device constraints as in the previous section: 75M, 150M, and 225M. Note that the smallest model in the MASS is close to 75M MACs. Hence, cannot search for model below these constraints.
Figure 4 plots the operating curves for the hybrid models found using the NAS, as well as using existing base architectures (MBV3-215M, MASS-240M) Table shows the hybrid performance the various coverage levels. Evolutionary search based hybrid models provide the following benefits:
Evolutionary search yields higher accuracy hybrid models than off- the-f classifiers. As illus- trated in Figure 4 evolutionary architecture search based hybrid models pareto dominate the hybrid models using the best known base models in MBV3 and MASS family of architectures.
16

---

Published as a conference paper at ICLR 2023
Up to 80% latency reduction achieve SoTA accuracy. Using base with 225M MACs and 76.5% accuracy, the hybrid model achieves 79.6% accuracy at 80% coverage.
Hybrid models outperform entropy thresholding.
MASS-500M (Global)
A.5 ALGORITHMS
Imaganat topa accunaeye
We summarise the methodological proposals as algo- rithms. The overall method is to begin with training super-net in the sense of Cai et al. 22200). for which the methods their paper can be utilised. This produces set of architectures df, with associated canonical mod- els for each E A. The overall procedure then is summarised Algorithm 3 This uses the two main procedures of architecture search (Algorithm (2 and hybrid training (Algorithm[] [T] subroutines, which in turn may be executed in modular way as discussed at length in the main text.
MASS 240M
Hybris M
70
M 240M
21522-215M
Mybrid-Sarch
Coverage)
Figure 4: Comparing hybrid models trained with Off-the off-th architectures vs architectures found using Joint NAS (Algorithm 2
In addition, we frequently tune a given router r and base and global models to locally trade-off resource usage levels and accuracy (which saves on retraining on each different value of @ that one may be interested in. This is realised by finding value adjusted to the constraint, and using the routing function r(;; t) = (z) 2 Ti (z) + t]. Such a may be found as in Algorithm
Algorithm 3 End-to-end Hybrid Procedure
1: Input: Training data B (x*, )') Validation data V {(0), ( resource constraint
Ø.
2: Train supernet using the method of Cai (2020).
(Architecture Search)
3: of &- resulting set of algorithms.
4: (as,ag) < output of Algorithm with V. .d.
5: Train initial models 6" E ab, 9d Og using B
(Hybrid Training)
6: (r, br) + output of Algorithm instantiated with B, 60, g", and with appropriate hyperparame-
ters.
7: Return: br)
Algorithm 4 Tuning Routing Model
1: Input: Validation data V {(x), n2 M target resource level Hybrid model (r, 6, .).
2: T <- {ra(z) ri (x) : x E V}.
c* min c R, + R(a,) (1 R) S e.
4: t" < c'tt quantile of T.
5: Return: t²
A.6 IMPLEMENTATION DETAILS
A.6.1 HYPER-PARAMETT SETTINGS.
We use SGD with momentum as the default optimizer all our experiments. We initialize our hybrid models from the corresponding pre-trained models and use learning rate of 1e for learning base and global models. We use a learning rate le for learning the routing network. We decay the learning rate using cosine learning rate scheduler. As recommended in the earlier works, use weight decay of le We set the number of epochs to be 50. We use a batch size of 256 in our experiments.
17

---

Published as a conference paper at ICLR 2023
A.6.2
MODEL DETAILS
Entropy Thresholding Baseline. As per recommendation in the literature (Teerapitayynon et al.
2017
Gangrade al. (021) we compute the entropy H of the base prediction probability distribution
by (2). This baseline allows access to a tunable threshold Predictions with entropy below this threshold are kept with the base model while the predictions with entropy above this threshold are sent to the cloud model. We use similar tuning as Algorithm 4 to trade-off resource usage.
Routing Model. Our routing model uses predictions from the base model and creates 2-layer neural network from these predictions. We create meta features from these predictions to reduce the complexity of the network, by (a) adding entropy feature, (b) and adding correlations between top 10 predictions, resulting in 101 dimensional input feature vector. The feed-forward network has 256 neurons in the first and 64 neurons in the second layer. The final layer outputs two dimensional score leading to binary prediction for the routing r. Note that the routing network described this manner contributes to less than 2% compute budget of the base model and hence its compute cost is negligible in comparison to the base and global models.
MBV3. We have used the MobileNetV3 Howard et (2019) models as base in the hybrid models designed for mobile devices (see Sec. 3.1 Sec.3.1.
We borrowed pre traitra models from publicly available implementation Table 8 lists the performance and compute characteristics of these borrowed models.
Table MBV3 models our setup.
Topl Accuracy
#Params
#MACs
MBV3-48
67.613
2.54M
48.3M
MBV3-143
73.3
3.99M
143.4M
VBV3-112
71.7
112M
MBV3-91
70.4
91M
MB
75.721
5.48M
215.3M
MASS. We borrowed the pre-trained Cai et al. (2020) models from the official public repository Table 9 lists the accuracy, number parameters and MACs for these models. We note that these models have been specialized by the authors with fine-tuning to achieve the reported performance.
Table Once-for-All Pre-trained models in setup.
Top1 Accuracy
#Params
#MACs
MASS-600 ('flops @ 595M
Mttplltopooooo I @ 80.0 finetune @75')
79.9
9.1M
595M
MASS-482 ('flops 482M top1 79.6 finetune @75)
79.6
9.1M
482M
MASS-389 ('flops @ 389M_topl @7.1 19..1__fieee. l_ineetne @ @75')
79.1
8.4M
389M
MASS-240 ("LG-G8 lat @ 24ms_topl @ 116.4_finetunee @25')
76.4
5.8M
230M
MASS-151 ('LG-G8 lat@ 16ms_ 16ms_topl @ fineetnff @25')
74.6
5,8M
151M
MASS-101 ('note8 lat@3lms sosssttplllllll 72.8 finetune @25')
72.8
4.6M
101M
MASS-67 ('note8 lat @ @2ms topl @ 70.4 finetune @ @25)
70.4
4.3M
67M
A.7 DIFFERENCE BETWEEN APPEALNET AND OUR HYBRID DESIGN.
Below we highlight main difference between AppealNet (Li et al. (2021) and our proposal.
AppealNet formulation does explicitly model any coverage constraint that enables the base model to operate at a tunable coverage level. In contrast, we explicitly model a coverage penalty.
Jointly learning the routing without any supervision is hard problem. Instead, we relax this formulation by introducing the routing oracle that specializes in routing network for given base and global pair. With this oracle, the task of learning routing reduces to binary classification
18

---

Published as a conference paper at ICLR 2023
problem with the routing labels obtained from the oracle. This also decouples the routing task from the base and global entanglement.
AppealNet does not use supervision like us, and as such such strategies ultimately resemble thresholding on examples whose anticipated loss exceeds some threshold. To see this consider Algo. line Li et al. (2021) 1 for m examples. Taking the derivative wrt y yields /3 // E., I-q(0, m Σx ((f((()))))))))))))))))) v) ((fo(z).)) v). The RHS is the excess loss. For small values of ((0)z), can approximate the LHS to yield: B m En + ((0[z)) ~ Excess-Loss. Simplifying we get: m ((0x)) 3 Excess-Loss
This expression suggests a relaxed objective that we should enforee the fact that examples sent to the cloud is broadly proportional to excess loss, and as such represents very weak supervision.
1
In addition, we propose a neural architecture search that finds pair of base and global architectures that optimise the hybrid accuracy at any given combined resource usage.
Empirically, AppealNet does not have any evaluations for the Imagenet scale dataset. The closest comparison we can find is with the Tiny-Imagenet dataset (one-tenth of the size of the Imagenet). While we cannot compare the two directly, since solve much harder problem than Tiny- Imagenet, we can make the following observations. At 70% coverage level, for AppealNet, the minimum performance difference between the hybrid model and the global model is 1.2% (see AppealNet, Fig. 5(d)), while our closest to the global in case of the MobileNet baseline is 0.3% (see our paper Table 1, row 3). Note that AppealNet performance will go down on Imagenet in comparison to Emn--mmgennet due to the hardness of the problem.
We compare Entropy Thresholding, AppealNet, and the proposed Hybrid model on the CIFAR-100 100 dataset. Table TOoooss that entropy thresholding outperforms AppealNet. In addition, the proposed Hybrid model outperforms these baselines substantially.
Table 10: Hybrid models for CIFAR-100 at various coverages.
Base A%c
Accuracy(%) at Cov.
Scheme
80%
70%
40%
Entropy
52.56
57.77
59.95
65.1
AppealNet
52.56
57.65
59.89
64.9
Hybrid-r
52.56
58.43
61.18
66.9
Hybrid-rb
52.56
59.32 62.48
67.4
A.8 DIFFERENCE BETWEEN LENS AND OUR HYBRID DESIGN.
Although below we highlight main difference between LENS (Oema et al. 2021 and our proposal, we emphasize that LENS studies the edge-cloud interactions purely from systems perspective and as such does not dwelve into the learning aspects and the trade-off required in routing the inputs in severely resource constrained edge devices as well as their limited communication capabilities.
(A) Our Objective: On large-scale tasks (such as ImageNet). for the given WiFi rate, our goal is to realize the accuracy of an arbitrarily large DNN model (deployable on the cloud) by means of hybrid method deployed on edge. We selectively route difficult inputs on the edge to the cloud, maintaining top-aceuracy, while consuming minimal energy/latency.
Our Edge. Our edge device only has CPU or MCU compute capabilities (see Sec. 3. In addition, these edge device severely resouce constrained, namely they only allow low powered transmission as well as low transmission rates. These constraints limits the model that can be deployed the edge to be very low footprint. For instance, our illustrative example only has 1 10Kbps transmission rate (see Sec. A.2)..
This together with our desired accuracy places stringent constraints on edge to crisply learn hard-to- tard-tto-redictt examples, and characterizes fundamental limits of hybrid ML.
(B) Cireuit/Systems Prior Works (ex: LENS or Neurosurgeon). Their goal for a given dataset is to split/partition computation of a (suitably optimized) DNN to minimize latency/energy in response changing wireless conditions.
19

---

Published as a conference paper at ICLR 2023
LENS Edge. Odema et al. (2021) has GPU compute capabilities the edge device. As result, large DNNs can be comfortably executed on this device without a significant delay as compared to the on-cloud solution. In addition, their edge device leverage high transmission rate (up to 25Mbps). As a result, LENS explores a different setting agnostic to data. They leverage low transmission lateney compensate the difference in edge and cloud GPU times, motivating partitioning.
(C) Objective (B) is suboptimal for objective (A). (B) requires the same network model on the edge and the cloud, which artificially constrains DNNs to fit into edge's specifications, while hoping realize cloud-server gains the partitioned parts. For large-scale tasks (ImageNet), high-accuracy can only be achieved by large DNNs (even with NAS optimization Cai et al. (2020), which are edge-deployable, and using different architectures edge/cloud is fundamental in (A).
(D) LENS baselines are too weak. Direct comparisons are difficult due to different system choices(see (B)). Still
note that LENS:
reports results on small CIFAR-10 dataset, which is not representative
uses VGG-16 based architecture(large DNN) typicalyy not edge-deployable
with all-cloud processing, achieves 82%, significantly lower than VGG16 published results
(93.56% see hhttps://ggttit
com/ ge fmany/ciiii far-vvgg
-with optimal NAS+partitioning gets 77% under 25% energy reduction (see Fig. 6)
In contrast, for CIFAR-IO we trained standard (tiny) models (see MCUNet model described as On-Device baseline in Sec. A.2) deployable on MCUs.
MCUNet al. 2020) is deployable on the resource constrained MCUs.
VGG-16 on CPU has 280X worse latency w.r.t our model
With all- processing we get 91.7% accuracy consuming 11mJ, and 85% under 25% energy reduction.
This shows using same model cloud/edge is suboptimal (see (C)).
(E) Large-scale Task: LENS code is unavailable; Direct Evaluation is difficult. LENS employs GP-based bayesian optimization to NAS, which known to produce poor results (see White et al. (2021), )) which is also evident from (D). Due to lack of publicly avaiable codebase, created a similar baseline to see the performance gap between our proposal and LENS on the illustrative example in the introduction (see Figure 2}. We optimized NAS+partitioning method by optimizing over OFA models/architecctress Cai et al. (2020). These architectures range from small to large models across diverse target accuracies. Hybrid methods overwhelmingly dominate NAS+partitioning methods (pink in Figure 5). again reinforcing our point (C).
A.9 ONCE-FOR-ALL SEARCH EXPERIMENTS
For our evolutionary search experiments, we used the Cai et al. there are two MobileNetV3 backbones available: (a) with width multiplier and (b) another with width multipler 1.2. The range models these two space together is around 75 600M MACs. MASS allows searching over expansion factor options [3,4,6], width multiplier [1, 1.2). convolutionarl kernel sizes [3,5,7], block depths [2,3,4], and resolutions [144, 160, 176, 192, 208, 224].
(020)) as the MASS. In this space,
To perform a mutation, each optimization variable is modified with probability 0.1, where modification entails re-sampling the variable from a uniform distribution over all of the options. The population size is set to 100, and the parent set size is set to 25.
Table I1 shows the characteristics of the base and global models found using this search. Similar to Cai et al. (2020) we fine tune these models further for 50 epochs with their setup to achieve the final accuracy.
A. MCUNET ROUTER DEPLOYMENT OVERHEAD
We deploy both MCUNet and our base with routing model on the MCU using the TensorFlow Lite for Microcontrollers (TFLM) runtime. Due to lack of operator support for reductions and sorting in TFLM, we replace the relevant operators with supported operations whose compute and memory
20

---

Published as a conference paper at ICLR 2023
80
Global
75
Imagenet Top1 Accuracy
70
65
On-Device
On-Cloud
60
Dynamic-Networks
Split-Computation
55
Hybrid
Upper-Bound
Base
Partiinti
250
500
750
1000
1250
1500
1750
2000
Inference Latency (ms)
Figure 5: Image recognition on the ImagetNet dataset: Accuracy vs Energy and Latency plot. This clearly shows that the hybrid design pareto dominates on-device well as other basclines while getting significantly closer the upper-bound in hybrid design.
21

---

Published as a conference paper at ICLR 2023
Table 11: Joint Evolutionary Architecture Search: Models found at three different base MAC constraints (75M.
150M, 225M).
Top1 Accuracy
#Params
#MACs
Scarch-MASS-225
76.5
5.8M
225M
Search-MASS-149
74.5
5.3M
149M
Search-MASS-75
70.8
4.5M
75M
complexity upperbounds the un-supported operations. Table 12 compares the performance energy profile of the hybrid model and the baseline when deployed on the micro-controller (STM32F746) with 320KB SRAM & 1MB Flash. It clearly shows that there is negligible cost of deploying the proposed routing scheme and only results in 2% slowdown.
Table 12: Profiling the on device latency and energy overhead associated with deploying the Hybrid model
(MCUNet + router) as compared to deploying the plain MCUNet model on the MCU.
Model
Latency
SRAM
Energy
MCUNet
0.25368s
156708 bytes 0.1112 joules
Hybrid-MCUNNt
0.25951s
158036 bytes 0.1134 joules
A.11 ABLATIVE EXPERIMENTS
A.11.1 BASE AND GLOBAL ON SAME DEVICE
So far we have focused on a setup where base and global models are deployed on separate hardware. In this experiment, we deploy the base and global models on the same device. As result, there is no communication delay in the setup. In such a setup, we can use a simpler evaluation metric for inference latency, i.e., hybrid MACs, i.e., the amount of multiply-add operations required execute the hybrid model. We pick up an architecture family and create a hybrid model using the smallest and largest architecture. For convenience, we perform this experiment for a known family, namely MobileNetV3 (MBV3) (Howard et al.] 2019). From MB V3, we pick the smallest model (48M MACs, 67.6% accuracy) as the base and largest model (215M MACs, 75.7% accuracy) as global create the Hybrid-MBB MBV3 model. Figure shows the hybrid model performance against the intermediate points in the MBV3 space.
76-
Imagent Tap1 Acumecytil
74-
incraaze
72-
MBV3
50
75
300
125
150
175
200
225
Multipy Add Operations (Million))
(a) MobileNetV3
Figure MBV3: Plot for hybrid MACs vs accuracy.
Figure 6 shows the hybrid model performance against the intermediate points in the MBV3 space as well as entropy thresholding baseline. These experiments provide evidence for the following properties of hybrid models:
Hybrid achieves SOTA w.E. global model with up 40% lower latency. Global model in MBV3 achieves 75.7% accuracy by off-loading every example to the cloud while hybrid model achieves same accuracy by sending only 60% examples to the cloud. Thus, saving 40% communication cost.
22

---

Published as a conference paper at ICLR 2023
Training Hybrid model for intermediate latency is inexpensive. To achieve single model at any latency. we find an architecture with this constraint and train it to non- trivial performance. Hybrid model with extreme points trades off latency for accuracy and save compute for training models for any intermediate constraint.
Hybrid models dominate entropy thresholding baseline used in dynamic neural networks. Hybrid models outperform entropy thresholding at every coverage level with up to 1.5% accuracy gains.
A.11.2 ROUTER VALIDATION
We evaluate the performance of the router against the oracle supervision and show that the router learnt using the procedure described in Sec. [2. generalizes well. For instance, while training hybrid model with pre-trained MBV33 and MBV3 V-V3ee models, on the oracle labels, the router achieves a training aceuracy of 87% and this translates into a validation accuracy of es 84%. In contrast, entropy thresholding the validation dataset achieves ~ 77% accuracy on the oracle labels.
A.11.3 IMDB EXPERIMENTS
We also learn hybrid model in the NLP domain. We train a sentiment classifier on the IMDb dataset Maas al. (20TT). We pick-up off-the-shelf pre-trained classifiers, namely (a) albert-base-v/ Lan et al. (2019) (11M params, 91 % accuracy) as the base and (b) bert-large Devlin et al. (2018) (340M params, 96% accuracy) the glohal. We use the hidden state from the last timestep in the sequence along with the classifier logits and entropy as the feature for the routing model. In order to save computation, we learn the hybrid model by training only the router. Table 13 shows the performance of the hybrid models and the entropy thresholding baseline at various coverage levels. It shows that hybrid models provide similar benefits on IMDb dataset. We note that, for further model footprint reduction, similar hybrid models can be constructed using efficient recurrent neural networks Kag et al. (2020); Kag & Saligrama (2021) as the base model and large transformer models as the global model.
Table 13: Hybrid models for IMDb various coverages.
Base
Base Cov.=97%
Cov.=95% Cov.=93%
MAC' Acc.(%)
Acc. (%)
Acc. (%) Acc. (%)
Entropy 91
93.78
94.38
95.25
Hybrid
91
94.31
95.45
96.01
A.11.4 MCUNET EXPERIMENT WITH EFFICIENTNET-B7
In the main text, due to limited compute resources, we restricted our global model be the MASS- 600 Cai et al. (2020) model. In this ablation, we explore the effect of deploying significantly expensive model on the cloud. We choose the best performing model the EfficientNet Tan & Le (2019) family, i.c., EfficientNet-B7. This model has 37B MACs and stores 66M network parameters. We borrow the implementation from the timm repository that achieves an accuracy of 86.5% on the Imagenet classification task. In contrast, the MASS-600 model has 600M MACs, 9. 1M parameters and achieves x 80% accuracy. For simplicity, we assume the cloud resources render the inference on EfficientNet-B7 to be similar MASS-60X In this experiment, MCUNet base used in the Sec. Thus, we can compare the performance of the hybrid models across different global models. Table 14 compares the accuracies obtained by the hybrid models with two different global models (MASS-60 600 and EfficientNet-B77 It clearly shows the following benefits:
train hybrid-r model with
Deploying a better global model improves the hybrid performance and with cloud resources such large models do not affect the energy consumption on the edge device. Assuming that the cloud has access to large compute pool, the inference latency on the edge device does not suffer as well.
*FfficientNet- BiteciientettB--nnn model from http:////tttccccooo/omaaamoomome
23

---

Published as a conference paper at ICLR 2023
It shows that our algorithm procedure to train hybrid models works across global models in different architecture families. Table 14: EtticientNet-Bi B7 Global model: Hybrid models STM32F746 MCU: Accuracy achieved by different methods at various latency constraints. Base model is the MCUNet model with 12M MACs and 200ms latency.
Accuracy (%) at Latency (ms)
Method
200
600
1000
1400
1600
2000
On-Cloud (MASS-600)
79.9
On-Cloud (EfficientNet-B77)
86.5
On-Device
51.1
60.9
63.5
Hybrid (Global=MASS-600))
62.3
71.2
77.9
79.5
Hybrid (Global-EEfficiemNeeeB777
64.9
76.2
82.8
85.7
A.12 SOCIETAL IMPACT AND LIMITATIONS
Edge devices offer range of predictive services to end users. Often times, these services require access to cloud resources to guarantee sate-of--the-ass performance as the edge-deployable model is very restrictive. Such cloud interaction has many downsides, including (a) increased inference latency, (b) increased battery usage on edge, (c) additional cost for cloud resources, (d) end user privacy concerns, and (e) increased carbon footprint due to cloud usage.
The proposed hybrid design aims to address these issues in the existing on-cloud solutions by only selectively querying the cloud on inputs that are hard to classify locally. Our proposal engages the cloud only when is sufficiently confident that the cloud usage would result in correct classification. As result, it increases the coverage, i.e., the number of inputs locally predicted by the base model without invoking the cloud model. Thus, the overall cloud utilization is reduced significantly as seen from our empirical evaluations. Note that, in the worst case, when the input is hard to predict locally, the router engages the cloud and gets hit with on-cloud latency.
Our hybrid design, much as possible, helps the existing predictive services to selectively querying the cloud. As a result, we get the following benefits as compared to the existing on-cloud solutions:
1. Decreased inference latency on the edge device due to communication delay
2. Decreased battery/energy usage on the edge device due to data transmission Reduced cost for access cloud resources
4. Reduced carbon footprint due to less resource usage
End user privacy concerns are addressed in two ways. First, by selectively querying the cloud, only a small fraction of data is sent to the cloud. Second, hybrid design allows the base model to operate as the abstaining classifier and in the process enables the practictioners to ask for user consent by showing the base model prediction and router confidence in those predictions. Such design gives the users informed consent on whether they are satisfied with the inference results or they would like to send the data to cloud as their local models are unable to correctly classify the inputs.
A.13 DYNAMIC COMMUNICATION LATENCY
Although our setup in Figure 2 assumes a constant communication latency, we can easily modify the setup incorporate dynamic latency delay. Assuming the base processing latency B, global processing latency G, communication delay D, and router coverage C, we can use the following constraint on the coverage C' achieve a target average latency L,
B + (1 C) * (D G) L
As per the main text, B = 200ms, G 25ms and the communication delay D = 2000ms. In case the communication delay has a high variation and ranges between [Dmin Dmax] we can store a lookup table on the edge device use different coverage threshold for different observed latency, by solving the above constraint at pre-defined communication delay intervals.
For the illustrative example, we simulate this setting by drawing communication latencies uniformly at random between [Dmin: D maax] Figure ( the dynamic communication with the constant communication cost setting. It has three dynamic ranges [200, 2000), [1000, 3000], 1500,3500),
24

---

Published as a conference paper at ICLR 2023
where the last two range keep the mean communication cost the constant setting. It can be clearly seen that proposed hybrid models outperform all the baselines in each setting.
80
Giobal
80
Global
les Accuncyyss
Imageener topa Accurscyy)))
70
70-
60
80
On-Cloud
On-Davice
Dynamic Natworks
On-Cloud
Spltt Computation
Dynami--Nuterks Networks
Splt-Compucation
Base
Upoor-Bound
Bose
Hybric
1000
Lakancy (ms)
inforence Latancy (ms)
(b)
80
Global
80-
Global
Accunacyy)))
70
70-
00
00
Dynamic Networks
Dynamic Networks
Spltt Computation
Spiit Computation Hybric
250
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
(ms)
inference (ms)
(c)
(d)
Constant Communication Latency (b) Dynamic Communication latency [400, 2400] (c) Dynamic Communication latency [1000, 3000] (d) Dynamic Communication latency [500, 3500]
Figure 7: Sctup is same Figure 2
14
03
(a)
(b)
(c)
Figure Algorithm Convergence. We show the training losses three components the Algorithm (a) router, (b) base, and (c) global model.
A. ALGORITHM CONVERGENCE ANALYSIS
In this ablation, we show that the Algorithm I for training hybrid models convergences empirically. We pick up the base and global model deseribed in the setup in the Figure We plot the training losses for the three components (router, base, global models) in the Figure [ It shows that base and global models convergence stable loss towards the end of the training cycle.
25


Reviews:
[{"review_id": "t7HKjVzoaH", "reviewer": "Reviewer_TiF9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a novel hybrid design where an edge-device selectively queries the cloud only on those hard instances that the cloud can classify correctly to optimize accuracy under latency and edge-device constraints. An end-to-end method to train neural architectures, base predictors, and routing models is also proposed which is enabled by a novel proxy supervision for training routing models.", "summary_of_the_review": "A clear article with simple yet relatively effective methods to solve the efficiency and accuracy dilemma of edge and cloud DNN execution. Would be great if the authors could provide more novelty and improvements justification.", "strength_and_weaknesses": "Strength:\n\n1. The paper provide a clear illustration of their methods and especially the comparison with the existing approaches.\n2. The experiments are setup solidly and the covered settings and the metrics are comprehensive \n\nWeakness: \n1. According to Figure 2, improvements over dynamic methods may not be good enough to justify the significance\n2. Limited novelty: alternating optimization to solve the coupled optimized parameters seem to be mentioned before by some works, such as [1] and [2]. And anyway it seems to be an intuitive approach.\n\n[1] Auto-NBA: Efficient and Effective Search Over the Joint Space of Networks, Bitwidths, and Accelerators\n\n[2] A3C-S: Automated Agent Accelerator Co-Search towards Efficient Deep Reinforcement Learning", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GcL-2aOy7H2", "reviewer": "Reviewer_XmVX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a supervised training framework to improve the classification model inference in edge-cloud cooperating scenarios. The framework utilizes pre-trained models to achieve labelization for the router model under the criteria that the samples that should be transferred to the cloud are cases in which local models fail. Moreover, the authors also utilize the trained router model to re-balancing the importance of samples for classification models on cloud and device. Optimizing the router model and classification are conducted jointly to improve each system component. Extensive experimental results on benchmarks demonstrate the outperformance of SOTA.\n\n", "summary_of_the_review": "This paper applies a data-based mixture of expert method on edge-cloud computing scenarios. The main contribution is that the mixture is conducted by data, simultaneously solving the model selection and improvement. Although some details require a more delicate design and the current approach is limited to the classification scenario, the proposed alternative training framework may facilitate delicate and in-depth investigations in the future.\n\n", "strength_and_weaknesses": "Strength:\n1. The proposed criteria for label construction for router training is reasonable and efficient. The criteria exclude corner cases in which cloud and device models fail.\n2. The joint training of models on cloud and local devices is impactful. Besides training a router to deliver a sample, the authors find that training each model (on a cloud or local device) can also benefit from such a router. This resolution leads a jointly trained base model to outperform an individually trained one experimentally, even with some abstaining.\n3. The paper is well-organized. The authors highlight the proposed scheme and provide several model structure optimization solutions.\n4. The experiments in this work are sufficient. \n\nWeakness:\n1. The metric used for the \"routing model\" is unavailable for regression tasks. The metric includes a strict equivalence evaluation between labels and predictions to identify the target execution platforms. However, the equivalence is unavailable in regression.\n2. The upper bound accuracy calculation is unreasonable. First, the proportion $\\frac{1 − c}{1 − a_b}$ in the formulation of upper bound accuracy is weird. Due to loss function in Eq (7), if optimality holds, $P(r(x) = 0)$ should be equal to $c$. Due to Eqn (1) and related statements, the upper bound should be $c a_b + (1-c)a_g$ since execution on device and cloud are complementary. Furthermore, the authors assume that accuracies on cloud and local devices are unchanged. However, this is unsustainable since distributions change in the proposed hybrid training framework. For example, the loss functions for device and cloud under Eqn (7) erase some samples for both.\n3. Some conclusions in the method section lack theoretical or experimental demonstrations. For example, there is no convergence demonstration of proposed algorithm 1. In the loss functions for cloud and device, several experiments to demonstrate the effectiveness of these \"hard masks\" will make it more reasonable.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ALyJMPjFiN9", "reviewer": "Reviewer_q8G9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an advanced two-stage inference strategy to reduce resource usage and communication cost. The key idea is that 1) use different edge and cloud models, 2) jointly train the router module, and 3) control the cost during training, dependent on the target environment. As a result, the proposed method achieves near-upper-bound performance in diverse resource constraints.", "summary_of_the_review": "Overall, the paper tries to solve an important and practical issue. The proposed method is novel, and the experimental results support the claim sufficiently. I believe this paper is helpful for both research and production areas.", "strength_and_weaknesses": "Strengths:\n- The proposed framework works end-to-end, including the routing module. Especially, the routing module is trained via proxy supervision (using oracle), which is a clever way to incorporate all modules in the training.\n- Experiments are carefully designed and performed. More importantly, actual MCU systems are used for the evaluation. “Hybrid accuracy” seems to be a good metric for these two-stage inference systems.\n- Previous approaches (split-computation, dynamic network, early exit, etc.) are thoroughly studied and compared. \n\nWeaknesses:\n- Minor: what if the global model fails to predict correctly? It seems that the overall process assumes the global model is always better than the local model.\n- Just a question; doesn’t the communication cost dependent on the model size, resolutions, etc.? It seems that such cost is somewhat fixed through the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "7GlhIo_w7R", "reviewer": "Reviewer_YaHL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes using a shallow network to route a subset of samples from the edge device to a remote server. The router, edge, and server models are trained jointly but iteratively. ", "summary_of_the_review": "Given that the evaluations only support latency-sensitive applications, but the optimization goal is not aligned with latency-sensitive systems, I think the paper can be more interesting for the systems community if it addresses either of the issues.  ", "strength_and_weaknesses": "Strengths:\n- The paper is well-organized.\n- Efficient inference on edge devices is a timely topic. \n- The idea of not sending the data to the server if it's not going to bring any improvement sounds interesting. \n\nWeaknesses:\n- Using average latency as an inference system metric here seems a bit unnatural to me. Controlling for the \"average\" latency is equivalent to maintaining the average sample throughput of the system. In the case of controlling for throughput, the batching mechanisms become quite effective: collect a batch of samples at the edge for T seconds, compress them as much as possible (even jointly if they have temporal correlation), and upload them to the server to be efficiently batch-processed by the server-class GPU. However, given the evaluations, I think the paper is not focusing on this regime of designs. On the other hand, in latency-sensitive applications, we are actually concerned about the \"tail\" latencies instead of the average. In that case, the proposed approach cannot provide fine-grained control over the metric of interest (tail latency): you are either going over the network with a 2sec delay or processing locally. For example, if we need a sub-second latency guarantee, the system cannot go over the network at all, and if we go for a 2.5sec latency guarantee, the system will process everything on the remote server. \n- How does this work relate to the Mixture of Experts literature? Can we think of r as the gating network and b and g as two experts with different sizes? How does your performance compare against training such an MoE but only running the expert that is hard-selected by the gating network?\n- \"We are the first to provably reduce router learning to binary classification and exploit it for end-to-end training based on novel proxy supervision of routing models.\" This contribution might be a little bit overstated. For example, have you seen the routing section in [1]?\n\n[1] Riquelme, C., Puigcerver, J., Mustafa, B., Neumann, M., Jenatton, R., Susano Pinto, A., Keysers, D. and Houlsby, N., 2021. Scaling vision with sparse mixture of experts. Advances in Neural Information Processing Systems, 34, pp.8583-8595.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster