Continuous Batching: Optimizing LLM Inference Throughput › Iteration-Level Scheduling
Language AI HandbookAll chapters Continuous Batching: Optimizing LLM Inference Throughput › Iteration-Level SchedulingOne section · Sections in this chapter5 / 14 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
The power of continuous batching comes from making scheduling decisions at every iteration. Rather than committing to a fixed plan when a batch starts, the system reevaluates its choices thousands of times per second. This fine-grained control lets advanced policies beyond simple FIFO ordering and allows the system to adapt dynamically to changing conditions.
Iteration-level scheduling is a fundamentally different mental model from batch-level scheduling. In batch-level thinking, the scheduler plans who gets to run for the next several hundred milliseconds. In iteration-level thinking, the scheduler decides who runs for the next 10 to 50 milliseconds, then immediately reconsiders. This rapid reconsideration is what lets the system to react quickly to completions, memory pressure, and priority changes.
Think of iteration-level scheduling like air traffic control at a busy airport. Rather than assigning each plane to a runway at the start of the day and having it sit there regardless of what happens, air traffic controllers continuously decide which plane goes next. They adapt to delays and changing weather, including emergencies. A plane that taxied out for a 30-minute flight does not hold its runway slot while slower cross-country flights catch up. The runway is always occupied with the next available plane.
Scheduling Decisions
At each iteration boundary, the scheduler faces several interconnected decisions that determine both throughput and fairness. These decisions happen in microseconds and must balance competing objectives.
Which requests to evict: Besides naturally completed requests, the scheduler might preempt requests to free memory for higher-priority work. This creates interesting tradeoffs between fairness and throughput. A request that has already consumed significant resources is sunk compute cost, but continuing it also delays new requests. The scheduler must weigh these factors according to the system's priorities. Most production systems avoid preemption except under severe memory pressure, preferring instead to rely on natural completion to free slots.
Which waiting requests to admit: When multiple requests are waiting, the scheduler chooses which to start first. This decision materially impacts user-perceived latency and overall system efficiency. Options include:
- FIFO. First-come, first-served, which is simple and fair. Every request eventually gets its turn in the order it arrived. This approach gives predictable behavior and prevents starvation.
- Shortest Job First. Prioritize requests with shorter expected outputs to minimize average latency. Short requests complete quickly, improving user experience. However, this requires predicting output length, which is not always possible.
- Priority-based. Honor explicit priority levels attached to requests. Time-sensitive applications might receive preferential treatment. This approach requires clear policies about what constitutes priority and careful tuning to prevent starvation of low-priority requests.
How to handle memory pressure: When the KV cache approaches capacity, the scheduler must decide whether to wait for completions or preempt active requests. Waiting reduces throughput but preserves work in progress. Preemption frees resources immediately but wastes the computation already invested in the preempted request. Systems like vLLM use a "swap" mechanism that saves KV caches to CPU memory before preemption, letting resumption without full recomputation, though this adds latency.
The scheduling policy also determines how the system handles surges. When a sudden burst of requests arrives and the queue grows long, the scheduler must decide whether to admit many short requests quickly or maintain fair ordering. Most production systems prioritize fairness to avoid the situation where a user submitting a long job during a burst waits arbitrarily longer than someone who arrived moments later.
Prefill and Decode Phases
Continuous batching must handle requests in different phases of their lifecycle. As we discussed in the KV Cache chapter, generation has two distinct phases with fundamentally different computational characteristics.
Prefill phase: Process all input tokens in parallel to build the initial KV cache. This phase is compute-bound and benefits from large batches of tokens. The GPU performs dense matrix multiplications over potentially thousands of input tokens, fully utilizing its computational capacity. Memory bandwidth is not the bottleneck during prefill because the computation is so intensive. A prompt with 2000 tokens generates 2000 key-value pairs simultaneously in a single forward pass.
Decode phase: Generate tokens one at a time, reading from the KV cache. This phase is memory-bandwidth-bound and benefits from large batches of requests. Each decode step reads the entire KV cache but performs relatively little computation per byte loaded. The GPU spends most of its time waiting for memory operations to complete, not performing arithmetic. This is why batching many requests together in the decode phase is so important: each request reads a different part of memory in parallel, amortizing the memory latency across many concurrent streams.
These phases have different computational characteristics that create challenges when mixing them in the same batch. Prefill processes many tokens per request; decode processes one token per request. Mixing them creates load imbalance: prefill requests demand heavy compute while decode requests sit largely idle waiting for memory operations to complete. The compute and memory bandwidth resources are used differently, which makes it harder to fully utilize either.
@dataclass
class PhasedRequest:
"""Request tracking both prefill and decode phases."""
id: int
input_length: int
output_length: int
phase: str = "prefill" # "prefill" or "decode"
tokens_generated: int = 0
prefill_complete: bool = False
class PhasedBatchSimulator:
"""Simulator showing prefill/decode phase handling."""
def __init__(self, max_batch_size: int = 8):
self.max_batch_size = max_batch_size
self.active_batch: List[PhasedRequest] = []
self.waiting_queue: deque = deque()
self.completed: List[PhasedRequest] = []
self.iteration = 0
# Track phase composition over time
self.phase_history = []
def submit_request(self, request: PhasedRequest):
self.waiting_queue.append(request)
def _fill_batch(self):
"""Add waiting requests to available slots."""
while (
len(self.active_batch) < self.max_batch_size and self.waiting_queue
):
request = self.waiting_queue.popleft()
request.phase = "prefill"
self.active_batch.append(request)
def step(self):
"""Execute one iteration."""
self._fill_batch()
if not self.active_batch:
return False
# Count phases
prefill_count = sum(
1 for r in self.active_batch if r.phase == "prefill"
)
decode_count = len(self.active_batch) - prefill_count
self.phase_history.append(
{
"iteration": self.iteration,
"prefill": prefill_count,
"decode": decode_count,
}
)
# Process each request based on phase
still_active = []
for request in self.active_batch:
if request.phase == "prefill":
# Prefill completes in one iteration (simplified)
request.prefill_complete = True
request.phase = "decode"
still_active.append(request)
else: # decode phase
request.tokens_generated += 1
if request.tokens_generated >= request.output_length:
self.completed.append(request)
else:
still_active.append(request)
self.active_batch = still_active
self.iteration += 1
return True
def run_until_complete(self):
while self.active_batch or self.waiting_queue:
self.step()Chunked Prefill
Modern continuous batching systems often use chunked prefill to better balance the two phases and smooth out the computational load. Instead of processing the entire prompt in one iteration, which can cause latency spikes when long prompts arrive, long prompts are split into manageable chunks.
The problem that chunked prefill solves is sometimes called "prefill monopolization." When a request with a 4000-token prompt arrives, the prefill phase consumes the entire GPU for 10-15 milliseconds while thousands of queued decode steps for existing requests are blocked. From those existing requests' perspectives, the system has frozen. Their time-to-next-token spikes sharply, even though they have been running smoothly for hundreds of iterations.
The chunking strategy divides a long prompt into pieces that can be processed incrementally. This allows decode iterations for other requests to proceed between prefill chunks, maintaining responsiveness. A request with a 3000-token prompt might be split into six chunks of 500 tokens each, with each chunk processed in a separate iteration, interleaved with decode steps for existing requests.
def chunk_prefill_tokens(input_length: int, chunk_size: int = 512) -> List[int]:
"""Split a prompt into prefill chunks."""
chunks = []
remaining = input_length
while remaining > 0:
chunk = min(remaining, chunk_size)
chunks.append(chunk)
remaining -= chunk
return chunks# Example chunking
chunk_size = 512
example_lengths = [128, 512, 1500, 3000]
chunking_results = []
for length in example_lengths:
chunks = chunk_prefill_tokens(length, chunk_size)
chunking_results.append((length, chunks))Prefill Chunking Examples (chunk_size=512): 128 tokens -> 1 chunks: [128] 512 tokens -> 1 chunks: [512] 1500 tokens -> 3 chunks: [512, 512, 476] 3000 tokens -> 6 chunks: [512, 512, 512, 512, 512, 440]
Chunked prefill lets interleaving decode tokens between prefill chunks, reducing latency spikes when long prompts arrive. Without chunking, a 3000-token prompt would monopolize the GPU for a significant duration, blocking all decode operations for other requests. With chunking, decode operations proceed smoothly while the long prompt is processed incrementally. The cost is that the prefilling request takes longer to complete its context ingestion, but this tradeoff is almost always worth it in serving scenarios with multiple concurrent users.