Little's Law and the Capacity of a Serving System

The one identity that holds for any queueing system whatsoever — L = λW — proved from an area argument, and the sizing rules that follow from it.

AI SystemsCore⏱ 1 hour11 min readlittle's lawconcurrencythroughputcapacity planning

2 problems →

AssumesWhat a Serving System Must Guarantee

The law

TheoremLittle's law

Consider any system into which items arrive and from which they eventually depart. Let $N(t)$ be the number present at time $t$ , let $A(T)$ be the number of arrivals in $[0,T]$ , and let $W_i$ be the time item $i$ spends in the system. Suppose the limits

\lambda = \lim_{T\to\infty} \frac{A(T)}{T}, \qquad \overline{W} = \lim_{n\to\infty} \frac 1n \sum_{i=1}^n W_i

exist and are finite. Then the time-average occupancy exists and equals their product:

\overline{L} \ =\ \lim_{T\to\infty}\frac1T\int_0^T N(t)\,dt \ =\ \lambda \overline{W} .

Assumptions

Every item that arrives eventually departs, and no item is present forever.
The two limits above exist and are finite. This is the only substantive hypothesis.
Nothing else. In particular: no assumption that arrivals are Poisson, that service times are exponential or independent, that service is first-come-first-served, that there is one server, or that the system is even work-conserving. The law is a sample-path identity, not a probabilistic one.

Key idea

Little's law relates three quantities, so it determines any one from the other two. That is how it is used in practice: measure the two you can measure, and deduce the third. The most common application is the one you cannot measure directly — average latency inside a component that does not emit per-request timings — from occupancy and arrival rate, both of which are easy counters.

Two immediate corollaries

Apply the law to a sub-system rather than the whole, and it gives something new each time. The trick is choosing the boundary.

CorollaryThe utilisation law

Draw the boundary around the servers only, excluding the queue. Items "arrive" at that sub-system when service begins and "depart" when it ends, so the arrival rate is the throughput $X$ and the time in the sub-system is the service time $S$ . Little's law gives

\overline{L}_{\text{busy}} \ =\ X\,\E[S],

where $\overline{L}_{\text{busy}}$ is the average number of busy servers. Dividing by the number of servers $c$ ,

\rho \ =\ \frac{X\,\E[S]}{c} .

CorollaryConcurrency needed for a throughput target

To sustain throughput $X$ when each request takes $W$ seconds end to end, the system must hold

L \ =\ X\,W

requests concurrently. Conversely, a system whose concurrency is capped at $L_{\max}$ — by a thread pool, a connection limit, or the KV-cache memory of a GPU — cannot exceed throughput $L_{\max}/W$ no matter how much offered load it receives.

Working the numbers

The corollary above is the sizing rule for an inference server, and it is worth doing concretely.

Suppose one replica must sustain $X = 20$ requests per second, and a request occupies the replica for $W = 4$ seconds — a 500-token generation at 8 ms per token, say, plus prefill and queueing. Then

L \ =\ 20 \times 4 \ =\ 80

requests must be resident simultaneously. Every one of them holds a KV cache. Using the KV-cache arithmetic from KV Cache, Batching and Little's Law, that resident count multiplied by the per-sequence cache size is a hard memory requirement — and if the GPU cannot hold 80 sequences' worth, the target throughput is unreachable on that replica at that latency, whatever the batching implementation does.

What this does not say

Little's law says nothing about variability. Two systems with identical $L$ , $X$ and $W$ can have completely different latency distributions — one tight around 4 seconds, the other mostly instant with a heavy tail. Since What a Serving System Must Guarantee established that the mean constrains the p99 only by a factor of $1/(1-p)$ , an identity about means is exactly as informative about the tail as that factor permits, and no more.

References

PaperJ. D. C. Little (1961). A Proof for the Queuing Formula L = λWThe original proof; the argument given here is the standard area/sample-path version.
PaperJ. D. C. Little (2011). Little's Law as Viewed on Its 50th AnniversaryLittle's own account of exactly how few assumptions the law requires.

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

TheoremLittle's lawproof includedIn any stable system, the long-run average number in the system equals the long-run arrival rate times the long-run average time in the system.
CorollaryThe utilisation lawproof includedApplying Little's law to the servers alone shows that utilisation equals throughput times mean service time, per server.
CorollaryConcurrency needed for a throughput targetproof includedTo sustain throughput X at latency W the system must hold XW requests concurrently, which bounds the batch size and the KV-cache memory a serving replica needs.

Problems (2)

All problems