Serving · Scheduling

Continuous Batching

refilling the batch after every decode step

toy server
4 slots · 12 requests
steps
56 static → 40 continuous
step time
8.0 ms LLaMA 3 8B · A100

All steps

  1. Why batch

    A decode step reads every weight of the model to produce one token per sequence. Reading them takes the same time whether one sequence or dozens share the step, so a batch multiplies tokens per second almost for free, until the arithmetic catches up with memory.

    step time ≈ max(weights / bandwidth, FLOPs / peak)

  2. Static batching

    With static batching the server starts a batch and runs it until its longest request is done. Finished requests keep their slot doing nothing (hatched), and new requests wait for the whole batch to end.

    a batch lasts as long as its longest request

  3. Refill after every step

    Continuous (iteration-level) batching, from the Orca paper, reschedules after every step: a finished request leaves at once and a waiting one takes its slot on the next step, with its prompt’s prefill folded into that step.

    refill free slots after every step

  4. Waiting and throughput

    Same requests, same four slots. Refilling every step keeps the slots busy with real work, so requests hardly wait to start, finish much sooner on average, and the whole queue is done in fewer steps.

    waiting ↓ · latency ↓ · throughput ↑

  5. Long prompts in chunks

    A new request’s prefill can be long: run in one step, its 512 prompt tokens make that step compute-bound and three times as slow, stalling every other request’s next token. Chunked prefill splits it into pieces small enough to hide under the memory-bound step time.

    prefill in chunks of 128, mixed with decodes

Code

# static batching: run a batch to completion
while batch: step(batch); batch = [r for r in batch if not r.done] or next_batch()
# continuous batching: reschedule every iteration
while True:
    running = [r for r in running if not r.done]           # finished ones leave now
    while waiting and len(running) < max_batch and fits(waiting[0]):
        running.append(waiting.pop(0))                     # its prefill joins this step
    step(running)                                          # one token for each
# chunked prefill: cap the prompt tokens per step
budget = 128; chunk = prompt[done:done + budget]

Go deeper