Queueing and the Utilisation Wall

Why latency diverges like 1/(1−ρ) as a server approaches saturation, derived exactly for M/M/1 and M/G/1, and why variance costs as much as load.

AI SystemsAdvanced⏱ 3 hours13 min readqueueing theoryM/M/1Pollaczek-Khinchineutilisationvariance

3 problems →

AssumesLittle's Law and the Capacity of a Serving System · Expectation, Variance and Conditional Expectation

The simplest queue, solved exactly

DefinitionKendall notation

A queue is written $A/B/c$ : $A$ the arrival process, $B$ the service distribution, $c$ the number of servers. $M$ means memoryless — Poisson arrivals, or exponential service; $D$ means deterministic; $G$ means a general distribution. So M/M/1 is Poisson arrivals, exponential service, one server; M/G/1 relaxes the service distribution.

TheoremStationary distribution of M/M/1

Let arrivals be Poisson with rate $\lambda$ and service times be exponential with rate $\mu$ , one server, first-come-first-served, infinite buffer. Write $\rho = \lambda/\mu$ . If $\rho < 1$ the number in system $N$ has stationary distribution

\pi_n \ =\ (1-\rho)\,\rho^{\,n}, \qquad n = 0,1,2,\dots

so $N$ is geometric, and $\E[N] = \dfrac{\rho}{1-\rho}$ .

CorollaryMean latency of M/M/1

\E[W] \;=\; \frac{1}{\mu-\lambda} \;=\; \frac{\E[S]}{1-\rho}, \qquad \E[W_q] \;=\; \E[W]-\E[S] \;=\; \frac{\rho}{1-\rho}\,\E[S].

Key idea

Mean latency is the service time multiplied by $1/(1-\rho)$ . That factor is the utilisation wall:

$\rho$	0.5	0.8	0.9	0.95	0.99
$\E[W]/\E[S]$	2	5	10	20	100

The last 9% of capacity costs a factor of ten in latency. This is why serving systems are provisioned at 50–70% utilisation and why the remaining headroom is not waste — it is what the latency target is purchased with.

Variance is a second axis of load

Exponential service times are convenient, not realistic. Real inference has service times set by output length, which is far from exponential. The general answer separates load from variability.

TheoremThe Pollaczek–Khinchine mean formula

For an M/G/1 queue — Poisson arrivals at rate $\lambda$ , i.i.d. service times $S$ with finite second moment, one server, work-conserving and non-preemptive with a discipline that does not use service times — the mean waiting time in queue is

\E[W_q] \;=\; \frac{\lambda\,\E[S^2]}{2\,(1-\rho)}, \qquad \rho = \lambda\,\E[S] < 1 .

Assumptions

Arrivals are Poisson. This is what licenses the PASTA property used below; the formula genuinely fails for non-Poisson arrivals, where Kingman's approximation is the usual substitute.
$\E[S^2] < \infty$ . Service distributions with infinite second moment have infinite mean wait at every positive utilisation, which is not a pathology — it is what heavy-tailed request sizes do.
The scheduler may not look at service times. Shortest-remaining-processing-time beats this formula, at the cost discussed at the end.

Writing $\E[S^2] = \E[S]^2(1+c_s^2)$ with $c_s = \sqrt{\Var(S)}/\E[S]$ the coefficient of variation puts the formula in its most usable form:

\boxed{\ \E[W_q] \;=\; \underbrace{\frac{\rho}{1-\rho}}_{\text{load}}\ \cdot\ \underbrace{\frac{1+c_s^2}{2}}_{\text{variability}}\ \cdot\ \underbrace{\E[S]}_{\text{scale}}\ }

CorollaryHalving service variability halves the queue

Exponential service has $c_s = 1$ , so the variability factor is $1$ and $\E[W_q] = \rho\E[S]/(1-\rho)$ , recovering the M/M/1 result. Deterministic service has $c_s = 0$ , giving variability factor $1/2$ :

\E[W_q]^{\,M/D/1} \;=\; \tfrac12\,\E[W_q]^{\,M/M/1} .

Making service times perfectly predictable is worth exactly as much as halving the queueing term — at $\rho = 0.9$ , it is worth as much as dropping utilisation to $0.82$ .

Key idea

There are two ways to shorten a queue and they are interchangeable: reduce load, or reduce variability. In LLM serving the second is often the cheaper lever, because output-length variance is enormous — a mix of 20-token and 2000-token generations has a coefficient of variation well above 1. Splitting that traffic into separate pools by expected length reduces $c_s$ within each pool, and the boxed formula says the queueing term falls proportionally.

When arrivals are not Poisson

HeuristicKingman's approximation

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

For a G/G/1 queue with arrival-interval coefficient of variation $c_a$ and service coefficient of variation $c_s$ ,

\E[W_q] \;\approx\; \frac{\rho}{1-\rho}\cdot\frac{c_a^2+c_s^2}{2}\cdot\E[S] .

Assumptions

This is an approximation, not a theorem. Kingman proved it is asymptotically exact in the heavy-traffic limit $\rho \to 1$ ; at moderate utilisation it is a rule of thumb that is typically right to within tens of percent, and it can be materially wrong when either distribution is heavy-tailed. It is stated here because it is the formula practitioners actually use, and it should be labelled for what it is.

More servers beat bigger servers

PropositionPooling servers reduces delay

Compare $c$ separate M/M/1 queues each receiving $\lambda/c$ , against one M/M/c queue receiving $\lambda$ with the same total capacity. The pooled system has strictly smaller mean waiting time at every $\rho \in (0,1)$ and $c \ge 2$ .

Numerically, at $\rho = 0.8$ : one server waits $4\E[S]$ ; four pooled servers wait $0.75\E[S]$ ; sixteen pooled servers wait $0.095\E[S]$ . Same utilisation, same total capacity, a forty-fold difference in delay.

What this does not say

None of this bounds the tail. The formulas here are all statements about $\E[W_q]$ . The geometric stationary distribution of M/M/1 does give the full law in that one case — and it is exponential, so its p99 is about $4.6$ times its mean — but M/G/1 tails depend on the service distribution in ways the mean formula cannot see. Tail behaviour under fan-out is taken up in Tail Latency and Fan-Out Amplification.

References

PaperJ. F. C. Kingman (1961). The Single Server Queue in Heavy TrafficSource of the heavy-traffic approximation quoted here as a heuristic.
PaperA. K. Erlang (1917). Solution of Some Problems in the Theory of Probabilities of Significance in Automatic Telephone ExchangesThe origin of the multi-server delay formula still called Erlang C.
BookM. Harchol-Balter (2013). Performance Modeling and Design of Computer Systems: Queueing Theory in ActionStandard modern treatment; the M/G/1 derivation here follows its structure.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremStationary distribution of M/M/1proof includedWith Poisson arrivals at rate λ and exponential service at rate μ, the number in system is geometric with parameter ρ = λ/μ.
CorollaryMean latency of M/M/1proof includedMean time in system is 1/(μ−λ), so latency diverges like 1/(1−ρ) as load approaches capacity.
TheoremThe Pollaczek–Khinchine mean formulaproof includedFor Poisson arrivals and any service distribution, mean queueing delay is λE[S²]/(2(1−ρ)), so it grows linearly in the second moment of service time.
CorollaryHalving service variability halves the queueproof includedDeterministic service produces exactly half the mean queueing delay of exponential service at the same utilisation.
PropositionPooling servers reduces delayproof includedOne queue served by c servers has strictly lower mean waiting time than c separate queues of the same total capacity, and the gap widens with c.
HeuristicKingman's approximationFor a general single-server queue, mean wait is approximately the product of a utilisation factor, a variability factor and the mean service time.
DefinitionKendall notationThe A/B/c naming scheme for queues, and what M, D and G stand for.

Problems (3)

All problems