PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Anders Vestrum, Arya Raeesi, Hanna Roed

arXiv:2608.16336v1cs.ARcs.DCcs.LG

TL;DR

Production LLM serving needs more than Llumnix’s binary priority model to represent heterogeneous SLA tiers. This paper extends Llumnix to K-tier scheduling and finds that four tiers provide the best cost-efficiency point, with gains sustained through 10 tiers.

  • Problem

    Llumnix’s binary priority model cannot express the richer SLA classes needed by heterogeneous LLM serving deployments.

  • Method

    The paper extends Llumnix with K-tier scheduling, exponentially decayed per-tier headroom, tier-aware dispatch, and migration support, evaluated across three workload distributions.

  • Results

    Four priority tiers achieve peak end-to-end P99 speedups of up to 3.13× and cost-per-latency improvements of up to 68% over INFaaS+vLLM.

  • Takeaways & Limitations

    A four-tier SLA model can capture critical, high, standard, and background traffic while preserving migration-capable schedulers’ high-priority optimizations.

  • Takeaways & Limitations

    The results are simulation-based; validation on real GPU clusters is needed to quantify hardware-dependent migration costs.

Abstract

from arXiv · show

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.

1 Introduction

LLM serving must handle unpredictable, heterogeneous requests and diverse latency requirements that defeat single-instance, one-shot scheduling. This work extends Llumnix to multi-tier prioritization and evaluates the resulting cost-efficiency and load-dependent tradeoffs.

  • Motivation: Unpredictable token counts, memory footprints, execution times, bursty arrivals, and diverse latency requirements make traditional single-instance FCFS serving insufficient.
  • Motivation: Single-instance schedulers target homogeneous workloads and cannot react to fragmentation, cross-instance imbalance, or newly arrived high-priority requests after placement.
  • Approach: The paper extends Llumnix from binary priorities to K ≥2 tiers, assigning each tier exponentially decayed headroom budgets with priority-aware ordering and migration support.
  • Evaluation: The evaluation spans uniform, Gaussian, and enterprise priority distributions, 10K and 15K request volumes, and four baseline schedulers.
  • Findings: Four priority tiers provide the best cost-efficiency point, while additional tiers yield diminishing isolation gains and increasing overhead, especially as load approaches saturation.

2 Background and Related Work

LLM serving is shaped by the tension between compute-bound prefill and memory-bandwidth-bound decode, alongside dynamic KV-cache memory demands. Prior systems address batching, cache management, heterogeneous SLOs, and evaluation efficiency through continuous batching, routing, guard mechanisms, and high-fidelity simulation.

  • LLM inference fundamentals: Prefill processes input tokens in parallel, whereas decode generates tokens autoregressively, creating a throughput–TTFT and TBT tradeoff.More prefill batching improves throughput but increases TTFT, while prioritizing decode continuity reduces TBT but can starve arrivals.
  • LLM inference fundamentals: KV-cache allocation grows dynamically because output length is unknown, making fragmentation a major bottleneck that PagedAttention reduces to under 4% waste in most cases.The KV-cache stores intermediate attention states for all active requests and is the dominant memory consumer.
  • Related serving systems: Continuous batching eliminates head-of-line blocking, while vLLM combines it with PagedAttention and Sarathi-Serve uses chunked prefills with stall-free scheduling.Sarathi-Serve achieves up to 5.6× improvement in serving capacity under pipeline parallelism.
  • Related serving systems: INFaaS routes requests using queue depth, service-time predictions, and replica-state penalties but lacks live migration and per-request memory-dynamics adaptation.Its routing function accounts for replica health and SLO tracking through ACTIVE, OVERLOADED, INTERFERED, and INACTIVE states.
  • SLO-aware scheduling: SCORPIO and SLOs-Serve make heterogeneous SLOs explicit through latency guards and multi-SLO optimization, achieving goodput gains up to 14.4× and per-GPU capacity gains of 2.2×.SLOs-Serve combines chunked prefill with speculative decoding, while classical MLFQ and priority preemption motivate exponential headroom decay.
  • Evaluation methodology: Vidur predicts latency, throughput, MFU, and memory usage from profiled runtimes, enabling reproducible scheduling evaluation without physical GPU clusters.Vidur-Search identifies optimal LLaMA2-70B deployments in approximately 1 CPU-hour versus roughly 42,000 GPU-hours for real hardware search.

3 System Design

The system adapts Llumnix’s two-level architecture to Vidur with a global scheduler coordinating local Llumlet replica schedulers. It extends freeness-based scheduling to K priority tiers through per-tier headroom, strict tier-aware dispatch, migration, and priority-isolated auto-scaling.

  • Architecture: A global Llumnix-style scheduler dispatches requests, coordinates migrations, recommends auto-scaling, and drains replicas across multiple local Llumlet schedulers.Each Llumlet maintains a priority-ordered queue, computes virtual usage, manages KV-cache blocks, and performs live migration.
  • Freeness metric: F > 0 indicates available replica capacity, while F < 0 indicates overload relative to virtual commitments and triggers migration.Virtual usage includes running-request usage, head-of-line demand, and priority headroom.
  • Multi-tier headroom: K priority tiers receive dedicated exponentially decaying headroom budgets, with hmax = 0.20 reserving 20% of capacity for tier 0.The full tier budget is charged whenever any request of that tier is present, allowing one critical request to block normal-priority dispatch on an overloaded replica.
  • Priority-aware scheduling: Tier 0 requests dispatch first with FCFS within each tier, and each request targets the non-draining replica with highest freeness.Full freeness guides dispatch and migration, whereas normal-priority freeness is reserved for auto-scaling decisions.
  • Migration and auto-scaling: 50 ms migration checks and a default ∆F threshold of 0.3 identify low-freeness sources and high-freeness destinations for request migration.Queued requests are preferred as migration candidates, followed by low-priority running requests with small KV footprints; auto-scaling uses cluster-average normal-priority freeness with thresholds −0.5 and 1.5.

4 Implementation

The extended Llumnix scheduler was implemented as a Vidur scheduling policy, combining replica- and global-level scheduling with priority-aware queueing, tier headroom, KV-cache management, and migration state machines. Experiments used multiple priority distributions and fixed multi-replica simulation configurations.

  • Implementation: The scheduler was integrated into Vidur, whose discrete-event engine uses profiled transformer latencies to predict TTFT, TBT, and end-to-end latency without GPUs.The implementation forked both the Vidur and Llumnix codebases.
  • Implementation: The integration adds replica scheduling with priority-ordered queues, virtual usage, per-tier headroom, block-level KV-cache management, and multi-stage migration state machines.These capabilities are implemented in LlumletReplicaScheduler.
  • Workload Generation: Three priority distributions were supported: uniform assigns 1/K probability per tier, Gaussian is middle-heavy, and enterprise models critical, mid-priority, and lower-priority traffic.Priority 0 denotes critical or interactive requests, while priority K −1 denotes background or batch requests.
  • Experimental Setup: 1,250 QPS across 4 replica instances was used for main priority sweeps, while comparative benchmarks used QPS = 10 with 1,000 requests.Simulations ran with 120 parallelized CPU threads across 120 configurations per distribution type.

5 Evaluation

The extended scheduler differentiates latency across priority tiers, with four tiers providing the strongest speedup and cost-effectiveness tradeoff. It sustains this behavior through 10 priority levels under moderate load, with overhead concentrated in prefill and tail gains weakening near saturation.

  • Priority differentiation: At K = 3, tier 0 reaches approximately 0.3 s median TTFT versus over 3 s for tier 2, while K = 5 preserves differentiation but slightly increases overall P99.Under K = 5, gaps between adjacent mid-priority tiers narrow, and lower-tier performance worsens as headroom consumption rises.
  • Priority differentiation: With 10% critical traffic, the enterprise distribution consistently utilizes tier 0 headroom and isolates mid-priority tiers 1–2 from background traffic.The enterprise distribution is identified as the most practically relevant evaluation distribution.
  • Scalability and overhead: Across K = 1–10, aggregate latency remains broadly stable, while Llumlet’s P99 rises modestly to ∼1.61 s at K = 7 before recovering.At QPS = 10, the workload is below saturation, so aggregate percentiles largely mask per-tier differentiation; prioritization overhead is concentrated in prefill while decode remains stable or slightly better.
  • Speedup and cost-effectiveness: Four priority tiers consistently maximize or nearly maximize E2E P99 speedup, E2E mean speedup, and cost-per-latency improvement across uniform, Gaussian, and enterprise workloads.K = 4 separates critical, high, standard, and background traffic while retaining effective load balancing and meaningful headroom isolation.
  • Speedup and cost-effectiveness: 5.0–8.3× prefill mean speedup substantially exceeds Llumnix’s reported ≤2.2×.Migration-driven load balancing redistributes prefill work to underloaded replicas and prevents bursty requests from forming convoy effects.
  • Scalability and overhead: At 15K requests, prefill P99 speedup drops to 2.0–3.2× because near-saturation reduces freeness differentials and leaves insufficient slack to relieve KV-cache pressure.Prefill P99 is more sensitive than the mean to bursty memory spikes and capacity limits.

6 Discussion

The discussion identifies a priority-granularity tradeoff: increasing tier count improves SLA differentiation but consumes headroom, reduces batching capacity, and raises latency. It recommends moderate, workload-aware tiering with proactive scaling, while noting simulation limitations and hardware-validation needs.

  • Priority-granularity tradeoff: Increasing priority tiers improves SLA differentiation but increases headroom consumption, reduces effective batching capacity, and raises average latency.Each active tier contributes its full budget Hp to virtual usage.
  • Priority-granularity tradeoff: K = 4 is the empirically robust optimum across workload distributions, supporting an initial deployment choice of 3–4 tiers rather than maximum granularity.The recommendation is to increase tier count only when SLO differentiation requirements demand it.
  • Load sensitivity: 10K requests mark the regime where priority-aware scheduling benefits most, whereas near 15K-request saturation migration loses effectiveness as replicas become equally overloaded.The discussion recommends pairing priority scheduling with proactive auto-scaling before saturation.
  • Workload distributions: The enterprise distribution delivers the best cost-efficiency results, while Gaussian workloads show substantial sensitivity to tier count and may benefit from adaptive tier reconfiguration.Enterprise gains arise from well-populated mid-priority queues and limited tier-0 competition; Gaussian speedups vary significantly between K = 3 and K = 5.
  • Limitations and future work: Simulation results cannot be directly compared with Llumnix hardware measurements because implementations, simulated hardware effects, and workload traces differ.Future work includes adaptive headroom, multilevel feedback queues, and GPU-cluster validation focused particularly on migration costs.

7 Conclusion

The paper extends Llumnix’s binary priority model to K-tier scheduling in Vidur, combining exponentially decayed per-tier headroom, tier-aware dispatch, and migration support. Across workloads and priority levels, K = 4 is the consistent optimum, providing strong SLO differentiation with limited throughput loss and practical production guidance.

  • System extension: K-tier scheduling replaces Llumnix’s binary high/normal classification with exponentially decayed per-tier headroom, tier-aware dispatch ordering, and full migration support.The implementation achieves meaningful SLO differentiation across four or more priority classes without significant overall system throughput loss.
  • Evaluation results: 3.13× peak E2E P99 speedups and 68% cost-per-latency improvements over INFaaS+vLLM occur at four priority tiers.The evaluation spans three workload distributions, two request-volume scales, and priority levels from 1 to 10.
  • Evaluation results: Beyond K = 5, benefits plateau, while headroom fragmentation overhead begins to dominate.The conclusion identifies K = 4 as the consistent optimum across the evaluated workloads and scales.
  • Production guidance: A four-tier SLA model covering critical, high, standard, and background traffic captures the spectrum of user latency requirements while preserving migration-capable scheduling optimizations.The authors present this configuration as practical guidance for production LLM serving deployments.

Appendix A: Priority Differentiation: Gaussian and Enterprise Grids

The appendix presents priority differentiation under Gaussian and enterprise distributions using TTFT and TBT CDFs plus end-to-end latency violin plots. Both figures compare K = 1, K = 3, and K = 5 configurations by priority.

  • Evaluation Views: Figures 8 and 9 provide full TTFT CDF, TBT CDF, and end-to-end latency violin-plot views for the Gaussian and enterprise distributions.The visualizations follow the format of Figure 5 in the main paper.
  • Gaussian Priority Distribution: Gaussian priorities are evaluated across K = 1, K = 3, and K = 5 using TTFT CDFs, TBT CDFs, and end-to-end latency violin plots.Figure 8 mirrors the main paper’s priority-differentiation format.
  • Enterprise Priority Distribution: Enterprise priorities are evaluated across K = 1, K = 3, and K = 5 using TTFT CDFs, TBT CDFs, and end-to-end latency violin plots.Figure 9 mirrors the main paper’s priority-differentiation format.

Appendix B: Speedup Tables: Gaussian and Enterprise Distributions

Appendix B reports Llumnix+Llumlet speedups over INFaaS+vLLM for Gaussian and enterprise priority distributions. The K = 4 configuration is optimal across all three evaluated distributions.

  • Cross-distribution result: K = 4 is the best-performing configuration across all three priority distributions.The appendix states that this optimum holds for Gaussian, enterprise, and the third distribution evaluated in the main paper.
  • Gaussian distribution: Table 3 reports Llumnix+Llumlet speedup over INFaaS+vLLM for the Gaussian distribution.Bold K marks the best-performing configuration.
  • Enterprise distribution: Table 4 reports Llumnix+Llumlet speedup over INFaaS+vLLM for the enterprise distribution.Bold K marks the best-performing configuration.
Loading 2608.16336v1…