Chapter 06

The scheduler

Two lists, one GPU, one choice per step.

chapter 5, last frame · continuous batching, one newcomer joinsslot 1slot 2slot 3newcomer's prefillslot 4slot 5slot 6one step, stretched to a prompt's worth of mathdon't mixprefill batchordecode batchthe default in SGLang and vLLM: each step is one kind of batch. Mixing comes back later, on purpose and bounded.

Chapter 5 ended here: a newcomer's prefill stretching everyone's decode step. Engines don't run the two together by default. They split the work into two kinds of batch and pick one each step. That's the scheduler.

← Batching & continuous batching
01 / 09
The scheduler’s arithmetic, once

A prefill batch of PP tokens takes about 2P⋅ttok2P \cdot t_{\text{tok}}; a decode step takes tstep≈tmemt_{\text{step}} \approx t_{\text{mem}}. With prefill-first, a newcomer gets TTFT≈2P ttok\text{TTFT} \approx 2P\,t_{\text{tok}} and everyone else sees a gap of that plus one decode step. Capping prefill batches at cc tokens and alternating gives

gap≈2c ttok+tstep,TTFT≈⌈P/c⌉⋅2c ttok+(⌈P/c⌉−1) tstep\text{gap} \approx 2c\,t_{\text{tok}} + t_{\text{step}}, \qquad \text{TTFT} \approx \lceil P/c \rceil \cdot 2c\,t_{\text{tok}} + (\lceil P/c \rceil - 1)\, t_{\text{step}}

Mixing a chunk of c≤n∗−Bc \le n^* - B into each decode step removes the gap entirely and gives TTFT≈⌈P/c⌉⋅tstep\text{TTFT} \approx \lceil P/c \rceil \cdot t_{\text{step}}. In SGLang: chunked_prefill_size is cc, enable_mixed_chunk turns on mixing, schedule_policy orders the waiting list, and the loop above is Scheduler.get_next_batch_to_run(), which tries to build a prefill batch first and falls back to the running decode batch.