Continuous Batching

★ The single largest throughput win in modern LLM serving — typically 3-10x. Also called iteration-level scheduling (Orca) or in-flight batching (TensorRT-LLM).

1. What is it?#

Making scheduling decisions at every decode step instead of once per batch.

STATIC:      [ decide batch ] → [ run to completion ] → [ decide batch ] → ...

CONTINUOUS:  [ decide ] → step → [ decide ] → step → [ decide ] → step → ...
                                    ↑
                     every step: finished sequences leave,
                                 waiting sequences join

The batch is not a fixed group; it’s a membership that changes every 5-50 milliseconds.

Diagram — Lifecycle of a request inside a continuous-batching engine#

stateDiagram-v2
    direction LR
    [*] --> Waiting: request arrives
    Waiting --> Prefill: admitted - slot and KV blocks free
    Prefill --> Decode: first token emitted
    Decode --> Decode: one token per step
    Decode --> Finished: EOS or max_tokens
    Decode --> Preempted: KV memory exhausted
    Preempted --> Waiting: re-queued, recomputed later
    Finished --> [*]: KV blocks freed immediately

2. Why does it exist?#

Because of the two failures of static batching (file 08):

1. Finished sequences hold slots until the longest finishes.
2. New requests wait for the whole batch.

Both come from the same assumption: that a batch is a unit that starts and ends together. Continuous batching drops the assumption.

The reason it works is the observation from file 08’s section 6: adding or removing a sequence just changes the number of rows in the matmuls. There’s no physical barrier — only a software design that assumed fixed shapes.

3. Simple analogy#

A hospital ward versus a scheduled surgery list.

Scheduled list (static batching): eight operating theatres all start at 9am and all finish when the longest operation ends at 4pm. Seven theatres sit empty from 11am. Patients arriving at 9:15 wait until tomorrow.

Ward (continuous batching): beds free up as patients are discharged, and the next patient is admitted immediately. Occupancy stays near 100%. Someone arriving at 9:15 gets the next available bed.

The key enabler in both cases: you can admit and discharge independently, at any time.

4. Tiny example#

The scheduler loop, in essence:

type Stage int

const (
	Prefill Stage = iota
	Decode
	Preempted
)

type Request struct {
	PromptIDs, OutputIDs []int
	Blocks               []int // KV blocks this request owns
	Stage                Stage
}

type Engine struct {
	model    Model
	kv       *BlockManager
	waiting  []*Request // not yet started
	running  []*Request // currently generating
	maxBatch int
}

func (e *Engine) Add(r *Request) { e.waiting = append(e.waiting, r) }

// Step runs ONE iteration of the engine loop and returns the requests that finished.
func (e *Engine) Step() (finished []*Request) {
	// ---- 1. ADMIT new requests if there's room and memory ----
	for len(e.waiting) > 0 && len(e.running) < e.maxBatch {
		r := e.waiting[0]
		blocks, err := e.kv.Allocate(e.kv.BlocksNeeded(len(r.PromptIDs)))
		if err != nil {
			break // out of KV memory; stop admitting
		}
		e.waiting = e.waiting[1:]
		r.Blocks, r.Stage = blocks, Prefill
		e.running = append(e.running, r)
	}
	if len(e.running) == 0 {
		return nil
	}

	// ---- 2 + 3. BUILD the batch and RUN one iteration ----
	// A mixed batch: prefill requests contribute many tokens, decode requests one each.
	tokens := e.model.ForwardMixed(e.running, e.kv) // one new token per running request

	// ---- 4. UPDATE state, RETIRE finished ----
	still := e.running[:0]
	for i, r := range e.running {
		r.OutputIDs = append(r.OutputIDs, tokens[i])
		r.Stage = Decode
		switch {
		case e.isDone(r):
			e.kv.Free(r.Blocks) // ← slot freed IMMEDIATELY
			finished = append(finished, r)
		case e.needsNewBlock(r):
			b, err := e.kv.Allocate(1)
			if err != nil { // out of memory — this request goes back to the queue
				e.preempt(r)
				continue
			}
			r.Blocks = append(r.Blocks, b...)
			still = append(still, r)
		default:
			still = append(still, r)
		}
	}
	e.running = still
	return finished
}

// preempt discards the request's KV and re-queues it at the front; it will be re-prefilled.
// (The alternative strategy is to swap its KV blocks out to host memory.)
func (e *Engine) preempt(r *Request) {
	e.kv.Free(r.Blocks)
	r.Blocks, r.Stage = nil, Preempted
	e.waiting = append([]*Request{r}, e.waiting...)
}

That is the core of vLLM, TGI, and every modern engine, in 50 lines. The real implementations add priorities, chunked prefill, prefix cache lookups, LoRA management, and careful memory accounting — but the loop is this.

5. Technical explanation#

The scheduling decisions per step#

Every iteration the scheduler decides:
  1. Which waiting requests to admit (if any)
  2. Whether to run prefill, decode, or both (mixed batching)
  3. Which running requests to preempt (if memory is short)
  4. How many prefill tokens to process this step (chunked prefill)

Each decision has a policy, and the policies determine your latency/throughput profile.

Admission policy#

FCFS                    simple, fair, but a long prompt can delay everyone
Shortest-job-first      better average latency, needs length prediction, starves long jobs
Priority                by tenant/tier — necessary for multi-tenancy
Memory-aware            admit only if KV space for the WORST CASE is available

The memory-aware constraint is the subtle one. If you admit a request assuming it generates 100 tokens and it generates 4,000, you may run out mid-flight and be forced to preempt. Two philosophies:

CONSERVATIVE: reserve KV for prompt + max_tokens up front.
              No preemption ever, but low utilization (most requests
              don't hit max_tokens).

OPTIMISTIC:   allocate as you go. High utilization, occasional preemption.
              What vLLM does.

Optimistic is right, because preemption is rare and cheap relative to the utilization gained.

Preemption#

When KV memory runs out mid-generation:

SWAP:      copy the victim's KV blocks to CPU memory, free the GPU blocks.
           Later, copy back. Cost: 2 × KV_size / PCIe bandwidth.
           For 1 GB of KV over PCIe Gen4: ~80 ms round trip.

RECOMPUTE: discard the victim's KV, re-prefill it later.
           Cost: one prefill of (prompt + generated_so_far).
           Often CHEAPER than swapping, because prefill is fast and
           PCIe is slow.

vLLM defaults to recompute for exactly this reason. The choice depends on prefill_speed vs PCIe_bandwidth, and prefill usually wins.

Victim selection matters: preempting the most-recently-admitted (LIFO) preserves the progress of long-running requests; preempting the longest-running frees the most memory. Most engines use LIFO-ish policies.

Mixed batching (prefill + decode in one step)#

Naive: run prefill steps and decode steps separately
       → a long prefill blocks all decodes (file 03)

Mixed: one forward pass containing both
       tokens = [prefill_req_A: 512 tokens] + [decode_req_B: 1] + [decode_req_C: 1] ...
       → varlen kernels handle the ragged shape

This is how chunked prefill works (Section XIII.05): the prefill is split into chunks of, say, 512 tokens, and each chunk rides along with the decode step.

Tuning: max_num_batched_tokens controls the total tokens per iteration. Larger = better prefill throughput, worse decode latency. vLLM’s default (2048-8192 depending on version) is a reasonable starting point; tune it against your ITL SLO.

Why it’s such a big win#

Static batching, batch 32, realistic lengths:
  average active sequences ≈ 8-12 (rest are finished, holding slots)
  → effective batch 10

Continuous batching, same memory:
  average active sequences ≈ 30-32
  → effective batch 31

Throughput ratio ≈ 3x — and the GPU was already paid for.

Plus: new requests join within one step (~5-50 ms) instead of waiting for the batch, so TTFT under load improves dramatically too. It’s the rare optimization that improves latency and throughput simultaneously.

6. Under the hood#

The state a continuous-batching engine tracks per request:

request_id
prompt_token_ids
output_token_ids
stage:            waiting | prefill | decode | preempted | finished
block_table:      [17, 3, 92, ...]        ← physical KV blocks
num_computed_tokens                       ← for chunked prefill
sampling_params:  temperature, top_p, seed, stop strings, max_tokens
arrival_time, first_token_time            ← for metrics
priority / tenant
lora_id                                   ← if multi-LoRA

And per step it builds:

input_token_ids:     flat array of all tokens this step
cu_seqlens:          request boundaries for varlen kernels
block_tables:        (num_seqs, max_blocks) for paged attention
seq_lens:            context length per sequence
sampling metadata:   per-request temperature, top_p, etc.

Building this metadata is CPU work that happens every step. At batch 256 with per-request Python objects, it can take milliseconds — which is why engines optimize it hard (flat arrays, cached tensors, incremental updates) and why some have moved the scheduler to C++/Rust.

7. Performance implications#

Measured (vLLM paper and reproductions), relative to static batching:

Workload                        Throughput gain
Uniform lengths                 1.5-2x     (less to gain — no idle slots)
Realistic chat (heavy-tailed)   3-5x
High variance (mixed use)       5-10x
With prefix caching added       up to 24x  (vLLM paper, sharing-heavy workload)

The gain is proportional to length variance. If all your requests generate exactly 100 tokens, static batching is nearly as good. Real traffic is heavy-tailed, so the gain is large.

8. Production implications#

• This is table stakes. Any LLM serving system without it is leaving 3-10x on the floor.
• Tune max_num_batched_tokens against your ITL SLO. It’s the main lever on the prefill/decode balance.
• Monitor preemption rate. Nonzero is fine; high (>1% of steps) means you’re memory-starved and should reduce max_num_seqs or add capacity.
• Monitor average running batch size. This is your real utilization signal — far more useful than GPU utilization.
• The scheduler is CPU work on the critical path. At high batch, profile it. If Python scheduling takes 3 ms of a 10 ms step, that’s 30% overhead.
• Admission policy is where fairness lives. Multi-tenant systems need priority or weighted fair queueing here (Section XII.05).

9. Common mistakes#

Building your own engine without continuous batching. The most expensive mistake in this curriculum.

Setting max_num_seqs to the memory maximum. Leaves no headroom; causes constant preemption.

Ignoring preemption metrics. Silent thrashing.

Assuming the batch size you configure is the batch size you get. It’s a ceiling.

Not handling the mixed prefill/decode case, so long prompts block decodes.

Letting the Python scheduler dominate at high batch. Profile it.

Unbounded waiting queue. Requests that will never be served in time still consume memory and give users a bad experience. Bound it and reject early (Section VIII.03).

10. Hands-on exercise#

A. Implement it. Extend your generation loop into a continuous-batching engine, following section 4. Support: admission, per-step batching, retirement, and a simple KV manager. Verify outputs match single-request generation. This is Project 08.

B. Measure the gain. With your implementation, simulate 500 requests with lognormal output lengths. Measure throughput and mean TTFT with (i) static batching, (ii) continuous batching. Report the ratio and compare to section 7.

C. Preemption. Deliberately undersize the KV pool and observe preemption. Implement both swap and recompute; measure which is faster for your setup. Explain using the PCIe bandwidth from Section II.09.

D. Tune a real engine. On vLLM, sweep --max-num-batched-tokens over {512, 2048, 8192, 32768} with a mixed workload of long prompts and streaming requests. Plot TTFT p95 and ITL p95 for each. Where’s the knee?

E. Scheduler cost. Profile vLLM’s scheduler at batch 8 vs batch 256. What fraction of step time is Python?

11. Interview questions#

1. Explain continuous batching to a backend engineer in 60 seconds.
2. What two problems of static batching does it solve, and how?
3. Why is preemption-by-recompute often better than preemption-by-swap? Do the arithmetic.
4. What does max_num_batched_tokens control and how would you tune it?
5. Why does the throughput gain depend on the output-length distribution?
6. What state does the engine track per request?
7. Your preemption rate is 15% of steps. What’s happening and what do you do?
8. Why does continuous batching improve both throughput and latency, when usually those trade off?

12. Further reading#

• [ESTABLISHED] Yu et al., “Orca: A Distributed Serving System for Transformer-Based Generative Models” (OSDI 2022) — the paper
• [ESTABLISHED] Kwon et al., “PagedAttention” (SOSP 2023) — the vLLM scheduler
• [REFERENCE] vLLM vllm/core/scheduler.py — read it; it’s ~700 lines and very instructive
• [ESTABLISHED] Anyscale, “How continuous batching enables 23x throughput in LLM inference”
• Next: 10 — PagedAttention