Serving an LLM meant choosing between throughput-killing batch decay (batches shrink as queries finish early) and latency-killing prefill intrusions (ORCA-style batching slots orders-of-magnitude-heavier encodings into decode steps) — ExeGPT decouples the two phases in time or in space, exposes four control knobs that are near-provably monotonic in throughput and latency, and branch-and-bounds over a distribution-driven simulator to find the schedule maximizing throughput under an explicit latency bound, averaging 2.9× (up to 15.2×) over FasterTransformer.
The argument in one glance
-
Problem
LLM inference is irregular in two directions at once
Generating text is autoregressive: one forward pass per token, each fed the last. Batch many queries together and the irregularity bites twice. Across ITERATIONS: queries finish at different lengths, so a batch of 128 dwindles to a handful — hardware runs at the pace of a shrinking batch. Across PHASES: encoding a whole prompt (prefill) costs orders of magnitude more compute than decoding one token, yet both must share the same GPUs. Meanwhile, a translation API and an offline summarizer have utterly different latency requirements — and both deserve maximal throughput within theirs.
-
What people did
Fixed batches, or continuously refilled ones
NVIDIA's FasterTransformer and DeepSpeed Inference keep batch sizes fixed through decoding — computing dead work for finished queries, or terminating them early and eating the shrinkage. ORCA's celebrated iteration-level scheduling (adopted by vLLM) refills instead: when a query completes, a NEW query's encoding slots into the running batch, keeping it full forever.
-
Why it fell short
Refilling ignores that prefill is a different animal
ORCA's substitution treats an encoding and a decoding as interchangeable batch slots — but encoding a prompt costs orders of magnitude more than one decode step. The result: pipeline bubbles wherever a heavyweight encoding lands mid-decode, and worse, UNCONTROLLABLE latency — any decode iteration might suddenly carry someone else's prefill, so ongoing queries stall unpredictably and no latency bound can be promised. And across all systems, the only latency/throughput dial is batch size — a blunt instrument that can crater throughput in the wrong parallel configuration.
-
This paper's idea
Decouple the phases; schedule with math, not folklore
ExeGPT breaks the assumption that a query's decode must immediately follow its encode on the same GPUs. Round-Robin Allocation (RRA) separates phases in TIME — encode a big batch once, decode N iterations, repeat; Workload-Aware Allocation (WAA) separates them in SPACE — some GPUs only encode, others only decode, asynchronously pipelined. Four control knobs (batch size, decoder micro-batches, PARTIAL tensor parallelism, encoding frequency) are designed to be monotonic in both throughput and latency — so a branch-and-bound search over a simulator driven by the workload's sequence-length distributions finds the throughput-maximal schedule under any latency bound in seconds to minutes. Versus FasterTransformer: 2.9× average, up to 15.2× throughput or 6× latency.
Why this problem is worth solving
By 2024, serving cost had become the practical ceiling on what
LLMs get used for, and the field had converged on a handful of
system tricks — KV caching,
ORCA’s iteration-level scheduling,
now industry standard via vLLM: instead of waiting for a whole
batch to finish, completed queries are replaced by new ones at
iteration granularity, keeping the batch full and enabling early
termination without shrinkage
The deeper obstacle is structural. A transformer’s
the two phases of generation:
prefill (encoding) processes the whole prompt in one heavily
parallel pass; decode generates one token per iteration,
reusing cached keys/values. Per invocation, prefill is orders
of magnitude more compute than a decode step — yet classic
systems interleave them freely on the same GPUs
What people did before, and where it broke
- FasterTransformer (the baseline that still won). NVIDIA’s engine with tensor and pipeline parallelism. Fixed decode batches: no early termination, so finished queries burn compute as padding until the batch’s longest query completes. Yet in the paper’s measurements it still outperformed DSI, ORCA-mode, and vLLM on their shared setting — a reminder that low-level engineering (CUDA, not Python, in the loop) still dominates.
- DeepSpeed Inference. Adds kernel-level optimizations and hybrid micro-batching (more micro-batches for prefill, fewer for decode — a trick FT later adopted). Same fixed-batch decay problem.
- ORCA / vLLM iteration mode. Continuous batching solves decay but prices encode and decode slots identically. Because a prefill is orders of magnitude heavier, batches carrying one stall the pipeline (bubbles) and any query’s latency depends on whether strangers’ prefills land in its decode path — uncontrollable under an SLA. (vLLM’s paging is orthogonal and complementary; its Python-side overhead also cost it against FT in these tests.)
- The universal blunt knob. All of them trade latency against throughput only via batch size — which interacts badly with parallel configuration and leaves enormous scheduling headroom unexplored: where to put encoders vs decoders, how often to encode, how deep to pipeline, how wide to tensor-parallelize.
How ExeGPT works
ExeGPT's four components and two strategies
-
XProfiler (once per model + cluster)
Measures single-layer encode/decode execution times across all feasible tensor-parallel degrees, batch sizes, and sequence lengths, plus tensor/pipeline synchronization overheads. Under two hours, one time.
-
Sequence distributions in, schedules out new
The workload is characterized by input- and output-length DISTRIBUTIONS (observed from the service over time; truncated normals fit real NLP datasets best). A probabilistic analysis computes how many queries complete at each decode iteration — which pins consistent encode/decode batch sizes and lets XSimulator construct accurate execution timelines for any candidate configuration.
-
Strategy 1 — RRA: decouple in time new
GPUs hold encoders and decoders round-robin. Execution alternates: encode one batch, then decode N_D iterations, repeat — refilling the decode pool in bulk, at a chosen frequency, instead of query-by-query. Encoding batch size is set to the expected number of completions per cycle, keeping batches statistically constant. More frequent encoding = fuller batches = more throughput, at latency cost.
-
Strategy 2 — WAA: decouple in space new
Some GPUs ONLY encode; others ONLY decode, allocated proportionally to measured compute (WAA-C) or memory (WAA-M), running asynchronously as a two-stage pipeline with KV caches shipped from encode to decode GPUs via CPU memory. Decoder-only models need the weights resident on both groups — a real memory tax (18–29%) that shapes when WAA wins.
-
Four monotonic knobs + branch-and-bound new
Batch size, decoder micro-batch count, PARTIAL tensor parallelism (apply TP to only a subset of pipeline GPUs — shrinking pipeline depth for latency at sync-overhead cost), and encoding frequency. Each is monotonic in throughput and latency (97%/96% of measured points within 5% tolerance), so a branch-and-bound search prunes the configuration space with certainty, finding the optimum in 3 seconds–5 minutes where exhaustive search needs 5 hours–a day. Run for RRA and WAA; take the better.
-
XRunner: enforcement on FasterTransformer new
Extends FT with early termination + KV-cache compaction, encode→decode cache transfer, computation/communication overlap, and dynamic runtime batch adjustment that holds workload within a threshold of the average (decoder-stage execution variance ends up under 6%). Distribution drift triggers re-scheduling; re-deploying weights from CPU DRAM takes 0.9–3.5 s.
The idea
Break the encode-then-immediately-decode weld. Every prior system implicitly guaranteed that the GPUs encoding query Q decode it, right away. ExeGPT’s two strategies each break the weld differently, and the difference is instructive. RRA keeps the hardware allocation but batches phase transitions in time: refill the decode pool every N_D iterations in bulk, so prefill’s weight lands in scheduled, bounded slots instead of ambushing random decode iterations — latency becomes predictable and the decode batch stays statistically full. WAA goes further and splits space: dedicated encode GPUs and decode GPUs sized by measured workload, running as an asynchronous two-stage pipeline. Each choice has a characteristic tax — RRA tolerates small bubbles between phases; WAA pays weight duplication (decoder-only models keep the model on both GPU groups) and KV shipping — which is why neither dominates: WAA wins short-output tasks (its bubbles stay small and its memory tax is low), RRA wins long outputs and giant models (WAA could not even run at 175B/341B).
Design the knobs so the search is trivial, then search exactly. The scheduling literature usually meets a messy configuration space with black-box autotuning. ExeGPT instead engineers the space to be searchable: all four control variables are constructed to move throughput and latency monotonically (increasing batch size raises both; more decoder micro-batches cuts latency and throughput; extending partial tensor parallelism to more GPUs shortens the pipeline; encoding more often fills batches). Monotonicity is then verified empirically — 97% of throughput points and 96% of latency points behave within a 5% tolerance, with the exceptions mapped and handled (partial TP’s degree is fixed per search pass to preserve the property). The payoff is a branch-and-bound that prunes with certainty instead of sampling with hope: optimal schedules in seconds to minutes, fast enough to re-run whenever the workload drifts.
Schedule the distribution, not the query. ExeGPT never knows any query’s output length — it knows the service’s length distributions, observable from history. The probabilistic analysis (probability a query completes at iteration U) converts those distributions into expected batch compositions, which is exactly what consistent scheduling needs: encode-batch sizes matched to expected completions, decode batches statistically constant, simulated timelines that match reality (decode-stage variance under 6% at runtime). The same machinery makes the system honest about its dependence: the drift study quantifies precisely how much latency margin a given mis-estimate costs (a 15% growth in mean output length needs ~10–13% tighter scheduling margins), and RRA can absorb drift by adjusting only its encoding frequency, no re-deployment needed.
Standing up a translation service under an SLA
From latency bound to running schedule with ExeGPT
L_B = latency bound (for generating a 99th-percentile-length sequence). B_E/B_D = encode/decode batch sizes. N_D = decode iterations between encodes (RRA's encoding frequency). Partial TP = tensor parallelism applied to a subset of pipeline GPUs. Numbers from the paper's OPT-13B/GPT-3 case studies and drift analysis.
Step 1 of 7
Profile once, keep forever
XProfiler sweeps single encode/decode layers across tensor-parallel degrees, batch sizes, and sequence lengths on the target cluster — under two hours, once per model+hardware pair. Every later scheduling decision is arithmetic over these measurements; no more full-system trial runs.
layer times + sync overheads = the simulator's vocabulary amortized across every schedule ever computed
Why it works
- Prefill and decode differ by orders of magnitude per invocation → any scheduler that prices them as equal batch slots (ORCA) must suffer bubbles and latency noise → phase decoupling in time (RRA) or space (WAA) lets each phase run at its own batch size, cadence, and GPU allocation.
- Query completions are individually unpredictable but statistically stable → distribution-driven scheduling sets encode batches to expected completions → decode batches stay full WITHOUT per-query refill, so early termination stops costing throughput and latency stays bounded.
- Each knob was designed so more of it moves throughput and latency in one known direction → the optimization problem is monotonic → branch-and-bound prunes exactly rather than sampling blindly, making optimal scheduling cheap enough to re-run on drift.
- The two strategies have complementary tax structures — RRA pays small inter-phase bubbles, WAA pays weight duplication and KV shipping → running the solver on both and taking the max covers short-output and long-output tasks, small and 341B-parameter models, with the same machinery.
- All scheduling intelligence sits above a C++/CUDA execution engine (extended FasterTransformer) → the gains stack on the strongest baseline rather than a strawman — the paper first shows FT beating DSI, ORCA-mode, and vLLM in its setting.
What it costs
- Distribution dependence. Schedules are only optimal for the distributions they were computed from; mis-specified means require explicit latency margins, and cold-start services without history must bootstrap conservatively. The drift analysis quantifies but does not eliminate this.
- WAA’s memory bill. Decoder-only models hold weights on both encode and decode GPUs (18–29% extra model memory) plus KV-cache transfer through CPU — enough that WAA simply cannot run at 175B/341B scale, ceding those regimes to RRA.
- Scheduling granularity, not request granularity. ExeGPT optimizes a steady-state schedule for a workload; it does not make per-request admission or preemption decisions, and bursty or multi-tenant traffic beyond the modeled distribution is out of scope.
- A 2024-vintage baseline set. Comparisons run against FasterTransformer-era systems, with ORCA emulated via vLLM’s iteration mode; the serving landscape (disaggregated prefill clusters, chunked prefill, speculative decoding) has since moved — largely in directions this paper’s decoupling argument anticipated.
- Synthetic-length methodology. Most experiments enforce sampled sequence lengths (suppressing end-of-sequence, as ORCA’s evaluation did); real-dataset runs (where ExeGPT’s margin actually GROWS to 4.4× because real tails are longer) cover a subset.
The evaluation
Six model instances (T5 11B; OPT 13B/101B; GPT-3 39B/175B/341B) on 48 A40s and 16 A100s; five tasks (summarization, translation, code generation, two conversational Q/A profiles) × four latency bounds each — twenty scenarios. The headline: 2.9× average throughput over FasterTransformer, up to 15.2× (tightest bound, GPT-3 175B, code generation) — or, equivalently, up to 6× lower latency at matched throughput. Real-dataset runs (WMT, Alpaca, CNN/DailyMail) widen the margin to 4.4× average, because real length distributions have the long tails that make batch decay worst.
LLM serving schedulers, by how they handle the two irregularities
| Property | FasterTransformer / DeepSpeed Inference | ORCA-style continuous batching (vLLM iteration mode) | ExeGPT (RRA / WAA) |
|---|---|---|---|
| Decode batch over time | |||
| Where prefill runs | Interleaved with decode on the same GPUs, same configuration | ||
| Latency control | |||
| Measured standing | |||
| Regime coverage | One configuration fits all tasks | One policy fits all tasks |
Check yourself
Check your understanding
1. ORCA's continuous batching — replacing each completed query with a new one mid-batch — was the celebrated fix for batch decay. Predict the TWO problems ExeGPT identifies with it.
2. Neither of ExeGPT's strategies dominates: WAA wins some workloads, RRA others. What determines the winner?
3. ExeGPT finds optimal schedules with branch-and-bound in seconds to minutes, where exhaustive search needs hours to a day. What property makes exact pruning valid, and where does it come from?
4. ExeGPT schedules from sequence-length DISTRIBUTIONS rather than per-query knowledge. What does this buy, and what is the measured cost when the distribution estimate is wrong?