Continuous Batching Inference Engine

The problem: static batching wastes the GPU

LLM inference is throughput-bound: you batch requests so a single read of the multi-gigabyte weights feeds many sequences at once and keeps the tensor cores busy. But decoding is autoregressive — each forward step produces exactly one token per sequence — and output lengths vary wildly. One request emits a 20-token answer; the request next to it streams a 2,000-token essay.

Static batching assembles N requests, runs the entire batch to completion, and returns them together. The batch is therefore locked for the duration of its slowest member. A sequence that hit its stop token at step 20 keeps occupying its slot through step 2,000: the GPU computes wasted rows (or padding), no new request can enter until the whole batch drains, and arriving requests sit in the queue for a full batch-runtime before they even start. The result is GPU utilization that routinely falls below 40%, inflated tail latency for short requests, and queueing latency that scales with the longest generation in the batch.

The fix is to stop treating a request as the unit of scheduling and instead schedule a single iteration (one decode step) at a time — admitting and evicting sequences continuously.

Static, dynamic, and continuous batching

There are three points on the spectrum, distinguished by when the batch is allowed to change:

• Static batching — a fixed batch is formed once and runs to completion. Simplest to implement, but utilization collapses under variable output lengths.
• Dynamic batching (server-side request batching, e.g. Triton) — the server waits a short window to gather arrivals into a batch, then runs that batch to completion. It amortizes the cost of forming batches, but each batch is still completion-locked, so the head-of-line problem just moves to the batch granularity. Great for fixed-shape models (vision, embeddings); poor for autoregressive LLMs.
• Continuous / iteration-level / in-flight batching — introduced by Orca and popularized by vLLM and TGI. The scheduling unit is one forward iteration, not one request. After every step the scheduler retires finished sequences (freeing their KV cache) and admits waiting ones, so the batch composition is re-decided each iteration and no sequence ever waits for another to finish.

flowchart TD
    subgraph STATIC["Static batching"]
        A1["Batch of 4 starts together"] --> A2["Run whole batch to completion"]
        A2 --> A3["Seq R1 stops at token 20"]
        A2 --> A4["Seq R2 still running at token 800"]
        A3 --> A5["R1 slot idles for ~780 steps"]
        A4 --> A6["Only now: free batch, admit next 4"]
    end
    subgraph CONT["Continuous batching"]
        B1["Run one decode step"] --> B2["Retire finished seqs, free KV"]
        B2 --> B3["Admit waiting seqs that fit"]
        B3 --> B1
    end
      

The continuous loop has no "drain" state — the same three operations (step, retire, admit) repeat forever, and the batch is reshaped on every pass.

The engine loop: per-iteration scheduler

The serving engine is a tight while loop. Each pass has three phases: a scheduling phase that decides the running set, a single fused model forward, and a post-processing phase that samples the next token, appends it, checks stop conditions, streams output, and frees the KV blocks of anything that just finished.

Admission is gated by the KV-cache budget. A sequence can only join the batch if there are enough free KV blocks for its next step; a brand-new request additionally needs blocks to hold the KV for its entire prompt during prefill. vLLM tracks free blocks and admits greedily up to a max_num_seqs / max_num_batched_tokens limit. Requests therefore move through a small state machine:

• WAITING — queued, no KV allocated yet.
• RUNNING — in the batch, KV allocated, producing tokens.
• PREEMPTED / SWAPPED — evicted under cache pressure; its KV is recomputed or swapped back later (see trade-offs).

The forward pass is "fused": in a single step the engine can run prefill for newly admitted requests and decode for in-flight ones together. Because each produced token is pushed to its client immediately (over SSE or a gRPC stream), TTFT for a request is essentially the latency of the iteration that completes its prefill.

sequenceDiagram
    participant Q as Waiting queue
    participant S as Scheduler
    participant K as KV cache
    participant G as GPU forward
    participant C as Client
    loop Every iteration
        S->>K: How many KV blocks are free
        K-->>S: Free block count
        S->>Q: Admit requests that fit the budget
        Q-->>S: New seqs join the running set
        S->>G: Run one fused prefill plus decode step
        G-->>S: One new token per running seq
        S->>C: Stream tokens out
        S->>S: Retire finished seqs and free their KV
    end
      

Everything the scheduler needs is cheap to track: the running set, the waiting queue, the count of free KV blocks, and each sequence's current length and sampling state. The whole decision is a greedy pass per iteration — which is exactly why scheduling overhead itself can become a bottleneck at high token rates (covered below).

Mixing prefill and decode

Prefill and decode have opposite compute profiles, and that is the central tension the scheduler must manage:

• Prefill processes the whole prompt in parallel — large matrix multiplies, one big compute-bound step that is heavy on FLOPs.
• Decode produces a single token — a tiny matrix multiply that is memory-bandwidth-bound, dominated by re-reading the weights and the KV cache.

Naively admitting a long prompt forces a huge prefill step that stalls every in-flight decode in the same iteration, producing a visible TPOT spike for every user in the batch. This is the prefill–decode interference problem.

Chunked prefill (Sarathi-Serve, also in vLLM) is the standard remedy: split a long prompt into fixed token-budget chunks and process one chunk per iteration, co-scheduled with ongoing decodes. Each step's compute stays bounded, so decode latency stays smooth while utilization climbs. A per-step token budget then lets you bias the engine: protect TPOT by prioritizing decodes, or protect TTFT by prioritizing prefills. At larger scale, some systems go further and disaggregate prefill and decode onto separate replicas entirely so the two phases never contend.

flowchart LR
    NR["New request, long prompt"] --> CP["Split prompt into prefill chunks"]
    CP --> SCH["Scheduler: token budget per step"]
    RUN["In-flight decodes"] --> SCH
    SCH --> STEP["One mixed step: many decodes plus one prefill chunk"]
    STEP --> TOK["Stream one token per decode"]
    STEP --> SCH
      

Throughput vs latency knobs

Continuous batching gives you a small set of dials, and almost every one trades throughput against latency or fairness. Tuning is the art of staying on the good edge of that Pareto frontier for your workload.

Bottlenecks & scaling

Once the iteration loop is in place, a predictable set of bottlenecks decides how far a single replica scales and when you must shard or add replicas.