#  SuperServe: Fine-Grained Inference Serving for Unpredictable Workloads

Alind Khare  Georgia Tech  Dhruv Garg  Georgia Tech  Sukrit Kalra  UC Berkeley
Snigdha Grandhi∗ Work done as a student at Georgia Tech Adobe  Ion Stoica  UC
Berkeley  Alexey Tumanov  Georgia Tech

###### Abstract

The increasing deployment of ML models on the critical path of production
applications in both datacenter and the edge requires ML inference serving
systems to serve these models under unpredictable and bursty request arrival
rates. Serving models under such conditions requires these systems to strike a
careful balance between the latency and accuracy requirements of the
application and the overall efficiency of utilization of scarce resources.
State-of-the-art systems resolve this tension by either choosing a static
point in the latency-accuracy tradeoff space to serve all requests or load
specific models on the critical path of request serving.

In this work, we instead resolve this tension by simultaneously serving the
entire-range of models spanning the latency-accuracy tradeoff space. Our novel
mechanism, SubNetAct, achieves this by carefully inserting specialized
operators in weight-shared SuperNetworks. These operators enable SubNetAct to
dynamically route requests through the network to meet a latency and accuracy
target. SubNetAct requires upto $2.6\times$ lower memory to serve a vastly-
higher number of models than prior state-of-the-art. In addition, SubNetAct’s
near-instantaneous actuation of models unlocks the design space of fine-
grained, reactive scheduling policies. We explore the design of one such
extremely effective policy, SlackFit and instantiate both SubNetAct and
SlackFit in a real system, SuperServe. SuperServe achieves $4.67$% higher
accuracy for the same SLO attainment and $2.85\times$ higher SLO attainment
for the same accuracy on a trace derived from the real-world Microsoft Azure
Functions workload and yields the best tradeoffs on a wide range of extremely-
bursty synthetic traces automatically.

##  1 Introduction

Recent advancements in machine-learning (ML) techniques have unlocked vast
improvements in both accuracy and efficiency of a variety of tasks such as
image classification [38], object detection [8, 3], text summarization [16],
sentiment analysis [29], next word prediction [47] etc. As a result, ML models
have been quickly deployed across a wide-range of applications in both
datacenters [61, 46, 41, 23, 37] and on the edge [4, 39, 17, 33], and are now
subject to the stringent requirements of a production application.

Notably, ML models on the critical-path of these applications must now deal
with _unpredictable_ request rates that rapidly change at a sub-second
granularity. For example, web applications in datacenters increasingly rely on
ML models [61, 46], and are known to have extremely bursty request rates, with
a peak demand that is $50\times$ higher than the average [32]. Similarly,
request rates in autonomous vehicles change rapidly as a function of various
factors such as the terrain (city vs. freeway driving), time of the day etc.
[17].

Thus, ML inference serving systems have the arduous task of striking a careful
balance between three key requirements of production applications facing
unpredictable request rates:

R1: Latency. ML models are being increasingly deployed in applications that
have extremely stringent latency requirements, quantified using a Service-
Level Objective (SLO) [31]. For example, both web serving [46, 41, 22] in
datacenters and autonomous vehicles [17, 33] on the edge must maximize the
number of requests completed within the specified SLO ranging from 10s to 100s
of milliseconds [17, 59].

R2: Accuracy. Techniques such as Neural Architecure Search (NAS) [48, 62, 5]
have enabled the development of multiple ML models that offer varying
accuracies for a particular task. As a result, applications demand the
highest-accuracy results possible within the latency targets of their
requests. For example, increased accuracy has been intricately tied to a
better user experience for web applications [54, 23]. Similarly, the safety of
an autonomous vehicle heavily relies on the accuracy of various different ML
models [17, 18].

R3: Resource-Efficiency. Web applications at Facebook process $200$ trillion
ML model requests daily [51], which represents a significant fraction of
Facebook’s datacenter demands [41]. In addition to the increasing
proliferation of ML models, their growing reliance on scarce resources such as
GPUs and specialized accelerators (e.g, TPUs [1], AWS Inferentia [2]) for
efficient inference has lead to resource tensions across applications in both
datacenters and on the edge [39]. Thus, inference serving systems that serve a
wide range of ML models must make judicial use of these scarce resources.

The first-generation of inference serving systems [11, 37, 10, 30, 36, 22, 59]
resolves this tension by choosing a static point in the tradeoff-space between
R1-R3 and serving all requests using the same model for the entirety of the
application’s runtime. As a result, applications must make a one-time decision
to forego meeting their SLO targets (R1) under bursty request rates or suffer
degraded accuracy (R2) under normal conditions. More recently, state-of-the-
art inference serving systems [42, 60] enable applications to register
multiple ML models spanning the entire pareto frontier of latency (R1) and
accuracy (R2) targets, and _automatically_ choose the appropriate model to
serve requests based on the incoming request rates. These systems must either
keep the entire set of models in memory or rely on _model switching_
techniques to load the required models at runtime [60]. As GPU memory remains
the key resource bottleneck in both datacenter and edge inference serving [32,
39], these systems must now choose between R3 – effectively utilizing the
available resources (by incurring the enormous latency penalties of switching
models), or R1 – meeting SLO targets under highly unpredictable request rates.

Conventional wisdom in inference serving literature touts the “ _non-
negligible provisioning time_ [for ML models due to switching], _which can
exceed the request processing times_ " as a “ _key characteristic of ML
workloads_ ", and "_rules out reactive techniques_ " for responding to bursty
request rates [21]. This wisdom has been widely accepted [42, 11, 22] leading
to the development of coarse-grained scheduling policies for inference serving
that must account for the enormous latency penalty of switching models when
reacting to bursty request rates. As a result, these coarse-grained policies
typically avoid or minimize switching models by design [42], and are hence,
unable to optimally navigate the tradeoff space between R1-R3 under rapidly-
changing, unpredictable request rates.

In this work, we challenge this conventional wisdom that forces a choice
between R1 and R3. We describe a mechanism, SubNetAct, to simultaneously serve
the entire range of models spanning the latency-accuracy tradeoff space
(R1-R2) in a resource-efficient manner (R3). At the core of our mechanism are
novel control-flow and slicing operators that SubNetAct carefully inserts into
the SuperNet [6, 44] neural architectures. SuperNets enable a latency-accuracy
tradeoff (R1-R2) by training a set of shared model weights for many neural
networks, without duplication. Prior works [6, 44] propose efficient
mechanisms for training SuperNets for both vision and NLP tasks, but require
each model instance to be individually extracted for inference, leading to a
similar choice as before between R1 and R3 – either load all individual models
or switch between them at runtime. However, SubNetAct’s novel operators
obviate the need to extract individual models and load them dynamically at
runtime. Instead, SubNetAct dynamically routes requests within one SuperNet
deployment with negligible overhead, enabling near-instantaneous _actuation_
of different models. As a result, SubNetAct unlocks orders of magnitude
improvements in the navigation of the latency-accuracy tradeoff-space (R1-R2),
while substantially reducing the memory footprint (R3) (see Section 2.2).

In addition to being resource-efficient (R3), SubNetAct’s agility in
navigating the latency-accuracy tradeoff space (R1-R2) fundamentally changes
the design space of scheduling policies. Instead of complex scheduling
policies that must reason about future request rates in a bid to avoid paying
the latency of switching ML models dynamically under bursts, SubNetAct enables
the specification of simple policies that directly optimize for the key
success metrics R1-R3. While conventional wisdom deems such reactive policies
infeasible, we explore one example point in this design space with a simple,
yet effective policy that we call SlackFit. SlackFit is a reactive scheduling
policy that exploits the near-instantaneous actuation property of SubNetAct to
make fine-grained decisions about how many requests to serve in a batch, and
which latency/accuracy choice to select for serving in real-time.

We summarize the contributions of this paper as follows:

  * $\bullet$

We introduce SubNetAct (Section 3.1), a novel mechanism that enables a
resource-efficient, fine-grained navigation of the latency-accuracy tradeoff
space. SubNetAct achieves this by carefully inserting novel control-flow and
slicing operators that dynamically route requests through a single SuperNet.

  * $\bullet$

We unlock the design space of fine-grained, reactive scheduling policies and
provide a mathematical formulation of their objective (Section 4.1). We then
propose SlackFit (Section 4.2), a simple, yet effective greedy heuristic and
show how it accurately approximates the optimal objective.

  * $\bullet$

We instantiate SubNetAct and SlackFit in a real-world system, SuperServe, a
real-time asynchronous model serving system with pluggable scheduling policies
(Section 5).

  * $\bullet$

We extensively evalute SuperServe with both SlackFit and several state-of-the-
art scheduling policies (Section 6). We find that SuperServe achieves $4.67$%
higher accuracy for the same SLO attainment and $2.85\times$ higher SLO
attainment for the same accuracy on the real-world Microsoft Azure Functions
trace.

##  2 Motivation and Background

(a) Model switching is expensive

(b) Coarse-grained scheduling

(c) Fine-grained scheduling

Figure 1: Fine-grained scheduling policies are beneficial. (a) The latency of
loading ResNet-18,34,50,101,152 [24], Wide-Resnet-101 [58] and ConvNeXt-Large
[35] is greater than its inference latency with a batch size of 16, making
model switching expensive. This gap widens as model sizes increase. (b) A
bursty request rate from the MAF [45] trace with a coarse-grained scheduling
policy leads to 2% of the requests missing their SLO (R1) and wasting
resources (R3) due to a $100$ms actuation delay typical of model switching
techniques. (c) A bursty request rate with a fine grained scheduling policy
that can switch models instantaneously can achieve 0% SLO misses and
effectively utilizes the GPU.

In Section 2.1, we motivate the development of a reactive, fine-grained
scheduling policy that maximizes R1-R3 under unpredictable, bursty request
rates. Section 2.2 then provides a background on Supernets [6, 44] and
discusses the properties of Supernets relevant to R1-R2 that make them a good
fit for a fine-grained exploration of the latency-accuracy tradeoff.

###  2.1 Fine-Grained Reactive Scheduling

Prior works in inference serving systems [59, 32] have exhaustively analyzed
both production traces from Microsoft Azure Functions (MAF) [45] and synthetic
application traces with a goal of highlighting their bursty request arrival
patterns. For example, Zhang et al. [59] underscore the high coefficient of
variance in request arrivals in production traces [45]. Further, the authors
claim that the bursty “ _sub-second request arrival patterns_ [are] _nearly
impossible to predict_ ", thus frustrating the goal of meeting the stringent
SLO requirements of requests in an ML-based production applications.

A strawman solution to fulfilling SLOs under bursty request rates requires
inference serving systems to provision for the peak. In this setting, these
systems load the entire set of models spanning the latency-accuracy tradeoff
space into GPU memory and switch between them as request rate fluctuates.
While this reduces the actuation latency of switching models, allowing
inference serving systems to rapidly degrade accuracy (R2) under bursts to
meet SLO targets (R1), it wastes resources under normal request rates (R3).

As a result, state-of-the-art inference serving systems [60, 42] rely on model
switching techniques that page models in and out when required, to make
efficient use of GPU memory (R3). However, as we show in Fig. 1(a), the
loading time of ML models from CPU to GPU memory is vastly more than the
inference time of the biggest batch size, and the gap widens as the model
sizes increase. Thus, in a bid to offset the cost of loading models on the
critical path of handling requests, inference serving systems rely on
_predictive_ scheduling policies that make coarse-grained estimations of
future request arrival patterns. Such policies are bound to be suboptimal
owing to the difficulty of predicting the short bursts in request arrival
rates coupled with their stringent SLO requirements [59].

We believe that the key to optimally serving bursty request rates instead lies
in the ability to rapidly switch between ML models thus obviating the need for
coarse-grained predictive scheduling policies. To validate our hypothesis, we
simulate a coarse-grained policy with an actuation delay (i.e., time taken to
switch to a new ML model that can handle the current request rate) of $100$ms
and an idealistic fine-grained policy with an actuation delay of $0$ms. Figs.
1(b) and 1(c) plot the effects of these policies on a small bursty subtrace
from the MAF trace. We observe that the coarse-grained policy leads to higher
SLO misses (R1) under increasing request rates and wasted resources (R3) under
decreasing request rates. On the other hand, the fine-grained policy is able
to instantaneously adjust to the increasing and decreasing request rates
leading to no missed SLOs and effective utilization of the GPU.

Figure 2: Supernets provide better latency-accuracy tradeoff. The accuracy
(R2) of subnets individually extracted from OFAResNet supernet [6] is vastly
superior to the hand-tuned ResNets from Fig. 1(a) for the same FLOP
requirements (R1).

###  2.2 Weight-Shared Supernets

The problem of navigating the pareto-optimal frontier of the latency-accuracy
tradeoff space (R1-R2) by finding highest accuracy DNNs for a specific latency
target is well studied in ML literature. Conventional Neural Architecture
Search (NAS) [63, 62, 48, 7, 34] approaches have enabled architectures
tailored to a particular latency target. However, these approaches search for
and train individual networks for a particular latency target and hence
require inference serving systems to either load all of them into memory and
waste resources (R3), or switch between them at runtime.

Instead, recent works [6, 44] have proposed first training one _supernet_ and
then extracting a subset of its layers to form _subnets_. As a result, once
the supernet is trained, no further retraining is required for a specific
subnet. Each extracted subnet targets a specific point in the latency-accuracy
tradeoff space, and partially shares its weights/layers with other subnets. In
addition, this automated neural architecture search (NAS) yields subnets that
correspond to vastly superior points in the latency-accuracy tradeoff space
(R1-R2). For example, Fig. 2 highlights the accuracy benefits of subnets
extracted from a ResNet-based supernet when compared to the hand-tuned ResNets
for an equivalent number of FLOPs.

In order to find subnets that target a particular point in the latency-
accuracy tradeoff space, the architecture search in supernets relies on the
following parameters: \- (i) Depth ($\mathbb{D}$) describes the depth of a
subnet, (ii) Expand Ratio ($\mathbb{E}$) describes layer-wise ratio of output
to input channels of a convolution or fully-connected layer, and (iii) Width
Multiplier ($\mathbb{W}$) describes layer-wise fraction of input and output
channels to be used. These parameters ($\mathbb{D}$, $\mathbb{E}$,
$\mathbb{W}$) combinatorially create an architecture space, $\Phi$
($|\Phi|\approx 10^{19}$) [6], from which individual subnets are extracted
_statically_ for inference.

##  3 SubNetAct: Instantaneous Model Actuation

Motivated by Section 2.1, we seek to develop a fine-grained, reactive
scheduling mechanism that enables efficient execution of ML-based production
applications (R1-R3) under bursty request rates. As discussed in Section 2.2,
prior work in supernets [6, 44] enables the extraction of individual models
that target a specific point in the latency-accuracy tradeoff space (R1-R2).
However, these approaches yield individual models that must either be
simultaneously deployed (wasting resources; R3) or paged in as request rates
fluctuate (missing SLOs; R1).

To resolve this fundamental tension, we make the key observation that by
virtue of performing architectural search _post_ training, a supernet subsumes
the entire architectural space of subnets. As a result, instead of extracting
and deploying individual subnets (as done previously), we can instead deploy a
supernet and _dynamically route_ requests to the appropriate subnet. This
observation leads us to introduce SubNetAct, a memory-efficient model
_actuation_ mechanism (R3) that exposes fine-grained control decisions to
near-instantaneously switch between subnets in order to pick the optimal point
in the latency-accuracy tradeoff space (R1-R2).

Figure 3: SubNetAct’s novel operators (LayerSelect, SubnetNorm, WeightSlice)
dynamically actuate subnets by routing requests through weight-shared layers
and non-weight-shared components.  Figure 4: SubNetAct’s memory savings. The
memory used by the normalization statistics is $500\times$ smaller than the
non-normalization layers. SubnetNorm decouples the normalization statistics
for each subnet and provides accurate bookeeping thus enabling high accuracy
(R1), with minimal increase in memory consumption (R3).

SubNetAct’s (Fig. 3) key insight lies in the introduction of the following
three novel operators that enable it to dynamically route requests to the
required subnet in a supernet:

(a) Reduced Memory Requirements.

(b) Instantaneous Model Actuation.

(c) High dynamic throughput range.

Figure 5: Efficacy of SubNetAct. (a) SubNetAct requires upto $2.6\times$ lower
memory to serve a higher-range of models when compared to the ResNets from
Fig. 1(a) and six individual subnets extracted from supernet [6] (b) SubNetAct
actuates different subnets near-instantaneously ($<1$ms), which is orders of
magnitude faster than the model switching time. (c) SubNetAct enables
instantaneous actuation of models that can sustain higher ingest rates thus
inducing a wide dynamic throughput range ($\approx 2-8k$ queries per second)
and increased accuracy.

LayerSelect. SubNetAct takes as input the depth $\mathbb{D}$, and dynamically
executes layers of a specific subnet based on $\mathbb{D}$. The depth
$\mathbb{D}$ is converted by SubNetAct to per-layer boolean values that
determine which layers participate in inference. SubNetAct then wraps each
layer in a LayerSelect operator that enforces control-flow by either passing
the input activation to the wrapped layer or skipping the layer and directly
forwarding input to the next layer. This operator enables layer-sharing among
subnets that differ in depth ($\Phi_{\mathbb{D}}\subset\Phi$), which reduces
the GPU memory consumption of the supernet (R3). Moreover, it enables near-
instantaneous (R1) switching of the supernet’s accuracy (R2) under bursty
request rates.

SubnetNorm. We observe that naively introducing the LayerSelect operator leads
to a significant drop in subnet accuracy (as low as $10$%). This is due to the
incorrect tracking of the mean ($\mu$) and variance ($\sigma$) in
normalization layers such as BatchNorm [27]. To account for this discrepancy,
SubNetAct introduces the SubnetNorm operator that precomputes and stores $\mu$
and $\sigma$ for each possible subnet by performing forward pass inference on
the training data. SubnetNorm takes as input a unique subnet ID ($i$) and a
layer ID ($j$) and outputs the precomputed normalization statistics
$\mu_{i,j}$ and $\sigma_{i,j}$. The layer $j$ then uses the provided
statistics to perform normalization of activations, effectively specializing
$j$ for each subnet $i$.

Although this bookkeeping increases the memory requirements of deploying the
supernet, Fig. 4 shows that the overhead of these non-shared normalization
statistics is $500\times$ smaller than the memory requirement of the shared
layers. As a result, SubNetAct can host thousands of subnets in memory by only
keeping the statistics unique to each subnet and sharing the non-normalization
weights amongst all the subnets.

WeightSlice. This operator dynamically selects channels in convolution or
fully-connected layers during inference. The input to WeightSlice is the
expand ratio ($\mathbb{E}$) or width multiplier ($\mathbb{W}$) for each layer,
which collectively determine the number of channels to be used. The operator
outputs layer-specific channel indices, which are then used to select weight
subsets for the forward pass inference. The operator enables partial layer-
sharing among subnets
($\\{\Phi_{\mathbb{E}}\cup\Phi_{\mathbb{W}}\\}\subset\Phi$), thus increasing
the number of available subnet architectures. As a result, SubNetAct is able
to provide the entire set of latency-accuracy options (R1-R2) to the
scheduling policies.

We note that the input to these operators (i.e., depth ($\mathbb{D}$), expand
ratio ($\mathbb{E}$) and width multiplier ($\mathbb{W}$)) remains similar to
the inputs for architectural search in ML literature [6]. Moreover, these
control inputs are independent from the input to the actuated subnet (i.e.,
the request served by the model), and are declaratively specified by a
scheduling policy (Section 5). Given the arrival rate, the scheduling policy
chooses a specific subnet for a request (by specifying the control tuple
$\mathbb{D}$, $\mathbb{E}$ and $\mathbb{W}$), which is then actuated by
SubNetAct near-instantaneously.

###  3.1 Discussion: Efficacy of SubNetAct

We now highlight SubNetAct’s efficacy in achieving key application
requirements (R1-R3) under bursty request rates.

Reduced Memory Requirements. SubNetAct’s novel operators enable subnets to
share layers in place and dynamically route requests to the appropriate subnet
based on the control tuple $\mathbb{D}$, $\mathbb{E}$ and $\mathbb{W}$
determined by a scheduling policy. As a result, SubNetAct can simultaneously
serve the entire range of models spanning the latency-accuracy tradeoff space
while drastically reducing memory requirements. Fig. 5(a) demonstrates this by
comparing the memory requirement of loading four different ResNets [24], six
individually extracted subnets [6], and SubNetAct that enables simultaneous
actuation of $500$ subnets. We observe that SubNetAct can reduce memory
consumption by upto $2.6\times$, while vastly increasing the latency-accuracy
tradeoff points that can be actuated.

Near-Instantaneous Model Actuation. While switching between individual models
requires loading their weights to the GPU, SubNetAct’s operators enable
scheduling policies to actuate any subnet in place without incurring
additional loading overhead. Fig. 5(b) compares the time taken to perform on-
demand loading of individual subnetworks versus in-place actuation of a subnet
in SubNetAct. We observe that SubNetAct’s model actuation is orders-of-
magnitude faster than on-demand loading of ML models. This allows scheduling
policies that use SubNetAct to rapidly actuate lower-accuracy models under
bursty conditions (R1) and switch to higher-accuracy models under normal load
(R2), without coarse-grained predictions about future request rates.

Increased Throughput & Accuracy. By providing instant model actuation,
SubNetAct allows scheduling policies to scale the throughput of the system up
and down rapidly, thus inducing a broad throughput range within as few as 6%
of accuracy to help meet SLO guarantees (R1-R2). Fig. 5(c) compares the
maximum sustained ingest throughput for a point-based open-loop arrival curve
for serving the largest, smallest, and a median subnetwork on 8 SubNetAct
workers. We observe that SubNetAct can serve a wide throughput range from
$2000$-$8000$ QPS, while being able to instantaneously increase accuracy
between $74\%$ to $80\%$.

##  4 Fine-Grained Scheduling Policies

SubNetAct’s near-instantaneous actuation of the entire latency-accuracy
tradeoff space unlocks the development of extremely fine-grained scheduling
policies that can directly optimize for R1-R2. We note that by virtue of
aggressively sharing weights/layers and dynamically routing requests within a
supernet, SubNetAct automatically maximizes resource efficiency (R3). In this
section, we first start with the problem formulation of online serving for the
new space of fine-grained policies enabled by SubNetAct (Section 4.1). We then
describe our proposed policy SlackFit that aims to achieve both high accuracy
and latency SLO attainment (Section 4.2).

###  4.1 Problem Formulation

SubNetAct hosts a set of all possible subnets $\Phi$, where each subnet
$\phi\in\Phi$ is defined by the control tuple $\mathbb{D}$, $\mathbb{E}$,
$\mathbb{W}$ and has an accuracy $Acc(\phi)$ and a latency-profile
$l_{\phi}(B)$ as a function of batch-size $B$. A _query_ 111We use the term
_query_ and _request_ interchangeably. $q$ arrives to the scheduler at time
$a_{q}$ with an SLO $d_{q}$. A fine-grained scheduling policy focuses on
selecting a subnet across supernets for queries across GPUs, along with a
batch $B$ to execute the query in [11, 22]. The arrival time $a(B)$ of $B$ is
the earliest arrival time and the deadline $d(B)$ is the earliest deadline of
all queries in $B$. $\mathcal{B}$ is the set of all possible batches of
queries. The policy decides if $B\in\mathcal{B}$ should execute at time $t$
using subnet $\phi$ on GPU $n$, which is captured by a decision variable
$I(B,t,n,\phi)\in\\{0,1\\}$.

Goal. The policy’s goal is to maximize the number of accurate responses (to
queries) within specified SLO (R1-R2).

Optimal Offline ILP. We now present the ILP formulation of a scheduling policy
that achieves our stated goal with an oracular knowledge about future query
arrivals:

$\text{maximize}\sum_{t}\sum_{n}\sum_{\phi\in\Phi}\sum_{B\in\mathbb{B}}\text{Acc}(\phi)\cdot|B|\cdot
I(B,t,n,\phi)$ (1)
$\text{s.t.}\sum_{t}\sum_{n}\sum_{\phi\in\Phi}\sum_{\\{B|q\in\mathbb{B}\\}}I(B,t,n,\phi)\leq
1,\;\;\;\;\;\;\;\forall q$ (1a)
$\sum_{B\in\mathbb{B}}\sum_{\\{t^{{}^{\prime}}\leq t\leq
t^{{}^{\prime}}+l_{\phi}(B)\\}}I(B,t^{{}^{\prime}},n,\phi)\leq
1,\;\;\;\;\;\;\;\forall n,t,\phi$ (1b) $a(B)\cdot I(B,t,n,\phi)\leq
t,\;\;\;\;\;\;\;\forall n,t,B,\phi$ (1c) $\sum_{\phi\in\Phi}I(B,t,n,\phi)\leq
1,\;\;\;\;\;\;\;\forall n,t,B$ (1d) $\sum_{\phi\in\Phi}(l_{\phi}(B)+t)\cdot
I(B,t,n,\phi)\leq d(B),\;\;\;\;\;\;\;\forall n,t,B$ (1e)
$I(B,t,n,\phi)\in\\{0,1\\},\;\;\;\;\;\;\;\forall n,t,B,\phi$ (1f)

The ILP maximizes the number of queries that satisfy their latency SLOs with
the highest possible accuracy across all the selected query batches i.e.,
$\exists\,\phi:I(B,t,n,\phi)=1$ and $Acc(\phi)\cdot|B|$ is maximized. The
constraints of the ILP denote -

  * (1a)

A query $q$ can be assigned to at-most one batch $B$.

  * (1b)

A GPU $n$ can only execute a single subnet $\phi$ on a single batch $B$ at a
particular time $t$.

  * (1c)

Batch $B$ can only execute after its arrival time $a(B)$.

  * (1d)

Each batch $B$ can be served with a maximum of one subnet $\phi$ on a GPU $n$
at a time $t$.

  * (1e)

The batch should complete before deadline $d(B)$.

  * (1f)

The choice variable $I(B,t,n,\phi)$ is a boolean indicator.

We note that our formulation (1) is a Zero-one Integer Linear Program (ZILP)
and solving it is known to be NP-Hard [40, 59]. Furthermore, it is impractical
to expect oracular query arrival knowledge. This renders the use of the
formulated ILP in the online model serving setting unrealistic. Instead, we
approximate its behavior under different query traffic conditions with an
online scheduling policy instead.

(a) Latency Heatmap

(b) Control Choices

Figure 6: SlackFit control parameter space. (a) latency heatmap for six
different (uniformly sampled w.r.t. FLOPs) pareto-optimal subnets in SubNetAct
as a function of accuracy (x-axis) and batch size (y-axis). The latency is
monotonic with batch size and accuracy. (b) the number of available choices
decrease as latency increases.

###  4.2 SlackFit: Online-Scheduling Policy

We introduce SlackFit—a simple yet effective online scheduling policy that
aims to maximize accuracy and latency SLO (R1-R2). SlackFit is a greedy
heuristic that approximates the ILP-based policy in Eq. (1) and makes the
decision-making tractable. SlackFit makes following design choices:

Operates on Pareto-Optimal Subnets ($\Phi_{\text{pareto}}$). To make subnet
choices in reasonable time, SlackFit operates on the $\Phi_{\text{pareto}}$
instead of $\Phi$. $\Phi_{\text{pareto}}$ is a set of pareto-optimal subnets
w.r.t. latency, accuracy obtained by using existing neural architecture search
(NAS) methods[6]222It takes $\leq$ 2min to perform NAS on supernets by using
latency and accuracy predictors. The size of $|\Phi_{\text{pareto}}|\approx
10^{3}$ is orders of magnitude smaller than $|\Phi|\approx 10^{19}$. This
contributes to rapid scheduling decisions in SlackFit.

Uses Monotonic Properties of Subnets in $\Phi_{\text{pareto}}$. SlackFit
leverages key properties of subnets in $\Phi_{\text{pareto}}$ to further
reduce the control search space by performing $O(log)$ operations. Fig. 13(a)
shows latency profiles of six subnets uniformly sampled w.r.t. FLOPs from
$\Phi_{\text{pareto}}$. The properties of subnets in $\Phi_{\text{pareto}}$
are - (P1) the latency increases monotonically with batch size, (P2) the
latency increases monotonically with accuracy, (P3) the latency difference
among different batch sizes of a subnet increases with increase in subnet
accuracy.

Properties P1 and P2 further reduce the dimensionality of control search for
SlackFit to a single dimension (i.e., latency) to determine both the subnet
$\phi$ and batch size $B$. Instead of searching the two-dimensional table
(Fig. 13(a)), SlackFit operates on one-dimensional set of evenly sized latency
buckets (Fig. 13(b)). Each bucket consists of control tuples $(B,\phi)$ such
that $l_{\phi}(B)$ remains within the range of bucket width. Buckets are
constructed to exploit P3 and to further reduce the search complexity to
$O(1)$ for bucket selection. By construction and property P3, low latency
buckets contain lower accuracy, higher throughput control choices, as the
inference latency of smaller accuracy subnets on higher batch sizes is
relatively lower. High latency buckets contain higher accuracy, lower
throughput control choices.

Slack-Based Decision-making. SlackFit’s insight is that the remaining slack of
the most urgent query provides proxy to changes in the traffic. Traffic peaks
lead to more queueing delays in the system and in-turn reduces the remaining
slack. Under low traffic, the slack remains high. Therefore, SlackFit uses
remaining slack for decision making. It chooses a bucket with latency that is
closest to and less than the remaining slack of the most urgent query. All
control choices within the bucket satisfy query deadline. It picks the control
choice with maximum batch size to opt for a high throughput choice especially
for lower slack (traffic peaks).

SlackFit Behavior. With slack-based decision making, SlackFit can
automatically adjust accuracy (R2) and throughput of the system by choosing
appropriate latency bucket on variable arrival traffic to maintain high SLO
(R1). A well-behaved trace (e.g., low ingest rate, variation) results in
higher slack. Higher slack leads to the choice of higher latency buckets. And,
higher latency buckets are correlated strongly with the probability of
choosing higher accuracy models (due to property P2). Conversely, bursty
traces lead to lower latency bucket choices, as SlackFit operates under
reduced latency slack. Lower latency bucket choices have higher batch sizes
configuration (due to property P3). Thus, SlackFit opportunistically maximizes
accuracy while satisfying latency SLO.

####  4.2.1 SlackFit Approximation of Optimal Offline ILP

We now provide insights on how SlackFit emulates behavior of the optimal
offline ILP. To understand the behavior of ILP, we formulate a proxy utility
function that captures the inner-term of the ILP objective function in Eq 1,
the utility function is defined for all subnet $\phi$, batch-size $B$ and a
deadline $d_{B}$ (earliest deadline of queries in batch) –

$\mathbb{U}(\phi,B,d_{B})=\begin{cases}\text{Acc}(\phi)\cdot|B|,&\text{if
}l_{\phi}(B)<d_{B}\\\ 0,&\text{otherwise}\end{cases}$ (2)

The utility in Eq. 2 is non-zero if and only if subnet $\phi$ performs batch-
inference on batch $B$ within the deadline $d_{B}$, and is zero otherwise.
Note that this captures the success metrics: maximizing both the number of
queries processed (R1) within their deadline and the accuracy they were served
with (R2).

A. Offline ILP and SlackFit Prefer Pareto-Optimal Subnets. SlackFit’s key
design choice is to operate pareto-optimal subnets w.r.t. latency, accuracy
($\Phi_{\text{pareto}}$) (§4.2). We claim that offline ILP also tends to
pareto-optimal subnets (w.r.t. latency, accuracy), as the these subnets yield
higher utility.

######  Lemma 4.1.

The utility of pareto-optimal subnets is higher than non-pareto-optimal
subnets if they have similar inference latency for a batch of queries.

$\begin{split}\mathbb{U}(\phi_{p},B,d_{B})>\mathbb{U}(\phi_{q},B,d_{B}),\;\;\;\;\;\;\;\;\forall
B,d_{B}\\\
\text{s.t.}\;\;\phi_{p}\in\Phi_{\text{pareto}},\;\phi_{q}\in\\{\Phi\setminus\Phi_{\text{pareto}}\\},\;l_{\phi_{p}}(B)\approx
l_{\phi_{q}}(B)\end{split}$

This validates SlackFit’s design choice to operate on pareto-optimal subnets
only. We defer the proof to Appendix §A.1.

B. Offline ILP and SlackFit Prioritize Lower Accuracy & Higher Batch Size
under High Load. We make a key observation that the utility of lower accuracy
$\text{Acc}(\phi_{low})$, higher batch sizes ($B_{high}$) configurations is
higher than higher accuracy ($\text{Acc}(\phi_{high})$), lower batch size
($B_{low}$) configuration in pareto-subnets of SubNetAct. This is because the
factor difference in accuracy of pareto-subnets ($<1$) is less than the factor
differences of batch-sizes as seen in Fig. 13(a) i.e.,
$\frac{\text{Acc}(\phi_{high})}{\text{Acc}(\phi_{low})}\leq\frac{|B_{high}|}{|B_{low}|}\Rightarrow\text{Acc}(\phi_{high})\cdot|B_{low}|\leq\text{Acc}(\phi_{low})\cdot|B_{high}|$.
Therefore,
$\mathbb{U}(\phi_{low},B_{high},d_{q})\geq\mathbb{U}(\phi_{high},B_{low},d_{q})$
may hold true under high load, in cases where the most urgent query q in a
batch of $k$ queries ($q\in B_{k}$) can be served either by a) low accuracy
model ($\phi_{min}$) with batch size $B_{k}$ or b) higher accuracy model
($\phi_{max}$) on a subset of queries (say $m$, $q\in B_{m}$) with remaining
queries ($B_{k}\setminus B_{m}$) missing the deadline due to high load. In
such cases, the offline ILP will tend to option (a). SlackFit also tends to
lower accuracy and higher batch size options under heavy load, as described in
“SlackFit’s Behavior” (§4.2).

C. Offline ILP and SlackFit Prefer Higher Accuracy under Low Load. We make yet
another observation from the latency profiles of sampled pareto-optimal
subnets in Fig. 13(a). For a batch size $B$, such that $B=B_{1}+B_{2}$ where
$B_{1}>B_{2}$, the following holds true in many cases -
$B_{1}\cdot\text{Acc}(\phi_{high})+B_{2}\cdot\text{Acc}(\phi_{low})>B\cdot\text{Acc}(\phi_{mid})$.
Therefore,
$\mathbb{U}(\phi_{high},B_{1},d_{q})+\mathbb{U}(\phi_{low},B_{2},d(B_{2}))\geq\mathbb{U}(\phi_{mid},B,d_{q})$,
may hold true under low load, where the most urgent query q in batch $B$ can
be served by either a) mid accuracy model ($\phi_{mid}$) with batch size $B$,
or b) high accuracy model ($\phi_{high}$) with larger-size batched partition
$B_{1}$ ($q\in B_{1}$) with rest of the queries in batch $B_{2}$ served with
the low accuracy model ($\phi_{low}$) and meeting deadline $d(B_{2})$. In such
cases, ILP will tend to option (b) i.e., an option with higher average
accuracy. SlackFit also tends to higher accuracy subnets under lower load, as
described in §4.2.

##  5 SuperServe: System Architecture

SuperServe is a system that instantiates both SubNetAct mechanism and SlackFit
policy. SuperServe’s architecture is illustrated in Fig. 7. The SuperServe
client submits asynchronous RPC queries to the router with a deadline. These
queries are enqueued to a global earliest-deadline-first (EDF) queue (❶). As
soon as any worker becomes available, SuperServe’s fine-grained scheduler is
invoked (❷). It decides on the query-batch ($B$) and the subnet ($\phi$) which
are then dispatched to the worker (❸). Upon receiving this query-batch, the
worker that instantiates the supernet instantaneously actuates the chosen
subnet in-place on the GPU using SubNetAct (❹), performs inference (❺), and
returns predictions for the query-batch (❻). The router redirects these
predictions back to the client (❼).

Router.  The router runs fine-grained scheduler and interfaces with workers
via RPCs. All queries are received, enqueued, and dequeued asynchronously in
the router. It maintains pending queries in a global EDF queue, ordered by
timestamps which denote query deadlines. The router invokes the scheduler
whenever (a) a worker signals availability and (b) the EDF queue is not empty.
It then sends query-batches to workers and also passes back the predictions to
the clients.

Fine-grained Scheduler.  The scheduler’s control decision is a batch-size and
subnet ($\phi=(\mathbb{D},\mathbb{E},\mathbb{W})$). The scheduler provide
pluggable APIs for different policy implementations. SlackFit is one such
policy implemented in the scheduler. All policies in scheduler leverage two
key properties to make control decisions: (a) predictability of DNN inference
latency, (b) fast actuation of SubNetAct on the query’s critical path.

Worker.  The DNN worker employs the SubNetAct mechanism to host a supernetwork
(R3). SubNetAct’s operators are implemented in TorchScript’s intermediate
representation (IR) [14]. After receiving a query-batch and subnet
($\mathbb{D}$, $\mathbb{E}$, $\mathbb{W}$) from the router, the worker
actuates the desired subnet inplace using SubNetAct. A forward pass on the
actuated subnet produces predictions that are returned to the router. The
router’s scheduler gets notified about worker availability on receiving the
predictions.

Supernet Profiler.  A supernet profiler is used when a supernet is submitted
to SuperServe. This profiling completes apriori, before the workload begins,
and off the critical path of the queries. The profiler first employs neural
architecture search (NAS) [6] to find pareto-optimal subnetworks from the
supernetwork for each latency target (key design choice of SlackFit §4.2). The
latency profiling is done the pareto-optimal subnets obtained by NAS. This
latency is a function of batch size and target worker GPU (latency profile in
Fig. 7 on RTX2080Ti GPU), and the profiling process for the subnetworks is no
different than the model profiling done for other existing models like ResNets
[24], Wide-ResNets [58], ConvNeXt [35] etc.

##  6 Evaluation

Figure 7: SuperServe’s Architecture. SuperServe consists of a router,
scheduler, workers and a supernetwork profiler. Clients submit queries with a
specified latency constraint (SLO) asynchronously. ❶ - ❼ represents the
critical path of the query in SuperServe. The latency profile estimation is
done apriori, off the critical path by the profiler.

We assess SuperServe’s end-to-end performance i.e., its ability to maximize
SLO attainment (R1) and accuracy (R2) under a variety of traffic conditions,
including synthetic traces (§6.2) and real-world derived Microsoft Azure
Functions trace (§6.3). SuperServe is resource-efficient (R3) due to the use
of SubNetAct mechanism, already established in §3.1. We conclude with
microbenchmarks (§6.4) that show SuperServe linearly scaling to 33,000 qps and
providing transparent fault tolerance.

###  6.1 Experimental Setup

Success metrics. SLO attainment is defined as the fraction of the queries that
complete within the latency deadline (R1). The mean serving accuracy is
calculated for the queries that satisfy the SLO and is the average of models’
profiled accuracy that were used to serve the queries (R2).

Traces. We evaluate SuperServe on three sets of traces: bursty, time-varying,
and real-world. Bursty and time-varying traces are synthetic, similar to those
used in InferLine [10]. We construct the bursty traces by starting with a base
arrival with mean ingest rate $\lambda_{b}$ (with $CV^{2}=0$) and add a
variant arrival trace with mean ingest rate $\lambda_{v}$ drawing inter-
arrival times from a gamma distribution (Fig. 12(a)). We vary $\lambda_{b}$,
$\lambda_{v}$ and $CV^{2}$. Time-varying traces differ from bursty by varying
the mean ingest throughput over time. We change the mean from
$\mu=1/\lambda_{1}$ to $\mu=1/\lambda_{2}$ at rate $\tau$ $q/s^{2}$ with a
fixed $CV^{2}_{a}$. Higher ingest acceleration $\tau$ $q/s^{2}$ corresponds to
faster change from $\lambda_{1}$ to $\lambda_{2}$. All synthetic trace
generation is seeded. Lastly, we use a MAF trace [45] for evaluation on a
real-world workload.

Baselines. We compare SuperServe with the single model serving systems that
don’t perform accuracy trade-offs (and the models are manually selected by
users, non-automated serving systems in §7). These systems are represented as
Clipper+ baseline and include systems like Clipper [11], Clockwork [22], and
TF-serving [37]. Clipper+ is manually configured to serve six different
accuracy points (subnets) that uniformly span the supernet’s accuracy range
and result in its six different versions. We also compare SuperServe with
INFaaS and note that INFaaS is designed to “pick the most cost-efficient model
that meets the [specified] accuracy constraint” [15, 42, 43]. However, in the
presence of unpredictable, bursty request rates, the choice of the model
accuracy to serve in order to meet the SLO requirements is unknown. Since,
unlike SuperServe, INFaaS does not automatically discover the accuracy of the
model to serve under unpredictable request rates and instead requires queries
to be hand-annotated with accuracy thresholds, we choose to run INFaaS with no
accuracy thresholds provided (§6.2.1,§6.2.2). In such a scenario, INFaaS
reduces to serving the most cost-efficient model (which is the model with the
minimum accuracy). We confirmed this behavior with the INFaaS authors, who
agree that “[our] representation of INFaaS as a baseline that always chooses
the same model is correct in the absence of an accuracy threshold, or a fixed
(never changing) accuracy threshold.” [15].

Subnet-Profiling. We use the supernet trained on ImageNet [12] dataset
released by [6] and enable SubNetAct in it. We extract pareto-subnets
($\Phi_{\text{pareto}}$) by running NAS (publicly released by [6]) on trained
supernet. The pareto-subnets in the supernet span $0.9-7.5$ GFLOPs range and
an accuracy range of $73-80\%$. Pareto-subnets are profiled with varied batch
sizes on NVIDIA RTX2080Ti GPU.

Test bed. SuperServe is implemented in C++ (17,500 lines of code). gRPC [20]
is used for communication between a client, the router and workers. The
experiments use 8 RTX2080Ti GPUs and 24 CPU cores. Each worker uses one GPU.

Figure 8: SuperServe with variable burstiness. SuperServe outperforms Clipper+
and INFaaS baselines by finding better tradeoffs and consistently achieving
$>0.999$ SLO attainment on bursty traces. Variable ingest rate
$\lambda_{v}=\\{$ $2950,$ $4900,$ $5550\\}$ q/s increases vertically (down).
$CV^{2}_{a}=\\{2,4,8\\}$ increases horizontally (across). SuperServe achieves
a better trade-off in SLO attainment (y-axis) and mean serving accuracy
(x-axis) in all cases. SuperServe consistently achieves high SLO attainment
$>0.999$.  Figure 9: SuperServe with arrival acceleration. SuperServe
outperforms Clipper+ and INFaaS baselines by finding better tradeoffs on time
varying traces. Mean ingest rate accelerates from $\lambda_{1}$ to
$\lambda_{2}$ q/s with $\tau$ $q/s^{2}$. $\tau=\\{250,500,5000\\}$ increases
horizontally (across), while $\lambda_{2}=\\{4800,6800,7800\\}$ increases
vertically (down) with $\lambda_{1}=2500$ q/s and $CV^{2}_{a}=8$ staying
constant. SuperServe finds a better trade-off in SLO attainment (y-axis) and
mean serving accuracy (x-axis).

###  6.2 End-to-End: Synthetic

We aim to answer the following questions, whether SuperServe (a) automatically
serves queries using appropriate models (accuracy) for different traces (R2),
(b) achieves a better trade-off w.r.t. the success metrics (R1-R2), (c)
withstands sharp bursts while maintaining high SLO attainment (R1) and (d)
instantaneously changes system capacity to serve traces where mean ingest rate
changes over time. To answer these questions, we evaluate SuperServe on the
bursty and time-varying traces (§6.1).

####  6.2.1 Baseline comparison with burstiness

Fig. 8 compares SuperServe with the baselines over a range of traces
increasing mean ingest rate $\lambda_{v}$ across and $CV^{2}_{a}$ down. All
traces are configured with $36$ms SLO. Achieving high SLO attainment (R1) and
high mean serving accuracy (R2) is desirable, which implies the best trade-off
is in the top-right corner of the graph. We demonstrate that no single choice
of a model is sufficient for different mean arrival rates and $CV^{2}_{a}$.
For instance, the SLO attainment of Clipper+(76.69) decreases as the
$CV^{2}_{a}$ increases for $\lambda_{v}=5550$ (row 3). Similarly, the SLO
attainment of Clipper+(78.25) decreases with increase in $\lambda_{v}$ for
$CV^{2}_{a}=2$ (column 1). We draw the following takeaways: (1) SuperServe
achieves a significantly better trade-off between SLO attainment and accuracy
(R1-R2) than the baselines(Clipper+ and InFaaS ). It is $4.33\%$ more accurate
than the baselines at an SLO attainment level of $0.9999$ and $2.06$x higher
SLO attainment at the same accuracy level. SuperServe is consistently at the
top-right corner in Fig. 8 across all the traces. (2) SlackFit automatically
selects appropriate models for sustaining different traffic conditions. As
$\lambda_{v}$ increases, SuperServe reduces serving accuracy while maintaining
high SLO attainment (columns).

Note that, across all the traces, InFaaS achieves an optimal SLO attainment
but with a significantly smaller mean serving accuracy (by up to $4.33\%$)
than SuperServe. InFaaS policy serves the min-cost (and hence min accuracy)
model for the trace without accuracy constraints. Whereas, SuperServe achieves
a better trade-off between the success metrics because (a) SubNetAct allows in
place activation of different subnetworks without affecting SLO attainment
(R1); (b) SlackFit opportunistically selects higher accuracy models based on
query’s slack (R2). Also, the difference between SuperServe and Clipper+
narrows w.r.t. accuracy as $CV^{2}_{a}$ increases. This is because SlackFit
switches to lower accuracy models more frequently with burstier traffic. This
system dynamics is detailed in §A.2.

####  6.2.2 Baseline comparison with arrival acceleration

Fig. 9 evaluates SuperServe performance at different levels of arrival rate
change (i.e., arrival acceleration). Traces start at $\lambda_{1}$ and
increase to $\lambda_{2}$ with acceleration $\tau$. Traces fix
$\lambda_{1}=2500qps$ and $CV^{2}_{a}=8$ but change $\lambda_{2}$ and
acceleration $\tau$ .

The $\tau$ and $\lambda_{2}$ are chosen to demonstrate that single, pre-
configured model choices are inadequate to sustain different rates of arrival
(mean $\lambda$) and acceleration ($\tau$). Clipper+($79.44$) starts diverging
as $\tau$ increases ( $\lambda_{2}$ is $6800$ $qps$ (row 2)). Similarly,
Clipper+($79.44$) starts diverging with increase in $\lambda_{2}$ ($\tau=250$
$q/s^{2}$ (column 1)). The key takeaways from this experiment are as follows:

  * $\bullet$

SuperServe rapidly scales system capacity and achieves a high SLO attainment
($0.991$-$1.0$) even with high values of $\tau$ ($5000$ $q/s^{2}$). The
experiment demonstrates two key properties of SuperServe— (a) the actuation
delay in SuperServe is indeed negligible, (b) the lower actuation delay helps
achieve higher SLO attainments for time-varying traces (R1). SuperServe
empirically demonstrates “agile elasticity” (§2.2), and withstands high
acceleration in arrival rate ($\tau$).

  * $\bullet$

SlackFit dynamically adjusts the serving accuracy over time (R2) and achieves
a better trade-off between success metrics (R1-R2). When the mean ingest
throughput is low ($\lambda_{1}$), SuperServe uses higher accuracy models. It
quickly switches to lower accuracy models when mean arrival rate is high
($\lambda_{2}$), as evident in system dynamics Fig. 12(b).

Fig. 9 experiments exhibit interesting trends. As the $\tau$ increases, the
gap between SuperServe and Clipper+ w.r.t. mean serving accuracy narrows. This
is because SlackFit selects smaller accuracy sooner with the increase in
$\tau$. Lower $\tau$ values give enough time to SuperServe to serve
intermediate mean arrival rates with higher accuracy models while gradually
moving to lower accuracy models as mean ingest rate increases to $\lambda_{2}$
qps. Whereas, InFaaS continues to serve min accuracy model for all traces as
its policy doesn’t maximize accuracy by design.

###  6.3 End-to-End: Real Workloads

(a) SuperServe achieves best tradeoffs w.r.t. SLO attainment and accuracy on a
real trace.

(b) SuperServe System Dynamics

Figure 10: SuperServe on Real World Trace. SuperServe on Microsoft Azure
Functions (MAF) [45] trace. (a) SuperServe is compared with Clipper+ and
INFaaS baselines, reaching $4.67\%$ higher accuracy at same SLO attainment and
$2.85$x higher SLO attainment at same accuracy than any fixed accuracy point
that can be served by INFaaS (in the absence of accuracy constraints) and
Clipper+. (b) System dynamics w.r.t. batch size and subnet activation control
decisions over time in response to ingest rate in the top graph.

We investigate if: (a) SlackFit is capable of achieving a better trade-off
between SLO attainment and mean serving accuracy on real workloads (R1-R2),
and (b) SubNetAct contributes to serve highly unpredictable workloads at high
SLO attainment.

We use the MAF trace [45] to evaluate SuperServe (similar to Clockwork [22]).
The trace is collected on Microsoft’s serverless platform and serves as a
reasonable workload to evaluate SuperServe as serverless ML inference is an
active research area [55, 28]. It consists of number of invocations made for
each function per minute and contains nearly 46,000 different function
workloads that are bursty, periodic, and fluctuate over time. We use 32,700
function workloads from the MAF trace, resulting in a mean arrival rate of
6400 qps. The 24 hour long trace is shrunk to 120 seconds using shape-
preserving transformations to match our testbed.

Result. Fig. 10(a) compares SuperServe with Clipper+ and InFaaS on the real-
world MAF trace. SuperServe achieves an SLO attainment (R1) of $0.99999$ (five
’9’s). Compared to Clipper+ and InFaaS , SuperServe is $4.65\%$ more accurate
(R2) at the same level of SLO attainment. It also achieves $2.85$x factor
improvement in SLO attainment at the same mean serving accuracy. Moreover,
Clipper+($79.44$, $80.16$) diverges on the MAF trace.

System Dynamics. Fig. 10(b) shows the ingest throughput (qps), serving
accuracy and batch size control decisions (made by SlackFit) for the MAF
trace. As seen in the figure, the trace contains periodic short-interval
spikes that reach upto 8750 qps, demonstrating the agility of the system.
SlackFit selects both smaller accuracy model and higher batch size during the
load spikes to meet the deadline (R1). SlackFit makes such control decisions
because it uses query’s slack as a signal to maximize batch size. As the query
slack decreases, it selects maximum batch size control parameters in the lower
latency buckets. Furthermore, these control decisions increase the system
capacity instantly through SubNetAct. Lastly, SlackFit serves higher accuracy
models when the ingest rate is low and hence, achieves better mean serving
accuracy (R2).

(a) Fault-Tolerance

(b) Scalability

(c) Policy-SE

Figure 11: SuperServe’s Micro-benchmarks. (a) SuperServe resiliency to faults.
SuperServe maintains high SLO attainment in the system by dynamically
adjusting served accuracy as workers drop out over time. The trace stays
statistically the same ($\lambda=3500$ qps, $CV^{2}_{a}=2$ (last row)). (b)
SuperServe scales linearly with the number of workers, achieving up to 33000
qps (orders of magnitude higher than published SotA systems) while maintaining
high .999 SLO attainment. (c) SlackFit finds the best tradeoff on the SLO
attainment/accuracy maximization continuum automatically (§6.4).

###  6.4 Microbenchmarks

Fault Tolerance. SubNetAct mechanism provides an additional advantage of
transparent fault tolerance. We run SuperServe with $100\%$ capacity ($8$
workers) with a bursty traffic trace ($\lambda=3500$ qps, $CV^{2}_{a}=2$) for
$60$ seconds and gradually kill a worker every $12$ seconds to simulate
faults. SuperServe shows resilience to decreases in system throughput capacity
to as low as 50% by maintaining SLO attainment as high as 0.999 for the
unchanging trace as it leverages subnetwork activation to serve lower accuracy
models automatically. Similar methodology was used in [53]. Fig. 11(a) shows
SLO attainment as a function of time (along with other system dynamics). As
the faults occur (workers killed, dotted red lines), SuperServe automatically
transitions to lower accuracy models to maintain high SLO attainment. We
attribute SuperServe’s fault tolerance to (a) a wide-dynamic throughput range
afforded by SubNetAct (Fig. 5(c)) that allows SuperServe to serve the workload
even with $50\%$ capacity, and (b) SubNetAct’s low actuation delay that
provides agility to rapidly increase system-capacity (during faults) without
sacrificing SLO attainment (R1).

Scalability. We assess if SuperServe reaches high SLO attainment at scale. To
show this, we scale the number of workers and observe the maximum throughput
SuperServe sustains to reach SLO attainment of $0.999$. We serve Resnet-18
[24] across all the workers with clients providing a batch of 8 images333we
don’t perform adaptive batching for this experiment. Scalability experiments
are conducted with $CV^{2}_{a}=0$. Fig. 11(b) shows sustained ingest
throughput with the increase in workers. In this experiment SuperServe
achieves an SLO attainment of $0.999$ while reaching throughputs as high as
$\approx 33000$ qps.

Policy Space Exploration. We compare different policies implemented in
SuperServe (Fig. 11(c)). We show that SlackFit achieves the best tradeoff
w.r.t. our success metrics compared to both MaxAcc (greedily maximizes
accuracy) and MaxBatch (greedily maximizes throughput) as $CV^{2}_{a}$ is
varied. Details of the policies and the experiment are in §A.5.

##  7 Related Work

We build on recent DNN supernet training progress, which is complementary to
this work. [6, 44] train supernets for image classification vision tasks
[image-classification]. Dynabert [25] supernet supports NLP tasks trained on
GLUE [52], including textual entailment, question answering and sentiment
analysis.

Model serving systems can be broadly divided into two categorizes — a) Non-
Automated, and b) Automated. Non-automated serving system expect application
developers to provide the prediction models and make explicit choices in the
accuracy-latency trade-off space. This category includes TensorFlow serving
[37], Clipper [11], InferLine [10], SageMaker [30], Triton [36], Shepherd [59]
and Clockwork [22]. TensorFlow Serving serves the models trained in TensorFlow
framework while Clipper and Triton support models trained from multiple
frameworks. Triton optimizes models for GPU serving. Clockwork guarantees
predictable tail latency for DNN inference by designing a predictable system
bottom up and making cross-stack design decisions explicitly for worst case
predictability. Inferline provides support for provisioning inference
pipelines that consist of multiple models, but the models are still hard coded
in the pipeline vertices. However, all the prior works in this category are
complementary to SuperServe. For instance, SuperServe’s workers can be made
more predictable by consolidating choices like Clockwork. Inferline’s
autoscaling policy can be used on top of SuperServe. The max-provisioning
ratio of the smallest subnetwork in SuperServe can be calculated to construct
traffic envelopes for Inferline’s high frequency tuner. The workers can then
be scaled up if the ingest throughput cannot be served by the smallest
subnetwork of the supernet.

In contrast, automated serving systems [42, 60] provide a mechanism for
switching between available latency/accuracy points and automate the
navigation of the accuracy-latency trade-off space with a policy, resulting in
automatic DNN selection at runtime. However, both [42] and [60] use state-of-
the-art DNNs (e.g., ResNets, MobileNets) and rely on model loading mechanism
instead of the supernet, which offers better pareto-optimality and orders of
magnitude faster model switching enabled via proposed SubNetAct.
Fundamentally, these state of the art mechanisms implicitly bias their
policies to avoid model switching, which clearly limits the ability of the
system to respond to unpredictable trace and query complexity dynamics in a
agile fashion. InFaaS’s DNN switching policy is biased towards selecting the
least accurate DNNs that satisfy accuracy constraints, as the goal of the
stated goal of the system is to satisfy constraints instead of treating
accuracy as an optimization objective. Model-Switching [60] switches between
CPU models only. Thus, it cleverly never incurs the overhead of GPU model
loading faced by other systems such as InFaaS and Clockwork. SuperServe
supports GPU model serving via subnetwork activation, addresing the model
switching overhead through its proposed SubNetAct.

Training Supernets. Supernet (as a concept) and its training was first
proposed by OFA [6]. The subnetworks trained as a part of training the
supernet are shown to offer a better accuracy-latency trade-off than existing
models like EfficientNets [49], ResNets [24], MobileNets [26] and
SlimmableNets [57]. Furthermore, there is a surge of recent works that propose
improvements to the supernet training such as CompOFA [44], and BigNAS [56].
For instance, CompOFA makes the training of Supernets faster and more accurate
by training a fewer number of subnetworks simultaneously. While BigNAS trains
the supernet in a one-shot fashion with a wider range of subnetworks. Dynabert
[25] trains a supernet based on transformer neural network architecture for
text datasets. It varies the depth and hidden dimensions in BERT-like models.
AutoFormer [9] is another technique that trains supernets derived from vision
transformers. The subnetworks extracted from AutoFormer’s supernet surpass
state-of-the-art vision transformers like ViT [13] and DeiT [50]. NasViT [19]
trains the supernet for semantic segmentation tasks and achieves a better
trade-off between accuracy and latency at fewer FLOPs. SuperServe provides
system support for serving Supernets trained using any existing technique. We
believe that Supernets are an emerging phenomenon, and system support for
serving them is the need of the hour.

##  8 Conclusion

We describe a novel mechanism SubNetAct that carefully inserts specialized
control-flow and slicing operators into SuperNets to enable a resource-
efficient, fine-grained navigation of the latency-accuracy tradeoff space.
SubNetAct unlocks the design space of fine-grained, reactive scheduling
policies. We explore the design of one such simple, yet effective greedy
heuristic-based cheduling policy SlackFit. We instantiate SubNetAct and
SlackFit in SuperServe, and extensively evaluate it on real-world workloads.
SuperServe achieves $4.67\%$ better accuracy at the same level of SLO
attainment or 2.85x better SLO attainment at the same level of serving
accuracy compared to state-of-the-art inference-serving systems.

## References

  * [1] Accelerate ai development with google cloud tpus.  https://cloud.google.com/tpu.
  * [2] Aws inferentia.  https://aws.amazon.com/machine-learning/inferentia/.
  * [3] Waleed Ali, Sherif Abdelkarim, Mahmoud Zidan, Mohamed Zahran, and Ahmad El Sallab.  Yolo3d: End-to-end real-time 3d oriented object bounding box detection from lidar point cloud.  In Proceedings of the European Conference on Computer Vision (ECCV) Workshops, pages 0–0, 2018.
  * [4] Ganesh Ananthanarayanan, Paramvir Bahl, Peter Bodík, Krishna Chintalapudi, Matthai Philipose, Lenin Ravindranath, and Sudipta Sinha.  Real-time video analytics: The killer app for edge computing.  computer, 50(10):58–67, 2017.
  * [5] Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar.  Designing neural network architectures using reinforcement learning.  arXiv preprint arXiv:1611.02167, 2016.
  * [6] 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.
  * [7] Han Cai, Ligeng Zhu, and Song Han.  Proxylessnas: Direct neural architecture search on target task and hardware.  arXiv preprint arXiv:1812.00332, 2018.
  * [8] Liang-Chieh Chen, George Papandreou, Florian Schroff, and Hartwig Adam.  Rethinking atrous convolution for semantic image segmentation.  arXiv preprint arXiv:1706.05587, 2017.
  * [9] Minghao Chen, Houwen Peng, Jianlong Fu, and Haibin Ling.  Autoformer: Searching transformers for visual recognition.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 12270–12280, 2021.
  * [10] Daniel Crankshaw, Gur-Eyal Sela, Corey Zumar, Xiangxi Mo, Joseph E. Gonzalez, Ion Stoica, and Alexey Tumanov.  Inferline: ML inference pipeline composition framework.  CoRR, abs/1812.01776, 2018.
  * [11] Daniel Crankshaw, Xin Wang, Guilio Zhou, Michael J Franklin, Joseph E Gonzalez, and Ion Stoica.  Clipper: A $\\{$Low-Latency$\\}$ online prediction serving system.  In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pages 613–627, 2017.
  * [12] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [13] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [14] Facebook.  Torchscript, 2022.
  * [15] Romero Francisco, Qian Li, and Christos Kozyrakis.  Personal Communication, December 2022.
  * [16] Shen Gao, Xiuying Chen, Piji Li, Zhaochun Ren, Lidong Bing, Dongyan Zhao, and Rui Yan.  Abstractive text summarization by incorporating reader comments.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 6399–6406, 2019.
  * [17] Ionel Gog, Sukrit Kalra, Peter Schafhalter, Joseph E Gonzalez, and Ion Stoica.  D3: a dynamic deadline-driven approach for building autonomous vehicles.  In Proceedings of the Seventeenth European Conference on Computer Systems, pages 453–471, 2022.
  * [18] Ionel Gog, Sukrit Kalra, Peter Schafhalter, Matthew A Wright, Joseph E Gonzalez, and Ion Stoica.  Pylot: A modular platform for exploring latency-accuracy tradeoffs in autonomous vehicles.  In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 8806–8813. IEEE, 2021.
  * [19] Chengyue Gong, Dilin Wang, Meng Li, Xinlei Chen, Zhicheng Yan, Yuandong Tian, Vikas Chandra, et al.  Nasvit: Neural architecture search for efficient vision transformers with gradient conflict aware supernet training.  In International Conference on Learning Representations, 2021.
  * [20] Google.  grpc, 2022.
  * [21] Arpan Gujarati, Sameh Elnikety, Yuxiong He, Kathryn S. McKinley, and Björn B. Brandenburg.  Swayam: Distributed autoscaling to meet slas of machine learning inference services with resource efficiency.  In Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference, Middleware ’17, page 109–120, New York, NY, USA, 2017. Association for Computing Machinery.
  * [22] Arpan Gujarati, Reza Karimi, Safya Alzayat, Wei Hao, Antoine Kaufmann, Ymir Vigfusson, and Jonathan Mace.  Serving DNNs like clockwork: Performance predictability from the bottom up.  In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), pages 443–462. USENIX Association, November 2020.
  * [23] Kim Hazelwood, Sarah Bird, David Brooks, Soumith Chintala, Utku Diril, Dmytro Dzhulgakov, Mohamed Fawzy, Bill Jia, Yangqing Jia, Aditya Kalro, et al.  Applied machine learning at facebook: A datacenter infrastructure perspective.  In 2018 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 620–629. IEEE, 2018.
  * [24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [25] Lu Hou, Zhiqi Huang, Lifeng Shang, Xin Jiang, Xiao Chen, and Qun Liu.  Dynabert: Dynamic bert with adaptive width and depth.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9782–9793. Curran Associates, Inc., 2020.
  * [26] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al.  Searching for mobilenetv3.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1314–1324, 2019.
  * [27] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In International conference on machine learning, pages 448–456. PMLR, 2015.
  * [28] Vatche Ishakian, Vinod Muthusamy, and Aleksander Slominski.  Serving deep learning models in a serverless platform.  CoRR, abs/1710.08460, 2017.
  * [29] Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Tuo Zhao.  SMART: Robust and efficient fine-tuning for pre-trained natural language models through principled regularized optimization.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2177–2190, Online, July 2020. Association for Computational Linguistics.
  * [30] Ameet V Joshi.  Amazon’s machine learning toolkit: Sagemaker.  In Machine Learning and Artificial Intelligence, pages 233–243. Springer, 2020.
  * [31] Sangeetha Abdu Jyothi, Carlo Curino, Ishai Menache, Shravan Matthur Narayanamurthy, Alexey Tumanov, Jonathan Yaniv, Ruslan Mavlyutov, Inigo Goiri, Subru Krishnan, Janardhan Kulkarni, et al.  Morpheus: towards automated $\\{$SLOs$\\}$ for enterprise clusters.  In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pages 117–134, 2016.
  * [32] Zhuohan Li, Lianmin Zheng, Yinmin Zhong, Vincent Liu, Ying Sheng, Xin Jin, Yanping Huang, Zhifeng Chen, Hao Zhang, Joseph E Gonzalez, et al.  $\\{$AlpaServe$\\}$: Statistical multiplexing with model parallelism for deep learning serving.  In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23), pages 663–679, 2023.
  * [33] Shih-Chieh Lin, Yunqi Zhang, Chang-Hong Hsu, Matt Skach, Md E Haque, Lingjia Tang, and Jason Mars.  The architectural implications of autonomous driving: Constraints and acceleration.  In Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems, pages 751–766, 2018.
  * [34] Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  arXiv preprint arXiv:1806.09055, 2018.
  * [35] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie.  A convnet for the 2020s.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11976–11986, 2022.
  * [36] Nvidia.  Triton inference system, 2020.
  * [37] Christopher Olston, Noah Fiedel, Kiril Gorovoy, Jeremiah Harmsen, Li Lao, Fangwei Li, Vinu Rajashekhar, Sukriti Ramesh, and Jordan Soyke.  Tensorflow-serving: Flexible, high-performance ml serving.  arXiv preprint arXiv:1712.06139, 2017.
  * [38] Kalin Ovtcharov, Olatunji Ruwase, Joo-Young Kim, Jeremy Fowers, Karin Strauss, and Eric S Chung.  Accelerating deep convolutional neural networks using specialized hardware.  Microsoft Research Whitepaper, 2(11):1–4, 2015.
  * [39] Arthi Padmanabhan, Neil Agarwal, Anand Iyer, Ganesh Ananthanarayanan, Yuanchao Shu, Nikolaos Karianakis, Guoqing Harry Xu, and Ravi Netravali.  Gemel: Model merging for $\\{$Memory-Efficient$\\}$,$\\{$Real-Time$\\}$ video analytics at the edge.  In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pages 973–994, 2023.
  * [40] Christos H Papadimitriou and Kenneth Steiglitz.  Combinatorial optimization: algorithms and complexity.  Courier Corporation, 1998.
  * [41] Jongsoo Park, Maxim Naumov, Protonu Basu, Summer Deng, Aravind Kalaiah, Daya Khudia, James Law, Parth Malani, Andrey Malevich, Satish Nadathur, et al.  Deep learning inference in facebook data centers: Characterization, performance optimizations and hardware implications.  arXiv preprint arXiv:1811.09886, 2018.
  * [42] Francisco Romero, Qian Li, Neeraja J Yadwadkar, and Christos Kozyrakis.  $\\{$INFaaS$\\}$: Automated model-less inference serving.  In 2021 USENIX Annual Technical Conference (USENIX ATC 21), pages 397–411, 2021.
  * [43] Francisco Romero, Qian Li, Neeraja J Yadwadkar, and Christos Kozyrakis.  Infaas policy’s decisions with respect to accuracy constraints, 2022.
  * [44] Manas Sahni, Shreya Varshini, Alind Khare, and Alexey Tumanov.  Comp{ofa} – compound once-for-all networks for faster multi-platform deployment.  In International Conference on Learning Representations, 2021.
  * [45] Mohammad Shahrad, Rodrigo Fonseca, Íñigo Goiri, Gohar Chaudhry, Paul Batum, Jason Cooke, Eduardo Laureano, Colby Tresness, Mark Russinovich, and Ricardo Bianchini.  Serverless in the wild: Characterizing and optimizing the serverless workload at a large cloud provider.  In 2020 USENIX Annual Technical Conference (USENIX ATC 20), pages 205–218, 2020.
  * [46] Jonathan Soifer, Jason Li, Mingqin Li, Jeffrey Zhu, Yingnan Li, Yuxiong He, Elton Zheng, Adi Oltean, Maya Mosyak, Chris Barnes, et al.  Deep learning inference service at microsoft.  In 2019 USENIX Conference on Operational Machine Learning (OpML 19), pages 15–17, 2019.
  * [47] Martin Sundermeyer, Ralf Schlüter, and Hermann Ney.  Lstm neural networks for language modeling.  In Thirteenth annual conference of the international speech communication association, 2012.
  * [48] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V Le.  Mnasnet: Platform-aware neural architecture search for mobile.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2820–2828, 2019.
  * [49] Mingxing Tan and Quoc Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  In International conference on machine learning, pages 6105–6114. PMLR, 2019.
  * [50] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In International conference on machine learning, pages 10347–10357. PMLR, 2021.
  * [51] Prahlad Venkatapuram, Zhao Wang, and Chandra Mallipedi.  Custom silicon at facebook: A datacenter infrastructure perspective on video transcoding and machine learning.  In 2020 IEEE International Electron Devices Meeting (IEDM), pages 9–7. IEEE, 2020.
  * [52] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman.  Glue: A multi-task benchmark and analysis platform for natural language understanding.  arXiv preprint arXiv:1804.07461, 2018.
  * [53] Stephanie Wang, John Liagouris, Robert Nishihara, Philipp Moritz, Ujval Misra, Alexey Tumanov, and Ion Stoica.  Lineage stash: fault tolerance off the critical path.  In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pages 338–352, 2019.
  * [54] Carole-Jean Wu, David Brooks, Kevin Chen, Douglas Chen, Sy Choudhury, Marat Dukhan, Kim Hazelwood, Eldad Isaac, Yangqing Jia, Bill Jia, et al.  Machine learning at facebook: Understanding inference at the edge.  In 2019 IEEE international symposium on high performance computer architecture (HPCA), pages 331–344. IEEE, 2019.
  * [55] Yanan Yang, Laiping Zhao, Yiming Li, Huanyu Zhang, Jie Li, Mingyang Zhao, Xingzhen Chen, and Keqiu Li.  Infless: A native serverless system for low-latency, high-throughput inference.  In Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’22, page 768–781, New York, NY, USA, 2022. Association for Computing Machinery.
  * [56] Jiahui Yu, Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang, Xiaodan Song, Ruoming Pang, and Quoc Le.  Bignas: Scaling up neural architecture search with big single-stage models.  In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision – ECCV 2020, pages 702–717, Cham, 2020. Springer International Publishing.
  * [57] Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang.  Slimmable neural networks.  arXiv preprint arXiv:1812.08928, 2018.
  * [58] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  arXiv preprint arXiv:1605.07146, 2016.
  * [59] Hong Zhang, Yupeng Tang, Anurag Khandelwal, and Ion Stoica.  $\\{$SHEPHERD$\\}$: Serving $\\{$DNNs$\\}$ in the wild.  In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pages 787–808, 2023.
  * [60] Jeff Zhang, Sameh Elnikety, Shuayb Zarar, Atul Gupta, and Siddharth Garg.  $\\{$Model-Switching$\\}$: Dealing with fluctuating workloads in $\\{$Machine-Learning-as-a-Service$\\}$ systems.  In 12th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 20), 2020.
  * [61] Minjia Zhang, Samyam Rajbandari, Wenhan Wang, Elton Zheng, Olatunji Ruwase, Jeff Rasley, Jason Li, Junhua Wang, and Yuxiong He.  Accelerating large scale deep learning inference through $\\{$DeepCPU$\\}$ at microsoft.  In 2019 USENIX Conference on Operational Machine Learning (OpML 19), pages 5–7, 2019.
  * [62] Barret Zoph and Quoc V Le.  Neural architecture search with reinforcement learning.  arXiv preprint arXiv:1611.01578, 2016.
  * [63] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le.  Learning transferable architectures for scalable image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8697–8710, 2018.

##  Appendix A Appendix

###  A.1 Utility of Pareto Points is Higher

######  Lemma A.1.

The utility of pareto-optimal subnets is higher than non-pareto-optimal
subnets if they have similar inference latency for a batch of queries.

$\begin{split}\mathbb{U}(\phi_{p},B,d_{B})>\mathbb{U}(\phi_{q},B,d_{B}),\;\;\;\;\;\;\;\;\forall
B,d_{B}\\\
\text{s.t.}\;\;\phi_{p}\in\Phi_{\text{pareto}},\;\phi_{q}\in\\{\Phi\setminus\Phi_{\text{pareto}}\\},\;l_{\phi_{p}}(B)\approx
l_{\phi_{q}}(B)\end{split}$

Proof By Contradiction. Assume a non-pareto optimal subnet ($\phi_{q}$) such
that it has higher utility than pareto optimal subnet ($\phi_{p}$) for a batch
$B$ and $l_{\phi_{p}}(B)\approx l_{\phi_{q}}(B)$ i.e.,
$\mathbb{U}(\phi_{p},B,d_{B})<\mathbb{U}(\phi_{q},B,d_{B})$.

Now, due to the pareto optimal property $Acc(\phi_{p})>Acc(\phi_{q})$, this
implies $Acc(\phi_{p})\cdot|B|>Acc(\phi_{q})\cdot|B|$ which implies
$\mathbb{U}(\phi_{p},B,d_{B})\geq\mathbb{U}(\phi_{q},B,d_{B})$ for any delay
$d_{B}$ as $l_{\phi_{p}}(B)\approx l_{\phi_{q}}(B)$. This is contradiction.
Hence Proved.

###  A.2 System Dynamics: Synthetic Traces

We also derive key observations from the dynamics to understand how SuperServe
achieves high SLO attainment and better trade-offs (R1-R2) for synthetic
traces.

Fig. 12 shows the system dynamics of SuperServe for both bursty and time-
varying traces. The mean ingest rate of the bursty traces is $7000$ qps and
they vary in $CV^{2}_{a}$ = {$2$, $8$}. Similarly, in case of the time-varying
traces, the ingest rate is increased from $\lambda_{1}$ qps to $\lambda_{2}$
qps at varying accelerations $\tau$ = {$250$ $q/s^{2}$, $5000$ $q/s^{2}$}. The
control decisions made by SlackFit (subnetwork (accuracy) and batch size) are
shown over time.

Fig. 12(a) shows system dynamics for the bursty traces. The trace with
$CV^{2}=8$ (blue line) has higher spikes than the trace with $CV^{2}=2$
(orange line). First, note that SuperServe operates at an accuracy range of
$76-78\%$ and never selects a higher accuracy subnetwork such as the
subnetwork of $80.16\%$ accuracy. This is because the subnetwork of $80.16\%$
accuracy diverges at the mean ingest rate of $7000$ qps (also seen in Fig. 8
last row). Hence, SuperServe automatically selects appropriate subnetworks for
different mean ingest rates. Moreover, SuperServe uses lower accuracy models
more frequently with increasing $CV^{2}_{a}$. This is because increased jitter
reduces query slack, causing SlackFit to pick lower latency buckets more
often. This corroborates the trend seen in Fig. 8 where the mean serving
accuracy of SuperServe monotonically decreases as $CV^{2}_{a}$ increases.
Lastly, during the load spikes, SlackFit usually selects control parameters
with high batch size and smaller subnetwork (§4.2.1). This control decision
allows SuperServe to drain the queue faster, resulting in a high SLO
attainment on the traces (R1).

Fig. 12(b) shows the system dynamics for the time-varying traces. $\tau=5000$
$q/s^{2}$ (blue line) increases the ingest rate from $2500$ qps to $7400$ qps
faster than $\tau=250$ $q/s^{2}$. For both the traces, SuperServe dynamically
changes the accuracy from $\approx 79.2$ to $\approx 77.5$ as mean ingest rate
increases. SuperServe’s ability to dynamically adjust accuracy helps it
achieve a higher mean serving accuracy (R2) compared to serving a single model
statistically. Moreover, for $\tau=5000$ $q/s^{2}$, SuperServe jumps to lower
accuracy and higher batch size control parameters quickly. While, for for
$\tau=250$ $q/s^{2}$, SuperServe uses intermediate models to serve the
intermediate ingest rate during $\approx 60-80$ seconds. A higher $\tau$ value
forces query’s slack to reduce drastically. Hence, SlackFit rapidly switches
to selecting control parameters of smaller subnetwork and higher batch size
from the low latency buckets (§4.2) to satisfy deadlines (R1). Therefore,
increase in $\tau$ decreases mean serving accuracy (a trend observed in Fig. 9
across the rows).

(a) Dynamic accuracy and batch size control: bursty traces

(b) Dynamic accuracy and batch size control: time-varying

Figure 12: System Dynamics on Synthetic Traces. Accuracy and batch size
control decisions shown over time in response to ingest throughput (q/s). (a)
bursty traces $\lambda=7000=(\lambda_{b}=1500)+(\lambda_{v}=5500)$ with
burstiness of $CV^{2}_{a}=2$ (orange) and $CV^{2}_{a}=8$ (blue). (b) time
varying traces accelerate from $\lambda_{1}=2500$ q/s to $\lambda_{2}=7400$
q/s with acceleration $\tau=250q/s^{2}$ (orange) and $\tau=5000q/s^{2}$
(blue). Batch size and subnetwork activation control choices over time show
how SuperServe reacts to each of the four plotted traces in real time. This
illustrates dynamic latency/accuracy space navigation.

###  A.3 Scheduling policies

(a) Latency Heatmap

(b) Control Choices

Figure 13: SlackFit control parameter space. (a) latency heatmap for six
different (uniformly sampled w.r.t. FLOPs) pareto-optimal subnets in SubNetAct
as a function of accuracy (x-axis) and batch size (y-axis). The latency is
monotonic with batch size and accuracy. (b) the number of available choices
decrease as latency increases.

The core functionality of the SuperServe’s scheduler is to maximize (a) SLO
attainment and (b) prediction accuracy for any arrival trace dynamics. The
scheduler offers a pluggable policy framework to support any application
sensitivity to these metrics by allowing arbitrarily different trade-offs
between them. SuperServe policy interface dictates that control decisions are
made w.r.t. the batch size and subnetwork to activate. Both of these control
parameters affect SLO attainment and serving accuracy. This is because the
scheduler a) perpetually operates under a latency constraint and b) these
control decisions have a cumulative effect over time (e.g., higher accuracy
affects queue build-up later). Finding a globally optimal set of batch size
and subnetwork control tuples over time is NP-hard. As our control decisions
must be made on the critical path of queries’ end-to-end latency, quick sub-
millisecond control decision making is a key performance requirement. Thus, to
meet the real time requirements, we primarily consider scheduling policies
that are greedy w.r.t. time. The policies decide the batch size and subnetwork
based on the remaining slack of the most urgent query. The slack is calculated
using a fast (sub-ms) $O(1)$ EDF queue lookup operation.

###  A.4 Control Parameter Space

The control parameter space of the scheduling policies is created using
SuperServe’s supernetwork profiler (Fig. 13(a)) by profiling latency as a
function of subnetwork accuracy and batch size. With $B$ possible batch size
choices and $S$ different subnetworks to serve the size of the control
parameter space is $B\times S$. All the scheduling policies use this space to
inform their trajectory through the latency/accuracy trade-off space.

Insights.  We draw some key insights from the control parameters’ space in
Fig. 13(a). (I1) the latency increases monotonically with batch size. (I2) the
latency increases monotonically with accuracy. (I3) the number of control
choices decreases with latency increase (Fig. 13(b))444this occurs due to
choice of power of 2 batch-size (which are granular enough to observe
reasonable latency differences) and availability of fewer model choices at
higher latency range.. These insights inform scheduling policy implementation
in in SuperServe. The larger batch size incurs sub-linearly higher latency,
which helps increase system throughput. Thus, it is always beneficial to
maximize batch size subject to the latency constraints. By increasing system
throughput, the systems utilization increases, serving more queries in the
same amount of time, which helps the SLO attainment. At the same time, a
policy may also favor more accurate subnetworks subject to query latency
constraints. This increases the overall accuracy of predictions rendered by
the system, improving application-visible quality of service. Thus, batch size
and accuracy forms two levers of control to maximize both SLO attainment and
prediction accuracy.

###  A.5 Policy Design Space

MaxBatch Policy. This policy first maximizes the batch size and then the
accuracy. It greedily finds a maximal batch size ($b$) for the smallest
accuracy subnetwork that fits within latency slack $\theta$.Within the chosen
batch size MaxBatch finds the maximum accuracy subnetwork ($s$) such that the
profiled latency $L(b,s)<\theta$ . It returns the control choice $(b,s)$. This
policy leverages insights (I1) and (I2). It takes O($log(B)$) operations to
find $b$ and O($log(S)$) operations to find $s$ (binary search on
monotonically increasing latency w.r.t. batch size and accuracy). As a result,
this lightweight policy scales well with the profile table, taking only
O($log(B)+log(S)$) operations to make control decisions.

MaxAcc Policy. MaxAcc first maximizes the accuracy and then the batch size.
Mirroring MaxBatch, MaxAcc performs a binary search for the largest accuracy
($s^{\prime}$) with $L(1,s^{\prime})<\theta$ first. Then, it finds the maximal
batch size ($b^{\prime}$) keeping the subnetwork choice fixed to the chosen
$s^{\prime}$, such that $L(b^{\prime},s^{\prime})<\theta$ ms. Similarly to
MaxBatch policy, it leverages insights (I1) and (I2) and takes
O($log(B)+log(S)$) operations to return the control choice
$(b^{\prime},s^{\prime})$.

The proposed SlackFit Policy. This is our best performing policy. At a high
level, SlackFit partitions the set of feasible profiled latencies into evenly
sized latency buckets. Each bucket consists of control tuples $(b,s)$ with
$L(b,s)$ within the range of bucket width. Then the policy chooses a bucket
with latency $\leq\theta$. Finally, from the choices within the selected
bucket, it picks the control choice that maximizes batch size. Intuitively,
selecting control parameters closest to slack $\theta$ configures the system
to operate as close to capacity as possible.In other words, choices with
latency less than that either reduce the throughput capacity or the serving
accuracy, eventually lowering system’s SLO attainment and accuracy. This draws
on the monotonicity insights (I1) and (I2). SlackFit’s novelty is in insight
(I3). We observe that SlackFit dynamically detects and adapts to the runtime
difficulty of the trace. A well-behaved trace (e.g., low ingest rate,
variation, acceleration) results in higher $\theta$. Higher $\theta$ leads to
the choice of higher latency buckets. And higher latency buckets are
correlated strongly with fewer control tuple choices (Fig. 13(b)), maximizing
the probability of choosing higher accuracy models! Conversely, mal-behaved
traces (higher ingest rate, variation, acceleration) lead to lower latency
bucket choices, as the scheduler is operating under much lower $\theta$
conditions. There are more control choices in lower latency buckets, which
leads to control tuples within those buckets to favor higher batch sizes. This
leads to processing the queue faster!

Experiment Result. In Fig. 11(c) we show that SlackFit achieves the best
tradeoff w.r.t. our success metrics compared to both MaxAcc – a policy that
greedily maximizes accuracy and MaxBatch — a policy that greedily maximizes
batches. The traces used mean $\lambda=7000$ qps
($(\lambda_{b}=1500)+(\lambda_{v}=5550)$) and
$CV^{2}_{a}\in\left\\{2,4,8\right\\}$. SlackFit reaches the highest SLO
attainment($0.999$) for all $CV^{2}_{a}$. MaxBatch starts under performing
w.r.t. SLO attainment with $CV^{2}_{a}$ increase. The SlackFit and MaxBatch
difference is most pronounced at the highest $CV^{2}_{a}$, eventually causing
a significant 5% drop in the SLO attainment. Both policies maximize the batch
size within latency slack $\theta$ when operating under small $\theta$. When
$\theta$ increases, however, MaxBatch continues to maximize the batch size
unconditionally—a greedy choice that leads to packing larger batches. This
greedy decision causes more time to be spent in a worker compared to SlackFit,
which adaptively shifts to higher accuracy models under larger $\theta$
conditions with compound effect on queued queries, eventually missing their
SLOs. maxAcc is unable to keep up with this trace. It never switches to policy
decisions that process the queue faster. This policy comparison shows a
continuum between faster queue processing and serving higher accuracy, with
SlackFit automatically finding the best point in this continuum.

##  Appendix B Serving fixed accuracy points

Experiment setup. The experiments were run for the MAF trace with the mean
ingest rate of $4,000$ queries per second. The MAF follows a poisson-like
distribution with $CV_{a}^{2}=1$ and the latency $SLO$ for each of these
requests was set to $30ms$. The scheduler at the router adaptively batches the
requests, along with an appropriate model based on the scheduling policy. The
query-batch and model configuration is then sent to one of the 6 workers, each
of which had an NVIDIA RTX 2080Ti GPU.

Results. In the plots, the red solid line represents the latency and accuracy
range of all available models. Any query with remaining slack (ms) in the
latency range spanned by the models can be served. It must be noted that while
the system can serve queries with remaining slack higher than the right-
interval red-line latency, queries with remaining slack lower than left-
interval red-line latency cannot be serviced and must be dropped. The goal
across policies is to manage the queue such that the remaining slack remains
within the model latency range, while maximizing accuracy.

For the $6$ Clipper$+$ experiments, the scheduler is constrained to provision
all request-batches with just a single model choice. This greatly affects the
system throughput, queueing delays and the SLO attainment.

  * •

While the lower accuracy models ($73.82$, $76.69$ and $77.64$) have low
inference latencies, they are able to serve the request batches within the SLO
deadlines with low queueing delays. Hence they achieve $99\%+$ latency $SLO$
attainment. This can also be seen from Fig 14 (a-c) where the remaining slack
latency is right-skewed and around $30ms$, which is the per-query latency
deadline.

  * •

On the other hand, higher accuracy models ($78.25$, $79.44$ and $80.16$) have
significantly higher inference latencies. This leads to higher per-request
serving time, higher queueing delays and lower SLO attainment. This can be
seen from Fig 14 (d-f) where the distribution begins to shift leftwards
towards lower remaining slack indicating significant queueing delays and lower
SLO attainment.

The above results show that fixed-accuracy scheduling is insufficient to
provide the best accuracy-SLO attainment tradeoff across different model
choices, for any given arrival-trace.

SlackFit on the other hand performs dynamimc model selection throughout the
models’ latency range. This provides the scheduler several choices to maximize
accuracy (higher accuracy models) during low loads and also leverage the lower
accuracy models during high loads. This policy serves multiple accuracy points
to help absorb queue build-up and mitigate queueing delays. Since Fig 15(a)
shows that the density function is always below the supernetwork latency
range, $>99\%$ queries meet their deadline, while also maximizing serving
accuracy.

(a) Clipper+($73.82$)

(b) Clipper+($76.69$)

(c) Clipper+($77.64$)

(d) Clipper+($78.25$)

(e) Clipper+($79.44$)

(f) Clipper+($80.16$)

Figure 14: Serving fixed accuracy points (a) SlackFit  Figure 15: Serving
multiple accuracy points