Beyond Binary Priorities: Multi-Tier SLA Scheduling for Large Language Model Serving

Serving every LLM request at the latency its tier is paying for

When you message an AI assistant, your request shares a GPU cluster with thousands of others: a chat turn that needs a sub-second reply, an enterprise API call with a contractual deadline, a batch job that can wait minutes. Llumnix (Sun et al., OSDI 2024) was the first system to treat this as a live-migration problem: instead of pinning each request to the instance it landed on, it moves running requests between instances to balance load and isolate priority traffic, cutting tail latency by an order of magnitude. But its notion of priority is a single bit, high or normal. Providers sell three to five SLA tiers, and one bit cannot express that.

This project extends Llumnix to K tiers, each with its own isolation budget, and asks how many tiers such a system should run. The answer, from a re-implementation inside Microsoft Research’s Vidur simulator across three workloads, is four: up to 3.1× better end-to-end P99 and 46 to 68 % better cost-per-latency, holding to ten tiers without tail collapse. Joint work with Anders Vestrum and Hanna Roed at UC Berkeley; on arXiv as 2608.16336.

Why one bit isn’t enough

LLM inference has two phases with opposite profiles: a compute-bound, bursty prefill over the input tokens, then a memory-bound decode that generates one token at a time. The KV-cache holding attention state dominates memory, and since output length is unknown at arrival, its footprint grows unpredictably. Every scheduling decision in Llumnix runs off one number, the freeness of a replica: the slack between its KV capacity and the usage committed to it, where committed usage includes a headroom term charged for high-priority requests. Headroom is virtual. It reserves nothing in memory; it just makes a replica holding priority traffic look fuller, so new normal traffic goes elsewhere.

In the original system that headroom is one scalar, charged for one class of request. Generalising it is the core of the work.

How it works

Two-level architecture. A global scheduler dispatches to the freest replica and decides what to migrate; a Llumlet on each replica keeps a priority-ordered queue, computes per-request virtual usage, and executes live migration.

A headroom budget per tier. Each tier p gets its own budget, decaying exponentially from the top: tier 0 reserves 20 % of capacity, and each tier below gets about a third of the one above, so the lowest tiers reserve almost nothing. The full budget is charged whenever any request of that tier is present on a replica, not per request. A single critical request is enough to steer background traffic away.

Dispatch and migration. Requests are dispatched in strict tier order, first-come-first-served within a tier, to the replica with the highest freeness. Every 50 ms the scheduler checks the imbalance between the freest and the fullest replica, and if it exceeds a threshold it moves one request from the full one to the free one, preferring cheap queued requests, then small low-tier ones. Tier 0 is never the one that moves.

Simulating it. Rather than burn GPU hours, the extended scheduler is a new policy inside Vidur, a discrete-event LLM-serving simulator that predicts latency from real profiling data. Tiers are drawn from three distributions: uniform (a stress test), Gaussian (middle-heavy), and enterprise (about 10 % critical, 70 % mid, the rest background). The primary baseline is an INFaaS-style global scheduler with cost-based dispatch but no migration, plus vLLM, Orca, and Sarathi-Serve.

Results

Tiers are isolated. Under the uniform distribution, K = 1 collapses to no differentiation: 10 to 12 seconds for everyone. At K = 3, tier 0 sees a median time-to-first-token of about 0.3 s while tier 2 waits over 3 s. At K = 5 the extremes stay apart, but the middle tiers bunch together.

Four tiers is the optimum. Speedup of the full system over INFaaS+vLLM, uniform distribution; the K = 4 row (bold) is peak or near-peak on every metric, and the same optimum recurs under the Gaussian and enterprise 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

Two numbers beat the original paper. Prefill mean speedup is 5 to 8× against Llumnix’s reported 2.2×, because continuous migration prevents the convoy effect where bursty prefill piles onto one instance. Cost-per-latency is 46 to 68 % against 16 to 36 %, because consolidating low-priority work frees KV capacity with fewer preemptions. The one metric that softens under heavy load is prefill P99, since near saturation the freeness differences that drive migration shrink. Swept to K = 10, the system holds parity with vLLM, Orca, and Sarathi-Serve with no tail collapse.

What I took away

More knobs to express priority do not monotonically help. Every tier spends real batching capacity on isolation it may never use, and the win sits where differentiation is fine enough to matter but coarse enough that the load balancer still has room to move things. For this workload, four is where those pressures meet.

The natural next steps are on the budget side: make the decay schedule adaptive, nudged by observed SLO violations; promote long-waiting requests so no tier starves; and validate migration costs on real A100 or H100 hardware rather than in simulation.