Section 14

Continuous batching

Stop wasting GPU steps

Sources: Orca: A Distributed Serving System for Transformer-Based Generative Models — Yu et al., 2022; vLLM documentation

The previous section established that a single request can use only a small fraction of the GPU’s arithmetic capacity during decode. The fix is obvious: run many requests at once, so a single read of the weights serves many tokens. A group of requests processed together is a batchbatchThe group of training examples used for one gradient estimate. Bigger batches reduce gradient noise but use more memory and compute per step.See in glossary →. The interesting question is: how do you assemble those batches?

There’s a naive answer and a much better answer. They are far enough apart in throughput that the better one (continuous batchingcontinuous batchingA scheduler that swaps finished requests out and queued requests in at every decode step instead of waiting for the whole batch to finish.See in glossary →) basically defines the difference between “a personal-use server” and “a production-grade inference engine.”

Static batching: the naive answer

The simplest scheme: take the first N requests in the queue, run them all through the model together, wait for all of them to finish, then take the next N. This is called static batching.

Static batching has two problems, both severe:

  1. Slow requests stall the batch. If your batch contains one request that wants 8 tokens of output and three that want 200, the 8-token request finishes after step 8, and then its GPU slot sits idle for the next 192 steps waiting for the others. The GPU is doing 192 × (3/4 useful work) instead of 192 × (4/4 useful work).

  2. New arrivals wait for the next batch. A request that shows up while the batch is mid-flight has to wait for the entire batch to drain before it gets to start. At a load of 100 requests in flight with average output length 200 tokens, the worst-case TTFT is terrible.

Production systems used to ship with this. People complained.

Continuous batching: drop in, drop out, every step

The iteration-level scheduling idea was demonstrated by the Orca paper and became widely used in systems such as vLLM. It makes the batch dynamic at decode steps:

  • At every decode step, check which requests have finished (hit EOS or max length).
  • Evict the finished requests from the batch.
  • Admit waiting requests into the now-empty slots.
  • Run the next decode step with the new batch composition.

Many serving engines can also mix prefill and decode in one step. A new request needs prefill (a long sequence of new tokens) while old requests need decode (one new token each). With suitable batch construction and attention kernels, both can share a forward pass; the exact policy is configuration- and version-dependent. vLLM supports this style of mixed scheduling through chunked prefill.

Try it

Below is a simplified Gantt chart: 4 GPU slots running 8 requests with different output lengths and arrival times. Toggle between static and continuous to see what changes.

Static batching vs continuous batching
Same 8 requests with different completion lengths and arrival times. Toggle the mode and watch the idle (gray) area shrink.
slot
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#0
1
1
1
1
1
1
1
1
6
6
6
6
6
8
8
8
8
8
8
8
#1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
#2
3
3
3
3
5
5
5
5
5
5
5
5
5
5
#3
4
4
4
4
4
4
7
7
7
7
7
7
7
7
7
← decode step
GPU utilization
67.7%
Idle decode slots
31 / 96
Continuous batching replaces finished requests immediately at every decode step. Idle gaps disappear. This is the single biggest serving-system win since the original Transformer — and the foundation for everything in §15+.

Notice in static batching how much “gray” idle area accumulates: those are decode steps that were paid for in HBM traffic but produced nothing. Continuous batching squeezes most of that gray out.

The role of the scheduler

A schedulerschedulerThe component that picks which requests run in the next forward pass given GPU memory and policy constraints.See in glossary → is the component that decides, every step, which requests to run. A simplified vLLM-style scheduler maintains two main states:

  • WAITING: requests that arrived but haven’t started prefill yet.
  • RUNNING: requests currently being decoded (or partially prefilled in a chunked-prefill setup).

At each step:

  1. Compute the available KV cache budget (how many free pages remain).
  2. Try to admit waiting requests until the budget is exhausted or a policy says stop.
  3. If memory is tight, preempt some RUNNING requests, potentially recomputing their KV later or moving cache state to another tier, depending on the serving engine and configuration.
  4. Build the per-step batch from the surviving RUNNING set + admitted prefills.

There are several knobs here:

  • Policy: FCFS (first-come-first-served), priority, fairness.
  • Max batch size: a hard upper bound to keep latency bounded.
  • Max KV memory utilization: the fraction of HBM the cache pool can take.
  • Chunked prefill (§17): split a single huge prefill across multiple steps to avoid blocking decoders.

The scheduler is one component used to pursue SLOs. If a service promises p99 TTFT < 1 s, it can combine scheduler settings with admission control, priorities, capacity provisioning, and load shedding to manage that target. No scheduler configuration can guarantee an SLO once demand exceeds available capacity.

Why batching alone isn’t enough

Continuous batching gets you most of the GPU back. But there’s still a subtle problem: the KV cache itself is contiguous in memory per-request. When a request finishes and its slot is reused for a new request, what happens to the old request’s KV? When the new request grows, what happens if it needs more memory than the old request’s old slot? You end up either pre-reserving enormous contiguous chunks (wasting memory) or moving things around (wasting time).

This is the problem vLLM’s signature contribution (PagedAttention) was introduced to solve. That’s the next section.