Queueing Theory for LLM Serving

A team sizes a deployment by dividing measured throughput by expected traffic, provisions 40% headroom, and ships. At 60% of the calculated capacity, p99 latency is four times the median. Nothing is broken and no alert fires, because the GPU is busy and the mean is fine.

The queue is doing what queues do. LLM serving obeys the same arithmetic as any other queueing system, and two properties of the workload make its behaviour unusually severe: concurrency is hard-capped by memory, and service times are heavy-tailed.

Little's Law sets the ceiling

For any stable system,

where \(L\) is the average number of requests in the system, \(\lambda\) the arrival rate, and \(W\) the average time in the system. Nothing about LLMs is special here; what is special is that \(L\) has a hard upper bound.

Continuous batching runs many sequences concurrently, and the number that fit is set by KV cache capacity. For a model with \(n_{\text{layers}}\) layers, \(n_{kv}\) key-value heads of dimension \(d_h\), at 2 bytes per element, one token of cache costs

with the leading 2 counting keys and values. Multiply by average sequence length, divide the free HBM by that, and you have \(L_{\max}\), the largest batch the server can hold. Rearranged, the law gives the sustainable arrival rate:

This is a constraint, not a target. Push \(\lambda\) above it and requests wait outside the batch, so \(W\) grows, which does not increase capacity; it converts throughput pressure into queueing delay. The observable is time-to-first-token climbing while tokens per second stays flat, and that specific signature means the queue, not the GPU, is the bottleneck.

Why the latency cliff arrives early

In an M/M/1 queue, waiting time is \(W_q = \rho / (\mu - \lambda)\) and diverges as utilisation \(\rho\) approaches 1. That much is familiar. Two workload properties make the LLM version worse than the textbook curve.

Service times are heavy-tailed. In a chat workload, output lengths span from a dozen tokens to several thousand, and decode time is roughly proportional to output length. Queueing delay grows with the variance of service time, not just the mean, so a workload whose 99^th percentile response is fifty times the median produces long queues at utilisation levels that would be comfortable with uniform service times.

Service time is unknown at admission. A classical scheduler can use service time to order the queue. An LLM server cannot: output length is not known until generation ends. Every scheduling decision is made under uncertainty about how long the job will occupy its slot, which is what turns a solved problem into an active research area.

Prefill and decode compete for the same device. A long prefill occupies the GPU in a way that stalls every decode already in flight, so one arrival can degrade latency for the entire resident batch. Chunked prefill exists to bound that interference, reporting 2.6x higher serving capacity for Mistral-7B on an A100 and up to 5.6x for Falcon-180B with pipeline parallelism (Agrawal et al., 2024, Sarathi-Serve, arXiv:2403.02310).

What to measure instead of utilisation

GPU utilisation is close to useless as a saturation signal, because continuous batching keeps the device busy by design; it reads near 100% at light load and at overload alike. The quantities that move first are queue depth, KV cache occupancy as a fraction of capacity, and the ratio of waiting time to service time.

Queue-aware scheduling is where the measurable wins are. QLM, which combines a request waiting-time estimator with a global scheduler, reported 40 to 90% improvements in SLO attainment and 20 to 400% in throughput against existing systems while maintaining or improving device utilisation (Patke et al., 2024, arXiv:2407.00047). Those gains come from ordering and admission, not from faster kernels.

When it breaks

The steady-state assumption fails under bursts. Little's Law describes averages over a stable interval. Real traffic arrives in bursts, and a burst that briefly exceeds \(L_{\max}\) leaves a queue that persists long after arrivals return to normal. Sizing on mean arrival rate systematically under-provisions.

Preemption changes the model. When a server evicts a running sequence to admit another, work already done is either recomputed or swapped, and neither appears in a simple \(L = \lambda W\) accounting. Effective capacity falls below the memory-derived \(L_{\max}\) under thrash.

Multi-turn conversations correlate arrivals. Sessions are not independent Poisson arrivals; a user's next request follows their last response. This produces synchronised load and makes tail latency worse than an independence assumption predicts.