Continuous Batching

ch07 · Continuous Batching¶

The problem¶

ch06 · Static Batching and Its Limits measured it: a third of the slot-steps in a mixed batch were spent computing tokens for sequences that had already finished, and a request arriving just after a batch formed waited for every member of that batch to drain before it could start.

Both come from one assumption, so deeply buried it barely looks like a decision: the batch is the unit of work. Sequences enter together and leave together because that is how the loop was written.

Nothing about the mathematics requires it.

The idea¶

Schedule per iteration, not per batch¶

A decode step does not care which sequences are in it. It reads the weights, applies them to whatever queries it is given, and returns one token for each. The set of sequences can be different on every single step and the arithmetic does not notice.

So make it different. On each step:

1. Retire any sequence that finished on the previous step. Its slot is free now.

2. Admit waiting requests into free slots.

3. Run one step over whatever is in the running set.

This is iteration-level scheduling, introduced by Orca and universally known as continuous batching. Both names are accurate: the granularity of scheduling is one iteration, and the batch never stops to re-form.

The two wastes from ch06 · Static Batching and Its Limits disappear rather than shrink:

• Ragged completion — gone. A finished sequence leaves on the next step, so no slot-step is ever spent on completed work.

• Admission delay — gone. A request waits at most one step for a free slot, instead of waiting for a whole batch.

Why this is the biggest win in the book¶

It is worth being precise about why, because the reason is not “it does less work”.

Throughput improves, but only modestly — the engine was already batching, and batching was already collecting the weight-read amortisation.

TTFT improves enormously, and that is a queueing effect. ch02 · Measuring What Matters showed the naive engine collapsing because requests queued behind other requests. Static batching shortened the queue but kept its structure: you still wait for a batch. Continuous batching removes the waiting almost entirely, so at loads where the static engine has a visible queue, the continuous engine has essentially none.

And because goodput counts requests that met a latency objective, an improvement concentrated in TTFT moves goodput far more than the throughput change alone would suggest.

There is no new mathematics in this chapter. There is no new kernel. The entire gain comes from changing when a sequence is allowed to join and leave.

The build¶

The engine subclasses ch06 · Static Batching and Its Limits’s and replaces step. That inheritance is the point: everything about how tokens are computed is unchanged.

class ContinuousBatchEngine(StaticBatchEngine):
    """Chapter 7: admit and retire per iteration rather than per batch.

    One change: the running set is re-evaluated every step. A finished sequence leaves immediately
    and a waiting one takes its place in the same step, so no slot is ever spent on a request that
    has already finished. No new mathematics, no new kernel — only when a sequence is allowed to
    join and leave.
    """

    name = "continuous-batch"

    def step(self) -> list[StepOutput]:
        # Retire anything that finished on the previous step, then refill the freed slots.
        self.running = [state for state in self.running if not state.finished]
        admitted: list[RequestState] = []
        while self.waiting and len(self.running) + len(admitted) < self.max_batch_size:
            admitted.append(self.waiting.pop(0))

        outputs: list[StepOutput] = []

        if admitted:
            logits, caches = _prefill_batch(self.model, admitted)
            for state, cache in zip(admitted, caches, strict=True):
                state.past = cache
            outputs += self._emit(admitted, _sample_batch(logits, admitted))
            self.running += admitted

        decoding = [state for state in self.running if state not in admitted and not state.finished]
        if decoding:
            outputs += self._emit(
                decoding, _sample_batch(_decode_batch(self.model, decoding), decoding)
            )

        return outputs

Three details do the work.

Retirement happens first. The running set is filtered before admission, so a slot freed by a sequence finishing on the previous step is reusable on this one.

Admitted requests are prefilled separately, then join the decode batch. A new arrival needs its whole prompt processed; sequences already running need one token each. These are different shapes, so this engine does them as two passes. That is honest but not ideal — the prefill pass makes the step longer, which every currently-streaming sequence feels as an ITL spike. ch10 · Chunked Prefill and Scheduling Policy addresses exactly this.

Nothing about sampling, caching or attention changed. The equivalence test holds without any tolerance:

def test_batching_does_not_change_output(model, mixed_specs, engine_cls):
    """ch06/ch07: batching is a scheduling change, not a different model."""
    assert _serve_batched(model, engine_cls, mixed_specs) == _serve_individually(model, mixed_specs)

And the waste counter from ch06 · Static Batching and Its Limits now reads zero by construction:

def test_continuous_batching_wastes_no_slots(model, mixed_specs):
    """ch07's fix: a finished sequence leaves immediately, so no slot-step is ever discarded."""
    engine = ContinuousBatchEngine(model)
    for prompt, n in mixed_specs:
        engine.add_request(
            Request(prompt_token_ids=list(prompt), params=SamplingParams(max_tokens=n))
        )
    while engine.has_work():
        engine.step()
    assert engine.wasted_slot_steps == 0


def test_disaggregation_does_not_change_output(model, mixed_specs):
    """ch11: moving the cache between pools must not change a single token."""
    from llmserve.engines.disaggregated import DisaggregatedEngine

    engine = DisaggregatedEngine(model)
    outputs: dict[int, list[int]] = {}
    for prompt, n in mixed_specs:
        request = Request(prompt_token_ids=list(prompt), params=SamplingParams(max_tokens=n))
        outputs[request.request_id] = []
        engine.add_request(request)
    guard = 0
    while engine.has_work() and guard < 10_000:
        for out in engine.step():
            outputs[out.request_id].extend(out.token_ids)
        guard += 1

    assert list(outputs.values()) == _serve_individually(model, mixed_specs)
    assert engine.transfers == len(mixed_specs), "every request must be handed off exactly once"
    assert engine.transferred_bytes > 0

The measurement¶

Against static batching, same trace, same model, same machine:

Conditions: TinyGPT (reference, random weights) (5,838,080 params), 4x x86_64 CPU, torch 2.14.0+cu130, poisson, prompt 32-96, output 16-48, seed 7, arrival rate 8.0/s, measured 2026-09-13T15:28:11+00:00.

The throughput column improves by a modest margin. The TTFT columns are a different story entirely — and note what happens to them as load rises. Static batching’s median TTFT climbs steadily with the arrival rate. Continuous batching’s barely moves. The engine is not merely faster; it has stopped queueing.

That is the shape to remember: an engine whose TTFT is flat in the arrival rate has capacity in hand, and one whose TTFT climbs is already queueing, whatever its throughput says.

Here is the whole journey so far, at the highest load we have measured:

Conditions: TinyGPT (reference, random weights) (5,838,080 params), 4x x86_64 CPU, torch 2.14.0+cu130, poisson, prompt 32-96, output 16-48, seed 7, arrival rate 16.0/s, measured 2026-09-13T15:28:33+00:00.

Four chapters of work, one saturating workload. Throughput has multiplied several times over, median TTFT has fallen from seconds to milliseconds, and goodput — the only number that counts requests actually served within their objective — has improved by well over an order of magnitude.

Two of those four steps (the KV cache, and this one) involved no new mathematics at all.

The cost¶

Continuous batching is close to strictly better, but not entirely free:

• The engine is now a scheduler, with genuine state: a running set, a waiting queue, admission and retirement rules. Every later chapter modifies this loop, and bugs in it produce starvation and unfairness rather than crashes.

• ITL gets worse, and unevenly so. Prefilling an admitted request lengthens that step for everyone already streaming. A user mid-sentence experiences somebody else’s arrival as a pause. The measurement above shows ITL rising with load for precisely this reason, and ch10 · Chunked Prefill and Scheduling Policy is the fix.

• Admission is now a policy decision. First-come-first-served is one choice among several, and the wrong one starves somebody. ch10 · Chunked Prefill and Scheduling Policy again.

• Memory pressure becomes bursty. Admitting several long prompts on one step can spike KV usage hard. With a contiguous per-sequence cache there is no graceful response available — which is the subject of ch08 · Paged Attention and the Block Manager.

That last point deserves emphasis. This engine assembles a padded batch from per-sequence caches on every step and takes it apart again afterwards, copying work proportional to the longest sequence present. It is correct, and it is wasteful, and it caps how far this design scales.

Key takeaways¶

• A decode step is indifferent to which sequences are in it, so the running set can change every step. That single observation is continuous batching.

• Retiring finished sequences immediately eliminates ragged-completion waste; admitting into freed slots eliminates batch-formation delay.

• The gain shows up mostly in TTFT, because it is a queueing improvement rather than a compute one — and goodput follows TTFT.

• Flat TTFT as load rises means capacity in hand. Rising TTFT means queueing, whatever throughput reports.

• The engine is now a scheduler, and its remaining problems — prefill interference, admission policy, bursty memory — are scheduling and memory problems, not arithmetic ones.

Looking ahead¶

The scheduler wants to admit more sequences than memory allows, and its per-sequence contiguous caches make every step copy more than it should. ch08 · Paged Attention and the Block Manager replaces that memory layout with fixed-size blocks and a block table, which raises the concurrency ceiling without buying a single byte of extra RAM.

Further reading¶

Orca (Yu et al., OSDI 2022, Appendix E) introduced iteration-level scheduling and is the primary source for this chapter; it is short and worth reading now that you have implemented its central idea. The vLLM paper builds on it and is better read after ch08 · Paged Attention and the Block Manager.