Prefill interference
Trace static and iteration-level schedules and explain chunked prefill, preemption and latency tradeoffs.
THE IDEA
A big prompt can stall everyone else
Admitting a new request means running its prefill, which is much more work than one decoding step. If the scheduler squeezes a long prompt into one iteration, that iteration takes a long time and every request that was about to get its next token waits for it. In the toy cost model (1 ms per decoding sequence, 0.1 ms per prefill token) a 2000-token prompt turns a 4 ms iteration into 204 ms.
Packing a large prompt into one iteration keeps the hardware busy, but every request that was waiting for its next token pays the delay. Throughput and individual latency targets can conflict.
Predict first. Does maximising prompt tokens in one iteration necessarily minimise every request's delay?
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
Compute the stall by hand with the toy cost model, then write the model.
Packing a large prompt into one iteration keeps the hardware busy, but every request that was waiting for its next token pays the delay. Throughput and individual latency targets can conflict.
- To do: Toy cost model: an iteration costs 1 ms per decoding sequence plus 0.1 ms per prefill token processed. With 4 sequences decoding and nothing else, ms per iteration?
- To do: A new 2000-token prompt is prefilled in ONE iteration alongside those 4 decodes. ms for that iteration?
- To do: How many times longer than normal is the wait for the next token of the 4 running requests?
Part 2. Do it in code
- iteration_time(decodes, prefill_tokens, decode_cost=1.0, prefill_cost=0.1): decodes · decode_cost + prefill_tokens · prefill_cost (milliseconds).
- stall_factor(decodes, prompt_tokens): iteration_time with the whole prompt divided by iteration_time without it. ValueError if decodes < 1.
- added_delay(decodes, prompt_tokens): extra milliseconds that the running requests wait because of the prompt.
- total_prompt_cost(prompts): sum of prefill_tokens · 0.1 over a list of prompt lengths.
Stuck, or something not working? You can come back to it any time.
CHECK YOUR UNDERSTANDING
Does maximizing prompt tokens in one iteration necessarily minimize every request's delay?
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.