Bursty LLM Scheduling: A Smarter WAIT for Real Traffic

Bursty LLM Scheduling: A Smarter WAIT for Real Traffic

Introduction

If you’ve ever used an LLM-powered app and noticed it feels “smooth… until it suddenly doesn’t,” you’ve already experienced the problem this research tackles. In real production systems, requests don’t arrive at a steady pace—they come in bursts, with quiet periods and sudden spikes. That mismatch between bursty workload reality and the simplified scheduling assumptions used in many inference papers is exactly what the authors address in new research from the original paper.

This work focuses on LLM inference scheduling under bursty workload distribution, by modifying the WAIT algorithm. Instead of pretending the arrival rate of requests is fixed (or even known in advance), the authors estimate it online and adapt batching decisions on the fly. The big idea: keep the strengths of WAIT (efficient batching that respects memory limits) but make it robust when traffic is non-stationary and unpredictable.

Why This Matters

Right now, LLM serving is “everywhere,” but capacity planning and performance engineering still often assume stability. Many systems still schedule as if request arrivals are roughly constant, which can create avoidable failure modes: GPU underutilization during lulls, or latency spikes when bursts hit and batching decisions lag behind reality. This research is significant because it directly targets the gap between queueing-model assumptions and the bursty, human-driven patterns seen in interactive AI products.

A very practical scenario: imagine a school chatbot or customer support agent that gets steady traffic all morning, then a burst at 3pm when a popular assignment drops or a support email campaign goes out. During the quiet period, you don’t want the scheduler to wait too long before forming batches (or you waste GPU cycles). During the burst, you need the scheduler to form batches quickly without thrashing memory (e.g., causing KV-cache churn). The modified WAIT approach is designed for exactly this kind of “sudden regime change” behavior.

And importantly, it builds on earlier AI scheduling efforts, but with a more theory-aware lens. Prior work like Sarathi and vLLM emphasize batching policies and systems efficiency—often evaluated under fixed-rate arrival assumptions. By modeling burstiness using an MMPP-2 (two-state Markov Modulated Poisson Process) and then adapting WAIT using online rate estimation, the paper moves scheduling toward something more defensible in real-world deployments.

Main Content Sections

What “Bursty Workloads” Break in Classic LLM Scheduling

LLM inference isn’t one simple step—it’s two phases: prefill and decode. Prefill processes the entire prompt at once (and builds KV-cache entries). Decode then generates tokens sequentially, one token per iteration, while reusing cached KV values and adding one new KV unit per generated token.

This structure creates a subtle scheduling problem:

• During prefill, you can benefit from parallelization (many prompts can be processed together).
• During decode, the system is limited by KV-cache growth and memory constraints.
• If your scheduler makes the wrong batching decision, you either:
  • Wait too long, leaving the GPU idle (hurts throughput/latency),
  • or batch too aggressively, causing memory stress and potential cache churn (harms latency, reduces overall efficiency),
  • and in multi-request settings, poor choices can even amplify starvation risks.

Many scheduling policies (including ones you’ll see in popular inference frameworks) are evaluated assuming request arrivals follow a Poisson process with a constant rate. That assumption is mathematically convenient—but real usage isn’t. Human-driven applications create patterns like clustered arrivals and sudden spikes. The paper points out that prior trace-based studies show strong deviations from stationarity and memorylessness.

So the key question becomes: how do you keep efficient batching when the arrival rate is changing over time—and you don’t know the future?

Why WAIT Works (When Arrivals Are Known) and Where It Fails in Practice

The original WAIT algorithm is built around a queueing-theoretic view of LLM serving. It assumes requests are grouped into m types. Each type j has:
- a tokenized prompt length l_j (prefill tokens),
- and a total decode length determined by an expected output size l'_j.

A request of type j runs through:
- stage 0 for prefill,
- then stages 1..l'_j for decode iterations as tokens are generated.

WAIT uses a threshold rule. Roughly speaking: it keeps track of how many requests of a given type are waiting in each stage. It then only triggers a batched compute iteration for type j when the inventory crosses a threshold n_j. Conceptually, it’s like the scheduler is saying:

“Don’t run the GPU for type j until we have enough work buffered to justify it—so we maximize throughput without breaking memory constraints.”

Crucially, those thresholds are computed using assumptions about arrival rates—specifically, that λ_j is known and stable. In other words, WAIT can be optimal (or close to optimal) in the regime where the scheduling model matches reality.

But in real deployments, arrival rates shift. When traffic regimes change (bursts and lulls), the precomputed thresholds become “stale.” That can cause:
- premature batching during bursts,
- excess waiting during lulls,
- and overall performance drift away from the ideal WAIT.

So the failure mode isn’t that WAIT is “bad.” It’s that the world isn’t static, and the thresholds depend on knowing the right parameters at the right time.

Using MMPP-2 to Model Burstiness Like Real Services (Not Just Math-Friendly Poisson)

To evaluate schedulers under realistic variability, the paper models arrivals using MMPP-2. If that sounds intimidating, here’s the intuition:

• Imagine traffic can be in one of two hidden modes:
  • a low-load state with rate like 50 req/s,
  • a high-load state with a higher rate like 100, 175, or 250 req/s (depending on the experiment).
• The system randomly switches between these states, governed by a Markov chain.
• While in a state, arrivals follow a Poisson process with that state’s rate.

That gives you burstiness with temporal correlation: you don’t just get “random noise,” you get sustained periods of high activity followed by lulls—exactly the kind of pattern interactive users produce.

The authors also emphasize an important evaluation fairness point: when comparing against simple Poisson traces, they ensure the time-averaged mean arrival rates match. That way, differences in scheduler performance can be attributed to burst structure, not just different overall traffic volume.

How the Modified WAIT Learns Traffic Rates Online (Without Needing Future Data)

Here’s the core contribution: a lightweight modification to WAIT that replaces fixed arrival rates with online estimated arrival rates.

Step 1: Smooth the observed interarrival times

At runtime, the scheduler observes arrival timestamps. For each request type j, it computes interarrival times and then estimates a local arrival rate.

Because raw interarrival timing is noisy (especially during bursts), the paper uses a smoothing pipeline:
- It averages the most recent w interarrival times in a window (window size w used as part of their estimation).
- Then it applies an Exponential Moving Average (EMA) to emphasize recent changes but keep longer trends.

They also add a Savitzky–Golay filter (a polynomial-based smoothing method) to preserve trends and peaks. The paper is careful to tune hyperparameters rather than guessing.

Step 2: Choose smoothing parameters via sensitivity analysis

They run estimation experiments using MMPP-2 scenarios with state arrival rates of:
- (50,100),
- (75,175),
- (100,250).

They evaluate estimation quality using:
- MAE (Mean Absolute Error),
- MAPE (Mean Absolute Percentage Error).

Across these settings, the paper reports the best-performing configuration as:
- EMA smoothing factor α = 0.05,
- Savitzky–Golay window length = 151,
- polynomial order = 2,
- moving-average window = 5.

With that setup, they report:
- average MAE = 15.39,
- average MAPE = 14.37%,
- maximum MAE = 17.78,
- maximum MAPE = 16.13%.

That’s the “confidence” layer: the rate estimator is not perfect, but it’s good enough to drive scheduler decisions.

Step 3: Update WAIT thresholds dynamically based on the estimated rate

In the original WAIT, thresholds n_j depend inversely on the (assumed known) arrival rate λ_j. In the modified version, they replace λ_j with a time-varying estimate \hat{λ}_t.

Interpretation:
- during surges (higher estimated rate), thresholds decrease, so the scheduler forms batches faster,
- during lulls (lower estimated rate), thresholds increase, avoiding wasteful batching and better preserving stable decode cadence.

Multi-type extension

If you have multiple request types, the authors estimate arrival rates independently per type, maintaining:
- a separate inventory counter,
- a separate adaptive threshold n_j(t),
- and a feedback loop per type.

So the system can flex across heterogeneous traffic (e.g., short prompts vs long prompts, different expected decode lengths).

What They Compared in Experiments (and What “Good” Looks Like)

To keep evaluation grounded, the paper simulates an NVIDIA A100 GPU using Microsoft Vidur. They compare against:
- vLLM,
- ORCA,
- Sarathi,
- plus WAIT in two versions:
1. the original WAIT with knowledge of the full arrival trace (idealized baseline),
2. the modified WAIT using online estimation.

They also enforce a fair constraint: the same batch size limit across algorithms.

The scenario split: demand level × burst transition speed

They test four workload regimes:
- Low Demand, Low Shift (LDLS)
- Low Demand, High Shift (LDHS)
- High Demand, Low Shift (HDLS)
- High Demand, High Shift (HDHS)

Where:
- Low/High Demand controls the baseline arrival rates,
- Low/High Shift controls how quickly MMPP transitions between low and high traffic states.

That distinction matters because scheduling becomes harder when bursts change rapidly.

Main Results: Modified WAIT Tracks Ideal Throughput and Often Improves Latency

Across their figures and reported conclusions, the pattern is consistent:

1. Throughput: The modified WAIT performs close to the ideal original WAIT (the one that assumes knowledge of arrivals). It also beats Sarathi and vLLM especially in Low Shift burst conditions.
2. Latency: In many cases, modified WAIT is comparable to original WAIT for latency, and in some high-demand cases it even surpasses original WAIT.

The authors summarize the key empirical findings like this:
- In Low Shift scenarios, modified WAIT achieves higher throughput than Sarathi, ORCA, and vLLM while keeping latency similar.
- Under High Shift scenarios, both original and modified WAIT need further improvements for latency; burst regime changes happen quickly enough that scheduling can’t perfectly match the “fluid dynamics” assumptions.

Since the paper’s text emphasizes that WAIT and modified WAIT align closely on throughput, the practical takeaway is that online adaptation doesn’t ruin the batching efficiency—it mainly protects you from the “stale threshold” problem.

To make the comparison feel concrete, here’s the high-level outcome the paper reports (not exact numeric values, since they’re shown in figures):

For production folks, this is a useful message: if your traffic bursts last long enough (common in many real apps, especially around events or user sessions), this approach should noticeably stabilize throughput.

Key Takeaways

• The problem isn’t just batching—it’s batching with the wrong arrival assumptions. Fixed-rate scheduling can drift badly under bursty, non-stationary traffic.
• The paper modifies WAIT with an online arrival rate estimator so thresholds adapt continuously instead of relying on precomputed (and stale) parameters.
• MMPP-2 provides a practical way to test burstiness with two hidden traffic modes, capturing sustained bursts and lulls.
• The best estimation configuration reports average MAE = 15.39 and average MAPE = 14.37% using α = 0.05, Savitzky–Golay window 151, polynomial order 2, and moving window 5.
• In simulations on A100 via Vidur, the modified WAIT achieves:
  • throughput close to ideal WAIT (with full arrival knowledge),
  • better throughput than Sarathi and vLLM in Low Shift burst conditions,
  • latency often comparable, with some cases where modified WAIT improves on the original WAIT.
• Future directions include better state-rate estimation (e.g., EMA + changepoint detection) and validating on real prompt/response traces, plus possibly predicting request types at arrival time.