Simulate continuous batching

The first time I read the Orca paper (Yu et al., 2022), the core idea seemed almost too simple: instead of waiting for every request in a batch to finish before starting new ones, just swap finished requests out and new ones in at every iteration. It took building a simulator to really understand how much this matters.

The problem with static batching

In static (or naive) batching, you collect a fixed number of requests, pad them to the same sequence length, and run them together until every request in the batch has produced its EOS token or hit the max length. The problem is obvious: if one request generates 500 tokens and another generates 20, the short request's GPU slot sits idle for 480 decode steps.

This is not a minor inefficiency. In real workloads, output lengths vary wildly. A summarization request might produce 50 tokens while a code generation request produces 2,000. Static batching means your effective throughput is determined by the longest request in the batch, not the average.

How continuous batching works

Continuous batching (also called iteration-level batching or in-flight batching) operates at the granularity of individual decode steps. After every step, the scheduler:

Checks which requests have finished (hit EOS or max length).
Removes finished requests from the batch.
Checks the waiting queue for new requests.
Runs prefill for new requests and adds them to the batch.
Runs the next decode step for the updated batch.

The GPU stays full. A slot freed by a finished request is immediately taken by a waiting request. There is no idle padding.

Building the simulator

I wrote a simple Python simulator to compare the two approaches. The simulator does not run actual GPU computation; instead it models the timing of prefill and decode steps based on realistic per-token latencies.

import random
from dataclasses import dataclass, field
from collections import deque

@dataclass
class Request:
    id: int
    prompt_len: int
    output_len: int
    arrival_time: float
    start_time: float = 0.0
    end_time: float = 0.0
    tokens_generated: int = 0

def generate_workload(n_requests, arrival_rate=10.0):
    """Generate requests with Poisson arrivals and variable output lengths."""
    requests = []
    t = 0.0
    for i in range(n_requests):
        t += random.expovariate(arrival_rate)
        prompt_len = random.randint(128, 1024)
        output_len = random.randint(16, 512)
        requests.append(Request(id=i, prompt_len=prompt_len,
                                output_len=output_len, arrival_time=t))
    return requests

# Timing constants (milliseconds per token, approximate H100 values)
PREFILL_MS_PER_TOKEN = 0.02   # compute-bound, fast per token
DECODE_MS_PER_STEP = 8.0      # memory-bound, fixed cost per step

Static batching simulator

def simulate_static(requests, max_batch_size=8):
    """Static batching: wait for full batch, pad to longest, run to completion."""
    queue = deque(requests)
    clock = 0.0
    completed = []

    while queue:
        # Collect a batch
        batch = []
        while queue and len(batch) < max_batch_size:
            req = queue.popleft()
            req.start_time = max(clock, req.arrival_time)
            batch.append(req)

        if not batch:
            break

        clock = max(r.start_time for r in batch)

        # Prefill: process all prompts (padded to longest)
        max_prompt = max(r.prompt_len for r in batch)
        prefill_time = max_prompt * PREFILL_MS_PER_TOKEN * len(batch)
        clock += prefill_time

        # Decode: run until the longest output is done
        max_output = max(r.output_len for r in batch)
        decode_time = max_output * DECODE_MS_PER_STEP
        clock += decode_time

        for r in batch:
            r.end_time = clock
            r.tokens_generated = r.output_len
            completed.append(r)

    return completed

Continuous batching simulator

def simulate_continuous(requests, max_batch_size=8):
    """Continuous batching: add/remove requests at every decode step."""
    waiting = deque(requests)
    active = []
    completed = []
    clock = 0.0

    while waiting or active:
        # Admit new requests if slots are available
        while waiting and len(active) < max_batch_size:
            req = waiting[0]
            if req.arrival_time <= clock:
                req = waiting.popleft()
                req.start_time = clock
                # Pay prefill cost for this request
                clock += req.prompt_len * PREFILL_MS_PER_TOKEN
                active.append(req)
            else:
                break

        if not active:
            if waiting:
                clock = waiting[0].arrival_time
                continue
            break

        # One decode step for all active requests
        clock += DECODE_MS_PER_STEP

        # Update token counts and check for completion
        still_active = []
        for req in active:
            req.tokens_generated += 1
            if req.tokens_generated >= req.output_len:
                req.end_time = clock
                completed.append(req)
            else:
                still_active.append(req)

        active = still_active

    return completed

Results

Running 200 requests with a Poisson arrival rate of 10 requests per second and output lengths uniformly distributed between 16 and 512 tokens:

random.seed(42)
workload = generate_workload(200, arrival_rate=10.0)

static_results = simulate_static(list(workload), max_batch_size=8)
continuous_results = simulate_continuous(list(workload), max_batch_size=8)

def report(results, label):
    latencies = [(r.end_time - r.arrival_time) for r in results]
    ttfts = [(r.start_time - r.arrival_time) for r in results]
    total_time = max(r.end_time for r in results)
    total_tokens = sum(r.tokens_generated for r in results)
    print(f"{label}:")
    print(f"  Total time:     {total_time:.0f} ms")
    print(f"  Throughput:     {total_tokens / (total_time/1000):.0f} tok/s")
    print(f"  Median latency: {sorted(latencies)[len(latencies)//2]:.0f} ms")
    print(f"  P99 latency:    {sorted(latencies)[int(len(latencies)*0.99)]:.0f} ms")
    print(f"  Median TTFT:    {sorted(ttfts)[len(ttfts)//2]:.0f} ms")

The continuous batching simulator consistently shows 2 to 3x better throughput and significantly lower median latency. The improvement comes from two sources: eliminated padding waste and reduced queuing delay (requests enter the batch sooner because slots free up as soon as individual requests finish rather than waiting for the entire batch).

What the simulator reveals

The throughput advantage of continuous batching grows with output length variance. When all requests produce the same number of tokens, the two approaches converge. The more diverse your workload, the more continuous batching helps.

What real systems add on top

This simulator captures the core scheduling logic, but production systems like vLLM and SGLang add several sophistications:

Chunked prefill: Instead of blocking the batch to run a full prefill, the prompt is processed in chunks interleaved with decode steps. This bounds the latency impact of long prompts on the decode batch.
Preemption: If GPU memory runs low, the scheduler can preempt lower-priority requests, saving their KV cache to CPU memory and resuming them later.
Prefix caching: Requests with shared prefixes skip redundant prefill computation, as I explored on day 40.

Continuous batching is the single most important scheduling optimization in LLM serving. It transforms GPU utilization from "limited by your slowest request" to "limited by your batch size."

Next: visualizing PagedAttention's block layout to see how the KV cache memory that backs continuous batching is actually organized.