--- title: The Batch Never Waits slug: continuous-batching canonical_url: https://blog.openfactoryai.com/continuous-batching published_at: 2026-07-14T20:45:00.289665+00:00 author: OpenFactoryAI tags: continuous batching, LLM serving, GPU scheduling, inference throughput, fairness tldr: Continuous batching lets an inference scheduler replace finished sequences with waiting work between decode iterations instead of holding a fixed batch until its longest request ends. That can increase occupancy and reduce queueing, but it does not eliminate tradeoffs. The scheduler must still allocate KV memory, mix prefill with decode, protect tenants, honor deadlines, and report goodput rather than peak tokens per second. key_takeaways: - A batch is a changing set of active sequences, not necessarily a fixed request group. - Iteration-level scheduling exposes admission and eviction decisions at every token step. - Long prefills can disrupt decode cadence unless work is chunked or separated. - First-come-first-served is simple but does not guarantee token-cost fairness across tenants. - Benchmark with declared arrivals, prompt lengths, output lengths, SLOs, and memory limits. --- 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. ::figure{template=timeline caption="Continuous batching replaces completed sequences between token iterations" items="t0 :: A+B active | t1 :: A+B active, C waits | t2 :: B completes | t3 :: A+C active | t5 :: C completes | t6 :: A+D active | t8 :: A completes"} ## 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](https://www.usenix.org/conference/osdi22/presentation/yu) 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: ```text batch = wait_until_batch_ready(queue) while any request in batch is unfinished: run_one_decode_step(batch) return all results ``` Continuous batch: ```text 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. ::figure{template=small-multiples caption="Toy two-slot trace: static reservation versus continuous replacement" items="Static slot 1 :: A,A,A,A,A,A,A,A,C,C,C | Static slot 2 :: B,B,idle,idle,idle,idle,idle,idle,D,idle,idle | Continuous slot 1 :: A,A,A,A,A,A,A,A | Continuous slot 2 :: B,B,C,C,C,D,idle,idle"} 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: ```text compute budget for the next iteration memory budget for all admitted sequence state ``` [PagedAttention](https://doi.org/10.1145/3600006.3613165) 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. ::figure{template=state-machine caption="Memory admission turns scheduling into an explicit state machine" items="Queued :: estimate tokens | Admissible? :: check blocks and priority | Prefill :: allocate KV | Decode active :: grow one step | Pressure :: preempt, swap, or reject | Complete :: release blocks | Cancelled :: release promptly"} ## 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](https://www.usenix.org/system/files/osdi24-agrawal.pdf) 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: ```text 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](https://www.usenix.org/conference/osdi24/presentation/zhong-yinmin) 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](/capacity-is-a-queue): completed requests per unit time that satisfy the named SLOs. ::figure{template=matrix caption="Scheduler policies trade efficiency, responsiveness, and protection" items="Large dynamic batch :: high throughput / queue risk | Decode priority :: stable TPOT / TTFT risk | Prefill priority :: fast admission / stream stalls | Short-job bias :: low mean / starvation risk | Fair sharing :: tenant protection / locality cost | Deadline policy :: SLO goodput / rejection cost"} ## 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](https://www.usenix.org/system/files/osdi24-sheng.pdf) 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: ```text 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: ```text 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: ```text 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](/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](/cost-per-verified-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](https://www.usenix.org/conference/osdi22/presentation/yu), 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](https://doi.org/10.1145/3600006.3613165), 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](https://www.usenix.org/system/files/osdi24-agrawal.pdf), Agrawal et al., OSDI 2024. Introduces chunked prefills and stall-free schedules. - [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://www.usenix.org/conference/osdi24/presentation/zhong-yinmin), Zhong et al., OSDI 2024. Frames serving capacity through simultaneous TTFT and TPOT objectives. - [Fairness in Serving Large Language Models](https://www.usenix.org/system/files/osdi24-sheng.pdf), 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. ## FAQ ### What is continuous batching in LLM inference? It is iteration-level scheduling in which the active set of sequences can change between model steps. Finished or cancelled sequences leave, waiting work enters when policy and memory permit, and the next iteration runs on the new batch. ### How is continuous batching different from static batching? A static batch commonly keeps a request group together until its longest member finishes. Continuous batching can reuse vacated slots immediately, reducing idle capacity caused by variable output lengths. ### Does continuous batching always reduce latency? No. Larger active batches, prefill admission, memory pressure, preemption, and queue policy can improve throughput while worsening TTFT, TPOT, tails, or fairness. Results must be measured under the target workload and SLO. ### Why does KV-cache memory limit batch size? Every active sequence retains attention state that grows with tokens. Model weights and workspace also consume memory. When KV blocks are unavailable, requests wait or the engine must preempt, swap, recompute, reject, or free other state. ### What is chunked prefill? It divides a long prompt's prefill into bounded chunks that can be scheduled alongside decode work. This can reduce long generation stalls, though chunk size trades prefill efficiency against decode cadence. ### How should continuous batching be benchmarked? Declare arrivals, bursts, prompt and output distributions, tenants, prefixes, hardware, runtime, memory settings, and SLOs. Report TTFT, TPOT, completion tails, SLO goodput, KV behavior, preemption, rejection, and per-tenant service. ## Test yourself ### 1. At what boundary can a continuous batch normally change membership? - [ ] Only after a deployment - [x] Between model iterations - [ ] Only when every request finishes - [ ] After billing closes **Explanation:** Iteration-level scheduling retires and admits sequences between model steps. ### 2. What does PagedAttention primarily improve? - [ ] Semantic answer equivalence - [x] KV-cache memory allocation and sharing - [ ] User authentication - [ ] Model training labels **Explanation:** It applies block-based virtual-memory ideas to serving-time KV state. ### 3. Why can a long prefill harm active generation? - [ ] It changes all model weights - [x] A large compute burst can delay decode iterations - [ ] It removes stop tokens - [ ] It guarantees cache hits **Explanation:** Co-located prefill and decode compete for the same accelerator execution time. ### 4. Why is equal request count not necessarily fair? - [ ] Every request has equal token cost - [x] Requests and tenants consume different input and output work - [ ] Fairness only applies to storage - [ ] Batching removes tenants **Explanation:** Token lengths and repeated calls create unequal service consumption. ### 5. Which metric best captures usable capacity? - [ ] Peak tokens per second alone - [ ] Largest configured batch - [x] Requests satisfying declared latency SLOs per unit time - [ ] GPU model name **Explanation:** SLO goodput counts completed work that meets the product's latency constraints.