📊 statistics

Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents

This paper establishes the mathematical queueing fundamentals for LLM inference, proving that work-conserving scheduling algorithms achieve maximum throughput for both individual and AI-agent workloads, while evaluating real-world systems to confirm the optimality of Orca and Sarathi-Serve and cautioning against the instability of FasterTransformer and vanilla vLLM.

Original authors: J. G. Dai, Tianze Deng, Yueying Li, Tianyi Peng

Published 2026-05-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: J. G. Dai, Tianze Deng, Yueying Li, Tianyi Peng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you run a high-speed factory that builds custom robots. In this factory, every order (a "request") goes through two distinct stages:

The Setup Phase (Prefill): You read the blueprints and gather all the necessary parts. This is a heavy lifting job that requires a lot of brainpower (compute) but happens all at once.
The Assembly Phase (Decode): You start building the robot, adding one part at a time, one by one. This is a slower, memory-heavy job that happens step-by-step.

Your factory has a giant, super-fast robot arm (the GPU) that can work on multiple orders simultaneously. However, the arm has a limit: it can only hold a certain total weight of parts in its gripper at once (the Token Budget).

The paper you provided is a mathematical study on how to organize the orders so that your factory never stops working and produces the maximum number of robots possible without getting clogged up.

Here is the breakdown of their findings using simple analogies:

1. The Golden Rule: "Don't Let the Arm Sit Idle"

The most important discovery in this paper is a concept called "Work-Conserving."

Imagine your robot arm is ready to grab parts.

The Bad Way: You only let the arm grab "Setup" parts if there are only Setup orders waiting. If there are "Assembly" orders waiting, you ignore them, even if the arm has empty space. Or, you only let it grab "Assembly" parts if there are only Assembly orders.
- Result: The arm sits half-empty, waiting for a specific type of order, while a huge pile of the other type of order builds up. The factory slows down or crashes.
The Good Way (Work-Conserving): If the arm has space, you fill it up with whatever is available. You mix Setup parts and Assembly parts in the same batch. You never let the arm sit idle if there is work to be done.

The Paper's Claim: Algorithms that follow this "fill the bucket" rule (like Orca and Sarathi-Serve) are mathematically proven to be the most efficient. They can handle the maximum possible amount of work without the system breaking down.

2. The "Old" vs. "New" Factory Managers

The authors tested four popular "managers" (scheduling algorithms) to see who followed the Golden Rule:

FasterTransformer & Vanilla vLLM (The Strict Managers): These managers are too picky.
- FasterTransformer only grabs Assembly parts. If there are no Assembly orders, it ignores the Setup orders waiting in line, even if the arm is empty.
- Vanilla vLLM only grabs Setup parts. If there are no Setup orders, it ignores the Assembly orders.
- Verdict: These are not optimal. Under heavy load, they cause the factory to get clogged and unstable.
Orca & Sarathi-Serve (The Flexible Managers): These managers mix the two types of work. They fill the arm with whatever fits.
- Verdict: These are optimal. They keep the factory running smoothly at maximum speed.

3. The "AI Agent" Factory (Complex Workflows)

Sometimes, one order isn't just a single robot; it's a whole team of robots working together.

The DAG (Directed Acyclic Graph): Imagine a workflow where Order A goes to Station 1, then Station 2, then Station 3, and never goes back.
- Finding: As long as the workflow is a straight line (no loops), the "Don't Let the Arm Sit Idle" rule still works perfectly across all stations.
The Fork-Join: Imagine Order A splits into three sub-tasks that go to three different stations, and they all have to finish before the final step can happen.
- Finding: The "Don't Let the Arm Sit Idle" rule still works here, too.
The Cycle (The Trap): Imagine Order A goes to Station 1, then Station 2, but Order B goes from Station 2 back to Station 1. They are chasing each other in a circle.
- Finding: Here, the "Don't Let the Arm Sit Idle" rule can fail. Even if the managers are trying their best, the circular traffic can cause a traffic jam that never clears. The paper shows that if your factory has these circular loops, you need a much smarter, more careful manager, not just a "fill the bucket" one.

4. The "Bucket Size" Surprise

There is a second limit in the factory: the Batch Size. This is the maximum number of orders the arm can hold, regardless of how heavy they are.

The Surprise: The authors found that sometimes, filling the arm to its absolute maximum weight limit (the Token Budget) is actually a bad idea.
The Analogy: Imagine you have a bucket that holds 100 lbs. You have 100 tiny pebbles (Setup) and 100 heavy bricks (Assembly).
- If you try to fill the bucket to 100 lbs with bricks, you might only fit 5 bricks. The time it takes to lift that heavy load is long.
- But if you stop at 50 lbs (a smaller load), you might be able to lift it much faster, allowing you to do more trips per hour.
The Finding: In specific situations, the most efficient strategy is to stop filling the bucket before it's full to keep the processing speed high. This means that even the "Good Managers" (Work-Conserving) can fail if the factory rules (batch size limits) are too strict and the mix of orders is just right to cause a jam.

Summary

The paper tells us:

Mix your work: Don't separate Setup and Assembly tasks. Mix them in the same batch to keep the GPU busy.
Orca and Sarathi-Serve are the winners: They follow the "mix and fill" rule, making them the most stable and efficient choices for most situations.
Watch out for loops: If your AI agents send tasks back and forth between servers in a circle, simple "fill the bucket" rules might not work; you need special traffic control.
Full isn't always best: Sometimes, leaving a little empty space in your batch is smarter than filling it to the brim, depending on how big the individual tasks are.

The goal of all this math is to help engineers build AI systems that don't crash when millions of people ask questions at once.

Technical Summary: Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents

Problem Statement

As demand for Large Language Models (LLMs) and AI agents grows, optimizing inference systems for efficiency is critical. While significant engineering efforts have focused on system-level improvements, there is a lack of a cohesive mathematical modeling and queueing-theoretic framework to evaluate scheduling algorithms. Specifically, the paper addresses the fundamental question: What is the maximal throughput rate for an LLM inference system, and which classes of scheduling algorithms can achieve this limit?

LLM inference presents unique challenges compared to classical queueing systems:

Dual-Phase Processing: Requests undergo a compute-bound prefill phase (processing input tokens to build the KV cache) followed by a memory I/O-bound decode phase (autoregressive token generation).
Batching Constraints: To maximize GPU utilization, requests are batched. However, mixing prefill and decode tokens creates interference, and hardware imposes a token budget ( $b_{max}$ ) and often a batch size ( $k_{max}$ ) constraint.
AI-Agent Workloads: Modern applications involve networks of LLM servers processing complex agent tasks, which may follow Directed Acyclic Graph (DAG) topologies, fork-join patterns, or contain cyclic routing.

Existing systems employ diverse strategies (e.g., FasterTransformer, vLLM, Orca, Sarathi-Serve) with varying priorities (prefill-first vs. decode-first) and batching capabilities (mixed vs. separated). Practitioners currently rely on costly, workload-specific benchmarking to choose systems, lacking a theoretical guarantee of stability or throughput optimality.

Methodology

The authors develop a rigorous queueing-theoretic framework to model LLM inference systems.

1. Stochastic Modeling

Basic Model: The system is modeled as a discrete-time Markov chain (DTMC) representing a two-class batch-service queue.
- Classes: Requests exist in either a prefill queue or a decode queue.
- Batching: The server processes a batch of tokens from both queues simultaneously, subject to a token budget $b_{max}$ .
- Asymmetry: Prefill tokens from a single request can be processed in bulk, while decode tokens are strictly sequential (one per request per batch).
Processing Time Model: Leveraging empirical traces, the batch processing time $t_b$ is approximated by a piecewise constant function dependent on the token load $b$ :
$t_b = c + a \cdot \lceil b/b_0 \rceil$
where $c$ is the base cost, $a$ is the marginal cost per block of $b_0$ tokens. This model captures the dominance of linear-layer computations in LLM inference.

2. Analytical Framework

Fluid-Limit Technique: The authors employ the fluid-limit framework (Dai 1995, Stolyar 1995) to analyze stability. They prove that under specific conditions, the scaled stochastic process converges to a deterministic fluid model.
Stability Definition: A system is stable (positive recurrent) if the total number of unprocessed tokens does not diverge as time approaches infinity.
Scheduling Class: The analysis focuses on work-conserving algorithms (those that fill the batch to capacity $b_{max}$ whenever possible) and introduces the K-FCFS condition (First-Come-First-Served with bounded overtaking) to handle the complexities of mixed batching.

3. Extensions

The framework is extended to:

Parallel Servers: Systems with load balancing (Random or Join-the-Shortest-Queue).
Multi-Class Networks: Single servers handling multiple request classes (e.g., different agent steps).
Network Topologies: Multi-server networks with DAG routing and fork-join synchronization.
Cyclic Routing: Analysis of networks with feedback loops (Rybko–Stolyar type).
Batch Size Constraints: Analysis of systems constrained by both token budget ( $b_{max}$ ) and maximum batch size ( $k_{max}$ ).

Key Contributions and Results

1. Throughput Optimality of Work-Conserving Scheduling

The paper establishes a fundamental design principle: Work-conserving scheduling algorithms achieve maximum throughput for single-server LLM inference and networks with DAG or fork-join topologies.

Theorem 2: For a single server, if the arrival load $\lambda(m_p + m_d)$ is less than the maximum processing rate $b_{max}/t_{b_{max}}$ , any work-conserving K-FCFS algorithm stabilizes the system. Conversely, if the load exceeds this threshold, the system is unstable under any algorithm.
Implication: This provides a theoretical upper bound ( $b_{max}/t_{b_{max}}$ ) and validates the shift in the industry toward work-conserving schedulers.

2. Evaluation of Existing Systems

Applying the theoretical framework to real-world algorithms yields clear classifications:

Throughput-Optimal (Work-Conserving):
- Orca: Supports mixed batching (prefill + decode) with prefill priority.
- Sarathi-Serve: Supports chunked prefill with decode priority and mixed batching.
- Latest vLLM (with chunked prefill): Work-conserving.
Suboptimal/Unstable (Non-Work-Conserving):
- FasterTransformer: Prioritizes decode but forbids mixed batching. It leaves the GPU idle when decode requests are insufficient to fill a batch, even if prefill requests are waiting.
- Vanilla vLLM: Prioritizes prefill but forbids mixed batching. It leaves decode requests waiting while processing prefill-only batches.
Experimental Validation: Real-world traces confirm that non-work-conserving algorithms (FasterTransformer, vanilla vLLM) become unstable (queue blowup) under moderate loads where work-conserving algorithms (Sarathi-Serve, Orca) remain stable.

3. AI-Agent Workloads and Network Topologies

DAG and Fork-Join: The paper proves that work-conserving scheduling remains throughput-optimal for networks of LLM servers arranged in DAGs or fork-join topologies, provided the load condition holds at each server.
Cyclic Routing (Rybko–Stolyar Counterexample): The authors demonstrate that work-conserving scheduling is not sufficient for networks with cyclic routing. They construct a two-server network where specific priority assignments under a work-conserving policy lead to instability, even when the total load is below capacity. This highlights the need for careful priority design or non-work-conserving policies (e.g., back-pressure) in cyclic topologies.

4. Impact of Batch Size Constraints

When a maximum batch size constraint ( $k_{max}$ ) is imposed alongside the token budget ( $b_{max}$ ):

The stability region becomes a two-dimensional convex hull in the $(\lambda_{prefill}, \lambda_{decode})$ plane, rather than a simple scalar threshold.
Counterintuitive Finding: In certain regimes (specifically near a vertex of the stability region involving mixed batches), strictly work-conserving algorithms that always fill to $b_{max}$ may fail to stabilize the system. Optimal stability may require operating at a lower token load (e.g., $b_0$ ) to balance the processing rates of prefill and decode tokens. This suggests that under tight batch size constraints, adaptive scheduling strategies are necessary.

Significance and Claims

The paper claims to provide the first rigorous queueing-theoretic foundation for LLM inference scheduling. Its significance lies in:

Design Principle: It identifies "work-conserving" as a key design principle for practitioners, offering theoretical assurance that algorithms like Sarathi-Serve and Orca are throughput-optimal, while warning against non-mixed batching approaches like FasterTransformer and vanilla vLLM.
Bridging Communities: It lowers the barrier for the queueing theory community to contribute to LLM systems by providing a formal model that captures the unique dual-phase and batching characteristics of LLMs.
Guidance for AI Agents: It extends stability analysis to AI-agent workloads, revealing that while DAG topologies are robust, cyclic topologies require more sophisticated scheduling than simple work-conserving policies.
Nuanced Constraints: It reveals that practical constraints like batch size limits can fundamentally alter stability regions, challenging the assumption that "filling the batch" is always optimal.

The authors conclude that while their work establishes a baseline for throughput optimality, future work must address latency optimization, richer processing time models (incorporating attention layers), and the design of adaptive algorithms for complex constraints and network topologies.