Continuous Batching

How long should a GPU sit idle, doing nothing, because it's waiting for one slow request to finish?

The intuitive answer is "zero seconds," and that's the entire motivation for continuous batching. Earlier serving systems made the answer closer to "most of the time." Fixing this turns out to be one of the biggest throughput wins in the entire inference stack.

Understanding why requires thinking about what actually happens when you batch multiple generation requests together.

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. If "memory-bandwidth-bound" means something to you, you're good.

The problem with static batching

Let's say you have four requests arrive at roughly the same time. You know from Post 5.2 that each request goes through a prefill phase (process the prompt in parallel) and then a decode phase (generate tokens one at a time). The decode phase is where the interesting scheduling problem lives, because 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 static batching (sometimes called "naive batching"), you group these four requests into a batch and run them together. Every decode step, the GPU processes all four requests in parallel. That's good, because the GPU has lots of parallel compute and running four sequences through the model costs barely more than running one, as long as the KV cache fits in memory (see Post 5.4).

But here's the problem. Request A finishes after 50 tokens. It hits its EOS token or its max length and it's done. The response is complete. But the batch keeps running, because Requests B, C, and D are still generating. Request A's slot in the batch is now dead weight. The GPU is still doing matrix multiplications for that slot at every step, but the results are meaningless. They get thrown away.

Request B finishes at step 100. Now two slots are wasted. Request C finishes at step 200. Three slots wasted, and the GPU is running at 25% useful utilization 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. GPU utilization: 42.5%.

Why you can't predict request lengths

You might wonder: can we just group requests of similar length together? In theory, sure. In practice, you don't know how long a response will be until the model generates it. 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. Most requests finish well before their limit.

Real-world request length distributions are heavy-tailed. Most requests are short (a quick answer, a one-liner), but a few are long (a detailed explanation, a big code block). So any given batch almost certainly has a mix of short and long requests, and the short ones finish early and sit idle.

The thing that makes this feel urgent is the economics. GPU time is expensive. An H100 costs roughly $2-3 per hour on cloud providers, and serving systems need to handle thousands of concurrent requests. If your GPU is running at 40% utilization because of padding waste, you're effectively paying 2.5x what you should for every generated token.

And it gets worse as batch sizes grow. With a batch of 32 requests, even one outlier that generates 10x more tokens than average drags the whole batch's utilization down. The other 31 slots finish and then just sit there, burning electricity, contributing nothing.

Orca's insight

In 2022, Yu et al. published a paper called "Orca" at OSDI that proposed a clean solution. The core idea is simple: instead of treating the batch as a fixed unit that starts and ends together, treat each decode iteration as a scheduling event.

At every single decode step, the scheduler checks: did any request just finish? If yes, evict it from the batch immediately and admit a new request from the waiting queue. The batch is no longer a static group that lives and dies together. It's a rolling window of active requests that constantly churns.

Decouple scheduling from the batch boundary.

The throughput implications are enormous, though. Hit play on the visualization below and watch the difference. In static mode, gray "idle" cells pile up as shorter requests finish. In continuous mode, new requests fill vacated slots immediately.

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. This is the key property that makes batching worthwhile in the first place: the decode phase is memory-bandwidth-bound, so adding more sequences to a batch barely increases compute time as long as the KV caches fit.

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

One important detail: 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. The active requests see a small per-step slowdown instead of one big stall.

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):
    """Main loop: admit, decode, evict, repeat."""
    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)
            req.kv_cache = model.prefill(req.prompt_tokens)
            active.append(req)
 
        if not active:
            break
 
        # 2. One decode step for every active request
        for req in active:
            next_token = model.decode_step(req.kv_cache)
            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:
                finished.append(req)
            else:
                still_active.append(req)
        active = still_active
 
    return finished

Throughput gains

How much does this actually help? The answer depends on the variance in request lengths.

If every request generates exactly the same number of tokens, continuous batching gives you nothing. There's no waste to eliminate. Static batching works fine because every slot finishes at the same time.

But real traffic has high variance. A chatbot might generate anywhere from 5 to 500 tokens per response. A code completion service might produce 1 line or 50. The higher the variance, the more waste static batching creates, and the bigger the win from continuous batching.

In practice, published benchmarks show 2-8x throughput improvements over static batching. The factor depends on the workload. Conversational workloads with lots of short responses mixed with occasional long ones tend to see the biggest gains. Workloads where every request is roughly the same length (like fixed-length summarization) see smaller improvements.

The gain from continuous batching is directly proportional to the waste in static batching, which is directly proportional to the variance in output lengths. Drag the slider below and watch what happens.

If you're serving a workload where every response is exactly 100 tokens, static batching is fine. Real serving traffic almost never looks like that, though.

Worked example

Let me make this concrete with smaller numbers. Say you have 4 batch slots and requests of lengths 3, 5, 8, and 12 decode steps. And there's a queue of waiting requests behind them: E (4 steps), F (6 steps), G (3 steps).

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. Utilization: 58%.

After step 3, slot 0 goes idle. After step 5, slot 1 goes idle. By step 9, three out of four slots are padding. And requests E, F, G? They're stuck in the queue the entire time, waiting for the batch to drain before they can even start.

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 most of the queued ones. Same hardware, same wall-clock time, roughly 2x the useful output.

Scale it up to 64 batch slots with a heavy-tailed length distribution (median response 30 tokens, p99 response 800 tokens) and the difference becomes dramatic. The long-tail request occupies its slot for 800 steps, and in a static batch every other slot that finished early is wasted for the duration. In a continuous batch, those slots serve dozens of additional requests.

There's a nice way to think about the utilization math. In static batching, utilization equals the average request length divided by the maximum request length in the batch. If the max is 10x the average (which is commonly seen for heavy-tailed distributions), you get 10% utilization. In continuous batching, utilization is closer to batch_size / (batch_size + avg_queue_wait), which approaches 100% as long as the queue isn't empty. The improvement is most dramatic exactly when static batching is worst, which is when you have high variance in output lengths.

Preemption: when memory runs out

There's a subtlety I skipped over. Each active request has a KV cache that grows with every token generated (we covered this in Post 5.4). With a large batch of long requests, you can run out of GPU memory for KV caches.

What do you do? You can't just reject the request, because it's already partially generated. Continuous batching enables a neat trick: preemption. You pause a long-running request (typically the one with the largest KV cache), offload its KV cache to CPU memory, and free up GPU memory for shorter requests that will finish quickly.

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 user sees slightly higher latency for that one request, but overall throughput stays high because the GPU is always doing useful work.

vLLM implements this with PagedAttention, which manages KV cache memory in fixed-size pages (similar to virtual memory in an OS). Pages can be allocated, freed, and swapped to CPU without wasting memory on fragmentation. If you've ever studied how operating systems manage physical RAM with page tables and swap space, the analogy is pretty direct. The KV cache pages are the "physical memory," and the scheduler decides which requests' pages stay resident and which get swapped out.

There are two preemption strategies: recompute (throw away the KV cache, regenerate it later via prefill when the request resumes) and swap (copy the KV cache to CPU RAM and copy it back later). Swapping is faster for long sequences where recomputing the prefill would be expensive, but it requires CPU memory proportional to the offloaded cache.

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 also improve latency, and this is easy to overlook. 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 as soon as any slot opens up. Time-to-first-token drops because you're not stuck behind one slow request.

"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. Continuous batching keeps slots full, and prefix caching keeps the compute you've already paid for.

Additional reading (and watching)

• Yu, G., et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models. OSDI 2022. The paper that introduced iteration-level scheduling and named the problem static batching quietly creates.

• 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 so they stop fighting for the same kernels.