Queueing theory for LLM capacity

A fleet that is "70 percent utilised" can feel fast, and the same fleet at 95 percent can feel broken, even though nothing about the hardware changed. This is queueing theory, and it is the single most useful piece of mathematics for capacity planning. You do not need to derive anything: you need four ideas and a calculator.

#Idea 1: Little's law

In any stable system, the average number of items inside equals the arrival rate times the average time each spends inside:

L = λ × W

• λ: requests per second
• W: average time in the system (queue + service)
• L: average requests in flight

If 6 requests arrive per second and each spends 12 seconds in the system, there are 6 × 12 = 72 requests in flight. Your replicas must hold at least 72 concurrent generations. This holds for any arrival pattern and any service-time distribution, which is why it appears in every capacity plan (capacity planning).

The catch: W includes queueing, and queueing depends on how close to capacity you are. That is the next idea.

#Idea 2: the hockey stick

Take a single server (one slot) with random (Poisson) arrivals and random (exponential) service. If utilisation is ρ = λ × S (S is the mean service time), mean response time is:

T = S / (1 − ρ)

Latency does not rise gently: it curves upward like a hockey stick. The last 10 percent of utilisation costs more than the first 80. Two consequences:

1. Sizing to "just enough" is a trap. A fleet sized for exactly the average load is unstable as soon as demand wobbles.
2. Small changes in demand near the knee create large changes in latency. A 5 percent traffic increase at 90 percent utilisation roughly doubles waiting time (from 10× to 20× in this model).

#Idea 3: pooling (the Erlang C result)

An LLM replica is not one server: it has several slots (say 8 concurrent generations), and a fleet has many replicas. When all slots draw from a shared queue, you have an M/M/c system with c servers. The Erlang C formula gives the probability that an arriving request must wait, and the mean wait follows:

a    = λ × S                      (offered load in "servers")
ρ    = a / c
P_wait = ErlangC(c, a)
W_q  = P_wait × S / (c × (1 − ρ))        (mean queue wait)

Computed for S = 8 s:

At 80 percent utilisation, a single replica makes the average request wait 2.3 seconds; ten replicas pooled behind one queue wait about two hundredths of a second. Same utilisation, a hundred times less waiting. Pooling is the reason big fleets can run hotter than small ones, and the reason a lonely replica needs far more headroom.

What this means in practice:

• Put all replicas behind one queue or one smart router (least outstanding requests), not independent per-replica queues with round-robin (gateways).
• Prefer fewer, bigger pools over many tiny isolated ones (per-tenant dedicated replicas are expensive precisely because they lose pooling).
• Multi-model fleets lose pooling across models: keep per-model pools large enough, or share via adapters and routing.

#Finding the safe utilisation for your SLO

Suppose your SLO says "95 percent of requests wait under 2 seconds in the queue". For M/M/c the waiting-time tail is P(W_q > t) = P_wait × exp(−(c·μ − λ)·t), with μ = 1/S. Solving numerically for S = 8 s gives the maximum utilisation that still meets the SLO:

The target utilisation is not a constant: it depends on pool size and SLO. A single replica should be run at under 60 percent for this latency goal; a 20-replica pool can run at 95 percent. Rules of thumb you often see ("run at 70 percent") are averages of this table.

A tool for this: compute it yourself.

import math

def erlang_c(c, a):
    s, term = 0.0, 1.0
    for k in range(c):
        if k: term *= a / k
        s += term
    top = term * a / c * (c / (c - a))
    return top / (s + top)

def p_wait_over(c, rho, S, t):
    a = rho * c; mu = 1 / S
    return erlang_c(c, a) * math.exp(-(c * mu - a * mu) * t)

def max_utilisation(c, S, t=2.0, target=0.05):
    lo, hi = 0.01, 0.999
    for _ in range(60):
        mid = (lo + hi) / 2
        lo, hi = (mid, hi) if p_wait_over(c, mid, S, t) <= target else (lo, mid)
    return lo

print(max_utilisation(80, 8.0))    # about 0.91

(For very large c the factorial terms overflow; use a log-space implementation or a library.)

#Idea 4: variability makes queues worse

The tables above assumed exponential service times. LLM requests are more variable than that: a 50-token reply and a 2,000-token reply may differ forty-fold. Variability increases waiting. Kingman's approximation (for a single server) and its multi-server cousin (Allen-Cunneen) scale the wait by the variability of arrivals and service:

W_q(G/G/c) ≈ W_q(M/M/c) × (c_a² + c_s²) / 2

where c² is the squared coefficient of variation (variance divided by mean squared) of inter-arrival times (c_a) and service times (c_s). Poisson arrivals have c_a² = 1. Exponential service has c_s² = 1. A lognormal service-time distribution with shape 0.8 has c_s² = e^0.64 − 1 ≈ 0.9, close to exponential, so the textbook numbers hold. Heavier tails (shape 1.2 gives c_s² ≈ 3.2) roughly double the waiting.

Real traffic is often burstier than Poisson (c_a² > 1): batch jobs, retries, users sharing links, agents firing parallel calls. Add that in too.

Practical ways to reduce variability:

• Cap max_tokens and prompt length at the gateway. The long tail is mostly a few outliers.
• Separate pools for long and short requests, or priority classes, so a 3,000-token summary does not block chat (reliability patterns).
• Smooth arrivals with client-side jitter and rate limits.
• Chunked prefill so long prompts do not monopolise the engine (vLLM).

#Where the textbook model breaks for LLMs

The M/M/c model assumes each server works at a fixed speed regardless of how busy the system is. A continuous-batching engine is different:

1. Service time grows with load. As concurrent sequences rise, each decode step takes longer and per-user tokens/s falls. The "service time" is not constant.
2. Slots are not equal. Memory (KV cache) limits concurrency before compute does, and different requests use different amounts.
3. Prefill interferes with decode. A long prompt arriving can pause everyone's token stream for hundreds of milliseconds.
4. Admission control changes the picture. Real systems cap queue length and reject; waiting is bounded, not infinite.

So treat the formulas as a first-order model that explains the shape (hockey stick, pooling gains, variability costs) and gives a starting target, then measure the real knee with a load test and set your autoscaling target at 60 to 70 percent of the measured concurrency where p95 TTFT crosses your SLO (load testing, autoscaling).

#Putting numbers on a plan

Worked example. Peak traffic 10 requests per second, mean time in service 8 seconds, 8 slots per replica, SLO: 95 percent of requests wait under 2 seconds.

1. Concurrency (Little): 10 × 8 = 80 slots busy at peak on average.
2. Replicas at 100 percent: 80 / 8 = 10. This is the minimum, with zero headroom.
3. Safe utilisation for a pool of about 10 replicas: about 90 percent from the table, but our model is optimistic and traffic is bursty, so plan at 70 to 75 percent.
4. Replicas: 80 / (8 × 0.72) ≈ 14, plus one for redundancy: 15.

That is 50 percent more hardware than the naive 10. Look at what the extra buys: at 100 percent utilisation the queue grows without bound; at 90 percent a 10-replica pool waits 0.26 s on average but its tail is long and a 5 percent surge cascades; at 72 percent waits are negligible and you survive a spike and a replica failure.

#From theory to alerts and dashboards

Queueing theory suggests the right signals (metrics):

• Queue depth and queue wait are the leading indicators; latency and errors lag.
• Utilisation of slots (running / capacity) is the position on the hockey stick.
• Arrival rate and its burstiness (variance of arrivals per minute).
• Service-time distribution (p50, p95, p99 of duration): its tail drives waiting.

An alert on "slot utilisation above 85 percent for 5 minutes with queue wait rising" fires before users notice, because you are climbing the hockey stick.

#Common mistakes

1. Sizing to 100 percent of average load.
2. One global "target utilisation" ignoring pool size and SLO.
3. Per-replica queues with round-robin routing, which throws away pooling.
4. Ignoring variability: a few very long requests wreck latency for everyone.
5. Believing the formulas past the knee: measure with a load test.
6. Planning from the daily average instead of the busy hour and bursts.
7. No admission control, so an overload becomes an unbounded queue.

#Exercise

A single replica has 8 slots, mean service time 6 seconds and receives 1.0 request per second.

1. What is utilisation, and how many requests are in flight on average (Little)?
2. If traffic grows 20 percent, by how much does the M/M/1-style response multiple change?
3. You add a second replica behind the same queue and keep 1.2 requests per second. What changes qualitatively?

Answers:

1. Offered load a = 1.0 × 6 = 6 slots busy, utilisation ρ = 6/8 = 75%, and about 6 requests are in flight.
2. Growth to 1.2 req/s gives a = 7.2, ρ = 90%. In the single-server picture the multiple goes from 1/(1−0.75) = 4× to 1/(1−0.9) = 10×, 2.5 times worse for a 20 percent increase. (The multi-slot pool is milder, but the direction and steepness are the same.)
3. Utilisation falls to 7.2 / 16 = 45% and pooling over 16 slots makes waiting negligible: you have bought both capacity and a statistical gain, and you can survive losing a replica (8 slots at 90 percent would again be painful, so keep an eye on N+1).

#Going deeper

• Compute the safe utilisation for your own pool size and SLO with the snippet above.
• Simulate it: the autoscaling simulator lab shows these effects with a changing arrival rate and cold starts.
• Continue with autoscaling policies in depth.