Continuous batching
Trace static and iteration-level schedules and explain chunked prefill, preemption and latency tradeoffs.
THE IDEA
Continuous (iteration-level) batching
Instead of fixing the batch until it empties, the scheduler looks at the end of every iteration: finished requests leave, and waiting ones are admitted into the free slots immediately. The same work then finishes in fewer iterations. In the example (lengths 2, 1, 2 with two slots) the schedule becomes A+B, A+C, C: 3 iterations and 5/6 = 83.33% utilisation, against 4 iterations and 62.5%.
| it 1 | it 2 | it 3 | it 4 | it 5 | it 6 | it 7 | |
|---|---|---|---|---|---|---|---|
| slot 1 | A | A | C | C | E | ||
| slot 2 | B | D | D | D | D |
| it 1 | it 2 | it 3 | it 4 | it 5 | it 6 | |
|---|---|---|---|---|---|---|
| slot 1 | A | A | C | D | D | D |
| slot 2 | B | C | D | E |
| iterations | utilisation | A done | B done | C done | D done | E done | |
|---|---|---|---|---|---|---|---|
| static | 7 | 71.4% | 2 | 1 | 4 | 6 | 7 |
| continuous | 6 | 83.3% | 2 | 1 | 3 | 6 | 4 |
The default has five requests, so the first three (2, 1, 2 tokens, two slots) are the chapter's example: 62.5% becomes 83.33%. Continuous admission needs a scheduler that decides every iteration and a cache that can hold new sequences at any time. Real token costs are not equal, so this is a toy.
Predict first. Can admission change after every token iteration?
Chapter context
Requests arrive at different times and finish after different output lengths. Scheduling decides which work enters each iteration and how waiting prompts compete with ongoing generation.
TRY IT YOURSELF
Part 1. Do it hands-on
Trace the continuous schedule by hand, then simulate it, including requests that arrive late.
| it 1 | it 2 | it 3 | it 4 | it 5 | it 6 | it 7 | |
|---|---|---|---|---|---|---|---|
| slot 1 | A | A | C | C | E | ||
| slot 2 | B | D | D | D | D |
| it 1 | it 2 | it 3 | it 4 | it 5 | it 6 | |
|---|---|---|---|---|---|---|
| slot 1 | A | A | C | D | D | D |
| slot 2 | B | C | D | E |
| iterations | utilisation | A done | B done | C done | D done | E done | |
|---|---|---|---|---|---|---|---|
| static | 7 | 71.4% | 2 | 1 | 4 | 6 | 7 |
| continuous | 6 | 83.3% | 2 | 1 | 3 | 6 | 4 |
The default has five requests, so the first three (2, 1, 2 tokens, two slots) are the chapter's example: 62.5% becomes 83.33%. Continuous admission needs a scheduler that decides every iteration and a cache that can hold new sequences at any time. Real token costs are not equal, so this is a toy.
- To do: Continuous batching: after every iteration finished requests leave and waiting ones are admitted. Iteration 1: A+B (B finishes). Iteration 2: A+C (A finishes). Iteration 3: C alone. Total iterations?
- To do: Active slot-iterations are still 5 but capacity is now 3 × 2 = 6. Utilisation in percent (2 decimals)?
- To do: At which iteration does request C finish (static schedule: 4)?
Part 2. Do it in code
- simulate_continuous(lengths, slots): requests wait in a first-in-first-out queue. Before every iteration, free slots are filled from the queue; every running request then generates one token; requests whose remaining length reaches 0 leave at the end of that iteration. Return the same dict as the static simulation (iterations, active, capacity, utilization, finish with 1-based finish iterations).
- with_arrivals(lengths, arrivals, slots): like simulate_continuous, but request i can only be admitted at an iteration index (0-based) >= arrivals[i]. If nothing is running and nothing has arrived yet, time still moves forward one iteration (idle). Return dict with iterations (including idle ones), active, capacity, utilization, finish.
Stuck, or something not working? You can come back to it any time.
CHECK YOUR UNDERSTANDING
Can admission change after every token iteration?
Chapter reference: math, worked example & code
This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.
Math and notation
In a simplified equal-cost decode schedule, utilization = active sequence-iterations / available sequence-iterations. This omits prefill costs and assumes uniform iteration time. A real scheduler needs measured compute, memory and latency constraints.
Worked example
Two slots serve requests A,B,C with output lengths 2,1,2. Static groups run A+B for two iterations, then C alone for two: 5 active slots out of 8 available. Continuous admission runs A+B, then A+C, then C: 5 active slots out of 6. Utilization rises from 62.5% to about 83.33% in this toy schedule; real token costs are not equal.
Reference code
The following example uses the Python standard library and does not call a remote service.
from math import isclose
static=[['A','B'],['A',None],['C',None],['C',None]]
continuous=[['A','B'],['A','C'],['C',None]]
util=lambda rows: sum(x is not None for row in rows for x in row)/(2*len(rows))
assert util(static) == .625
assert isclose(util(continuous),5/6)
Python examples are provided for study and local execution; this page does not execute Python.
Common mistakes
Continuous batching does not guarantee a fixed improvement. Chunked prefill changes scheduling granularity, not the model's context dependencies. Include cache movement or recomputation costs when comparing preemption policies.