# 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.

Source: https://www.mlfoundry.in/learn/continuous-batching  
Section: Generative AI › Serving Generative Models  
Level: advanced · 7 min read · updated 2026-10-21

**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 $B$ 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

$$
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)
$$

- $n_i$: output tokens of request i in the batch
- $U_\text{static}$: share of slot-steps that produce a real token; the rest is padding
- $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, $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 $T_\text{batch}$, the time of the longest one.

## Scheduling every iteration

1. Before each forward pass, drop sequences that emitted an end token or hit their length limit, and return their responses.
2. Fill the free slots from the queue (first come, first served), as far as the slot limit and free **KV cache** memory allow.
3. Run 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. Append each new token to its sequence (and stream it to the client), then go back to step 1.

> Figure: 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 $[\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

$$
t_\text{iter}\approx t_w + b\,t_\text{seq} + c_\text{pre}\sum_{j\in\text{new}} p_j
$$

- $t_w$: fixed cost of reading the weights once per iteration (memory-bound)
- $b\,t_\text{seq}$: per-sequence cost: reading its KV cache and its share of compute
- $c_\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

> Figure: 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

The six requests of the diagram, with t(b) = 12 + 0.25·b ms per iteration (prefill cost ignored).

| Measure | Static | Continuous |
| --- | --- | --- |
| Iterations | 9 at b = 4, then 5 at b = 2 (14) | 6 at b = 4, 2 at b = 3, 1 at b = 1 (9) |
| Time | 9·13 + 5·12.5 = 179.5 ms | 6·13 + 2·12.75 + 12.25 = 115.75 ms |
| Throughput | 31 / 0.1795 s = 172.7 tok/s | 31 / 0.11575 s = 267.8 tok/s |
| Busy slot-steps | 31 / 56 = 55.4% | 31 / 36 = 86.1% |
| R5 first token | iteration 10 | iteration 4 |

```python
from collections import deque

# (name, arrival iteration, output tokens) as in the diagram
reqs = [("R1", 1, 4), ("R2", 1, 9), ("R3", 1, 6), ("R4", 1, 3), ("R5", 2, 5), ("R6", 3, 4)]
B = 4                                     # max sequences per iteration

def serve(reqs, B):
    pending, queue, running = deque(reqs), deque(), {}
    it = 0
    while pending or queue or running:
        it += 1
        while pending and pending[0][1] <= it:           # arrivals
            queue.append(pending.popleft())
        while queue and len(running) < B:                # refill free slots
            name, _, n_out = queue.popleft()
            running[name] = [0, n_out, it]               # prefill runs in this pass
        for name in list(running):                       # one forward pass
            st = running[name]
            st[0] += 1                                   # one new token each
            if st[0] == st[1]:                           # eos: leave immediately
                print(f"{name}: iterations {st[2]}-{it}")
                del running[name]
    return it

print("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)

> **Full slots are not free:** Each extra sequence adds its KV-cache reads to every step, so time per output token grows with the batch. Admitting until memory is full can also force preemption later, when running sequences grow and the cache runs out. Engines then evict a sequence and recompute or swap its cache (see **PagedAttention**). Cap `max_num_seqs` or the batch token budget to the latency your users accept, not just to what fits.

> **Why it took until 2022:** Request-level batching was fine for fixed-cost models, and serving frameworks exposed models as "one request in, one response out". Iteration-level scheduling needs the server to own the generation loop and the per-sequence KV state. That is why it arrived with dedicated LLM engines rather than as a feature of general model servers.

**Strengths**

- 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.

**Limitations**

- 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.

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

- A. About 29%
- B. About 50%
- C. About 75%
- D. 100%, because padding is free

**Answer:** A. About 29% — $U=(10+10+10+200)/(4\cdot200)=230/800=28.75\%$. Three slots sit idle for 190 iterations, and the three short answers wait about 20 times longer than needed.

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

- A. Its tokens are decoded before theirs
- B. Its prefill runs in the same forward pass as their decode step, so that iteration takes much longer
- C. It evicts their KV cache
- D. Continuous batching reorders tokens by prompt length

**Answer:** B. Its prefill runs in the same forward pass as their decode step, so that iteration takes much longer — Prefill processes the whole prompt in one compute-bound pass. Everyone in the batch waits for that pass before getting their next token. Chunked prefill limits the tokens per iteration to bound this stall.

**Key points**

- Schedule per iteration, not per request: finished sequences leave immediately, waiting ones join at the next forward pass.
- Request-level batching wastes $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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
