Hugging Face: Continuous Batching from First Principles

Continuous batching is a critical optimization for Large Language Model (LLM) serving that maximizes throughput by processing multiple conversations in parallel and swapping them out as soon as they are completed. By eliminating the need for padding and allowing the simultaneous processing of prefill and decoding phases, continuous batching enables AI services to handle thousands of concurrent users efficiently.

The Role of Attention and the Prefill Phase

At the core of LLM generation is the attention mechanism, which is the only part of the network where different tokens interact. In a standard forward pass, the model processes an input sequence (the prefill phase) to predict the next token.

This process involves projecting input tokens into query ($Q$), key ($K$), and value ($V$) states. The model then computes similarity scores via $Q K^{T}$, which has a quadratic complexity of $\mathcal{O}(n^{2} d)$ relative to the sequence length $n$. A causal attention mask is applied to ensure that each token only interacts with tokens that preceded it, preventing future tokens from influencing the past.

Optimizing Generation with KV Caching

Generating tokens one-by-one (the decoding phase) would be computationally wasteful if the model recomputed the $K$ and $V$ states for every previous token in the sequence for every new token generated.

KV caching solves this by storing the key and value states created during the prefill and previous decoding steps. This reduces the compute cost of generating token $n + 1$ from $\mathcal{O}(n^{2})$ to $\mathcal{O}(n)$, trading computation for memory. For example, in Llama-2-7B, storing one token requires approximately 16 KB of memory in float16 precision across 32 layers and 32 heads.

Handling Large Prompts via Chunked Prefill

When initial prompts are exceptionally long, the memory required for activations can exceed available GPU memory, making it impossible to perform prefill in a single forward pass.

Chunked prefill addresses this by splitting the initial prompt into smaller, manageable chunks. By utilizing the KV cache, the model stores states from the first chunk and prepends them to the states of the subsequent chunk, allowing the prompt to be processed incrementally without losing information.

From Batched Generation to Continuous Batching

To increase throughput (tokens generated per second), models process multiple prompts in parallel. However, traditional methods introduce significant inefficiencies:

  • Batched Generation: Requires all prompts to be the same length, necessitating padding tokens (<pad>). This is wasteful when prompt lengths vary.
  • Dynamic Scheduling: Allows replacing a finished prompt with a new one, but still requires heavy padding because a new prompt in the prefill phase must be batched with others in the decoding phase.

Ragged Batching

To eliminate padding waste, ragged batching removes the batch axis entirely and instead concatenates all prompts into a single sequence. Token interaction is controlled strictly via the attention mask, ensuring that tokens from one prompt do not interact with tokens from another.

The Continuous Batching Algorithm

Continuous batching combines ragged batching with dynamic scheduling to keep the GPU fully utilized. The process follows these logic steps:

  1. Maximize Memory Budget: The system attempts to fill the GPU memory budget of $m$ tokens per batch.
  2. Prioritize Decoding: All prompts currently in the decoding phase are added to the batch first (each occupying one token).
  3. Fill with Prefill: The remaining space is filled with prompts in the prefill phase, using chunked prefill to split inputs as necessary.
  4. Dynamic Replacement: Finished prompts (those that generate an <eos> token) are removed immediately and replaced with new incoming requests.

Summary of Key Techniques

Continuous batching achieves its efficiency through the integration of three primary technical components:

Technique Primary Benefit
KV Caching Avoids recomputing past token representations during decoding.
Chunked Prefill Enables processing of prompts that exceed GPU memory limits.
Ragged Batching Eliminates padding waste by concatenating sequences and using masks.
Dynamic Scheduling Maintains high throughput by swapping requests in real-time.

Sources