Batching and scheduling chains: concurrency, goodput, queues and budgets

A scheduling round tests whether you can turn arrival rates and step times into concurrency, memory and tail latency. Most of these chains use Llama 3.1 8B on one H100 SXM, so the numbers can be compared across cards.

Little's law for an LLM server

inputs   10 requests/s, 0.5 s TTFT, 300 output tokens at 25 ms each
W        TTFT + (output - 1) x TPOT = 0.5 + 299 x 0.025 = 7.975 s
L        lambda x W = 10 x 7.975 = 79.75 requests in the system
decoding 10 x 299 x 0.025 = 74.75 sequences decoding at any moment
sanity   74.75 / 0.025 s = 2,990 tokens/s = 10 requests/s x 299 tokens

The law holds for any stable system, so it is a cross-check on dashboards: a waiting-plus-running gauge that disagrees with rate times time is measuring something else.

Drilled in: Little's law and KV sizing

KV in flight and the naive ceiling

inputs   the 79.75 requests above on Llama 3.3 70B, 1,650 tokens each on average
         320 KiB of KV per token; TP=4 pool of 159.8 GB = 487,600 tokens
in flight  79.75 x 1,650 x 327,680 B = 43.1 GB
ceiling    159.8 GB / (1,650 x 327,680 B x 7.975 s) = 37 requests/s
sanity   the ceiling assumes W stays at 7.975 s, and it does not: more
         concurrency slows every step

Treat 37 requests/s as an upper bound. As concurrency rises, TPOT rises, W grows and the pool fills well before the naive rate.

Drilled in: Little's law and KV sizing

Goodput at a TPOT target

inputs   Llama 3.1 8B BF16 on one H100 SXM, 2,048 tokens of context, 10 ms TPOT target
batch 64   (16.06 + 64 x 2,048 x 131,072 / 1e9) GB / 3.35 TB/s = 9.9 ms, 6,450 tok/s
batch 128  (16.06 + 34.4) GB / 3.35 TB/s = 15.1 ms, 8,505 tok/s
sanity   32% more tokens at batch 128, and every request misses 10 ms:
         goodput goes from all of them to none

Throughput keeps rising past the SLO; goodput falls off a cliff at it. Size the batch from the target, then read the throughput off the curve.

Drilled in: Goodput versus throughput

Swap or recompute a preempted request

inputs   Llama 3.1 8B BF16 on H100 SXM; 128 KiB of KV per token; 4K context
swap     out and back: 2 x 131,072 B / 50 GB/s = 5.2 us per token
recompute 2 x 8.03e9 FLOPs plus attention at 50% MFU = 34.7 us per token
break-even  262,144 B / 34.7 us = 7.6 GB/s of effective bandwidth
sanity   a batched swap wins; per-block copies of 32 KiB that reach
         only 3 to 4 GB/s lose to recompute

The link's rated bandwidth is not the one that matters. Small scattered copies achieve a fraction of it, which is why engines that swap must batch the copies.

Drilled in: Preemption: recompute or swap · Swap versus recompute

Head-of-line blocking under FCFS

inputs   Llama 3.1 8B on one H100 SXM at 50% MFU, token budget 8,192
         a 32,768-token prompt arrives ahead of ten 500-token prompts
steps    32,768 / 8,192 = 4 full steps before a short prompt gets budget
FCFS     short prompts' TTFT 1.80 s in a step-level simulation
by length  short prompts 0.27 s; the long prompt waits one extra step, 0.16 s
sanity   mean TTFT 1.78 s to 0.41 s, and prompt length is known on arrival,
         so this reordering needs no prediction

Shrinking the budget does not fix the order; it only makes each step shorter and less efficient. Capping one prompt's share of each step does.

Drilled in: Head-of-line blocking, FCFS and SJF

The p99 TTFT knee

inputs   M/M/1 queue, mean prefill S = 66.5 ms, p99 TTFT target 1 s
formula  p99 response = 4.6 x S / (1 - rho)
limit    4.6 x 0.0665 / (1 - rho) <= 1  ->  rho <= 0.69
slope    1 / (1 - rho)^2: 11 at 70% load, 4 at 50%
sanity   the "keep it under 70%" rule falls out of these inputs; lognormal
         prompt lengths pull the limit to about 50%

The model is a starting point. A batching engine's service time depends on its load, which bends the curve further.

Drilled in: The p99 TTFT utilization knee

A 100K-token prompt under the budget

inputs   Llama 3.1 8B, vLLM v0.32.0 defaults on H100 (budget 8,192, chunked
         prefill on), 64 decoders; 494.5 TFLOP/s achieved (50% MFU)
chunk 1  2 x 8.03e9 x 8,192 / 494.5e12 = 266 ms linear
         + 524,288 x 8,128^2 / 2 / 494.5e12 = 35 ms causal attention = 301 ms
later    each chunk adds 524,288 x 8,128^2 / 494.5e12 = 70 ms of attention
chunks   ceil(100,000 / 8,128) = 13
sanity   the 64 decoders' inter-token latency goes from 9.9 ms to 301 ms
         and climbs from there for 13 steps

Chunked prefill keeps decoders alive. It does not keep them fast, and the attention term grows with each chunk because later chunks attend to everything before them.

Drilled in: A 100K-token prompt, step by step · Chunked prefill and the token budget

Tenant cost in weighted tokens

inputs   tenant A: 200 input, 100 output tokens per request
         tenant B: 8,000 input, 1,000 output tokens per request
weights  about 1 per input token and 3 per output token, from the roofline
cost     A = 200 + 3 x 100 = 500; B = 8,000 + 3 x 1,000 = 11,000
ratio    22x per request
sanity   round-robin by request gives B 22 / 23 = 96% of the GPU

Fairness has to count what each request costs. A per-tenant counter charged as tokens are processed, with the tenant furthest behind admitted first, gives each tenant its share.

Drilled in: Tenant fairness with token quotas