-
Notifications
You must be signed in to change notification settings - Fork 0
Batching and Scheduling
Scheduling decides which requests run, when, and together with which others. Batching is the mechanism that makes memory-bound decode efficient: if several requests read the same weights in the same step, the cost of reading those weights is shared.
This is the layer where hardware efficiency becomes serving throughput.
- Amortize weight reads — the entire point of batching in decode
- Meet latency targets — throughput at unbounded latency is not a product
- Keep the device busy — idle hardware is wasted capacity
- Stay fair — no request should starve
- Respect memory limits — coordinate with Memory Management
flowchart LR
A[Incoming requests] --> B[Batching and Scheduling]
B <--> C[Memory Management]
B --> D[Runtime]
D --> B
style B fill:#2d6a9f,color:#fff
The loop back from the runtime is essential: scheduling in LLM serving is a per-step decision, not a per-request one.
Decode reads the full weight set to produce one token. That read costs the same whether one request or thirty-two are in flight.
| Batch size | Weight bytes read per token | Effective efficiency |
|---|---|---|
| 1 | Full model | Terrible — pure bandwidth waste |
| 8 | Full model ÷ 8 | Much better |
| 32 | Full model ÷ 32 | Approaching compute bound |
Batching converts a matrix-vector operation into a matrix-matrix one, moving decode up the roofline from bandwidth bound toward compute bound. This is the single largest throughput lever in LLM serving.
The limit is memory: every concurrent request needs its own KV cache. Maximum batch size is set by cache capacity, which is why Memory Management and scheduling are inseparable.
The two phases have opposite characteristics, and scheduling must handle both.
| Prefill | Decode | |
|---|---|---|
| Work per step | Whole prompt | One token |
| Bound by | Compute | Memory bandwidth |
| Duration | One step, potentially long | Many short steps |
| Batching benefit | Modest — already compute bound | Enormous |
The interference problem: a long prefill occupies the device for a while, and every decode request in flight stalls waiting. Users see this as a latency spike unrelated to their own request.
Responses:
| Approach | Idea | Tradeoff |
|---|---|---|
| Prefill priority | Run prefills first | Decode latency suffers |
| Decode priority | Never interrupt decode | Time-to-first-token suffers |
| Chunked prefill | Split a long prompt into pieces, interleave with decode | Slightly less efficient prefill, far smoother latency |
| Disaggregation | Separate hardware pools for each phase | Best isolation, requires cache transfer between pools |
Chunked prefill is the standard compromise: it bounds the worst-case stall a decode request can experience, at modest cost.
Static batching — collect N requests, run them to completion together — wastes enormous capacity, because requests finish at different times and finished slots sit idle until the whole batch completes.
Continuous batching re-forms the batch every decode step. Completed requests leave immediately; waiting requests join as slots free. Since each decode step is short, admission latency stays low and utilization stays high.
This is why the scheduler runs per step. The consequences are worth stating plainly:
- Batch composition changes constantly; kernels must handle variable batch size efficiently
- Requests in a batch are at different sequence positions, so attention must handle ragged lengths
- Admission and eviction decisions happen at high frequency and must be cheap
| Policy | Behavior | Good for | Weakness |
|---|---|---|---|
| FCFS | First come, first served | Fairness, simplicity | Head-of-line blocking on long requests |
| Shortest-first | Prioritize short requests | Average latency | Long requests can starve |
| Priority classes | Tiered service levels | Mixed workloads | Needs careful class definition |
| Fair queuing | Equal share per user | Multi-tenant systems | More bookkeeping |
Since output length is unknown in advance, "shortest-first" requires prediction, and mispredictions cause the starvation it was meant to avoid. Most production systems use FCFS with priority classes and explicit preemption rather than trying to predict.
Under memory pressure a running request may have to be evicted. Two options:
- Swap — move its KV cache to slower memory, restore later. Preserves work, costs bandwidth.
- Recompute — discard the cache, re-run prefill on resume. Frees memory immediately, wastes prior work.
Recomputation is often cheaper than it sounds, because prefill is compute bound and efficient, while swapping consumes the bandwidth decode desperately needs.
A small draft model proposes several tokens; the target model verifies them in a single forward pass. Accepted tokens are kept, and the first rejection resets to that point.
This works because verification of k tokens costs roughly the same as generating one — decode is bandwidth bound, so processing a few extra positions is nearly free. It converts spare compute into latency reduction.
Scheduling implications: batch size becomes variable in a new way, acceptance rate determines actual speedup, and a low acceptance rate can make things slower rather than faster.
| Metric | Definition | Why it matters |
|---|---|---|
| Throughput | Tokens generated per second, system-wide | Capacity and cost per token |
| TTFT | Time to first token | The latency users feel first |
| TPOT | Time per output token | Perceived generation speed |
| Batch occupancy | Average active slots vs. maximum | Direct efficiency measure |
| Queue wait time | Admission delay | Reveals under-provisioning |
| Preemption rate | Evictions per unit time | High values indicate thrashing |
| Goodput | Throughput meeting latency SLOs | The honest combined metric |
Throughput and latency trade off directly through batch size. Reporting either alone is misleading — goodput exists because of this.
| Problem | Root cause | Fix |
|---|---|---|
| Low utilization | Static batching leaving idle slots | Continuous batching |
| TTFT spikes | Long prefill blocking decode | Chunked prefill |
| Throughput collapses under load | Preemption thrashing | Admission control; headroom; hysteresis |
| Long requests starve | Aggressive shortest-first | FCFS with priority classes |
| Batch size limited well below compute limit | KV cache capacity | Cache quantization; paging; see Memory Management |
| Speculative decoding slower | Low acceptance rate | Better draft model, or disable it |
| Tail latency far worse than median | Unbounded queueing | Cap queue depth; shed load |
- Schedule per step, not per request. Continuous batching is the baseline, not an optimization.
- Chunk long prefills. It costs a little efficiency and prevents the worst latency behavior.
- Make admission memory-aware. Never start what you cannot finish.
- Keep headroom. A system at exactly 100% capacity has no room to absorb variance.
- Measure goodput. Optimizing throughput alone produces a system nobody wants to use.
- Watch the tail. P99 latency reveals problems that averages hide entirely.
- Prefer recompute to swap under pressure, unless measurement says otherwise.
- Shed load explicitly. Rejecting a request cleanly beats accepting it and timing out.
See also: Memory Management · Runtime · Performance Optimization · Inference Software