Continuous batching: the salon with 8 chairs that does not wait for the slow customer — Orca, vLLM, chunked prefill and goodput

· By José Manuel Román
Contents

This post complements those on KV cache (the artefact continuous batching manages), PagedAttention (the memory piece that makes it viable), Disaggregated serving (the next layer of optimisation), Speculative decoding, Multi-LoRA and MoE (the three extensions that coexist with the scheduler in production).

You are here: DEPLOY

You are here: DEPLOY · iterative scheduler, one piece below PagedAttention1 · Data2 · Tune3 · Eval4 · Deploy5 · Observe6 · Retrain

TL;DR

The static batching of the original HuggingFace Transformers (the pre-2022 era) systematically under-used the GPU for two structural reasons. First: the scheduling unit was the complete request; the longest one in the batch blocked all the others until it finished (severe head-of-line blocking, P95 TTFT five to ten times worse than reasonable). Second: each batch slot reserved memory for max_seq_len even though the real output was much shorter; documented padding waste sat between 60 % and 80 % and sustained GPU SM utilisation on real workloads fell to 20-40 %. Orca (Yu et al., OSDI 2022, FriendliAI + Seoul National University) introduced the idea that unjammed everything: the scheduling unit stops being the request and becomes one decoder iteration, a single token. After each iteration the scheduler can add new requests to the batch and remove the finished ones. vLLM (Kwon et al., SOSP 2023, UC Berkeley) materialised it open-source and production-grade thanks to PagedAttention, which solves the KV cache fragmentation that theoretical continuous batching would cause with dynamic allocation. SARATHI / Sarathi-Serve (Microsoft Research India, OSDI 2024) closed the last gap: the prefill stalls that paused active decodes when a new request arrived, via chunked prefill (splitting a long prefill into small chunks and mixing them with decodes in the same step) and stall-free batching. DistServe (Zhong et al., OSDI 2024) reformulated the key metric: what matters is goodput (requests/s meeting the TTFT and TPOT SLOs), not raw throughput. In May 2026, vLLM v1 brings a unified scheduler with chunked prefill always-on; SGLang adds RadixAttention, which gives cross-request prefix-cache hits; TensorRT-LLM calls it in-flight batching; llama.cpp supports it natively. The three operational tensions are speculative decoding (nested raggedness), multi-LoRA (each request with its adapter) and MoE (each expert sees very few tokens per step at a typical batch size). This post takes apart the mechanism, the maths (GPU utilisation, goodput vs throughput), the three variants (Orca → vLLM → Sarathi-Serve), the pitfalls (preempt-on-OOM, starvation, inverse HoL) and the real numbers with production configurations.

The analogy: the salon with 8 chairs

A hair salon with 8 chairs and a single brilliant stylist who moves between them. Customers arrive with very different needs: some want a 15-minute cut, others a 2-hour colour with a base, others a 90-minute straightening. The question is how to organise the flow.

The traditional strategy (what HuggingFace Transformers did in its original generate()) is to seat 8 customers at once, all at the same time, and accept nobody new until the last one finishes. If one of those 8 is a 2-hour job, the 7 who wanted the 15-minute cut sit there doing nothing for 1 hour and 45 minutes. The stylist finishes with the quick ones and is left staring at empty chairs until the colour is done. When everyone is ready, another 8 come in. That is static batching, and the only thing that stops it from being worse is that the GPU does not complain like a human customer.

The continuous strategy (Orca, vLLM) changes the scheduling unit. The stylist does not think “I am going to do one whole customer and then the next”; he thinks “on each tick I take one step of work at every occupied chair and, every time a chair frees up, I call the next customer in the queue without waiting for the others to finish”. The quick-cut customer leaves after 15 minutes, his chair is filled immediately with the next one, and the slow jobs proceed at their own pace without delaying anyone. The stylist is never idle.

The continuous strategy with chunked prefill (SARATHI / Sarathi-Serve) adds a subtler distinction. Some customers need a long initial phase (a 10-minute hair analysis before the cut; in LLM terms, the prefill of the prompt). Without chunked prefill, the stylist had to stop all the other chairs to do the new customer’s analysis in one go, and that was a stall visible in the TPOT of the active ones. With chunked prefill, the analysis is split into 2-minute pieces interleaved between the other customers’ active cuts. The customers already under way no longer notice pauses; the new customer takes slightly longer to start his cut proper, but the whole salon does not freeze.

And the metric that matters: the owner does not want to maximise “customers served per hour” at the cost of some leaving furious. He wants to maximise “customers served per hour within the time SLA”, and that is goodput, DistServe’s contribution.

The problem continuous batching solves

There are two structural pathologies of static batching that deserve to be explained with concrete numbers.

Padding waste. Each batch slot reserved memory for max_seq_len (prompt + max output), even though the real output ended in far fewer tokens. For a batch of 32 with heterogeneously distributed output lengths (half of them ≤50 tokens, a long tail up to 4,000), the typical memory waste was 60-80 %. That translated directly into wasted concurrency: with the same VRAM, instead of serving 32 requests with smart allocation, you served 8.

HoL blocking (Head-of-Line). The scheduling unit was the complete request. A batch containing one request of 500 tokens and 31 of ≤50 tokens ran 450 extra “empty” iterations (the GPU executed forward passes for all 32 slots, even though 31 had already finished). Wasted compute cost: ~84 % of the tail time in the example.

Measurable result. Sustained GPU SM utilisation on real workloads under static batching: 20-40 %. That is, ~70 % of the datacenter’s compute went unused. When the first Orca and vLLM benchmarks came out showing 10-24× throughput improvement, it was not marketing exaggeration; it was recovering all that wasted compute.

Orca (OSDI ‘22): the idea that changed everything

The paper by Yu, Jeong, Kim, Kim and Chun at OSDI 2022 (“Orca: A Distributed Serving System for Transformer-Based Generative Models”, from Seoul National University + FriendliAI) introduced two contributions that have remained the basis of everything that followed.

Iteration-level scheduling. Instead of scheduling at the level of the complete request, it schedules at the level of one decoder iteration: the step that generates ONE token. After each iteration the scheduler can (a) add new requests to the batch, (b) remove requests that have generated EOS or reached max_tokens, (c) reorder priorities. The compute engine executes exactly one iteration over the current batch.

Selective batching. Here is the non-obvious subtlety. The technical problem with batching requests of different lengths and different KV cache states is that some operations (the GEMMs of the Q, K, V projections and the FFN) are insensitive to position and can be batched by concatenating tokens, whereas attention is sensitive to per-request state (each request has its own KV cache of a different length). Orca’s solution: batch the GEMMs (concatenate all the step’s tokens into a [total_tokens, hidden] tensor) and run attention sequentially per request.

Paper result: up to 36.9× throughput vs FasterTransformer on GPT-3 175B at the same latency level. Orca is not open-source, it is only documented in the paper. FriendliAI commercialises it as the Friendli Engine. But the idea was published and everyone adopted it.

vLLM (SOSP ‘23): the open-source materialisation

What Orca described as a concept, vLLM materialised in production. The paper by Kwon, Li, Zhuang, Sheng et al. (UC Berkeley Sky Computing Lab, SOSP 2023) introduces PagedAttention, covered in detail in the PagedAttention deep dive, but it also consolidates continuous batching as universal practice.

The reason PagedAttention is a prerequisite for practical continuous batching is fragmentation. If you are going to insert and remove requests from the batch dynamically, and each request has a KV cache that grows on every iteration, traditional contiguous allocation fragments the HBM until it is unusable. PagedAttention splits the KV cache into fixed-size blocks (16 tokens by default) allocated on demand from a global pool. Memory waste falls from ~60-80 % to less than 4 % (only the last partially filled block per sequence).

vLLM paper metrics (2023):

  • vs HuggingFace Transformers (static, no continuous batching): up to 24× throughput.
  • vs HuggingFace TGI (which already had primitive continuous batching): ~3.5×.
  • vs FasterTransformer: 2-4× at the same latency.

What operationally distinguishes vLLM from Orca: vLLM runs attention in a single fused CUDA kernel (paged_attention_kernel) over non-contiguous blocks; Orca described attention as sequential, request by request. And vLLM exposes OpenAI-compatible APIs that let you drop the engine into existing stacks without touching the client.

Chunked prefill (SARATHI / Sarathi-Serve, OSDI ‘24)

There is a detail the original Orca/vLLM continuous batching did not solve: when a new request enters the batch, its prefill (processing the whole prompt at once) can take hundreds of milliseconds. During that time, the active decodes of the other requests are essentially paused, the GPU being dedicated to the new prefill. This showed up as spikes in TPOT (“inter-token latency”) every time a long request came in, which broke strict SLAs.

SARATHI (Agrawal et al., arXiv 2308.16369, August 2023) and later Sarathi-Serve (same group at Microsoft Research India, OSDI 2024, arXiv 2403.02310) introduce two combined ideas:

Chunked prefill. A long prefill (8,192 tokens, say) is split into chunks (2,048 tokens, say) processed one per iteration. Instead of one 200 ms step processing 8K tokens, four 50 ms steps processing 2K each.

Decode-maximal batching (“stall-free”). On each iteration, the scheduler first fills the batch with the active decodes (each costing 1 token), and only the leftover space goes to new prefill chunks. The result: active decodes keep advancing 1 token per iteration without pausing, while the new request completes its prefill in small bites.

The observation that justifies it: prefill is compute-bound (it processes N tokens at once and saturates FLOPs) while decode is memory-bound (1 token per step, under-using compute, with the GPU waiting on HBM). Mixing prefill chunks with decodes in the same step exploits the arithmetic-intensity slack: the decodes piggyback on the free compute of the prefill chunk.

Numbers:

  • Original SARATHI (LLaMA-13B on an A6000): decode throughput +10×, end-to-end +1.33×.
  • Sarathi-Serve (Mistral-7B on an A100): 2.6× serving capacity vs plain vLLM. Yi-34B on 2×A100: 3.7×. Falcon-180B with pipeline parallel: 5.6×.

Adoption in May 2026: always-on in vLLM v1 (default since v0.8.0, January 2025), SGLang, TensorRT-LLM. The key setting in vLLM is --max-num-batched-tokens (the token budget per step; default 2048). Raising it prioritises throughput, lowering it prioritises low TPOT.

Goodput: the metric that matters (DistServe, OSDI ‘24)

The classic “throughput” metric (requests/s or tokens/s) has a problem when there are SLOs. A server can report 1,000 req/s while P99 TTFT is 30 seconds and the SLO is 1 second, so only about 200 req/s actually meet the contract.

DistServe (Zhong et al., OSDI 2024) formalises goodput as the right metric: goodput = max sustained request rate meeting the SLOs (TTFT bound AND TPOT bound). The practical definition is usually: maximum rate with ≥90 % of requests within both SLOs.

Why it matters for the scheduler:

  • Optimising raw throughput leads to maximising batch size, which inflates P99 TPOT.
  • Optimising goodput limits the batch size when TPOT starts violating the SLO, prefers small requests if the batch already has a tail, and leaves resources available for new requests.

DistServe result: up to 7.4× more requests served or a 12.6× tighter SLO vs vLLM at the same SLO attainment. The gain comes from disaggregating prefill and decode onto different GPUs (removing the interference between phases), but the idea of optimising for goodput is independent and applicable to any scheduler.

Operationally this translates into monitoring:

goodput_proxy = histogram_quantile(0.95, vllm:time_to_first_token_seconds_bucket) < SLO_TTFT
              AND histogram_quantile(0.95, vllm:time_per_output_token_seconds_bucket) < SLO_TPOT

The iterative scheduler in action

Static batching — 4 slots, padding to max_len, new req arrives → waitsslot 1slot 2slot 3slot 4batch recycled only when ALL finish ↑Continuous batching — a free slot is refilled IMMEDIATELY on each tickslot 1slot 2slot 3slot 4each coloured bar = 1 decoder iteration (1 token) of a requestChunked prefill — new prefill interleaved with active decodes (no stall)prefill chunk 1decode tick, active reqsprefill chunk 2 (same step as the decodes)

The maths that matter

Three formulas explain much of the operational behaviour.

GPU utilisation under static batching. With a batch of size B whose seq_len_i are the real lengths and max(seq_len_i) is the length that defines the padding:

$$U_{\text{static}} = \frac{\sum_i \text{seq len}_i}{B \cdot \max_i \text{seq len}_i}$$

For B=32, 30 sequences of 50 tokens and 2 of 500: U = (30·50 + 2·500) / (32·500) = 2500/16000 = 15.6 %. Four out of every five GPU cycles wasted.

GPU utilisation under continuous batching (idealised).

$$U_{\text{continuous}} \approx 1 - \frac{T_{\text{scheduler}}}{T_{\text{iteration}}}$$

With scheduler overhead of ~50-200 µs and an iteration time of ~10-30 ms: U > 95 %. The unit of loss is no longer padding, it is scheduling overhead, and that is negligible compared with the forward pass.

Goodput vs throughput.

$$\text{Goodput}(R) = R \cdot P(\text{latency} < \text{SLO})$$

where R is the offered request rate. Typical curve: goodput grows linearly with R up to the saturation knee, then falls because P(SLO) collapses when the system congests. The optimal point is just before the knee, not at peak throughput.

Example: at R=100 req/s with P(SLO)=0.99, goodput = 99. At R=200 req/s with P(SLO)=0.4, goodput = 80. More offered load, less useful goodput.

Chunked prefill token budget. On each vLLM step with chunked prefill active:

$$\text{prefill tokens this step} = \text{max num batched tokens} - \text{num decodes active}$$

Each active decode costs 1 token of the budget; the rest is filled with new prefill chunks. If max_num_batched_tokens = 2048 and num_decodes_active = 200, there are 1,848 tokens for prefill (one chunk of 1,848 or several small chunks).

Real implementations in May 2026

EngineCurrent scheduler VChunked prefill defaultRelevant notes
vLLM v1 (default ≥0.8.0)unified V1always-onEngineCore isolated in a separate process; prefix caching with O(1) eviction; preempt-mode recompute by default; xgrammar/outlines backends.
SGLangown (PyTorch ecosystem)yesRadixAttention gives cross-request prefix-cache hits; non-blocking CPU scheduler; leader in stable latency at high concurrency.
TensorRT-LLMproprietary “in-flight batching”yesPolicies GUARANTEED_NO_EVICT (conservative, default) and MAX_UTILIZATION (aggressive, risk of a pause when the KV is full). Compile-time vs runtime.
Triton + tensorrtllm_backendgpt_model_type: inflight_fused_batchingyesmax_queue_delay_microseconds to group newly arrived requests. Decoupled mode for SSE streaming.
llama.cpp (llama-server)own--cont-batching ON since 2024-np N parallel slots; no PagedAttention (contiguous KV per slot), so less flexible but simpler. Endpoint :8080/metrics.

A typical production-ready vLLM v1 configuration:

vllm serve meta-llama/Llama-3.1-70B-Instruct \
  --tensor-parallel-size 4 \
  --max-num-batched-tokens 4096 \
  --max-num-seqs 256 \
  --enable-chunked-prefill \
  --enable-prefix-caching \
  --preemption-mode recompute \
  --scheduling-policy fcfs \
  --gpu-memory-utilization 0.92

SGLang equivalent:

python -m sglang.launch_server \
  --model meta-llama/Llama-3.1-70B-Instruct \
  --tp 4 \
  --chunked-prefill-size 4096 \
  --max-running-requests 256 \
  --enable-radix-cache

The three operational tensions

Continuous batching + speculative decoding. Speculative decoding produces 1 to γ+1 tokens per step depending on the acceptance rate. The batch stops being uniform in tokens produced per iteration: nested raggedness. PagedAttention absorbs it (the KV cache can grow at different rates per request in the same step), but the scheduler loses symmetry. At low QPS (a conversational assistant) the combination is excellent: vLLM reports up to 2.8× speedup. At high QPS, the draft consumes slots from the decode pool and can reduce aggregate goodput. Rule of thumb: disable speculative decoding when gpu_cache_usage > 0.85. Full detail in Speculative decoding.

Continuous batching + multi-LoRA. Each request in the batch can use a different adapter (via SGMV, see Multi-LoRA serving). Worst case: every request in the batch with a different adapter and a different rank, and throughput falls by up to 50 % vs the base with no LoRA. Best case: all requests on the same adapter, equivalent to the base with no LoRA. Practical mitigation: group adapters by rank in the routing ahead of the engine; set --max-lora-rank to the maximum actually served, not generously above it.

Continuous batching + MoE. Each expert sees batch · k / N tokens per step. With DeepSeek-V3 (256 experts, k=8) and batch=32 in decode, each expert processes only 1 token on average: total compute starvation. To match the per-GPU throughput of a dense model, MoE needs batches »10× larger, which puts pressure on the KV cache. Wide-EP (see MoE inference) distributes the experts across many GPUs and allows larger effective batches per expert, at the cost of all-to-all comms that add milliseconds per step.

Metrics to monitor

The Prometheus metrics exposed by vLLM (prefix vllm:, vllm_ when scraped):

  • vllm:time_to_first_token_seconds (Histogram) — TTFT including queue time.
  • vllm:time_per_output_token_seconds (Histogram) — TPOT.
  • vllm:e2e_request_latency_seconds (Histogram) — end-to-end.
  • vllm:num_requests_running (Gauge) — active batch.
  • vllm:num_requests_waiting (Gauge) — queue depth.
  • vllm:num_requests_swapped (Gauge) — preempted to CPU.
  • vllm:gpu_cache_usage_perc (Gauge) — fraction of KV cache occupied.
  • vllm:gpu_prefix_cache_hit_rate (Gauge) — prefix cache hits.
  • vllm:num_preemptions_total (Counter) — preemptions. Any sustained value is a red flag.

Practical operational rules:

  • Stable zone under sustained load: gpu_cache_usage_perc ∈ [0.7, 0.9].
  • Warning at >0.95 (preemption imminent).
  • Critical if num_requests_waiting grows faster than num_requests_running: the server is not absorbing the load; scale out.

Operational pitfalls

Preempt-on-OOM. When gpu_cache_usage reaches ~1.0 with pending requests that need to grow their KV, vLLM preempts. V1 does RECOMPUTE by default (discards the KV, regenerates it on return); V0 did SWAP (moves it to CPU). RECOMPUTE is better for short sequences (cheap to regenerate); SWAP is better for long ones. The vllm:num_preemptions_total metric should be zero or near zero in steady state.

Inverse HoL blocking (memory monopoly). A very long request occupies many KV blocks, so small requests do not fit in the batch even though compute is free. Chunked prefill mitigates the compute blocking during a new prefill, but it does not solve the memory monopoly. Partial solution: per-request limit policies (an aggressive max_tokens) or priorities.

Starvation. FCFS can leave requests pending for a long time if the active ones do not finish. vLLM supports --scheduling-policy priority with an x-priority header. Recent work (NeurIPS 2024 Efficient LLM Scheduling by Learning to Rank, arXiv:2501.14312 Locality-aware Fair Scheduling) proposes schedulers with quantum-based starvation prevention; not yet integrated into vLLM mainline.

Badly calibrated chunk size. A small chunk (512) gives low TPOT, high TTFT and memory overhead from more KV accesses. A large chunk (8192+) gives low TTFT and TPOT spikes during the chunk. Rule: start at 2,048, measure P95 TPOT, adjust.

Batch size cap. A high --max-num-seqs gives more concurrency but P99 TPOT explodes. A low one wastes throughput. Rule of thumb: max_num_seqs ≈ HBM_for_KV / (avg_seq_len × bytes_per_token_KV).

Implications for on-premise hardware

On an RTX 4090 (24 GB). llama.cpp with --cont-batching -np 4-8 is the natural pattern. Typical models: Llama 3 8B Q4_K_M with ~8 parallel slots, aggregate throughput on the order of hundreds of tok/s. vLLM also works if the weights fit (Llama 3 8B BF16 does; the 70B does not fit whole), although PagedAttention on consumer hardware gives less return than in the datacenter.

On a generic 4×H100 SXM cluster (320 GB, NVLink). Here vLLM v1 / SGLang are the de facto standard. Typical configurations:

  • Llama 3 70B FP8 + TP=4: dozens of concurrent sessions with P95 TPOT under 50 ms, tens of thousands of aggregate tok/s at a moderate batch size.
  • Llama 3 70B AWQ-INT4 + TP=2 plus the rest of the cluster for additional concurrency or multi-LoRA with SGMV.
  • DeepSeek-V3 needs larger setups (8-16 H100) to fit whole in FP8; with Wide-EP, continuous batching starts operating on much larger batches and the economics change (see MoE).

The rule of thumb for May 2026: vLLM v1 with chunked prefill always-on and prefix caching enabled is the sensible default configuration for any dense model that fits comfortably; SGLang offers better stable latency at high concurrency thanks to the overlap between the CPU scheduler and the GPU step; TensorRT-LLM gives peak throughput at high concurrency with the rigidity of compile-time.

What we have not covered

  • Locality-aware fair scheduling (arXiv:2501.14312) and learning-to-rank schedulers (NeurIPS 2024): the next generation of algorithms closing the fairness vs prefix-cache locality trade-off.
  • Smooth goodput (arXiv:2410.14257): a refinement of the DistServe metric using max slowdown instead of a binary SLO.
  • Triton tensorrtllm_backend in production: decoupled mode for streaming, ensembles with pre/post-processing, autoscaling with KServe.
  • vLLM speculators v0.3.0 and the vLLM-compatible drafter training framework.

See also

  • The pass: the vLLM scheduler step — the concrete algorithm implementing this batching: the {request: number of tokens} dictionary assembled on each iteration, the max-num-batched-tokens budget and preemption by RECOMPUTE.
  • KV cache: the working memory — the artefact continuous batching manages; without understanding it you cannot see why the minimum unit is the decoder iteration.
  • PagedAttention deep dive — the memory piece without which dynamic continuous batching would fragment the HBM; a deep dive into the block manager.
  • Disaggregated serving: prefill and decode in specialised pods — the next layer: when continuous batching is already squeezed dry, separating prefill and decode gives another round of improvements (origin of the DistServe paper that contributes the concept of goodput).
  • Speculative decoding — the scheduler’s first operational tension: each request in the batch can produce 1 to γ+1 tokens per step.
  • Multi-LoRA serving — the second tension: heterogeneous batching with SGMV lets each request use its own adapter, but the scheduler has to group by rank to keep throughput up.
  • MoE inference — the third tension: each expert sees very few tokens per step at a typical batch size, forcing much larger batches than in dense models.
  • The six-stage LLMOps pipeline — the master map in which Deploy is stage 4.
  • Capacity planning for on-premise LLM inference — the DistServe goodput that appears here is exactly the metric that closes the crossing of VRAM budget × time budget in sizing.
  • GPU observability for LLM inference — the vllm:num_requests_running, num_requests_waiting and gpu_cache_usage_perc metrics that come from the iterative scheduler are the operational cockpit of the engine in production.
  • Optimising prefill in vLLM — chunked prefill translates iterative scheduling into concrete parameters: --max-num-batched-tokens is the budget the scheduler splits between prefill chunks and decode tokens per step.
  • Optimising decode in vLLM — --max-num-seqs and --gpu-memory-utilization are the two dials that determine how many decode slots the scheduler can keep before queueing.
  • LLM autoscaling on Kubernetes — the scheduler queue (num_requests_waiting) is the primary metric for HPA with KEDA on an on-premise cluster.
  • SMs, CUDA streams and CUDA graphs — batching is precisely what amortises the memory bottleneck of decode and exposes the launch bottleneck; that is why batching and CUDA graphs reinforce each other.
  • Serving engine comparison (vLLM/SGLang/TRT-LLM/Dynamo) — where the implementation differences in continuous batching between engines land: the real goodput of vLLM vs SGLang vs TRT-LLM measured with the same harness.

References