Beyond Binary Priorities: Multi-Tier SLA Scheduling for LLM Serving

Introduction

Production LLM serving must satisfy heterogeneous service-level objectives across a diverse population of users, from latency-critical interactive API calls to background batch jobs. Llumnix (Sun et al., OSDI 2024) introduced a migration-capable, multi-instance scheduler that unifies load balancing, defragmentation, priority isolation, and auto-scaling under a single freeness metric, but its priority model is binary: every request is either “high” or “normal,” controlled by a single fixed headroom value. This abstraction is too coarse for real deployments, where providers commonly differentiate three to five SLA tiers (platinum, gold, silver, standard, free) with distinct latency targets. This project extends Llumnix to $K \geq 2$ priority tiers, assigning each tier its own isolation budget via exponential headroom decay, and asks a concrete design question: what is the right number of priority tiers for a migration-capable LLM serving system, and how should isolation headroom be allocated across them?

Evaluated across three realistic workload distributions in Microsoft Research’s Vidur simulator, the answer is four. Four tiers deliver the best cost-efficiency tradeoff, with end-to-end P99 speedups up to $3.1\times$ and cost-per-latency improvements of 46–68% over an INFaaS+vLLM baseline, all while preserving strong SLO differentiation and sustaining gains all the way to 10 tiers without tail-latency collapse. Beyond five tiers, isolation benefits plateau and overhead from headroom fragmentation begins to dominate.

This was a joint course project at UC Berkeley (EECS), Sep–Dec 2025, with Anders Vestrum and Hanna Rød. We reimplemented the relevant scheduling architecture in Vidur and built INFaaS, vLLM, Orca, and Sarathi-Serve comparison baselines so the multi-tier extension could be evaluated against both global-routing and per-replica schedulers at scale.

Problem Definition

LLM inference has two phases with opposite resource profiles: a compute-bound, bursty prefill that processes all input tokens in parallel, and a memory-bandwidth-bound decode that generates tokens autoregressively. The KV-cache that stores attention state for active requests is the dominant memory consumer, and because output length is unknown a priori, its footprint grows unpredictably throughout a request’s lifetime. Single-instance schedulers (vLLM, Orca, Sarathi-Serve) optimize per-replica throughput but dispatch at the cluster level with one-shot FCFS or round-robin policies: once a request lands on a replica, it stays there, leaving the system structurally unable to react to cross-instance load imbalance or to re-isolate high-priority requests that arrive after an instance is already overloaded. Llumnix removes this constraint with runtime live migration of running requests across instances; this work generalizes the priority abstraction that migration is steered by.

The freeness metric

The central abstraction is the freeness of a replica, the slack between its KV-cache capacity and the virtual usage committed to it:

$$F \;=\; \frac{M - \sum_r V(r)}{B},$$

where $M$ is the replica’s total KV-cache block capacity, $\sum_r V(r)$ is the virtual usage summed over all requests $r$ associated with the replica (including queued ones), and $B$ is the current batch size. $F > 0$ signals available capacity; $F < 0$ means the replica is overloaded relative to its virtual commitments and triggers migration.

The per-request virtual usage encodes physical KV footprint, head-of-line demand, and a priority-dependent headroom term:

$$V(r) \;=\; \begin{cases} \textsf{req.demand} & r \text{ is head-of-line} \\ 0 & r \text{ queued} \\ \textsf{physUsage}(r) + H(p, i) & r \text{ running} \\ \infty & r \text{ on a draining replica} \end{cases}$$

The headroom function $H(p, i)$ returns the budget reserved for priority tier $p$ on instance $i$. In the original Llumnix this is a single scalar charged only to high-priority requests; generalizing it to $K$ tiers is the core of this extension.

Approach

Two-level architecture

The system follows Llumnix’s two-level design, adapted to Vidur. A Llumnix-style global scheduler sits atop $N$ Llumlet local replica schedulers, one per simulated GPU instance. The global scheduler dispatches incoming requests to the freest non-draining replica, decides when and which requests to migrate, issues auto-scaling recommendations from cluster-wide freeness, and marks replicas for graceful draining. Each Llumlet maintains a priority-ordered request queue, computes per-request virtual usage including priority headroom, manages block-level KV-cache allocation, and executes multi-stage live migration.

Multi-tier priority model

Llumnix defines headroom as a single scalar $h$, charged as $h / \text{numHighPriorityRequests}$ for high-priority requests and zero otherwise, so a loaded replica looks artificially less free and discourages further normal-priority dispatch. We generalize this to $K$ tiers. Each tier $p \in \{0, \dots, K-1\}$ gets a dedicated headroom budget via exponential decay:

$$H_p \;=\; M \cdot h_{\max} \cdot e^{-\lambda p},$$

with $h_{\max} = 0.20$ (tier 0 reserves 20% of capacity) and $\lambda$ chosen so $H_{K-1} \approx 0$. Exponential decay mirrors the diminishing isolation requirements of lower tiers while protecting overall efficiency. The total virtual headroom on a replica is

$$V_{\text{headroom}} \;=\; \sum_{p=0}^{K-1} H_p \cdot \mathbb{1}\bigl[\text{numRequests}(p) > 0\bigr].$$

The full budget $H_p$ is charged whenever any request of priority $p$ is present, not per request, so a single critical request can effectively block normal-priority dispatch to an overloaded replica.

Priority-aware dispatch and migration

The global scheduler keeps a sorted pending queue and dispatches in strict priority order (tier 0 first), FCFS within a tier, selecting the non-draining replica with the highest freeness ($\arg\max F$). Two freeness values are maintained per replica: full freeness $F_{\text{full}}$ includes priority headroom and drives dispatch and migration targeting, while normal-priority freeness $F_{\text{normal}}$ excludes headroom and is used only for auto-scaling, so isolation headroom is never mistaken for a genuine capacity shortage and never triggers spurious scale-out.

Migration is evaluated on a time interval (50 ms in most experiments) and a load-imbalance threshold $\Delta F = \max(F) - \min(F) \geq \theta$ ($\theta = 0.3$). When triggered, the scheduler picks low-freeness sources and high-freeness destinations and migrates one request each, preferring queued requests (no KV state, cheap) and then low-priority running requests with small footprints. Running requests migrate in stages: each stage copies a fixed block chunk from source to destination while the request keeps executing on the source, and only the final handoff incurs a brief re-enqueue latency, while decode tokens are generated throughout.

Simulation and baselines

The extended scheduler was implemented as a new policy in Vidur, forking both the Vidur and Llumnix codebases. Vidur’s discrete-event engine models transformer operator latencies from real profiling data, predicting TTFT, TBT, and end-to-end latency without GPU hardware; its configuration search can identify optimal deployments for LLaMA2-70B in roughly 1 CPU-hour versus an estimated 42,000 GPU-hours on real hardware. A PrioritySampler draws request tiers from three distributions: uniform (equal $1/K$ per tier, a stress test), Gaussian (middle-heavy, centered at $\lfloor K/2 \rfloor$), and enterprise (≈10% critical at tier 0, ≈70% mid-priority, 5–20% background, modeling a deployment where most traffic is standard). Request lengths follow a right-skewed synthetic mix calibrated to real API traffic (≈65% short 64–128-token turns, tapering to ≈2% very-long 384–512-token code generation). As the primary comparison baseline we implemented an INFaaS-style global scheduler with a cost-based dispatch function combining estimated queue depth, EWMA service time, and state penalties, but unlike Llumnix it performs no live migration and maintains no KV-aware freeness.

Results

Main priority sweeps run on 4 replicas at aggregate QPS = 1,250 (Poisson); the cross-scheduler benchmark uses QPS = 10 to isolate overhead. Experiments swept 120 configurations per distribution on Berkeley Research Computing infrastructure.

Priority differentiation works, and four tiers is the optimum

Under the uniform distribution, $K=1$ collapses to no differentiation (median end-to-end latency 10–12 s for everyone). At $K=3$, tier 0 reaches a median TTFT of ≈0.3 s versus over 3 s for tier 2, clear evidence of effective isolation. At $K=5$, tier 0 stays fast while tier 4 absorbs the longest tail, but the gap between adjacent mid-priority tiers narrows and system P99 rises slightly. The Gaussian distribution leaves tier-0 headroom mostly idle (few critical requests), so it is utilized less efficiently overall, while the enterprise distribution, with consistently busy tier-0 headroom and a large isolated mid-priority band, produces the largest absolute speedups.

Sweeping the scheduler comparison from $K=1$ to $K=10$ at moderate load, Llumlet sustains all 10 priority levels without latency collapse and holds aggregate parity with vLLM, Orca, and Sarathi-Serve. Llumlet’s P99 rises modestly to ≈1.61 s at $K=7$ before recovering (the cost of more active tiers inflating total virtual usage), and this overhead is concentrated in prefill, with decode latency stable or slightly better than baselines throughout. The aggregate trend confirms overhead neutrality; per-tier differentiation is the separate story shown by the controlled sweeps above.

Speedup over INFaaS+vLLM

The table reports speedup of the full system (Llumnix global + Llumlet local) over the INFaaS+vLLM baseline under the uniform distribution at two request scales. The $K=4$ optimum (in bold) recurs across all three distributions.

Scale	Prefill P99	Prefill mean	E2E P99	E2E mean	Cost/Lat.	$K$
10K requests	$4.79\times$	$8.23\times$	$2.87\times$	$2.80\times$	65%	3
10K requests	$\mathbf{4.87\times}$	$\mathbf{8.23\times}$	$\mathbf{3.13\times}$	$\mathbf{2.88\times}$	68%	4
10K requests	$4.16\times$	$8.11\times$	$3.04\times$	$2.92\times$	67%	5
15K requests	$2.98\times$	$5.00\times$	$1.87\times$	$1.97\times$	46%	3
15K requests	$\mathbf{3.16\times}$	$\mathbf{5.16\times}$	$\mathbf{2.12\times}$	$\mathbf{2.08\times}$	53%	4
15K requests	$2.72\times$	$5.07\times$	$2.04\times$	$2.12\times$	51%	5
Llumnix (reported)	$\leq 5.5\times$	$\leq 2.2\times$	$\leq 2.9\times$	$\leq 2.0\times$	16–36%	2

Three findings stand out. Four tiers is consistently optimal: across all distributions, $K=4$ achieves peak or near-peak E2E P99, E2E mean, and cost-per-latency, because four tiers separate critical, high, standard, and background traffic without fragmenting queues so finely that load-balancing heuristics lose traction. Prefill mean speedup exceeds the original paper ($5.0$–$8.3\times$ vs. Llumnix’s $\leq 2.2\times$): migration-driven load balancing continuously redistributes prefill work and prevents the convoy effect where bursty prefill requests pile onto one instance, whereas INFaaS’s reactive cost model responds more slowly to transient bursts. Cost-per-latency improvements (46–68%) also exceed the reported 16–36%, because consolidating low-priority requests frees KV capacity for high-priority work with fewer preemption penalties. Prefill P99 speedup is the one metric that drops at high load (2.0–$3.2\times$ at 15K), since near saturation all replicas approach capacity and the freeness differential that drives migration shrinks.

The priority-granularity tradeoff

The results crystallize a general principle: as $K$ grows, finer granularity enables more precise SLA differentiation, but each tier with any active requests charges its full budget $H_p$ to virtual usage, reducing effective batching capacity and raising average latency. The empirical optimum at $K=4$ is robust across workloads. Benefits are also load-dependent: most pronounced at moderate load where freeness variance is high and migration opportunities abundant, and diminishing near saturation where every replica is equally overloaded. This argues for pairing fine-grained prioritization with proactive auto-scaling that detects saturation before migration loses its leverage.

Future Work

The static exponential-decay schedule is the most natural thing to make adaptive: monitoring the observed latency differential between tiers and adjusting $H_p$ upward when SLO violations appear and downward when headroom sits unused. Tier assignment is currently fixed at arrival, so a multilevel-feedback-queue extension could promote long-waiting requests to prevent starvation of low tiers under sustained load. Vidur-Search could replace manual tuning entirely, automatically searching headroom schedules and tier counts for a given workload and SLO target. The cross-scheduler benchmark also ran below saturation (QPS = 10), where headroom rarely binds and pooled percentiles look similar across schedulers; rerunning at higher utilization with per-tier breakdowns would directly demonstrate the intended split of high tiers improving at the expense of low ones. Finally, validating the simulation on a real A100/H100 cluster would quantify the gap between simulated and hardware migration costs, which hinge on PCIe and NVLink bandwidth not fully captured by Vidur.