S09Batching & Scheduling·244 lines

Continuous Batching

Static batching makes every request wait for the slowest one. Admitting and retiring requests between forward passes raises throughput several-fold.

static vs continuous
iteration-level scheduling
ragged batches
bubble elimination

Motivation

The problem

S05 left us with an uncomfortable fact: a decode step reads the entire model to produce one token, and the GPU's arithmetic units are idle over 99% of the time. The fix suggests itself. Process several requests in the same forward pass, so that one weight read serves many tokens. Batch 32 gives you roughly 32× the throughput for roughly the same time per step.

Then you try to implement it and hit the wall that makes LLM serving different from every other batched workload: you do not know how long a request will run.

Classical batching forms a group, runs it to completion, then returns all the results together. With LLMs, that means the batch runs until its longest member finishes. A request that needed 5 tokens sits in its slot for 500 steps producing nothing; a request arriving one step after the batch forms waits for the whole thing to drain.

Core idea

The solution

Stop treating the batch as a unit. Make admission and retirement decisions between every forward pass instead of between every batch. Orca called this iteration-level scheduling; everyone now calls it continuous batching.

the loop, restructuredpython

def run(self):
    while self.has_work():
        # --- these two steps used to happen once per BATCH ----------
        for req in self.running:
            if req.finished:
                self.retire(req)              # free its KV blocks
        while self.can_admit():
            self.running.append(self.waiting.popleft())
        # ------------------------------------------------------------

        logits = self.model.forward_batch(self.running)   # one pass
        for req, row in zip(self.running, logits):
            req.append(sample(row, req.params))

Two lines moved inside the loop, and that is the technique. It is affordable only because of S06: retiring a request must free its KV memory instantly, and admitting one must allocate without reshuffling anyone else. With contiguous caches, retiring a request mid-batch would leave a hole nobody could use.

The batch is now ragged

Every request in the batch sits at a different position with a different context length, so there is no rectangular tensor to build. Kernels take a flattened token buffer plus a cu_seqlens array of cumulative sequence lengths, and index accordingly. FlashAttention's varlen API and PagedAttention both assume this shape. Continuous batching cannot be bolted onto a naive implementation for exactly that reason.

Mechanics

How it works

Diagramstatic vs continuous batching on identical traffic

Same six requests, same four slots. Static batching wastes 30 slot-steps on padding and makes E and F wait 12 and 11 steps. Continuous batching leaves 16 idle slot-steps of spare capacity instead, starts E and F 11 and 10 steps earlier, and finishes everything by t=14 instead of t=22.

Why the gain is so large on real traffic

How large the win is depends on the variance of output lengths. If every request generated exactly 100 tokens, static batching would be nearly optimal and continuous batching would buy almost nothing.

Real traffic is nothing like that. Output lengths are heavy-tailed: most responses are short, a few are very long, and in a batch of 32 the ratio between the mean and the max is routinely 10× or more. Padding to the max therefore wastes most of the batch. Measured improvements land consistently in the 2–4× range.

typical throughput gain: 2–4×; against static batching on chat-shaped traffic
and latency improves too: ↓; no waiting for the next batch boundary
extra memory required: 0; given paged KV; this is pure scheduling

What batching does not fix

Batching improves throughput per GPU, not latency per request. Past a point it makes single-request latency worse: at large batch sizes the forward pass becomes compute-bound again, so each step takes longer and every request in the batch feels it.

That trade-off is the fundamental one in serving, and S10 exists to manage it. Somebody has to decide how large the batch should be, right now, given the requests queued and the latency you promised.

Explore

Try it

Twelve requests with heavy-tailed lengths arrive over the first eighteen steps. Run it in continuous mode, then flip to static and run it again. The head-to-head panel keeps both results, so you can compare them directly.

Simulatorstatic vs continuous batchingrun both modes, then change the traffic seed

batching

batch slots4traffic seed4

step 64 / 64

completed: 11/12
useful tokens: 213
GPU utilisation: 83%
avg latency: 25.0 steps

execution timeline · continuous batching

slot0

slot1

slot2

slot3

generating a token
padding — finished, still occupying the slot
idle slot

A finished request is retired and its slot refilled at the very next step. There is no batch boundary at all; the 'batch' is whichever requests happen to be running right now.

head-to-head, same traffic and same slots

completed in 64 steps

continuous11

static7

GPU utilisation

continuous83%

static47%

avg latency (steps)

continuous25.0

static31.9

Continuous batching does not make any single forward pass faster. What it removes are the gaps: the padding, and the wait for the next batch. On real traffic with heavy-tailed output lengths that is consistently a 2–4× throughput improvement and a large latency improvement at the same time. Getting both at once is rare enough to be worth noticing.

Try slots = 1. Both modes become identical: with one slot there is no padding to eliminate. Continuous batching is an occupancy optimisation, not a kernel one.

Build it

Implementation

The ragged batch is the part worth writing carefully. Instead of a [batch, seq, hidden] tensor with padding, flatten every request's tokens into one long sequence and carry an offsets array.

code/s09_continuous_batching.py (excerpt)python

def build_batch(running: list[Request]):
    """Flatten a ragged batch the way real kernels want it."""
    token_ids, positions, cu_seqlens = [], [], [0]

    for req in running:
        new = req.tokens_to_process()          # prefill: many; decode: 1
        token_ids.extend(new)
        positions.extend(range(req.computed, req.computed + len(new)))
        cu_seqlens.append(len(token_ids))      # cumulative offsets

    return Batch(
        token_ids=np.array(token_ids),         # [total_tokens] — no padding
        positions=np.array(positions),
        cu_seqlens=np.array(cu_seqlens),       # [num_requests + 1]
        block_tables=[r.block_table for r in running],
    )

Sampling parameters are per request, not per batch

Once the batch is heterogeneous, so is everything downstream. Request 0 may want greedy decoding, request 1 temperature 1.2 with top-p 0.9, and request 2 a grammar constraint. A batched sampler that applies one set of parameters to the whole batch is the most common bug on a first implementation. It stays invisible until a user complains that temperature=0 is not deterministic.

Run it locally

Runs a synthetic workload with heavy-tailed output lengths through both a static batcher and a continuous batcher, sharing the same arrival trace, and reports throughput, GPU utilisation, padding waste and per-request latency percentiles.

$ python code/s09_continuous_batching.py

Expect: A ~2.9× faster drain for continuous batching, padding falling from ~70% of slot-time to zero, and a side-by-side latency percentile table showing both improve at once.

Only NumPy is required — setup instructions.

Production notes

In production

Orca (OSDI '22) — introduced iteration-level scheduling and selective batching. Every engine since is a descendant.
vLLM — the scheduler runs once per step(), producing a fresh set of running requests each iteration.
TGI, TensorRT-LLM, SGLang, LMDeploy — all ship it. TensorRT-LLM calls it "in-flight batching", a better name.
llama.cpp — supports it via parallel sequences in the server binary. Its main use case is single-user local inference, where batch size is 1 and none of this applies.

Exercises

1
Plot throughput and P99 latency against batch size for a fixed arrival rate. Find the knee: the largest batch that still meets a 50 ms inter-token latency target.
2
Make output lengths uniform instead of heavy-tailed and re-run the comparison. Confirm the advantage of continuous batching mostly disappears, and explain why in one sentence.
3
Add per-request sampling parameters to the batched sampler and write the test that catches the "one temperature for the whole batch" bug.

Continue

What's next

We now admit requests every step, but on what basis, and how many? What happens when memory runs out mid-generation, or when a huge prompt arrives? S10 builds the scheduler. Those decisions live there, and so does most of an engine's observable behaviour.

Check yourself

Questions

Answer before you look. A wrong answer tells you more than a right one, because the explanation points at the part of the chapter to reread.

Check yourselfQuestion 1 of 6

What property of real traffic makes continuous batching worth 2–4× rather than nearly nothing?

Score 0/6