Continuous batching from first principles

Continuous batching

Large language models (LLMs) predict the next token in a sequence, processing entire prompts and generating tokens one-by-one. Continuous batching is a key optimization for serving these models efficiently, particularly with many concurrent users. Hugging Face’s research details how continuous batching achieves significant throughput gains by strategically combining multiple conversations in parallel.

Why This Matters

Current LLM inference often struggles with maximizing GPU utilization due to padding and inefficient batching. Ideal models assume uniform input lengths, but real-world prompts vary greatly, leading to significant wasted computation and increased costs – a single 8-hour App Engine outage in 2012 cost Google an estimated $860,000 in lost revenue. Continuous batching addresses this by minimizing padding and dynamically scheduling tasks, improving resource utilization and reducing latency.

Key Insights

• KV-cache, 2018: Stores key and value states to avoid redundant computations during decoding.
• Chunked Prefill: Splits long prompts into manageable chunks to overcome memory limitations during the initial processing phase.
• Ragged Batching: Combines prompts of varying lengths into a single batch without padding, utilizing attention masks to maintain context separation, used in production by many LLM providers.

Working Example

# This is a conceptual example, actual implementation is complex
# and relies on deep learning frameworks like PyTorch or TensorFlow.

import torch

def apply_attention_mask(query, key, value, mask):
    """Applies an attention mask to the attention scores."""
    attention_scores = torch.matmul(query, key.transpose(-2, -1))
    masked_attention_scores = attention_scores.masked_fill(mask == 0, float('-inf'))
    attention_weights = torch.softmax(masked_attention_scores, dim=-1)
    output = torch.matmul(attention_weights, value)
    return output

# Example mask (True where attention is allowed, False otherwise)
mask = torch.tensor([
    [1, 1, 1, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 1, 1, 1]
], dtype=torch.bool)

# Dummy query, key, value tensors
query = torch.randn(3, 5, 64)
key = torch.randn(3, 5, 64)
value = torch.randn(3, 5, 64)

output = apply_attention_mask(query, key, value, mask)
print(output.shape) # Expected output: torch.Size([3, 5, 64])

Practical Applications

• Hugging Face Inference Endpoints: Leverages continuous batching to serve large language models with high throughput and low latency.
• Pitfall: Incorrectly implemented attention masks can lead to context leakage between different prompts in a batch, resulting in inaccurate or nonsensical outputs.

References:

• https://huggingface.co/blog/continuous_batching