Continuous Batching

When one request finishes before the others in its batch, can a queued request take its place at the next decode iteration?

In a static batch, the queued request waits until the whole batch finishes. Continuous batching can admit it between iterations, subject to memory and scheduling budgets.

Prerequisites

You'll get the most out of this post if you're comfortable with the prefill and decode phases and the KV cache. The short version is that prefill processes the prompt in parallel, decode generates tokens one at a time, and the KV cache stores previously computed attention state so you don't recompute it every step.

The problem with static batching

Suppose four requests arrive at roughly the same time. Each goes through the prefill and decode phases. Decode scheduling must account for the fact that different requests generate different numbers of tokens.

Request A might need 50 output tokens. Request B might need 100. Request C, 200. Request D, 500.

In this fixed, padded static-batch example, the four requests occupy the same four slots until every request finishes. Every decode step, the GPU processes all four requests in parallel. Running several sequences can reuse weight reads, although additional compute and cache traffic increase step time (see Post 5.4).

Request A finishes after 50 tokens, reaching EOS or its length limit. Its slot remains in the padded computation while B, C, and D continue, but its later outputs are discarded. A server that removes finished rows would avoid that padding work; this example measures the fixed-slot baseline.

Request B finishes at step 100. Now two slots are wasted. Request C finishes at step 200. Three slots wasted, and only one of four slots is doing useful token work for the remaining 300 steps until Request D finally finishes.

Add it up. Over 500 time steps across 4 slots, you have 2,000 total cell-steps. Request A used 50, B used 100, C used 200, D used 500. That's 850 useful cells out of 2,000. Useful slot occupancy: 42.5%. This counts scheduled token positions, not measured GPU utilization.

Why you can't predict request lengths

Grouping requests by expected output length can reduce padding, but their actual lengths are unknown before generation. The model decides when to emit EOS. A prompt that says "summarize this in one sentence" might produce 15 tokens or 60, depending on the input. A code generation prompt might produce 10 lines or 200. You can set a max_tokens limit, but that's an upper bound, not a prediction. The gap between actual length and the configured limit depends on the workload.

Orca's insight

In 2022, Yu et al. proposed iteration-level scheduling in "Orca" at OSDI: admit and remove requests at decode-iteration boundaries instead of waiting for the batch to finish.

At each boundary, the scheduler removes finished requests and can admit waiting requests if memory and execution budgets allow.

How it works in practice

The architecture has four pieces:

Request queue. Incoming requests land in a FIFO queue (sometimes with priority). They wait here until a batch slot opens up.

Scheduler. At each decode iteration, the scheduler runs. It checks the active batch for any request that just emitted an EOS token or hit its max output length. Those requests get evicted, their KV caches freed, and their results go back to the client. Then the scheduler looks at the queue. If there are waiting requests and free slots, it admits them. The key constraint is memory: the scheduler can only admit a new request if there's enough GPU memory for its KV cache.

Active batch. The set of requests currently being decoded. Each one is at a different point in its generation. Some might be on their 3rd token, others on their 150th. The GPU processes all of them in a single forward pass each step. Additional sequences can amortize weight traffic when decode is bandwidth-limited. Step time still grows once compute, cache reads, or communication become limiting.

Completed requests. Finished requests with their generated text, ready to be returned to the client.

When a new request joins mid-batch, it needs to go through its own prefill phase to build up its KV cache before it can participate in the shared decode steps. In early implementations, the new request's prefill would block the entire batch for one step. This matters because prefill is more compute-intensive than a single decode step, so a long prompt joining the batch could cause a noticeable stutter for all the other active requests.

Later optimizations like chunked prefill break the prefill into smaller chunks that can be interleaved with ongoing decode steps. Instead of processing 4,096 prompt tokens in one shot, the scheduler might process 512 tokens of the new prompt per iteration, spreading the cost across 8 steps. This bounds the prefill work added to each iteration, though its effect on decode latency depends on the chunk and batch sizes.

from dataclasses import dataclass, field
 
@dataclass
class Request:
    id: str
    prompt_tokens: list[int]
    max_new_tokens: int
    generated: list[int] = field(default_factory=list)
    kv_cache: object = None
    done: bool = False
 
def continuous_batching_loop(model, queue: list[Request], max_batch: int = 4):
    """Scheduling sketch; model methods are application adapters.
    Prefill stores the pending next-token logits in each request state.
    decode_batch samples those logits and advances surviving requests.
    """
    if max_batch < 1:
        raise ValueError("max_batch must be positive")
    active: list[Request] = []
    finished: list[Request] = []
 
    while active or queue:
        # 1. Admit new requests into empty slots
        while len(active) < max_batch and queue:
            req = queue.pop(0)
            if req.max_new_tokens <= 0:
                req.done = True
                finished.append(req)
                continue
            req.kv_cache = model.prefill(req.prompt_tokens)
            active.append(req)
 
        if not active:
            break
 
        # 2. One decode step for every active request
        next_tokens = model.decode_batch([req.kv_cache for req in active])
        for req, next_token in zip(active, next_tokens):
            req.generated.append(next_token)
            if next_token == EOS or len(req.generated) >= req.max_new_tokens:
                req.done = True
 
        # 3. Evict finished requests, free their memory
        still_active = []
        for req in active:
            if req.done:
                req.kv_cache = None  # release the completed request state
                finished.append(req)
            else:
                still_active.append(req)
        active = still_active
 
    return finished

Throughput gains

For one simultaneously admitted cohort whose requests all finish together, continuous batching has no empty slots to refill. With staggered arrivals or prefill work, scheduling can still matter even when output lengths are equal.

A workload with varied output lengths leaves more padding in a fixed batch. Refilling that capacity requires queued work and enough memory to admit it.

Worked example

Consider 4 batch slots and requests of lengths 3, 5, 8, and 12 decode steps, with E (4 steps), F (6 steps), and G (3 steps) waiting in the queue.

Static batching: All 4 slots run for 12 steps (padded to the longest). That's 4 x 12 = 48 total cell-steps. Active cells: 3 + 5 + 8 + 12 = 28. Wasted cells: 20. Slot occupancy: 58.3%.

After step 3, slot 0 goes idle. After step 5, slot 1 goes idle. By step 9, three out of four slots are padding. E, F, and G wait for the batch to finish before starting.

Continuous batching: Request A finishes at step 3. The scheduler immediately evicts it and admits E into that slot. E starts generating and will finish at step 7. Request B finishes at step 5, F enters. When E finishes at step 7, G enters. The slots stay occupied almost the entire time.

By the time the static batch would have finished its 12 steps, the continuous batch has served all 4 original requests plus all three queued requests. Over the same 12-iteration window, it performs 41 useful token steps instead of 28: about 1.46× as many. Calling that a wall-clock throughput gain additionally assumes equal iteration durations and omits prefill/admission cost; real step time depends on the active batch.

For the fixed padded batch, slot occupancy equals the average request length divided by the maximum length. A maximum 10 times the average gives 10% occupancy. For either scheduler, the metric is useful token steps divided by available slot-steps; continuous batching approaches full occupancy only while enough ready work is available.

Preemption: when memory runs out

Each active request has a KV cache that grows with every generated token. A batch of long requests can exhaust GPU cache memory even if all requests fit when admitted.

One option is to abort a request, but a scheduler can instead preserve it for later. With a swapping policy, it pauses the request and offloads its KV cache to CPU memory, freeing GPU memory for other work. Other policies discard the cache and later recompute it; preemption does not always imply a CPU swap.

Once the shorter requests complete and free their KV cache memory, you reload the paused request's KV cache back onto the GPU and resume generation from where it left off. The paused request waits longer. Whether this improves total throughput depends on transfer cost, the replacement work, and the scheduler.

PagedAttention manages KV cache memory in fixed-size blocks, reducing external fragmentation while retaining some partially filled-block waste.

Recomputation spends model compute to rebuild the discarded state; swapping spends transfer bandwidth and CPU memory to preserve it. Their relative cost depends on the cache size and hardware.

Misconceptions

"Continuous batching eliminates all waste." There's still overhead from request admission (prefill for new requests) and memory management. And if the queue is empty, you can't fill vacated slots. The utilization gain depends on having enough queued requests to keep the batch full.

"It only helps throughput, not latency." It can reduce queueing latency. In static batching, a new request has to wait for the entire current batch to finish before it can start. If the slowest request in the current batch needs 500 more tokens, the new request waits 500 steps. In continuous batching, the new request can enter at an earlier iteration boundary if admission budgets allow, shortening the queueing part of time-to-first-token.

"Bigger batches are always better." Larger batches improve throughput up to a point, but eventually you hit either memory limits (KV caches don't fit) or compute saturation (the GPU is fully utilized and adding more requests just increases latency for everyone). The sweet spot depends on model size, sequence length, and hardware.

What's next

The next post covers prefix caching: what happens when multiple requests share the same prompt prefix and how modern servers skip the prefill work for the shared bytes entirely.

Additional reading (and watching)

• Yu, G., et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models. OSDI 2022. Introduces iteration-level scheduling and evaluates it against static batching.

• Kwon, W., et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP 2023. The vLLM paper; pairs continuous batching with paged KV cache management and preemption.

• Agrawal, A., et al. (2023). Sarathi: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills. arXiv preprint. Chunked prefill, which keeps new-request admission from stalling the batch.

• Patel, P., et al. (2023). Splitwise: Efficient generative LLM inference using phase splitting. arXiv preprint. Splits prefill-heavy and decode-heavy work across machines with separate hardware allocations.