Llumnix: Dynamic Scheduling for Large Language Model Serving

• LLM requests vary in input and output lengths, latency objectives, execution time, and dynamically growing GPU-memory demand, making workload requirements unpredictable.The number of generated tokens is not known in advance, so both request duration and resource demand are uncertain.Source: §1 · p. 1
• Existing scheduling leaves isolation, memory fragmentation, and differentiated priorities unresolved, causing interference, SLO violations, queuing delays, and difficulty meeting diverse latency objectives.Load balancing can reduce preemptions and interference while fragmenting free memory across instances; existing systems often treat requests equally.Source: §1 · p. 2
• Llumnix runtime-reschedules requests across instances for load balancing, de-fragmentation, urgent-request prioritization, and faster instance saturation or draining during auto-scaling.The approach reacts at runtime rather than relying solely on one-shot request dispatch.Source: §1 · p. 2, Figure 1 · p. 2
• Llumnix combines request and GPU-memory-state migration with a distributed scheduling architecture and virtual-usage-based load balancing to unify rescheduling goals.Coordinated computation and memory transfer provide near-zero downtime constant to sequence length; continuous rescheduling is designed for scalability.Source: §1 · p. 2
• P99 first-token latency improves by up to 15× and P99 per-token generation latency by up to 2× versus INFaaS; high-priority requests accelerate 1.5×, with 36% cost savings at similar tail latencies.Evaluation used a 16-GPU cluster, realistic workloads, and vLLM as the underlying inference engine.Source: §1 · p. 2

Background

• Task-agnostic LLMs use context-specific prompts to support diverse applications, including chatbots, search, summarization, coding, assistants, and agents.The paper attributes this capability to larger models and datasets and pre-training approaches such as few-shot learning.Source: §2 · p. 3
• Applications create requests with varying input/output lengths and urgency; autoregressive serving makes prefill latency, including queuing, and decode token speed user-perceivable.The paper notes GPT-family maximum sequence lengths grew from 32k (GPT-4) to 128k (GPT-4 Turbo) from March to November 2023.Source: §2 · p. 3
• Continuous batching admits and removes requests immediately, while dynamically allocated PagedAttention KV-cache blocks support larger batches but can exhaust memory and force running requests back into the queue.The KV cache stores intermediate attention states for reuse across generated tokens; reserving for maximum sequence length would limit batch size.Source: §2 · p. 3

Unpredictable memory demands and preemptions

• 3.8× higher P99 than P50 per-token decode latency exposes the cost of unpredictable memory-driven preemptions in vLLM serving.At 0.42 req/s and 62% average memory load, 8% of requests were preempted; preemption accounted for 70% of the P99 request's latency, totaling 50 seconds across two preemptions.Source: §3 · p. 4

Performance interference among requests

• Up to 2.6× decode-step time gap at the same sequence length shows that batched requests interfere through GPU compute and memory-bandwidth competition.Figure 4 compares LLaMA-7B on one GPU and LLaMA-30B on four GPUs across sequence lengths and batch sizes.Source: §3 · p. 4, Figure 4 · p. 4

Memory fragmentation

• Queued prefill requests can persist despite sufficient total cluster memory when free memory is fragmented across instances.External fragmentation remains a prefill problem because accommodating all input-token KV cache blocks requires a single allocation on an instance; Figure 5 illustrates the mismatch between total free memory and queued-request demands.Source: §3 · p. 4, Figure 5 · p. 4

Different emergency and priorities of requests; Opportunity: request rescheduling across instances

• Latency-sensitive requests can be delayed by normal requests because existing systems treat requests equally, motivating systematic priority differentiation.Llumnix explores rescheduling across model instances, where free space elsewhere in the cluster may avoid preemptions, accommodate new requests, or mitigate interference; existing systems keep requests on their initially scheduled instance throughout autoregressive execution.Source: §3 · p. 4

4.1 Overview

• Llumnix reschedules requests across instances for load balancing, de-fragmentation, prioritization, and draining or saturating instances during auto-scaling.It builds on continuous batching and dynamic memory allocation; rescheduling reacts to actual memory growth as output lengths become known, while balancing load and fragmentation.Source: §4.1 · p. 5

4.2 Live Migration of LLM Requests

• By copying completed KV-cache blocks while decoding continues, Llumnix limits request downtime to copying the final iteration’s cache.KV cache is append-only, so earlier blocks remain unchanged; a handshake coordinates pre-allocation, completion or preemption checks, aborts, and commit across instances.Source: §4.2 · pp. 5–6

4.3 Distributed Scheduling Architecture

• Llumnix separates cluster-level, instance-oriented decisions from per-request migration decisions made by distributed instance-level llumlets.The global scheduler uses reported virtual-usage loads to dispatch requests, pair source and destination instances, and control auto-scaling; each llumlet selects requests and coordinates migration.Source: §4.3 · p. 6

4.4.1 Goals and Definitions

• Llumnix targets lower queuing, preemption, and interference costs, adapts to cluster load for cost efficiency, and supports request priorities for differing SLOs.Applications can specify scheduling priority to reduce queueing delay and execution priority to reduce interference; Llumnix currently supports high and normal classes and generalizes to more.Source: §4.4.1 · pp. 6–7

4.4.2 Virtual Usage

• Virtual usage unifies load balancing, de-fragmentation, prioritization, and instance draining by making selected requests or instances appear overloaded to the same policy.Queued requests receive virtual usage equal to their real memory demand; high-priority requests receive profiled headroom, while a terminating instance gets a fake request with infinite virtual usage.Source: §4.4.2 · p. 7

4.4.3 Policies

• Llumnix dispatches higher-scheduling-priority requests first to the instance with the highest freeness, F = (M −∑V)/B, and periodically migrates requests between instances selected by freeness thresholds.For migration, llumlets favor lower-priority and shorter-sequence requests; auto-scaling keeps average normal-priority freeness within a range by adding or terminating instances when thresholds persist.Source: §4.4.3 · p. 8

Implementation

• Llumnix is a standalone, extensible library with an interface for backend inference engines, and currently supports vLLM.The implementation comprises 3,300 lines of Python; vLLM provides continuous batching, PagedAttention, and tensor-parallel inference [34] [56].Source: §5 · p. 8

Multi-instance serving

• Ray [42] actors host backend instances and components, while request frontends expose an OpenAI-style API and forward generated tokens during migrations.This keeps token delivery to end users steady while requests move across backend instances.Source: §5 · p. 8

KV cache transfer

• Pipelined migration uses Gloo Send/Recv because concurrent NCCL invocations are unsafe, while maintaining negligible downtimes.KV-cache copies between CPU and GPU memory run on another CUDA stream to avoid blocking inference; in typical deployments, migration between instances does not interfere with single-machine tensor-parallel inference [44].Source: §5 · p. 8

Block fusion

• Llumnix fuses vLLM’s dynamically allocated, non-contiguous KV-cache blocks into a contiguous CPU buffer to avoid many small-message transfers.For a 16-bit LLaMA-7B model, each block is 128 KB, and a 1k-token sequence translates to 4k blocks.Source: §5 · p. 8

Fault tolerance

• If the global scheduler fails, frontends dispatch requests directly and disable migration; failed instances abort their running requests, and Ray restarts failed actors.Ongoing migrations on failed instances are aborted through a handshake, and the migrating request itself may or may not be aborted depending on source-instance health.Source: §5 · p. 9

6.1 Experimental Setup

• The evaluation uses a 16-GPU cluster, LLaMA-7B and LLaMA-30B models, public conversation datasets, and generated long-tail traces with varied arrival patterns and sequence lengths.The generated traces contain 10,000 requests each; all schedulers use vLLM as the underlying inference engine.Source: §6.1 · p. 9

6.2 Migration Efficiency

• Migration downtime stays roughly 20–30 ms as sequence length grows, up to 111× shorter than the baselines; migration adds up to 1% decode-time overhead while active.In serving experiments, each instance has ongoing migration for roughly 10% of the time span on average.Source: §6.2 · p. 10, Figure 10 · p. 10

6.3 Serving Performance

• On ShareGPT and BurstGPT traces, Llumnix improves end-to-end latency by up to 2× mean and 2.9× P99 versus round-robin and INFaaS++; it reduces mean preemption loss by 84% versus round-robin.On generated traces, it reduces preemption loss by 70.4% on average across experiments, equivalent to an average 1.3-second reduction in end-to-end latency.Source: §6.3 · pp. 10, 12, Figure 11 · p. 11
• Against INFaaS++, Llumnix improves mean/P99 end-to-end latency by up to 1.5×/1.6× and mean/P99 prefill latency by up to 7.7×/14.8× across generated traces.The gains are larger on traces with more long inputs, where migration reduces queuing from memory fragmentation.Source: §6.3 · pp. 10–11, Figure 11 · p. 11
• During a busy-period case study, Llumnix’s average fragmented-memory share is 0.7% versus INFaaS++’s 7.9%, a 92% reduction.Migration also reduces preemptions, which helps improve P99 decode latency by up to 2× versus INFaaS++ across generated traces.Source: §6.3 · pp. 11–12, Figure 12 · p. 11

6.4 Support for Priorities

• With 10% of requests prioritized, Llumnix improves high-priority mean request latency by 1.2× to 1.5× versus Llumnix-base, including under higher burstiness.Normal-request mean request, prefill, and decode latencies increase by up to 4.5%, 13%, and 2%, respectively.Source: §6.4 · p. 12, Figure 13 · p. 12

6.5 Auto-scaling

• With varying scaling thresholds, Llumnix preserves roughly 5s P99 prefill latency while saving 36% of cost versus INFaaS++.With the default scaling range, it saves up to 16% cost under Poisson arrivals and 18% under Gamma arrivals while improving latency.Source: §6.5 · pp. 12–13, Figure 15 · p. 13, Figure 14 · p. 13

6.6 Scheduling Scalability

• With 64 LLaMA-7B instances, Llumnix has near-zero scheduling stalls at high request rates, while the centralized baseline stalls up to 40 ms per iteration, causing 1.7× slowdown.Llumnix distributes intra-instance scheduling across llumlets and reports instance-level metrics rather than every request’s status.Source: §6.6 · p. 13, Figure 16 · p. 13

LLM inference

• Prior LLM-serving systems target diverse bottlenecks, including GPU kernels, cost efficiency, completion time, bursty-workload latency, batching, and memory use.Examples include FasterTransformer, TurboTransformer [25], LightSeq [61], FlashAttention [21], SpotServe, FastServe, AlpaServe [35], Orca, and vLLM [34].Source: §7 · p. 13

LLM inference and request scheduling

• Llumnix extends prior mostly solo-instance LLM-serving work with request migration and a unified load-aware policy for throughput, prioritized SLOs, and instance auto-scaling.Prior work includes kernel optimizations, preemptive serving, pipeline parallelism, continuous batching, and KV-cache memory optimization; the append-only KV cache enables request migration. The authors plan to explore combining global scheduling with local preemptive or fair scheduling.Source: §7 · pp. 13–14

Request scheduling

• Traditional DNN schedulers target one-time inference, whereas LLM requests autoregressively run unpredictable iterations and maintain KV-cache states; DeepSpeed-MII uses round-robin dispatch.Llumnix incorporates request migration and LLM-aware scheduling, unlike simple round-robin dispatch, to support throughput, latency, prioritized SLOs, and resource-efficient auto-scaling.Source: §7 · p. 14

Multiple model types

• Llumnix currently focuses on multiple instances, while INFaaS schedules across model types and variants; supporting multiple model types is future work.Potential LLM cases include task-specific fine-tuned models and variants with different sizes or precisions, expanding latency/throughput and accuracy tradeoffs.Source: §7 · p. 14

Isolation vs. fragmentation

• Llumnix uses runtime request migration to reconcile isolation and resource utilization as unpredictable LLM workloads change.Packing improves utilization but can cause interference, while spreading improves isolation but increases fragmentation; earlier work addressed the tradeoff in datacenters and GPU clusters, including Gandiva job migration.Source: §7 · p. 14

Migration

• Llumnix migrates requests while decoding continues on GPUs, minimizing downtime at negligible cost regardless of sequence length.Unlike Gandiva, which migrates training jobs through checkpoint-resume at mini-batch boundaries, directly migrating entire LLM request states is unacceptable for latency SLOs and can involve large, sequence-length-dependent working sets.Source: §7 · p. 14

• Llumnix envisions serving LLMs like Unix because both share universality, multi-tenancy, and dynamism.Source: §8 · p. 14
• It adapts OS isolation and priority abstractions, implements context switching through inference-request migration, and continuously reschedules requests.Source: §8 · p. 14
• Together, these mechanisms deliver better latency and cost efficiency while supporting differentiated SLOs.Source: §8 · p. 14

Abstract

• The artifact includes source code and scripts to run the experiments and reproduce the evaluation results.Source: Abstract · p. 19

Scope

• The artifact can be used to reproduce the results of experiments covering serving performance (Figure 11), support for priorities (Figure 13), and auto-scaling (Figures 14 and 15).Source: Scope · p. 19

Hosting

• Llumnix’s artifact is publicly available on GitHub’s `osdi24ae` branch, not the official release’s `main` branch.The paper notes that it describes the differences between the branches later.Source: Hosting · p. 19

Requirements

• Reproduction requires four GPU machines, each with four 24 GB A10 GPUs; the authors recommend the ecs.gn7i-c32g1.32xlarge VM type.The artifact runs on GPU machines and has software dependencies mostly the same as vLLM.Source: Requirements · p. 19

Difference from the Official Release

• The artifact is based directly on vLLM, whereas the official release is a standalone Python library designed to be more extensible and non-intrusive to inference backends.Source: Difference from the Official Release · p. 19
• The artifact is not fault-tolerant, whereas the official release provides fault tolerance for each component.Source: Difference from the Official Release · p. 19
• The official release is actively developed, with support for distributed request frontends, newer vLLM versions and models, and further scheduling-policy improvements supported or planned.Source: Difference from the Official Release · p. 19
• The artifact reproduces the paper’s experiments, but the official release is recommended for production use or further research.The artifact is a research prototype used in the paper’s experiments; the official release was refactored afterward.Source: Difference from the Official Release · p. 19
• The artifact is sufficient to reproduce the paper’s results, while the official release is recommended for production use or further research.Source: Difference from the Official Release · p. 19