Catalog My learning Blog
LLM System Design Course: RAG, Vector Databases, Cost · Phase 4 · Lesson 17 · 8 min read

LLM Batching and Continuous Batching Explained

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: Why Head-of-Line Blocking Dominates Static Batching
  4. Real-World Examples
  5. Review Questions & Answers

Learning Objective

Explain why batching improves GPU throughput for LLM inference, describe how continuous batching removes the head-of-line blocking inherent in static batching, explain how paged KV cache management raises achievable batch size, and reason about the resulting throughput and latency tradeoff.

Concept Explanation

Batching works because of the memory-bandwidth bottleneck established in the previous lesson. Generating one token requires reading the model's weights out of high-bandwidth memory, and that read dominates the cost of the step. If you process one request at a time, you pay that read to produce a single token. If you process thirty-two requests together, you pay the same read once and produce thirty-two tokens, because the same weights multiply against thirty-two different activation vectors. Throughput therefore scales dramatically with batch size at first, up to the point where the arithmetic units rather than memory bandwidth become the constraint, or where memory runs out. This is why an unbatched inference server can leave the overwhelming majority of an expensive GPU idle.

Static batching, the naive implementation, collects requests into a fixed group, runs them together, and returns when all are done. It fails badly for generation because completion lengths vary wildly. If thirty-one requests in a batch finish in fifty tokens and one runs to two thousand, the whole batch occupies the GPU until the longest finishes, the thirty-one completed slots sit idle producing padding, and the thirty-one users wait for a response that was ready long ago. This is head-of-line blocking, and because output length is unpredictable by nature, it is not a rare edge case but the normal condition.

Continuous batching, also called iteration-level or in-flight batching and introduced in the Orca work presented at OSDI in 2022, fixes this by making the scheduling decision at each generation step rather than per batch. After every token, the scheduler evicts requests that have finished and admits waiting requests into the freed slots. A new request can join a batch already in progress rather than waiting for the current one to drain, and a finished request returns immediately rather than waiting for its neighbors. The effect on real workloads with variable output lengths is large, and it is the single most important reason a purpose-built inference server substantially outperforms a naive loop over a model.

The remaining constraint is KV cache memory. Each active request stores the key and value tensors for every token it has processed, and that cache grows as generation proceeds, so the number of concurrent requests a server can hold is bounded by cache memory rather than by compute. Early implementations pre-allocated a contiguous block per request sized to the maximum possible length, which wasted enormous amounts of memory on requests that finished early and fragmented what remained. The PagedAttention technique introduced with vLLM in 2023 applies the idea behind operating system virtual memory: the cache is split into fixed-size blocks allocated on demand, with a per-request block table mapping logical positions to physical blocks. Internal fragmentation drops to at most one partial block per request, blocks can be shared between requests with a common prefix, and the achievable batch size rises substantially, which translates directly into throughput because throughput is a function of batch size.

Two practical consequences follow for a systems designer. First, batching trades individual latency for aggregate throughput, and the right point on that curve depends on the workload: an interactive chat product should cap batch size and prioritize time to first token, while an offline enrichment job should push batch size as high as memory allows and ignore per-request latency entirely. Running both workloads against the same endpoint with the same configuration guarantees that one of them is badly served, which is a strong argument for separate serving pools. Second, if you consume a hosted API you do not control any of this directly, but you still benefit from knowing it exists: it explains why latency varies with someone else's traffic, why provisioned-throughput tiers exist, and why a self-hosted deployment whose numbers look terrible is usually misconfigured rather than fundamentally slow.

ApproachScheduling GranularityGPU UtilizationLatency BehaviorWhere It Applies
No batchingOne request at a timeVery low; memory bandwidth wasted per tokenBest single-request latency, terrible throughputA local prototype only
Static batchingPer batch, fixed membershipModerate; collapses when output lengths differEveryone waits for the longest generation in the batchUniform-length offline jobs
Continuous batchingPer generation stepHigh; freed slots refill immediatelyFinished requests return at once; new ones join in flightAny production serving stack
Continuous batching plus paged KV cachePer generation step, blocks on demandHighest; fragmentation nearly eliminatedSame, at a substantially larger batch sizeHigh-throughput self-hosted serving

Worked Example: Why Head-of-Line Blocking Dominates Static Batching

The arithmetic below uses a realistic output length distribution and shows that the loss from static batching is not a tail-case inefficiency but the ordinary operating condition.

Code
Batch of 32 requests. Output lengths are naturally variable:
  24 requests finish at ~60 tokens
   6 requests finish at ~300 tokens
   2 requests run to ~1,500 tokens

STATIC BATCHING
  The batch runs for max(lengths) = 1,500 steps.
  Useful token-slots produced:  24*60 + 6*300 + 2*1500 =  6,240
  Token-slots the GPU actually computed: 32 * 1,500     = 48,000
  -> ~87% of the compute produced padding.
  -> The 24 fast requests were READY at step 60 and returned at step 1,500.

CONTINUOUS BATCHING (schedule after every step)
  step   60: 24 slots free -> 24 queued requests admitted immediately
  step  300:  6 slots free ->  6 more admitted
  step 1500:  2 slots free
  -> The GPU stays near full occupancy throughout.
  -> Fast requests return at step 60, not step 1500.

WHY THE BATCH COULD NOT SIMPLY BE LARGER: KV CACHE MEMORY
  Pre-allocating for the worst case, as early servers did:
    32 slots x 4,096 max tokens x per-token KV bytes
    -> reserved as if every request would run to 4,096 tokens
    -> a 60-token request wastes 98.5% of its reservation
  Paged allocation (PagedAttention):
    16-token blocks handed out on demand; a 60-token request holds 4 blocks
    -> waste bounded by one partial block per request
    -> identical prompt prefixes can SHARE physical blocks
    -> the same memory holds several times more concurrent requests, and
       throughput scales with concurrent requests.
Static batching versus continuous batching over generation steps: a fixed batch held hostage by its longest generation while completed slots emit padding, against a per-step scheduler that evicts finished requests and admits queued ones immediately, with paged KV cache blocks allocated on demand underneath.
Static batching versus continuous batching over generation steps: a fixed batch held hostage by its longest generation while completed slots emit padding, against a per-step scheduler that evicts finished requests and admits queued ones immediately, with paged KV cache blocks allocated on demand underneath.

Real-World Examples

  • The vLLM project from researchers at UC Berkeley, presented at SOSP in 2023, introduced PagedAttention to manage the KV cache in fixed-size blocks in the manner of operating system paging, and reported throughput improvements of up to roughly twenty-four times over a naive HuggingFace Transformers serving loop at comparable latency, attributing the gain primarily to the larger batch sizes that reduced memory fragmentation made possible.
  • Iteration-level scheduling was introduced by the Orca system presented at OSDI in 2022, and the technique now appears under the name continuous or in-flight batching in essentially every serious inference server, including vLLM, NVIDIA TensorRT-LLM, and Hugging Face Text Generation Inference. That convergence is a strong signal that per-step scheduling is not an optimization but a baseline requirement for serving generation workloads.
Key TakeawaysBatching trades per-request latency for aggregate throughput, so a single serving configuration cannot be right for both an interactive chat path and an offline enrichment job. Run them on separate pools with different batch-size caps and scheduling priorities, or accept that one of the two is being badly served by a compromise neither workload asked for.

Review Questions & Answers

Because decoding is bound by memory bandwidth rather than by arithmetic. Producing a single token requires streaming the model's weights out of memory, and that transfer dominates the cost of the step regardless of how many requests are in flight. Running thirty-two requests together amortizes one weight read across thirty-two token computations, since the same weights multiply against thirty-two different activation vectors. Throughput therefore rises nearly in proportion to batch size until either the arithmetic units saturate or KV cache memory is exhausted, which is why an unbatched server leaves most of an expensive GPU idle.

A static batch returns only when every member has finished, so its duration is set by the longest generation in it. Requests that completed early hold their slots producing padding and their responses are withheld until the slowest finishes. It is the normal case because output length is chosen by the model during generation and varies by an order of magnitude across ordinary requests, so almost every realistic batch contains both very short and very long generations. The result is that both utilization and latency are governed by the tail of the length distribution rather than by its typical value.

Pre-allocating a contiguous per-request cache sized to the maximum possible output length reserves memory that most requests never use, and it fragments the remainder so that free memory cannot be assembled into new reservations. Paged allocation hands out small fixed-size blocks on demand, bounding waste to at most one partial block per request and eliminating external fragmentation, and it additionally allows requests sharing an identical prompt prefix to share the same physical blocks. It matters beyond memory because throughput is essentially a function of how many requests can be resident concurrently, so removing the memory ceiling directly raises the batch size and therefore the tokens per second the hardware delivers.

Because it explains the behavior you observe and the choices you are offered. Latency varying for identical requests reflects the batch you happened to land in alongside other customers' traffic. Provisioned throughput tiers exist to give you reserved capacity rather than shared scheduling. Discounted asynchronous batch tiers exist because relaxing latency lets the provider schedule for maximum batch efficiency. And if you ever evaluate self-hosting, knowing that continuous batching and paged cache management are the difference between a tenth and most of the hardware's capacity prevents the common error of benchmarking a naive serving loop and concluding the hardware is inadequate.