Vol. XXIII · Serving Plate 4 of 9continuous batching, iteration-level scheduling, static batching, Orca, throughput, time to first token, queueingCE

Continuous Batching.

Admit new requests at every step, not when the whole batch is done.

Decode needs many sequences in each forward pass to use the GPU’s arithmetic (plate XXIII.1). The obvious way to get them is static batching: collect requests, run them together until every one has finished, then start the next batch. But answers differ in length; a batch runs as long as its longest answer, finished sequences sit idle in it, and new requests wait for the whole batch.

Continuous batching — iteration-level scheduling, introduced by the Orca server of Yu and colleagues (2022) — makes the scheduling decision at every decode step: finished sequences leave immediately, waiting requests are prefilled and join the running batch. The workshop serves Llama 3 8B on one H100 under both policies as the request rate rises.

Below: left, median time to first token against the request rate for both policies; right, throughput in output tokens per second. Readouts are at the chosen rate.

What you will learn

Contrast static and continuous batching.
Explain head-of-line blocking.
Measure latency and throughput under load.
Name iteration-level scheduling.

Workshop

Simulated: Llama 3 8B in BF16 on one H100, Poisson arrivals, prompt and output lengths exponential with means 1 024 and 256, paged cache, up to 256 sequences at once. Static: a new batch starts only when every sequence of the last has finished. Times are roofline estimates from the H100’s published specifications (989 TFLOP/s dense BF16, 3.35 TB/s), assuming 60% of peak compute and 80% of peak bandwidth are reached plus 0.2 ms per pass — not measurements.

Never wait for the longest answer

At 8 requests a second, static batching makes a new request wait 8.11 s at the median for its first token — it must wait for the running batch’s longest answer — while continuous batching admits it within 0.027 s. Throughput separates more slowly: at 16 requests a second static batching delivers 2,516 output tokens a second against 3,469, because sequences that finish early leave their slots idle until the batch ends.

Continuous batching is now universal in LLM serving: vLLM, SGLang, TensorRT-LLM and the services built on them all schedule at every step. It brings a new interference, visible in the time per token: each admission adds a prefill to the step, so running users see a stall whenever a long prompt joins. The remedies are to split long prefills into chunks mixed with decode steps (chunked prefill), or to run prefill on separate machines (plate XXIII.7).

Static batching remains right where all sequences have the same length and arrive together — offline scoring of a fixed dataset, for example.

Terms

Static batching: Running a batch until its last sequence finishes before starting another.
Continuous batching: Admitting and retiring sequences at every decode step.
Head-of-line blocking: New work waiting behind the slowest item in front of it.
Chunked prefill: Splitting a long prompt’s prefill into pieces mixed with decode steps.

Continuous batching schedules at every step, so a new request never waits for the longest answer in front of it.

Sources

Yu, Jeong, Kim, Kim and Chun, “Orca: A Distributed Serving System for Transformer-Based Generative Models”, OSDI 2022.
Kwon et al., SOSP 2023.