# A Tale of Two Scales: Reconciling Horizontal and Vertical Scaling for
Inference Serving Systems

Kamran Razavi  Paderborn University
Technical University of Darmstadt ,  Mehran Salmani  Ilmenau University of
Technology ,  Max Mühlhäuser  Technical University of Darmstadt ,  Boris
Koldehofe  Ilmenau University of Technology and  Lin Wang  Paderborn
University

###### Abstract.

Inference serving is of great importance in deploying machine learning models
in real-world applications, ensuring efficient processing and quick responses
to inference requests. However, managing resources in these systems poses
significant challenges, particularly in maintaining performance under varying
and unpredictable workloads. Two primary scaling strategies, horizontal and
vertical scaling, offer different advantages and limitations. Horizontal
scaling adds more instances to handle increased loads but can suffer from cold
start issues and increased management complexity. Vertical scaling boosts the
capacity of existing instances, allowing for quicker responses but is limited
by hardware and model parallelization capabilities.

This paper introduces Themis, a system designed to leverage the benefits of
both horizontal and vertical scaling in inference serving systems. Themis
employs a two-stage autoscaling strategy: initially using in-place vertical
scaling to handle workload surges and then switching to horizontal scaling to
optimize resource efficiency once the workload stabilizes. The system profiles
the processing latency of deep learning models, calculates queuing delays, and
employs different dynamic programming algorithms to solve the joint horizontal
and vertical scaling problem optimally based on the workload situation.
Extensive evaluations with real-world workload traces demonstrate over
$10\times$ SLO violation reduction compared to the state-of-the-art horizontal
or vertical autoscaling approaches while maintaining resource efficiency when
the workload is stable.

††copyright: none††ccs: Computer systems organization Cloud computing††ccs:
Computer systems organization Reconfigurable computing

##  1\. Introduction

Cloud-based deep learning (DL) inference is a common component in modern
intelligent applications and services, often involving multiple DL models
interconnected in a dataflow multi-model (pipeline) system (Razavi et al.,
2022). An example is a real-time video analytics application for traffic
management, which may include models for video frame extraction, object
detection, object classification, and tracking (Elhoseny, 2020). The
performance of such systems is mostly evaluated based on two indicators: user
satisfaction, quantified through Service Level Objectives (SLOs) mainly on the
end-to-end latency (Gujarati et al., 2017), and resource efficiency (Zhang et
al., 2019), referring to the optimal utilization of computational resources.
These performance indicators ensure the delivery of high-quality results while
efficiently using resources, which is crucial for the scalability and
sustainability of cloud-based DL applications (Luo et al., 2022; Razavi et
al., 2022; Zhang et al., 2019; Gunasekaran et al., 2022; Ali et al., 2020;
Mounesan et al., 2024).

Efficient resource management in DL inference serving systems is crucial to
maintaining system performance, especially under variable and unpredictable
workloads (Razavi et al., 2024; Salmani et al., 2023). Two primary scaling
strategies are often used to manage these dynamic workloads: horizontal and
vertical scaling. Horizontal scaling involves the addition of more instances
of the same DL model to handle increased loads, facilitating workload
distribution without altering the resource configuration of existing
instances. By distributing the workload across several instances, horizontal
scaling can handle large workloads and maintain performance as demands grow.
However, bringing up new instances in horizontal scaling involves cold start
issues (LeMay et al., 2020; Luo et al., 2022; Pavlenko et al., 2024; Romero et
al., 2021a) due to booting up additional instances, configuring them, and
joining them into the system, which can take several seconds to minutes. The
cold start issue reduces system responsiveness when the workload changes
unpredictably, leading to SLO violations and reduced user satisfaction.
Additionally, horizontal scaling increases system management’s complexity,
requiring more sophisticated load balancing.

Vertical scaling, conversely, focuses on adding resources such as CPU cores to
existing DL model instances, thereby boosting the capacity of existing
instances to handle more tasks simultaneously. A recently announced feature
named in-place vertical scaling (Authors, 2023) by Kubernetes (Foundation,
2019)—a dominant open source system to orchestrate and manage the containers
in the system—allows additional resources to be added to existing instances
without the need for rebooting or downtime, offering a significant advantage
concerning the cold start issue. Additional computing resources, such as extra
CPU cores, allow inference requests to be batched and processed concurrently,
improving the system throughput. This capability enables a much quicker
response to increased load compared to setting up new instances as required in
horizontal scaling. While vertical scaling can provide rapid speed-up by
instantly increasing the resources of a single instance, it is often limited
by the physical capabilities of the hardware and the parallelizability of the
DL model. Once those limits are reached, no further speed-up is possible, thus
reaching the maximum throughput. In contrast, horizontal scaling can continue
to expand by adding more instances. Furthermore, vertical scaling can lead to
higher costs due to the need for high-end hardware, and it presents a single
point of failure risk, where if the single instance fails, it can
significantly impact system stability.

Existing inference serving systems mainly focus on horizontal scaling mainly
due to the benefits of the scalability of horizontal scaling and the
limitations of vertical scaling. Studies like INFaaS (Romero et al., 2021a)
focus on individual DL models where horizontal scaling is used in response to
workload changes by bringing up new virtual machines. Others have considered
DL pipelines and use horizontal scaling to optimize resource costs by
switching between hardware types or model variants when the workload changes
(Crankshaw et al., 2020; Ghafouri et al., 2024; Razavi et al., 2022). All of
the mentioned approaches suffer from cold start issues when facing dramatic
workload increases. Sponge (Razavi et al., 2024) uses in-place vertical
scaling and changes the CPU allocation of the running instance to absorb the
sudden changes in the workload. However, they only consider a single DL model
and ignore the challenges behind the data dependency of pipeline inference
serving systems. Moreover, their approach suffers from SLO violations under
high request rates that are beyond the capabilities of one powerful instance
due to parallelization and physical hardware limitations, as discussed above.
In short, existing autoscaling solutions suffer from non-responsiveness under
high workload variability, and to compensate for that, they require a
significant level of over-provisioning. Ideal autoscaling should be
responsive, meaning it can immediately react to sudden workload changes, and
resource-efficient, avoiding over-provisioning, while limiting SLO violations
by ensuring end-to-end inference latency.

In this work, we explore how to reduce SLO violations and resource costs by
studying an autoscaling mechanism that combines both vertical and horizontal
scaling mechanisms and leverages the benefits of both mechanisms in the
pipeline inference serving system. Based on the insights from such an
exploration, we design an autoscaler, named Themis, that uses a two-stage
autoscaling strategy, where it first leverages the responsiveness
characteristics of in-place vertical scaling to absorb the unpredictable surge
of requests in the workload. Second, Themis performs horizontal scaling to
optimize resource efficiency when the workload tends to stabilize by
transitioning to a set of less powerful instances.

To be precise for the vertical scaling strategy, after getting the application
pipeline with its SLO, Themis addresses the challenges regarding the in-place
vertical scaling decision-making in pipelines by first profiling the
processing latency of all the DL models with respect to different CPU and
batch size allocations, and calculating the queuing delay based on the given
batch size and the arrival rate. Next, Themis finds the right amount of
resources to serve the incoming workload (avoiding under- or over-
provisioning) for all the models in the system, in a single shot, by
encapsulating the autoscaling problem in an Integer Program (IP) and solving
it using dynamic programming. In contrast to existing solutions where
heuristics are used for scaling decision-making that results in sub-optimal
solutions, we use dynamic programming to solve the IPs which generates optimal
solutions by breaking the problem into simpler subproblems and solving each
subproblem only once, storing their solutions to avoid redundant calculations.
For the transitions between vertical and horizontal scaling strategies, Themis
analyzes why an autoscaler needs to switch between scaling strategies, how to
transit between them, and when to do it. For that, Themis designs a state
transition policy to decide when to use which autoscaling strategy and uses it
during runtime to enable responsiveness and resource efficiency while
guaranteeing end-to-end inference latency.

In short, this paper makes the following contributions. After presenting the
motivation and identifying the challenges (§2), we

  * •

present the design of Themis, including its overall architecture and system
components (§3);

  * •

introduces an integer program to capture the vertical and horizontal resource
scaling problem in DL inference serving systems and present our solutions
based on dynamic programming (§4);

  * •

build a system prototype for Themis and evaluate it with real-world workload
traces (§6). Overall, Themis reduces the SLO violation by over $10\times$
compared to the baselines.

§7 summarizes related work. §8 draws final conclusions.

##  2\. Background and Motivation

Inference services, a critical component of online platforms and mainly
composed of multiple models that are chained together, have unique
characteristics that make them both latency-sensitive and resource-intensive.
The latency sensitivity of these services arises from their interaction with
online users. Users expect quick responses when interacting with these
services, making delay or latency undesirable. On the other hand, inference
services are also resource-intensive due to the heavy computations they need
to perform (Gujarati et al., 2020; Crankshaw et al., 2020). The dual
characteristics of latency sensitivity and resource-intensiveness make
designing and managing inference services challenging. It is essential to find
a balance between providing quick responses to user interactions and managing
the heavy computational resources required by these services.

Figure 1. Vertical scaling vs. horizontal scaling reaction time in case of
workload bursts. Horizontal scaling is not responsive. The gray area indicates
SLO violation. Figure 2. Using vertical and horizontal scaling jointly to
absorb bursts and reduce operational costs. Vertical scaling provides
responsiveness, while horizontal scaling provides cost efficiency. The gray
area indicates SLO violation.

Figure 1 depicts the vertical and horizontal scaling response time of a ResNet
car detection model (He et al., 2016) to the workload changes under the SLO of
1000 ms. The number of requests starts from 20 requests per second (RPS) and
then rises $6\times$ (to 120 RPS) for 5 seconds and then drops back to 20 RPS.
If the system captures the workload changes immediately and uses horizontal
scaling, the new instances will become available after 5-6 seconds as
evaluated in (Razavi et al., 2022). In this scenario, all the requests (100)
in that short period will violate their SLO, and the scaling decisions cannot
capture the burstiness and waste resources until a new scaling decision is
made. On the other hand, by using in-place vertical scaling, we can change the
computational resources of the available DL models and absorb the burstiness
almost instantly (with an overhead of less than 100 ms). Next, as the workload
decreases, we reduce the allocated resources, reducing operational costs.
Using in-place vertical scaling for a short duration of 5 seconds, we could
reduce the SLO violation rate by roughly $5\times$. It should be noted that
the amount of resources in vertical scaling is higher than in horizontal
scaling, as discussed in the previous section, meaning that horizontal scaling
provides higher throughput. The next question arises: can we switch to
horizontal scaling after we absorb the burstiness with vertical scaling?
Figure 2 answers this question by suggesting that when the workload becomes
stable again (the stabilization is discussed in Section 5.1.2), we can switch
to horizontal scaling and reduce the operational cost by 40% in this simple
car detection scenario. Therefore, a combination of vertical and horizontal
scaling can react to workload changes fast enough, simultaneously reducing
total resource consumption.

Table 1. Comparison of Themis with previous works; Pipeline: A chain of models or just a single model? Resource Efficiency: Does this work use horizontal scaling for the highest resource efficiency? Responsiveness: Does this approach use in-place vertical scaling to respond quickly to the changes in the workload? ($\ast$) uses model-variants as a way of vertical scaling. System | Pipeline | Resource Efficiency | Responsiveness
---|---|---|---
INFaaS | ✕ | ✓ | ✕$\ast$
InferLine | ✓ | ✓ | ✕
GrandSLAm | ✓ | ✕ | ✕
FA2 | ✓ | ✓ | ✕
Scrooge | ✓ | ✓ | ✕
Cocktail | ✕ | ✕ | ✓
InfAdapter | ✕ | ✓ | ✕$\ast$
IPA | ✓ | ✓ | ✕$\ast$
Sponge | ✕ | ✕ | ✓
Themis | ✓ | ✓ | ✓

Table 1 presents an overview of related latency-sensitive inference serving
systems. While most of the previous works use only horizontal scaling or
model-variant changes for resource efficiency, they all suffer significantly
from rapid changes in the workload if they do not over-provision their
resources, which directly impacts operational costs negatively. On the other
hand, the only work that considers responsiveness using vertical scaling in
terms of changing the resources (not the model variant or model ensemble)
becomes unpractical when the workload surpasses the capacity of one DL model
with the highest possible resource allocation (hardware limitation).
Furthermore, it does not consider pipeline, hence the challenges of data
dependency using in-place vertical scaling are not addressed.

##  3\. Themis

In this section, we first discuss the challenges of designing a new autoscaler
that benefits from both vertical and horizontal autoscaling mechanisms. Next,
we give an overview of Themis, its architecture, and the main components.
Finally, we discuss the assumptions and the limitations of Themis.

###  3.1. Challenges

We have identified the following challenges in designing a new strategy that
symbiotically combines both horizontal and vertical scaling:

Data dependency [dd]. The resource allocation decision becomes even more
challenging when DL models have data dependencies (pipelines) in the serving
system since the resource scaling decision for one DL model may affect
downstream DL models. Therefore, we need a fast enough approach to find
solutions for all the DL models in the pipeline in a single shot.

Adaptation period [ap]. After using vertical scaling, we need to identify when
is a good time to switch to horizontal scaling to save resources. To be
precise, we need to find an answer to this question: “How to correctly predict
that the workload is stable enough that we do not need to allocate extra
resources for vertical scaling?”

Hardware limitation for vertical scaling [hl]. One of the drawbacks of
vertical scaling compared to horizontal scaling is that the DL model’s maximum
capacity is bound to the hardware capabilities. Every hardware has a maximum
limit for processing power; once it is reached, the DL model cannot scale up
any further. Thus, we must find a placement algorithm for assigning DL models
in a pipeline in a distributed cluster.

Batch size [bs]. Apart from resource allocation and resource placement in
inference serving systems, there is a dominant factor that directly affects
the latency and throughput of DL models, named batch size. The batch size can
be changed online to increase the DL model’s throughput based on the demand at
the cost of higher inference latency. As a result, we need to find the optimal
batch size. Large batches can significantly impact the response time of
requests within a batch. On the other hand, small batches might miss out on
opportunities for improved throughput and cost efficiency.

###  3.2. System Design

Figure 3. An overview of the Themis architecture. The executor receives the
requests and processes them. The monitor service collects the metric data from
the stages. The optimizer makes both vertical and horizontal scaling decisions
for the DL models. The Adapter enforces the scaling decisions by configuring
the queues and the executor.

Figure 3 provides an overview of Themis. The system comprises five main parts
(profiler, executor, monitor, optimizer, and adapter). The profiler creates a
new performance model for any registered DL model in the system. The stage
component gets the requests and executes the DL model. The monitor component
keeps track of the pipeline’s request rate (workload distribution). The
optimizer uses data from the monitor and the profiler components to find an
optimal resource allocation solution based on in-place vertical or horizontal
scaling. Finally, the adapter enforces the decisions made by the optimizer to
the system.

The profiler component sends profiling requests to the DL model with different
configurations (different CPU and batch size allocations) (answering [bs]). It
then records the latencies under each configuration and uses them to create
the performance model of each DL model in the system. Furthermore, these
latency profiles are used for in-place vertical scaling in the optimizer. Note
that this component runs offline, and the performance profiles generated by
this component will be used online.

The executor consists of multiple stages, each of which is composed of the
queuing and the model processing parts. Each stage has one centralized queue
and one or more processing model instances. The queuing component fetches the
requests from the user or other stages, sends the arrival rate statistic to
the optimizer, batches the requests based on the optimizer’s decision, and
sends the batches to their associated models for inference. It uses a round-
robin approach to distribute batches among the processing instances (decided
by the optimizer) in its stage. The processing instance has the DL model and
the computing power (determined by the optimizer based on the incoming
workload) to process the batches sent by the stage queuing component. After
processing the batches, the instance sends the results to the next stage or
the user. Both components keep track of the queuing and processing latencies.
In the last stage, a query with the gathered latencies is generated and sent
to the monitor component for further analysis.

The monitor gets the arrival rate statistics from the first stage queue and
the total request latency from the last model instances. The optimizer will
fetch the arrival rate statistics to find optimal resources and batch sizes
for the whole system while guaranteeing end-to-end request latencies, and the
total request latency will be used to report the system and the profiler’s
performance. To reduce the monitor overhead, we append the latencies to the
same request as they pass through different pipeline stages.

The optimizer gets the arrival rate from the first queuing component and feeds
it to the horizontal autoscaler. Next, it uses an LSTM predictor to estimate
the highest workload in the following 10-second time window and feeds the
predicted workload to the horizontal autoscaler (answering [ap]). The
horizontal scaling results are sent to the adapter if no additional resources
are required. If not, the optimizer checks if there are enough physical
hardware resources for using in-place vertical scaling to support the current
workload (answering [hl]). If there are enough resources, the system uses in-
place vertical scaling to respond to changes in the workload by finding the
optimal resource allocation for all the DL models in the system in a single
shot (answering [dd]). If not, the optimizer calculates the maximum throughput
using vertical scaling and switches to horizontal scaling for the remaining
requests.

The adapter is responsible for enforcing the configurations made by the
optimizer to the cluster. The configurations for each DL model in the system
are batch size, resource allocation of model instances, and the number of
instances. After the new configuration is received from the optimizer, the
adapter first compares the new set of configurations with the current state of
configurations. If there are changes, the adapter makes two calls for each
model’s new configuration, one to the queue for adjusting the batch size and
one to the executor to adjust the computing resources of the models (vertical
scaling) or change the instance number of the model (horizontal scaling). The
batch size will be immediately updated, and changes in the computing resources
will be almost instant (less than 100 ms). The scale in/out of the instances
will take seconds (roughly 5-6 seconds).

###  3.3. Assumptions and Limitations

The in-place vertical scaling part of Themis uses the vertical scaling feature
of Kubernetes, which currently is on the alpha branch and only supports CPU
and memory real-time modification. However, inference serving systems can
benefit greatly from other accelerators, such as GPUs and TPUs, which,
unfortunately, are not supported at this moment. Also, Themis uses simple
queuing management, whereas a more complex queuing simple may provide a more
accurate queuing latency. Moreover, multiple variants for the same DL models
with different properties, such as accuracy/latency trade-offs, can be
leveraged to reduce costs further. Finally, we consider uniform SLOs, where
all DL inference requests in the system have the same end-to-end latency SLO
requirement.

##  4\. Autoscaling Problem

In this section, we provide a mathematical representation of the joint
horizontal-vertical autoscaling problem in an inference serving system to
react to the changes in the workload. We encapsulate the joint autoscaling
problem into an Integer Program (IP) that decides the batch size, computing
resource, and the number of instances of each DL model in the system in a
single shot. The goal of the IP is to minimize the cost while guaranteeing the
requests SLO. It achieves it by using vertical scaling when there are sudden
changes in the workload to capture the workload burstiness. Furthermore, when
the workload is stable (see Section 5.1.2), the IP switches to horizontal
scaling to save operational costs. We use different dynamic programming
approaches to solve the IP based on the workload status.

###  4.1. Performance Profiling

A DL model processes requests with different latencies based on the allocated
computational resources and batch sizes. Previous works have shown that
processing latency has a linear/quadratic relationship with batch size (Kannan
et al., 2019; Razavi et al., 2022). Sponge (Razavi et al., 2024) has shown
that the processing latency relationship is inverse to the core allocation in
inference serving systems. We follow the same guidelines and use the following
formula to build a performance profile for each DL model in the system:

(1) $\begin{split}l(b,c)=&\frac{\gamma\times
b}{c}+\frac{\epsilon}{c}+\delta\times b+\eta.\end{split}$

Formula 1 predicts the processing latency with the given batch size ($b$) and
computing resources ($c$) of the DL model. We execute the DL model with
different batch sizes and resource allocation configurations to find the
static variables ($\gamma,\epsilon,\delta,\eta$) to get the processing
latencies. We then use the latency data and fit the above formulation to get
the DL performance profile. We perform the same approach offline for all the
DL models in the system and create a unique performance profile for each.

All the used notations are available in Table 2.

Table 2. Notations Symbol |  Description
---|---
$S$ |  Set of all models for an application
$SLO$ |  Latency SLO of the application
$n_{s}$ |  number of instances of model $s\in S$
$b_{s}$ |  batch size of model $s\in S$
$c_{s}$ |  CPU core allocation of model $s\in S$
$\lambda$ |  Request arrival rate
$l_{s}(b,c)$ |  Processing time of model $s\in S$ with allocation core $c$ and batch size $b$
$q_{s}(b)$ |  Queuing time of model $s\in S$ with batch size $b$
$h_{s}(b,c)$ |  Throughput of model $s\in S$ with allocation core $c$ and batch size $b$

###  4.2. Queue

Due to the differences in the number of DL instances, computing resources, and
batch size, the DL model instances process requests with different latencies.
Also, to form the batches to increase the system performance, the first
request in the batch must wait for the arrival of the last request in the
batch, causing an extra queuing delay. Because of the mentioned reasons, the
requests in batches leave the queue at different speeds (i.e., the last
request in the batch leaves the queue immediately, and the first request in
the batch must wait the longest, hence it has the slowest speed in terms of
leaving the queue), causing a dynamic queuing latency. FA2 (Razavi et al.,
2022) uses Equation (2) for the worst-case scenarios. The worst-case scenario
can happen when there are no available instances (out of the n instances for
the same DL model) to process the current batch (meaning that all $n$
instances are busy and the next batch needs to wait for one of the instances
to be free ($l(b)-\frac{nb+1}{\lambda}$)) or the first request waits for the
arrival of the last request in the same batch ($\frac{b-1}{\lambda}$).
Therefore, the worst case is the maximum of these two equations, as shown in
the following equation.

(2) $q(b,n)=\max\left(\frac{b-1}{\lambda},l(b)-\frac{nb+1}{\lambda}\right).$

However, they do not consider the speed-up/down caused by changing the
computing resources of the DL model instances, which directly affects the
queuing drainage. Therefore, we propose the following equation to incorporate
the computing resources in the DL model as well:

(3)
$q(b,c,n)=\max\left(\frac{b-1}{\lambda},l(b,c)-\frac{nb+1}{\lambda}\right).$

Similar to FA2, we argue that the worst-case scenario happens for the latter
scenario, where the first request needs to wait for the last request of the
same batch due to the fact that by increasing the computing resources and
reducing the processing latency, the DL models catch up with the workload.
This means that the aggregate throughput of all the instances will equal or
exceed the workload, i.e., $n\times h(b,c)\geq\lambda$, i.e., the second part
of the above equation is always less than zero. Therefore, we use a simplified
queuing latency prediction as:

(4) $q(b)=\frac{b-1}{\lambda}.$

###  4.3. Problem Formulation

The goal of the optimizer is to decide the least amount of allocated resources
of all instances ($\sum_{s\in S}n_{s}\times c_{s}$), subject to guaranteeing
the end-to-end latency of requests and supporting the workload.

The end-to-end latency of a request is the aggregation of queuing and
processing latencies of all the stages in the pipeline, which should be lower
than the given SLO:

(5) $\text{End-to-End Latency}=\sum_{s\in
S}l_{s}(b_{s},c_{s})+q_{s}(b_{s})\leq SLO.$

To maintain system stability, the combined throughput of all instances of a
stage must meet or exceed the request rate. Formally, for any stage, the
product of its instance’s throughput and the number of instances should be
greater than or equal to the sum of request rates across all instances, i.e.,
$s\in S$, $h_{s}(b_{s},c_{s})\times n_{s}\geq\lambda$. This constraint ensures
adequate provisioning for all stages, effectively managing the queuing of
inference requests at each stage.

The problem can be formulated with the following IP:

(6) $\displaystyle\min$ $\displaystyle\sum_{s\in S}n_{s}\times c_{s}$ subject
to $\displaystyle\sum_{s\in S}l_{s}(b_{s},c_{s})+q_{s}(b_{s})\leq SLO$
$\displaystyle\lambda\leq h_{s}(b_{s},c_{s})\times n_{s},\forall s\in S$
$\displaystyle b_{s},c_{s},n_{s}\in\mathbb{Z}^{+},\forall s\in S$

The last constraint in Equation 6 states that the batch sizes and number of
instances should be positive. Next, we solve the above IP with different
approaches based on the current workload situation.

###  4.4. Optimizer

Two dynamic variables per stage affect the total cost significantly and can be
adjusted in the IP from the previous section, namely core allocation, $c$, and
instance number, $n$. The former is used in vertical scaling (changing the
processing latency of a model), and the latter is used in horizontal scaling
(distributing the workload to multiple instances). As we explain in Section 5,
vertical scaling is not the most cost-efficient mechanism for serving requests
compared to horizontal scaling, but the in-place vertical scaling feature is
more responsive when there are changes in the workload. Therefore, we solve
the IP with two different mindsets, using vertical scaling to respond quickly
or saving more resources with horizontal scaling.

However, a similar IP cannot be solved efficiently in real-time as the problem
grows exponentially as the number of stages grows (Romero et al., 2021a;
Razavi et al., 2022; Ghafouri et al., 2024). Consequently, we need to use
heuristics or limit the solver to some extent (reducing the feasible space to
explore). We leverage the limited SLO (which is usually a few thousand
milliseconds), limited batch sizes (1-16), and limited core allocation
(limited to the hardware the model is placed on (1-16 CPU cores)) in inference
serving systems and provide dynamic programming algorithms to find the optimal
solution for either vertical or horizontal scaling. Both algorithms run in
$O(SLO\times b_{max}\times c_{max}\times|S|)$ time complexity, which reduces
the exponential execution time (dependent on the number of stages) to the
dominant SLO time by incorporating the space complexity using dynamic
programming. Section 5.1.3 discusses which algorithm to be executed at a given
time.

####  4.4.1. Vertical Scaling

As discussed above, we use dynamic programming to find the optimal solution
for the vertical scaling to absorb the sudden changes in the workload.

Algorithm 1 aims to find the optimal CPU allocations for the given pipeline
considering their performance profile and the specified SLO. The algorithm
takes the pipeline SLO, a set of models denoted by $S$ with their
corresponding performance profile, and the workload $\lambda$ as input and
returns the values $c_{s}$ and $b_{s}$ for all the DL models $s\in S$. Dynamic
programming solves the IP by first solving the problem with just having one
stage and then increasing it to the pipeline one by one. For any added model,
we consider all possible SLOs (1 to SLO) and divide the picked number into two
parts, one for the current DL model and one for the previous DL models. We
check whether it is possible with the current division to serve the workload
in all the DL models. We continue the procedure until all the models are
visited. In the end, if there is no possible solution, we use a binary search
on the workload to find the maximum possible workload supported by vertical
scaling and bring up new instances (horizontal scaling) to support the
remaining workloads.

input : SLO, Set of models $S$ and their latency model, $\lambda$

output : $c_{s},b_{s}\forall s\in S$

1 for  _$s$ in $[0,|S|,1]$_ do

2 for  _$i$ in $[SLO,-1,-1]$_ do

3 if  _(s == 0 and dp[s][i]) or s (!= 0 and dp[s - 1][i])_ then

4 for  _$c$ in $[1,c_{max}]$_ do

5 for  _$b$ in $[1,b_{max}]$_ do

6 l = calculate $l_{s}(b,c)$, q = $\frac{b-1}{\lambda}$

7 h = calculate $h_{s}(b,c)$

8 l += q

9 if  _$h\leq\lambda$ and $l\leq SLO$_ then

10 continue

11 if  _s == 0_ then

12 if  _$dp[s][i+l]$ is False_ then

13 $dp[s][i+l]$ = True

14 $best[s][i+l]$ = $(c,c,b)$

15

16 else if  _$dp[s-1][i]$ and i ¿ 0_ then

17 if  _$dp[s][i+l]$ is False_ then

18 $dp[s][i+l]$ = True

19 $best[s][i+l]$ = $(best[s-1][i][0]+c,c,b)$

20 else if  _$best[s-1][i][0]+c <best[s][i+l][0]$_ then

21 $best[s][i+l]$ = $(best[s-1][i][0]+c,c,b)$

22

23

24

25Check if there is a solution in dp[—S— - 1].

26 if  _No solution_ then

27 left = 1, right = $\lambda$

28 while  _right - left ¿ 1_ do

29 mid = (right - left) // 2

30 if  _Vertical scaling with $\lambda=mid$_ then

31 right = mid

32 else

33 left = mid

34 return Vertical Scaling with $\lambda=left$ and Horizontal Scaling with
$\lambda=\lambda-left$ with the same CPU as Vertical Scaling.

35 else

36 result = calculate recursively the optimal configurations for all the
models using best.

37 return result

Algorithm 1 Vertical Scaling

To be precise, we iterate first over the stages (line 1) and then iterate on
all possible SLO values with different batch sizes and core allocations (lines
2-5). Then, we estimate the total latency by calculating the processing
latency and then aggregating it with the queuing latency (lines 6-8). Next, if
the current throughput supports the incoming workload and the aggregated
latency is lower than the SLO, we check if the current model is the first in
the pipeline since there is no need to divide the current SLO. If so, we store
the current configuration (current CPU and batch size allocations) (lines
11-14). If not, we check if the current configuration is the least total
resource allocations with the current SLO division (lines 15-20). After
considering all the configurations, we check if there is a possible candidate
(line 21) by checking if the algorithm has reached the last DL model in the
pipeline. If not, we use binary search on the workload and feed it to the same
algorithm to find how much of the workload vertical scaling can support (lines
22-29). We then calculate the needed instances for serving the remaining
requests using horizontal scaling with the same CPU core allocations (line
30). If there is a valid configuration, we find the configurations for all the
models recursively (lines 31-33).

####  4.4.2. Horizontal Scaling

Similar to vertical scaling, we use dynamic programming to find the optimal
instance number (horizontal scaling) for all the DL models in the system in a
single shot. The main difference between the vertical and horizontal scaling
algorithms is that we can support any workload using horizontal scaling.
Hence, we calculate the number of needed 1-core instances (line 5), and we
calculate the least total resource-consuming configuration (lines 11-20) in
Algorithm 2. Finally, we recursively find the optimal number of instances for
all the models and send the results to the adapter for the system adaptation.

input : SLO, Set of models $S$ and their latency model, $\lambda$

output : $n_{s},b_{s}\forall s\in S$

1 for  _$s$ in $[0,|S|,1]$_ do

2 for  _$i$ in $[SLO,-1,-1]$_ do

3 if  _(s == 0 and dp[s][i]) or s (!= 0 and dp[s - 1][i])_ then

4 for  _$b$ in $[1,b_{max}]$_ do

5 l = calculate $l_{s}(b,1)$, q = $\frac{b-1}{\lambda}$

6 h = calculate $h_{s}(b,1)$

7 l += q

8 if  _$h\leq\lambda$ and $l\leq SLO$_ then

9 continue

10 ins = workload // throughput

11 if  _s == 0_ then

12 if  _$dp[s][i+l]$ is False_ then

13 $dp[s][i+l]$ = True

14 $best[s][i+l]$ = $(ins,ins,b)$

15

16 else if  _$dp[s-1][i]$ and i ¿ 0_ then

17 if  _$dp[s][i+l]$ is False_ then

18 $dp[s][i+l]$ = True

19 $best[s][i+l]$ = $(best[s-1][i][0]+ins,ins,b)$

20 else if  _$best[s-1][i][0]+ins <best[s][i+l][0]$_ then

21 $best[s][i+l]$ = $(best[s-1][i][0]+ins,ins,b)$

22

23

24

Algorithm 2 Horizontal Scaling

##  5\. Transition

In this section, we explain the necessity of transitioning to horizontal
scaling after initially using in-place vertical scaling to respond to changes
in workload. We detail the circumstances under which vertical and horizontal
scaling transitions should occur and provide a comprehensive method for
switching between these mechanisms.

First, we present a mathematical proof demonstrating the superior performance
of horizontal scaling in terms of throughput, addressing the why of this
transition, contrasting it with the responsiveness offered by vertical scaling
as discussed in Section 2. We outline the horizontal and vertical scaling
transition steps based on this proof (answering how). Finally, to address the
when of these transitions, we develop an LSTM model to predict the maximum
requests per second (RPS) for the next few seconds, guiding the decision of
when to switch from vertical scaling to horizontal scaling. All the transition
states are available in Figure 4.

Figure 4. Transition states between vertical and horizontal scaling
strategies.

###  5.1. Vertical Scaling to Horizontal Scaling

This part describes why we need to switch to horizontal scaling from vertical
scaling and discusses how and when it must be done.

####  5.1.1. Why

Amdahl’s law describes the theoretical speed-up in the execution time of a
parallelizable task (Amdahl, 1967). In Formula 7, $L(r)$ calculates the speed-
up of a task with the given computational resources ($r$) and the
parallelization share ($p$) of the task.

(7) $L(r)=\frac{1}{(1-p)+\frac{p}{r}}.$

We use Amdahl’s law to show that 1-core instances always provide the same or a
higher throughput compared to the multiple-core instances in DL models under a
fixed workload using the same amount of resources. We use induction to prove
this statement by setting total resources $r=2$ and then $r=n\times(n+1)$.

For $r=2$, we have $2\times$ 1-core instances which implies $2\times L(1)$ and
$1\times$ 2-core instance which gives the task speed-up of $1\times L(2)$. The
execution time of $2\times L(1)$ instances is
$2\times(\frac{1}{(1-p)+\frac{p}{1}})=2\times 1=2$ while the latency of the
execution time of $1\times L(2)$ instances is
$\frac{1}{(1-p)+\frac{p}{2}}=\frac{2}{2-p}$ which can be at most $2$ as the
parallelization share can be between 0 and 1. Therefore, $2\times L(1)\geq
1\times L(2)$, meaning that $2\times 1-core$ has a total higher speed-up
$1\times$ 2-core, resulting in the same or higher throughput.

For $r=n\times(n+1)$, we calculate $(n+1)$ $n$-core instances ($(n+1)\times
L(n)$) and $n$ $n+1$-core instances ($n\times L(n+1)$) as follows:

(8) $(n+1)\times L(n)=(n+1)\times\frac{1}{(1-p)+\frac{p}{n}}=\frac{(n+1)\times
n}{n-np+p}.$

(9) $n\times L(n+1)=n\times\frac{1}{(1-p)+\frac{p}{n+1}}=\frac{(n+1)\times
n}{n-np+1}.$

As $0\leq p\leq 1$, $(n+1)\times L(n)$ process more requests than $n\times
L(n+1)$ based on Formula 8 and Formula 9, $(n+1)\times L(n)$ results in a
higher throughput.

Finally, as for any number of cores, more instances with a lower core number
achieve a higher throughput. We conclude that for any $r=n$, $n\times 1-core$
instances achieve the highest possible throughput under a fixed workload.

####  5.1.2. How

There are two scenarios in which we switch to horizontal scaling from vertical
scaling: (i) when the workload is stable, as described in the next section,
and (ii) when there are not enough hardware resources for vertical scaling to
support the workload.

For the former scenario, we use the argument in the previous part and bring up
as many 1-core instances as needed to serve the requests minus the currently
running instances, which we reduce their resources to 1-core as soon as the
rest of the instances are up and running. For instance, if currently, two
3-core instances are serving the requests and four 1-core instances can serve
the same number of requests, we bring up two 1-core instances and reduce the
3-core instances’ resources to 1-core instances using in-place resource
scaling.

For the latter scenario, when there is a hardware limitation, or there is no
speed-up possible because of the limited parallelism of the DL model, we serve
as many requests as possible with the currently running instances by
increasing their resources to the maximum to reduce the SLO violations and
simultaneously bring up new 1-core instances to serve the remaining requests.

####  5.1.3. When

To decide when to switch from vertical scaling to horizontal scaling in case
of workload stability, we design an LSTM to predict the next ten seconds’
maximum RPS and feed the predicted value and the current RPS to the horizontal
scaling algorithm 2 to check whether the current and future configurations are
the same. If so, we switch to horizontal scaling to save resources. We use the
horizontal scaling algorithm to check if the workload is stable since the
currently running instances may be able to serve more requests than the
current workload. Therefore, more RPS may not need more resources.

For building the LSTM model, we use an input layer, a 25-unit LSTM layer,
followed by a one-unit dense output layer. We trained the network using the
Adam optimizer with the MSE loss function. Figure 5 shows the LSTM result,
where we train it with 14 days of the Twitter dataset (archiveteam, 2021) and
seven days as validation (more details in Section 6). The workload prediction
takes less than 30 ms, with a Mean Absolute Percentage Error of 5.8%, making
it practical for getting live inference.

Figure 5. LSTM inference result.

###  5.2. Horizontal Scaling to Vertical Scaling

This part describes why we need to switch to vertical scaling from horizontal
scaling and discusses how and when it must be done.

####  5.2.1. Why and When

When there is an increase in the workload, horizontal scaling needs to bring
up new instances, load the required heavy libraries such as Tensorflow or
PyTorch, and initialize the model. These actions take a few to tens of
seconds, which drastically reduces the responsiveness of horizontal scaling.
On the other hand, in-place vertical scaling can instantly increase the
computing resources of the running instances, making it a better option in
terms of responsiveness. Therefore, when there is a sudden surge of requests
(when the current resource allocation cannot support the increased requests),
we switch to vertical scaling to absorb as many extra requests as possible.

####  5.2.2. How

Now, to answer how to transition from horizontal scaling to vertical scaling,
let’s assume that we have more than one 1-core instance in a stage since with
just one 1-core instance, the previous part states how to scale. The following
question arises when there is a change in the workload requiring more
resources: Should we increase the resources of one instance, the resources of
a subset of instances, or the resources of all the instances to react to the
changes in the workload? To answer this question, we use similar proof as in
the previous section by first considering two 1-core instances, analyzing how
to scale them vertically, and then generalizing them to any number of
instances.

For $r=2\times n$, we calculate both configurations speed-up; once giving all
the resources to one instance ($instance_{1}=2\times n-1$ and
$instance_{2}=1)$ and once distribute the resources evenly
($instance_{1}=instance_{2}=n$). The speed-up calculation for $r=2\times n-1$
is as follows:

(10) $L(2\times n-1)=\frac{1}{(1-p)+\frac{p}{2\times n-1}}=1+\frac{2\times
p\times(n-1)}{2\times(n-np+p)-1}.$

By having the second instance with 1-core and no speed-up, we have the total
speed-up of $2+\frac{2\times p\times(n-1)}{2\times(n-np+p)-1}$. On the other
hand, if we distribute the resources evenly to both instances, each with n CPU
cores, we will have the total speed-up of:

(11) $2\times L(n)=2\times\frac{1}{(1-p)+\frac{p}{n}}=2+\frac{2\times
p\times(n-1)}{n-np+p}.$

Now, if $n-np+p\leq 2\times(n-np+p)-1$, we have shown that distributing
resources evenly has a higher total speed-up, resulting in a higher
throughput. The equation can be proven as follows:

(12) $\begin{split}n-np+p&\leq 2\times(n-np+p)-1\\\ 1&\leq n-np+p\\\ 1-p&\leq
n\times(1-p)\end{split}$

The last part is true since $n$ (the number of allocated CPU cores) is always
greater than 1.

The same proof applies to any number of instances, which is omitted to reduce
repeatability. Therefore, evenly distributing resources generates a higher
throughput compared to giving a subset of instances more resources. We follow
the same practice in our system, and when vertical scaling is needed, we scale
all the instances to the same amount of resources.

##  6\. Experimental Evaluation

We implemented the inference services using PyTorch (Paszke et al., 2019) and
Hugging Face (Face, [n. d.]). The queuing component is implemented using
Python AsyncIO (python software foundation, 2022). We implemented Themis in
Python 111https://github.com/mehransi/Themis. We evaluated Themis on a testbed
consisting of two servers, each equipped with Core i9-9940x CPUs at 3.3GHz and
interconnected with a stable private Ethernet network (1Gbps). We set up a
Kubernetes cluster using MicroK8s (Ltd, [n. d.]) on these two servers and
configured the InPlaceVerticalScaling feature gate, an alpha-stage feature
that enables in-place vertical scaling.

Workload: To evaluate Themis, we developed a workload generator that uses the
real-world Twitter traces (archiveteam, 2021) as the workload pattern
(requests per second) and sends requests to the pipelines following a Poisson
distribution to mimic the workloads on data centers. Furthermore, we use
roughly 10-minute traces from the validation data discussed in Section 5.1.3
for evaluation purposes. The selected traces show a steady workload and heavy
bursts, demonstrating the systems’ behavior under a realistic and dynamic
workload. We scale the traces for each pipeline to match the hardware capacity
we run the experiments on.

DL Models: To compare Themis with existing solutions in realistic
environments, we use DL models across the computer vision, natural language
processing, and audio recognition domains. These domains are also extensively
used in other DL inference serving systems (Kannan et al., 2019; Crankshaw et
al., 2020; Romero et al., 2021a, b; Razavi et al., 2022; Ghafouri et al.,
2024). Table 3(b) summarises the DL models we use to evaluate Themis. We
further assessed the equation in Formula 1 with 512 requests per batch size
and CPU core configuration as demonstrated in Figure 6 to show the
effectiveness of the equation.

Table 3. DL Models and Applications (a) DL Models

Task | Architecture | Abbreviation
---|---|---
Object Detection (ultralytics, 2024) | YOLOv5n | OD
Object Classification (Foundation, 2024) | ResNet18 | OC
Audio to Text (Wang et al., 2020) | FAIRSEQ S2T | AT
Sentiment Analysis (Das, 2024) | DistillBERT | SA
Language Identification (Zein, 2024) | XLM-RoBERTa | LI
Neural Machine Translation (Elan, 2024) | Elan-mt | NT
Text Summarization (Liu, 2024) | T5-small | TS

(b) Applications

Name | Pipeline | SLO
---|---|---
Video Monitoring |  OD$\rightarrow$OC | 780
Audio Sentiment Analysis |  AT$\rightarrow$SA | 1350
Natural Language Processing |  LI$\rightarrow$NT$\rightarrow$TS | 2550

Figure 6. Performance profile of Translator and Classifier DL models with
different CPU and batch configurations.

Pipelines: We evaluate Themis using three pipelines as specified in Table 3(b)
similar to the pipelines used in recent works (Zhang et al., 2017; clarifai,
[n. d.]; Du et al., 2023; Wu et al., 2022). For the SLO of each pipeline, we
follow a similar methodology described in (Gujarati et al., 2017) and
calculate the processing latency with the least batch size and core allocation
($b=c=1$), aggregate the processing latencies of DL models, and multiply the
result by a factor of three.

Baselines: We compare Themis to a state-of-the-art horizontal scaling (FA2
(Razavi et al., 2022)) and an extended version of the recently proposed in-
place vertical scaling (Sponge (Razavi et al., 2024)) in inference serving
systems. FA2 solves the horizontal autoscaling problem by simultaneously
considering the joint problem of batch size and number of instance selections.
It increases the resource utilization of the DL models’ instances, reducing
the needed instances. Sponge uses in-place vertical scaling to react to sudden
changes in the workload. However, their approach only considers one model in
the system. To be able to compare Themis with Sponge, we use the approach in
Algorithm 1 without the horizontal scaling part (one instance per DL model) as
an extension of Sponge to solve the in-place vertical autoscaling problem in
inference pipelines.

Metrics: We consider the following metrics in the evaluation, collected by
Prometheus (Authors, 2024c):

  * •

SLO violation rate: We collect each stage latency (consisting of queuing and
processing latencies), aggregate them, and use them to check whether a request
has violated the application’s SLO.

  * •

Cost: We use the number of instances $\times$ allocation CPU cores per
instance of each DL model and report the aggregated results.

  * •

Request dropping: We consider request dropping to avoid pending requests in
the queues. We collect the dropped requests and use them to calculate the
total SLO violation rate.

  * •

P99 latency: Each second, multiple requests are being served. We pick the P99
of the requests to measure Themis and compare it with the P99 latency of the
baselines.

###  6.1. End-to-End Performance

Video Monitoring. Figure 7 provides a detailed evaluation of Themis,
horizontal scaling, and vertical scaling used to handle the Twitter trace
workloads in the video monitoring pipeline. The top sub-figure shows the
workload, starting low and stable, sharply increasing around the 50 second,
peaking near the 180 second, and gradually returning to the initial RPS around
the 450 second.

When the workload starts, horizontal scaling violates more than half of the
requests since the initial state with one instance on each DL model is not
capable of supporting the incoming workload. To support the workload,
horizontal scaling brings new instances up, where the cold start-up issue
kicks in and starts violating the requests until the instances are spawned and
warmed up. On the other hand, both Themis and vertical scaling immediately
increase the number of CPUs for their running instances to increase their
throughput, hence supporting the starting workload.

After a few seconds, in Themis, when the optimizer detects the workload is
stable with the help of the LSTM, it switches to more 1-core instances to
reduce the costs and, at the same time, to increase the DL models’ throughput
(second 10). The situation becomes complex when the workload increases to over
40RPS from 10RPS, where none of the approaches have enough up-and-running
resources to capture the surge of requests, resulting in violating the SLOs.
However, Themis and vertical scaling approaches change the computing resources
of the running instances to the maximum to reduce the SLO violations. Themis
has a slightly lower SLO violation rate since, in the previous seconds, it has
brought up more 1-core instances to reduce the overall cost. The horizontal
scaling approach initially has the highest violation rate since it needs to
bring up new instances to support the current workload, but after the
instances are up and running, it distributes the workload to multiple
instances and stops violating the requests, which takes roughly 15 seconds.
The vertical scaling approach adapts itself to the initial part of the
workload. However, it starts suffering from SLO violation since one instance,
even with the maximum resource allocation per DL model, is insufficient to
support the incoming workload. After detecting the workload surge, Themis
changes the computing resources of the running instances to maximum and
simultaneously commands the system to bring up new instances to support the
increased workload. With this approach, Themis violates the requests in less
than a few seconds by compensating it with more cost at the 55 second. After
capturing the surge, the optimizer reduces the allocated resources to half to
save costs by switching to horizontal scaling. After that, there are some
fluctuations in the workload where Themis is capable of capturing immediately
due to the responsiveness of in-place vertical scaling, but horizontal scaling
still shows lots of SLO violations (over 10% in some seconds), where it needs
to bring up new instances and violates SLOs meanwhile. After the workload
reaches its initial RPS (450 second), all the approaches serve requests
efficiently.

Figure 7. End-to-end comparison on the video monitoring pipeline. Themis
reduces the SLO violation to roughly 0.1% by using both scaling mechanisms
jointly. Horizontal and vertical scaling mechanisms violate 2.4% and 39.3% of
the requests’ SLO, respectively.

Audio Sentiment Analysis. Figure 8 depicts the end-to-end evaluation over the
audio sentiment analysis pipeline. Both models in the audio sentiment analysis
pipeline are heavier than the ones in video monitoring, and with the same
hardware, the system can process a lower RPS. Therefore, we use almost half of
the previous workload in this experiment.

Unlike the video monitoring pipeline, the gap between the SLO and the
processing latency with $b=c=1$ is greater, and Themis uses the opportunity
and increases the DL models’ batch size more aggressively, resulting in higher
throughput and lower needed resources. Because of the bigger batch sizes, the
system does not need to switch to lower CPU cores using in-place vertical
scaling, unlike the video monitoring pipeline, which changes the CPU cores
more frequently to keep up with the workload. On the other hand, the bigger
batch sizes increase the pipeline SLO violation from 0.1% to 0.5%. The
violation rate increases to 6.5% in horizontal scaling due to the fact that
the models are heavier, and the initialization takes longer, thereby a slower
reaction time and a higher SLO violation rate. Vertical scaling suffers from
the queuing back pressure throughout the experiment, demonstrating the
importance of distributing the requests to multiple instances. Also, at the
moment, we depend on the LSTM and the performance profiles to switch to
horizontal scaling to improve resource efficiency. Our LSTM might delay this
process by predicting higher values for the maximum workload of the next
period, as depicted in the same figure.

Figure 8. End-to-end comparison on the audio sentiment analysis pipeline.
Themis reduces the SLO violation to less than 0.5%. Horizontal scaling
violates 6.5% of the requests, while vertical scaling violates most of the
requests, reaching over 72% of the total SLO violation.

Natural Language Processing. Figure 9 demonstrates the end-to-end evaluation
over the natural language processing pipeline. The pipeline contains three DL
models (compared to two DL models in the other pipelines), which are the most
resource-intensive DL models in our experiments. Therefore, we scale the RPS
to the range of $(2,12)$. Following the same pattern, Themis scales the
resources vertically at the beginning, and after capturing the initial
workload, it reduces the resources to a minimum to match the workload.
Horizontal scaling suffers the most in this scenario since the DL models are
heavy and bring up new instances with the weight loading time taking over 10
seconds, resulting in violating roughly half of the requests SLO. Vertical
scaling drops almost all the requests (over 96%) due to not having enough
resources.

Figure 9. End-to-end comparison on the natural language processing pipeline.
Themis reduces the SLO violation to less than 3.8%. Horizontal scaling
violates 50.7% of the requests SLO, and vertical scaling violates 96.7% of the
requests SLO.

Overall, Themis demonstrates adaptability to workload changes, effectively
scaling resources up and down in response to demand. Despite workload spikes,
the system manages to keep P99 latency mostly within the SLO threshold,
indicating efficient latency management. The CPU usage graph reflects resource
efficiency, increasing during high demand and conserving resources when demand
is low. The figure highlights the effectiveness of these strategies in
managing varying workloads, maintaining low latency and low cost, and
minimizing SLO violations.

###  6.2. Intra and Inter Parallelism

In deep learning frameworks like TensorFlow (Abadi et al., 2016) and PyTorch
(Paszke et al., 2019), two key parameters significantly impact request
processing latency: inter and intra operation parallelism. These parameters
have been extensively studied to determine their optimal configurations for
various scenarios (Zheng et al., 2022).

The intra operation parallelism parameter allows tasks within a single batch
of requests to be parallelized, thereby enhancing processing efficiency within
that batch. This parameter can be dynamically adjusted during runtime,
offering flexibility and adaptability to changing workloads. In contrast, the
inter operation parallelism parameter enables multiple tasks to be executed in
parallel across different batches. However, unlike intra operation
parallelism, the inter operation parameter is initialized once and remains
fixed. This static nature can pose challenges, especially with in-place
vertical scaling, where resource allocation needs may shift dynamically.

As shown in Figure 10, the inter operation parameter has minimal impact if new
batches of requests are sent only after the previous batches have been fully
processed. This suggests that the effectiveness of inter operation parallelism
is context-dependent, proving more beneficial in scenarios with concurrent
batch processing rather than sequential processing.

Figure 10. The effect of Intra and Inter parallelism parameters on the YOLOv5n
and ResNet18 models with 4 CPU cores. Inter parallelism parameter does not
affect the processing latency when there is one batch at a time in the DL
model.

###  6.3. Request Dropping Effect

When there is a surge of requests on the system, they may accumulate in the
queues, leading to violations not only of their SLOs but also of new incoming
requests, as older requests must be processed first. To prevent this,
inference serving systems implement request dropping to alleviate queue back
pressure (Razavi et al., 2022; Ghafouri et al., 2024).

Different request-dropping strategies can be employed to minimize SLO
violations. One strategy is to drop any request already reaching SLO at any
processing or queuing stage. Another approach is to allow a buffer, such as
three times the SLO, acknowledging that some delay might be acceptable.
Finally, an approach is never to drop requests, opting to serve all requests
regardless of the cost.

Figure 11 compares these three strategies using Themis and baseline scaling
approaches over the first 100 seconds of the workload depicted in Figure 7,
which includes a sudden increase in demand. Themis successfully serves almost
all requests (over 99%) during this period with virtually no SLO violations.
In contrast, when the dropping strategy is relaxed (3x SLO and No Dropping),
both horizontal and vertical scaling mechanisms experience significant request
dropping, with over 20% and 40% drop in horizontal and vertical scaling,
respectively. Thus, the 1x SLO strategy is the most effective in minimizing
SLO violations for these approaches.

Figure 11. The effect of different dropping strategies. The 1xSLO dropping
strategy helps reduce the total number of SLO violations.

##  7\. Related Work

This section discusses autoscaling in inference serving systems and
microservices since DL models are mainly encapsulated in microservices, and
the inference pipelines are composed of several interconnected microservices
as discussed in Section 2.

Autoscaling in Inference Serving Systems: Multiple approaches have been
proposed to reduce total resource consumption either using vertical or
horizontal scaling in inference serving systems while guaranteeing SLOs
(Crankshaw et al., 2020; Romero et al., 2021a; Ghafouri et al., 2024; Romero
et al., 2021b; Hu et al., 2021; Gujarati et al., 2020; Salmani et al., 2023;
Dhakal et al., 2020; Shen et al., 2019; Nigade et al., 2022; Gunasekaran et
al., 2022; Crankshaw et al., 2017). FA2 (Razavi et al., 2022) uses graph
transformation and dynamic programming techniques to reduce the number of
instances in horizontal scaling. The graph transformation component
deconstructs the execution graph, simplifying it and enabling optimal
solutions to be found in real time. Meanwhile, the dynamic programming
solution determines the optimal batch size and scaling factor for each DL
model within the pipeline, ensuring efficiency and performance optimization.
Sponge (Razavi et al., 2024) uses a greedy approach to guarantee end-to-end
latency of one DL model under a dynamic network using in-place vertical
scaling. Similar to this work, they encapsulate the autoscaling problem into
an IP and solve it in real time.

Autoscaling in Microservices: Current practices in microservice autoscaling
mechanisms are mainly rule-based heuristics (Authors, 2024a, b; Florio and
Nitto, 2016; Toffetti et al., 2017; Khazaei et al., 2017; Zheng et al., 2019;
Sriraman and Wenisch, 2018), meta-heuristics (Chen and Bahsoon, 2017; Frey et
al., 2013; Verbowski et al., 2018), or recently, machine learning based
(Sachidananda and Sivaraman, 2024; Rossi et al., 2019; Qiu et al., 2023).
Kubernetes Vertical Pod Autoscaler (VPA) (Authors, 2024b) and Horizontal Pod
Autoscaler (HPA) (Authors, 2024a) manage the allocation of computing resources
and the scaling of instances for microservices using threshold-based metrics.
VPA adjusts the CPU and memory resources allocated to individual pods based on
their current usage to ensure optimal performance. Conversely, HPA scales the
number of instances up or down in response to real-time demands by monitoring
metrics like CPU and memory utilization. However, it is advised not to use VPA
and HPA together, as they may interfere with each other’s operations. When
both are set, their concurrent adjustments can lead to conflicting actions,
resulting in inefficient resource allocation and potential performance
degradation. A close work, SHOWAR (Baarzi and Kesidis, 2021), uses the
empirical variance in the historical resource usage for vertical scaling to
have an improved resource allocation compared to the default commonly used
metric-based Kubernetes Vertical Autoscaler (Authors, 2024b) (VPA), and uses
CPU scheduler’s eBPF metrics to design a more accurate horizontal autoscaler
than Kubernetes Horizontal Autoscaler (Authors, 2024a) (HPA). In vertical
scaling in SHOWAR and Kubernetes VPA, the microservices are bounded by a
maximum of 1-core CPU allocation since microservices do not leverage multiple
CPU cores to accelerate the microservices’ performance in contrast to DL
models. Furthermore, the vertical autoscaler in SHOWAR does not react to
changes in the workload but to CPU and memory metrics, which results in SLO
violations in terms of unpredictable changes in the workload.

##  8\. Conclusion

In this paper, we have presented Themis, a novel system designed to enhance
inference serving through an innovative two-stage autoscaling strategy. By
combining in-place vertical scaling with horizontal scaling, BoS effectively
addresses the challenges of managing resource allocation under variable and
unpredictable workloads. Extensive evaluation with real-world workloads
demonstrates Themis reduces the SLO violation by over $10\times$ and minimizes
the cost when the demand is low, showing Themis’s potential to provide
responsive and cost-effective inference-serving solutions.

For future works, we consider enhancing Themis’s capability to utilize
heterogeneous hardware resources effectively. Modern data centers often
comprise a mix of CPUs, GPUs, TPUs, and specialized accelerators. Integrating
Themis with hardware-aware scaling policies can optimize the allocation of
tasks to the most suitable hardware, further improving efficiency and
performance. Moreover, different placement strategies can be employed where
new instances should reside. It requires answering the question of whether we
should use a bin packing approach to utilize the physical machines to the
maximum, a fair distribution of instances using a round-robin approach to not
exhaust the machines, or if the most sparse instance distribution generates
the ideal configuration in terms of guaranteeing SLOs.

## Acknowledgements

This work has been supported by Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) – Project-ID 210487104 - SFB 1053.

## References

  * (1)
  * Abadi et al. (2016) Mart(́i) n Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016\.  Tensorflow: A system for large-scale machine learning. In _USENIX Symposium on Operating Systems Design and Implementation (OSDI)_. 265–283.
  * Ali et al. (2020) Ahsan Ali, Riccardo Pinciroli, Feng Yan, and Evgenia Smirni. 2020.  Batch: Machine learning inference serving on serverless platforms with adaptive batching. In _SC20: International Conference for High Performance Computing, Networking, Storage and Analysis_. IEEE, 1–15.
  * Amdahl (1967) Gene M Amdahl. 1967.  Validity of the single processor approach to achieving large scale computing capabilities. In _Proceedings of the April 18-20, 1967, spring joint computer conference_. 483–485.
  * archiveteam (2021) archiveteam. 2021.  Archiveteam-twitter-stream-2021-08.  https://archive.org/details/archiveteam-twitter-stream-2021-08.
  * Authors (2023) The Kubernetes Authors. 2023.  In-place Resource Resize for Kubernetes Pods.  https://kubernetes.io/blog/2023/05/12/in-place-pod-resize-alpha/.  Accessed on 30.01.2024.
  * Authors (2024a) The Kubernetes Authors. 2024a.  Kubernetes Horizontal Pod Autoscaling.  https://kubernetes.io/docs/tasks/run-application/horizontal-pod-autoscale/.  Accessed on 30.01.2024.
  * Authors (2024b) The Kubernetes Authors. 2024b.  Kubernetes Vertical Pod Autoscaling.  https://cloud.google.com/kubernetes-engine/docs/concepts/verticalpodautoscaler/.  Accessed on 30.01.2024.
  * Authors (2024c) The Prometheus Authors. 2024c.  Prometheus monitoring and alerting toolkit.  https://prometheus.io/.  Accessed on 30.01.2024.
  * Baarzi and Kesidis (2021) Ataollah Fatahi Baarzi and George Kesidis. 2021.  Showar: Right-sizing and efficient scheduling of microservices. In _Proceedings of the ACM Symposium on Cloud Computing_. 427–441.
  * Chen and Bahsoon (2017) Tao Chen and Rami Bahsoon. 2017.  Self-Adaptive Trade-off Decision Making for Autoscaling Cloud-Based Services.  _IEEE Transactions on Services Computing_ 10, 4 (2017), 618–632.
  * clarifai ([n. d.]) clarifai. [n. d.].  Clarifai.  https://clarifai.com/clarifai/main/workflows
  * Crankshaw et al. (2020) Daniel Crankshaw, Gur-Eyal Sela, Xiangxi Mo, Corey Zumar, Ion Stoica, Joseph Gonzalez, and Alexey Tumanov. 2020.  InferLine: Latency-Aware Provisioning and Scaling for Prediction Serving Pipelines. In _ACM Symposium on Cloud Computing (SoCC)_. 477–491.  https://doi.org/10.1145/3419111.3421285
  * Crankshaw et al. (2017) Daniel Crankshaw, Xin Wang, Guilio Zhou, Michael J Franklin, Joseph E Gonzalez, and Ion Stoica. 2017.  Clipper: A $\\{$Low-Latency$\\}$ Online Prediction Serving System. In _USENIX Symposium on Networked Systems Design and Implementation (NSDI)_. 613–627.
  * Das (2024) Souvick Das. 2024.  SentimentAnalysisDistillBERT.  https://huggingface.co/Souvikcmsa/SentimentAnalysisDistillBERT.  Accessed on 30.01.2024.
  * Dhakal et al. (2020) Aditya Dhakal, Sameer G. Kulkarni, and K. K. Ramakrishnan. 2020.  GSLICE: Controlled Spatial Sharing of GPUs for a Scalable Inference Platform. In _ACM Symposium on Cloud Computing (SoCC)_. 492–506.  https://doi.org/10.1145/3419111.3421284
  * Du et al. (2023) Ruofei Du, Na Li, Jing Jin, Michelle Carney, Scott Miles, Maria Kleiner, Xiuxiu Yuan, Yinda Zhang, Anuva Kulkarni, Xingyu Liu, et al. 2023\.  Rapsai: Accelerating Machine Learning Prototyping of Multimedia Applications through Visual Programming. In _Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems_. 1–23.
  * Elan (2024) Mitsua Elan. 2024.  ElanMT-BT-ja-en.  https://huggingface.co/Mitsua/elan-mt-bt-ja-en.  Accessed on 30.01.2024.
  * Elhoseny (2020) Mohamed Elhoseny. 2020.  Multi-object detection and tracking (MODT) machine learning model for real-time video surveillance systems.  _Circuits, Systems, and Signal Processing_ 39, 2 (2020), 611–630.
  * Face ([n. d.]) Hugging Face. [n. d.].  Hugging Face.  https://huggingface.co/.  Accessed on 11.07.2024.
  * Florio and Nitto (2016) Luca Florio and Elisabetta Di Nitto. 2016.  Gru: An Approach to Introduce Decentralized Autonomic Behavior in Microservices Architectures. In _IEEE International Conference on Autonomic Computing (ICAC)_.
  * Foundation (2019) The Linux Foundation. 2019.  Kubernetes.  https://kubernetes.io.  Accessed on 29.10.2021.
  * Foundation (2024) The PyTorch Foundation. 2024.  ResNet18.  https://pytorch.org/vision/main/models/generated/torchvision.models.resnet18.html.  Accessed on 30.01.2024.
  * Frey et al. (2013) Sören Frey, Florian Fittkau, and Wilhelm Hasselbring. 2013.  Search-based genetic optimization for deployment and reconfiguration of software in the cloud. In _IEEE International Conference on Software Engineering (ICSE)_.
  * Ghafouri et al. (2024) Saeid Ghafouri, Kamran Razavi, Mehran Salmani, Alireza Sanaee, Tania Lorido-Botran, Lin Wang, Joseph Doyle, and Pooyan Jamshidi. 2024.  IPA: Inference Pipeline Adaptation to Achieve High Accuracy and Cost-Efficiency.  arXiv:2308.12871 [cs.DC]
  * Gujarati et al. (2017) Arpan Gujarati, Sameh Elnikety, Yuxiong He, Kathryn S McKinley, and Björn B Brandenburg. 2017.  Swayam: distributed autoscaling to meet slas of machine learning inference services with resource efficiency. In _ACM/IFIP/USENIX Middleware Conference_. 109–120.
  * Gujarati et al. (2020) Arpan Gujarati, Reza Karimi, Safya Alzayat, Wei Hao, Antoine Kaufmann, Ymir Vigfusson, and Jonathan Mace. 2020.  Serving DNNs like Clockwork: Performance Predictability from the Bottom Up. In _USENIX Symposium on Operating Systems Design and Implementation (OSDI)_. 443–462.
  * Gunasekaran et al. (2022) Jashwant Raj Gunasekaran, Cyan Subhra Mishra, Prashanth Thinakaran, Bikash Sharma, Mahmut Taylan Kandemir, and Chita R Das. 2022.  Cocktail: A multidimensional optimization for model serving in cloud. In _USENIX NSDI_. 1041–1057.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * Hu et al. (2021) Yitao Hu, Weiwu Pang, Xiaochen Liu, Rajrup Ghosh, Bongjun Ko, Wei-Han Lee, and Ramesh Govindan. 2021.  Rim: Offloading Inference to the Edge. In _Proceedings of the International Conference on Internet-of-Things Design and Implementation_. 80–92.
  * Kannan et al. (2019) Ram Srivatsa Kannan, Lavanya Subramanian, Ashwin Raju, Jeongseob Ahn, Jason Mars, and Lingjia Tang. 2019.  GrandSLAm: Guaranteeing SLAs for Jobs in Microservices Execution Frameworks. In _ACM European Conference on Computer Systems (EuroSys)_. 1–16.  https://doi.org/10.1145/3302424.3303958
  * Khazaei et al. (2017) Hamzeh Khazaei, Rajsimman Ravichandiran, Byungchul Park, Hadi Bannazadeh, Ali Tizghadam, and Alberto Leon-Garcia. 2017.  Elascale: autoscaling and monitoring as a service. In _ACM Annual International Conference on Computer Science and Software Engineering (CASCON)_.
  * LeMay et al. (2020) Matthew LeMay, Shijian Li, and Tian Guo. 2020.  Perseus: Characterizing performance and cost of multi-tenant serving for cnn models. In _2020 IEEE International Conference on Cloud Engineering (IC2E)_. IEEE, 66–72.
  * Liu (2024) Steven Liu. 2024.  T5-small.  https://huggingface.co/stevhliu/my_awesome_billsum_model.  Accessed on 30.01.2024.
  * Ltd ([n. d.]) Canonical Ltd. [n. d.].  MikorK8s V1.30/h.  https://microk8s.io/.  Accessed on 11.07.2024.
  * Luo et al. (2022) Shutian Luo, Huanle Xu, Kejiang Ye, Guoyao Xu, Liping Zhang, Guodong Yang, and Chengzhong Xu. 2022.  The power of prediction: microservice auto scaling via workload learning. In _Proceedings of the 13th Symposium on Cloud Computing_. 355–369.
  * Mounesan et al. (2024) Motahare Mounesan, Mauro Lemus, Hemanth Yeddulapalli, Prasad Calyam, and Saptarshi Debroy. 2024.  Reinforcement Learning-driven Data-intensive Workflow Scheduling for Volunteer Edge-Cloud.  arXiv:2407.01428 [cs.DC] https://arxiv.org/abs/2407.01428
  * Nigade et al. (2022) Vinod Nigade, Pablo Bauszat, Henri Bal, and Lin Wang. 2022.  Jellyfish: Timely Inference Serving for Dynamic Edge Networks. In _2022 IEEE Real-Time Systems Symposium (RTSS)_. 277–290.  https://doi.org/10.1109/RTSS55097.2022.00032
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ 32 (2019).
  * Pavlenko et al. (2024) Anna Pavlenko, Joyce Cahoon, Yiwen Zhu, Brian Kroth, Michael Nelson, Andrew Carter, David Liao, Travis Wright, Jesús Camacho-Rodr(́i) guez, and Karla Saur. 2024.  Vertically Autoscaling Monolithic Applications with CaaSPER: Scalable C ontainer-a s-a-S ervice P erformance E nhanced R esizing Algorithm for the Cloud. In _Companion of the 2024 International Conference on Management of Data_. 241–254.
  * python software foundation (2022) python software foundation. 2022.  AsyncIO library.  https://docs.python.org/3.8/library/asyncio.html.  Accessed on 11.07.2024.
  * Qiu et al. (2023) Haoran Qiu, Weichao Mao, Chen Wang, Hubertus Franke, Alaa Youssef, Zbigniew T Kalbarczyk, Tamer Başar, and Ravishankar K Iyer. 2023.  $\\{$AWARE$\\}$: Automate workload autoscaling with reinforcement learning in production cloud systems. In _2023 USENIX Annual Technical Conference (USENIX ATC 23)_. 387–402.
  * Razavi et al. (2024) Kamran Razavi, Saeid Ghafouri, Max Mühlhäuser, Pooyan Jamshidi, and Lin Wang. 2024.  Sponge: Inference Serving with Dynamic SLOs Using In-Place Vertical Scaling. In _Proceedings of the 4th Workshop on Machine Learning and Systems_. 184–191.
  * Razavi et al. (2022) Kamran Razavi, Manisha Luthra, Boris Koldehofe, Max Mühlhäuser, and Lin Wang. 2022.  FA2: Fast, accurate autoscaling for serving deep learning inference with SLA guarantees. In _2022 IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS)_. IEEE, 146–159.
  * Romero et al. (2021a) Francisco Romero, Qian Li, Neeraja J Yadwadkar, and Christos Kozyrakis. 2021a.  INFaaS: Automated Model-less Inference Serving. In _USENIX Annual Technical Conference (ATC)_. 397–411.
  * Romero et al. (2021b) Francisco Romero, Mark Zhao, Neeraja J Yadwadkar, and Christos Kozyrakis. 2021b.  Llama: A Heterogeneous & Serverless Framework for Auto-Tuning Video Analytics Pipelines. In _ACM Symposium on Cloud Computing (SoCC)_. 1–17.
  * Rossi et al. (2019) Fabiana Rossi, Matteo Nardelli, and Valeria Cardellini. 2019.  Horizontal and vertical scaling of container-based applications using reinforcement learning. In _2019 IEEE 12th International Conference on Cloud Computing (CLOUD)_. IEEE, 329–338.
  * Sachidananda and Sivaraman (2024) Vighnesh Sachidananda and Anirudh Sivaraman. 2024.  Erlang: Application-Aware Autoscaling for Cloud Microservices. In _Proceedings of the Nineteenth European Conference on Computer Systems_. 888–923.
  * Salmani et al. (2023) Mehran Salmani, Saeid Ghafouri, Alireza Sanaee, Kamran Razavi, Max Mühlhäuser, Joseph Doyle, Pooyan Jamshidi, and Mohsen Sharifi. 2023.  Reconciling High Accuracy, Cost-Efficiency, and Low Latency of Inference Serving Systems. In _Proceedings of the 3rd Workshop on Machine Learning and Systems_. 78–86.
  * Shen et al. (2019) Haichen Shen, Lequn Chen, Yuchen Jin, Liangyu Zhao, Bingyu Kong, Matthai Philipose, Arvind Krishnamurthy, and Ravi Sundaram. 2019.  Nexus: A GPU Cluster Engine for Accelerating DNN-Based Video Analysis. In _ACM Symposium on Operating Systems Principles (SOSP)_. 322–337.  https://doi.org/10.1145/3341301.3359658
  * Sriraman and Wenisch (2018) Akshitha Sriraman and Thomas F. Wenisch. 2018.  $\mathrm{\mu}$Tune: Auto-Tuned Threading for OLDI Microservices. In _USENIX Symposium on Operating Systems Design and Implementation (OSDI)_.
  * Toffetti et al. (2017) Giovanni Toffetti, Sandro Brunner, Martin Blöchlinger, Josef Spillner, and Thomas Michael Bohnert. 2017.  Self-managing cloud-native applications: Design, implementation, and experience.  _Future Generation Computer Systems_ 72 (2017), 165–179.
  * ultralytics (2024) ultralytics. 2024.  YOLOv5.  https://github.com/ultralytics/yolov5.  Accessed on 30.01.2024.
  * Verbowski et al. (2018) Chad Verbowski, Ed Thayer, Paolo Costa, Hugh Leather, and Björn Franke. 2018.  Right-Sizing Server Capacity Headroom for Global Online Services. In _IEEE International Conference on Distributed Computing Systems (ICDCS)_. 645–659.
  * Wang et al. (2020) Changhan Wang, Yun Tang, Xutai Ma, Anne Wu, Sravya Popuri, Dmytro Okhonko, and Juan Pino. 2020.  Fairseq S2T: Fast speech-to-text modeling with fairseq.  _arXiv preprint arXiv:2010.05171_ (2020).
  * Wu et al. (2022) Tongshuang Wu, Michael Terry, and Carrie Jun Cai. 2022.  Ai chains: Transparent and controllable human-ai interaction by chaining large language model prompts. In _Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems_. 1–22.
  * Zein (2024) Dina El Zein. 2024.  xlm-roberta-base-finetuned-language-identification.  https://huggingface.co/dinalzein/xlm-roberta-base-finetuned-language-identification.  Accessed on 30.01.2024.
  * Zhang et al. (2019) Chengliang Zhang, Minchen Yu, Wei Wang, and Feng Yan. 2019.  Mark: Exploiting cloud services for cost-effective, SLO-aware machine learning inference serving. In _2019 $\\{$USENIX$\\}$ Annual Technical Conference ($\\{$USENIX$\\}$$\\{$ATC$\\}$ 19)_. 1049–1062.
  * Zhang et al. (2017) Haoyu Zhang, Ganesh Ananthanarayanan, Peter Bodik, Matthai Philipose, Paramvir Bahl, and Michael J Freedman. 2017.  Live video analytics at scale with approximation and $\\{$Delay-Tolerance$\\}$. In _14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17)_. 377–392.
  * Zheng et al. (2022) Lianmin Zheng, Zhuohan Li, Hao Zhang, Yonghao Zhuang, Zhifeng Chen, Yanping Huang, Yida Wang, Yuanzhong Xu, Danyang Zhuo, Eric P Xing, et al. 2022\.  Alpa: Automating inter-and $\\{$Intra-Operator$\\}$ parallelism for distributed deep learning. In _16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)_. 559–578.
  * Zheng et al. (2019) Tianlei Zheng, Xi Zheng, Yuqun Zhang, Yao Deng, ErXi Dong, Rui Zhang, and Xiao Liu. 2019.  SmartVM: a SLA-aware microservice deployment framework.  _World Wide Web_ 22, 1 (2019), 275–293.