Continuous Batching and Why Your Latency Varies

Your request does not get a GPU. It gets a seat in a batch that is being rebuilt after every single token, alongside requests from people you will never meet, and the composition of that batch is the largest single source of latency variance in hosted inference.

What static batching did wrong

The obvious way to batch is to collect B requests, run them together until all of them finish, then start the next batch. It is also badly wrong for generation, for two reasons that compound.

First, a batch finishes when its longest member finishes. Nine requests that want twenty tokens and one that wants two thousand means nine slots sit idle for the remaining 1,980 steps, computing padding. Second, a request that arrives just after the batch launched waits for the whole batch, no matter how small it is. With generation lengths varying by two orders of magnitude — a yes/no answer and a long document summary go through the same endpoint — utilisation collapses.

Iteration-level scheduling

Continuous batching, introduced as iteration-level scheduling in the Orca paper (Yu et al., OSDI 2022) and now standard in vLLM, TensorRT-LLM, TGI and SGLang, changes the unit of scheduling from the request to the decode step. The loop is:

loop forever:
    finished = [s for s in running if s.done]
    evict(finished)                      # frees their KV blocks

    while kv_free() >= kv_needed(head(waiting)) and len(running) < max_seqs:
        admit(waiting.pop())             # prefill it, add to the batch

    step(running)                         # ONE token for every live sequence
    emit(tokens)

A sequence that hits its stop token leaves at the end of that iteration, its KV blocks are freed immediately, and a waiting request takes the slot on the next one. No padding to the longest generation, no waiting for a batch boundary. The published result in Orca, and the reason every serving stack adopted it, was a large throughput improvement at fixed latency compared with request-level batching — the paper reports its own numbers against FasterTransformer and is the right citation to read rather than a figure repeated second-hand.

Two details of that loop determine what you experience. The admission test has two conditions, and which one binds changes the server’s character: a sequence limit caps how many conversations can run at once regardless of size, while the KV check caps how much total context is resident. A server bounded by the sequence limit is fair to long prompts and wastes memory; one bounded by KV capacity uses its memory fully and quietly penalises whoever brought the largest prompt, because their admission requires the most contiguous free capacity.

And the waiting list is a scheduling policy, not a queue you can reason about from outside. First-come-first-served is the common default and is the only one that guarantees no starvation; policies that prefer short prompts raise throughput and can leave a very large request waiting indefinitely under sustained load. Providers do not publish which they use, which is one of several reasons the same model behaves differently on two endpoints.

Where your variance comes from

Now the consequence for one request. Three distinct mechanisms make an identical call slower on Tuesday than it was on Monday:

• Admission delay. If the batch is at max_num_seqs, or the free KV blocks cannot cover your prompt’s cache, you wait. Nothing about your request is being computed; it is queued. This term is unbounded above and depends purely on other people’s traffic.
• Batch-size effect on step time. A decode step over a batch of 8 and over a batch of 200 do not take the same wall-clock time. Because decode is memory-bound (see prefill vs decode) the weight read is amortised across the batch, so step time grows far slower than linearly — but it does grow. Your tokens per second is therefore a function of how busy the server is.
• Prefill interference. Someone else’s 100k-token prompt has to be prefilled, and on a naive scheduler that prefill occupies the device for a long compute-bound pass during which no decode steps happen. Every streaming user sees a pause. This is the classic “my stream froze for two seconds and then caught up” report.

Preemption adds a fourth: under memory pressure the scheduler may evict a running sequence and recompute its prefill later, which shows up as a long stall partway through a generation.

Chunked prefill, and the trade it makes

The fix for prefill interference is to stop treating a prompt as one indivisible pass. Chunked prefill — sometimes called split-fuse — cuts a long prompt into fixed-size pieces and schedules one piece per iteration alongside the ongoing decodes, so a giant prompt costs every streaming user a small slice of each step rather than one enormous pause.

It is a genuine trade, not a free win: the long prompt’s own time to first token gets worse, because its prefill is now spread over many iterations and shares the device. Servers that expose the knob let an operator choose which side of that trade to be on. If you are on a hosted API you do not choose, which is one more reason two providers of the same model behave differently.

What a client can do about it

Very little inside a single request, and quite a lot around it.

• Set max_tokens to what you actually need. Some schedulers reserve KV capacity against it, so an inflated value can cost you admission priority you did not need to spend.
• Treat mid-stream stalls as normal and use an inter-token stall timeout rather than one overall deadline — see choosing a timeout.
• Measure percentiles, never means. Queueing produces a long right tail by construction, and a mean of a long-tailed distribution describes nobody’s experience.
• Have a second endpoint. Admission delay is the one term you cannot optimise and can entirely sidestep by sending the request somewhere less busy.