Fast Distributed Inference Serving for Large Language Models

🎯 Pitch

FastServe demonstrates that GPU memory overflow, not scheduling granularity, is the hidden bottleneck in token-level preemptive scheduling for LLM inference—addressing it via proactive KV cache offloading yields up to 31.4× throughput gains over vLLM under identical latency targets.

1. Executive Summary

FastServe introduces a distributed inference serving system for large language models that exploits the autoregressive generation pattern to enable iteration-level preemption—scheduling decisions made after each output token rather than waiting for job completion. Using a novel skip-join Multi-Level Feedback Queue scheduler (which places arriving jobs into an appropriate priority queue based on their profiled input length rather than always starting at the highest priority) and a proactive key-value cache management mechanism (which overlaps GPU-to-host memory offloading of intermediate state with ongoing computation), FastServe addresses head-of-line blocking that causes queuing delay to dominate up to 90% of end-to-end latency in existing FCFS-based systems like vLLM. Evaluated on OPT-13B through OPT-175B with real-world ShareGPT and Alpaca workloads, FastServe improves throughput by up to 31.4× and 17.9× over vLLM under the same average and tail latency service-level objectives, respectively—establishing that preemptive scheduling at token granularity dramatically outperforms run-to-completion execution only when paired with memory management that prevents GPU cache overflow from stalling newly admitted jobs.

2. Context and Motivation

The Core Problem: Head-of-Line Blocking in LLM Inference Serving

The central problem this paper addresses is head-of-line blocking in inference serving systems for large language models. To understand why this is a problem, let's first establish what happens when you deploy an LLM to serve real users.

When multiple users send prompts to a chatbot (e.g., ChatGPT), the inference serving system must process these requests on limited GPU hardware. The natural approach is to batch multiple requests together and process them simultaneously on the GPU—this maximizes hardware utilization. However, LLM inference has a distinctive characteristic that makes naive batching problematic: each request takes a variable and unpredictable amount of time to complete. The output length—how many tokens the model generates before emitting an end-of-sequence token—is not known in advance. It depends on the semantics of the prompt and the model's generative behavior.

In existing systems like vLLM [11] and Orca [10], once a batch of requests begins processing, it runs until every request in the batch finishes generating all its tokens. This is called run-to-completion execution, governed by a simple first-come-first-served (FCFS) scheduling policy. The problem is stark: if your batch contains one request that generates 500 tokens alongside several requests that generate only 20 tokens, the short requests finish early but their results cannot be returned to the user until the long request completes. Meanwhile, newly arrived requests cannot join the processing batch until the entire current batch finishes. This is head-of-line blocking—a long job at the head of the queue delays everything behind it.

Figure 1 quantifies the severity. The paper breaks down end-to-end latency into queuing delay (time spent waiting before execution begins) and execution time (time actually spent generating tokens). For synthetic workloads where all jobs have identical input and output lengths (the "Fix-Len" columns), queuing delay is minimal—roughly 20% of total latency at 90% load, rising slightly at full load. But for real-world workloads drawn from ShareGPT and Alpaca datasets, the picture flips: queuing delay constitutes 87.6–98.0% of total latency depending on the dataset and load level. In other words, users are waiting almost entirely because of scheduling inefficiency, not because the model is slow at generating tokens. Optimizing execution time—making the GPU kernels faster, compressing the model, etc.—only addresses the ~10% of latency that comes from actual computation. The overwhelming majority of user-perceived latency is a scheduling problem.

Why This Problem Matters

The paper's motivation is intensely practical, grounded in the demands of interactive AI applications. Users of ChatGPT and similar systems expect instant responses—the interaction model is conversational, not batch-oriented. If a user asks a simple question and must wait 30 seconds because their request got queued behind someone else's request for a lengthy creative writing task, the experience is unacceptable. The paper frames this as a direct threat to user engagement and the viability of LLM-powered applications.

The technical significance runs deeper. The paper identifies that LLM inference sits in a fundamentally different regime from traditional DNN inference serving. Traditional models like ResNet process each input in a single forward pass—execution time is deterministic and highly predictable, depending only on the model architecture and input dimensions, both known at compile time. Systems like Clockwork [8] and Shepherd [9] exploit this predictability by profiling execution times offline and using that information to construct precise schedules. LLM inference breaks this assumption: while the time per iteration (per-token generation) is predictable, the number of iterations is a random variable drawn from a long-tailed distribution over the model's behavior space. This means that:

Predictability-based scheduling fails. You cannot pre-compute a schedule because you don't know how long each job will run. Prior serving systems that depend on accurate execution time profiling (Clockwork, Shepherd) are inapplicable.
The job size distribution is highly skewed. Both the ShareGPT and Alpaca datasets exhibit long-tailed output length distributions—most requests are short, but a non-trivial fraction are very long. This skew means FCFS scheduling creates disproportionate queuing delays: the occasional long job blocks many short jobs that arrive after it, dramatically inflating average latency.
GPU memory is the binding constraint. You cannot simply make batches arbitrarily large to reduce the frequency of head-of-line blocking, because each request requires storing a key-value cache (intermediate state for the attention mechanism) that grows with sequence length. GPU memory is scarce (80GB on an A100), and a significant fraction is already consumed by model weights. The paper calculates that a single OPT-175B request with an input of 512 tokens and just one output token requires 2.3 GB for its KV cache alone. This makes the memory constraint acute and growing—as models support longer context windows (Gemini 1.5, Claude-3), the problem intensifies.

Where Prior Approaches Fall Short

The paper identifies limitations across three axes of existing work: scheduling policy, GPU memory management, and parallelization strategy.

Run-to-completion scheduling is the root cause. Both vLLM and Orca incorporate sophisticated optimizations for LLM inference. Orca [10] introduced iteration-level scheduling, meaning the serving system processes one iteration (one output token per request) at a time rather than whole jobs. Within each iteration, new requests can join the batch and completed requests can leave. This eliminates one source of blocking—you don't have to wait for the whole batch to finish before returning results or admitting new work. vLLM [11] further introduced PagedAttention, which manages the KV cache at block granularity to reduce memory fragmentation, enabling more efficient batching within the same memory budget. However, the paper emphasizes a crucial point: both systems still use FCFS scheduling with run-to-completion semantics. Once a request enters the processing batch, it remains there until it finishes generating all its tokens. The scheduler never preempts an in-progress job to make room for a newly arrived, potentially shorter job. This is why, despite their optimizations, they still suffer from the queuing delay dominance shown in Figure 1.

"However, they both use first-come-first-served (FCFS) to process inference jobs. Once a job is scheduled, it runs until it finishes." (Section 1)

The paper positions this as a scheduling problem that execution optimizations cannot solve. No amount of kernel fusion, memory compression, or attention optimization addresses the fact that a long-running job should occasionally be set aside to let shorter jobs through.

The naive application of preemptive scheduling creates a memory crisis. The natural solution to head-of-line blocking is preemptive scheduling—interrupt a running job, save its state, start a shorter job, and resume the interrupted job later. The paper identifies that LLM inference naturally supports preemption at token granularity: after generating each output token, the system can decide whether to continue with the current batch or swap in different jobs. However, preemptive scheduling introduces a new problem: GPU memory overhead for preempted jobs. Under FCFS, only the currently-running batch's KV caches must be stored in GPU memory—a manageable quantity bounded by the maximum batch size. Under preemptive scheduling, many jobs may be partially completed and suspended, and their KV caches must be preserved to avoid recomputation when they resume. The paper demonstrates this empirically in Figure 8: for a small OPT-2.7B model under a synthetic workload, the peak KV cache memory consumption under the skip-join MLFQ scheduler is 7× larger than under FCFS. Without a mechanism to handle this memory explosion, preemptive scheduling is impractical—the GPU will simply run out of memory, forcing the scheduler to defer newly arrived high-priority jobs anyway, defeating the purpose of preemption.

The paper examines two strawman solutions to this memory pressure and explains why they fail:

Defer newly arrived jobs when GPU memory is full. This is the approach of existing systems like vLLM. But under memory-constrained conditions (e.g., when many long-sequence jobs are in flight), the GPU remains full of in-progress jobs, and MLFQ degenerates back to FCFS because no new jobs can be admitted regardless of priority. The preemption mechanism becomes hollow if there is no memory to load the preempting job's state.
Kill and recompute low-priority jobs. Release the KV caches of low-priority suspended jobs, freeing GPU memory for high-priority arrivals. This wastes the computation already invested in the killed jobs, which must regenerate their KV caches from scratch when resumed. More critically, it can cause deadlocks due to the interaction with starvation prevention. A killed low-priority job, after waiting long enough, gets promoted to high priority (starvation prevention). When promoted, it may need to kill the currently-executing job (which in turn may have previously killed it), creating a cyclical dependency.

Existing systems lack principled scheduling policies for variable-size jobs. The information-theoretic challenge is that LLM inference is semi-information-agnostic: the output length is unknown a priori, but the input length is known and the per-iteration execution time is predictable via profiling. Classical scheduling theory offers SRPT (Shortest Remaining Processing Time) as the optimal policy for minimizing average latency when job sizes are known. But with unknown output lengths, SRPT cannot be directly applied. MLFQ (Multi-Level Feedback Queue) is the established approach for information-agnostic settings—jobs start at high priority and are demoted to lower priorities as they consume more service time, approximating SRPT without knowing job sizes in advance. However, the paper identifies that classical MLFQ fails for LLM inference because of the initialization phase. The first iteration of LLM inference (processing the entire input prompt and building the initial KV cache) takes significantly longer than subsequent decoding iterations—Figure 5 shows that for an input length of 1024 tokens, the first iteration is approximately 10× longer than later iterations. A classical MLFQ would place every new job in the highest-priority queue (with the shortest quantum), but long-input jobs would exhaust that quantum before even completing their first iteration. The scheduler faces an impossible choice: preempt before the first token is generated (wasting all the computation in the unfinished first iteration, since intermediate activations are discarded) or let it run to completion of the first iteration (violating the MLFQ quantum mechanism and potentially causing head-of-line blocking).

The parallelization strategy creates additional coordination complexity. For models too large to fit on a single GPU (e.g., OPT-175B requires 350GB for weights alone, exceeding any single A100's 80GB), serving systems must use tensor parallelism (splitting operators across GPUs) and pipeline parallelism (splitting layers into stages across GPUs). Under preemptive scheduling with pipeline parallelism, the scheduler must manage multiple batches in flight simultaneously across different pipeline stages, decide which job to schedule at each stage boundary, and coordinate KV cache swapping across distributed GPU memory. Existing systems like vLLM support only tensor parallelism for the largest models, and their FCFS scheduling avoids these coordination problems by never having to preempt mid-pipeline.

How This Paper Positions Itself

FastServe positions itself as the first inference serving system to exploit LLM autoregression for preemptive scheduling at token granularity, addressing head-of-line blocking through a combination of three integrated mechanisms:

A scheduling policy tailored to the semi-information-agnostic setting. Rather than applying classical MLFQ (which is designed for fully information-agnostic settings) or fixed-priority scheduling (which only uses input length but ignores decoding-phase behavior), FastServe's skip-join MLFQ uses profiled initialization-phase time to place arriving jobs into an appropriate initial priority queue—skipping the highest-priority queues whose quanta are too short to accommodate even one iteration of that job. This avoids the initialization-phase quantum exhaustion problem while still allowing short-output-length jobs to receive priority over long-output-length jobs, because the decoding phase's constant per-iteration time means jobs that produce few tokens naturally complete within higher-priority quanta and are never demoted.
A memory management strategy that makes preemptive scheduling practical. The proactive KV cache swapping mechanism extends the effective KV cache capacity from GPU memory to host (CPU) memory, but does so before the GPU runs out of space, overlapping data transfer with ongoing computation so that swapping latency is hidden. The paper explicitly contrasts this with reactive approaches that stall computation waiting for transfers, and with recomputation approaches that waste GPU cycles rebuilding discarded caches.
Extensions to distributed serving that preserve the scheduling semantics across parallelization strategies. For pipeline-parallel deployments, FastServe generalizes the MLFQ scheduler to handle multiple jobs in-flight across pipeline stages, and distributes the KV cache across GPUs with coordinated swapping instructions that propagate through the pipeline alongside intermediate results.

The paper frames its contribution not as competing with inference execution optimizations (iteration-level scheduling, PagedAttention, kernel fusion) but as complementing them at the scheduling layer. FastServe's implementation actually incorporates these optimizations—it uses iteration-level scheduling from Orca and PagedAttention from vLLM, and implements efficient C++/CUDA kernels that outperform Python-based alternatives. The claim is that these execution optimizations, while necessary, are insufficient without a scheduling policy that addresses the queuing delay that dominates end-to-end latency. The paper's positioning is succinctly captured in the contrast between Figure 1's breakdown (90% queuing delay) and the design goal: execution optimization addresses the 10%; FastServe addresses the 90%.

3. Technical Approach

3.1 Reader Orientation

FastServe is a distributed inference serving system—a piece of infrastructure that sits between users (who send prompts to an LLM) and the GPU cluster (which executes the model to generate responses). It solves the problem of head-of-line blocking in LLM inference by exploiting the autoregressive generation pattern to make scheduling decisions at the granularity of individual output tokens, rather than waiting for complete jobs to finish. The solution has the shape of a priority-based preemptive scheduler (the skip-join MLFQ) coupled with a GPU memory manager (proactive KV cache swapping) that prevents the memory overhead of preemption from overwhelming the limited GPU memory capacity.

3.2 Big-Picture Architecture (Diagram in Words)

The system comprises five major components connected in a processing pipeline, as depicted in Figure 4:

Job Pool — a queue of incoming inference requests from clients. Each request contains the prompt text (tokenized as input), sampling parameters (temperature, maximum output length), and a unique job identifier. This is the entry point for all work into the system.
Job Profiler — a static profiling database, built offline, that maps (model architecture, hardware configuration, input sequence length) to the execution time of the first iteration (the initialization phase) and subsequent iterations (the decoding phase). When a new job arrives, the scheduler queries this profiler with the job's input length to obtain a precise time estimate for how long its first output token will take to generate.
Skip-Join Multi-Level Feedback Queue (MLFQ) Scheduler — the central scheduling component that decides which jobs to execute next. It maintains $n$ priority queues ( $Q_1, Q_2, \ldots, Q_n$ ), each with an associated time quantum $q_1 < q_2 < \ldots < q_n$ . Unlike classical MLFQ where all jobs start in $Q_1$ , FastServe's scheduler uses the profiled initialization time to skip-join each arriving job directly into the highest-priority queue whose quantum is large enough to accommodate at least one full iteration of that job. Jobs are demoted to lower-priority queues when they exhaust their quantum without finishing, and starved jobs are periodically promoted back to $Q_1$ . The output of the scheduler is a batch of up to MaxBatchSize jobs dispatched for one iteration of execution.
Distributed Execution Engine — a set of GPU workers (implemented as Ray actors) that execute the LLM inference. The engine receives a batch of jobs from the scheduler, runs exactly one iteration for each job (generating one output token per job), and returns the generated tokens. It supports tensor parallelism (splitting individual operators across GPUs) and pipeline parallelism (splitting layers into sequential stages across GPUs) for models too large to fit on a single GPU. It incorporates iteration-level scheduling (jobs can join and leave the batch between iterations) and PagedAttention (block-grained KV cache allocation to reduce fragmentation).
Key-Value Cache Manager — a memory management layer that controls the residency of intermediate attention state (the KV cache) between GPU memory and host (CPU) memory. When the scheduler preempts a job, its KV cache remains in GPU memory if capacity permits; when GPU memory approaches saturation, the manager proactively offloads selected KV caches to host memory before space runs out, and uploads them back before their associated jobs are scheduled again. The manager coordinates across distributed GPUs for pipeline-parallel deployments, propagating swapping instructions alongside pipeline stage communication.

Information flow: A client submits a request → the job pool enqueues it → the profiler provides the initialization-phase time for the input length → the scheduler skip-joins the job into the appropriate MLFQ priority queue → when the job reaches the head of its queue and the execution engine has capacity, the scheduler dispatches a batch containing this job → the execution engine runs one iteration (generating one token), updating the KV cache → the scheduler examines the job's status (finished? quantum exhausted? starved?) and moves it to the appropriate queue → if GPU memory pressure is detected, the KV cache manager proactively swaps KV caches between GPU and host memory in the background → steps 4-6 repeat until the job generates an end-of-sequence token or reaches maximum output length → the complete response is returned to the client.

3.3 Roadmap for the Deep Dive

First, the scheduling design space. I will explain why classical MLFQ fails for LLM inference (the initialization-phase quantum exhaustion problem) and why fixed-priority and naive SRPT are insufficient—this establishes why a new scheduler design is necessary.
Second, the skip-join MLFQ scheduler in full detail. I will walk through the multi-queue structure, the skip-join rule (how input length determines initial queue placement), the demotion rule, the starvation prevention mechanism, and the precise algorithm (Algorithm 1). This is the core intellectual contribution.
Third, the proactive KV cache management mechanism. I will quantify the memory pressure created by preemptive scheduling, explain why naive solutions (deferring or killing jobs) fail, derive the Estimated Next Scheduled Time (ENST) metric that guides swapping decisions, and describe the pipelining of data transfer with computation.
Fourth, the distributed serving extensions. I will cover how the scheduler handles multiple in-flight batches under pipeline parallelism, how the KV cache is partitioned across GPUs, and how swapping instructions propagate through the pipeline alongside intermediate results.
Fifth, the job profiler. I will briefly describe how iteration times are collected offline and used at scheduling time—this is background infrastructure that enables the skip-join rule.

3.4 Detailed, Sentence-Based Technical Breakdown

This is a systems design paper whose core idea is that head-of-line blocking in LLM serving can be eliminated by exploiting the autoregressive generation pattern to make preemptive scheduling decisions after each output token, and that the memory overhead of this preemption can be managed through proactive KV cache offloading to host memory.

The Scheduling Problem: Why Classical Approaches Fail

Before presenting the skip-join MLFQ design, the paper analyzes why three straightforward scheduling strategies are insufficient for LLM inference serving—this analysis motivates each element of the final design.

Why naive MLFQ fails (the initialization-phase problem). In classical MLFQ, every arriving job enters the highest-priority queue $Q_1$ , which has the shortest quantum $q_1$ . The job is allowed to execute for up to $q_1$ time; if it doesn't finish, it is demoted to $Q_2$ (with a larger quantum $q_2 > q_1$ ), and so on. This design approximates Shortest Remaining Processing Time (SRPT) without knowing job sizes: jobs that finish quickly (i.e., are "short") complete within $Q_1$ or $Q_2$ and never experience demotion; jobs that require more total service time are progressively demoted, receiving less frequent but longer execution slices.

The problem for LLM inference is that the first iteration is substantially more expensive than subsequent iterations. Figure 5 shows the iteration time for OPT-2.7B on an A100 for different input lengths:

For input length 128: the first iteration takes approximately 0.01 seconds, while iterations 2–4 take approximately 0.002 seconds—about a 5× difference.
For input length 1024: the first iteration takes approximately 0.09 seconds, while subsequent iterations still take approximately 0.002 seconds—about a 45× difference.

The paper quantifies why this matters (Section 4.1):

"When employing the original MLFQ, a job is immediately assigned to the highest priority queue upon arrival. However, due to its substantial initialization phase time, the job may deplete its quantum before completing its first iteration."

The scheduler faces an impossible choice when a job's initialization time exceeds $q_1$ :

Preempt before the first token is generated. The partially-computed first iteration's intermediate activations (not the KV cache—the KV cache is built during the first iteration and only complete at its end) are discarded. When the job resumes, it must recompute the entire first iteration from scratch. This wastes GPU cycles and time.
Do not preempt—let the job complete its first iteration even though it exceeds $q_1$ . This violates the fundamental mechanism of MLFQ (quantum enforcement) and reintroduces head-of-line blocking: a long-initialization job can occupy the GPU for tens of milliseconds while newly arrived short-input jobs queue up.

Either choice undermines the scheduler's purpose. The root cause is that classical MLFQ assumes service time is homogeneous across a job's lifetime (each quantum consumes roughly similar amounts of work), but LLM inference has a front-loaded cost structure where the first quantum is much more expensive than any subsequent one.

Why fixed-priority scheduling fails (ignoring the decoding phase). An alternative is to assign each job a fixed priority based solely on its input length—shorter inputs get higher priority. This leverages the strong correlation between input length and first-iteration time (Figure 5), effectively approximating SRPT when the initialization phase dominates total job time. However, this strategy is blind to the decoding phase:

"Many real-world datasets like ShareGPT and Alpaca show a long tail distribution implying that jobs with a long output length also exist. When the decoding phase dominates the total latency, the fixed priority scheduling may deviate from the optimal performance of SRPT." (Section 4.1)

Consider two jobs: Job A has a short input (high priority under fixed-priority) but generates 500 output tokens; Job B has a long input (low priority) but generates only 5 output tokens. Fixed-priority scheduling would prioritize Job A over Job B, but Job B would finish much faster overall if allowed to run first. The decoding phase—where each iteration has roughly constant cost regardless of input length—makes total job duration depend on output length, which fixed-priority scheduling ignores.

Why SRPT cannot be directly applied (unknown output length). SRPT requires knowing the remaining processing time for each job—exactly the output length, which depends on the semantics of the prompt and the model's generation behavior. Predicting output length is an open research problem and is not solved by any existing technique. The paper explicitly states:

"While the execution time for one iteration (generating one output token) can be determined based on the model architecture and hardware, the total number of iterations (i.e., the output sequence length) remains unknown and is challenging to predict since it depends on the semantics of the job." (Section 2.3)

This constrains the design space: the scheduler must work with partial information (input length known, per-iteration time predictable, but output length unknown), which the paper terms the semi-information-agnostic setting.

The Skip-Join MLFQ Scheduler: Core Design

The skip-join MLFQ scheduler is designed to exploit the semi-information-agnostic nature of LLM inference: it uses the known input length (and corresponding profiled iteration times) to determine initial queue placement, while using the MLFQ's feedback mechanism (demotion based on consumed service time) to handle the unknown output length. Section 4.1 presents the full design, and Algorithm 1 formalizes it in pseudocode (lines 3–25).

Queue structure and quanta. The scheduler maintains $n$ priority queues $Q_1, Q_2, \ldots, Q_n$ , ordered from highest priority ( $Q_1$ ) to lowest ( $Q_n$ ). Each queue $Q_i$ has an associated time quantum $q_i$ , with $q_1 < q_2 < \ldots < q_n$ . The quantum of the highest-priority queue $q_1$ is set to the minimum iteration time across all possible input lengths—that is, the decoding-phase iteration time, which is constant for a given model and hardware configuration. The paper states that quanta for successive queues follow a doubling pattern:

"FastServe sets the quantum of the lower priority queue to two times of that of the higher priority queue, which aligns with previous work [34] on MLFQ." (Section 4.1, Algorithm 1 explanation)

So $q_2 = 2q_1, q_3 = 4q_1, q_4 = 8q_1$ , etc. This exponential spacing ensures that a job that generates $k$ tokens total will, in the worst case, be demoted only $O(\log k)$ times.

Skip-join rule (lines 6–9 of Algorithm 1). When a new job arrives, rather than always entering $Q_1$ , the scheduler queries the Job Profiler to obtain the job's initialization-phase time $t_{init}$ (the predicted time for its first iteration, based on its input length and the profiled iteration times for the current model and hardware). The scheduler then finds the highest-priority queue whose quantum is at least $t_{init}$ :

$p_{job} = \min i, \text{ s.t. } q_i \geq t_{init}$

where $p_{job}$ is the index of the queue the job joins, $i$ indexes queues from 1 (highest) to $n$ (lowest), and $q_i$ is the quantum of queue $i$ .

Operational meaning: A job with input length 512 on OPT-2.7B might have $t_{init} \approx 0.05$ seconds. If $q_1 = 0.002$ (the decoding iteration time), $q_2 = 0.004$ , $q_3 = 0.008$ , $q_4 = 0.016$ , $q_5 = 0.032$ , $q_6 = 0.064$ , then the scheduler would select $Q_6$ (since $0.064 \geq 0.05$ ), skipping queues 1 through 5. The job does not enter $Q_1$ through $Q_5$ at all—hence "skip-join."

Why this form: The skip-join rule solves the initialization-phase quantum exhaustion problem by ensuring a job always enters a queue whose quantum is large enough to accommodate at least its first iteration. This eliminates the preemption dilemma: the job can complete its first iteration within its initial quantum, so the scheduler never has to decide whether to preempt mid-initialization. The rule also ensures that jobs with shorter inputs (smaller $t_{init}$ ) enter higher-priority queues than jobs with longer inputs. This provides the benefit of fixed-priority scheduling (short-initialization jobs get priority) without its blindness to output length: once decoding begins, the constant per-iteration time interacts with the MLFQ demotion mechanism to handle output-length variation (see below). The "skip" aspect is critical for efficiency: if a long-initialization job were required to traverse $Q_1, Q_2, \ldots$ sequentially, it would be preempted and demoted multiple times before producing even one output token, each preemption wasting the partially-completed initialization phase.

Demotion rule (lines 16–17 of Algorithm 1). After each iteration, the scheduler checks whether the job has exhausted its quantum in its current queue. The quantum tracks total accumulated execution time within the current queue—not total time since arrival. If the accumulated time in the current queue exceeds $q_i$ , the job is demoted from $Q_i$ to $Q_{i+\eta}$ , where $\eta$ is a configurable demotion step (the paper implies $\eta=1$ in the example from Figure 7, with "demoted to the next priority queue"). The paper states:

"FastServe demotes a job to an $\eta$ times lower priority queue based on its next iteration time." (Section 4.1)

Operationally: during the decoding phase, each iteration takes time $t_{dec}$ (roughly constant). Suppose a job is in $Q_3$ with quantum $q_3 = 4t_{dec}$ . It can complete up to $\lfloor q_3 / t_{dec} \rfloor$ iterations in $Q_3$ —roughly 4 iterations—before exhausting its quantum. If it generates more than 4 tokens, it will be demoted to $Q_4$ (with quantum $q_4 = 8t_{dec}$ ), where it can generate up to roughly 8 more tokens before further demotion. This feedback mechanism ensures that the total number of demotions grows logarithmically with output length, and that short-output jobs (which finish before exhausting even one quantum) remain at their initial high priority throughout their lifetime.

Why this form: The demotion mechanism is what makes MLFQ approximate SRPT in the face of unknown output length. A job that generates few tokens will finish within one or two quanta and experience no (or few) demotions, receiving high-priority service throughout its short life. A job that generates many tokens will be progressively demoted, receiving service less frequently as it reveals itself to be "long." This self-revealing property allows the scheduler to prioritize short jobs without knowing output lengths in advance. The key insight of the paper's design is that this mechanism works cleanly only if the initial quantum is large enough for the first iteration—which the skip-join rule ensures.

Starvation prevention (lines 19–21 of Algorithm 1). A risk of the skip-join + demotion mechanism is that jobs with long inputs AND long outputs (starting in low-priority queues and being further demoted) may be perpetually starved—always preempted by newly arriving short-input jobs. The scheduler prevents this through a promotion mechanism governed by a threshold parameter $\alpha$ :

"FastServe tunes $\alpha$ based on the user-specified SLO, which is set to 300 ms by default." (Section 4.1)

Each job tracks its starve time—the accumulated wall-clock time since it was last executed. Periodically (each scheduling cycle), the scheduler checks whether any job's starve_time exceeds $\alpha$ . If so, the job is forcibly promoted to $Q_1$ (the highest-priority queue), regardless of its current queue, and its starve time is reset to zero.

Operational meaning: Suppose a job with input length 2048 generates 200 output tokens. It initially skip-joins to a low-priority queue (because $t_{init}$ is large), gets demoted further as it produces tokens, and rarely reaches the head of its queue because higher-priority queues always have work. After approximately 300 ms of cumulative waiting, the scheduler promotes it to $Q_1$ . In $Q_1$ , the quantum is small ( $q_1 = t_{dec}$ ), so the job produces at most one token before being demoted again. This "priority boost" ensures the job makes at least some forward progress, preventing indefinite starvation while still allowing the scheduler to prioritize shorter jobs most of the time.

Why this form: Starvation prevention is a standard concern in MLFQ-based scheduling, but it is especially acute in the LLM serving setting because the range of job "sizes" (output lengths) spans orders of magnitude—from single-token responses to multi-paragraph generations. Without promotion, a job that produces 1000 tokens could wait for minutes while the system processes hundreds of short jobs. The threshold $\alpha$ is tied to the Service Level Objective (SLO)—the user-specified latency target—ensuring that even the longest jobs complete within acceptable bounds. The paper validates this empirically: Figure 12 shows that FastServe's P95 tail latency (which reflects the worst-case performance for long jobs) is substantially better than baselines, and Figure 13 shows high SLO attainment rates at various multiples of the base latency.

Batch formation (lines 22–25 of Algorithm 1). After processing all job movements (skip-join for new arrivals, demotions for quantum-exhausted jobs, promotions for starved jobs), the scheduler forms a batch of up to MaxBatchSize jobs to dispatch for one iteration. It iterates through queues from highest to lowest priority, selecting jobs that are in a "ready" state (not waiting for KV cache upload or other preconditions) and adding them to the output batch until MaxBatchSize is reached or all queues are exhausted. The batch is then dispatched to the execution engine for one iteration.

Scheduling example (Figure 7). The paper provides a concrete walkthrough that crystallizes the design. Three jobs arrive simultaneously: J1 (input length large ⇒ large $t_{init}$ ; 2 total iterations), J2 (input length small ⇒ small $t_{init}$ ; 2 total iterations), J3 (medium; 2 total iterations). Under FCFS (Figure 7a), processing order is J1 → J2 → J3 (first-come-first-served order), and average completion time is 4.23 time units. Under original MLFQ (Figure 7b), all jobs start in $Q_1$ , but J1's large $t_{init}$ causes preemption before its first iteration completes, wasting work; average completion time is 5.0—worse than FCFS. Under skip-join MLFQ (Figure 7c), J1 skip-joins to $Q_4$ (because $t_{init}$ is large), while J2 and J3 skip-join to higher-priority queues. J2 finishes first, then J3, then J1; average completion time is 3.3, approaching the SRPT optimum of 3.0 (Figure 7d). The paper remarks:

"Generally, algorithms that have access to more information perform better than those with limited information."

The Key-Value Cache Memory Problem

Preemptive scheduling at token granularity creates a data management crisis. To understand why, we must first understand what the KV cache is and why it is large.

What is the KV cache? In the Transformer architecture (Figure 2), each layer contains a Masked Self-Attention module. During attention computation, for each token position, the model computes a query vector (what this position is "looking for"), a key vector (what this position "offers" to other positions), and a value vector (the information to aggregate). To compute attention for token $t$ , the model must compute the dot product of token $t$ 's query with the keys of all preceding tokens (1 through $t-1$ ), then use those attention weights to aggregate the values. Without caching, each iteration would recompute the keys and values for all preceding tokens—an $O(t^2)$ cost that grows quadratically with sequence length.

The KV cache optimization (introduced by fairseq [24] and adopted universally) stores the computed key and value vectors for each token in GPU memory after they are first computed. Figure 3 illustrates the mechanism:

Initialization phase (first iteration): The model processes all input tokens simultaneously, computing keys and values for each, storing them in the KV cache ("Cache" arrows in Figure 3, left). This is a parallel operation over the input sequence.
Decoding phase (subsequent iterations): For each new output token, the model computes only that token's query, key, and value. The keys and values for all preceding tokens are retrieved from the cache rather than recomputed ("Retrieve" arrows in Figure 3, right), and the new token's key and value are stored in the cache ("Update" arrows). This reduces per-iteration work to $O(t)$ rather than $O(t^2)$ .

The memory cost is substantial. For a single inference job with input length $s$ and current output length $t$ (so total sequence length $s + t$ ), the KV cache stores, for each of the $l$ Transformer layers, $h$ -dimensional key and value vectors for every token. With FP16 precision (2 bytes per element), the total KV cache size in bytes is:

$KV_{size} = 4 \times l \times h \times (s + t)$

where $l$ is the number of layers, $h$ is the hidden dimension, and the factor of 4 accounts for: 2 (key + value) × 2 bytes (FP16) = 4 bytes per dimension per token per layer.

For OPT-175B: $l = 96$ , $h = 12288$ . With input length $s = 512$ and minimum output length $t = 1$ :

$KV_{size} = 4 \times 96 \times 12288 \times 513 \approx 2.3 \times 10^9 \text{ bytes} = 2.3 \text{ GB}$

This is for a single job that has generated one output token. As output length grows, the KV cache grows linearly—a job generating 256 tokens would require approximately $4 \times 96 \times 12288 \times 768 \approx 3.4$ GB, and the memory is held as long as the job is active (suspended or running).

Why preemptive scheduling explodes memory usage. Under FCFS run-to-completion, the system only needs to hold KV caches for the currently executing batch—at most MaxBatchSize jobs. When a batch completes, all KV caches are freed. Under preemptive MLFQ scheduling, the system must hold KV caches for all jobs that have started but not yet finished, which includes:

The currently executing batch (up to MaxBatchSize jobs).
All partially-completed jobs in all priority queues that have been preempted and are awaiting resumption.

Figure 8 demonstrates the quantitative difference. For a synthetic workload on OPT-2.7B (a small model) with maximum output length 20, the peak KV cache memory consumption under the skip-join MLFQ scheduler is approximately 15 GB, compared to approximately 2 GB under FCFS—a 7× increase. For larger models, the absolute numbers are much larger and the problem becomes urgent. The paper states:

"The GPU memory demand becomes even more pronounced when deploying larger LLMs like OPT 175B." (Section 4.2)

Since an A100 GPU has 80 GB of which a substantial portion is consumed by model weights (350 GB across 16 GPUs for OPT-175B means approximately 22 GB per GPU for weights alone, plus overhead), the remaining KV cache budget is severely constrained. Under MLFQ, the KV cache for all suspended jobs can easily overflow this budget.

Why two naive solutions fail. The paper explicitly analyzes and rejects two approaches:

Strawman 1: Defer new jobs when GPU memory is full. This is what existing systems like vLLM do—when KV cache memory is exhausted, newly arrived jobs must wait, regardless of their priority. The paper explains why this defeats the purpose of MLFQ in the LLM context:

"In this manner, although new jobs are assigned with higher priority, they are blocked to await the free memory space. Under extreme GPU memory-constrained settings (e.g., long sequence inference), this solution would degenerate MLFQ to FCFS, which again suffers from head-of-line blocking." (Section 4.2)

The key dynamic: if all in-flight jobs are long-sequence (consuming large KV caches), the GPU stays full, and newly arriving short jobs—which should receive immediate high-priority service—cannot be admitted. The MLFQ's priority mechanism becomes irrelevant because memory unavailability overrides scheduling priority. Preemption without memory management is no preemption at all.

Strawman 2: Kill and recompute low-priority jobs. Release the KV caches of the lowest-priority suspended jobs (discarding them entirely) to free GPU memory for high-priority arrivals. When the killed jobs resume later, they must recompute their KV caches from scratch:

"This solution has two problems. First, the killed jobs lose their generation states, necessitating to rebuild their key-value tensors. This results in the waste of valuable computational resources and time. Second, it may cause deadlocks." (Section 4.2)

The deadlock scenario (Section 4.2, paragraph on "Strawman solution 2"): Job A (low priority) is killed to free memory for Job B (high priority). Job B runs. Due to starvation prevention (Section 4.1), Job A's starve time eventually exceeds $\alpha$ , and it is promoted to $Q_1$ . Job A now has higher priority than Job B. If memory is still tight, Job A may need to kill Job B to proceed. But Job B, once killed, will itself eventually be promoted... This cyclical dependency can cause both jobs to be killed and recomputed repeatedly without making progress.

Proactive Key-Value Cache Management

The core insight of the KV cache management design is that GPU memory and host memory can be treated as a two-level cache hierarchy, with data movement overlapped with computation to hide its latency (Section 4.2 and Figure 9).

Key observation: KV cache residency requirement. The KV cache for a job must reside in GPU memory only when that job is being executed (i.e., during the iteration that generates its next token). While the job is suspended in a queue awaiting its next scheduling slot, its KV cache can reside in host memory. This is the fundamental enabler for memory offloading.

The latency challenge. Swapping KV caches between GPU memory and host memory is not free. The paper quantifies this:

"When deploying OPT 175B on 16 NVIDIA A100 GPUs, the key-value tensors of a job can occupy 2.3 GB memory. The token generation time in the decoding phase is about 60 ms, while the time to swap the key-value tensors between host memory and GPU memory with PCIe 4.0×16 full bandwidth is about 36 ms." (Section 4.2)

So for a single job on OPT-175B, swapping its entire KV cache takes approximately 60% of the time it takes to generate one token. If swapping and inference are done sequentially (reactively), this adds substantial overhead to every job that requires a swap.

Proactive swapping (Figure 9). Rather than waiting until a job needs to be executed and then swapping its data, the proactive mechanism initiates swaps before the job is scheduled, overlapping the data movement with the execution of the currently running batch:

Figure 9a (reactive): The PCIe bus is idle during the execution of Job J1. When J1 finishes or is preempted, the system begins swapping J2's KV cache from host to GPU memory. The GPU is idle during this transfer. Then J2 executes. Total time = $t_{exec}(J1) + t_{swap}(J2) + t_{exec}(J2)$ .
Figure 9b (proactive): While J1 executes on the GPU, the system simultaneously transfers J2's KV cache over PCIe. By the time J1 completes, J2's data is already in GPU memory. The GPU immediately begins executing J2. Total time = $\max(t_{exec}(J1), t_{swap}(J2)) + t_{exec}(J2)$ , where the $\max$ approaches $t_{exec}(J1)$ if the swap is fully hidden. This is faster than reactive swapping by up to $t_{swap}$ .

The proactive approach transforms the swapping overhead from a latency addition to a latency overlap—the extra cost is effectively zero for the end-to-end schedule, provided the swap time is less than or equal to the execution time of the concurrent batch.

The Estimated Next Scheduled Time (ENST). The proactive mechanism must decide which KV caches to swap in or out, and in what order, to maximize overlap and minimize the likelihood that a job must wait for an unfinished swap. The paper defines the ENST metric to guide these decisions (Section 4.2, equations and surrounding text).

The intuition: a job's KV cache should be swapped out of GPU memory to host memory if the job will not be scheduled again for a long time (high ENST, freeing space for active jobs). A job's KV cache should be swapped in from host memory to GPU memory if it will be scheduled soon (low ENST), so it is ready when needed. Jobs with intermediate ENST might remain where they are. The challenge is estimating when a job will next be scheduled under the MLFQ policy, which depends on the job's current priority, the quanta of all higher-priority queues, the job's starvation timer, and the batch size.

The ENST for job $i$ is computed as the minimum of two competing effects:

$\text{ENST}(i) = \min\left(T_{promote}(i), T_{execute}(i)\right)$

where $T_{promote}(i)$ is the time until job $i$ is promoted to $Q_1$ due to starvation prevention, and $T_{execute}(i)$ is the estimated time until job $i$ would naturally reach the head of its queue given the higher-priority workload ahead of it.

Computing $T_{promote}(i)$ (starvation-driven next-scheduled time). Each job tracks its accumulated starvation time since last execution. The starvation prevention threshold $\alpha$ (default: 300 ms) defines the maximum waiting time. Therefore:

$T_{promote}(i) = \alpha - \text{starve\_time}(i)$

If job $i$ has already waited 200 ms, then $T_{promote}(i) = 300 - 200 = 100$ ms. If it hasn't been waiting long (starve_time small), this term is large and won't dominate the ENST.

What it computes: the remaining time before the starvation prevention mechanism forcibly promotes this job to the highest priority, giving it an execution slot. After this time, the job will be scheduled regardless of queue priority.

Why this form: starvation prevention guarantees an upper bound on waiting time; the ENST must respect this bound because the swap manager must have the job's KV cache in GPU memory by this deadline at the latest. Using $\min$ ensures the ENST is conservative—it reflects whichever mechanism will schedule the job soonest.

Computing $T_{execute}(i)$ (priority-driven next-scheduled time). This term estimates how long the job must wait based on the work ahead of it in higher-priority queues. For each higher-priority queue $Q_k$ (where $k$ ranges from job $i$ 's current priority index $+1$ up through the highest priority), all jobs in those queues will be executed before job $i$ . The total execution time contributed by a single job $j$ in a higher-priority queue, as it is demoted from its current priority down to job $i$ 's priority level, is:

$T_{execute}(i, j) = \sum_{i.priority < k \leq j.priority} q_k$

where $j.priority$ is the priority index of job $j$ , $i.priority$ is the priority index of job $i$ , and $q_k$ is the quantum of queue $k$ . This sum tallies the time job $j$ can spend in each intermediate queue as it is progressively demoted.

What it computes: the total CPU/GPU execution time that one specific higher-priority job $j$ will consume before it is demoted to job $i$ 's priority level or lower, assuming the job does not finish before reaching $i$ 's level (conservative assumption for estimating upper-bound waiting time).

The total execution time of all higher-priority jobs ahead of job $i$ is then:

$T_{execute}(i) = \frac{1}{B} \sum_{i.priority < j.priority} T_{execute}(i, j)$

where $B$ is the maximum batch size. The division by $B$ accounts for the fact that up to $B$ jobs can execute simultaneously in a batch.

What it computes: the expected wall-clock time until all jobs currently in higher-priority queues have been executed at least once each, given that the system processes them in batches of size $B$ . This is a rough estimate—the paper acknowledges the simplifying assumption that "those jobs do not finish earlier before being demoted to the priority queue of job $i$ ."

Why this form for ENST: Taking the minimum of the promotion-driven time and the priority-driven time captures the earliest possible next-scheduling opportunity. The ENST is used to rank jobs for swapping:

Jobs with the largest ENST are swapped out first (they won't be needed soon, so their GPU memory can be freed).
Jobs with the smallest ENST are swapped in first (they will be needed soon, so their data should be resident in GPU memory).

This ranking ensures the KV cache manager makes forward-looking decisions that minimize the probability of a cache miss (a job being scheduled while its KV cache is still in host memory, incurring reactive swap latency).

Handling bursts of new jobs (Section 4.2). The proactive mechanism assumes gradual, predictable job arrivals. When a burst of new high-priority jobs arrives simultaneously, the manager may be forced to evict existing jobs reactively because there isn't time to proactively swap before the burst hits. To mitigate this:

"FastServe reserves some idle key-value cache slots specifically for new jobs, ensuring immediate availability without the need for reactive job swapping." (Section 4.2)

The number of reserved slots is tuned based on historical job arrival patterns—"a higher frequency of job bursts necessitates a larger number of reserved slots." This trades some GPU memory capacity (kept idle) for latency predictability during bursty arrivals.

Swapping overhead in practice (Figure 15b). The paper measures the actual latency impact of proactive swapping by breaking down end-to-end latency into three components: queuing delay, execution time, and swapping time (the time a job is blocked waiting for a swap to complete). Figure 15b shows that swapping time accounts for less than 5% of end-to-end latency across all arrival rates for OPT-13B on ShareGPT. This validates the proactive design: the overlap hides nearly all swapping cost. In contrast, the paper shows in Figure 15a that the reactive approach causes substantial performance degradation at moderate-to-high arrival rates (latency is approximately 2.7× higher at an arrival rate of 3.0 jobs/second), and the recomputation approach is even worse (approximately 2.7× worse than reactive at high load due to wasted recomputation cycles).

Distributed Serving Extensions

For models that exceed single-GPU capacity (e.g., OPT-175B at 350 GB weights), FastServe extends the scheduler and KV cache manager to work across multiple GPUs using tensor parallelism and pipeline parallelism (Section 4.3).

Tensor parallelism review. Tensor parallelism splits individual operators (e.g., a matrix multiplication in a Transformer layer) across multiple GPUs. Each GPU holds a horizontal slice of the weight matrix, computes its portion of the output, and an all-reduce communication step aggregates results. The key property relevant to scheduling: all GPUs in a tensor-parallel group execute the same operations on the same job at the same time—they are tightly synchronized.

Pipeline parallelism review. Pipeline parallelism splits the layers of the model into sequential stages, with each stage assigned to a different GPU (or tensor-parallel group of GPUs). During inference, a job's intermediate activations flow from stage 1 to stage 2 to stage 3, etc. Multiple jobs can be in-flight simultaneously across different pipeline stages—while stage 2 processes job A, stage 1 can begin processing job B. This is a form of temporal parallelism that increases throughput but requires the scheduler to manage multiple active jobs concurrently.

Scheduling under pipeline parallelism (Section 4.3). The key challenge: in classical MLFQ, if no new job arrives, the scheduler would continue executing the same job until it finishes or is demoted. But under pipeline parallelism, after a job completes its first stage and sends intermediate results to the next stage, the first stage becomes idle—it can begin processing a different job while the original job is still in flight in later stages. The scheduler must decide what to run next at each stage boundary, not just at job boundaries.

FastServe's approach:

"To preserve the semantics of MLFQ, FastServe still keeps the running job in the priority queue, but schedules the highest priority job in the pending state." (Section 4.3)

Operationally: When stage 1 finishes processing job A and transmits intermediate results to stage 2, the scheduler does not demote or remove job A from its priority queue—the job is still "running" from the system's perspective, just in a later pipeline stage. The scheduler then selects the next highest-priority job that is in the "pending" (ready) state to begin processing on stage 1. This means multiple jobs can be actively consuming quanta simultaneously across different pipeline stages. The quantum accounting tracks per-job execution time, so each job accumulates time toward its quantum independently. A job will be demoted when its total accumulated execution time (summed across all pipeline stages it has traversed within its current priority level) exceeds its queue's quantum.

KV cache management under distributed serving. The KV cache is partitioned across GPUs following the same partition scheme as the model itself:

"In LLM inference, each key-value tensor is used by the same stage of the LLM. Therefore, FastServe partitions key-value tensors as tensor parallelism requires, and assigns each key-value tensor to the corresponding GPU so that all computation on a GPU only needs local key-value tensors on the same GPU." (Section 4.3)

This is an important design choice: KV cache tensors for a given layer reside on the same GPU that computes that layer. When the model uses tensor parallelism within a stage, each tensor-parallel GPU in the group holds a shard of the KV cache for that stage. This locality ensures that attention computation can access the KV cache directly from local GPU memory without cross-GPU KV cache transfers.

Coordinated swapping across pipeline stages. A challenge arises because different pipeline stages process different jobs at different times. If the KV cache manager independently decides to swap a job's KV cache on stage 1 but not on stage 2 (or vice versa), the job may have its data partially resident and partially on host—leading to inconsistent state. The paper addresses this with a coordinated protocol:

"To reduce redundant control, before processing the intermediate result sent from the previous stage, the current stage does the same offloading or uploading action as the previous stage does." (Section 4.3)

The mechanism (Figure 10): The centralized KV cache manager determines which jobs should be offloaded or uploaded, and sends swapping instructions to the first pipeline stage. When the first stage transmits intermediate results to the second stage, it piggybacks the swapping instructions alongside the activation data. The second stage can then initiate its KV cache swaps for the same job(s) concurrently with receiving and processing the intermediate results—the data transfer for intermediate results (GPU-to-GPU over NVLink or network) occupies a different communication channel than the KV cache swapping (GPU-to-host over PCIe), so they proceed in parallel. This parallelism further reduces end-to-end swapping overhead because multiple stages can swap simultaneously rather than sequentially.

When tensor parallelism splits the first stage across multiple GPUs, the centralized manager sends identical swapping instructions to all GPUs in the tensor-parallel group, ensuring consistent behavior.

Implications of pipeline scheduling on batching. Under pipeline parallelism with multiple in-flight jobs, the effective batch size may temporarily exceed MaxBatchSize across the entire pipeline (if stage 1 processes batch $B_1$ while stage 2 still processes $B_0$ ), but each individual stage processes at most MaxBatchSize jobs at once. The scheduler ensures that the total system-wide concurrency respects the memory constraints: the KV cache manager tracks total KV cache memory across all stages and initiates proactive offloading when necessary, considering that a job's KV cache spans all pipeline stages.

The Job Profiler

The Job Profiler is a background component that collects execution time data offline and provides lookups at scheduling time. While not the focus of the paper's contribution, it is essential infrastructure (Section 4.1, paragraph on "Our solution: skip-join MLFQ").

What it profiles. For a given (model architecture, model size, hardware configuration), the profiler measures:

$t_{init}(s)$ : the time to execute the first iteration (initialization phase) for input sequence length $s$ .
$t_{dec}$ : the time to execute one decoding iteration (generating one additional output token), which is roughly constant for a given configuration regardless of current output length.

These measurements are collected once offline by running the model with varying input lengths on the target GPU(s) and recording iteration times.

How it is used at scheduling time. When a new job arrives, the scheduler extracts its input length $s$ (the number of tokens in the prompt). It queries the profiler: "for input length $s$ , what is $t_{init}$ ?" The profiler returns the cached measurement. This $t_{init}$ value is then used in the skip-join rule to determine which queue the job enters (see the skip-join rule equation above).

Why profiling works. Unlike total job duration (which depends on the unpredictable output length), the per-iteration execution time is deterministic:

"For each iteration, the execution is similar to the traditional one-shot DNN inference, whose execution time is highly predictable [8, 35]." (Section 4.1)

The computation within one iteration is a fixed DNN forward pass whose operations and memory footprint are determined entirely by the current sequence length (known) and the model architecture (known). The hardware (GPU model, memory bandwidth, interconnect) is fixed. Therefore, the execution time is predictable to within small variance. This is the same principle that enables Clockwork [8] for traditional DNNs, and it carries over to the per-iteration granularity of LLM inference—even though the number of iterations is unpredictable.

Relationship to the semi-information-agnostic setting. The profiler is what makes the setting semi rather than fully information-agnostic. The system knows the input length (extractable from the prompt without any inference) and the per-iteration timing (from offline profiling), giving it accurate information about the first iteration's cost. It does not know the output length, keeping the scheduling problem information-agnostic in the dimension that matters for the decoding phase. This partial knowledge is sufficient to solve the initialization-phase quantum exhaustion problem (via skip-join) while leaving the decoding-phase scheduling to the MLFQ feedback mechanism (demotion based on consumed tokens), which is designed for unknown job sizes.

Summary of Configurable Parameters

The paper specifies several tunable parameters that govern the scheduler and memory manager behavior:

Number of priority queues $n$ : Not explicitly specified in the paper, but implicitly determined by the range of quanta needed (from minimum iteration time for $q_1$ up to a quantum large enough to accommodate the largest possible $t_{init}$ for the maximum supported input length).
Queue quanta $q_1, q_2, \ldots, q_n$ : $q_1$ is set to the minimum iteration time (decoding phase). Subsequent quanta follow the doubling rule: $q_{i+1} = 2q_i$ . This exponential spacing is chosen because it aligns with prior work on MLFQ scheduling [34] and ensures logarithmic demotion count.
Starvation prevention threshold $\alpha$ : Defaulted to 300 ms (Section 4.1). Tuned based on the user-specified Service Level Objective (SLO). A smaller $\alpha$ prevents starvation more aggressively but reduces the differentiation between short and long jobs (long jobs get promoted sooner, behaving more like short jobs). A larger $\alpha$ provides stronger priority differentiation but risks violating tail latency SLOs.
Maximum batch size $B$ : Not a system parameter but a hardware constraint—determined by the GPU memory available for KV caches of the executing batch. The paper sets this to the maximum value that fits within GPU memory for the target model and hardware, and uses the same value for all baselines to ensure fair comparison.
Demotion step $\eta$ : While not explicitly stated in the paper's parameter list, the demotion rule moves jobs "to the next priority queue" (Section 4.1), implying $\eta = 1$ . The paper references the possibility of different demotion steps but does not evaluate alternatives.
Reserved KV cache slots for burst arrivals: The number is "based on historical job arrival patterns," with higher burst frequencies requiring more reserved slots (Section 4.2). This is a deployment-specific tuning parameter.
KV cache block size: FastServe implements PagedAttention [11] and inherits its block size (16 tokens by default for vLLM, though not explicitly re-stated in this paper).

4. Key Insights and Innovations

Innovation 1: Identifying Queuing Delay, Not Execution Time, as the Bottleneck—And Reframing the Problem Accordingly

The paper's most impactful intellectual move happens in the very first figure (Figure 1) and the analysis surrounding it: the frank recognition that the dominant fraction of end-to-end latency in LLM serving is not model execution but queuing delay caused by head-of-line blocking. For FCFS-based systems serving real-world workloads (ShareGPT, Alpaca), queuing delay accounts for 87.6–98.0% of total latency. The paper reframes the problem statement: optimizing GPU kernels, compressing KV caches, and reducing memory fragmentation (the focus of prior work like Orca [10] and vLLM [11]) addresses only the ~10% of latency that comes from execution. The other ~90% is a scheduling problem that execution optimizations are structurally incapable of solving.

This represents a fundamental reframing, not an incremental refinement. Prior to this work, the LLM serving literature treated the problem as an execution efficiency challenge—how to make token generation faster and how to pack more work into limited GPU memory. Orca's iteration-level scheduling was the closest prior work to addressing the scheduling dimension, but it still used FCFS with run-to-completion semantics: once a job entered the batch, it stayed until finished. The field's implicit assumption was that if execution were made fast enough, scheduling wouldn't matter. Figure 1 demolishes this assumption with concrete evidence: even with highly optimized execution (FastServe-FCFS, which uses the same efficient C++/CUDA kernels as the full system), queuing delay dominates when job sizes are heterogeneous. Optimizing execution time is a diminishing-returns game when it is not the bottleneck.

The paper's diagnostic framing—separating total latency into queuing delay and execution time, and showing the former is the dominant term—is a conceptual contribution that reorients the research agenda. It implies that future LLM serving systems should be designed as scheduling systems first, execution engines second, a priority inversion from the prevailing approach. This reframing is what licenses the entire subsequent design: if queuing delay is the problem, preemptive scheduling is the solution class, and the design challenges become those of adapting preemptive scheduling to the unique characteristics of LLM inference.

Innovation 2: The Semi-Information-Agnostic Formulation and Its Architectural Consequences

The paper introduces a precise characterization of the information available to an LLM inference scheduler: the semi-information-agnostic setting. This is subtle but consequential. Classical scheduling theory recognizes two regimes: fully informed (all job sizes known in advance, enabling optimal policies like SRPT) and fully agnostic (no prior knowledge, requiring feedback-based approximation like classical MLFQ). The paper identifies that LLM inference inhabits a third, intermediate regime:

The output length is unknown a priori (agnostic), because it depends on the semantics of the prompt and the model's generative behavior—predicting it is effectively an open research problem.
The input length is known before execution begins (informed), because the prompt text is available when the request arrives.
The per-iteration execution time is predictable (informed), because each iteration is a deterministic DNN forward pass whose cost depends only on the model architecture, hardware, and current sequence length—all known quantities.

This characterization is conceptually novel in the LLM serving context. Prior work implicitly treated the setting as either fully informed (Clockwork [8] relies on complete execution time predictability, which breaks for variable-length LLM jobs) or fully agnostic (the standard MLFQ assumption, which ignores the available input-length signal). By explicitly naming the semi-information-agnostic property, the paper creates a design space that hadn't been articulated: exploit the partial information where it exists (input length determining initial queue placement via skip-join), while using the MLFQ feedback mechanism where information is absent (output length determining demotion behavior). The skip-join mechanism is not just an engineering trick—it is the architectural consequence of correctly characterizing the information regime. The paper contrasts this with the two strawman scheduling approaches in Section 4.1 (fixed-priority and naive MLFQ), each of which exploits only one dimension of the available information and fails when the other dimension dominates.

This framing also has predictive power beyond the specific skip-join design. It suggests a family of scheduling policies that could exploit other forms of partial information—for example, if future work develops even a weak predictor of output length (e.g., a classifier that estimates whether a prompt will produce a short or long response), the semi-information-agnostic framework shows exactly how to incorporate that predictor: as additional signal for initial queue placement, while retaining the MLFQ feedback mechanism as a safety net for prediction errors. This is a theoretical contribution in the form of a design principle, not just an implemented mechanism.

Innovation 3: Proving That Memory Management, Not Just Scheduling Policy, Determines Whether Preemption Is Practical

The paper makes a systems contribution that goes beyond "preemptive scheduling reduces latency": it demonstrates that preemptive scheduling is only viable if paired with a memory management strategy that prevents GPU KV cache overflow from nullifying the scheduling gains. This insight emerges from the systematic diagnostic in Section 4.2, where the paper shows (Figure 8) that the MLFQ scheduler increases peak KV cache memory consumption by 7× compared to FCFS, and then analyzes why the two obvious workarounds (deferring new jobs or killing low-priority jobs) both fail in ways that defeat the purpose of preemption.

What makes this intellectually distinctive is not the proactive swapping mechanism itself (GPU-to-host offloading is a known technique in other contexts), but the identification of the dependency relationship: scheduling policy and memory management are not independent design choices for LLM serving—they are coupled through the KV cache, and optimizing either in isolation is fragile. Deferring new jobs (the approach of existing systems like vLLM) makes the scheduler's priority decisions irrelevant when memory is tight, because new jobs cannot be admitted regardless of priority. Killing and recomputing low-priority jobs creates deadlock cycles with starvation prevention. The paper doesn't just propose a better mechanism; it articulates why the coupling exists (the KV cache is simultaneously the state that enables efficient token generation and the memory bottleneck that limits job concurrency) and what properties a solution must have (non-blocking admission of high-priority jobs, preservation of work already invested in preempted jobs, deadlock-free interaction with priority promotion).

The proactive design's concrete demonstration that swapping overhead can be reduced to under 5% of end-to-end latency (Figure 15b) transforms the conversation around GPU memory for LLM serving. Prior work treated GPU memory capacity as a hard constraint that fundamentally limits batch size and concurrency (e.g., vLLM's PagedAttention reduces fragmentation but doesn't change the total capacity). FastServe shows that the effective KV cache capacity can be expanded to include host memory, and that the latency cost of this expansion can be nearly eliminated through proactive overlap. This is a systems-level insight about resource hierarchy: GPU memory is a cache, host memory is the backing store, and a well-designed prefetching policy can make the cache effectively transparent. The ENST metric operationalizes this insight by connecting the swapping order to the scheduler's own predictions about future job execution order—a closed-loop design where the scheduler informs the memory manager and vice versa, rather than treating them as independent layers.

Innovation 4: Resolving the Conflict Between Preemptive Scheduling and Tail Latency Through Starvation Prevention with SLO-Aware Thresholds

A standard criticism of preemptive scheduling policies that prioritize short jobs (like MLFQ and its variants) is that they risk starving long jobs, inflating tail latency. This is especially acute for LLM serving where "short" and "long" can differ by orders of magnitude—a one-token response versus a multi-paragraph generation. The paper demonstrates that this tension can be resolved by coupling the starvation prevention threshold to the user-specified SLO, rather than treating starvation prevention as a heuristic separate from the performance objective.

The design is conceptually clean: the parameter α (default: 300 ms) is the maximum time any job can wait before being forcibly promoted to the highest-priority queue. This directly encodes the latency SLO into the scheduling policy. If the SLO requires that 95% of jobs complete within some bound, setting α appropriately ensures that even the longest jobs make forward progress within that window. The empirical evidence (Figures 12 and 13) shows this works in practice: FastServe not only improves average latency but also tail latency (P95), and maintains high SLO attainment rates across different SLO stringencies. For OPT-175B on ShareGPT, FastServe improves throughput at the same P95 latency by up to 17.9× over vLLM.

This is more than just "we added a timeout." It is a design principle: the scheduling policy should be parameterized directly by the deployment's latency objectives, not by ad-hoc thresholds that require separate tuning. Prior MLFQ-based schedulers (e.g., Tiresias [34] for DL training) used starvation prevention as a safety valve but did not tie the threshold to an SLO. The paper shows that doing so simultaneously addresses the theoretical concern (MLFQ can starve long jobs) and the practical requirement (meeting tail latency SLOs), unifying the scheduling theory with the serving system's operational goals. The ENST metric in the KV cache manager further extends this principle: the starvation-driven promotion time $T_{promote}(i)$ is one of the two components of the ENST calculation, meaning the memory management system also respects the SLO by ensuring that jobs approaching their starvation limit have their KV caches swapped in before the promotion fires. This creates a consistent, SLO-aware control path that spans both scheduling and memory management.

5. Experimental Analysis

Evaluation Methodology

Dataset. The paper uses two real-world LLM conversation datasets: ShareGPT [13] (user-shared conversations with ChatGPT) and Alpaca [14] (GPT-3.5-generated self-instruct data). These datasets contain real-world input-output pairs but lack arrival timestamps, so the paper generates request arrival times following a Poisson process parameterized by an arrival rate, following the methodology of prior work [11]. The choice of these datasets is motivated by their long-tailed output length distributions, which create the head-of-line blocking problem that FastServe targets.
Base model(s). The paper evaluates on the OPT family [18] at three scales: OPT-13B (40 layers, 40 attention heads, 5120 hidden dimension, 26 GB weights), OPT-66B (64 layers, 72 heads, 9216 hidden dimension, 132 GB weights), and OPT-175B (96 layers, 96 heads, 12288 hidden dimension, 350 GB weights). OPT was chosen as a representative open-source LLM family widely used in both academia and industry. All models use FP16 precision. OPT-175B is explicitly noted as "an open-source LLM similar to the largest GPT-3 model" (Section 1).
Metrics. The primary metric is average per-token latency, calculated as "the mean of every job's end-to-end latency divided by its output length" (Section 6.1). This normalizes for varying output lengths and measures user-perceived responsiveness. The paper also reports P95 tail latency (the 95th percentile of per-token latency across jobs) and P95 goodput (the throughput achievable when 95% of jobs meet their latency SLO). For throughput comparison, the paper sets a latency Service Level Objective (SLO) at 10× the latency of a single decoding-phase iteration, which is specified as 0.3 seconds based on profiling. Throughput is then measured as the maximum job arrival rate at which the system maintains per-token latency below this SLO.
Baselines. Four systems are compared:
- FasterTransformer [26]: NVIDIA's production-grade inference engine (v5.3), which implements highly optimized GPU kernels and supports tensor and pipeline parallelism, but uses job-level scheduling—once a batch starts, it runs to completion for all jobs.
- vLLM [11]: The state-of-the-art LLM serving system (v0.1.7) that implements iteration-level scheduling [10] and PagedAttention [11] to reduce KV cache memory fragmentation, but uses FCFS scheduling with run-to-completion execution.
- FastServe-FCFS: FastServe's distributed execution engine (same C++/CUDA implementation, same optimizations) but without the skip-join MLFQ scheduler or proactive KV cache management—it uses FCFS scheduling. This baseline isolates the contribution of the paper's techniques from implementation efficiency differences.
- FastServe: The full system with skip-join MLFQ scheduler and proactive KV cache management.
All baselines use the same tensor parallelism size, pipeline parallelism size, and batch size as FastServe for fair comparison, with the exception that vLLM only uses tensor parallelism for OPT-175B because it does not support pipeline parallelism (Table 2).
Generation budget / compute accounting. The paper does not frame the evaluation in terms of a "compute budget" the way a scaling laws paper would—this is a systems paper evaluating serving throughput and latency, not a methods paper evaluating accuracy vs. compute. Fairness is ensured by giving all systems the same GPU hardware (same number and type of GPUs), the same model at the same precision, and the same maximum batch size. The arrival rate (jobs/second) is varied to measure the latency-throughput curve, and throughput at the SLO boundary is compared.
Cross-validation / statistical protocol. No formal cross-validation is reported. The evaluation uses end-to-end system measurements under simulated Poisson-arrival workloads, with multiple arrival rates swept to produce latency-throughput curves. The paper does not report confidence intervals or error bars, and does not describe multiple runs with different random seeds for the arrival process. This is consistent with standard practice in systems conferences (SOSP, OSDI) where the focus is on demonstrating system-level improvements under controlled workload generation rather than statistical hypothesis testing over multiple data splits.

Main Quantitative Results

End-to-End Latency and Throughput Under ShareGPT Workload

Figure 11 (first row) presents the core end-to-end results for the ShareGPT dataset across three model scales. The key headline: FastServe consistently achieves dramatically lower average per-token latency than all baselines at every arrival rate, and can sustain substantially higher throughput before crossing the SLO threshold (0.3 s/token).

For OPT-13B on a single A100 GPU (Figure 11a): vLLM maintains latency below the SLO up to approximately 1.5–2.0 jobs/second. FastServe-FCFS improves this to approximately 2.5 jobs/second due to its more efficient C++ implementation and kernel fusion. FastServe extends this to approximately 4.0–4.5 jobs/second before crossing the SLO—roughly 2–3× higher than vLLM and 1.6–1.8× higher than FastServe-FCFS. FasterTransformer, lacking iteration-level scheduling entirely, crosses the SLO at very low arrival rates (below 1 job/second). The paper quantifies the overall throughput improvement: FastServe outperforms FasterTransformer by 31.5–74.9× in terms of throughput under the SLO.

For OPT-66B on 4 A100 GPUs (Figure 11b): vLLM sustains roughly 2.5–3.0 jobs/second under SLO, while FastServe reaches approximately 5.0–5.5 jobs/second—an improvement of roughly 1.7–2.2× over vLLM and 1.4–1.8× over FastServe-FCFS. The relative gain is slightly smaller than for OPT-13B because the model is larger and absolute throughput is lower across all systems, compressing the dynamic range.

For OPT-175B on 16 A100 GPUs (Figure 11c): vLLM sustains approximately 2.5–3.0 jobs/second under SLO, while FastServe reaches approximately 6.0–6.5 jobs/second—roughly 2.1–2.6× higher. FastServe-FCFS achieves approximately 4.5 jobs/second, making the contribution of the skip-join MLFQ and proactive memory management approximately 1.3–1.4× on top of the efficient implementation. The paper's claim of 18.3× improvement over vLLM (stated in Section 6.2) corresponds to the maximum ratio across all model sizes and datasets at the boundary of the measurable range, not the ratio at a specific arrival rate.

The paper emphasizes that even at low arrival rates (where queuing delay is minimal), FastServe maintains lower latency than baselines because its scheduler can immediately begin processing short jobs rather than queuing them behind longer-running jobs. At higher arrival rates where queuing dominates, the gap widens dramatically.

End-to-End Latency and Throughput Under Alpaca Workload

Figure 11 (second row) shows results for the Alpaca dataset. Since Alpaca jobs are generally smaller (shorter input and output lengths), all systems can sustain higher absolute arrival rates before crossing the SLO, but the relative ordering is preserved. For OPT-13B (Figure 11a, second row), vLLM sustains approximately 15–20 jobs/second, FastServe-FCFS approximately 25 jobs/second, and FastServe approximately 35–40 jobs/second—roughly 1.6–2.7× over vLLM. For OPT-66B, the throughput advantage is approximately 1.5–2.0×. For OPT-175B, FastServe improves throughput by 3–31.4× over vLLM (the 31.4× figure is the paper's stated maximum; visual inspection of Figure 11c suggests the typical advantage is closer to 2–3× at comparable latency). FastServe outperforms FasterTransformer by 9.5–15.8× on Alpaca. FastServe-FCFS outperforms FastServe itself by approximately 1.6–2× on Alpaca.

A notable observation: the relative advantage of FastServe over FastServe-FCFS is somewhat smaller on Alpaca than on ShareGPT. This is consistent with the head-of-line blocking diagnosis: Alpaca has a less extreme long tail in output length distribution, so FCFS suffers less from blocking, and the preemptive scheduler's advantage is correspondingly smaller. This is not stated explicitly in the paper but can be inferred from the figures.

Tail Latency Results

Figure 12 presents P95 (95th percentile) per-token latency for the ShareGPT dataset. The paper uses this to address the concern that preemptive scheduling and MLFQ can cause starvation for long jobs, hurting tail latency. The headline: FastServe simultaneously improves both average and tail latency, with substantial throughput gains at the same P95 latency SLO.

For OPT-13B (Figure 12a): at the P95 SLO of 0.3 s/token, vLLM sustains approximately 1.0–1.5 jobs/second, FastServe-FCFS approximately 1.5–2.0 jobs/second, and FastServe approximately 3.5–4.0 jobs/second—roughly 2.8–4.0× over vLLM and 2.0–2.3× over FastServe-FCFS. The paper states that FastServe improves throughput by up to 2–2.8× over FastServe-FCFS for OPT-13B and OPT-66B.

For OPT-175B (Figure 12c): vLLM sustains approximately 2.0 jobs/second at the P95 SLO, while FastServe reaches approximately 5.0 jobs/second—roughly 2.5× higher. FastServe-FCFS reaches approximately 3.3 jobs/second. The improvement of FastServe over FastServe-FCFS at the P95 SLO is approximately 1.5×. The paper reports overall improvements of up to 17.9× and 59.8× compared to vLLM and FasterTransformer, respectively, under the same tail latency SLO.

The mechanism behind the tail latency improvement: starvation prevention (Section 4.1, threshold α = 300 ms) ensures that even long jobs are promoted to the highest-priority queue and make forward progress within acceptable bounds. The paper argues that prioritizing short jobs actually helps long jobs indirectly by reducing their queuing delay—when short jobs are processed quickly, they vacate the system sooner, freeing resources for long jobs. The net effect is that both average and tail latency improve.

Goodput Under Varying SLOs

Figure 13 evaluates P95 goodput for OPT-13B under three SLO stringencies: 5×, 10×, and 20× the latency per phase (initialization and decoding) under light load. Goodput is defined as throughput when 95% of jobs meet their SLO. This metric captures the tradeoff between maximizing throughput and meeting latency guarantees.

At 5× SLO (the strictest): vLLM achieves approximately 0.63 jobs/second, FastServe-FCFS approximately 1.77 jobs/second, and FastServe approximately 2.59 jobs/second—roughly 4.1× over vLLM and 1.46× over FastServe-FCFS.

At 10× SLO (the default throughout the paper): vLLM achieves approximately 0.64 jobs/second, FastServe-FCFS approximately 1.83 jobs/second, and FastServe approximately 3.01 jobs/second—roughly 4.7× over vLLM and 1.64× over FastServe-FCFS.

At 20× SLO (the most relaxed): the pattern holds, with FastServe achieving approximately 3.15 jobs/second versus vLLM's 0.76 jobs/second—roughly 4.1× over vLLM. The paper states that FastServe "outperforms vLLM by 4.1× to 4.7× and FastServe-FCFS by 1.46× to 1.64×" across the three SLO settings.

This experiment demonstrates two things. First, the relative advantage of the skip-join MLFQ scheduler (FastServe vs. FastServe-FCFS) is consistent across different SLO stringencies—it is not an artifact of a particular threshold. Second, FastServe maintains high goodput even under strict SLOs, suggesting the starvation prevention mechanism effectively bounds tail latency without sacrificing the throughput benefits of preemptive scheduling.

Ablation Studies and Robustness Checks

The paper evaluates design choices through a series of controlled experiments on OPT-13B under the ShareGPT workload, each isolating the contribution of a specific component. These experiments are described in Section 6.3, and each uses the same single-GPU testbed to provide fair within-paper comparisons.

Skip-join MLFQ scheduler effectiveness (Figure 14). The paper compares four scheduling policies—FCFS, Fixed Priority (jobs prioritized by input length only), Naive MLFQ (classical MLFQ with all jobs entering $Q_1$ ), and Skip-Join MLFQ (FastServe)—while varying the ratio between input and output lengths in the workload. This ratio is a key experimental knob because it controls whether the initialization phase or the decoding phase dominates total job time. The latency is normalized to the slowest system at each ratio. FCFS consistently has the highest latency (normalized to 1.0) due to head-of-line blocking at all ratios. Naive MLFQ performs well at low ratios (where initialization phase is not dominant and classical MLFQ's queue structure works as designed), but degrades significantly as the ratio increases—at a ratio of 256, Naive MLFQ's normalized latency is approximately 0.45–0.50 compared to FCFS. Fixed Priority shows the opposite pattern: it performs poorly at low ratios (normalized latency ~0.70 at ratio 0.25, because it ignores decoding-phase variation) but improves at high ratios (approaching ~0.10 at ratio 256, because initialization phase dominates and input-length-based priority approximates SRPT). Skip-Join MLFQ consistently achieves the lowest normalized latency across all ratios, from approximately 0.11 at ratio 0.25 to approximately 0.07 at ratio 256. The paper quantifies the improvement: FastServe outperforms FCFS, Naive MLFQ, and Fixed Priority by up to 8.9×, 1.87×, and 13.9×, respectively. This experiment validates the core design claim: skip-join MLFQ exploits the semi-information-agnostic setting to outperform both input-length-only scheduling (Fixed Priority) and classical MLFQ, and its advantage is robust to variations in the relative importance of input and output length.
KV cache management policy comparison (Figure 15a). The paper compares three approaches to handling KV cache memory pressure under the skip-join MLFQ scheduler: Recompute (discard KV caches of low-priority jobs and recompute when needed), Reactive swapping (swap KV caches between GPU and host memory on-demand when memory is full), and Proactive swapping (FastServe's design with ENST-based prefetching and overlapping data transfer with computation). At low arrival rates (below ~1.0 jobs/second), all three approaches perform identically because GPU memory is sufficient to hold all KV caches—no swapping or recomputation is triggered. As the arrival rate increases beyond approximately 1.5 jobs/second, GPU memory becomes insufficient, and the approaches diverge sharply. At an arrival rate of 2.5 jobs/second: Reactive achieves latency of approximately 0.18–0.20 s/token, Proactive achieves approximately 0.10–0.12 s/token, and Recompute achieves approximately 0.28–0.30 s/token. The paper states that Proactive outperforms Reactive by 1.7× and Recompute by 2.7×. The Proactive curve continues to maintain lower latency than the others as arrival rates increase, though all approaches eventually cross the SLO as the system saturates. This experiment demonstrates that: (a) swapping to host memory is necessary (Recompute, which discards work, is significantly worse); (b) the proactive approach of overlapping data transfer with computation is substantially better than reactive (on-demand) swapping; and (c) the advantage grows with load, as the opportunity for overlap increases when more jobs are in flight.
Latency breakdown with proactive swapping (Figure 15b). The paper decomposes FastServe's end-to-end latency into three components: queuing delay (time waiting in the priority queues), execution time (actual token generation on the GPU), and swapping time (time the job is blocked waiting for KV cache data transfer to complete). This breakdown is shown across the range of arrival rates for OPT-13B on ShareGPT. The key finding: swapping time accounts for less than 5% of total latency at all arrival rates. At an arrival rate of 1.0 jobs/second, swapping is approximately 0% (entirely hidden), queuing is approximately 10%, and execution is approximately 90%. As arrival rates increase to 3.0 jobs/second, swapping rises to approximately 3–4%, queuing rises to approximately 40%, and execution drops to approximately 56%. The dominance of queuing and execution over swapping confirms the paper's claim that the proactive mechanism effectively hides nearly all data transfer latency. The paper explains:

"The reason confirms that the proactive swapping mechanism can overlap most of the swapping time with the execution time of other jobs. As a result, the proactive swapping mechanism nearly does not affect the end-to-end latency."

This is a critical validation: if swapping overhead were significant, the scheduler's latency improvements would be partially offset by data transfer stalls, but Figure 15b shows this is not the case.
Fixed Priority and Naive MLFQ under varying workload characteristics (Figure 14, discussed above). This experiment serves double duty as both scheduler ablation and robustness check across workload skew. The consistent advantage of Skip-Join MLFQ across input-to-output length ratios from 0.25 to 256 demonstrates that the design is not tuned to a specific workload characteristic and generalizes across the spectrum from output-length-dominated to input-length-dominated regimes.

Critical Assessment

The experiments in this paper primarily demonstrate that FastServe's preemptive scheduling with proactive memory management substantially improves throughput at a given latency SLO compared to FCFS-based serving systems, with the margin of improvement depending on workload skew, model size, and the SLO threshold. The experiments are comprehensive within their systems-evaluation framing—multiple model scales, two real-world datasets, comparison against production-grade baselines, and ablation of the key design components. However, there are several dimensions where the experimental evidence is narrower than the paper's framing suggests, or where additional experiments would have strengthened the claims.

The 31.4× and 17.9× numbers. These headline figures appear in the abstract and Section 1 as the maximum throughput improvements over vLLM under average and tail latency SLOs, respectively. However, the figures represent the maximum ratio across all evaluated configurations (models, datasets, arrival rates) rather than the typical improvement. Visual inspection of Figure 11 suggests that under the SLO threshold (0.3 s/token), the throughput advantage of FastServe over vLLM is more typically in the 1.5× to 4× range across configurations. The 31.4× figure appears to come from the Alpaca dataset on OPT-175B (Figure 11c, second row), where vLLM's measured throughput appears anomalously low relative to its performance on other configurations—vLLM's curve in this subfigure sits very close to the y-axis, suggesting either that vLLM struggles specifically with Alpaca + OPT-175B (possibly due to memory management differences since vLLM uses only tensor parallelism for OPT-175B while FastServe uses both tensor and pipeline parallelism, making this an "apples to partial oranges" comparison) or that a measurement artifact is amplifying the ratio. The paper is transparent about the parallelism configuration difference (Table 2: "vLLM only uses tensor parallelism to serve OPT-175B, because it does not support pipeline parallelism"), and this is a legitimate feature advantage of FastServe, but it means the 31.4× figure conflates the scheduling policy improvement with the parallelism strategy improvement. A fairer comparison would either add pipeline parallelism support to vLLM (difficult because it is not implemented) or use a configuration where both systems use the same parallelism strategy. The 17.9× tail latency improvement (Figure 12) is similarly the maximum observed ratio.

The FastServe-FCFS baseline. This baseline is crucial for isolating the contribution of the skip-join MLFQ scheduler and proactive memory management from implementation efficiency. However, the paper does not provide a detailed breakdown of why FastServe-FCFS outperforms vLLM—the stated reasons are "more efficient C++ implementation and fuses more operations into fewer GPU kernels" (Section 6.2), but no profiling data or kernel-level comparison is provided. This is acceptable for a systems paper (efficient implementation is a legitimate contribution), but it means readers cannot assess how much of the overall improvement comes from better engineering versus better scheduling. The contribution of the scheduling policy specifically is the gap between FastServe and FastServe-FCFS, which is typically 1.3–4× depending on configuration (e.g., 2–4× on ShareGPT OPT-13B, ~1.6–2× on Alpaca, ~1.5× for P95 latency on OPT-175B). These are significant improvements but substantially smaller than the headline 31.4× figure.

The difficulty estimation cost analog: the job profiler. A subtle issue: the skip-join MLFQ depends on accurate profiling of iteration times for varying input lengths (Section 4.1). The paper does not evaluate the accuracy or robustness of this profiling. If the profiled initialization time for a given input length is off by, say, 20%, the skip-join rule might place the job in a queue whose quantum is too small, causing the initialization-phase preemption problem that the design was intended to avoid. The paper implicitly assumes that profiling is accurate, which is reasonable for a fixed hardware configuration, but it does not test sensitivity to profiling errors. This is a mild concern—profiling DNN inference time on a fixed GPU is typically very stable—but it is an unevaluated dependency of the scheduling policy.

Single GPU architecture, single interconnect. All experiments use NVIDIA A100 GPUs with PCIe 4.0×16 for GPU-to-host communication. The proactive swapping mechanism's effectiveness depends on the ratio of PCIe bandwidth to GPU compute throughput: if the PCIe link is significantly slower relative to the GPU, swapping overhead grows and the proactive overlap becomes less effective. The paper's claim that swapping is less than 5% of latency (Figure 15b) is demonstrated only for this specific hardware configuration. On older GPUs with slower PCIe (e.g., PCIe 3.0) or on GPUs with different memory bandwidth characteristics, the swapping overhead might be larger and the proactive advantage correspondingly smaller. This is a standard limitation of systems evaluations (results are hardware-specific), but the paper does not discuss this sensitivity.

Workload generation assumptions. The Poisson arrival process used to generate request inter-arrival times is a standard modeling choice in systems evaluation (used by vLLM [11], Orca [10], and many other serving papers), but real-world LLM serving workloads may exhibit burstier arrival patterns (e.g., correlated arrivals during peak usage hours, flash crowds). The paper acknowledges burstiness in the context of KV cache management (Section 4.2, reserved idle slots for burst arrivals) but does not evaluate FastServe under bursty workload patterns. The Poisson assumption likely makes the evaluation somewhat optimistic—bursty arrivals would stress the proactive swapping mechanism's ability to prefetch KV caches before jobs are scheduled, potentially increasing swapping-visible latency.

Limited statistical reporting. The paper reports latency-throughput curves (Figures 11, 12) without error bars or confidence intervals, and without specifying whether results are averages over multiple runs with different arrival-process random seeds. Given that the Poisson arrival process is stochastic, different random seeds could produce modestly different latency measurements, particularly at higher arrival rates where system behavior becomes sensitive to the precise inter-arrival timing. This is standard practice in the systems conferences where the paper is published, but it means the reported improvements should be interpreted as representative rather than precisely measured to within narrow confidence bounds. The ablation experiment in Figure 14 reports normalized latency without specifying the normalization baseline numerically, making it difficult to assess absolute performance differences.

Missing experiments that would have strengthened the paper. Several experiments are notably absent:

No comparison against Orca [10] directly. Orca introduced iteration-level scheduling, a technique that FastServe incorporates. While Orca and vLLM share the same fundamental limitation (FCFS scheduling, no preemption), a direct comparison would confirm that FastServe's advantage over vLLM is not partially attributable to vLLM-specific implementation choices. The paper uses vLLM as the primary comparison point because it is the state-of-the-art, which is reasonable, but a head-to-head with Orca would provide a cleaner ablation of the scheduling policy difference (both use iteration-level scheduling; only FastServe adds preemption).
No evaluation on varied hardware. All experiments use A100 GPUs. A comparison across GPU generations (e.g., V100 with PCIe 3.0) would test the robustness of the proactive swapping mechanism under different bandwidth regimes.
No sensitivity analysis on MLFQ parameters. The paper specifies that α = 300 ms and that quanta follow a doubling pattern, but it does not evaluate how performance varies with different α values or different quantum spacing strategies. Figure 13 evaluates different SLO targets (5×, 10×, 20×), which indirectly relates to α tuning, but a direct sweep of α would more clearly show the starvation prevention mechanism's impact on the latency-throughput tradeoff.
No failure case analysis for the proactive swapping mechanism. The paper demonstrates that swapping overhead is <5% under the tested workloads, but does not show what happens when the proactive mechanism fails—e.g., when the ENST prediction is wrong and a job is scheduled with its KV cache still in host memory, incurring reactive latency. A workload with rapidly changing job size distributions or adversarial arrival patterns could expose such failures.

Overall assessment. The experiments robustly demonstrate that preemptive scheduling at token granularity, combined with proactive KV cache offloading, enables significantly higher throughput at a given latency SLO than FCFS-based approaches, particularly for workloads with heterogeneous job sizes. The primary mechanism (eliminating head-of-line blocking) is clearly validated, and the ablation experiments (scheduler comparison in Figure 14, memory management comparison in Figure 15a) isolate the contributions of the key components. The headline 31.4× and 17.9× figures should be understood as maxima across configurations rather than typical improvements, with the more representative range being ~1.5–4× for the full system over vLLM and ~1.3–4× for the scheduling policy specifically over an equally-optimized FCFS baseline. The experimental design is appropriate for a systems paper targeting SOSP/OSDI-level venues, with the caveats about hardware specificity, workload modeling assumptions, and statistical reporting being standard in this genre.

6. Limitations and Trade-offs

6.1 The Job Profiler Assumes Perfectly Predictable Iteration Times—But No Sensitivity Analysis Is Provided

The assumption or constraint. The entire skip-join MLFQ scheduler depends on the Job Profiler to provide accurate initialization-phase execution times ( $t_{init}$ ) for each arriving job's input length. The paper argues this is reasonable because "for each iteration, the execution is similar to the traditional one-shot DNN inference, whose execution time is highly predictable" (Section 4.1). However, DNN inference time is not perfectly deterministic in practice—it varies with GPU temperature, concurrent kernel launches, memory controller contention from other processes, and NUMA effects in multi-GPU systems. More importantly, the first iteration's cost depends not only on input length but also on the batch composition at the time of execution. When a job runs its first iteration alongside other jobs in a batch, the total computation and memory footprint determines execution time, and this varies with the other jobs' sequence lengths and the total batch size. The profiler captures single-job or fixed-batch timing, but the actual batch composition is dynamic and determined at scheduling time. The paper does not evaluate the accuracy of the profiler, nor does it test sensitivity to profiling errors.

The consequence. If the profiled $t_{init}$ underestimates the actual first-iteration time for a given input length and batch composition, the skip-join rule will place the job in a queue whose quantum is too small to accommodate a full first iteration. The scheduler then faces exactly the dilemma the design was intended to avoid: preempt mid-initialization (wasting the partially-computed first iteration, since intermediate activations are discarded) or let the job exceed its quantum (violating MLFQ semantics and reintroducing head-of-line blocking). Conversely, an overestimated $t_{init}$ places the job in a lower-priority queue than necessary, denying it the fast-track service it could have received if the initialization were actually shorter than profiled. The system's correctness—not just its performance—depends on the profiling being accurate to within the quantum granularity. A profiling error of even a few milliseconds could shift a job across a queue boundary (recall that quanta follow a doubling pattern, so adjacent queues have substantially different quantum sizes).

What evidence exists in the paper. None. The paper provides no measurement of profiling accuracy, no comparison of profiled versus actual iteration times, and no experiment that varies input lengths to test whether the skip-join rule consistently places jobs in the correct queue. Figure 5 shows profiled iteration times for OPT-2.7B as a motivating example, but this is a clean offline measurement on a single GPU with no concurrent workload—it does not reflect the online serving environment where multiple batches with varying compositions execute concurrently. The system's end-to-end evaluation (Figures 11–13) measures aggregate latency and throughput, which would mask occasional profiling errors if they are infrequent. But a workload dominated by a particular input length range could expose systematic profiling bias.

Mitigation status. The paper does not address profiling accuracy. It treats the profiler as a solved infrastructure component and does not discuss error tolerance, re-profiling strategies for different hardware, or safety mechanisms (e.g., what happens when a job exceeds its quantum mid-initialization—does the scheduler detect this and compensate?). Unlike the skip-join rule and the KV cache manager, which are presented with detailed design rationale, the profiler is described in a single paragraph (Section 4.1) with no evaluation or error analysis. A practitioner deploying FastServe would need to independently verify that their profiled iteration times match online behavior under load, and would need to decide how to handle the edge case where they do not.

6.2 The Headline 31.4× and 17.9× Figures Conflate Scheduling Policy Improvements with Parallelism Strategy Differences

The assumption or constraint. The paper's most prominent quantitative claims—"FastServe improves the throughput by up to 31.4× and 17.9× under the same average and tail latency requirements, respectively" (Abstract, Section 1)—compare FastServe against vLLM. However, the experimental configuration for the largest model (OPT-175B) introduces a parallelism strategy discrepancy that is orthogonal to the scheduling policy contribution. Table 2 explicitly notes: "vLLM only uses tensor parallelism to serve OPT-175B, because it does not support pipeline parallelism." FastServe uses both tensor parallelism and pipeline parallelism for OPT-175B. Pipeline parallelism allows multiple batches to be in-flight simultaneously across different pipeline stages, which can increase throughput independently of any scheduling policy improvement—even under FCFS, pipeline parallelism provides better GPU utilization than tensor parallelism alone by reducing pipeline bubbles. The paper acknowledges this difference in the baseline description but does not adjust the headline numbers accordingly.

The consequence. The 31.4× maximum improvement over vLLM (measured on Alpaca + OPT-175B, Figure 11c, second row) and the 17.9× tail latency improvement (Figure 12c) partially reflect the throughput gain from pipeline parallelism, not just the gain from skip-join MLFQ scheduling and proactive KV cache management. A reader glancing at the abstract gets the impression that the scheduling policy alone provides a ~30× improvement, when in reality the scheduling component's contribution—isolated via the FastServe-FCFS baseline (which uses the same parallelism strategy as FastServe)—is typically ~1.3–4×. The paper itself provides the numbers to decompose this: FastServe-FCFS (FCFS scheduling on the same parallelized engine) already outperforms vLLM significantly on OPT-175B (Figure 11c), and the incremental gain of FastServe over FastServe-FCFS is the scheduling contribution. For OPT-175B ShareGPT, FastServe-FCFS achieves approximately 4.5 jobs/second at the SLO versus vLLM's 2.5–3.0 jobs/second—the parallelism strategy accounts for roughly 1.5–1.8× of the improvement. The additional ~1.3–1.4× from FastServe on top of FastServe-FCFS (reaching ~6.0–6.5 jobs/second) is the scheduling policy gain.

What evidence exists in the paper. The paper's own decomposition via the FastServe-FCFS baseline makes this conflation transparent to careful readers who trace the numbers through Figures 11–13, but the abstract and introduction present the aggregate number without the decomposition. The Alpaca OPT-175B result (Figure 11c, second row) shows an unusually large gap between vLLM and FastServe-FCFS—much larger than the gap for smaller models—which suggests that vLLM's lack of pipeline parallelism is especially penalizing for the largest model, and that the 31.4× figure is largely a parallelism advantage, not a scheduling advantage. The paper states the parallelism discrepancy in Section 6.1 ("vLLM only uses tensor parallelism to serve OPT-175B, because it does not support pipeline parallelism") and mentions it as a baseline limitation, but does not explicitly caution readers that the headline numbers are inflated by this configuration difference.

Mitigation status. Not addressed. The paper's abstract and conclusion report the maximum observed ratios without qualification. A more conservative reporting practice would be to present the scheduling contribution (FastServe vs. FastServe-FCFS) as the primary result and the aggregate improvement (FastServe vs. vLLM) as an upper bound that includes parallelism benefits. Alternatively, the paper could have evaluated vLLM with a comparable parallelism configuration—for instance, by augmenting vLLM with a pipeline-parallel execution layer, or by comparing both systems under tensor-parallelism-only for the largest model (even if this limits performance, it would provide a clean apples-to-apples comparison). The current presentation treats pipeline parallelism as a feature of FastServe (which it is, and it is a legitimate contribution), but does not decompose the headline number into its feature components, potentially misleading readers who do not examine the baseline configuration carefully.

6.3 The Proactive Swapping Mechanism's Effectiveness Is Demonstrated Only on a Single GPU-to-Host Interconnect (PCIe 4.0×16) and a Specific Model Scale

The assumption or constraint. The proactive KV cache swapping design depends on the PCIe bandwidth between GPU and host memory being sufficient to overlap data transfer with computation, so that swapping latency is hidden. The paper quantifies this for its specific hardware: "When deploying OPT 175B on 16 NVIDIA A100 GPUs, the key-value tensors of a job can occupy 2.3 GB memory. The token generation time in the decoding phase is about 60 ms, while the time to swap the key-value tensors between host memory and GPU memory with PCIe 4.0×16 full bandwidth is about 36 ms" (Section 4.2). The proactive mechanism works because 36 ms (swap time) < 60 ms (execution time), allowing the swap to complete within the execution window of the preceding batch. The evaluation in Figure 15 (proactive vs. reactive comparison, latency breakdown) uses OPT-13B on a single A100 GPU—the paper does not perform the equivalent measurement for larger models or different hardware configurations.

The consequence. The viability of the proactive approach depends on the ratio of swap time to execution time. If this ratio exceeds 1.0, the swap cannot be fully hidden within a single batch's execution window, and overlapping becomes partial at best. Several realistic deployment scenarios would increase this ratio:

Older GPU hardware or slower interconnects. On PCIe 3.0 (roughly half the bandwidth of PCIe 4.0), the swap time for a 2.3 GB KV cache doubles to approximately 72 ms, exceeding the 60 ms decoding iteration time. The swap can no longer be fully overlapped, and some fraction of the transfer latency will appear on the critical path.
Larger KV caches due to longer sequences. As sequence length grows (e.g., for models supporting 128K token context windows like Gemini 1.5), the KV cache per job grows proportionally. A 4× larger KV cache has 4× longer swap time, potentially exceeding the per-iteration execution time even on PCIe 4.0.
Faster GPUs relative to interconnect bandwidth. The A100 used in the paper represents a specific point in the GPU-to-interconnect bandwidth ratio. A GPU with faster computation but the same PCIe bandwidth (e.g., future GPU generations) would have shorter per-iteration execution time without a corresponding reduction in swap time, worsening the ratio.
Multi-GPU setups where PCIe bandwidth is shared. In a multi-GPU server, multiple GPUs may share PCIe lanes to the host. If several GPUs attempt proactive swapping simultaneously, the effective per-GPU bandwidth drops, increasing swap time.

In any of these scenarios, the swap time fraction of end-to-end latency would grow beyond the <5% shown in Figure 15b, and the advantage of proactive over reactive swapping would shrink. The paper's claim that "the proactive swapping mechanism nearly does not affect the end-to-end latency" (Section 6.3, discussion of Figure 15b) is demonstrated only for the specific (hardware, model, workload) combination tested, and the conditions under which it generalizes are not characterized.

What evidence exists in the paper. Figure 15b shows swapping overhead < 5% for OPT-13B on a single A100. The paper provides the arithmetic for OPT-175B's swap-time-to-execution-time ratio (36 ms vs. 60 ms) as motivation, but does not experimentally validate the swapping overhead for the large-model distributed case. The OPT-175B experiments (Figure 11c, Figure 12c) measure end-to-end latency and throughput, which would aggregate swapping overhead into the total—but the paper does not break down latency for OPT-175B as it does for OPT-13B in Figure 15b, so readers cannot assess whether the proactive mechanism maintains the same <5% overhead at scale. The burst-handling discussion (Section 4.2) implicitly acknowledges that the proactive mechanism can be stressed by workload patterns, but the evaluation uses Poisson arrivals, which are smoother than real-world bursty traffic.

Mitigation status. The paper acknowledges the fundamental dependency on the swap-to-execution time ratio in the motivating analysis (Section 4.2: "the overhead of swapping is not negligible compared to the token generation time") and uses it to justify the proactive rather than reactive design. But it does not characterize the boundary conditions under which proactive swapping succeeds or fails, and it does not discuss hardware sensitivity. A practitioner deploying FastServe on older hardware or with very-long-context models would have no guidance from the paper on whether the proactive mechanism remains effective. The paper's response to the burst-handling challenge (reserved idle KV cache slots) is a partial mitigation for one failure mode (arrival bursts) but does not address the fundamental bandwidth-ratio sensitivity.

6.4 The ENST Metric Uses Crude Approximations That May Cause Systematic KV Cache Misplacement Under Certain Workload Distributions

The assumption or constraint. The Estimated Next Scheduled Time (ENST) metric that guides proactive KV cache swapping decisions relies on two simplifying assumptions that may not hold in practice. First, when estimating $T_{execute}(i)$ —the time until all higher-priority jobs ahead of job $i$ have been executed—the paper assumes "those jobs do not finish earlier before being demoted to the priority queue of job $i$ " (Section 4.2). This is a worst-case assumption: every higher-priority job is assumed to consume its full quantum in every intermediate queue as it is progressively demoted. In reality, many higher-priority jobs will finish (i.e., generate their end-of-sequence token) before being demoted all the way to job $i$ 's level, which means the actual $T_{execute}(i)$ may be substantially shorter than the ENST estimate. Second, the division by the maximum batch size $B$ to compute $T_{execute}(i)$ assumes perfect batching—that all higher-priority jobs can be packed into full batches and executed simultaneously. In practice, batching efficiency depends on memory constraints, job arrival timing, and sequence length heterogeneity within the batch.

The consequence. The ENST metric is used to rank jobs for swapping decisions: jobs with the largest ENST are swapped out of GPU memory first (they are predicted to be inactive longest), and jobs with the smallest ENST are swapped in first (they are predicted to be scheduled soonest). If ENST systematically overestimates the actual time until next schedule (due to the pessimistic "no early finish" assumption), it will:

Swap out jobs too aggressively. A job whose ENST is estimated as large may actually be scheduled much sooner because the higher-priority jobs ahead of it finish quickly. Its KV cache gets moved to host memory unnecessarily, and when it is scheduled earlier than predicted, the system must perform a reactive swap (or the job stalls waiting for its KV cache to be uploaded), incurring the very latency the proactive mechanism was designed to avoid.
Swap in unnecessary jobs. A job predicted to be scheduled soon (low ENST) may in fact be far from execution because some higher-priority jobs that were assumed to finish early actually run long. Its KV cache occupies precious GPU memory while inactive, potentially forcing out the caches of jobs that are genuinely about to be scheduled.

These mispredictions erode the advantage of proactive over reactive swapping. The paper's experimental evidence (Figure 15) shows that proactive outperforms reactive for the tested workloads, indicating that ENST-based predictions are sufficiently accurate on average. However, workload distributions that deviate from the tested ShareGPT/Alpaca patterns could trigger systematic ENST errors. For example, a workload dominated by short-output, long-input jobs (where initialization time is large but the job finishes after only a few decoding iterations) would cause many jobs to finish before being demoted, violating the "no early finish" assumption. Conversely, a workload with uniformly long outputs (where every job consumes its full quantum at every level) would make the assumption accurate, and ENST predictions would be reliable.

What evidence exists in the paper. None directly. The paper does not evaluate ENST prediction accuracy—it does not compare predicted versus actual next-scheduled times, does not measure the frequency of ENST mispredictions causing reactive swaps, and does not test workload distributions that stress the ENST assumptions. The comparison of proactive versus reactive swapping (Figure 15a) provides indirect evidence that ENST works for ShareGPT, but this is only one workload distribution. The paper does not vary workload characteristics (e.g., the ratio of short-output to long-output jobs, the skew of the output length distribution) in its KV cache management experiments to test robustness.

Mitigation status. Not addressed. The paper does not discuss the accuracy of the ENST approximation or propose mechanisms to correct for prediction errors (e.g., adjusting ENST estimates based on observed job completion rates, or maintaining a confidence interval around ENST predictions that feeds into a risk-aware swapping policy). The starvation prevention mechanism ( $T_{promote}(i)$ term in ENST) provides a guaranteed upper bound on waiting time, which guards against the worst-case scenario where a job is never predicted to run soon, but it does not address the accuracy of the priority-driven component of ENST. A practitioner would need to validate that ENST predictions remain accurate for their specific workload characteristics, or risk performance degradation from prediction-driven thrashing.

6.5 All Experiments Use a Single Model Family (OPT) on a Single Class of Tasks (Conversational Text Generation), Limiting Evidence for Generalization

The assumption or constraint. The entire evaluation—all latency-throughput curves, all scheduler ablations, all memory management comparisons—uses the OPT model family (OPT-13B, OPT-66B, OPT-175B) and two datasets (ShareGPT, Alpaca) that represent conversational text generation tasks. The paper states that OPT is "widely used in both academia and industry" (Section 6.1) and that OPT-175B is "similar to the largest GPT-3 model" (Section 1). However, the LLM landscape is diverse: models differ in architecture (encoder-decoder vs. decoder-only, attention mechanism variants like Multi-Query Attention [28] and Group-Query Attention [29], which the paper itself cites), training methodology, tokenizer design, and inference-time behavior. The OPT family uses a standard decoder-only Transformer architecture with multi-head attention—it does not represent architectural variants that are increasingly common in production deployments.

The consequence. Several aspects of FastServe's design may behave differently under different model architectures:

The initialization-to-decoding time ratio. Figure 5 shows that for OPT-2.7B, the first iteration is 5–45× more expensive than subsequent iterations, depending on input length. This ratio drives the need for skip-join. Models with different attention mechanisms (e.g., Multi-Query Attention, which shares key-value heads across queries) reduce KV cache size and per-iteration computation, potentially changing the initialization-to-decoding cost ratio. If a model's first iteration is only marginally more expensive than decoding iterations, the skip-join mechanism provides little benefit over classical MLFQ, and the complexity of skip-join may not be justified.
KV cache size per token. The paper's formula for KV cache size ( $4 \times l \times h \times (s + t)$ ) assumes full multi-head attention. Models using Group-Query Attention or Multi-Query Attention have smaller KV caches (fewer distinct key-value heads), which changes the memory pressure calculation and the swap-time-to-execution-time ratio. This affects both the necessity and the effectiveness of proactive KV cache management.
Pipeline parallelism behavior. Models with different layer counts and hidden dimensions (e.g., LLaMA-70B with 80 layers and 8192 hidden dimension vs. OPT-66B with 64 layers and 9216 hidden dimension) have different pipeline stage balancing characteristics. The scheduling extensions for pipeline parallelism (Section 4.3) assume that stages are roughly balanced, but severe imbalance could cause some stages to become bottlenecks, changing the effective MLFQ behavior across the pipeline.
Task-dependent output length distribution. Conversational text generation (ShareGPT, Alpaca) exhibits long-tailed output length distributions, which is the workload skew that creates head-of-line blocking. Other LLM tasks—code generation, summarization, translation, structured data extraction—have different output length characteristics. Summarization, for example, typically produces outputs shorter than inputs, making the initialization phase dominant and reducing the importance of decoding-phase scheduling. Code generation may produce very long outputs with deterministic stopping conditions. A scheduler optimized for conversational workloads may be suboptimal for these other tasks.

What evidence exists in the paper. The paper evaluates only the OPT family on only conversational datasets. The model architecture limitation is partially acknowledged implicitly: the paper cites Multi-Query Attention [28] and Group-Query Attention [29] in Section 2.3 as memory-saving techniques, but does not evaluate FastServe with models that use these techniques. The task diversity limitation is not discussed.

Mitigation status. Not addressed. The paper does not claim generality beyond the evaluated configurations, but it also does not discuss the model- and task-specific dependencies of its design. The inference serving community typically expects evaluation across multiple model families (e.g., LLaMA, Falcon, GPT-NeoX) and task types to establish generality—this paper's single-family evaluation is narrower than comparable systems papers. A practitioner using a non-OPT model or serving a non-conversational task would need to independently validate that the skip-join MLFQ and proactive KV cache management are effective for their configuration.

6.6 The System Does Not Account for Latency (Wall-Clock Time) When Allocating the "Compute Budget" Across Sequential and Parallel Job Execution

The assumption or constraint. FastServe's scheduling policy optimizes for throughput at a given average or tail latency SLO, measured in seconds per token. However, the scheduler's decisions about which jobs to execute in each batch are based on priority queue ordering, not on the absolute wall-clock deadlines of individual requests. The starvation prevention mechanism (threshold $\alpha$ = 300 ms by default) imposes a soft deadline—a job waiting longer than $\alpha$ is promoted to $Q_1$ —but this is a single threshold for all jobs, not a per-job latency budget. In a serving system with heterogeneous latency requirements (e.g., some users have stricter SLOs than others, or some requests are part of a latency-sensitive interactive session while others are batch submissions), a uniform $\alpha$ provides no differentiation.

More critically, the entire evaluation is structured around average and P95 latency under steady-state Poisson arrivals. Real-world serving systems face transient overload (arrival rate spikes that temporarily exceed system capacity), during which all jobs experience inflated latency. FastServe's MLFQ-based scheduler will continue to prioritize short jobs during overload, providing differentiated service—short jobs will still complete quickly while long jobs absorb the excess queuing delay. But the starvation prevention threshold $\alpha$ may become the dominant scheduling mechanism during sustained overload: all jobs eventually hit the $\alpha$ threshold, get promoted to $Q_1$ , execute one token, get demoted again, wait $\alpha$ seconds, get promoted again, and so on. In this regime, the scheduler degenerates to a form of round-robin with quantum $\alpha$ , and the throughput-optimal short-job-first property of MLFQ is lost. The paper does not evaluate FastServe under overload conditions, so the behavior and performance of the system when pushed beyond its capacity is unknown.

The consequence. Two practical deployment concerns arise:

No per-request latency differentiation. If a serving system must provide different latency guarantees to different users (e.g., a premium tier with 100 ms SLO vs. a free tier with 1 second SLO), FastServe's uniform $\alpha$ cannot enforce this differentiation. All jobs receive the same starvation prevention guarantee. An operator could theoretically deploy multiple FastServe instances with different $\alpha$ settings, but the scheduler has no notion of per-job SLO classes.
Unknown overload behavior. Under sustained overload, the degradation curve (how quickly latency increases as arrival rate exceeds capacity) is not characterized. The Poisson-arrival experiments sweep arrival rates up to the point where latency exceeds the SLO and report throughput at the SLO boundary, but they do not show behavior beyond this point. In a production deployment, overload is inevitable (traffic spikes, partial hardware failures), and operators need to know whether the system degrades gracefully (throughput remains near capacity, latency grows linearly with queue depth) or catastrophically (thrashing, priority inversion, or memory exhaustion causing failures). The interaction between MLFQ scheduling and the proactive KV cache manager under overload could produce complex dynamics: when all queues are full and arrival rate exceeds departure rate, the cache manager's ENST predictions may become systematically wrong (because the assumption that higher-priority jobs eventually finish breaks down when the system is perpetually backlogged), causing reactive swapping that further reduces throughput—a positive feedback loop toward collapse.

What evidence exists in the paper. The paper evaluates the system at arrival rates up to and slightly beyond the SLO boundary (Figures 11–13). The curves in Figure 11 show latency increasing sharply as arrival rate approaches the saturation point, but the experiments stop shortly after crossing the SLO. The paper does not report throughput under overload, maximum sustainable throughput regardless of latency, or latency behavior at 2× or 3× the SLO. The goodput experiment (Figure 13) evaluates SLO attainment under increasing load but does not characterize the nature of SLO violations (whether they are mild overruns or multi-second delays). The starvation prevention mechanism is evaluated indirectly through P95 latency (Figure 12) and SLO attainment (Figure 13), but only under normal (non-overload) conditions.

Mitigation status. Not addressed. The paper does not discuss overload behavior, per-request SLO differentiation, or admission control mechanisms that would prevent the system from accepting more work than it can process within latency targets. These are standard concerns in production serving systems (e.g., load shedding, request prioritization by deadline, adaptive admission control), and their absence is a practical gap for anyone deploying FastServe in a production environment with variable load. The paper's focus is on improving throughput under a latency SLO during normal operation, which it demonstrates successfully, but the operational envelope—what happens when that SLO cannot be met—is left uncharacterized.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper performs a diagnostic reframing rather than a paradigm shift—it does not introduce a new model architecture or a fundamentally new class of scheduling algorithms, but it changes what problem the field should be optimizing for. The core insight, crystallized in Figure 1, is that queuing delay, not execution time, dominates LLM inference latency under real-world workload distributions. Prior work (Orca, vLLM, FasterTransformer) focused overwhelmingly on making token generation faster—kernel fusion, memory compression, iteration-level batching—because the implicit assumption was that execution was the bottleneck. FastServe demonstrates that for workloads with heterogeneous job sizes (ShareGPT, Alpaca), queuing delay accounts for 87.6–98.0% of end-to-end latency, and execution optimizations can only address the remaining sliver. This reorients the research agenda: LLM serving systems should be designed as preemptive schedulers first, execution engines second.

The paper also reconciles the apparent contradiction between two observations in the literature. On one hand, iteration-level scheduling (Orca) had shown that admitting new jobs between iterations improves throughput over job-level scheduling—but it still used FCFS, and the improvement was attributed to better GPU utilization. On the other hand, preemptive scheduling (MLFQ, SRPT) was known to minimize average latency in information-agnostic settings, but it was assumed to be inapplicable to LLM inference because job sizes are unknown and preemption seemed too expensive. FastServe shows that these two observations are not contradictory—they are incomplete descriptions of the same problem. Iteration-level scheduling provides the mechanism for fine-grained preemption (you can swap jobs between iterations), but FCFS provides no policy for deciding when to preempt. Preemptive scheduling provides the policy, but only if the system can handle the memory overhead and the initialization-phase cost structure. The paper unifies these threads by showing that iteration-level scheduling is the enabler, MLFQ is the policy, skip-join adapts the policy to the LLM-specific cost structure, and proactive KV cache management makes the policy practical under GPU memory constraints. Each piece is necessary; none is sufficient alone.

The paper's semi-information-agnostic characterization also resolves a tension between two strawman scheduling strategies evaluated in Section 4.1. Fixed-priority scheduling (using only input length) works well when the initialization phase dominates (long inputs, short outputs) but fails when the decoding phase dominates (short inputs, long outputs). Classical MLFQ works well under homogeneous per-iteration costs but fails when the first iteration is orders of magnitude more expensive than subsequent ones. The paper shows that neither extreme is correct for real LLM workloads, which exhibit both long-tailed input lengths and long-tailed output lengths. Skip-join MLFQ synthesizes both sources of information: input length determines initial placement (exploiting the known first-iteration cost), while consumed decoding iterations determine demotion (letting output length reveal itself through the feedback mechanism). This resolves the contradiction by showing that the two strawman approaches are not competing alternatives but partial solutions that must be combined.

The finding that proactive KV cache management reduces swapping overhead to under 5% of end-to-end latency (Figure 15b) changes the calculus for GPU memory management in LLM serving. Prior work treated GPU memory as a hard capacity constraint—you fit as many KV caches as you can, and when memory is full, you either defer new jobs (vLLM's approach, which reintroduces head-of-line blocking) or you accept that preemption is impractical. FastServe demonstrates that GPU memory can be treated as a cache backed by host memory, with a well-designed prefetching policy (ENST-based ranking) that makes the cache nearly transparent. This opens a new design space: future systems can provision for the active working set of KV caches (those currently being executed or scheduled soon) rather than the total KV cache footprint, because inactive caches can reside in host memory at negligible latency cost. The effective KV cache capacity becomes limited by host memory (hundreds of GB to TB), not GPU memory (tens of GB), fundamentally expanding the feasible scale of concurrent job processing.

A subtler implication concerns the relationship between model architecture and serving system design. The paper identifies the initialization-to-decoding cost ratio (Figure 5) as the key parameter that determines whether skip-join is beneficial. This ratio varies with model architecture—it depends on the attention mechanism (full multi-head, multi-query, grouped-query), the layer count, and the hidden dimension. The paper's analysis implies that model architects and serving system designers should co-design around this ratio: a model with lower initialization-to-decoding cost asymmetry might not need skip-join (classical MLFQ would suffice), while a model with extreme asymmetry (very deep, very wide, processing very long inputs) benefits more from aggressive skip-join. This is a concrete example of how inference-time characteristics should influence model design, not just the other way around—a reversal of the typical direction of influence.

The work also makes certain research directions less attractive. The paper's latency breakdown (Figure 15b) shows that execution time is a minority contributor to end-to-end latency under high load, and that further execution optimizations (faster kernels, better attention implementations) yield diminishing returns because they address a component that is already small. This suggests that the marginal value of execution-level optimizations is declining for interactive serving, and that scheduling and memory management are the higher-leverage investments. Similarly, the paper's analysis of why naive MLFQ and fixed-priority both fail (Section 4.1) suggests that simple scheduling heuristics—"always prioritize short inputs" or "use standard MLFQ with a longer first quantum"—are insufficient because they ignore one dimension of the cost structure. Future work that proposes new scheduling heuristics should be evaluated against the skip-join baseline and should demonstrate robustness to variations in both input-length and output-length distributions. A heuristic that excels on one distribution but degrades on the other is not a genuine advance.

Follow-Up Research This Work Enables

Characterizing the ENST prediction accuracy and designing robust alternatives under adversarial workload patterns. The ENST metric (Section 4.2) makes two strong assumptions: higher-priority jobs do not finish early (they consume full quanta at every demotion level), and perfect batching efficiency (all higher-priority jobs can be packed into batches of size $B$ ). The paper's ablation (Figure 15a) shows that the metric works for ShareGPT workloads, but no experiment characterizes when it fails. A follow-up study would systematically vary the workload completion-time distribution—adjusting the fraction of jobs that finish early (before being demoted to the lowest-priority queue of interest), the correlation between input length and output length, and the arrival burstiness—while measuring (a) the distribution of ENST prediction errors (predicted vs. actual next-scheduled time), (b) the frequency of reactive swaps caused by ENST mispredictions (a job scheduled before its KV cache finishes uploading), and (c) the resulting end-to-end latency penalty. The goal is to identify the workload characteristics that bound ENST's reliability and, if a failure regime exists, to design an adaptive ENST that adjusts its "no early finish" assumption based on observed job completion rates in each priority queue. The paper's own starvation prevention threshold $\alpha$ provides a natural upper bound for correction—if ENST is wildly overestimating, the $T_{promote}(i)$ term will dominate the $\min$ , providing a safety net. Quantifying how often this safety net activates would reveal whether ENST's approximations are problematic in practice.

Combining skip-join MLFQ with output-length prediction models. The paper explicitly identifies the unknown output length as the key information gap that forces the scheduler to use feedback-based MLFQ rather than optimal SRPT. Since the paper's publication, the field has seen progress in predicting LLM output length from the prompt and early-generation tokens (e.g., using a lightweight classifier head on the LLM's hidden states). A natural extension would test whether an imperfect output-length predictor can improve on skip-join MLFQ. The experiment: train or obtain a predictor that takes the prompt text and produces a distribution over output length (or a binary short/long classification), then modify the skip-join rule to incorporate this prediction alongside the input-length-based initialization time. For example, the initial queue placement could be $\arg\min_i$ subject to $q_i \geq t_{init} + \hat{t}_{decode} \cdot \widehat{E}[output\_length]$ , using the predicted output length to adjust the initial priority upward for predicted-short jobs and downward for predicted-long jobs. The key metric: does the predictor-augmented scheduler outperform pure skip-join MLFQ on average latency, and does it do so robustly when the predictor makes errors? The semi-information-agnostic framework (Section 4.1) provides the theoretical grounding: the predictor adds partial information to the decoding-phase dimension, and the MLFQ feedback mechanism serves as a safety net when predictions are wrong. A negative result—showing that even a moderately accurate predictor provides no benefit over MLFQ's self-revealing mechanism—would be valuable in its own right, as it would demonstrate that the information-agnostic approach is not fragile to missing information.

Evaluating FastServe on model architectures with substantially different initialization-to-decoding cost ratios. The paper's evaluation uses the OPT family, which uses standard multi-head attention. The skip-join mechanism's value proposition depends critically on the ratio of first-iteration cost to subsequent-iteration cost (Figure 5). Models using Multi-Query Attention (MQA, Shazeer 2019 [28]) or Grouped-Query Attention (GQA, Ainslie et al. 2023 [29]) share key-value heads across queries, reducing the KV cache size and the per-token attention computation, which changes both the memory pressure and the initialization-to-decoding cost ratio. A direct replication of the key experiments (Figures 11, 14, 15a) on LLaMA-2 (GQA) or Falcon (MQA) at comparable parameter counts would test whether the skip-join advantage is architecture-specific. The hypothesis: MQA/GQA models have smaller KV caches (reducing the memory pressure that makes proactive swapping necessary) and more uniform per-iteration costs (reducing the benefit of skip-join over classical MLFQ). If the advantage shrinks substantially, it would imply that FastServe's design is optimized for the specific cost structure of full multi-head attention, and that the LLM serving community needs a more general scheduling framework that adapts to the model's attention mechanism.

Stress-testing FastServe under bursty arrivals and overload with latency-critical and best-effort job classes. The paper evaluates FastServe under steady-state Poisson arrivals and characterizes throughput at the SLO boundary, but real deployments face arrival bursts (correlated requests during product launches, viral events) and sustained overload (traffic exceeding capacity). A stress-test experiment would generate workload traces with varying burst sizes (e.g., doubling or tripling the baseline arrival rate for short intervals) and sustained overload factors (e.g., 1.2×, 1.5×, 2.0× the saturation throughput) while measuring (a) the latency distribution for short vs. long jobs during bursts, (b) the recovery time after a burst subsides (how quickly the queue drains), (c) the behavior of the proactive KV cache manager during overload (does ENST-based swapping break down when no jobs finish and all queues are backlogged?), and (d) whether a simple admission control policy (e.g., rejecting or deferring jobs with the largest input length when queue depth exceeds a threshold) improves latency for admitted jobs without causing starvation for rejected ones. The paper's reserved idle KV cache slots (Section 4.2) are a partial solution for bursts, but the experiment would quantify how many slots are needed as a function of burst magnitude, and whether the static reservation policy is sufficient or an adaptive policy (dynamically adjusting reservation based on recent arrival rate) is needed. The goal is to produce a characterization of FastServe's operational envelope—under what conditions it degrades gracefully versus catastrophically—which would guide deployment decisions in production environments.

Integrating disaggregated prefill-decoding architectures with skip-join scheduling. Recent work on LLM serving architectures (Splitwise [53], DistServe [41]) proposes disaggregating the initialization phase (prefill) and the decoding phase onto separate GPU pools, with the rationale that these phases have different computational characteristics and resource requirements. FastServe's skip-join MLFQ is designed for a monolithic serving architecture where each GPU handles both phases. However, the skip-join insight—that initialization-phase time should determine initial scheduling priority—is conceptually orthogonal to the monolithic vs. disaggregated choice. A follow-up would port the skip-join MLFQ scheduler to a disaggregated architecture: the prefill pool would use a scheduling policy that prioritizes jobs based on their profiled prefill time (shorter prefill = higher priority), while the decoding pool would use a standard MLFQ or the decoding-phase component of skip-join. The key questions: does disaggregation reduce the need for skip-join (because long-prefill jobs no longer block short-decode jobs, since they run on separate hardware)? Or does skip-join still provide value within each pool (because prefill times vary with input length even within the prefill pool)? The experiment would compare a disaggregated system with FCFS scheduling against one with skip-join scheduling, measuring the throughput-latency tradeoff across a range of workload distributions. This would test whether the paper's scheduling contributions are tied to the monolithic architecture or generalize to the emerging disaggregated paradigm.

Building a closed-loop self-improving scheduler that adjusts quantum sizes and starvation thresholds online based on observed workload. FastServe's MLFQ parameters—the quantum doubling factor (fixed at 2×), the number of queues, and the starvation threshold $\alpha$ (default 300 ms)—are set statically based on profiled iteration times and the SLO. These choices implicitly assume a particular workload distribution. A follow-up would implement an online tuning mechanism that observes the empirical distribution of job completion times (how many tokens jobs actually generate before finishing or being demoted at each queue level) and adjusts quanta and thresholds to optimize a specified objective (e.g., minimize average latency subject to a P95 tail latency constraint). The mechanism would be a feedback controller layered on top of the MLFQ: if jobs in $Q_3$ consistently finish within 30% of $q_3$ , shrink $q_3$ to improve responsiveness; if jobs in $Q_1$ consistently exhaust $q_1$ and are demoted, consider increasing $q_1$ to reduce demotion overhead; if the P95 latency approaches the SLO under normal load, decrease $\alpha$ to provide earlier starvation relief. The experiment would evaluate whether the adaptive scheduler outperforms the static configuration when workload characteristics shift (e.g., from conversational to summarization tasks), and whether the adaptation converges quickly enough to be useful in deployments with diurnal or task-driven workload shifts. This direction is motivated by the paper's own acknowledgment that $\alpha$ is "tuned based on the user-specified SLO" (Section 4.1)—automating that tuning closes the loop between the SLO specification and the scheduler's behavior.

Practical Applications and Downstream Use Cases

Conversational AI serving at scale with heterogeneous request lengths. The most direct application is the one the paper evaluates: serving chatbots and conversational AI systems (ChatGPT, Claude, Gemini) where user requests vary dramatically in the length of both the input prompt (from a one-sentence question to a multi-page document) and the generated response (from a one-word answer to a multi-paragraph explanation). In such deployments, FastServe's skip-join MLFQ scheduler provides ~1.3–4× higher throughput at the same latency SLO compared to an equally-optimized FCFS baseline (the FastServe-FCFS gap in Figures 11–13), and up to 2–18× compared to vLLM depending on model size and workload skew. The practical impact: an organization serving 100,000 requests per hour on OPT-175B-class hardware could either (a) provision 4× fewer GPUs for the same latency target, reducing infrastructure cost by a comparable factor, or (b) maintain the same GPU footprint and absorb 4× traffic growth before latency degrades. The proactive KV cache management is particularly valuable for deployments supporting long context windows (Gemini 1.5 at 1M tokens, Claude-3 at 200K), where per-request KV cache sizes are extreme and the memory management bottleneck is the binding constraint on concurrency.

Cost-efficient batch inference for LLM evaluation and data generation pipelines. Organizations that run offline batch inference—evaluating LLMs on benchmark suites (MATH, HumanEval, MMLU), generating synthetic training data via self-instruct, or scoring candidate outputs for RLHF—typically process thousands of prompts with highly variable output lengths. In batch settings, the latency SLO might be relaxed (minutes rather than seconds are acceptable), but throughput (prompts completed per GPU-hour) directly determines cost. FCFS-based systems like vLLM suffer head-of-line blocking even in batch mode if long-generation prompts are interleaved with short ones, because the processing batch cannot drain until the longest job finishes. FastServe's preemptive scheduling mitigates this: short-generation prompts are not delayed by co-batched long-generation prompts, because the scheduler can preempt the long job and return the short job's result immediately. The efficiency gain translates directly to cost savings: at 4× higher throughput under the same latency SLO, a batch evaluation that would take 10 GPU-hours on vLLM takes ~2.5 GPU-hours on FastServe. For data generation pipelines where prompts are generated programmatically (self-instruct, rejection sampling with iterative refinement), the throughput improvement is particularly relevant because the number of prompts to process is under the developer's control and directly determines the pipeline's turnaround time.

On-device or edge deployment of smaller LLMs with limited memory. The paper demonstrates FastServe on OPT-13B on a single A100 (40 GB), but the memory management design—proactive KV cache offloading to host memory with overlapped transfer—has particular relevance for edge deployments where GPU memory is even more constrained (e.g., NVIDIA Jetson, Apple Silicon with unified memory, or consumer GPUs with 8–16 GB VRAM). In these settings, the KV cache memory constraint binds at much smaller model scales and batch sizes, and the effective capacity expansion provided by host-memory offloading can be the difference between serving one concurrent user and serving several. The paper's result that swapping overhead is under 5% of latency (Figure 15b) is measured on an A100 with PCIe 4.0—on a platform with slower but still dedicated GPU-host bandwidth (e.g., Apple's unified memory architecture has high bandwidth to the Neural Engine), the ratio of swap time to compute time might remain favorable. A practitioner deploying a 7B-parameter model on a Mac Studio for local inference could use FastServe's KV cache manager to support multiple concurrent users or multiple ongoing conversations without running out of unified memory, maintaining interactive latency by swapping inactive conversation state to system memory.

Multi-tenant LLM serving platforms with latency differentiation requirements. Cloud LLM APIs (OpenAI, Anthropic, together.ai) serve multiple customers with potentially different latency expectations—a real-time coding assistant needs sub-200ms response, while a batch summarization job tolerates several seconds. FastServe's starvation prevention mechanism, parameterized by the SLO threshold $\alpha$ (default 300 ms), can be extended to support per-tenant $\alpha$ values: requests from the low-latency coding assistant tier get promoted to $Q_1$ more aggressively (smaller $\alpha$ ), while batch summarization requests are allowed to wait longer (larger $\alpha$ ). This differentiation would operate within the same physical GPU cluster, avoiding the cost of provisioning separate hardware for separate SLO tiers. The key implementation change is associating each job with an SLO class at admission time and replacing the global $\alpha$ with a per-job threshold $\alpha(job)$ in the starvation check (Algorithm 1, line 19). The experiment to validate: run the ShareGPT workload with two classes of jobs (25% strict-SLO, 75% relaxed-SLO) and measure whether the strict-SLO class meets its latency target without substantially degrading throughput for the relaxed-SLO class. The paper's existing SLO evaluation (Figure 13, showing goodput at 5×, 10×, and 20× SLO) provides partial evidence that the system can meet varying SLO targets, but does not test mixed-SLO workloads.