LLM & VLM courseBlog
84Track 5: LLM inference and serving · session 7 of 65

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.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: BeginnerBefore this: Sessions 78 and 80 (prefill and decode, the KV cache); session 18 (padding masks) helps

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:

\[ t(B) \;=\; \max\!\left( \frac{B\, F_{\text{tok}}}{\pi},\; \frac{b N + B\, T\, s_{\text{kv}}}{\beta} \right), \qquad F_{\text{tok}} = 2N + 4\, L\, d_{\text{attn}}\, T \tag{84.1} \]
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:

\[ \text{TPOT}(B) = t(B), \qquad X(B) = \frac{B}{t(B)} \;\text{tokens/s in total}, \qquad \frac{1}{t(B)} \;\text{tokens/s per user} \tag{84.2} \]

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\).

One user at a time: 4 steps, weights read 4 times user 14.83 ms user 24.83 ms user 34.83 ms user 44.83 ms 19.3 ms64.8 GB Batch of 4: 1 step, weights read once user 1 user 2 user 3 user 4 4.95 ms, 16.6 GB read 16.06 GB weights + 4 × 0.13 GB KV cache 3.9 times less time for the same 4 tokens
Figure 1. Four decode tokens of Llama 3 8B (BF16) on one H100 SXM, each user with 1,024 tokens in the cache. Served one after another, the 16.06 GB of weights are read four times. Served as one batch, they are read once, and only the four small KV caches are extra. Times are roofline lower bounds from formula (84.1).
Worked example: what a batch of 32 buys

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:

\[ t(B) = t_w \left( 1 + \frac{B}{B_{1/2}} \right), \qquad t_w = \frac{bN}{\beta}, \qquad B_{1/2} = \frac{bN}{T\, s_{\text{kv}}} \tag{84.3} \]
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\):

\[ X(B) = X_\infty \,\frac{B}{B + B_{1/2}}, \qquad X_\infty = \frac{\beta}{T\, s_{\text{kv}}} \tag{84.4} \]

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

\[ B^{*} = \frac{t_w}{F_{\text{tok}}/\pi \;-\; T\, s_{\text{kv}}/\beta} \qquad \text{(only if the denominator is positive)} \tag{84.5} \]

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.

Worked example: where Llama 3 8B bends on an H100

\(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.

total tokens/sTPOT (ms)TPOT targetdoes not fit in memory
Figure 2. Formula (84.1) with datasheet peaks (H100 SXM: 989 TFLOP/s, 3.35 TB/s, 80 GB; A100 80 GB: 312 TFLOP/s, 2.039 TB/s, two of them for the 70B model), BF16/FP16 weights and cache, and 90% of GPU memory usable. The x-axis is logarithmic. Dashed marks: \(B_{1/2}\) (the bend), \(B^{*}\) (compute roof, if it exists) and the memory limit. Filled dots: your batch size; green circles: the best batch for the target. These are best-case numbers; real engines are slower.
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):

\[ B_{\text{SLO}} = \left\lfloor B_{1/2} \left( \frac{\tau}{t_w} - 1 \right) \right\rfloor \qquad \text{(and also } B \le \tau \pi / F_{\text{tok}} \text{ for the compute limit)} \tag{84.6} \]

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:

\[ B_{\text{mem}} = \left\lfloor \frac{u\, M - bN - M_{\text{act}}}{T_{\text{res}}\, s_{\text{kv}}} \right\rfloor \tag{84.7} \]
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
Worked example: how many sequences fit

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:

\[ \eta = \frac{\sum_{i=1}^{B} \ell_i}{B \cdot \max_i \ell_i} \tag{84.8} \]
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

\[ \bar\eta = \frac{B \mu}{B\, \mu H_B} = \frac{1}{H_B} \approx \frac{1}{\ln B + 0.577} \tag{84.9} \]

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.

useful decode steps (one request)next request in the same rowpadding or idle
Figure 3. \(5B\) requests with exponential output lengths (mean 40 tokens, at most 200; seeded, so the same button always gives the same requests) on \(B\) rows. Each column is one decode step; prefill is not drawn. In static modes the vertical lines are batch boundaries, and every request’s result is returned when its batch ends. “Sorted by length” needs to know the answer lengths in advance, which a real server does not.
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

\[ \lambda \;\lt\; \frac{B_{\max}}{t_0 + c\, B_{\max}}, \qquad \text{and at full load the batch settles at } \; k = \frac{\lambda\, t_0}{1 - \lambda c} \tag{84.10} \]
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.

mean latency, your settingsmean latency, no batchingbatches on the GPU
Figure 4. A one-pass model with an illustrative cost \(t(B) = 10 + 0.5B\) ms, Poisson arrivals (seeded), 5,000 requests per run, the first 500 not counted. Top: the first 300 ms; ticks are arrivals, boxes are batches (height = batch size). Bottom: mean latency (waiting + compute) against the arrival rate, on a log scale, cut at 1 s. The dashed line is the capacity limit of formula (84.10).
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

\[ B \;=\; \lambda \cdot n \cdot \text{TPOT}(B) \tag{84.11} \]

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

Algorithm 1: choose the decode batch size
  1. 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\)
  2. \(t_w \leftarrow bN/\beta\); if \(\tau \lt t_w\): return “impossible: fewer bytes or more GPUs needed”
  3. \(B_{1/2} \leftarrow bN / (T s_{\text{kv}})\) // formula (84.3)
  4. \(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)
  5. \(B_{\text{mem}} \leftarrow \lfloor (uM - bN)/(T_{\text{res}} s_{\text{kv}}) \rfloor\) // formula (84.7)
  6. \(B \leftarrow \min(B_{\text{SLO}}, B_{\text{mem}})\)
  7. return \(B\), TPOT \(= t(B)\), throughput \(= B / t(B)\) // formula (84.1); a best case
Algorithm 2: a dynamic batcher (one-pass model)
  1. input: a queue of requests with arrival times, \(B_{\max}\), \(\tau\)
  2. loop:
  3.   wait until the GPU is free and the queue is not empty
  4.   \(a_0 \leftarrow\) arrival time of the oldest waiting request
  5.   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\)
  6.   batch \(\leftarrow\) the oldest \(\min(B_{\max}, |\text{queue}|)\) requests; pad them to a common shape
  7.   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

SettingKind of batchingWhat sets the batch size
Chat assistant (online LLM serving)Continuous batching, built on this session’s cost modelTPOT and TTFT targets, KV-cache memory
Offline generation: synthetic data, evaluation, RL rolloutsVery large static or continuous batchesMemory only; latency per request does not matter
Embedding models for search and RAGDynamic batching (one forward pass per request)Max queue delay and \(B_{\max}\); padding to the longest text in the batch
Rerankers, classifiers, moderation filtersDynamic batching, often with length bucketsp99 latency target
Video retrieval and fingerprinting (embed every frame or clip of a library)Large static batches of frames, offlineMemory of the encoder; frames all have the same size, so no padding
Live video: action recognition, key-moment detection on many streamsDynamic batching across streamsFrame deadline per stream (for example, 33 ms at 30 frames per second)
Video question answering and Video-RAG with a VLMContinuous batching of decode; long visual prefillsVery 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
Decode at small batch is memory-bound: each step reads all weights (16 GB for an 8B model in BF16) to do about one multiply-add per weight. With \(B\) sequences in the step, the weights are still read once, so the step time grows only by the extra KV-cache reads while \(B\) tokens are produced. For Llama 3 8B on an H100 at \(T = 1024\), \(B = 32\) gives 25 times the throughput of \(B = 1\) for 26% more time per step.
Write the step time of a batched decode step and explain each term.core
\(t(B) = \max(B F_{\text{tok}}/\pi,\ (bN + B T s_{\text{kv}})/\beta)\). The first term is compute: each token needs about \(2N\) FLOPs plus attention over \(T\) cached positions. The second is memory: the weights \(bN\) are read once and shared, and each of the \(B\) caches \(T s_{\text{kv}}\) is read separately. TPOT is \(t(B)\) and throughput is \(B/t(B)\).
Where does the throughput curve bend, and why?core
In the memory-bound part, \(X(B) = X_\infty B/(B + B_{1/2})\) with \(B_{1/2} = bN/(T s_{\text{kv}})\) and \(X_\infty = \beta/(T s_{\text{kv}})\). The bend is at \(B_{1/2}\), where the batch’s caches are as big as the weights: throughput is half of its ceiling and TPOT is twice the weight-read time. If computing a token takes longer than reading its cache (short contexts), the curve can instead flatten at the compute roof \(B^{*} = t_w / (F_{\text{tok}}/\pi - T s_{\text{kv}}/\beta)\), about 424 for Llama 3 8B on an H100 at \(T = 128\).
Does decode become compute-bound at a large enough batch?advanced
Only if the time to compute one token, \(F_{\text{tok}}/\pi\), is larger than the time to read one sequence’s cache, \(T s_{\text{kv}}/\beta\). For Llama 3 8B on an H100 this holds at \(T = 128\) (16.3 µs vs 5.0 µs) but not at \(T = 1024\) (16.8 µs vs 40 µs). With longer contexts, decode stays memory-bound at every batch size, and the ceiling \(\beta/(T s_{\text{kv}})\) is set by the cache size. That is why GQA, MLA and KV quantization raise throughput directly.
How do you choose a batch size for a TPOT target of 20 ms?core
Check \(\tau \ge t_w = bN/\beta\); otherwise no batch works. Then \(B_{\text{SLO}} = \lfloor B_{1/2}(\tau/t_w - 1) \rfloor\), also capped by the compute limit \(\tau\pi/F_{\text{tok}}\) and by memory \(B_{\text{mem}}\). For Llama 3 8B on an H100 at \(T = 1024\): \(t_w = 4.79\) ms, \(B_{1/2} = 120\), so \(B_{\text{SLO}} = 379\), memory allows 416, and throughput is about 19,000 tokens/s (a best case). For Llama 2 70B on two A100s, \(t_w = 33.8\) ms, so 20 ms is impossible.
What limits the batch size in LLM serving?basic
Three things. Memory: every sequence keeps a KV cache of \(T s_{\text{kv}}\) bytes, and all caches plus the weights must fit (formula 84.7). Latency: a larger batch raises TPOT, so the SLO caps \(B\). Traffic: by Little’s law, the batch cannot be larger than \(\lambda \cdot n \cdot \text{TPOT}\); at low traffic there are simply not enough requests. For large models on few GPUs, memory usually binds first.
What is wrong with static batching for LLM generation?core
Requests end at different times, but the batch runs until the longest one ends. Finished rows produce padding, new requests wait for the whole batch, and short requests get the latency of the longest. The useful share is \(\sum \ell_i / (B \max \ell_i)\); for exponential lengths it averages \(1/H_B\): 36.8% at \(B = 8\) and 24.6% at \(B = 32\), so the waste grows with the batch size. Prompts must also be padded to the longest prompt in prefill.
Why left padding for decoder-only generation?basic
With left padding, the last real token of every row is in the last column, so the next-token logits are read from the same column for all rows, and each new token is appended at the same column. With right padding, rows would have their last real token at different columns, and appending after the pads would make the model condition on pad positions. Positions must still be counted from the first real token, and the attention mask must hide the pads.
Explain dynamic batching and its two knobs. Can batching reduce latency?core
A dynamic batcher (Clipper, Triton) collects arriving requests and launches a batch when it has \(B_{\max}\) requests or the oldest has waited \(\tau\). At low load, \(\tau\) only adds latency. At high load, batching raises the capacity from \(1/(t_0 + c)\) to \(B_{\max}/(t_0 + cB_{\max})\); without it the queue grows without end. So above the single-request capacity, batching lowers latency dramatically. At full load the batch size settles at \(k = \lambda t_0/(1 - \lambda c)\) by itself.
Why are long contexts expensive to serve, even when the model is small?advanced
The ceiling of decode throughput is \(X_\infty = \beta/(T s_{\text{kv}})\), independent of the model size, and the bend \(B_{1/2} = bN/(T s_{\text{kv}})\) moves to smaller batches as \(T\) grows. The memory limit \(B_{\text{mem}}\) also falls as \(1/T\). For Llama 3 8B on an H100, the ceiling falls from about 25,000 tokens/s at \(T = 1024\) to about 6,200 at \(T = 4096\). Long video or RAG prompts therefore cost much more per output token, not only in prefill.
Why does batching help prefill much less than decode?core
A prefill of \(P\) tokens already shares each weight read across \(P\) tokens, so with \(P\) in the hundreds or thousands it is compute-bound. Putting more prompts in the batch adds compute time in proportion, so throughput per GPU hardly changes; and padding prompts to the longest adds waste (40% useful for prompts of 120, 300, 800 and 2,000 tokens). Batching small prefills, or mixing prefill chunks with decode steps (Sarathi), still helps, because it fills the idle compute of decode steps.

Exercises

  1. For Llama 3 8B on an H100 at \(T = 2048\), compute \(B_{1/2}\), \(X_\infty\) and the TPOT at \(B = 64\).
  2. Same model and GPU, \(T = 4096\), TPOT target 20 ms. What is \(B_{\text{SLO}}\)? Does it fit in memory with \(u = 0.9\)?
  3. 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?
  4. Use formula (84.9) to find the useful share of static batching at \(B = 16\) for exponential lengths.
  5. 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?
  6. 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
1. One cache is \(2048 \times 131{,}072 = 268\) MB. \(B_{1/2} = 16.06 / 0.268 = 59.8\); \(X_\infty = 3.35 \times 10^{12} / 2.68 \times 10^{8} = 12{,}480\) tokens/s. \(t(64) = (16.06 + 64 \times 0.268)/3350 = 9.92\) ms (memory-bound; compute would be 1.11 ms). 2. \(B_{1/2} = 29.9\), so \(B_{\text{SLO}} = \lfloor 29.9 \times (20/4.794 - 1) \rfloor = 94\). Memory allows \(55.94 / 0.537 = 104\), so 94 fits; TPOT 19.9 ms, about 4,700 tokens/s. 3. \(62 / (4 \times 40) = 38.8\%\). Returned at the end: every request waits 40 steps, mean 40. Returned when finished: \((12 + 3 + 40 + 7)/4 = 15.5\) steps; but the rows still stay busy until step 40. 4. \(H_{16} = 3.381\), so \(1/H_{16} = 29.6\%\). 5. \(32 / (10 + 16) \text{ ms} = 1{,}231\) requests/s; without batching \(1 / 10.5 \text{ ms} = 95.2\) requests/s. At \(\lambda = 1\) per ms: \(k = 1 \times 10 / (1 - 0.5) = 20\). 6. \(t(128) = 9.92\) ms, so a request stays \(250 \times 9.92 = 2.48\) s, and Little’s law gives \(\lambda = 128 / 2.48 = 51.6\) requests/s (ignoring prefill time).

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

\[ t(B) = \max\!\left(\frac{BF_{\text{tok}}}{\pi}, \frac{bN + BTs_{\text{kv}}}{\beta}\right), \quad X(B) = X_\infty\frac{B}{B + B_{1/2}}, \quad B_{1/2} = \frac{bN}{Ts_{\text{kv}}}, \quad \bar\eta = \frac{1}{H_B} \]

References for this session

  1. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  2. Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
  3. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  4. Yu et al. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models
  5. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention
  6. Agrawal et al. (2023). SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills
  7. Agrawal, Kedia, Panwar et al. (2024). Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve
  8. Crankshaw, Wang, Zhou, Franklin, Gonzalez, Stoica (2017). Clipper: A Low-Latency Online Prediction Serving System
  9. NVIDIA (2024). Triton Inference Server user guide: Batchers (dynamic batching)
  10. Llama Team, Meta (2024). The Llama 3 Herd of Models
  11. Touvron et al. (2023). Llama 2: Open Foundation and Fine-Tuned Chat Models
  12. Williams et al. (2009). Roofline: An Insightful Visual Performance Model for Multicore Architectures