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

Anders Vestrum; Arya Raeesi; Hanna Roed

cs.ARAug 17, 2026

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

Authors: Anders Vestrum, Arya Raeesi, Hanna Roed

Organizations: UC Berkeley, EECS Department

Abstract

Modern LLM serving deployments must simultaneously satisfy heterogeneous service-level objectives (SLOs) across a diverse population of user tiers, ranging from latency-critical API calls to background batch processing. Llumnix introduced a dynamic, migration-capable multi-instance scheduler for LLM inference that achieves load balancing, defragmentation, prioritization, and auto-scaling through a unified "freeness" metric. However, Llumnix's priority model is restricted to two levels (high and normal), an abstraction too coarse to express the richer SLA classes common in production deployments. In this work, we extend Llumnix's priority model to support an arbitrary number of tiers and evaluate the effects of this extension under three realistic priority distributions (uniform, Gaussian, enterprise) using Vidur, a high-fidelity LLM inference simulator. We implement per-tier headroom with exponential decay, tier-aware dispatch ordering, and the full Llumnix migration pipeline inside Vidur's hierarchical scheduling framework. We compare our extended scheduler against INFaaS (global routing baseline), vLLM, Orca, and Sarathi-Serve (per-replica baselines), sweeping priority levels from 1 to 10. Our experiments demonstrate that four priority tiers yields the best cost-effectiveness tradeoff, achieving prefill mean speedups of up to 8.3x and end-to-end P99 speedups of up to 3.1x over INFaaS with cost-per-latency improvements of 46 to 68%, while preserving strong SLO differentiation across tiers. We further show that the system sustains these gains at 10 priority levels without tail latency collapse, with overhead concentrated in the prefill phase.

Figures & tables

Panel of Figure 1 — Figure 1: Two-level scheduling architecture. Priority-tagged request streams $P_{0}$ (critical) through $P_{K-1}$ (background) enter the Llumnix global scheduler, which dispatches them to $N$ Llumlet replica schedulers and receives freeness reports in return. Bidirectional migration links support live KV-cache transfer between replicas.

Panel of Figure 2 — Figure 2: Components of virtual usage in the freeness metric. The stacked bar shows a single replica’s KV memory partitioned into running-request allocations, head-of-line demand, priority headroom, and free space. Freeness $F$ is positive when virtual usage leaves slack, and goes negative when headroom plus demand exceed $M$ , triggering migration.

Panel of Figure 3 — Figure 3: Per-tier headroom allocation under exponential decay ( $K=4$ , $h_{\max}=0.20$ , $\lambda=1.0$ ). Tier 0 reserves 20% of KV capacity; each subsequent tier decays by $e^{-\lambda}{\approx}37\%$ . Total headroom across all tiers is 31.1% of $M$ .

Panel of Figure 4 — Figure 4: Multi-stage live migration of a running request’s KV-cache from Instance A to Instance B. In each stage the Llumlet copies a fixed block chunk while the request continues executing on A. After the final stage the request is committed to B. Only a brief re-enqueue latency is incurred at the handoff; decode-phase tokens are generated throughout.

Tokens	Prob.	Description
64–128	$\sim$ 65%	Short (chat, classification)
128–256	$\sim$ 22%	Medium (summarization)
256–384	$\sim$ 10%	Long (document analysis)
384–512	$\sim$ 2%	Very long (code generation)

Table 1: Request length distribution used in all experiments.

Figure 5: Priority differentiation under uniform priority distribution. Rows: $K=1$ , $K=3$ , $K=5$ priority tiers. Columns: TTFT CDF, TBT CDF, end-to-end latency violin plot by priority.

Panel of Figure 6 — Figure 6: End-to-end latency (P50/P90/P99) for all schedulers as a function of priority level count $K$ (4 replicas, 1,000 requests, QPS $=10$ ). Across $K=1$ – $10$ , aggregate latency remains broadly stable, indicating that increasing priority granularity does not introduce large overhead at this load.

Figure 7: Llumlet vs. vLLM Round-Robin across priority levels $K=1$ – $10$ , broken down by request end-to-end, prefill, and decode latency (P99 and mean).

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
	4.87 $\times$	8.23 $\times$	3.13 $\times$	2.88 $\times$	68%	4
	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
	3.16 $\times$	5.16 $\times$	2.12 $\times$	2.08 $\times$	53%	4
	2.72 $\times$	5.07 $\times$	2.04 $\times$	2.12 $\times$	51%	5

Table 2: Speedup over INFaaS+vLLM — Uniform distribution. Bold

K

marks the best-performing configuration.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 8: Priority differentiation under Gaussian priority distribution. Rows: $K=1$ , $K=3$ , $K=5$ . Columns: TTFT CDF, TBT CDF, end-to-end latency violin plot by priority.

Figure 9: Priority differentiation under enterprise priority distribution. Rows: $K=1$ , $K=3$ , $K=5$ . Columns: TTFT CDF, TBT CDF, end-to-end latency violin plot by priority.

Scale	Prefill P99	Prefill Mean	E2E P99	E2E Mean	Cost/Lat.	K
10K requests	3.24 $\times$	7.47 $\times$	2.26 $\times$	2.45 $\times$	56%	3
	4.25 $\times$	8.33 $\times$	3.07 $\times$	2.79 $\times$	67%	4
	3.49 $\times$	7.51 $\times$	2.43 $\times$	2.74 $\times$	59%	5
15K requests	2.00 $\times$	4.68 $\times$	1.49 $\times$	1.71 $\times$	33%	3
	2.70 $\times$	5.24 $\times$	2.02 $\times$	1.96 $\times$	51%	4
	2.25 $\times$	4.88 $\times$	1.97 $\times$	1.67 $\times$	41%	5

Appendix

Table 3: Speedup over INFaaS+vLLM — Gaussian distribution. Bold

K

marks the best-performing configuration.

Scale	Prefill P99	Prefill Mean	E2E P99	E2E Mean	Cost/Lat.	K
10K requests	3.10 $\times$	8.06 $\times$	2.18 $\times$	2.27 $\times$	54%	3
	4.41 $\times$	8.28 $\times$	3.02 $\times$	2.79 $\times$	67%	4
	4.12 $\times$	8.14 $\times$	2.96 $\times$	2.89 $\times$	66%	5
15K requests	1.77 $\times$	4.51 $\times$	1.31 $\times$	1.44 $\times$	24%	3
	2.76 $\times$	5.04 $\times$	1.94 $\times$	1.95 $\times$	48%	4
	2.61 $\times$	5.06 $\times$	1.97 $\times$	2.08 $\times$	49%	5

Appendix

Table 4: Speedup over INFaaS+vLLM — Enterprise distribution. Bold

K

marks the best-performing configuration.

LLM Inference Scheduling

Large language model inference scheduling allocates requests, batches, compute, and KV-cache memory to balance latency, throughput, and service-level objectives.

See all 160 papers

Cascade: Exploiting SLO-Aware latency budget for fair and high goodput LLM inference serving
Aug 6, 2026Muhammad Adnan, Rohan Mahapatra, Prashant J. Nair +4LLM Serving LLM Inference Scheduling
The University of British Columbia · Microsoft Azure Research · NVIDIA
Beyond Prediction: Tail-Aware Scheduling for LLM Inference
Jun 16, 2026Yueying Li, Yuanfan Chen, Jiayang Chen +6LLM Serving Inference-Time Optimization
Cornell University, Computer Science Department, NY, USA · Microsoft Azure System Research, WA, USA · Cornell University, Electrical and Computer Engineering Department, NY, USA +2
Ranking Before Serving: Low-Latency LLM Serving via Pairwise Learning-to-Rank
Sep 25, 2025Yiheng Tao, Yihe Zhang, Matthew Dearing +4LLM Serving Learning to Rank
University of Illinois Chicago, Chicago, IL, USA · Argonne National Laboratory, Lemont, IL, USA

Aug 6, 2026J/K move · Enter open · S save

Cascade: Exploiting SLO-Aware latency budget for fair and high goodput LLM inference serving

Muhammad Adnan, Rohan Mahapatra, Prashant J. Nair, Daniel Berger+3

The University of British Columbia · Microsoft Azure Research · NVIDIA

LLM Serving LLM Inference Scheduling KV-Cache Management

Open paper AskPDF arXiv

The reasoning and agentic capabilities of large language models have expanded the range of applications they support, from short interactive exchanges to long, compute-heavy requests. LLM serving platforms today define response-latency service-level objectives, even though requests within the same service can differ by orders of magnitude in input length, generation length, execution cost, and the availability of reusable KV-cache state. As a result, requests governed by the same service level objective have different urgency: after accounting for the time required to execute them, some have substantial latency headroom while others have almost none. We define this headroom---the difference between a request's service level objective and its predicted remaining service time---as its per-request latency budget. We present Cascade, an LLM serving system that estimates and continuously updates this budget from request characteristics, KV-cache state, and current system load. Unlike prior SLO-aware schedulers that use deadlines to govern request ordering alone, Cascade uses a single per-request budget to jointly coordinate request scheduling and KV-cache management across the memory hierarchy. Its scheduler prioritizes requests with little remaining budget, while its memory manager uses the same budget to decide whether non-resident KV state should be restored or prefetched from a deeper tier, retained in HBM, or recomputed. By directing queueing and data-movement overhead toward requests that can absorb it, Cascade improves SLO-satisfied goodput while preserving fairness across heterogeneous request classes. On production traces across three large language models, Cascade improves goodput by up to2.4x and reduces SLO violations by 40% relative to the default vLLM first-come, first-served scheduler.

Abstract

LLM Inference Scheduling

Explore similar work

Cascade: Exploiting SLO-Aware latency budget for fair and high goodput LLM inference serving

Beyond Prediction: Tail-Aware Scheduling for LLM Inference

Ranking Before Serving: Low-Latency LLM Serving via Pairwise Learning-to-Rank