Throughput Optimization › Continuous Batching

Continuous batching (also called iteration-level scheduling or in-flight batching) solves the static batching inefficiency by decoupling batch construction from request lifecycle. Instead of assembling a batch and running it to completion, the system re-evaluates the batch composition after every single generation step.

After each decoding iteration, the scheduler checks two things:

1. Which requests in the current batch have just finished (generated an end-of-sequence token or hit the maximum length)?
2. Which new requests are waiting in the queue?

Finished requests are immediately evicted. Their KV cache memory is freed. New requests are inserted to fill the freed slots. The next iteration processes a fresh batch that may contain requests at completely different generation stages.

This seemingly simple change greatly improves utilization. Consider a batch of 8 requests. With static batching, if 6 requests finish at step 20 but 2 continue to step 200, those 6 slots sit idle for 180 steps. With continuous batching, those 6 slots are filled with new requests at step 21. The GPU is doing useful work for those 180 steps instead of waiting.

The scheduler also handles prefill integration naturally. When a new request is admitted to the batch, its prompt tokens are processed in a prefill pass before the first decode step. Modern continuous batching implementations (such as vLLM and TGI) interleave prefill and decode at the step level, so a newly admitted request contributes its first generated token to the output stream within one scheduling interval.

One question that arises when learning about continuous batching is how requests at different generation stages can run together. Request A is at token 150, request B is at token 5, request C was just admitted. How does the GPU handle this?

The answer is that the GPU does not care. Each decode step processes one token per request in the batch, using that request's current KV cache state. The model parameters are shared, and the input to each request's decode step is simply its most recently generated token plus its KV cache. Whether that KV cache has 150 entries or 5 entries is irrelevant to the GPU; it reads the relevant portion and proceeds.

The KV cache for each request grows by one entry per decode step. The memory manager needs to track each request's current KV cache size and ensure new pages are allocated as requests grow. This is where PagedAttention becomes critical, as we discuss below.

The throughput improvement from continuous batching depends on the variance in output lengths across your workload. For uniform output lengths, there is no benefit because all requests finish simultaneously anyway. For highly variable output lengths (typical in production, where users ask a mix of simple and complex questions), the improvement is substantial.

Empirical results from the vLLM evaluation (Kwon et al., 2023) showed 2-4x higher throughput compared to static batching on standard benchmarks, with the improvement growing as batch sizes increased and output length variance widened. Real production systems often see even larger improvements because production length distributions are more variable than benchmark distributions, which tend to use fixed or narrow length ranges.

The intuition for the improvement is simple: every batch slot that static batching leaves idle is a slot that continuous batching fills with real work. The more long requests in your workload, the more idle slots static batching creates, and the more benefit continuous batching delivers.

Continuous batching requires fine-grained memory management. Each active request holds a KV cache: the stored key and value tensors from all previous attention layers and all previous tokens. A 7B-parameter model with 32 attention layers and 32 key/value heads, processing sequences up to 2048 tokens, needs roughly:

$$M_{\text{kv}} = 2 \times L \times n_{h} \times d_{h} \times T \times \text{bytes\_per\_element}$$

where:

• $2$: factor for storing both keys and values
• $L$: number of transformer layers
• $n_{h}$: number of attention heads (or key-value heads in grouped-query attention)
• $d_{h}$: head dimension ($d_{\text{model}} / n_h$)
• $T$: current sequence length
• $\text{bytes\_per\_element}$: typically 2 bytes for FP16

For a 7B model this works out to roughly 1 MB per token of KV cache. A batch of 100 requests at 500 tokens each occupies about 50 GB of KV cache alone, exceeding the memory of a single A100 GPU.

The traditional approach to KV cache allocation pre-allocates a contiguous block of memory for each request, sized for the maximum possible output length. This wastes enormous amounts of memory when requests complete early, because the pre-allocated but unused portions of the block sit empty until the request finishes and the entire block is freed.

PagedAttention (Kwon et al., 2023) addresses this by managing KV cache in fixed-size pages, similar to virtual memory in operating systems. Rather than allocating a contiguous block for each request's full context, the system allocates pages on demand as the sequence grows and reclaims them when the request completes. This eliminates fragmentation and enables the fine-grained memory sharing needed for efficient continuous batching.

The page size is a tunable parameter. Smaller pages reduce internal fragmentation (wasted space within a partially filled page) but increase bookkeeping overhead. Larger pages reduce bookkeeping but increase fragmentation. Most implementations use page sizes between 16 and 64 tokens, which balances these concerns across typical workloads.

PagedAttention also enables memory sharing between requests with the same prompt prefix. In a system serving many users with the same system prompt, the KV cache pages for that shared prefix can be stored once and pointed to by all active requests. This prefix caching can dramatically reduce KV cache memory usage in applications with long, fixed system prompts.

The simulation shows continuous batching requires significantly fewer total GPU steps to process the same set of requests. This translates directly to higher throughput: the GPU spends more of its time generating tokens that users are waiting for, and less time running steps for requests that have already finished.

The magnitude of the improvement depends heavily on the length distribution. A workload with very uniform output lengths shows little improvement. A workload with extreme variance (some requests finishing in 5 tokens, others running to 2,000) shows improvements approaching the ratio of longest to shortest output. This is exactly the distribution you see in production chat services, where users sometimes ask trivial yes/no questions and sometimes request multi-page documents.

The scheduler in a continuous batching system is responsible for several decisions that directly affect throughput:

Admission control decides which waiting requests enter the active batch. A simple scheduler admits requests in arrival order. More sophisticated schedulers use priority queues, preempt long-running requests when high-priority work arrives, or reserve capacity for interactive users versus batch users.

Memory management tracks available KV cache pages and denies admission when memory is insufficient. Without this gate, requests that exceed available memory will cause out-of-memory errors that crash the serving process. The scheduler must model expected KV cache growth to prevent over-admission.

Preemption handles the case where a long-running request occupies a slot that a high-priority request needs. The scheduler can checkpoint the long request's KV cache state, evict it from the batch, process the high-priority request, then restore the long request when capacity is available. This adds latency to the preempted request but protects latency for high-priority work. Most production schedulers implement preemption as a last resort, triggering only when memory pressure is severe.