Continuous Batching

Unlike static batching, which waits for a fixed number of requests to accumulate, continuous batching forms batches dynamically from a pool of incoming requests. The scheduler continuously adds new requests and removes completed ones, ensuring the GPU is never idle waiting for a batch to fill. This is crucial for interactive applications where requests arrive asynchronously and have highly variable sequence lengths (e.g., short queries vs. long document summarization).

The core innovation is scheduling at the token generation level, not the request level. Within a single batch, each request can be at a different stage of its generation:

• Prefill Phase: The initial parallel computation of the prompt.
• Decode Phase: The sequential, autoregressive generation of output tokens. The scheduler manages a hybrid batch containing requests in both phases simultaneously. As some requests finish generation, they are removed, and new requests in the prefill phase are added, creating a continuous flow of work.

Efficient memory management for the Key-Value (KV) Cache is essential. Each request's cache grows as it generates tokens. Continuous batching requires the system to:

• Dynamically allocate and free GPU memory for each request's KV cache.
• Handle highly variable sequence lengths without wasting memory due to padding (which static batching requires). Advanced systems like vLLM use PagedAttention, which treats the KV cache as non-contiguous 'pages' in memory. This allows for efficient sharing of memory blocks between requests and eliminates fragmentation, which is critical for maintaining high throughput with continuous batching.

Continuous batching optimizes for aggregate throughput (tokens/second across all users) but introduces nuanced latency characteristics:

• Improved Tail Latency: New requests don't wait for a full batch; they can join an existing batch almost immediately, reducing queue time.
• Potential Per-Request Latency Increase: A request in the decode phase may have its generation slightly delayed while the GPU works on the prefill phase of newer requests in the same batch. The overall system efficiency gain typically outweighs this minor per-iteration delay. The technique is designed for high-throughput serving scenarios where maximizing GPU utilization is the primary cost driver.

Continuous batching is a foundational feature of modern, high-performance LLM serving engines:

• vLLM: Implements it with its PagedAttention backend, achieving near-linear throughput scaling with batch size.
• TensorRT-LLM: Calls it in-flight batching, integrating it with its compiled graph optimizations for NVIDIA GPUs.
• Triton Inference Server: Supports dynamic batching with a configurable window to group inference requests. These implementations handle the complex orchestration of variable-length sequences, memory management, and scheduling transparently to the user.

Unlike static batching which waits for a fixed batch size, continuous batching treats the batch as a live set. New requests are inserted as they arrive, and completed sequences are immediately evicted upon generating an end-of-sequence token. This creates a rolling batch that maintains a high GPU occupancy with heterogeneous sequence lengths, dramatically improving overall system throughput.

The scheduler operates at the granularity of a single decoding iteration. For each iteration:

• The engine computes the next token for all active sequences in the current batch.
• It updates the KV cache for each sequence.
• Sequences that have finished are removed.
• New sequences are added if resources allow. This fine-grained control minimizes idle time, as the GPU is never waiting for a slow sequence to finish before starting work on new ones.

Continuous batching's efficiency is tightly coupled with advanced KV cache management. The PagedAttention algorithm, pioneered by vLLM, is critical. It:

• Treats the KV cache as non-contiguous memory pages.
• Allows flexible allocation and sharing of cache blocks across sequences.
• Eliminates memory fragmentation caused by variable-length sequences.
• Enables memory sharing for prompts in multi-tenant scenarios, further optimizing memory usage.

NVIDIA's TensorRT-LLM implements a similar concept called in-flight batching. It leverages the TensorRT runtime to:

• Dynamically manage batch composition within a pre-compiled engine.
• Integrate with KV cache management and attention kernels optimized for variable batch sizes.
• Utilize continuous batching alongside other optimizations like operator fusion and quantization for peak performance on NVIDIA GPUs.

Implementing continuous batching involves balancing key parameters:

• Max Batch Size: The physical limit of concurrent sequences, constrained by GPU memory (primarily KV cache).
• Scheduling Policy: Deciding which requests to admit next (e.g., FIFO, priority).
• Preemption: Whether to pause a long-running sequence to admit a higher-priority one.
• Latency vs. Throughput: While maximizing throughput, engineers must monitor tail latency (P99) to ensure individual user experience doesn't degrade.

Key-Value (KV) Caching is a fundamental optimization that stores the computed key and value tensors for previously processed tokens in memory. During autoregressive generation, this cache is reused for each new token, eliminating the need to recompute attention over the entire prior context for every forward pass. Continuous batching's efficiency is heavily dependent on effective KV cache management, as each request in a dynamic batch maintains its own cache, making memory allocation and sharing critical.

PagedAttention is the memory management algorithm that enables vLLM's high-performance continuous batching. It treats the KV cache as non-contiguous, pageable memory (similar to an operating system). This allows for:

• Elimination of memory fragmentation from variable-length sequences.
• Efficient sharing of cached prompt computations across multiple generation requests.
• Dynamic allocation of cache space, which is essential for continuous batching where new requests with unknown final lengths are constantly added. Without PagedAttention, continuous batching would be severely limited by wasted memory.

In-Flight Batching (or Iteration-Level Batching) is the core scheduling mechanism that makes continuous batching possible. Unlike static batching which processes a fixed set of requests to completion, in-flight batching:

• Re-evaluates the batch composition at every decoding iteration (step).
• Adds new requests to the batch as soon as they arrive.
• Removes completed sequences from the batch, freeing resources.
• Maintains a 'ragged' tensor where each sequence in the batch can be at a different generation step. This dynamic scheduling is what allows GPUs to maintain near-100% utilization under variable load.

Continuous batching fundamentally optimizes for aggregate throughput (tokens/second across all users) at the potential cost of increased per-request latency for individual users. This is a key trade-off:

• Static Batching: Favors latency for requests that wait for the batch to fill, but maximizes throughput once the batch is full.
• Continuous Batching: Minimizes queue time (good for latency) but can introduce slight overhead from managing a dynamic, ragged batch, and may delay the completion of a single request if the GPU is kept busy serving many small, new requests. The optimal configuration balances these metrics based on service-level objectives (SLOs).