Continuous batching

Continuous batching (Orca, OSDI 2022) reschedules after every decode step: finished sequences leave at once and queued ones take their slots, so the GPU never decodes padding. Orca reported 36.9× FasterTransformer's throughput at equal latency.

7 min read818 wordsadvanced0 viewsupdated 2026-10-21

Definition

Continuous batching (iteration-level scheduling; NVIDIA TensorRT-LLM calls it in-flight batching) is a way of serving autoregressive models in which the scheduler forms a new batch before every forward pass. A sequence leaves the batch as soon as it emits its end token, and a waiting request joins at the next iteration. It was introduced by Orca (Yu, Jeong, Kim, Kim and Chun, "Orca: A Distributed Serving System for Transformer-Based Generative Models", OSDI 2022). The name "continuous batching" spread with Hugging Face TGI and vLLM in 2023.

A language model generates one token per forward pass, and requests need very different numbers of passes: a yes/no answer needs 2, an essay 800. Classic model servers batch at the request level. They collect up to BB requests, run them together, and return when the batch is done. That suits image classifiers, where every input costs one pass. For generation it fails twice: short requests sit in finished slots until the longest one ends, and new arrivals wait for the whole batch to drain.

Batching itself is what makes decoding cheap. Each decode step reads every weight from GPU memory once, whether the batch holds 1 sequence or 64, and the matrix units are mostly idle at batch 1 (see KV cache). So the goal is to keep every slot busy with a real sequence at every step. Continuous batching is the scheduler that does this. Every serving engine covered in Inference servers (vLLM, TGI) uses it.

The waste in request-level batching

Ustatic=∑i=1BniB⋅max⁡ini,Tbatch=∑k=1max⁡init(B)U_\text{static}=\frac{\sum_{i=1}^{B} n_i}{B\cdot\max_i n_i},\qquad T_\text{batch}=\sum_{k=1}^{\max_i n_i} t(B)
nin_i
output tokens of request i in the batch
UstaticU_\text{static}
share of slot-steps that produce a real token; the rest is padding
t(B)t(B)
time of one decode iteration at batch size B; padded slots still cost compute

With outputs of 4, 9, 6 and 3 tokens, Ustatic=22/36=61%U_\text{static}=22/36=61\%. Output lengths in chat traffic are long-tailed, so one long answer per batch is enough to idle most slots. Every request in the batch also gets its response at TbatchT_\text{batch}, the time of the longest one.

Scheduling every iteration

  1. 1Before each forward pass, drop sequences that emitted an end token or hit their length limit, and return their responses.
  2. 2Fill the free slots from the queue (first come, first served), as far as the slot limit and free KV cache memory allow.
  3. 3Run one pass over the whole batch. Newly admitted requests run their prefill (the full prompt) in this pass. Running ones decode one token each.
  4. 4Append each new token to its sequence (and stream it to the client), then go back to step 1.
4 slots · output tokens R1 4, R2 9, R3 6, R4 3, R5 5, R6 4 (31 in all)R1–R4 arrive before iteration 1, R5 during iteration 2, R6 during iteration 31234567891011121314iterstatic (request-level): the batch ends when its longest member endsslot 0slot 1slot 2slot 3R1eosR2eosR3eosR4eosR5eosR6eos14 iterations · 31 / 56 slot-steps busy (55%) · R5, R6 wait until iteration 10continuous (iteration-level): a freed slot is refilled next iterationslot 0slot 1slot 2slot 3R1eosR2eosR3eosR4eosR5eosR6eos9 iterations · 31 / 36 slot-steps busy (86%) · R5 starts at 4, R6 at 5R1 eos → R6 joins at 5R3 eos → slot idlesR4 eos → R5 joins at 4prefill + first tokenone decode tokenfinished, slot held, response not sentOrca (OSDI 2022): the scheduler is called once per iteration, not once per request;linear layers run on all batch tokens stacked, attention per sequence (selective batching)
fig.Six requests on four slots, in iterations. Static: R1–R4 run until R2's ninth token, so slots 0, 2 and 3 hold finished sequences (dashed) for 5, 3 and 6 iterations. R5 and R6 wait until iteration 10, and the whole job takes 14 iterations with 31 of 56 slot-steps busy (55%). Continuous: R5 takes R4's slot at iteration 4 and R6 takes R1's at iteration 5. All six finish in 9 iterations, with 31 of 36 slot-steps busy (86%).

Ragged batches are the hard part to implement. The sequences in one iteration have different lengths, and new ones bring whole prompts. Orca's selective batching stacks all tokens of the iteration into one [∑iℓi, d][\sum_i \ell_i,\ d] matrix for the QKV projections and MLPs, which do not care which sequence a token belongs to. It splits them only for attention, which runs per sequence over that sequence's own keys and values. Modern engines go further with variable-length attention kernels over a paged cache (see PagedAttention), so no padding is ever materialised.

Prefill gets in the way

titer≈tw+b tseq+cpre∑j∈newpjt_\text{iter}\approx t_w + b\,t_\text{seq} + c_\text{pre}\sum_{j\in\text{new}} p_j
twt_w
fixed cost of reading the weights once per iteration (memory-bound)
b tseqb\,t_\text{seq}
per-sequence cost: reading its KV cache and its share of compute
cpre∑pjc_\text{pre}\sum p_j
prefill of the prompts admitted this iteration (compute-bound)

A 4,000-token prompt joining the batch makes that iteration many times slower than a pure decode step, so every running sequence sees a gap between two tokens. Chunked prefill caps the tokens per iteration (vLLM's max_num_batched_tokens) and spreads a long prompt over several iterations, mixed with decodes. Sarathi-Serve (Agrawal et al., OSDI 2024) and DeepSpeed-FastGen's Dynamic SplitFuse (2023) build on this. Disaggregated serving (DistServe, Splitwise, 2024) instead runs prefill and decode on separate GPUs.

Reported results and engine behaviour

Orca (OSDI 2022)
36.9× the throughput of NVIDIA FasterTransformer at the same latency, on GPT-3 175B; FasterTransformer batched per request
vLLM (SOSP 2023)
2–4× the throughput of FasterTransformer and Orca at the same latency; the gain comes from fitting more sequences per batch with paged KV memory, on top of iteration-level scheduling
Hugging Face TGI
the Rust router batches continuously; --max-batch-total-tokens caps the tokens (prompt + generated) held by one batch
vLLM
--max-num-seqs caps sequences per iteration; --max-num-batched-tokens caps tokens per iteration, which bounds the prefill cost
TensorRT-LLM
in-flight batching in the C++ batch manager, the same idea under another name
continuous: free slots refilled every iteration · 8 slots · 8 req/siteration = 12 + 0.25·batch ms, + 0.04 ms per prefilled prompt tokenarriveslot 0slot 1slot 2slot 3slot 4slot 5slot 6slot 70s2s4s6s8s10s12s14ssolid = generating · dashed = finished, slot held (padding)32 requests, 3427 output tokensstaticcontinuouscont ÷ staticall 32 done at15.73 s8.55 s0.54×throughput217.9 tok/s400.7 tok/s1.84×mean latency7.41 s2.32 s0.31×mean queue wait4.34 s0.77 s0.18×busy slot-steps39.2%75.3%1.92×
scheduler
fig.32 requests (3,427 output tokens, prompts of 40–399 tokens) with Poisson arrivals and a toy cost of 12 + 0.25·b ms per iteration plus 0.04 ms per prefilled token. Defaults (8 slots, 8 req/s): static batching finishes at 15.73 s with 217.9 tok/s, a mean latency of 7.41 s and 39.2% of slot-steps busy. Continuous finishes at 8.55 s with 400.7 tok/s (1.84×), a latency of 2.32 s and 75.3% busy. With 16 slots it reaches 471.5 tok/s against 265.3, and queue wait falls to 8 ms. At 2 req/s throughput is limited by arrivals (166.8 vs 183.8 tok/s), but latency still drops from 4.22 s to 1.42 s.

The figure shows the two regimes. Under light load the server is idle part of the time, so continuous batching mostly cuts latency: nobody waits for someone else's long answer. Under heavy load it raises throughput, because the slots stay full. At 4 slots and 8 req/s the continuous scheduler is 94.4% busy and the queue wait grows to 3.15 s. Then the only fix is more slots, which means more KV memory.

Worked example: the diagram, timed

MeasureStaticContinuous
Iterations9 at b = 4, then 5 at b = 2 (14)6 at b = 4, 2 at b = 3, 1 at b = 1 (9)
Time9·13 + 5·12.5 = 179.5 ms6·13 + 2·12.75 + 12.25 = 115.75 ms
Throughput31 / 0.1795 s = 172.7 tok/s31 / 0.11575 s = 267.8 tok/s
Busy slot-steps31 / 56 = 55.4%31 / 36 = 86.1%
R5 first tokeniteration 10iteration 4
The six requests of the diagram, with t(b) = 12 + 0.25·b ms per iteration (prefill cost ignored).
python
1from collections import deque
2
3# (name, arrival iteration, output tokens) as in the diagram
4reqs = [("R1", 1, 4), ("R2", 1, 9), ("R3", 1, 6), ("R4", 1, 3), ("R5", 2, 5), ("R6", 3, 4)]
5B = 4 # max sequences per iteration
6
7def serve(reqs, B):
8 pending, queue, running = deque(reqs), deque(), {}
9 it = 0
10 while pending or queue or running:
11 it += 1
12 while pending and pending[0][1] <= it: # arrivals
13 queue.append(pending.popleft())
14 while queue and len(running) < B: # refill free slots
15 name, _, n_out = queue.popleft()
16 running[name] = [0, n_out, it] # prefill runs in this pass
17 for name in list(running): # one forward pass
18 st = running[name]
19 st[0] += 1 # one new token each
20 if st[0] == st[1]: # eos: leave immediately
21 print(f"{name}: iterations {st[2]}-{it}")
22 del running[name]
23 return it
24
25print("total iterations:", serve(reqs, B)) # 9 (static batching: 14)
An iteration-level scheduler loop over the diagram's six requests (runs as is; the model call is replaced by a token counter)

Use when

  • +No padding steps: throughput rises with load until KV memory or compute saturates.
  • +Short requests return as soon as they finish, so latency tracks each request's own length.
  • +New requests start at the next iteration instead of after the current batch.

Avoid when

  • −Needs per-sequence KV state, ragged-batch kernels and a scheduler inside the generation loop.
  • −Prefills mixed into decode steps cause token-latency spikes unless prefill is chunked.
  • −Admitting greedily can overcommit memory and force preemption.

Check yourself

A static batch holds four requests that generate 10, 10, 10 and 200 tokens. What share of its slot-steps produce real tokens?

Check yourself

Under continuous batching, why does a long new prompt slow down the other users' streams?

Remember

  • ✓Schedule per iteration, not per request: finished sequences leave immediately, waiting ones join at the next forward pass.
  • ✓Request-level batching wastes 1−∑ni/(Bmax⁡ni)1-\sum n_i/(B\max n_i) of its slot-steps and returns every response at the time of the longest one.
  • ✓Selective batching: linear layers run on all tokens stacked; attention runs per sequence (now via variable-length, paged kernels).
  • ✓Light load: mainly lower latency. Heavy load: higher throughput, until KV memory limits the slots.
  • ✓Prefill in a decode batch stalls everyone; chunked prefill and prefill/decode disaggregation address it.
← back to Generative AI roadmap