Continuous batching (iteration-level scheduling), explained

Continuous batching (also called iteration-level scheduling or in-flight batching) is the scheduling policy at the heart of every modern LLM server. Instead of collecting a batch of requests, running it until the longest one finishes and only then starting the next, the server re-forms the batch at every forward pass: finished sequences leave immediately, waiting requests join as soon as there is room, and the GPU never decodes padding on behalf of a request that has already returned. It sits one layer above the kernels (PagedAttention, FlashAttention) and one layer below the policies that refine it (chunked prefill, prefill/decode disaggregation, speculative decoding). If you serve a fine-tuned model, it is the single largest lever on cost per token you will pull, and it is on by default in vLLM, SGLang and TensorRT-LLM.

Where it came from#

The idea was published as iteration-level scheduling in Orca (Yu, Jeong, Kim, Kim and Chun, OSDI 2022). Before Orca, transformer serving systems inherited the request-level batching of image classifiers: a batch was a fixed set of requests, and the engine returned results only when the whole batch was done. The Orca authors pointed out the two consequences for autoregressive generation: requests that finish early cannot return, and requests that arrive late wait for the entire running batch. Their fix was to let the scheduler hand the engine a single iteration at a time and rebuild the batch between iterations. On GPT-3 175B they reported 36.9 times the throughput of FasterTransformer at the same latency level.

Iteration-level scheduling created a new difficulty: requests in one batch are at different positions, with different prompt lengths and different numbers of cached tokens, so their tensors do not line up. Orca's answer was selective batching: flatten all tokens from all requests into one ragged batch for the matrix multiplications (QKV projection, MLP, output projection), which do not care which request a token belongs to, and split back into per-request work only for attention. Every modern engine still does exactly this, with variable-length attention kernels in place of Orca's split. The other missing piece was memory. Orca reserved KV cache for the maximum length of each request, which wasted most of it; vLLM's PagedAttention (Kwon et al., 2023) allocated the cache in fixed-size blocks on demand, which is what let continuous batching run at the batch sizes where it pays off. vLLM reported 2 to 4 times the throughput of Orca and FasterTransformer at the same latency.

The bottleneck it attacks: decode is memory-bound#

A decode step generates one token for each of the $b$ sequences in the batch. For a dense model with $N$ parameters stored in 16-bit precision, the step must stream every weight from HBM once, about $2N$ bytes, plus the KV cache of every sequence. It performs about $2N$ floating-point operations per token. Writing $B_W$ for achievable memory bandwidth, $F$ for achievable compute throughput, $c_i$ for the context length of sequence $i$ and $\kappa$ for KV bytes per token, a roofline estimate of the step time is

The weight term does not depend on $b$. That is the whole economic argument for batching: the 16 GB of an 8B model must be read whether one sequence or two hundred benefit from it. The compute term only catches up when $b$ approaches the ridge point $F/B_W$. For an H100-class GPU with 3.35 TB/s and 989 dense bf16 TFLOP/s, that ratio is about 295 FLOP per byte, and since a bf16 decode token does 2 FLOPs per 2 bytes of weight, arithmetic intensity is roughly $b$ FLOP per byte. Below a batch of a few hundred, decode is bandwidth-bound and throughput scales almost linearly with batch size. Our roofline article derives this in more detail.

The solid curve in Figure 1 is the one that matters in practice. At batch 1 the model produces 153 tokens per second; at 64 it produces 6,400; at 256 it produces 12,450, an 81-fold gain for 3.1 times the step latency (20.6 ms instead of 6.5 ms). The catch is that you only get those batch sizes if the scheduler keeps the batch full, and with autoregressive generation that is exactly what static batching cannot do.

Why static batching wastes the batch

Output lengths vary by an order of magnitude between requests. Under static batching, each of the $B$ slots in a batch is occupied for ${\max }_j{o}_j$ steps, where $o_j$ is the output length of request $j$, but does useful work only for $o_i$ of them. The fraction of slot-steps that produce a returned token is

The expected maximum grows with $B$, so larger static batches waste more. For a lognormal output-length distribution with mean 248 tokens (the workload used below), Monte Carlo gives $\mathbb{E}[\max ]$ of 481, 812 and 1,210 tokens for $B=4,16,64$, so $\eta$ is 0.51, 0.31 and 0.20. Four out of five decode slots in a 64-wide static batch are padding. Continuous batching makes $\eta$ approximately 1 by construction, and in addition removes the queueing delay of waiting for a batch boundary.

How it works, step by step#

A continuous-batching engine runs a loop. Every iteration it asks the scheduler for a set of sequences and a number of tokens for each, executes one forward pass over the flattened tokens, samples, and hands results back.

running, waiting = [], deque()
while True:
    waiting.extend(new_arrivals())
    # 1. retire finished sequences and free their KV blocks
    for seq in [s for s in running if s.finished]:
        kv.free(seq); running.remove(seq); stream_done(seq)
    # 2. admit waiting requests while there is room (slots and KV blocks)
    while waiting and len(running) < max_num_seqs and kv.can_allocate(waiting[0]):
        seq = waiting.popleft(); kv.allocate(seq.prompt_len); seq.needs_prefill = True
        running.append(seq)
    # 3. if a decode cannot grow its KV, preempt the newest sequence (recompute later)
    while not kv.can_append(running):
        victim = running.pop(); kv.free(victim); waiting.appendleft(victim)
    # 4. one forward pass over a ragged batch: whole prompts for new sequences, 1 token for others
    tokens = [s.prompt if s.needs_prefill else [s.last_token] for s in running]
    logits = model.forward_ragged(tokens, kv)          # selective batching
    for s, l in zip(running, logits):
        s.append(sample(l, s.params)); s.needs_prefill = False
        s.finished = s.hit_eos() or s.hit_stop() or len(s.output) >= s.max_tokens

Three details make or break the loop. First, admission is gated by KV-cache capacity, not only by a slot count, because a sequence's memory grows by $\kappa$ bytes per generated token and nobody knows the final length in advance. Second, when the cache runs out mid-generation, something must give: vLLM preempts the most recently admitted sequence and later recomputes its prefix, while older designs swapped KV blocks to CPU memory. Third, step 4 mixes prompt processing (prefill) with decoding. In the simplest form shown here, and in Orca, a new request's whole prompt enters the same pass as other requests' single decode tokens; vLLM's original scheduler instead ran prefill-only iterations whenever requests were waiting. Either way, one long prompt makes that iteration slow for everyone in it. That stall is what chunked prefill fixes, and it shows up clearly in the simulation below.

Worked example by hand#

Take the eight requests in Figure 2 and a GPU that can decode four sequences per step. Their outputs total $8+2+3+1+3+4+2+5=28$ tokens.

Static. The first batch is A, B, C, D, which runs for $\max (8,2,3,1)=8$ steps. The second batch is E, F, G, H, which runs for 5. Total 13 steps, or 52 slot-steps, of which 28 do useful work: $\eta =28/52=54\%$. Every request in the first batch completes at step 8, every request in the second at step 13, so the mean completion time is $(4\times 8+4\times 13)/8=10.5$ steps.

Continuous. When D finishes after step 1, E takes its slot; when B finishes after step 2, F joins; when C finishes after step 3, G joins; when E finishes after step 4, H joins. A finishes at 8, H at 9. Total 9 steps, $\eta =28/36=78\%$ (the last steps have empty slots only because the queue ran dry), and completion times are 8, 2, 3, 1, 4, 6, 5, 9 with mean 4.75 steps. The same hardware returns results 2.2 times sooner on average and finishes the whole set 31% faster, with no change to the model or kernels.

Capacity math: Little's law and GPU-seconds per request#

Two formulas tell you what a continuously batched server can sustain. The first is Little's law applied to the decode phase. If requests arrive at rate $\lambda$ and each spends $\mathbb{E}[o]$ iterations decoding, the steady-state number of sequences in the batch is

With the linear fit $t(b)\approx a+\gamma b$ (in our model $a=6.47$ ms and $\gamma =0.055$ ms per extra sequence at 1,125-token contexts), this solves to $b=\lambda \mathbb{E}[o]a/(1-\lambda \mathbb{E}[o]\gamma )$. At $\lambda =10$ requests per second and $\mathbb{E}[o]=248$, decoding alone needs a batch of about 18. The batch size is an output of the arrival rate, not a setting: max_num_seqs only caps it.

The second formula counts GPU time. Each request costs its prefill plus its share of every decode step it rides in:

where $p$ is the prompt length. For our workload (mean prompt 1,001 tokens, mean output 248), the mean prefill costs 28.3 ms and, at a full batch of 256, each decoded token costs 0.080 ms of GPU time, so $\mathbb{E}[\tau ]=28.3+248\times 0.080=48.2$ ms and the server tops out near 20.8 requests or 5,140 output tokens per second. Note what dominates: at a full batch, prefill is 59% of the GPU time even though prompts are only four times longer than outputs. Long-prompt workloads (RAG, agents with big tool schemas) are prefill-bound under continuous batching, which is why prefix caching matters so much for them.

Simulated numbers: static vs continuous#

To put numbers on this we wrote a seeded discrete-event simulator (Python, about 200 lines) that uses the step-time model of Figure 1 and replays Poisson arrivals with lognormal prompt lengths (mean 1,000, clipped to 32 to 8,192) and lognormal output lengths (mean 250, clipped to 8 to 2,048). Static batching pads prompts and outputs to the longest in the batch, as a naive generate() loop does, and dispatches as soon as the GPU is free with up to $B$ waiting requests. Continuous batching admits up to 256 sequences and runs whole prompts in prefill-only iterations, like vLLM's original scheduler. Each point is 1,500 requests with the first 10% discarded as warm-up. All of this is a model with stated assumptions, not a benchmark of any engine.

Static batching saturates at about 400 to 420 output tokens per second with either $B=16$ or $B=64$: the bigger batch amortises weights better but pads more, and the measured slot efficiency was 0.30 and 0.21, matching the $\eta$ formula. Continuous batching kept latency nearly flat to 16 requests per second and saturated at about 4,350 tokens per second, roughly 85% of the 5,140 bound from the GPU-seconds formula (the gap is iterations where the batch is not full and prefill-only iterations that stall decodes). That is a 10.5 times capacity difference on identical hardware and kernels. Orca's 36.9 times was measured against a different baseline, but the mechanism is the same.

One number in the simulation is a warning rather than a win. With prefill-only iterations, the p99 gap between two consecutive tokens of the same request was 196 ms at 16 requests per second and 294 ms at 20, against a median time per output token of 20 to 36 ms. Those are decode stalls: every time a long prompt is admitted, everyone else's next token waits for it. Continuous batching fixes throughput and time to first token; it does not by itself fix token-to-token smoothness.

Interaction with fine-tuned and post-trained models#

Output length distribution. Continuous batching is most valuable when output lengths are spread out, and post-training changes that spread. Reasoning models trained with GRPO or RLVR emit long, highly variable chains of thought, which makes static batching even worse and pushes KV memory into preemption territory. A narrow classifier fine-tune that answers in five tokens is the opposite: decode is short and the server becomes prefill-bound.

Stop tokens and chat templates. A fine-tune that never emits the end-of-sequence token the server expects (a template mismatch, a tokenizer with a new special token not registered as a stop token, an SFT set whose targets lack the EOS) runs every request to max_tokens. Under continuous batching this is not just slow for that request: it pins a slot and its KV for the whole budget, shrinking everyone's effective batch. Watch the share of requests finishing with reason length after every new checkpoint.

LoRA adapters. Many fine-tunes are served as adapters over a shared base. Continuous batching across adapters requires kernels that apply a different low-rank update to each row of the ragged batch, which is what Punica (Chen et al., 2023) and S-LoRA (Sheng et al., 2023) introduced. Engines cap the number of distinct adapters in one batch (vLLM's max_loras), so a request for an adapter outside the active set waits even when slots are free. The trade-off between serving adapters and merging them is covered in multi-LoRA serving and LoRA: merge vs adapter.

Quantised fine-tunes. Halving the weight bytes with 4-bit or 8-bit weights lowers the constant $a$ in $t(b)$ but not the KV term $\gamma$, so at large batches the benefit shrinks unless the KV cache is also compressed (KV-cache compression, FP8 KV).

Evaluation reproducibility. Batch composition can change the order of floating-point reductions in some kernels, so the exact result for one request may depend on what else is in the batch, and therefore on server load. vLLM documents this and offers an opt-in batch-invariant mode (the VLLM_BATCH_INVARIANT setting, currently beta) whose stated purpose is outputs that are deterministic and independent of batch size and request order, motivated among other things by reproducible RL rollouts. If you compare a base and a fine-tuned model on a served endpoint, small differences at temperature 0 may be scheduling noise, not training; enable batch invariance or evaluate offline with a fixed batch.

Tuning knobs#

Tune with a load generator that replays your real prompt and output length distribution, not fixed lengths. Sweep the arrival rate, plot TTFT, TPOT and throughput as in Figure 3, and pick the operating point where your latency SLO still holds. Our latency SLO tuning article walks through the procedure, and utilisation and batching economics turns the resulting tokens per second into cost.

Failure modes and how to spot them#

Preemption thrash. When KV memory is oversubscribed, sequences are evicted and recomputed, and recomputation costs a full prefill. Symptoms: throughput falling as load rises, a non-zero preemption counter, rising p99 end-to-end latency. Fixes: more KV memory (higher utilisation, FP8 KV, tensor parallelism), a lower max_num_seqs, or a smaller max_model_len.

Decode stalls. p99 inter-token latency several times the median, with spikes that line up with long prompts arriving. Fix with chunked prefill or by separating prefill and decode onto different GPUs.

Queueing collapse. Past saturation, waiting time grows without bound while throughput stays flat (the right edge of Figure 3). The server cannot fix this; admission control, rate limits, or more replicas can.

Runaway generations. Requests hitting max_tokens because of missing stop tokens or a degenerate repetition loop in a fine-tune. They look like an unexplained drop in batch efficiency.

Adapter churn. With many LoRA adapters and a small active set, requests queue for adapter loads. Watch per-adapter queue time, not only global TTFT.

When it helps, and when it does not#

Implementation sketch#

You rarely implement this yourself: vLLM, SGLang and TensorRT-LLM all ship it. A typical vLLM configuration for a fine-tuned 8B model with optional adapters:

from vllm import LLM, SamplingParams

llm = LLM(
    model="path/to/your-finetuned-8b",   # merged weights; or base + enable_lora=True
    max_num_seqs=256,                    # cap on concurrent sequences per iteration
    max_num_batched_tokens=8192,         # token budget per iteration
    gpu_memory_utilization=0.90,         # weights + KV blocks
    max_model_len=8192,                  # longest context you actually need
)
params = SamplingParams(temperature=0.7, max_tokens=1024, stop_token_ids=[128009])  # set your template's stop ids
outputs = llm.generate(prompts, params)   # the engine batches continuously under the hood

If you want to see the mechanism, the core of a toy engine with Hugging Face models is short: keep a per-sequence KV cache, call the model on a list of sequences with different lengths via a padded attention mask, and rebuild the list every step. It will be slow because padding wastes compute, which is exactly why production engines use ragged batches and paged KV. In POFE, evaluation and RL rollouts run on a continuously batched engine, so the throughput numbers you see in a run's logs reflect this policy, not batch-at-a-time generation.

Further reading#

Yu et al. (2022) is the primary source and still the clearest statement of iteration-level scheduling and selective batching. Kwon et al. (2023) explains why KV memory management is the precondition for large continuous batches. Agrawal et al. (2024) analyse the throughput-latency trade-off that remains and introduce stall-free scheduling. Sheng et al. (2023) treat fairness, and Punica and S-LoRA extend batching across adapters.

Frequently asked questions#

References#

1. Gyeong-In Yu, Joo Seong Jeong, Geon-Woo Kim, Soojeong Kim, Byung-Gon Chun (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models. www.usenix.org/conference/osdi22/presentation/yu
2. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, Ion Stoica (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention. arxiv.org/abs/2309.06180
3. Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S. Gulavani, Alexey Tumanov, Ramachandran Ramjee (2024). Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve. arxiv.org/abs/2403.02310
4. Lequn Chen, Zihao Ye, Yongji Wu, Danyang Zhuo, Luis Ceze, Arvind Krishnamurthy (2023). Punica: Multi-Tenant LoRA Serving. arxiv.org/abs/2310.18547
5. Ying Sheng, Shiyi Cao, Dacheng Li, Coleman Hooper, Nicholas Lee, Shuo Yang, Christopher Chou, Banghua Zhu, et al. (2023). S-LoRA: Serving Thousands of Concurrent LoRA Adapters. arxiv.org/abs/2311.03285
6. Ying Sheng, Shiyi Cao, Dacheng Li, Banghua Zhu, Zhuohan Li, Danyang Zhuo, Joseph E. Gonzalez, Ion Stoica (2023). Fairness in Serving Large Language Models. arxiv.org/abs/2401.00588
7. vLLM project (2025). vLLM documentation: Optimization and Tuning (chunked prefill, preemption). docs.vllm.ai/en/latest/configuration/optimization.html
8. vLLM project (2025). vLLM documentation: Batch Invariance. docs.vllm.ai/en/latest/features/batch_invariance.html

Related reading