The Batch Never Waits

A conventional batch is a photograph: collect requests, run them together, wait for the group to finish.

Autoregressive language-model inference is a film. One sequence may stop after two output tokens. Another may generate two hundred. New requests arrive while both are running. If the serving engine treats the group as immutable, finished slots sit empty behind the longest sequence.

Continuous batching changes the unit of scheduling. At the boundary between model iterations, completed sequences leave and eligible waiting sequences enter. The active batch evolves token by token.

That simple mechanism is why modern serving engines can keep accelerators busier under variable-length traffic. It is also why the scheduler becomes part of product behavior. Every iteration asks who gets memory, compute, and time next.

Decode is iterative, so request-level batches waste slots

After prompt processing, or prefill, an autoregressive model produces output sequentially. At each decode iteration it consumes each active sequence's latest token and KV state, computes logits, selects a next token, and appends new KV state. A sequence leaves when it emits a stop token, reaches a limit, is cancelled, or fails.

Orca made iteration-level scheduling a central serving design. Rather than schedule an entire request as one indivisible job, its scheduler invokes one model iteration for the current batch. Selective batching handles transformer operations whose inputs do not all behave the same way.

The distinction can be expressed as two loops.

Static request batch:

batch = wait_until_batch_ready(queue)
while any request in batch is unfinished:
    run_one_decode_step(batch)
return all results

Continuous batch:

while serving:
    retire_finished(active)
    release_their_KV_blocks()
    admit_waiting_requests(active, free_memory, policy)
    run_one_model_iteration(active)

Real engines fuse operations, overlap work, schedule prefills, distribute model layers or tensors, and manage asynchronous output. The pseudocode exposes the policy boundary: admit_waiting_requests decides the service users experience.

A four-request trace

Consider two available sequence slots. To isolate decode scheduling, assume all prefills are already complete.

Request	Arrival step	Required output steps
A	0	8
B	0	2
C	1	3
D	3	1

Under a rigid policy, A and B form the first batch. B finishes at step 2, but its reserved slot remains empty while A runs through step 8. C and D then form a second batch. Their completion steps are 11 and 9 respectively. Mean flow time from arrival is 6.5 token steps.

Under continuous replacement, C enters after B retires. D enters after C retires. Completion occurs at steps 8, 2, 5, and 6. Mean flow time is 4.25 steps.

In this simplified accounting, static batching performs 16 useful request-steps across 22 available slot positions, or 72.7 percent occupancy. Continuous batching performs 14 useful request-steps across 16 available positions, or 87.5 percent. The totals differ because D overlaps A rather than consuming a later batch step.

This is not a GPU benchmark. A token step does not take constant wall time across batch sizes. The trace omits prompt work, memory limits, scheduling overhead, kernels, padding, and transfer. It demonstrates one mechanism only: a short request no longer reserves capacity until its longest batch peer finishes.

A live batch is constrained by KV memory

Why not admit every waiting sequence? Each active sequence needs KV-cache storage that grows with its tokens. The model weights, runtime workspace, adapters, and temporary activations also occupy accelerator memory.

The scheduler therefore has at least two budgets:

compute budget for the next iteration
memory budget for all admitted sequence state

PagedAttention manages KV state in blocks inspired by virtual memory. Reducing fragmentation and enabling sharing can fit more useful sequences into a batch. It does not remove the admission decision. When blocks are scarce, the engine must delay, preempt, swap, recompute, reject, or reserve headroom.

Future length is unknown. A request with a maximum of 4,096 output tokens might stop after 30 or continue for all 4,096. Reserving the maximum wastes memory. Reserving only current state risks later pressure. Paging permits incremental allocation, but an overloaded system still needs a policy for the next block.

Track admission failures separately from compute saturation:

• requests waiting for a KV block;
• preemptions and recomputed tokens;
• swapped bytes and transfer time;
• cache eviction caused by admission;
• batch size at each iteration;
• unused memory held as safety reserve.

An apparently idle GPU may be blocked on memory state, data movement, or a scheduling barrier.

Prefill and decode compete inside the same engine

Continuous batching is often described through decode replacement, but new requests first require prefill. Prefill processes the prompt, commonly in a large parallel operation. Decode advances active sequences one token at a time and users notice gaps between those tokens.

Admitting a 50,000-token prompt as one prefill can occupy the device long enough to stall decodes already in flight. The batch is technically busy while streaming quality degrades.

Sarathi-Serve splits large prefills into chunks and constructs schedules that combine bounded prefill work with decode work. The mechanism trades a single long interruption for smaller controlled pieces. Chunk size influences prefill completion, decode cadence, kernel efficiency, and scheduling overhead.

An illustrative token budget per iteration might be:

iteration token budget: 2,048
active decode tokens:      160  (one per active sequence)
available prefill chunk: 1,888

The numbers are configuration inputs, not universal defaults. A small chunk protects time-per-output-token but can fragment prefill and reduce efficiency. A large chunk finishes prompts sooner but risks decode stalls.

DistServe takes a different boundary by placing prefill and decode on separate GPU pools and optimizing goodput under time-to-first-token and time-per-output-token objectives. Separation reduces direct phase interference but adds KV transfer, network, placement, and pool-sizing concerns.

Neither “co-locate” nor “disaggregate” is a default answer. Workload shape and SLO decide.

Throughput and latency pull the scheduler in different directions

Larger batches often use parallel hardware more efficiently. Waiting to form or grow a batch, however, delays individual requests. Admitting more work can increase aggregate tokens per second while worsening TTFT or TPOT.

This produces a policy surface, not one optimum:

Objective	Scheduler tendency	Failure if over-optimized
throughput	keep batches large	queue and token latency rise
TTFT	admit new prefills quickly	active decodes stall
TPOT	protect decode cadence	new prompts wait
completion latency	favor short remaining jobs	long jobs starve
prefix locality	group shared prefixes	other tenants wait
fairness	balance charged service	hardware locality declines
deadline goodput	prioritize feasible deadlines	best-effort work gets displaced

Peak throughput is meaningful only with the latency point at which it was obtained. Use the goodput definition from Capacity Is a Queue: completed requests per unit time that satisfy the named SLOs.

First come is not automatically fair

Imagine two continuously backlogged tenants.

• Tenant X submits 100 requests of 20 total tokens.
• Tenant Y submits 10 requests of 2,000 total tokens.

Giving each tenant the same number of request admissions does not give them the same amount of model service. Counting output tokens alone also omits prompt cost. Equal wall time can be difficult to attribute when sequences share batched operations.

Fairness in Serving Large Language Models formalizes fairness using a cost function that accounts for input and output token work and proposes Virtual Token Counter, a work-conserving scheduler. The paper supplies a rigorous model and evaluated algorithm. A product must still choose the fairness domain:

• per end user, API key, tenant, workflow, or paid class;
• equal or weighted shares;
• whether cached prompt work is charged;
• how retries and speculative branches count;
• how unused entitlement can be borrowed;
• what urgent traffic may preempt.

Fairness is not synonymous with identical latency. A weighted enterprise class and a best-effort batch class can be fair under their explicit contract. Hidden noisy-neighbor behavior is not.

Head-of-line blocking moves inside the token scheduler

Continuous batching removes one form of head-of-line blocking: a short completed sequence need not wait for a long batch peer before its slot is reused. Other forms remain.

• A long prefill can block decode iterations.
• A large request can hold KV memory across many steps.
• First-come-first-served can place an infeasible-deadline request before feasible work.
• Strict priority can starve lower classes.
• Prefix-local scheduling can favor a hot prompt family.
• An agent can issue many parallel calls and occupy a tenant's entire share.

Preemption can help but has a bill. Discarded KV state requires recomputation. Swapping state consumes bandwidth and adds latency. Pausing a tool-using agent may hold external resources. Record the reason and full rework for every preemption.

The gateway and orchestrator should cooperate with the engine. A cancelled user task must cancel losing inference branches. A deadline should reach the scheduler rather than expiring silently upstream. Retry policy should avoid resubmitting into the same overloaded route.

Cancellation and backpressure are scheduler inputs

An agent may launch three candidate calls and accept the first verified answer. The other two calls become waste as soon as the winner commits. If cancellation stops at the orchestrator while their sequences remain active, the engine continues allocating KV blocks and decode steps to outputs nobody will use.

Cancellation needs an identity that survives every hop:

user task -> workflow run -> model attempt -> engine request -> active sequence

The engine should distinguish a request cancelled while queued, during prefill, and during decode. Each state releases different resources and produces different wasted-work metrics. Record tokens computed after the cancellation signal, not only requests eventually labelled cancelled. This “cancellation lag” reveals buffering and propagation failures.

Deadlines should also be absolute timestamps, not a fresh timeout at each service. A request with 80 milliseconds remaining should not enter a 200-millisecond prefill merely because the engine received a new local timeout. Admission can reject it, route it to a feasible smaller model, degrade context, or return a controlled partial result according to product policy.

Backpressure tells upstream components not to create work the route cannot finish usefully. Useful signals include bounded queue capacity, estimated start time, deadline feasibility, per-tenant token debt, and retry-after guidance. The orchestrator can then reduce parallel branches, defer background evaluation, or choose a cheaper route.

Uncoordinated retries create positive feedback:

overload -> timeout -> retry -> higher arrival rate -> deeper overload

Use capped exponential backoff with jitter where retries are safe, but do not treat it as a substitute for admission control. Side-effecting requests also need idempotency so a transport timeout does not duplicate an action.

This feedback loop is why scheduler telemetry belongs at the task level. A route may report respectable token throughput while completing fewer verified tasks because it spends capacity on cancelled branches, infeasible deadlines, and repeated attempts.

A benchmark that can answer a product question

A continuous-batching benchmark needs more than a request count and a model name.

Declare:

model revision and numerical format
hardware, topology, runtime, and configuration
arrival process and burst pattern
prompt-token distribution
requested and observed output-token distribution
number of tenants and weights
prefix-sharing distribution
sampling and stop conditions
warm/cold KV and prefix state
TTFT, TPOT, completion, and deadline objectives

Report at least:

• offered requests and tokens per second;
• accepted, rejected, cancelled, and completed requests;
• p50, p95, and p99 TTFT, TPOT, and completion latency;
• SLO goodput;
• iteration duration and active sequence count over time;
• KV occupancy, allocation failures, swaps, and recomputation;
• per-tenant charged service and latency;
• output quality or verified outcome rate if scheduling changes context or fallback.

Use an open-loop load generator when testing overload. A closed-loop client that waits for each response before issuing the next request reduces offered load as the system slows, concealing queue growth.

Test at least four workloads: short uniform chat, mixed short and long outputs, long-prefill retrieval, and bursty agent fan-out. The scheduler that wins one can lose another.

A builder playbook

1. Trace one iteration

Capture queued requests, active sequences, admitted prefills, decode tokens, KV blocks, iteration duration, completions, and preemptions. Link the spans to the end-to-end request path in From Prompt to Proof.

2. Separate queue time from execution time

TTFT includes gateway wait, engine queue, prefill, and first decode. If only model execution is measured, a scheduler can look faster while users wait longer.

3. Define the policy in product terms

Write tenant weights, priority classes, maximum queue age, cancellation behavior, deadline admission, preemption cost, and overload rejection. Review these as API behavior, not hidden runtime knobs.

4. Sweep load through the knee

Increase open-loop arrivals while holding workload distribution fixed. Plot throughput and SLO goodput together. The useful capacity point is before goodput falls, not where raw token emission peaks.

5. Change one scheduler dimension at a time

Sweep maximum batched tokens, maximum sequences, prefill chunk size, scheduling discipline, and preemption mode independently first. Mixed changes make causal diagnosis hard.

6. Price the outcome

Higher utilization can reduce accelerator cost per token yet increase retries, abandonment, and deadline failures. Feed verified completions, not emitted tokens, into Cost per Successful Outcome.

The decision

Continuous batching is the right mental model for shared autoregressive inference because sequence membership changes at token boundaries. It extracts useful parallel work from variable request lengths. It does not make scheduling neutral.

Choose the policy that maximizes verified SLO goodput for the real workload while satisfying explicit tenant and priority contracts. Then keep enough trace detail to explain every admission, stall, preemption, and rejection.

The serving engine is not merely turning prompts into tokens. At every iteration, it is deciding whose automation moves forward.

References

• Orca: A Distributed Serving System for Transformer-Based Generative Models, Yu et al., OSDI 2022. Establishes iteration-level scheduling and selective batching for transformer generation.
• Efficient Memory Management for Large Language Model Serving with PagedAttention, Kwon et al., SOSP 2023. Connects dynamic batching capacity to block-based KV-cache management.
• Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve, Agrawal et al., OSDI 2024. Introduces chunked prefills and stall-free schedules.
• DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving, Zhong et al., OSDI 2024. Frames serving capacity through simultaneous TTFT and TPOT objectives.
• Fairness in Serving Large Language Models, Sheng et al., OSDI 2024. Formalizes token-aware service fairness and proposes Virtual Token Counter.

The scheduler trace and occupancy values are illustrative. The exact inputs and calculations are retained in the claim ledger.