Project 07 — Dynamic Batching

Group requests that arrive close together, and map the throughput/latency trade you just bought.

1. What you build#

A batcher in front of your Project 06 engine with two knobs — max_batch_size and max_wait_ms — that forms a batch, pads it, runs it to completion, and returns results to each caller. Plus a sweep that draws the latency-vs-throughput curve for every setting.

This is static batching formed dynamically: the classic Triton/TF-Serving design. Its weaknesses for LLMs are what you are here to measure, because they motivate Project 08.

Diagram — The batcher#

flowchart LR
  R["Requests"] --> Q["Queue"]
  Q --> B{"Batch full, OR oldest<br/>waited max_wait_ms?"}
  B -->|"no"| Q
  B -->|"yes"| PD["Left-pad + attention mask"]
  PD --> G["Generate to completion<br/>finished rows keep their slot"]
  G --> O["Return all results"]

  class Q,B queue
  class PD,G compute
  class R,O neutral

2. Why it matters#

Batching is how you raise arithmetic intensity: one read of the weights serves many sequences. But run-to-completion batching wastes most of its slots on generative workloads. Seeing that waste in your own numbers is what makes continuous batching feel inevitable instead of clever.

3. Read first#

• I.06 — Batching basics
• V.08 — Static and dynamic batching
• VIII.04 — Batching in servers

4. Spec#

Batcher(max_batch_size, max_wait_ms)
  - dispatch when batch is full OR oldest request has waited max_wait_ms
  - pad prompts to the longest in the batch; LEFT-pad for decoder-only models
  - attention mask so padding is never attended to
  - per-sequence EOS tracking; batch ends when ALL sequences are done
  - finished sequences keep occupying their slot (that is the flaw)

Workload for all measurements: Poisson arrivals; prompt length lognormal (median ~200 tokens); output length lognormal (median ~100, heavy tail to 1000).

5. Milestones#

1. Batched generation, offline. Take 8 prompts of different lengths; generate as a batch; outputs must equal generating each alone (greedy).
2. The batcher. A loop that collects from the queue under the two knobs.
3. Wire it in. Replace Project 06’s one-at-a-time engine loop. Streaming still works per request.
4. Sweep. max_batch_size ∈ {1,2,4,8,16,32} × max_wait_ms ∈ {0,5,20,50} × three arrival rates. Record throughput, TTFT p50/p95, E2E p50/p95.
5. Waste accounting. For every decode step log active / batch_size. Report the average — this is your slot utilization.

6. Starter skeleton#

// collectBatch blocks for the first job, then gathers more until the batch is
// full or maxWait has passed since the first one arrived.
func collectBatch(q <-chan *Job, maxBatch int, maxWait time.Duration) []*Job {
	batch := []*Job{<-q} // block for the first
	deadline := time.NewTimer(maxWait)
	defer deadline.Stop()
	for len(batch) < maxBatch {
		select {
		case job := <-q:
			batch = append(batch, job)
		case <-deadline.C:
			return batch
		}
	}
	return batch
}

// generateBatch runs the whole batch TO COMPLETION: everyone waits for the slowest.
func generateBatch(m BatchModel, jobs []*Job) {
	ids, mask := leftPad(jobs) // decoder-only models: pad on the LEFT, mask the padding
	state := m.Prefill(ids, mask)
	done := make([]bool, len(jobs))
	maxTokens := 0
	for _, j := range jobs {
		maxTokens = max(maxTokens, j.MaxTokens)
	}
	for step := 0; step < maxTokens; step++ {
		next := state.ArgmaxLast() // one token per row
		allDone := true
		for i, j := range jobs {
			if !done[i] {
				j.Emit(next[i])
				done[i] = next[i] == m.EOS() || j.HitLimit()
			}
			allDone = allDone && done[i]
		}
		if allDone {
			break
		}
		state = m.Decode(state, next) // finished rows still occupy their slot: that is the flaw
	}
}

7. What to measure#

Produce one chart: throughput on x, p95 E2E latency on y, one point per configuration. That Pareto frontier is the deliverable.

8. Done when#

• Batched outputs equal unbatched outputs under greedy decoding.
• You have the Pareto chart and can pick a configuration for a stated SLO.
• You have a measured slot-utilization number and can explain why it is low.
• You can say exactly when max_wait_ms > 0 helps and when it only adds latency.

9. Common pitfalls#

Right-padding a decoder-only model. The next-token logit is read from a pad position. Outputs silently degrade.

No attention mask, or a mask not extended each step.

Position IDs with left padding. Some models need explicit position_ids; verify equivalence against single-request output, not by eyeballing text.

Waiting when the server is idle. max_wait_ms only pays off if another request is likely to arrive inside the window.

Measuring with uniform output lengths. It hides the whole problem.

10. Stretch goals#

• Length bucketing: separate queues per prompt-length range to cut padding waste.
• Adaptive wait: set max_wait_ms from the observed arrival rate.
• Early compaction: when half the batch is done, drop finished rows from the tensors and the KV cache. You are now halfway to Project 08.
• Run the same sweep on a GPU and find the batch size where decode stops being memory-bound.

11. Interview questions this project answers#

1. What do max_batch_size and max_wait_ms each trade?
2. Why does batching raise throughput almost for free at small batch sizes in decode?
3. Why pad on the left for decoder-only models?
4. Why is run-to-completion batching a poor fit for generative workloads? Quantify it.

12. Next#

Project 08 — Continuous batching