Queueing, saturation, and Little’s law
Connect concurrency, throughput, and latency
Before you begin
Follow a linked prerequisite when you cannot explain it from memory. Background skills without links are stated as abilities rather than hidden terminology.
- Units, work, and rates
- Average rate and time
At 10:00 a load generator begins sending 700 inference requests each second to a language-model server. The server log records the timestamp when its gateway accepts each request, the timestamp when the GPU scheduler admits the request, and the timestamp when the final token leaves the server. A monitoring plot shows 70 admitted requests waiting at 10:01, 180 at 10:02, and 310 at 10:03 even though individual GPU kernels remain fast.
Each accepted request occupies a concrete place while it is incomplete. A request can wait in the gateway's in-memory list, wait in the GPU scheduler for a compatible batch, execute model operations on the GPU, or wait for output processing. Engineers call an ordered waiting collection a queue. The growing count means that requests enter the measured server faster than the server completes them; an efficient kernel does not prevent the wider service from running above sustainable capacity.
Little's law relates three averages for a stable interval: the number of requests inside a declared entry-and-exit boundary, the rate at which requests cross the exit as completed work, and the time each completed request spent inside. The law can reveal that a GPU dashboard omits requests waiting at the gateway. The law cannot predict the 99th-percentile latency because requests with different prompt lengths and arrival bursts can produce the same three averages.
Define the queueing boundary
Choose where an item enters and leaves the measured system. A request can enter when the load balancer accepts it and leave when the final response reaches the client. A narrower GPU-scheduler boundary can begin after preprocessing and end when device work completes. Both are valid, but their populations and time measurements are different.
Use the same boundary for all three terms in Little's law. L is the average number of items inside. Lambda is the average completion or effective arrival rate through that boundary during stable operation. W is the average time that those items spend inside. Mixing gateway latency with GPU-only concurrency produces an invalid comparison.
Understand why L equals lambda times W
Suppose a stable service completes 500 requests each second and each request remains inside for an average of 0.4 seconds. During the time one request is present, approximately 500 requests/s × 0.4 s = 200 requests' worth of occupancy accumulates on average. Little's law formalizes this conservation relationship: L = lambda W.
The result is general because Little's law does not require exponential arrivals or a particular service-time distribution. The calculation does require consistent long-run averages and a stable population. If the queue grows throughout the measurement, there is no finite steady operating point to summarize with the reported averages.
Separate service time from waiting time
Response time contains waiting time and service time. Service time is the interval during which resources actively process the item under the chosen model. Waiting time accumulates when the item is ready but a dependency or capacity limit prevents progress. Reducing kernel service time can reduce both terms because a faster server also releases capacity sooner.
Near saturation, waiting can dominate. A small service-time reduction may then produce a larger response-time benefit than its direct duration because it creates capacity headroom. The opposite also occurs: a faster kernel can leave throughput unchanged when another stage limits completions.
Saturation and stability
Below capacity, the service can complete work faster than the long-run arrival rate. Idle periods provide room to absorb bursts. As utilization approaches capacity, that room shrinks. A cluster of long requests or a brief arrival burst creates a queue that takes longer to drain.
When arrivals exceed sustainable completions, the queue grows. Throughput can remain flat at the service limit while latency and in-flight work increase without bound. A short load test can conceal this condition if it ends before memory fills or clients time out. Plot queue length and latency over time, not only their final averages.
Batching changes service cost and waiting
A scheduler can hold requests briefly to form a larger batch. The larger batch may use matrix units and weight reuse more efficiently, reducing average device time per token. The request pays the batch-formation delay before it receives that benefit.
Variable prompt and output lengths complicate the tradeoff. A long sequence can delay shorter sequences in a static batch. Continuous batching admits and removes work at iteration boundaries, which reduces some head-of-line blocking but adds scheduling and cache-management decisions. Evaluate the complete throughput-latency curve instead of one maximum batch size.
Averages do not determine tail latency
Little's law relates averages. Two services can have the same L, lambda, and W while producing different p99 latency. One can serve nearly uniform requests; the other can mix many short requests with a small number of extremely long requests.
Tail behavior requires additional evidence about arrival bursts, service-time variation, scheduling order, retries, and shared-resource interference. Use Little's law as an accounting check, then inspect distributions and timelines to explain the tail.
L = λWIf monitoring disagrees, check whether population, rate, and latency use the same boundary.
Worked example: Sizing concurrency from observed service behavior
During a stable load test, a language-model endpoint completes 900 requests per second. Mean latency from gateway admission to response completion is 240 milliseconds. A GPU dashboard reports 80 requests in flight.
- Convert 240 milliseconds to 0.240 seconds. Apply Little's law at the end-to-end boundary: L = 900 requests/s × 0.240 s = 216 requests. The service should contain about 216 admitted but incomplete requests on average.
- Compare this result with the GPU dashboard's 80. The dashboard probably counts only sequences admitted to active or waiting GPU batches. Approximately 136 requests are elsewhere inside the wider boundary, such as preprocessing, scheduler admission, or an application queue.
- Instrument each boundary and verify the populations. Apply Little's law separately to the gateway-to-completion system and the GPU-scheduler subsystem. Each calculation should use the rate and residence time measured across the same entry and exit points.
- Increase offered load by 10% for a sufficiently long interval. Suppose completion rate remains near 900 requests/s while queue length and p99 latency increase continuously. The service is above sustainable capacity even though the throughput number looks stable.
- Add admission control with a bounded queue and compare goodput: requests completed within the service objective. Report rejections explicitly. Without admission control, many of those requests would have timed out after consuming queue memory and user time.
Conclusion: The calculation identifies a missing population of queued requests and distinguishes throughput at capacity from a stable operating point. Further distribution data is still required to explain p99 latency.
Common errors
- Applying steady-state averages to an interval in which the queue grows throughout the test. The reported operating point is not stable.
- Using offered arrival rate when some work is rejected before entering the measured boundary. Use the rate that crosses the same boundary as L and W.
- Interpreting Little's law as a tail-latency model. Little's law constrains means and does not determine percentiles.
- Treating unused capacity as an error without considering burst absorption and latency. Online services often require explicit headroom.
Reference summary
L = λWSuppose the gateway accepts requests into the measured service and the response writer removes them after the final token. If the stable service completes 1,000 requests each second and each completed request spends an average of 0.2 seconds between those events, the service contains about 200 admitted requests on average. A GPU dashboard that reports only 40 probably excludes requests waiting in gateway or scheduler queues. Little’s law exposes the mismatch because all three quantities must use the same entry and exit events.
- Below saturation, added concurrency can fill execution slots that would otherwise remain idle. Batching can also reduce the average service cost per request.
- Near saturation, the system has little unused capacity to absorb bursts or long requests. Waiting time becomes sensitive to variation even when the average arrival rate stays below the average service rate.
- Above sustainable capacity, arrivals accumulate faster than completions. The queue grows until admission control rejects work, clients time out, or available memory is exhausted.
- Tail latency depends on the complete service-time distribution, request ordering, batch formation, retries, and interference from other work.
Knowledge check
After maximum batch size increases, GPU activity rises, completed requests per second remains flat, and p99 request latency doubles. Describe the expected scheduler-queue plot and explain why more device activity did not produce more completed work.
Show the answer guide
- Below the larger batch limit, the scheduler-queue plot can remain short while batching fills unused device capacity. At the flat completion rate, the service has reached a limiting resource and additional admitted work begins to accumulate in the queue.
- After saturation, the queue-depth curve should trend upward or remain at a higher level instead of returning to zero between bursts. The corresponding queue-time and p99 request-latency curves rise, consistent with the reported doubling.
- Larger batches can raise GPU activity by running longer or denser iterations, but the flat completed-request rate shows that the extra activity did not increase service completions at the offered workload.
- Each active request receives progress less often when batch iterations take longer or when the scheduler waits to assemble them. The added waiting, rather than lack of GPU work, explains the latency increase.
- Offered, admitted, completed, and rejected rates plus batch size, iteration duration, and queue age are needed to distinguish useful batching from overload.
Reproduce queue growth in a discrete event table
Model a service for 60 seconds with exactly 20 arrivals per second and capacity for 18 completions per second. Update queue depth once per second, then repeat with capacity 22 per second. Assume no initial queue and state how completions are limited when the queue is empty.
Evidence to keep: Keep both per-second event tables, the predicted 2-request-per-second growth calculation, queue-depth plots, final queue sizes, and a written explanation of the stable and unstable cases using arrival and completion rates.
Queueing models explain competition among requests. The roofline model next examines one CUDA kernel by comparing its floating-point-operation count with bytes transferred between HBM and the on-chip cache hierarchy.
Sources and further reading
The lesson explanations synthesize primary papers and official references. Follow the originals for proofs, exact APIs, architecture details, and version-sensitive behavior.
- Amdahl, Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities↗
- Little, A Proof for the Queuing Formula: L = λW↗
- Roofline: An Insightful Visual Performance Model↗
- NVIDIA Nsight Systems User Guide↗
Official reference for capturing and reading CPU, CUDA API, GPU workload, and communication timelines.
- Nsight Compute Profiling Guide↗
- MLPerf Training Benchmark↗