Continuous Batching: Scheduling, Cache Admission and Capacity

Scheduling iterations rather than whole requests

A generative request performs prefill and then a variable number of decode steps. A request-granular batch holds its membership until the group finishes; an iteration-level scheduler can retire completed requests and admit new work between model steps. Orca's OSDI2022 contribution includes iteration-level scheduling and selective batching. Throughput gains depend on request lengths, hardware and the scheduling baseline; no universal30× speedup follows from iteration-level scheduling.

A bus versus revolving-door analogy helps: the bus leaves with a fixed group, whereas the room's occupants can change after each tick. But the room is not magically always full. Arrivals, prompt processing, token budget, KV capacity, fairness, deadlines and hardware efficiency can all limit admission. Continuous batching is more than a shorter batch timeout; waiting for a full request group to finish leaves ragged-length slots unavailable regardless of the admission timeout.

Prerequisites are per-request KV storage and prefill/decode behavior. Outcomes: calculate static slot waste, implement a bounded scheduler, derive Little's law with consistent units, separate throughput from latency, reason about chunked prefill, and trace a pinned vLLM scheduler without claiming to run its service.

Static, dynamic and continuous timelines

For output lengths20,500,200,250 in a fixed-width batch of four, useful token-steps are970 and reserved slot-steps are2000. Utilization in this constant-cost slot model is48.5%, not48% exactly. A compacting implementation may stop computing finished rows yet still fail to admit new requests; distinguish idle admission slots from literal padding computation. GPU utilization counters are not this fraction.

Fixed membership, capacity 2, lengths [1, 4, 1, 1]:
step 1: A B       A finishes
step 2: - B
step 3: - B
step 4: - B       B finishes
step 5: C D       C,D finish
 
Continuous membership:
step 1: A B       A finishes
step 2: C B       C finishes
step 3: D B       D finishes
step 4: - B       B finishes

This example saves one model iteration. It does not establish a2× makespan or5×p95 improvement on arbitrary traffic. Under no backlog, constant lengths or expensive admissions, the gain can be small. Dynamic batching groups arrivals within a time window; continuous batching changes membership across iterations. Both techniques can exist in one system.

Why selective batching is valid

For an ordinary decoder in evaluation mode, sequence i reads its own state and shared weights. Tokenwise normalization, projections and MLPs can operate on concatenated token rows. Attention must preserve request boundaries, correct positions and each request's KV block mapping. A block-diagonal mask is a conceptual formulation; variable-length/paged kernels use sequence metadata rather than necessarily materializing a huge mask.

A new request must first process its prompt. Its first output token is sampled from the final prompt position's logits; subsequent decode steps process previously generated tokens. Counting prompt tokens, generated tokens and cached tokens as interchangeable causes off-by-one capacity errors. A simulator may use a conservative upper bound, but must say so. Mathematical independence does not ensure bitwise identity across different batched kernels or RNG orderings; per-request seeded sampling and logit tolerances are separate reproducibility controls.

Exact CPU scheduling experiment

This event-driven simulator assumes all requests arrive at time zero and prefill is free. Each active request emits one token per unit-cost step. It conservatively reserves prompt plus maximum output tokens for admission, so it illustrates safe accounting rather than optimistic paging/preemption. Finished requests release the entire reservation. Static membership waits for all members to finish; continuous membership can refill between iterations. No sleep, GPU inference or real latency result is involved.

from dataclasses import dataclass
import math
@dataclass(frozen=True)
class Request:
    id: str
    prompt: int
    output: int
 
def simulate(requests,capacity,kv_budget,continuous):
    if type(capacity) is not int or type(kv_budget) is not int or capacity<1 or kv_budget<1:
        raise ValueError('positive integer capacity and KV budget required')
    if type(continuous) is not bool: raise ValueError('boolean policy required')
    if len({r.id for r in requests})!=len(requests): raise ValueError('duplicate id')
    for r in requests:
        if type(r.prompt) is not int or type(r.output) is not int:
            raise ValueError('integer token counts required')
        if r.prompt<1 or r.output<1 or r.prompt+r.output>kv_budget:
            raise ValueError('invalid or individually impossible request')
    waiting=list(requests); running=[]; finished={}; start={}; trace=[]
    used=0; clock=0; emitted=0
    while waiting or running:
        if continuous or not running:
            while waiting and len(running)<capacity:
                req=waiting[0]; reserve=req.prompt+req.output
                if used+reserve>kv_budget: break  # explicit FCFS head-of-line policy
                waiting.pop(0); running.append([req,req.output])
                used+=reserve; start[req.id]=clock
        if not running: raise RuntimeError('no progress')
        trace.append({'time':clock,'active':[r.id for r,_ in running],'reserved':used})
        assert used<=kv_budget
        clock+=1
        for entry in running: entry[1]-=1; emitted+=1
        for req,remaining in list(running):
            if remaining==0:
                finished[req.id]=clock; used-=req.prompt+req.output
        running=[entry for entry in running if entry[1]>0]
        assert used==sum(r.prompt+r.output for r,_ in running)
    assert used==0 and emitted==sum(r.output for r in requests)
    return {'steps':clock,'finished':finished,'start':start,'trace':trace,'tokens':emitted}
 
reqs=[Request(str(i),2,n) for i,n in enumerate([1,4,1,1])]
a=simulate(reqs,2,30,False); b=simulate(reqs,2,30,True)
assert a['steps']==5 and b['steps']==4
assert b['finished']=={'0':1,'2':2,'3':3,'1':4}
assert b['tokens']==7
assert sum([20,500,200,250])/(4*500)==0.485
# No queue means no automatic throughput gain.
solo=[Request('solo',2,4)]
assert simulate(solo,2,10,True)['steps']==simulate(solo,2,10,False)['steps']
# Capacity limits win over nominal batch size.
small=simulate(reqs,20,6,True)
assert all(t['reserved']<=6 for t in small['trace'])
try: simulate([Request('too-long',3,8)],2,10,True)
except ValueError: pass
else: raise AssertionError('impossible request admitted')
# Finite-trace Little identity: all arrivals zero, area under number-in-system.
area=sum(sum(end>t for end in b['finished'].values()) for t in range(b['steps']))
mean_W=sum(b['finished'].values())/len(reqs)
throughput=len(reqs)/b['steps']; mean_L=area/b['steps']
assert abs(mean_L-throughput*mean_W)<1e-12
assert abs((500/60)*(300/40)-62.5)<1e-12
print('static',a['steps'],'continuous',b['steps'],'mean L',mean_L,'mean W',mean_W)

Conservative reservations waste capacity when actual outputs are much shorter than the maximum. Optimistic admission must allocate before a forward step or have an explicit preemption/recompute policy; merely incrementing kv_used after generation can exceed the budget. A complete implementation must define packing/sampling and release prompt KV as well as output KV. This complete simulator tests the invariant but does not pretend to implement a production varlen model.

A reservation is not a computed-token count. For a prompt of 3 and output cap 2, this simulator reserves 5 slots. A real causal model prefills positions 0–2 and samples the first output from position 2. Before processing that emitted token, the cache still contains 3 positions, with 1 output token pending. Processing it fills position 3 and samples the second output; if that ends the request, there are 4 computed positions, not 5. The conservative reservation can then be released at a safe worker boundary. Speculative lookahead and block rounding require additional separately accounted reservations.

Scheduler/worker handoff contract: one scheduler owns admission and logical state; a dispatch carries request identity, a generation/epoch, computed-prefix length, pending tokens and the allocated block table. Allocation must succeed before dispatch, including any growth/lookahead. A worker result may advance only the matching live epoch. Cancellation marks a request retired, but its blocks remain unavailable for reuse until in-flight work acknowledges completion or is safely fenced. Otherwise an old kernel can overwrite a new tenant's recycled block. Retries must not double-count output or free a reservation twice. This is a required design contract, not a claim that the synchronous simulator implements asynchronous workers; the next lesson supplies an executable lease model.

A realistic extension adds arrival timestamps, prefill costs, context-dependent step times, cancellations, deadlines and block rounding. Compare latency from arrival, not from admission alone. Include failed/rejected requests in goodput accounting rather than dropping them to improve latency plots.

Little's law, derived with a boundary

Draw one horizontal interval from each request's arrival to departure. The area under the number-in-system curve equals the sum of all interval durations, apart from observation-window boundary corrections. Divide by elapsed time t:

In a stable long-run system with consistent boundaries this becomes L=lambda*W. L includes waiting if W includes waiting. It relates averages, not p99; it does not prove a proposed service rate is achievable. At sustained arrivals above capacity the queue grows and a finite steady-state W does not exist.

For500requests/minute and300output tokens at40tokens/s per stream, the idealized decode duration is7.5seconds and mean active decode concurrency is62.5. Add queueing/prefill/network time if sizing the whole system. Required output rate is2500tokens/s. That workload only fits if the serving stack actually sustains the necessary per-stream rate at that concurrency, KV memory and prompt mix; the equation is a consistency check, not a GPU-count oracle.

Aggregate output throughput is the sum of active stream rates over a consistent time window.200tokens/s across two streams does not imply100 each: rates could be150 and50. Dividing by concurrency gives a mean only under the stated measurement boundary. Report distributions and active-versus-queued counts.

Chunked prefill, priority and fairness

A long prompt can consume a long iteration and delay existing streams. Prefill-first policies can improve admission/TTFT while harming ITL; decode-first policies can smooth active streams while delaying new arrivals. Neither is universally best for interactive or offline work. Active decodes still grow KV, so decode priority does not make memory pressure monotonically decrease or eliminate preemption.

Chunked prefill splits a prompt across iterations and budgets some prompt tokens beside decode tokens. Sarathi-Serve studies this tradeoff. A token budget is not a hard time budget: attention cost depends on prefix length, shapes and kernels. Tiny chunks add overhead and reduce prefill efficiency; large chunks can stall streams. Under overload, no chunk size guarantees both bounded TTFT and ITL without admission control. Add fairness/aging or priority policy so long prompts cannot starve indefinitely.

For vLLM0.11.0 V1, the source scheduler first considers running requests, computes pending token work from required versus computed tokens, caps it by available token budget/model limits and asks the KV manager for slots. Allocation failure can cause preemption before scheduling proceeds; waiting requests are considered under remaining resources. long_prefill_token_threshold is not a universal2048-token switch below which chunking is impossible. Chunking may arise because remaining step budget is smaller than requested prompt work. Read this release's config and effective startup logs rather than transfer V0 defaults blindly.

Tune max_num_seqs (scheduled sequence ceiling), max_num_batched_tokens (per-iteration token work) and explicit prompt/output/context limits jointly. Benchmark one axis at a time with the same trace. Inspect p50/p95/p99 TTFT and ITL, throughput, SLO-compliant goodput, preemptions, queue age and KV usage. Lowering max sequences may reduce preemption but also throughput; increasing token budget may help prefill while hurting ITL. No fixed5% cost or30–40% upgrade regression is asserted.

Prefix sharing, speculation and disaggregation

Prefix caching saves repeated prefill for identical compatible prefixes, subject to cache-key isolation and eviction. It does not eliminate queueing, uncached suffix prefill, first-token sampling or network time. vLLM V1's prefix caching and unified token scheduling are documented architectural changes; the January2025 blog's benchmarks belong to their tested workloads, not an automatic upgrade multiplier.

SGLang's RadixAttention stores reusable prefixes in a radix tree. Compare actual versions and cache-hit workloads rather than assert that any partial-prefix match yields a fixed5× gain over vLLM. Speculative decoding can save memory-bound decode iterations when draft acceptance is high; at high batching it can consume compute/cache that another request could use. There is no timeless automatic concurrency cutoff to trust without reading the selected release.

Splitwise and DistServe separate prefill and decode resources and transfer KV state. This can reduce interference and improve goodput under SLOs in their evaluated settings. Transfer cost is at least cache bytes/effective link bandwidth, plus protocol/synchronization/queue overhead. A512MiB cache over an illustrative25GB/s effective link takes at least about21.5ms one-way before overhead. Hardware pools, load imbalance, failure recovery, privacy and transfer bottlenecks can outweigh the benefit. Do not assume A100/H100 equivalence, undocumented vendor adoption or a universal2–4×tokens-per-dollar gain.

Worked SLA and load-test recipe

Worked capacity exercise:10QPS, average1500-token prompts,400-token completions, prefill5000tokens/s and decode40tokens/s/stream at concurrency32; targets p99TTFT≤300ms and at least30tokens/s/stream. Prompt arrival demand alone is15000tokens/s, three times the stated prefill capacity. Even with no queue,1500/5000=300ms leaves no headroom for any overhead. Decode at40tokens/s lasts10s, implying100 average active decode requests at10QPS, versus measured32. One device is not established feasible; in fact the stated prefill capacity rules it out. Three prefill-equivalent devices at100% utilization still do not prove a tail SLO. Use measured mixed-workload service curves and headroom, not ceil(mean-demand/capacity) as a p99 guarantee.

To test a serving system in an authorized environment: freeze model/checkpoint/runtime/hardware, warm the intended execution paths, replay a recorded or generated arrival trace with known prompt/output distributions, and measure end-to-end from scheduled arrival to avoid coordinated omission. Run both open-loop arrivals and bounded-concurrency tests, clearly labeled. Include cold/warm prefix-cache conditions, burst and long-prompt cases, cancellation and impossible-request rejection. Stop at a predeclared memory/error/SLO threshold. The CPU simulator does not start a server or download a model; serving-system measurements remain a separate experiment.

A report needs input/output tokens, accepted/rejected/canceled counts, arrival process, run duration, warmup, cache hits, effective flags, precision, TP degree, aggregate throughput and per-stream latency. An8000–12000tokens/s anecdote without those conditions is not a usable capacity estimate. Four-way FP8 sharding of405B is not a general eight80GB-node recipe: weight capacity must be checked per rank first.

Recall and source-tracing answers

1. Continuous versus dynamic batching? Iteration membership can change before a request completes; dynamic request grouping alone cannot recover all ragged completion slots.
2. Which phase benefits? Both can benefit from batching; low-concurrency decode often gains weight reuse, whereas prompt processing already has many rows. Quantify rather than assert a fixed winner.
3. Why isolate attention? Each request must attend only to its permitted context and positions. Tokenwise operations can share kernels without sharing semantic state.
4. What does memory constrain? Cache capacity limits admission, but compute, bandwidth, communication, token budget and SLOs also bind. Paging does not make finite memory infinite.
5. Which scheduler knobs? Sequence/token ceilings and prefill/decode/fairness policy; do not confuse these configuration choices with naming two different algorithms supplied by every release.
6. Trace one request in vLLM? In the pinned scheduler, follow waiting admission → prefix/computed-token accounting → slot allocation → scheduled-token output → worker result update → completion/free. At failed allocation inspect the actual victim policy and state reset; do not assume shortest remaining length is known.
7. When is preemption healthy? Some policies accept it as a tradeoff; zero preemptions can be entirely appropriate. High preemption warrants examination of output tails, reservations and scheduling, not automatic hardware purchase.

Primary sources and execution boundary

Orca, Sarathi-Serve, DistServe, Splitwise, vLLM V1 announcement, vLLM0.11.0 scheduler, and SGLang. Exact passages and source hashes accompany local math/tests. Only the event simulator is executed; no serving throughput, fleet sizing deployment or GPU experiment is represented as reproduced.

Course navigation

Series: Deep Learning & LLMs From Scratch — 80 sessions · Session 70 / 80 · Module M11 · ~2 hours

Previous: ← DL S069 · Next: DL S071 →

Optional reading

Use these links for additional background. Version-specific behavior is documented in the primary references above.

• Optional resource 1
• Optional resource 2
• Optional resource 3