Continuous Batching Explained: Iteration-Level Scheduling in Modern LLM Servers

In traditional web microservices and classical machine learning inference (such as image classification or tabular models), request processing is homogeneous and predictable: an input array is submitted, a single forward pass is executed, and a response is returned within fixed millisecond budgets.

Generative Large Language Models, however, present a unique challenge: requests are radically heterogeneous in both prompt length and generation length. A quick factual query may finish in 10 tokens, while a complex coding prompt in the same batch may require 2,000 tokens.

This lesson explores why traditional Static Batching and Dynamic Request-Level Batching cripple GPU throughput, and how Continuous Batching (Iteration-Level Scheduling) solves the Head-of-Line blocking dilemma.

1. The Breakdown of Legacy Batching Paradigms

A. Static Batching

In static batching, the serving engine waits for $B$ requests to accumulate (or times out), groups them into a fixed batch tensor, and pads all input sequences to the maximum length of the batch:

1. Padded Compute Waste: If Request 1 has 50 prompt tokens and Request 2 has 2,000 prompt tokens, Request 1 must be padded with 1,950 dummy <pad> tokens. The GPU executes floating-point matrix multiplications on meaningless zeros.
2. Head-of-Line (HoL) Blocking: The batch must stay locked in execution until the longest generation request emits its stop token. If one user requests a full 2,000-token essay, 31 other users who asked simple yes/no questions have their responses withheld until the essay finishes!

B. Dynamic Request-Level Batching (Triton / TorchServe)

Dynamic batching improved on static batching by introducing a queue timeout (e.g., max_batch_delay = 50ms). However, once a batch was assembled, it was treated as an atomic, immutable execution unit. Finished requests could not be evicted, and incoming requests could not join a running batch until all active requests in that batch finished.

2. The Orca / vLLM Breakthrough: Iteration-Level Continuous Batching

In 2022, Microsoft Research published Orca (Yu et al.), introducing the concept of Iteration-Level Scheduling (commonly called Continuous Batching or Cellular Batching).

Instead of treating a batch as an immutable set of requests that runs to completion over hundreds of iterations, the scheduler operates at the granularity of a single forward pass (iteration).

How Continuous Batching Operates:

1. Per-Iteration Decision: At the start of every forward pass, the scheduler inspects:
   • Which active decoding requests emitted an <eos> token or hit max_tokens $\to$ Evict them immediately and stream completion to client.
   • Which requests in the waiting queue can fit into the free KV cache block budget $\to$ Inject them immediately into the next forward pass.
2. Elimination of Padding: Because sequences are addressed dynamically through PagedAttention block tables, input and output tensors are flattened into a 1D packed jagged array. Zero padding tokens are processed.
3. Throughput Scaling: Continuous batching achieves up to $10\times -20\times$ higher token throughput than static batching under realistic multi-tenant traffic distributions.

3. Minimal Python Implementation: Continuous Batch Scheduler

The following Python script simulates an iteration-level continuous batching engine that manages a waiting queue, dynamically inserts new prompts, and evicts completed sequences on every forward pass.

4. 🏆 Landmark Global Arena Capstone #3 Preview

In Arena Capstone #3 (global-llm-continuous-batch-scheduler), you will build a complete iteration-level continuous batch scheduler featuring:

• Priority waiting queues and prefill/decode slot allocation.
• Dynamic eviction of finished sequences on the exact token iteration they emit <eos>.
• Immediate slot backfilling with arriving requests.
• Metrics tracking for Time to First Token (TTFT) and Inter-Token Latency (ITL).

5. Summary & Key Takeaways

1. Static Batching Causes Severe Head-of-Line Blocking: Waiting for the slowest request in a batch forces finished GPU slots to sit completely idle.
2. Continuous Batching Operates Per-Iteration: The scheduler makes insertion and eviction decisions on every single forward pass step.
3. Zero Padding Waste: By leveraging ragged tensor layouts and PagedAttention, continuous batching eliminates all <pad> token computations.
4. Massive Throughput Gains: Continuous batching delivers a $10\times -20\times$ throughput multiplier for production multi-tenant inference workloads.