Chapter 06

The scheduler

Two lists, one GPU, one choice per step.

Ch. 5 Step 9 · 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 batchSGLang's default: each step is one kind of batch (vLLM v1 mixes by default) · mixing comes back in step 7, on purpose and bounded

Ch. 5 Step 9 ended here: a newcomer's prefill stretching everyone's decode step. SGLang doesn'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 P⋅ttokP \cdot t_{\text{tok}}; a decode step takes tstep≈tmemt_{\text{step}} \approx t_{\text{mem}}. With prefill-first, a newcomer gets TTFT≈P ttok\text{TTFT} \approx P\,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≈c ttok+tstep,TTFT≈⌈P/c⌉⋅c ttok+(⌈P/c⌉−1) tstep\text{gap} \approx c\,t_{\text{tok}} + t_{\text{step}}, \qquad \text{TTFT} \approx \lceil P/c \rceil \cdot c\,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, 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. chunked_prefill_size caps a prefill batch and is on by default (8,192 tokens on an H100), but a prompt that is partway through its chunks gets its next chunk on the very next step, so on its own it does not shorten the freeze. --prefill-decode-interval N runs NN decode steps after every prefill batch, and N=1N = 1 gives the alternation in step 6. --enable-mixed-chunk turns on mixing; the chunk and the decodes then share one budget, so cc = chunked_prefill_size −B- B.