Batching: Static and Dynamic

1. What is it?#

Three generations of batching strategy:

NO BATCHING       one request at a time. Simple, catastrophically inefficient.
STATIC BATCHING   collect N requests, run them to completion together.
DYNAMIC BATCHING  collect requests for a short window, then run the batch.
CONTINUOUS        (file 09) — schedule at every decode step.

This file covers the first three and shows exactly why they’re insufficient for autoregressive generation, which motivates file 09.

2. Why does it exist?#

Because batching is the only way to amortize the weight read (Section I.06), and because the naive approaches to batching have specific, quantifiable failures that the modern approach fixes.

Understanding why static batching fails is more useful than knowing that continuous batching is better.

3. Simple analogy#

A ferry.

No batching: one car per crossing. Absurd.

Static batching: wait until the ferry is full, cross, unload everyone, return. Efficient per-crossing, but the first car waits for the last, and the ferry sits idle at the far shore while one truck slowly disembarks.

Dynamic batching: wait up to 5 minutes or until full, whichever comes first. Better — bounded waiting.

Continuous batching: a ferry that never stops, where cars board and disembark while it’s moving. Sounds impossible for ferries; entirely possible for GPUs, because “boarding” is just adding a row to a matrix.

4. Tiny example#

Static batching’s waste, simulated:

// batching.go — static batches vs continuous batching, on the same request lengths.
package main

import (
	"fmt"
	"math"
	"math/rand"
)

func lengths(n int) []int {
	rng := rand.New(rand.NewSource(0))
	out := make([]int, n)
	for i := range out { // log-normal: most outputs short, a few very long
		out[i] = min(max(int(math.Exp(4.5+rng.NormFloat64())), 1), 4000)
	}
	return out
}

func simulateStatic(lens []int, batchSize int) {
	var totalSlots, usefulSlots, totalSteps int
	for i := 0; i < len(lens); i += batchSize {
		batch := lens[i:min(i+batchSize, len(lens))]
		steps := 0
		for _, l := range batch {
			steps = max(steps, l) // the batch runs until the LONGEST finishes
			usefulSlots += l
		}
		totalSlots += steps * len(batch)
		totalSteps += steps
	}
	fmt.Printf("static:     utilization %.1f%%, total steps %d\n", 100*float64(usefulSlots)/float64(totalSlots), totalSteps)
}

func simulateContinuous(lens []int, batchSize int) {
	var running []int
	steps, useful, next := 0, 0, 0
	for next < len(lens) || len(running) > 0 {
		for len(running) < batchSize && next < len(lens) {
			running = append(running, lens[next]) // refill immediately
			next++
		}
		steps++
		useful += len(running)
		kept := running[:0]
		for _, r := range running {
			if r > 1 {
				kept = append(kept, r-1)
			}
		}
		running = kept
	}
	fmt.Printf("continuous: utilization %.1f%%, total steps %d\n", 100*float64(useful)/float64(steps*batchSize), steps)
}

func main() {
	lens := lengths(1000)
	simulateStatic(lens, 32)
	simulateContinuous(lens, 32)
}

Output:

static:     utilization 15.5%, total steps 30629
continuous: utilization 88.3%, total steps 5310

Static batching wastes 84% of slot-steps and takes almost 6x longer. That is not a tuning problem; it’s structural.

5. Technical explanation#

Why static batching fails for generation#

Batch of 4, generating different lengths:

step:  0    100   200   300   400
  A    ████████████████████████     400 tokens
  B    ███                          30 tokens, then IDLE for 370 steps
  C    █████                        60 tokens, then IDLE for 340 steps
  D    ██                           20 tokens, then IDLE for 380 steps
       └──── batch occupied for 400 steps ────┘

Slot-steps used:    4 × 400 = 1600
Slot-steps useful:  400+30+60+20 = 510
Utilization: 32%

Two independent problems:

1. Finished sequences hold their slot (and their KV cache) until the longest finishes.
2. New requests can’t join — they wait for the entire batch to complete.

With a realistic heavy-tailed length distribution, utilization is typically 20-40%.

Dynamic batching — and what it does and doesn’t fix#

while True:
    batch = []
    deadline = now() + max_wait
    while len(batch) < max_batch and now() < deadline:
        req = queue.get(timeout=deadline - now())
        if req: batch.append(req)
    if batch: run_to_completion(batch)

Fixes: unbounded waiting for a batch to fill (the max_wait timeout bounds TTFT).

Does not fix: the two problems above. Once the batch starts, it’s static.

Dynamic batching is the right answer for non-autoregressive models — image classifiers, embedders, rankers — where every request takes the same time. Triton Inference Server’s dynamic batcher is excellent for exactly those. For LLMs it’s insufficient.

The tuning tradeoff (for dynamic batching)#

max_wait small (5 ms):   good TTFT, small batches, poor throughput
max_wait large (100 ms): worse TTFT, full batches, good throughput

Optimal depends on arrival rate:
  high QPS → batch fills before the timeout → max_wait irrelevant
  low QPS  → timeout dominates → you're paying latency for nothing

A useful rule: set max_wait ≈ the time to fill a batch at your p50 arrival rate, capped by your TTFT budget minus prefill time.

Padding waste, on top of slot waste#

Batch of prompts: [1200, 45, 300, 2000, 80] tokens
Padded to 2000:   5 × 2000 = 10,000 token-positions processed
Actually needed:  3,625
→ 64% of prefill compute wasted

Solved by varlen kernels (Section IV.11), independent of the batching strategy.

Where each strategy is correct#

6. Under the hood#

What “adding a sequence to the batch” physically means:

Before: input tensor (8, 1, 4096) — 8 sequences, 1 token each
After:  input tensor (9, 1, 4096)

The matmuls just have one more row. The KV cache has one more sequence's blocks.
The attention kernel gets one more entry in its metadata.

That’s it. There is nothing physically preventing per-step batch changes — which is why continuous batching was possible all along and simply hadn’t been implemented until Orca (2022). The barrier was framework design (fixed-shape graphs), not hardware.

7. Performance implications#

Strategy               Throughput (relative)   p50 TTFT   Complexity
No batching            1.0x                    best       trivial
Static (size 32)       6-10x                   worst      low
Dynamic (32, 50ms)     8-14x                   moderate   low
Continuous (32)        20-30x                  good       high

Continuous batching is typically 2-4x better than static batching at the same batch size, purely from eliminating idle slots.

8. Production implications#

• Use an engine with continuous batching for any LLM. vLLM, SGLang, TGI, TensorRT-LLM (in-flight batching), all have it. This is not a place to build your own.
• Dynamic batching is still right for your embedding service. Don’t over-apply the LLM lesson.
• max_batch_size in a continuous-batching engine is a memory ceiling, not a target. The scheduler decides the actual batch per step.
• Watch the average running batch size as a health metric. If it’s 3 when memory allows 60, you have a traffic or scheduling problem, not a hardware problem.

9. Common mistakes#

Using static batching for LLMs. 60-80% waste.

Tuning max_wait without measuring arrival rate. At high QPS it does nothing; at low QPS it’s pure added latency.

Padding to max length. Compounds the waste.

Setting max_batch_size too high and running out of KV memory mid-batch, triggering preemption.

Assuming a bigger batch is always better. Above the ridge point you pay latency for diminishing throughput (Section I.06).

10. Hands-on exercise#

A. Run the simulation. Execute the code in section 4. Vary the batch size and the length distribution’s σ. How does static batching’s utilization depend on length variance? What happens as σ → 0?

B. Measure real utilization. On a static-batching setup (or simulate one by disabling continuous batching), measure actual vs theoretical throughput.

C. Dynamic batching tuning. Build a simple dynamic batcher for a non-LLM model. Sweep max_wait from 1 ms to 200 ms at three different arrival rates. Plot TTFT and throughput. Find the optimum for each rate.

D. Padding waste. With a realistic length distribution, compute the padding waste for batch sizes 8, 32, 128. Then compute it for a varlen (packed) implementation.

11. Interview questions#

1. Why does batching improve LLM throughput? Give the mechanism.
2. Why does static batching fail for autoregressive generation? Quantify the waste.
3. What does dynamic batching fix and what does it not fix?
4. For which model types is dynamic batching the correct choice?
5. How do you choose max_wait for a dynamic batcher?
6. What physically has to change to add a sequence to a running batch?
7. Your average running batch size is 4 but memory allows 64. What do you investigate?

12. Further reading#

• [ESTABLISHED] Yu et al., “Orca” (OSDI 2022) — quantifies static batching waste
• [REFERENCE] NVIDIA Triton dynamic batching documentation
• Next: 09 — Continuous batching