Continuous Batching

Continuous batching is what makes modern inference engines 3-5× faster than naive serving. By scheduling at the iteration level (every decode step) instead of the batch level, it eliminates the idle GPU time from mismatched request lengths.

---

1. The Problem: Static Batching

Static batching groups requests into a batch and processes them together until all requests finish:

Static Batch [A, B, C, D]:
  Step 1:  A  B  C  D     (all active)
  Step 10: A  B  C  D     (A finishes at step 10)
  Step 11: _  B  C  D     (A's slot is IDLE, wasting GPU)
  ...
  Step 50: _  B  _  D     (A and C done, slots idle)
  ...
  Step 200: _  _  _  D    (only D still running, 75% waste)
  Step 200: batch complete → finally start next batch

Effective throughput drops to 25% when only 1 of 4 requests is still generating. New requests must wait until the entire batch finishes — adding queuing delay.

---

2. Continuous Batching: Iteration-Level Scheduling

The key insight: reschedule after every decode step, not after every batch.

Step t:    [A, B, C, D]    (all active)
Step t+10: A finishes → remove A, pull in E from queue
           [E, B, C, D]    (E starts prefill)
Step t+20: C finishes → remove C, pull in F
           [E, B, F, D]
Step t+50: B finishes → remove B, pull in G
           [E, G, F, D]
...
(GPU always has ~4 active requests, never idle slots)

After every step, the scheduler:

1. Checks completions: Any request that hit EOS or max length? → Remove it, free its KV cache
2. Checks queue: Any waiting requests? → Pull them in, start their prefill
3. Assembles batch: All active requests (mix of prefill and decode) form the next step’s batch

---

3. The Scheduling Loop

# Simplified continuous batching scheduler
while True:
    # 1. Remove completed requests
    for req in running_batch:
        if req.is_complete():
            running_batch.remove(req)
            free_kv_cache(req)
            send_response(req)
    
    # 2. Admit new requests (if resources available)
    while waiting_queue and can_admit():
        req = waiting_queue.pop()
        allocate_kv_cache(req)
        running_batch.add(req)
    
    # 3. Execute one step
    for req in running_batch:
        if req.needs_prefill():
            prefill_step(req)     # process prompt tokens
        else:
            decode_step(req)      # generate next token
    
    # 4. Back to step 1 — every iteration!

Prefill and Decode in the Same Batch

A critical detail: newly admitted requests need prefill while existing requests need decode. The batch contains a mix:

Step t: [Decode(B), Decode(D), Decode(E), Prefill(G)]

This mixed batch is handled by the attention backend — prefill tokens process the full prompt, while decode tokens process just one new token each.

For how long prefills are broken into chunks to avoid blocking decode, see Chunked Prefill.

---

4. Impact

Metric	Static Batching	Continuous Batching
Effective batch utilization	20-40%	80-95%
Throughput (tokens/s)	Baseline	3-5× higher
Queue latency	High (wait for batch)	Low (admitted per-step)
Implementation complexity	Simple	Moderate

The throughput gain comes from two sources:

1. No idle slots — completed requests free resources immediately
2. No queue blocking — new requests enter without waiting for a batch to finish

---

5. When Continuous Batching Isn’t Enough

Limitation	Cause	Solution
Long prefill blocks all decode	Prefill monopolizes GPU for one step	Chunked Prefill
KV cache memory exhaustion	Too many concurrent requests	PagedAttention preemption
Shared prefix redundancy	Same system prompt prefilled repeatedly	Prefix Caching

---

Self-Check

• Explain why static batching wastes GPU time with variable-length requests
• Describe the iteration-level scheduling loop (check completions → admit new → execute)
• Explain how prefill and decode requests coexist in the same batch
• Calculate the throughput improvement from eliminating idle slots
• Identify when continuous batching alone isn’t sufficient

---

References

• Orca: A Distributed Serving System for Transformer-Based Generative Models (Yu et al., 2022)
• vLLM: Easy, Fast, and Cheap LLM Serving (Kwon et al., 2023)