Scheduling: token budgets, chunked prefill, preemption and priorities

An inference engine is mostly a scheduler wrapped around a fast forward pass. Every step (one pass through the model) it decides which sequences to run, how many tokens of each, and what to do when memory is short. Most "why is my p99 so bad" investigations end in one of the settings in this lesson.

#The step loop

Each step has two budgets:

• A token budget (max_num_batched_tokens in vLLM, a chunk size in SGLang): the maximum number of tokens processed in one forward pass.
• A sequence budget (max_num_seqs): the maximum number of running sequences.

And one hard constraint: free KV-cache blocks. A sequence can only run if its cache fits (paged blocks).

#Why the token budget exists

A step's duration is set by two things: the time to read the weights (fixed, memory-bound) and the compute for the tokens in the batch (grows with tokens). Below some token count a step costs roughly the weight read; above it, compute dominates and the step grows linearly.

Rough numbers for an 8B model on one datacenter GPU:

• Weight read: 16 GB at 3 TB/s is about 5 ms.
• Compute for N tokens: about 2 × 8e9 × N FLOPs. At an effective 500 TFLOP/s, 2048 tokens is 33 TFLOP, about 66 ms.

So a step with 64 decodes takes about 5 to 8 ms, while a step with a 2048-token prefill chunk takes about 65 ms. Every decode in that step waits the full 65 ms for its next token. That is the whole tension: big steps are efficient for prefill, but they hurt the streaming users sharing the step.

#Chunked prefill

Instead of processing a whole prompt in one step, split it into chunks and put one chunk plus all running decodes into each step (Sarathi-Serve is the paper behind the idea).

budget = 2048 tokens per step, 48 decodes running
chunk  = 2048 - 48 = 2000 prompt tokens per step

An 8000-token prompt:   step 1: 2000 + 48 decodes
                        step 2: 2000 + 48 decodes
                        step 3: 2000 + 48 decodes
                        step 4: 2000 + 48 decodes   -> prefill done, first token next step

Effects:

The last row is the neat part: decode leaves compute idle and prefill leaves memory bandwidth idle. Mixing them in one step uses both. Recent vLLM versions enable chunked prefill by default; SGLang exposes a chunked-prefill size.

#Choosing the budget

Set it from your latency target: pick the largest budget whose step time still meets your inter-token latency target, measured on your hardware under mixed load (benchmarking).

#The sequence budget and the throughput curve

max_num_seqs caps concurrency. Throughput rises with concurrency because each weight read serves more tokens, then flattens, while per-user speed falls:

sequences   step time   tokens/s total   tokens/s per user
   1          5 ms          200               200
  16          6 ms         2667               167
  64          9 ms         7111               111
 256         25 ms        10240                40

(Illustrative shape, not a benchmark.) Past the knee you gain little throughput and users feel it. The right cap depends on your service-level objective: choose the largest concurrency at which inter-token latency still meets it.

#When memory runs out: preemption

The KV cache is allocated in blocks as sequences grow. If the pool runs dry while sequences are still generating, the scheduler must act:

1. Preempt by recompute. Free the victim's blocks, put it back in the waiting queue, and re-prefill it later (cheap if its prefix is in the prefix cache).
2. Preempt by swap. Copy its blocks to host memory and bring them back later (needs fast host links and enough RAM).
3. Reject new work early (admission control) so the situation never arises.

Preemption is a symptom. If metrics show many preemptions, tokens are being computed twice. Fix it by:

• Lowering max_num_seqs or max_model_len.
• Raising the memory fraction given to the cache (gpu_memory_utilization).
• Quantising the KV cache (quantisation in depth).
• Adding capacity.

Which sequence to evict is a policy choice. Common ones: the most recently arrived (it has done the least work), or the lowest priority.

#Scheduling policies

A practical pattern: two classes, interactive and batch. Batch work fills idle capacity and is the first to be preempted when interactive traffic rises (know your workload).

#Queueing and admission control

A scheduler cannot fix overload. When arrivals exceed capacity the queue grows without bound and latency becomes unlimited. Protect the system:

• Bound the queue and return "busy" or 429 beyond it.
• Estimate cost at admission (prompt tokens plus max new tokens) and reject requests that cannot fit.
• Set timeouts at the gateway (gateways).
• Autoscale on queue depth or KV usage, not only on GPU utilisation (observability).

#What to watch

#Common mistakes

• Huge token budget with chat users. It looks fastest on a throughput benchmark and feels bad to people.
• Benchmarking with uniform prompts. The real damage comes from the occasional 30,000-token request, so test with a long tail.
• Treating preemption as free. It silently doubles compute for the victims.
• Capping max_model_len at the model maximum "just in case". It forces a larger worst-case reservation per sequence; set it to what you serve.
• Autoscaling on GPU utilisation alone. A saturated cache can leave utilisation moderate while latency is terrible.

#Exercise

Your engine has a 4096-token budget and runs 128 decodes per step. A request with a 20,000-token prompt arrives.

1. How many prompt tokens go into each step, and how many steps does the prefill take?
2. If step time is about 110 ms during these steps, what happens to running users' inter-token latency, and what would you change if the target is 50 ms?

Answers: the chunk is 4096 − 128 = 3968 tokens, so about 5.05, that is 6 steps (five full chunks and a small last one), roughly 0.66 s before the big request's first token. Running users see about 110 ms between tokens during those steps instead of the usual few milliseconds, which misses a 50 ms target. Lower the budget (for example to about 1500 tokens so a step is around 50 ms), accept that the long prompt takes more steps, and check time to first token for it.

#Going deeper

• The Sarathi-Serve paper on chunked prefill and stall-free batching.
• The vLLM and SGLang scheduler documentation for the exact flag names in your version.
• Disaggregated prefill and decode for the alternative of separating the two phases onto different machines.