Continuous Batching

I-00 followed a single request from gateway arrival to streamed completion. A production serving engine handles many requests at once and decides which pieces of each run in the next model iteration. Instead of picking one fixed batch size, a modern scheduler decides how many prompt tokens, decode tokens, active sequences, and KV blocks can run in the next step without breaching latency targets or exhausting memory.

This tutorial builds a compact iteration-level scheduler. It sorts out terminology by source, schedules decode work ahead of chunked prefill, preempts lower-priority work under an explicit rule, enforces bounded backpressure during overload, and emits a replayable iteration trace.

Terminology Depends on the Source

These labels are not universal synonyms. Triton's "dynamic batcher" combines waiting requests into a batch before execution, whereas its iterative-sequence documentation describes continuous, iteration-level, and inflight batching as strategies that form batches at each iteration step (NVIDIA Triton batching). Orca proposed the mechanism under the name iteration-level scheduling (Yu et al., OSDI 2022). Always name the engine and exact scheduling rule when comparing systems.

Why Batching Helps Decode

At small batch sizes, decode typically spends more time reading model weights from HBM than computing with them. Batching several active sequences together amortizes each layer's weight read across multiple token updates. Larger batches can therefore raise aggregate throughput, but each step can also take longer and consume more KV memory.

An inference scheduler therefore balances at least four constraints at once:

• total token work admitted into the current iteration;

• number of concurrently active sequences;

• KV blocks needed now and as active outputs continue growing; and

• latency and priority rules across waiting and running requests.

Keeping every sequence slot occupied is not enough on its own: admitting one multi-thousand-token prompt in full can stall ongoing decodes, and admitting too many growing sequences at once can force mid-generation preemption or out-of-memory failures.

Static and Request-Dynamic Batching

Suppose eight requests generate 20, 45, 80, 120, 150, 90, 60, 200 output tokens. In a simplified output-slot illustration that counts the first token emitted at the end of prefill as round 1 and ignores prompt-length differences, a fixed eight-request batch spans 200 output rounds: one prefill pass plus 199 decode passes. Those rounds expose 8 × 200 = 1,600 output-token slots, yet produce only:

20 + 45 + 80 + 120 + 150 + 90 + 60 + 200 = 765 useful tokens
wasted slots = 1,600 - 765 = 835
waste ratio  = 835 / 1,600 = 52.19%

Request-dynamic batching can shorten how long arrivals wait at the gate to form a batch, but if the resulting batch still stays locked together until the 200-token straggler finishes, completion-length skew wastes the same 835 slots.

Iteration-level scheduling retires finished sequences immediately and can admit waiting requests on the next step. Across 200 abstract rounds, an eight-slot engine has a ceiling of 1,600 occupied output slots if eight useful decodes run on every round, though real throughput sits lower once prefill chunks, sampling, KV headroom, and scheduler overhead take their share. How many extra requests finish during that interval depends on replacement prompt lengths and prefill costs, so a capacity estimate needs an explicit workload model, not slot arithmetic alone.

Chunked Prefill and Decode-Maximal Scheduling

Admitting new requests mid-flight exposes prefill/decode interference whenever a long prompt monopolizes an iteration. Sarathi-Serve addresses this with chunked prefills and stall-free scheduling: each batch first packs one token for every running decode, then spends the remaining token budget on prefill chunks, so new prompts join without pausing ongoing decodes (Agrawal et al., OSDI 2024). This tutorial calls that decode-first batch construction decode-maximal scheduling. vLLM V1 likewise enables chunked prefill by default where possible and schedules pending decodes before prefills within its max_num_batched_tokens budget (vLLM Optimization and Tuning). Chunk size sets the trade-off: larger chunks raise prefill compute efficiency at the risk of wider ITL spikes, while tiny chunks protect decode cadence at the cost of kernel-launch overhead and repeated attention reads over earlier chunks.

Our simulator implements this seven-step loop per iteration:

1. inspect new arrivals at the current iteration;

2. when a high-priority arrival finds all active slots occupied, preempt the active normal-priority request with the largest remaining work only if the waiting queue has room to hold the victim; otherwise fall through to the normal bounded enqueue or rejection rule;

3. enqueue normal arrivals until the waiting queue reaches its fixed cap, rejecting arrivals beyond that cap;

4. promote waiting requests into any free active slots;

5. allocate 1 token of budget to each active request that has already finished prefill;

6. spend remaining iteration token budget on prefill chunks of up to 3 tokens per request; and

7. emit the request's first output token on the iteration its prefill finishes (only later tokens consume decode budget), then retire completed requests at the end of the step.

To keep queue and priority transitions easy to verify by hand, preempted requests retain partial progress at zero transfer cost (an idealized offload), and the simulator bounds sequence slots, queue depth, and per-step token work rather than physical KV blocks. Production engines pay real preemption costs. vLLM V1, for instance, defaults to RECOMPUTE rather than SWAP preemption: it frees the preempted request's KV cache space and recomputes that state once memory becomes available again (vLLM Optimization and Tuning).

Freeze the Scheduler Scenario

Requests:

At iteration 1, high-priority request C preempts A because A has more remaining work (3 + 3 = 6) than B (1 + 2 = 3). C finishes its 2-token prefill and emits its single output token within iteration 1. At iteration 2, D claims the freed active slot, E joins A in the two-slot waiting queue, and F fails fast because the queue is full, surfacing overload as explicit backpressure instead of a silent timeout.

Worked Example: Trace the Iterations

Under the policy above, the iteration-by-iteration trace is:

First-output and completion iterations:

Because the simulator tracks discrete token budgets rather than kernel execution time, this trace validates scheduling order and admission bounds rather than GPU wall-clock latency.

Build the Scheduler Simulator

Save as simulate_scheduler.py:

import json
from pathlib import Path

MAX_ACTIVE = 2
MAX_QUEUE = 2
TOKEN_BUDGET = 6
PREFILL_CHUNK = 3
MAX_ITERATIONS = 200
PRIORITY_PREEMPTION = True

REQUESTS = [
    {"id": "A", "arrival": 0, "priority": "normal", "prompt": 6, "output": 3},
    {"id": "B", "arrival": 0, "priority": "normal", "prompt": 4, "output": 2},
    {"id": "C", "arrival": 1, "priority": "high", "prompt": 2, "output": 1},
    {"id": "D", "arrival": 2, "priority": "normal", "prompt": 4, "output": 2},
    {"id": "E", "arrival": 2, "priority": "normal", "prompt": 1, "output": 1},
    {"id": "F", "arrival": 2, "priority": "normal", "prompt": 1, "output": 1},
]

states = {
    item["id"]: {
        **item,
        "prompt_remaining": item["prompt"],
        "output_remaining": item["output"],
        "first_output": None,
        "completed": None,
        "preemptions": 0,
        "result": "pending",
    }
    for item in REQUESTS
}
active = []
waiting = []
trace = []

def remaining_work(request_id):
    state = states[request_id]
    return state["prompt_remaining"] + state["output_remaining"]

def enqueue(request_id):
    if len(waiting) >= MAX_QUEUE:
        states[request_id]["result"] = "rejected"
        return False
    states[request_id]["result"] = "waiting"
    waiting.append(request_id)
    return True

if not (0 < MAX_ACTIVE <= TOKEN_BUDGET and MAX_QUEUE >= 0 and PREFILL_CHUNK > 0):
    raise ValueError("invalid scheduling budgets")
if len(states) != len(REQUESTS) or any(x["prompt"] < 1 or x["output"] < 1 for x in REQUESTS):
    raise ValueError("unique IDs and positive lengths required")

for iteration in range(MAX_ITERATIONS):
    record = {"iteration": iteration, "decode": [], "prefill": [], "prefill_emitted": [], "preempted": [], "rejected": []}

    for item in [x for x in REQUESTS if x["arrival"] == iteration]:
        request_id = item["id"]
        if len(active) < MAX_ACTIVE:
            active.append(request_id)
            states[request_id]["result"] = "active"
        elif item["priority"] == "high" and PRIORITY_PREEMPTION:
            victims = [rid for rid in active if states[rid]["priority"] == "normal"]
            if victims and len(waiting) < MAX_QUEUE:
                victim = max(victims, key=remaining_work)
                active.remove(victim)
                states[victim]["preemptions"] += 1
                states[victim]["result"] = "waiting"
                waiting.insert(0, victim)
                active.append(request_id)
                states[request_id]["result"] = "active"
                record["preempted"].append(victim)
            elif not enqueue(request_id):
                record["rejected"].append(request_id)
        elif not enqueue(request_id):
            record["rejected"].append(request_id)

    while waiting and len(active) < MAX_ACTIVE:
        request_id = waiting.pop(0)
        active.append(request_id)
        states[request_id]["result"] = "active"

    budget = TOKEN_BUDGET
    for request_id in list(active):
        state = states[request_id]
        if state["prompt_remaining"] == 0 and state["output_remaining"] > 0 and budget > 0:
            state["output_remaining"] -= 1
            budget -= 1
            record["decode"].append(request_id)
            if state["first_output"] is None:
                state["first_output"] = iteration

    for request_id in list(active):
        state = states[request_id]
        if state["prompt_remaining"] > 0 and budget > 0:
            amount = min(PREFILL_CHUNK, state["prompt_remaining"], budget)
            state["prompt_remaining"] -= amount
            budget -= amount
            record["prefill"].append([request_id, amount])
            if state["prompt_remaining"] == 0:
                state["output_remaining"] -= 1
                state["first_output"] = iteration
                record["prefill_emitted"].append(request_id)

    completed_now = []
    for request_id in list(active):
        state = states[request_id]
        if state["prompt_remaining"] == 0 and state["output_remaining"] == 0:
            state["completed"] = iteration
            state["result"] = "completed"
            active.remove(request_id)
            completed_now.append(request_id)

    record["completed"] = completed_now
    record["queue"] = list(waiting)
    record["active"] = list(active)
    record["unused_budget"] = budget
    assert len(waiting) <= MAX_QUEUE and len(active) <= MAX_ACTIVE
    assert 0 <= budget <= TOKEN_BUDGET
    trace.append(record)

    terminal = all(state["result"] in {"completed", "rejected"} for state in states.values())
    if terminal:
        break

artifact = {
    "termination": "all_terminal" if terminal else "iteration_limit",
    "policy": {
        "max_active": MAX_ACTIVE,
        "max_queue": MAX_QUEUE,
        "token_budget": TOKEN_BUDGET,
        "prefill_chunk": PREFILL_CHUNK,
    },
    "trace": trace,
    "requests": {
        request_id: {
            "first_output": state["first_output"],
            "completed": state["completed"],
            "preemptions": state["preemptions"],
            "result": state["result"],
        }
        for request_id, state in states.items()
    },
}
Path("request_summary.json").write_text(json.dumps(artifact["requests"], indent=2))
print(json.dumps(artifact, indent=2))

Run:

python simulate_scheduler.py > scheduler_trace.json

Verify that A.preemptions=1, F.result="rejected", C completes at iteration 1, B at iteration 2, D at iteration 4, and A and E at iteration 5, with request_summary.json written alongside the trace. If termination ever reports "iteration_limit", the workload failed to drain within MAX_ITERATIONS.

What Historical Throughput Results Actually Establish

Orca reported 36.9× higher throughput than FasterTransformer (6.81 versus 0.185 requests/s) on a GPT-3-style 175B FP16 model across 16 A100-40GB GPUs using synthetic prompts and forced output lengths, evaluated at a matched median end-to-end latency normalized by generated-token count of 190 ms (Yu et al., OSDI 2022). That figure is a whole-system comparison under those exact conditions, against FasterTransformer driven by a request-level batching scheduler, not a universal multiplier for continuous batching.

Anyscale's 2023 benchmark ran OPT-13B on a single A100-40GB GPU against naive static batching in Hugging Face Pipelines. It reported up to 8× throughput from continuous-batching implementations and up to 23× from vLLM, which adds continuous-batching-specific memory optimizations. The throughput run submitted a burst of 1,000 requests (512 input tokens each, capped exponential output lengths); it did not measure SLO-bounded online capacity. The authors also wrote that they had not analyzed which optimization contributes most to vLLM's performance, only that they suspect its dynamic rather than ahead-of-time KV reservation. The gap between 8× and 23× therefore should not be cited as "PagedAttention alone" (Anyscale benchmark, 2023).

Deliberately Broken Cases

Unbounded Queue

Raise MAX_QUEUE to infinity and feed eight arrivals per iteration into an engine retiring two. The queue grows by roughly six requests every step. Continuous batching keeps GPU execution dense, but it cannot keep up once arrival rate exceeds service rate; production systems still need bounded queues, explicit rejection with a retry policy, or priority load shedding.

Unchunked Long Prefill

Let a single 6,000-token prompt monopolize an entire iteration while active decodes wait behind it. Aggregate token throughput may still look healthy, while streaming users see an ITL spike. Chunking bounds how much prompt work enters one scheduling quantum; physically separating prefill and decode pools in I-03 is a heavier architectural alternative.

Eviction Without Accounting

Aggressive scheduler modes may pause or evict an in-progress sequence when growing KV caches exhaust memory. TensorRT-LLM's legacy runtime guide contrasts MAX_UTILIZATION, which schedules aggressively at the risk of pausing requests once the KV cache limit is reached, with the default GUARANTEED_NO_EVICT, which admits conservatively so that a started request is never paused (TensorRT-LLM runtime options). Always verify the default policy of the exact engine backend and version you deploy, and account for recomputation or swap latency whenever preemption triggers.

Hands-On Exercise

Run three variants:

1. the baseline policy above;

2. PREFILL_CHUNK=6; and

3. PRIORITY_PREEMPTION=False, so high-priority C waits in the queue.

For each variant, report:

• first-output and completion iteration per request;

• peak waiting-queue length;

• total preemptions and rejections;

• unused token budget per iteration; and

• whether any decode-ready request waits while prefill consumes budget.

Next, append two normal arrivals per iteration across iterations 0 through 9 (each with prompt length 6, output length 3, and unique IDs) under the baseline budgets, and also test a high-priority arrival when both active slots and the waiting queue are full. Confirm that the waiting queue never exceeds two entries and that sustained overload surfaces as explicit rejections rather than unbounded queue growth.

Reference completion iterations for the three initial variants appear below (- means rejected; first-output iterations and unused budgets appear in scheduler_trace.json). The arrival branch if len(active) < MAX_ACTIVE: lets newly arriving requests claim an empty active slot ahead of already queued work. That choice keeps the fixture simple and is not a fairness recommendation; a real scheduler also needs aging, deadlines, and cancellation handling so queued requests do not starve.

Measurable Exit Criteria

The scheduler tutorial passes when:

• all request lengths, budgets, priorities, and scheduling rules are explicit;

• decode plus prefill tokens never exceed six in any iteration;

• no baseline prefill chunk exceeds three tokens;

• A is preempted exactly once and later resumes from its retained progress;

• F is rejected when the two-slot waiting queue is full, and priority preemption never pushes the queue past two entries;

• first-output and completion iterations match the worked tables;

• the sustained-overload run keeps queue length at or below two;

• historical 8×, 23×, and 36.9× citations retain their model, hardware, baseline, metric, and denominator; and

• the Anyscale vLLM gap is not attributed to PagedAttention in isolation.

Retrieval Practice

1. How does iteration-level scheduling differ from request-dynamic batching?

2. Why does a per-step token budget capture scheduling cost better than a sequence-count cap alone?

3. What latency problem does chunked prefill mitigate?

4. Why does continuous batching fail to eliminate overload queues?

5. What state does our toy preemption keep for free that a recompute-on-preemption engine discards?

6. Why should Anyscale's 23× vLLM figure not be cited as a PagedAttention-only speedup?

Answer Key

1. Iteration-level scheduling retires finished sequences and admits waiting work between individual autoregressive steps rather than locking a batch together until its longest sequence finishes.

2. Each occupies one sequence slot, but a prompt chunk processes and caches several tokens in one iteration, whereas an ordinary decode step processes one token and adds one KV entry.

3. Chunked prefill caps how much prompt work can run alongside active decodes in one iteration, which bounds how long a long prompt can stall streaming ITL at some cost in prefill efficiency.

4. Whenever arrival rate stays above sustainable service rate, requests must either accumulate in a queue or be shed; batching efficiency raises service rate up to hardware limits without changing that conservation law.

5. The toy simulator keeps already processed prompt and decode progress at zero cost, whereas a recompute policy drops the victim's KV blocks and re-runs prefill when the request resumes.

6. The benchmark measured vLLM end to end (combining continuous batching, PagedAttention, and engine-level optimizations) in an offline burst without isolating PagedAttention's individual share.

What This Post Does Not Cover

I-02 turns per-token KV state into paged block capacity. I-04 adds local prefix reuse and distributed cache-aware routing. I-03 evaluates disaggregating prefill and decode onto separate worker pools. I-07 turns these scheduling mechanics into an open-loop capacity and SLO benchmark.

Source Notes

• Yu, G., Jeong, J. S., Kim, G. W., et al. "Orca: A Distributed Serving System for Transformer-Based Generative Models." OSDI, 2022. Primary source for iteration-level scheduling and the scoped 36.9× FasterTransformer comparison. usenix.org

• Agrawal, A., Kedia, N., Panwar, A., et al. "Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve." OSDI, 2024. Primary source for chunked prefill and stall-free, decode-first scheduling. arxiv.org/abs/2403.02310

• vLLM Project. "Optimization and Tuning." Current documentation, accessed 2026-11-02. First-party V1 defaults for chunked prefill, decode-first scheduling, and recompute preemption. docs.vllm.ai

• NVIDIA Triton Inference Server. "Batchers." Current documentation, accessed 2026-11-02. First-party distinction between request-dynamic batching and iterative/continuous/inflight batching. docs.nvidia.com

• Daniel, C., Shen, C., Liang, E., and Liaw, R. "How Continuous Batching Enables 23x Throughput in LLM Inference While Reducing p50 Latency." Anyscale, 2023-06. Vendor burst benchmark retained with model, hardware, baseline, and non-isolation scope. anyscale.com

• NVIDIA TensorRT-LLM. "Useful Runtime Options." Current documentation, accessed 2026-11-02. First-party capacity-scheduler and eviction-policy semantics. nvidia.github.io