Batching basics and the latency–throughput trade-off
A GPU that decodes for one user is mostly waiting for memory. Batching lets many users share each read of the weights, so total tokens per second grows almost for free, until the KV cache, the compute limit or a latency target stops it. This session builds the cost model of one batched step, shows where the throughput curve bends, and explains static batching, dynamic batching, padding waste and the memory limit on the batch size.
What you will learn
- Why batching helps decode: the weights are read once per step and shared by B tokens
- The step-time model t(B), total throughput X(B) and TPOT(B), and the two places where the curve bends (KV saturation and the compute roof)
- How to pick the largest batch that meets a TPOT target, with real Llama 3 8B and Llama 2 70B numbers
- How KV-cache memory caps the batch size, and why reserving memory for the maximum length wastes it
- Static batching, left padding and padding waste; why the waste grows with B (the 1/H_B result)
- Dynamic batching with a time window and a maximum batch size, and why batching can lower latency under high load
- Why request-level batching is not enough for LLMs, as a preview of continuous batching (Orca)
Why this matters
One GPU can run Llama 3 8B for one user at about 200 tokens per second at best. The same GPU can serve 64 users, each with 1,024 tokens of context, at about 135 tokens per second each, which is almost 9,000 tokens per second in total. The hardware is the same and the model is the same. The only change is that the 64 users share each step. This is batching, and it is the single biggest lever on the cost of LLM serving.
In session 78 we saw why: a decode step must read every weight from GPU memory (HBM), and at batch size 1 it does only about one multiply-add per weight it reads. The arithmetic units wait for memory more than 99% of the time. If \(B\) sequences take their decode step together, the weights are read once and used \(B\) times. The step gets only a little slower, and the work done grows \(B\) times.
But batching is a trade-off, not a free gift. A bigger batch makes each step slower, so each user waits longer between tokens (a higher TPOT, time per output token). Every sequence in the batch needs its own KV cache, so memory caps the batch. Requests do not arrive together and do not end together, so we must either wait for more requests (adding delay) or run half-empty batches, and with the simplest scheme we pay for padding: slots that compute nothing useful. This session builds a small cost model that answers the practical questions: how much throughput does batch size \(B\) give, where does the curve bend, what is the largest batch that meets a latency target, and what does memory allow?
In session 83 we placed batching on the system-level branch: it changes the server, not the model, and it is lossless (with correct masks, every sequence gets the same tokens it would get alone). This session covers the basics: static and dynamic batching. The stronger form used by vLLM, SGLang and TensorRT-LLM, continuous batching (first in Orca), comes in session 135; here we see exactly which problem it solves.
One step, many sequences: the weights are read once
Take one decode step of a batch of \(B\) sequences. Each sequence has \(T\) tokens in its KV cache and makes one new token. Two things are read from HBM:
- The weights: \(bN\) bytes for \(N\) parameters stored with \(b\) bytes each (\(b = 2\) for BF16). They are the same for every sequence, so they are read once per step.
- The KV caches: each sequence attends to its own keys and values, \(T\, s_{\text{kv}}\) bytes, where \(s_{\text{kv}}\) is the cache size per token (formula 78.6). These are different for every sequence, so they are read \(B\) times.
The arithmetic is about \(2N\) FLOPs per token for the weights plus the attention work over the cache. A GPU can overlap arithmetic and memory reads, so the step takes at least the larger of the two times:
- Read the symbols
- \(t(B)\)
- the time of one decode step for a batch of \(B\) sequences (a lower bound from the roofline)
- \(F_{\text{tok}}\)
- FLOPs for one new token: \(2N\) for the weight matmuls, plus \(4 L d_{\text{attn}} T\) for \(QK^\top\) and the weighted sum of values over \(T\) cached positions
- \(\pi\), \(\beta\)
- peak compute (FLOP/s) and memory bandwidth (bytes/s) of the GPU, for example 989 TFLOP/s and 3.35 TB/s on an H100 SXM
- \(bN\)
- weight bytes, read once per step and shared by the batch
- \(T s_{\text{kv}}\)
- KV-cache bytes of one sequence; \(s_{\text{kv}} = 2 L n_{kv} d_h b\) is 131,072 bytes per token for Llama 3 8B and 327,680 for Llama 2 70B
This is formula (78.9) of session 78, turned into a time. From it we get the two numbers that a serving engineer watches. The step time is the time each user waits for their next token, and the batch makes \(B\) tokens per step:
The trade-off is in these two lines. When \(B\) grows, \(X\) grows (good for the owner of the GPU) and \(t\) grows too (bad for each user). Batching helps only because \(t(B)\) grows much more slowly than \(B\) at first.
Figure 1 shows the effect for four users of Llama 3 8B on one H100 at \(T = 1024\).
Llama 3 8B, one H100 SXM, \(T = 1024\). The weights are \(bN = 2 \times 8.03 \times 10^9 = 16.06\) GB, and one sequence’s cache is \(1024 \times 131{,}072 = 0.134\) GB.
\(B = 1\): bytes \(= 16.19\) GB, \(t = 16.19 / 3350 = 4.83\) ms, so 207 tokens/s. The compute time is only \(1.66 \times 10^{10} / 9.89 \times 10^{14} = 0.017\) ms: memory-bound by far.
\(B = 32\): bytes \(= 16.06 + 32 \times 0.134 = 20.36\) GB, \(t = 6.08\) ms. Total throughput \(32 / 6.08 \text{ ms} = 5{,}267\) tokens/s, which is 25.4 times more. Each user now gets 164.6 tokens/s instead of 206.9, which is 20% slower. That is the trade-off in one line: 25 times the throughput for 20% more latency per token.
The curve: tokens/s and TPOT against batch size
The memory-bound part
For most real settings, decode stays memory-bound (we check when this fails below). Then only the second term of (84.1) matters, and we can write it in a form that is easy to read:
- Read the symbols
- \(t_w\)
- the time to read the weights once; the floor of any decode step (4.79 ms for Llama 3 8B on an H100)
- \(B_{1/2}\)
- the batch size at which the KV caches of the batch are as large as the weights: \(B_{1/2}\, T\, s_{\text{kv}} = bN\)
Put this into \(X = B / t\):
This curve has a simple shape. For \(B \ll B_{1/2}\), \(X\) grows almost linearly with \(B\) and TPOT is almost flat: this is the “free” part of batching. At \(B = B_{1/2}\), the throughput is exactly half of its ceiling \(X_\infty\), and TPOT is exactly twice \(t_w\). For \(B \gg B_{1/2}\), the throughput hardly grows, but TPOT grows linearly with \(B\): every extra sequence brings its own cache to read, and nothing is shared any more. \(B_{1/2}\) is where the curve bends. The ceiling \(X_\infty\) depends only on the bandwidth and the cache per sequence, not on the model size. A large model has a high floor \(t_w\), but its ceiling is set by its cache.
The compute-bound part
The curve can also bend for a second reason: the arithmetic catches up with the memory. The compute time \(B F_{\text{tok}} / \pi\) grows linearly with \(B\) from zero; the memory time starts at \(t_w\) and grows more slowly if the cache is small. They meet at
The denominator compares, per sequence, the compute time of one token with the time to read one cache. If reading the cache takes longer than computing the token, the denominator is negative and the step never becomes compute-bound, however large \(B\) is. Beyond \(B^{*}\), extra sequences add compute time one for one, throughput is flat at \(\pi / F_{\text{tok}}\), and TPOT grows linearly.
\(t_w = 16.06 \text{ GB} / 3.35 \text{ TB/s} = 4.79\) ms.
Short context, \(T = 128\). One cache is 16.8 MB, so \(B_{1/2} = 957\). Compute per token: \(F_{\text{tok}} = 1.613 \times 10^{10}\) FLOPs, 16.3 µs at peak; reading one cache takes 5.0 µs. The denominator of (84.5) is 11.3 µs, so \(B^{*} = 4.79 \text{ ms} / 11.3\, \mu\text{s} = 424\). The compute roof comes first: above about 424 sequences, throughput stops at about 61,000 tokens/s.
Medium context, \(T = 1024\). One cache is 134 MB, so \(B_{1/2} = 120\) and \(X_\infty = 3.35 \times 10^{12} / 1.342 \times 10^{8} = 24{,}959\) tokens/s. Reading one cache takes 40 µs, longer than the 16.8 µs of compute, so there is no \(B^{*}\): the step stays memory-bound at every batch size. At \(B = 120\), TPOT is 9.59 ms (twice 4.79) and the throughput is 12,482 tokens/s (half of the ceiling), as formula (84.4) says.
Long context, \(T = 4096\). \(B_{1/2} = 30\) and \(X_\infty = 6{,}240\) tokens/s. The free part of batching ends very early.
This is why long contexts are expensive to serve, and why methods that shrink \(s_{\text{kv}}\) (grouped-query attention, MLA, KV-cache quantization) raise the throughput ceiling directly: \(X_\infty\) is proportional to \(1/s_{\text{kv}}\). Explore the curve in Figure 2.
How to read Figure 2
The orange curve (top) is total throughput; the blue curve (bottom) is TPOT. Start with the 8B model at \(T = 1024\): the orange curve rises fast up to about \(B = 120\) (the \(B_{1/2}\) mark) and then flattens, while TPOT starts to climb. Move the TPOT target: the readout gives the largest batch that meets it and still fits in memory. At 20 ms that is 379 sequences and about 19,000 tokens/s. Set \(T = 128\): the compute roof \(B^{*} \approx 424\) appears and the curve becomes flat there. Switch to Llama 2 70B: the floor is 34 ms, so any target below 34 ms is impossible, and memory allows only 18 sequences at \(T = 1024\), long before the curve bends.
Choosing the batch for a latency target
A real service has a service-level objective (SLO), for example “TPOT at most 50 ms” (20 tokens per second, faster than people read). In the memory-bound part, solve \(t(B) \le \tau\) with formula (84.3):
Two facts follow. First, if \(\tau \lt t_w\), no batch size works: the target is below the time to read the weights once. Llama 2 70B on two A100s has \(t_w = 33.8\) ms, so a 20 ms TPOT target is impossible on that hardware, whatever the server does (only fewer bytes, such as quantized weights, or more GPUs can help). Second, the answer is very sensitive to \(T\): for Llama 3 8B with \(\tau = 20\) ms, \(B_{\text{SLO}} = 379\) at \(T = 1024\) but only 94 at \(T = 4096\).
The best operating point is the largest batch that meets the latency target and fits in memory. The set of best points for all targets is the latency–throughput frontier: you can move along it by choosing \(B\), but not above it. Improvements to the system (better kernels, quantization, smaller caches) move the frontier itself. Sarathi-Serve, a later paper, frames LLM scheduling exactly as “taming the throughput–latency trade-off”.
The memory limit on the batch
Every sequence in the batch keeps its own KV cache in HBM for its whole life. The caches must fit next to the weights:
- Read the symbols
- \(M\), \(u\)
- total GPU memory and the fraction the server may use (engines keep a margin; we use \(u = 0.9\))
- \(M_{\text{act}}\)
- temporary activation memory of one step; small in decode, and we ignore it in the numbers below
- \(T_{\text{res}}\)
- the number of tokens reserved per sequence. A simple server reserves prompt length + maximum new tokens, because it does not know how long the answer will be
Llama 3 8B on one H100. \(0.9 \times 80 - 16.06 = 55.94\) GB for caches. At \(T_{\text{res}} = 1024\): \(55.94 / 0.134 = 416\) sequences. At 4,096: 104. At 8,192: 52.
Llama 2 70B on two A100s. The weights are 137.96 GB (68.98 billion parameters). \(0.9 \times 160 - 137.96 = 6.04\) GB is left, and one 1,024-token cache is 0.336 GB, so only 18 sequences fit; at 4,096 tokens only 4. Even with all 160 GB, 22 GB holds 16 sequences of 4,096 tokens. Here memory, not compute and not the bend, sets the batch size: \(B_{1/2} = 411\) and \(B^{*} = 236\) at \(T = 1024\) are far out of reach. This is a common situation for large models on few GPUs, and one reason people use more GPUs than the weights alone need.
Reserving \(T_{\text{res}}\) for the maximum length is wasteful. If the limit is 2,048 new tokens and the average answer has 300, most of each reservation is never used. The vLLM paper measured that in existing systems only 20.4% to 38.2% of the KV-cache memory held actual token states. [Certain: quoted from Kwon et al., 2023.] Less waste means more sequences in the batch, so higher throughput at the same latency. vLLM gets this by allocating cache memory in small pages on demand (PagedAttention, see session 134); the paper reports 2 to 4 times higher throughput than earlier systems. [Certain: from the vLLM abstract.]
Static batching and padding waste
So far we assumed all \(B\) sequences are busy in every step. Real requests differ in prompt length and in answer length. The simplest way to batch them is static batching: collect \(B\) requests, run them together from the first step to the last, and only then start the next batch. This is what a plain model.generate(batch) call does.
A GPU kernel wants rectangular tensors, so different lengths must be made equal by padding: filling with a dummy token that the attention mask hides (see session 18). Static batching pays for padding twice:
- In prefill, all prompts are padded to the longest prompt. For decoder-only models we pad on the left, so that every row’s last real token sits in the last column and the new tokens are appended in the same column for all rows.
- In decode, the batch runs until its longest answer ends. A sequence that finished early still occupies its row (it produces padding tokens that are thrown away), and new requests cannot use that row until the whole batch ends.
The fraction of useful work is the same simple ratio in both cases:
- Read the symbols
- \(\ell_i\)
- the length of request \(i\): its prompt length (prefill) or its number of output tokens (decode)
- \(\eta\)
- the share of computed slots that are useful; \(1 - \eta\) is padding waste
How bad is this for typical answers? Output lengths vary a lot: many answers are short, a few are very long. A simple model is an exponential distribution with mean \(\mu\). The maximum of \(B\) independent exponential lengths has mean \(\mu H_B\), where \(H_B = 1 + \tfrac12 + \dots + \tfrac1B\) is the harmonic number. So over many batches the useful share is
This gives 48% at \(B = 4\), 36.8% at \(B = 8\) and 24.6% at \(B = 32\). [Certain: exact for exponential lengths; checked by simulation in the code below.] The waste grows with the batch size, because a bigger batch is more likely to contain one very long answer. Static batching fights against itself: the batching that should raise throughput also raises the share of padding.
There is a latency cost too. If the server returns results when the batch ends, a request with a 5-token answer waits as long as the longest answer in its batch. And a new request that arrives just after a batch starts waits for the whole batch to finish before its prefill can even begin. Figure 3 compares static batching in arrival order, static batching with requests sorted by length, and a preview of continuous batching, where a finished row is refilled at once.
How to read Figure 3
With the first set of requests and \(B = 8\), static batching in arrival order needs 683 steps and only 30.1% of the slots do useful work; the mean latency is 420 steps. Sorting by length puts similar lengths together: 317 steps, 64.9% useful, mean latency 107 steps. Refilling rows as soon as they are free reaches 339 steps and 60.7% without knowing any lengths; its remaining waste is the tail at the end, when the queue is empty and rows go idle. Increase \(B\) to 16 in arrival order: the share of useful slots drops to 27.9%, as formula (84.9) predicts.
The worked example in numbers. Four prompts of 120, 300, 800 and 2,000 tokens, padded to 2,000: \(\eta = 3{,}220 / 8{,}000 = 40.25\%\). Almost 60% of the prefill compute is spent on pad tokens. Two common fixes for prefill are bucketing (group requests of similar length into the same batch) and packing (concatenate prompts into one long row and use a variable-length attention kernel that keeps them separate, as in FlashAttention’s varlen mode), which removes prefill padding fully. For decode, the real fix is to stop batching whole requests and batch steps instead, which is continuous batching.
Dynamic batching: waiting for a batch to form
Static batching assumes that \(B\) requests are already waiting. On a live server they arrive one by one at random times. Dynamic batching forms batches on the fly with two settings: a maximum batch size \(B_{\max}\) and a maximum queue delay \(\tau\). When the GPU is free, the server takes the waiting requests. If fewer than \(B_{\max}\) are waiting, it may wait until the oldest one has waited \(\tau\), hoping more arrive. This is the classic scheme of serving systems such as Clipper and the NVIDIA Triton Inference Server, whose dynamic batcher exposes these knobs as max_batch_size and max_queue_delay_microseconds. [Certain: Triton documentation.]
Dynamic batching was built for models that answer in one forward pass: classifiers, embedding models, rerankers, image and video-frame encoders. For them a request is one step, and the cost of a batch is roughly a fixed part plus a part that grows with \(B\): \(t(B) \approx t_0 + cB\) (the fixed part \(t_0\) is again mostly reading the weights). A server that runs one batch after another can serve at most
- Read the symbols
- \(\lambda\)
- the arrival rate of requests (requests per second)
- \(t_0\), \(c\)
- the fixed and the per-item cost of one batch
- \(k\)
- the batch size when the GPU never rests: \(k\) requests arrive during one batch of time \(t_0 + ck\), so \(k = \lambda (t_0 + ck)\)
The first inequality is a stability condition. If requests arrive faster than the server can finish them, the queue grows without end and so does the latency. Without batching (\(B_{\max} = 1\)) the limit is \(1/(t_0 + c)\). With batching it can be many times higher. This gives a result that surprises many people: under high load, batching lowers latency. Without it, the queue explodes; with it, the GPU does more work per second, the queue stays short, and requests wait less. The second formula shows that batching adapts by itself: when the load rises, more requests pile up during each batch, so the next batch is larger and more efficient.
At low load, the picture is different. The GPU is often idle, few requests are waiting, and the delay \(\tau\) only adds latency. Waiting helps the owner (fewer, fuller batches use less GPU time) but rarely the user. Figure 4 is a small event simulation of this trade-off.
How to read Figure 4
The default is 200 requests/s, \(\tau = 5\) ms, \(B_{\max} = 32\): batches of about 2 to 3 requests, mean latency about 17 ms. The blue curve (no batching) goes off the chart above about 95 requests/s, because one request at a time cannot keep up. Raise \(\lambda\) to 1,000/s: the batches grow to about 21 by themselves and the latency stays near 32 ms, as formula (84.10) predicts (\(k = 20\)). Now set \(\lambda\) to 50/s and compare \(\tau = 0\) with \(\tau = 20\) ms: the latency doubles from about 13 to 26 ms, for slightly fuller batches (1.1 to 2.0 requests). Set \(B_{\max} = 1\) to see the unstable queue at high load.
Why request-level batching is not enough for LLMs
Dynamic batching fixes the arrival problem: it collects requests over time. But if each batch is then run as a static batch from prefill to the last token, all the padding and latency problems of the last section remain, because LLM requests end at different times. The survey states the problem directly: the request lengths in a batch can be different, which leads to low utilization when short requests finish and long ones are still running. [Certain: survey, Section 6.2.2.] Orca’s answer is iteration-level scheduling: the scheduler decides the batch again at every decode step, so finished sequences leave and new ones join at once. Orca reported a 36.9 times throughput improvement over NVIDIA FasterTransformer on GPT-3 175B at the same latency. [Certain: Orca abstract, OSDI 2022.] The “refill” mode of Figure 3 is a simplified view of this idea; session 135 covers it, together with chunked prefill and split-fuse.
Little’s law: from batch size to requests per second
One more relation links the batch to the traffic a server can take. In steady state, the number of requests inside a system equals their arrival rate times the time each one stays (Little’s law, a general result from queueing theory). For decode, a request stays about \(n \cdot \text{TPOT}\) for \(n\) output tokens, so the batch that a given traffic creates is
For Llama 3 8B on an H100 at \(T = 1024\), a batch of 64 has TPOT 7.36 ms. With answers of \(n = 500\) tokens, each request stays 3.68 s, so this batch serves \(\lambda = 64 / 3.68 = 17.4\) requests per second. If the traffic is higher, the batch grows, TPOT grows, and each request stays longer: the server finds its own operating point on the curve of Figure 2, until it hits the SLO or the memory limit. Capacity planning (session 141) starts from exactly this calculation.
The algorithms and the code
- input: model (\(N\), \(b\), \(L\), \(d_{\text{attn}}\), \(s_{\text{kv}}\)), GPU (\(\pi\), \(\beta\), \(M\), \(u\)), context \(T\), reserved length \(T_{\text{res}}\), TPOT target \(\tau\)
- \(t_w \leftarrow bN/\beta\); if \(\tau \lt t_w\): return “impossible: fewer bytes or more GPUs needed”
- \(B_{1/2} \leftarrow bN / (T s_{\text{kv}})\) // formula (84.3)
- \(B_{\text{SLO}} \leftarrow \min\big(\lfloor B_{1/2}(\tau/t_w - 1)\rfloor,\ \lfloor \tau\pi / F_{\text{tok}} \rfloor\big)\) // memory part and compute part of (84.6)
- \(B_{\text{mem}} \leftarrow \lfloor (uM - bN)/(T_{\text{res}} s_{\text{kv}}) \rfloor\) // formula (84.7)
- \(B \leftarrow \min(B_{\text{SLO}}, B_{\text{mem}})\)
- return \(B\), TPOT \(= t(B)\), throughput \(= B / t(B)\) // formula (84.1); a best case
- input: a queue of requests with arrival times, \(B_{\max}\), \(\tau\)
- loop:
- wait until the GPU is free and the queue is not empty
- \(a_0 \leftarrow\) arrival time of the oldest waiting request
- wait until \(\text{now} \ge a_0 + \tau\) or the queue holds \(B_{\max}\) requests // no wait at all if the GPU was busy for longer than \(\tau\)
- batch \(\leftarrow\) the oldest \(\min(B_{\max}, |\text{queue}|)\) requests; pad them to a common shape
- run the model on the batch; return each result to its caller
The PyTorch code below runs static batching with left padding on a tiny decoder with a KV cache. It checks that the batched greedy outputs are exactly the outputs of running each prompt alone, shows that forgetting the padding mask breaks this, and counts the padding waste. It runs on a CPU in about a second.
import torch, torch.nn.functional as F torch.manual_seed(0) V, d, H, L, PAD = 50, 32, 4, 2, 0 # vocab, width, heads, layers, pad id dh = d // H class Block(torch.nn.Module): def __init__(s): super().__init__() s.n1, s.n2 = torch.nn.LayerNorm(d), torch.nn.LayerNorm(d) s.qkv, s.o = torch.nn.Linear(d, 3 * d), torch.nn.Linear(d, d) s.ff = torch.nn.Sequential(torch.nn.Linear(d, 4 * d), torch.nn.GELU(), torch.nn.Linear(4 * d, d)) def forward(s, x, cache, mask): # mask: (B, 1, T_new, T_all), True = may attend B, T, _ = x.shape q, k, v = s.qkv(s.n1(x)).split(d, dim=-1) q, k, v = [t.view(B, T, H, dh).transpose(1, 2) for t in (q, k, v)] if "k" in cache: k = torch.cat([cache["k"], k], 2); v = torch.cat([cache["v"], v], 2) cache["k"], cache["v"] = k, v a = F.scaled_dot_product_attention(q, k, v, attn_mask=mask) x = x + s.o(a.transpose(1, 2).reshape(B, T, d)) return x + s.ff(s.n2(x)) class TinyLM(torch.nn.Module): def __init__(s): super().__init__() s.emb, s.pos = torch.nn.Embedding(V, d), torch.nn.Embedding(64, d) s.blocks = torch.nn.ModuleList([Block() for _ in range(L)]) s.head = torch.nn.Linear(d, V) def forward(s, ids, pos, caches, mask): x = s.emb(ids) + s.pos(pos) for blk, c in zip(s.blocks, caches): x = blk(x, c, mask) return s.head(x[:, -1]) model = TinyLM().eval() @torch.no_grad() def generate(prompts, n_new, mask_pads=True): """Static batch: left-pad prompts, prefill once, decode n_new steps for every row.""" B, P = len(prompts), max(len(p) for p in prompts) ids = torch.full((B, P), PAD); keep = torch.zeros(B, P, dtype=torch.bool) for i, p in enumerate(prompts): # LEFT padding: real tokens end at column P-1 ids[i, P - len(p):] = torch.tensor(p); keep[i, P - len(p):] = True if not mask_pads: # the bug: pads are treated as real tokens keep[:] = True pos = (keep.cumsum(1) - 1).clamp(min=0) # real tokens get positions 0, 1, 2, ... causal = torch.tril(torch.ones(P, P, dtype=torch.bool)) mask = (causal[None] & keep[:, None, :])[:, None] # (B, 1, P, P) mask = mask | torch.eye(P, dtype=torch.bool)[None, None] # pad rows see themselves (avoids NaN) caches = [dict() for _ in range(L)] logits = model(ids, pos, caches, mask) # PREFILL for the whole batch out, nxt_pos = [], pos[:, -1:] + 1 for _ in range(n_new): nxt = logits.argmax(-1, keepdim=True); out.append(nxt) keep = torch.cat([keep, torch.ones(B, 1, dtype=torch.bool)], 1) logits = model(nxt, nxt_pos, caches, keep[:, None, None, :]) # DECODE: 1 token per row nxt_pos = nxt_pos + 1 return torch.cat(out, 1), keep prompts = [[3, 14, 15], [9, 26, 5, 35, 8, 9, 7], [2, 7], [18, 28, 18, 28, 4]] batched, keep = generate(prompts, 6) alone = torch.cat([generate([p], 6)[0] for p in prompts]) print(batched.tolist()) print("batched == one at a time:", torch.equal(batched, alone)) P = max(map(len, prompts)) bad = generate(prompts, 6, mask_pads=False)[0] print("without the padding mask:", torch.equal(bad, alone)) print(f"prefill slots used: {sum(map(len, prompts))} of {len(prompts) * P}") # padding waste when outputs have different lengths (static batch runs until the longest ends) n_out = torch.tensor([12, 3, 40, 7]) print(f"decode slots used: {n_out.sum().item()} of {len(n_out) * n_out.max().item()}" f" = {n_out.sum().item() / (len(n_out) * n_out.max().item()):.1%}")
With PyTorch 2.8 on a CPU this prints the four token lists [[2, 12, 14, 29, 6, 47], [6, 47, 23, 6, 47, 9], [21, 33, 22, 29, 6, 15], [48, 18, 23, 47, 23, 6]], then batched == one at a time: True, without the padding mask: False, prefill slots used: 17 of 28 and decode slots used: 62 of 160 = 38.8%. Three details matter. The pads are on the left, so the next token of every row is predicted from the last column. Positions are counted only over real tokens, so a left-padded prompt gets the same positions as when it runs alone. And a pad row that may attend to nothing would give NaN in the softmax, so it is allowed to see itself (its output is never used). The exact token IDs can change with the PyTorch version; the two equality checks do not.
The second program, in plain Python, checks formula (84.9) by simulation and runs the dynamic batcher of Algorithm 2:
import random rng = random.Random(0) # 1) Static batching: share of useful decode slots when output lengths are exponential def static_util(B, batches=20000, mean=40): used = slots = 0 for _ in range(batches): n = [rng.expovariate(1 / mean) for _ in range(B)] used += sum(n); slots += B * max(n) # every row runs until the longest one ends return used / slots for B in (1, 4, 8, 32): H = sum(1 / k for k in range(1, B + 1)) print(f"B={B:2d} simulated {static_util(B):.3f} formula 1/H_B {1 / H:.3f}") # 2) Dynamic batching: wait at most tau ms or until B_max requests are queued def dynamic(lam, tau, B_max, N=20000, t0=10.0, c=0.5): # service time t0 + c*B ms (illustrative) t, arr = 0.0, [] for _ in range(N): t += rng.expovariate(lam) * 1000; arr.append(t) # Poisson arrivals, in ms i, free, lat, sizes = 0, 0.0, [], [] while i < N: full = arr[i + B_max - 1] if i + B_max - 1 < N else float("inf") launch = max(free, min(arr[i] + tau, full)) # GPU free AND (window over OR batch full) k = 0 while i + k < N and k < B_max and arr[i + k] <= launch: k += 1 free = launch + t0 + c * k lat += [free - a for a in arr[i:i + k]]; sizes.append(k); i += k lat = sorted(lat[1000:]) return sum(lat) / len(lat), lat[int(0.99 * len(lat))], sum(sizes) / len(sizes) for lam, tau, B_max in [(50, 0, 32), (50, 20, 32), (200, 5, 32), (800, 5, 32), (90, 0, 1)]: m, p99, b = dynamic(lam, tau, B_max) print(f"rate {lam:3d}/s tau {tau:2d} ms B_max {B_max:2d}: mean {m:6.1f} ms p99 {p99:6.1f} ms mean batch {b:5.2f}")
It prints useful shares of 1.000, 0.479, 0.368 and 0.247 against the formula values 1.000, 0.480, 0.368 and 0.246. For the batcher it prints mean latencies of about 13.1 ms (\(\lambda = 50\), \(\tau = 0\)), 26.2 ms (\(\tau = 20\)), 17.2 ms (\(\lambda = 200\)), 25.8 ms with a mean batch of 13.4 (\(\lambda = 800\), where formula (84.10) gives \(k = 13.3\)), and 112 ms without batching at 90 requests/s, just below that setting’s capacity of 95 requests/s. The numbers come from Python 3.9’s random module; another Python version may print slightly different values.
Where this is used
| Setting | Kind of batching | What sets the batch size |
|---|---|---|
| Chat assistant (online LLM serving) | Continuous batching, built on this session’s cost model | TPOT and TTFT targets, KV-cache memory |
| Offline generation: synthetic data, evaluation, RL rollouts | Very large static or continuous batches | Memory only; latency per request does not matter |
| Embedding models for search and RAG | Dynamic batching (one forward pass per request) | Max queue delay and \(B_{\max}\); padding to the longest text in the batch |
| Rerankers, classifiers, moderation filters | Dynamic batching, often with length buckets | p99 latency target |
| Video retrieval and fingerprinting (embed every frame or clip of a library) | Large static batches of frames, offline | Memory of the encoder; frames all have the same size, so no padding |
| Live video: action recognition, key-moment detection on many streams | Dynamic batching across streams | Frame deadline per stream (for example, 33 ms at 30 frames per second) |
| Video question answering and Video-RAG with a VLM | Continuous batching of decode; long visual prefills | Very large KV caches per request push \(B_{1/2}\) and \(B_{\text{mem}}\) down |
Common mistakes
- Thinking batching makes each user faster. It raises total tokens per second; each user’s TPOT always gets worse, slowly at first and linearly after the bend.
- Right padding in batched generation with a decoder-only model. The new token would be appended after the pads, and the model would predict from a pad position. Use left padding (or a ragged batch) and correct position IDs.
- Forgetting the padding mask or the position offset. The outputs change silently. Always test that a batched run gives the same tokens as single runs, as in the code above.
- Measuring throughput at one batch size and calling it “the” throughput. Throughput is a curve \(X(B)\); report it with the TPOT (or SLO) at which it was measured.
- Ignoring the KV cache in the batch limit. The weights may fit easily while the caches allow only a handful of sequences (4 sequences of 4,096 tokens for Llama 2 70B on two A100s with a 10% margin).
- Planning with short benchmark prompts. \(B_{1/2}\) and \(X_\infty\) fall as \(1/T\); a server tuned at \(T = 128\) collapses on real RAG or video prompts.
- Setting a long max queue delay “for efficiency”. At low load it adds its full value to latency and buys little; at high load the queue forms batches by itself.
Interview questions
Why does batching increase decode throughput so much?basic
Write the step time of a batched decode step and explain each term.core
Where does the throughput curve bend, and why?core
Does decode become compute-bound at a large enough batch?advanced
How do you choose a batch size for a TPOT target of 20 ms?core
What limits the batch size in LLM serving?basic
What is wrong with static batching for LLM generation?core
Why left padding for decoder-only generation?basic
Explain dynamic batching and its two knobs. Can batching reduce latency?core
Why are long contexts expensive to serve, even when the model is small?advanced
Why does batching help prefill much less than decode?core
Exercises
- For Llama 3 8B on an H100 at \(T = 2048\), compute \(B_{1/2}\), \(X_\infty\) and the TPOT at \(B = 64\).
- Same model and GPU, \(T = 4096\), TPOT target 20 ms. What is \(B_{\text{SLO}}\)? Does it fit in memory with \(u = 0.9\)?
- A static batch has output lengths 12, 3, 40 and 7. What share of decode slots is useful? What is the mean latency in steps if results are returned at the end of the batch, and if each result is returned when it finishes?
- Use formula (84.9) to find the useful share of static batching at \(B = 16\) for exponential lengths.
- A one-pass model has \(t(B) = 10 + 0.5B\) ms and \(B_{\max} = 32\). What is the maximum stable arrival rate? Without batching? What batch size does a load of 1,000 requests/s produce?
- A server runs Llama 3 8B at \(B = 128\) and \(T = 1024\). Answers have 250 tokens on average. How many requests per second can it serve (best case)?
Answerscheck
Key takeaways
- A decode step reads the weights once for the whole batch, so \(t(B) = \max(BF_{\text{tok}}/\pi,\ (bN + BTs_{\text{kv}})/\beta)\) (84.1) grows slowly at first, and throughput \(B/t(B)\) grows almost linearly (84.2).
- In the memory-bound part, \(X(B) = X_\infty B/(B + B_{1/2})\) with \(B_{1/2} = bN/(Ts_{\text{kv}})\) and \(X_\infty = \beta/(Ts_{\text{kv}})\) (84.3, 84.4). The curve bends at \(B_{1/2}\); at short context it can hit the compute roof \(B^{*}\) first (84.5).
- The best batch is the largest one that meets the TPOT target (84.6) and fits in memory (84.7). A target below \(t_w = bN/\beta\) is impossible.
- Static batching wastes slots on padding: \(\eta = \sum\ell_i/(B\max\ell_i)\) (84.8), about \(1/H_B\) for exponential lengths (84.9), and it gets worse as \(B\) grows.
- Dynamic batching collects requests with \(B_{\max}\) and \(\tau\); it raises capacity and lowers latency under load (84.10). For LLMs it must be combined with step-level scheduling: continuous batching. Little’s law links batch, traffic and TPOT (84.11).
Key formulas
References for this session
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
- Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
- Agrawal et al. (2023). SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
- Agrawal, Kedia, Panwar et al. (2024). Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
- Crankshaw, Wang, Zhou, Franklin, Gonzalez, Stoica (2017). Clipper: A Low-Latency Online Prediction Serving System
- NVIDIA (2024). Triton Inference Server user guide: Batchers (dynamic batching)
- Llama Team, Meta (2024). The Llama 3 Herd of Models
- Touvron et al. (2023). Llama 2: Open Foundation and Fine-Tuned Chat Models
- Williams et al. (2009). Roofline: An Insightful Visual Performance Model for Multicore Architectures