Inference Foundations
Serving a model at scale is governed by the mathematics of waiting lines and the physics of the key-value cache. This appendix develops the analytical serving models that the book’s inference and operations chapters draw on, establishing how queuing dynamics and attention-cache memory arithmetic combine into a single serving constraint under strict latency service-level objectives (SLOs). In C³ terms, inference turns compute capacity, communication with memory and clients, and coordination across queues into one serving constraint.
How to Use This Appendix
This appendix is a quantitative reference for serving systems. Use the queuing model to choose a batch size or predict tail latency under a given arrival rate; use the key-value cache arithmetic to size memory or determine when the cache, rather than compute, caps throughput.
Reach for it from the inference and operations chapters: when those chapters cite a serving result, the derivation lives here. Read it linearly for the full argument, or consult the worked GPT-3 example and the batch-size decision framework for templates directly applicable to production systems.
Serving Performance Analysis
Serving performance analysis has two coupled layers. The queue determines how requests wait, batch, and shed under stochastic arrivals; the key-value cache determines how much live state the accelerator can hold while meeting the latency budget. The subsections that follow derive the queueing model first, then connect that model to memory-capacity limits in the worked serving examples.
Queuing theory for batched inference
The batching efficiency curve provides intuition about throughput-latency trade-offs, but production systems require rigorous analysis to determine optimal batch sizes under stochastic arrival patterns. Queuing theory provides the mathematical framework to derive these optimal operating points and to understand why certain batch sizes outperform others under specific conditions.
The M/G/c/K queue model for GPU serving
GPU inference systems can be modeled as M/G/c/K Queues, a standard notation from queueing theory that captures the essential characteristics of production serving systems:
- M (Markov arrivals): Requests arrive according to a Poisson process with rate \(\lambda_{\text{arr}}\). This models the memoryless property of user requests, where arrival of one request does not predict the timing of the next.
- G (General service distribution): Service times follow a general distribution, not restricted to exponential. GPU inference times depend on batch size and exhibit deterministic components (compute) mixed with stochastic variation (memory contention, kernel scheduling).
- c (Number of servers): The system has \(c\) parallel GPU workers, each capable of serving requests independently.
- K (Queue capacity): The system maintains a finite queue of capacity \(K\) requests. Requests arriving to a full queue are rejected (load shedding).
The notation comes from the same systems-performance lineage that sized telephone networks before it was applied to GPU clusters.
Systems Perspective 0.1: Queuing theory and performance
For a batched inference system with batch size \(B\), service time becomes a function of batch size. Let \(T_{\text{svc}}(B)\) denote the time to process a batch of \(B\) requests. From the physics of batching (Batching Strategies at Scale), equation 1 models this as:
\[T_{\text{svc}}(B) = T_{\text{fixed}} + t_{\text{req}} \cdot B \tag{1}\]
where \(T_{\text{fixed}}\) represents fixed service overhead (kernel launch, weight loading from high-bandwidth memory (HBM)) and \(t_{\text{req}}\) represents marginal per-request computation time. This linear model captures the first-order behavior observed in production systems, though actual service times may exhibit slight sublinearity due to memory bandwidth saturation at large batch sizes.
The Effective Service Rate for batched processing is:
\[\mu_{\text{eff}}(B) = \frac{B}{T_{\text{svc}}(B)} = \frac{B}{T_{\text{fixed}} + t_{\text{req}} \cdot B}\]
The effective rate increases with batch size, approaching the asymptotic limit \(1/t_{\text{req}}\) as \(B \to \infty\).
Response time analysis
The total response time \(T\) for a request consists of three components:
\[E[T] = E[W] + E[T_{\text{batch}}] + E[T_{\text{svc}}]\]
where:
- \(E[W]\) is the expected waiting time in queue before joining a batch
- \(E[T_{\text{batch}}]\) is the expected per-request batch-accumulation delay before dispatch
- \(E[T_{\text{svc}}]\) is the expected inference time once the batch executes
For dynamic batching with maximum wait time \(T_{\text{max}}\) and maximum batch size \(B_{\text{max}}\), the first request triggers the batching window. Let \(N \sim \operatorname{Poisson}(\lambda_{\text{arr}}T_{\text{max}})\) count subsequent arrivals during that window and let \(k=B_{\text{max}}-1\). For \(B_{\text{max}}>1\), the realized batch size is \(B=\min(B_{\text{max}},1+N)\), including the trigger request, so:
\[E[B] = \sum_{n=0}^{k-1}(n+1)\Pr(N=n) + B_{\text{max}}\Pr(N\geq k)\]
Let \(\tau_k\) be the Erlang-distributed time of the \(k\)th subsequent arrival. A full batch closes when \(\tau_k \leq T_{\text{max}}\), while a timeout batch closes at \(T_{\text{max}}\) with \(N=n<k\). The mean per-request accumulation delay within each realized batch is:
\[E[T_{\text{batch}} \mid \text{full}] = \frac{1}{2}E[\tau_k \mid \tau_k \leq T_{\text{max}}]\]
\[E[T_{\text{batch}} \mid N=n,\ \text{timeout}] = \frac{T_{\text{max}}}{2}\left(1+\frac{1}{n+1}\right), \qquad 0 \leq n < k\]
Weighting each batch outcome by its realized request count gives the mean delay of a randomly selected request:
\[E[T_{\text{batch}}] = \frac{B_{\text{max}}\Pr(N\geq k)E[\tau_k/2 \mid \tau_k\leq T_{\text{max}}] + \sum_{n=0}^{k-1}(n+1)\Pr(N=n)E[T_{\text{batch}} \mid N=n,\ \text{timeout}]}{E[B]}\]
When batches reliably fill before timeout, this expression approaches \(E[\tau_k]/2=(B_{\text{max}}-1)/(2\lambda_{\text{arr}})\). For \(B_{\text{max}}=1\), the batch contains only its trigger request and accumulation delay is zero.
Optimal batch size derivation
The optimal batch size \(B\) minimizes expected response time subject to throughput requirements:
\[B = \operatorname{arg\,min}_{B} E[T(B)] \quad \text{subject to} \quad \mu_{\text{eff}}(B) \geq \lambda_{\text{arr}}\]
The constraint ensures system stability (service rate exceeds arrival rate).
For a high-traffic regime in which batches of size \(B\) reliably fill before timeout, substituting the response time components gives:
\[E[T(B)] = E[W(B)] + \frac{B-1}{2\lambda_{\text{arr}}} + T_{\text{svc}}(B)\]
For a tractable waiting-time estimate, use an M/G/1 surrogate that treats batches as Poisson “super-requests.” If the request arrival rate is \(\lambda_{\text{arr}}\) and the average batch size is \(B\), this surrogate uses batch arrival rate \(\lambda_{\text{batch}}=\lambda_{\text{arr}}/B\). This is not the exact process produced by grouping Poisson request arrivals, because fixed-size grouping yields Erlang inter-batch times; finite \(K\) or \(c>1\) requires a bulk-service model or simulation. Within the explicit surrogate, the Pollaczek-Khinchine formula gives:
\[E[W] = \frac{\lambda_{\text{batch}} \cdot E[T_{\text{svc}}^2]}{2(1 - \rho_{\text{serv}})}\]
where \(\rho_{\text{serv}} = \lambda_{\text{batch}} \cdot E[T_{\text{svc}}] = \lambda_{\text{arr}} \cdot E[T_{\text{svc}}]/B\) is the server utilization. The second moment \(E[T_{\text{svc}}^2]\) captures service time variability.
For the linear service time model with deterministic service in this surrogate:
\[E[W(B)] = \frac{\lambda_{\text{arr}} \cdot T_{\text{svc}}(B)^2}{2B(1 - \lambda_{\text{arr}} \cdot T_{\text{svc}}(B)/B)}\]
For production sizing, teams often first enforce a utilization headroom target rather than solving the full latency minimization problem. With \(T_{\text{svc}}(B)=T_{\text{fixed}}+t_{\text{req}} B\), the constraint \(\rho_{\text{serv}}=\lambda_{\text{arr}} T_{\text{svc}}(B)/B \leq \rho_{\text{target}}\) yields the target-utilization batch bound (equation 2):
\[B_{\min}(\rho_{\text{target}}) = \frac{\lambda_{\text{arr}} T_{\text{fixed}}}{\rho_{\text{target}} - \lambda_{\text{arr}} t_{\text{req}}} \tag{2}\]
where \(\rho_{\text{target}}\) is the target utilization (typically 0.7–0.8 for production systems to maintain latency headroom) and \(\rho_{\text{target}} > \lambda_{\text{arr}} t_{\text{req}}\).
Systems Perspective 0.2: Target-utilization batch sizing
- Higher traffic \((\lambda_{\text{arr}})\): Required batch size increases.
- Higher fixed overhead \((T_{\text{fixed}})\): Required batch size increases to amortize overhead.
- Higher target utilization \((\rho_{\text{target}})\): Required batch size decreases, but with less latency headroom.
This utilization-constrained sizing explains why large language models (LLMs) (high \(T_{\text{fixed}}\) from weight loading) benefit from larger batches than vision models (low \(T_{\text{fixed}}\)), even at the same arrival rate.
Worked example: GPT-3 serving at 100 QPS
Consider serving a GPT-3 class model (175B parameters) under the following system parameters:
- Arrival rate: \(\lambda_{\text{arr}} = 100\) requests/second
- Hardware: 8\(\times\) A100 GPUs with tensor parallelism
- Weight loading overhead: \(T_{\text{fixed}} = 50\) ms (time to load attention matrices per forward pass)
- Per-token compute: \(t_{\text{req}} = 0.5\) ms per request (amortized across batch)
- Average output length: 100 tokens per request
- Target utilization: \(\rho_{\text{target}} = 0.75\)
For the prefill phase (processing input prompt), service time follows equation 1:
\[T_{\text{svc}}(B) = 50 + 0.5 \cdot B \text{ ms}\]
Applying equation 2 to compute the minimum batch size that meets the 75 percent target utilization (leaving 25 percent headroom):
\[B_{\min} \approx \frac{100 \times 0.05}{0.75 - 100 \times 0.0005} = \frac{5}{0.70} \approx 7.14\]
Rounding up gives \(B=8\) as the smallest batch size that meets the target utilization headroom. Evaluating the surrogate response-time expression under the full-batch assumption then shows how larger batches reduce utilization but add batch-accumulation delay:
Evaluating GPT-3 serving performance across batch sizes (table 1) exposes the trade-off between queuing delay and server utilization:
| Size \(B\) | \(T_{\text{svc}}(B)\) (ms) | req/s | \(\rho_{\text{serv}}\) | E[W] (ms) | \((B-1)/(2\lambda_{\text{arr}})\) (ms) | E[T] (ms) |
|---|---|---|---|---|---|---|
| 1 | 50.5 | 19.8 | 505% (unstable) | \(\infty\) | 0.0 | \(\infty\) |
| 4 | 52.0 | 76.9 | 130% (unstable) | \(\infty\) | 15.0 | \(\infty\) |
| 8 | 54.0 | 148.1 | 67.5% | 56.1 | 35.0 | 145.1 |
| 16 | 58.0 | 275.9 | 36.3% | 16.5 | 75.0 | 149.5 |
| 32 | 66.0 | 484.8 | 20.6% | 8.6 | 155.0 | 229.6 |
Four operational regimes emerge across these batch sizes:
- Unstable regime (batch sizes 1–4): Utilization exceeds 100 percent, meaning the system cannot keep up with arrivals. Queues grow unboundedly.
- Stability threshold (batch size 8): At 67.5 percent utilization, the system is stable but queuing delays contribute significantly to latency (56.1 ms), causing queuing latency to explode near saturation (figure 1).
- Latency knee (batch sizes 8–16): Batch size 8 gives the lowest mean latency in this model. Batch size 16 trades a few milliseconds of additional total latency for lower utilization and queue wait time (16.5 ms vs. 56.1 ms), while \(B=32\) leaves still more utilization headroom but pays too much batch-accumulation delay.
- Diminishing returns (batch sizes beyond 32): Further batch size increases would reduce utilization, but memory constraints prevent exploration.
Applying Little’s Law provides an internal consistency check for these results.
Napkin Math 0.1: Applying Little's Law to verify
At \(B=16\) with \(\lambda_{\text{arr}} = 100\) req/s and \(E[T] =\) 149.5 ms:
\(Q_{\text{req}} = 100 \times\) 0.1495 s = 14.95 requests in system
With batch size 16 and utilization 36.3 percent:
- Expected requests in service: 16 \(\times\) 0.363 = 5.8
- Expected requests in queue: 14.95 - 5.8 = 9.14
This matches the response-time decomposition: roughly 6 requests are in service and roughly 9 are waiting or accumulating into batches on average.
Decision framework: Batch size selection given SLA
Production systems must select batch size to meet Service Level Objectives (SLOs), typically specified as latency percentiles (for example, P99 latency < 200 ms). The following framework systematizes this decision:
Step 1: Characterize service time
Measure \(T_{\text{fixed}}\) and \(t_{\text{req}}\) empirically by profiling inference at batch sizes 1, 8, and 32. Fit the linear model \(T_{\text{svc}}(B) = T_{\text{fixed}} + t_{\text{req}} B\).
Step 2: Compute stability threshold
Find minimum batch size \(B_{\text{min}}\) such that \(\mu_{\text{eff}}(B_{\text{min}}) > \lambda_{\text{arr}}\):
\[B_{\text{min}} = \frac{T_{\text{fixed}} \lambda_{\text{arr}}}{1 - t_{\text{req}} \lambda_{\text{arr}}}\]
Any batch size below \(B_{\text{min}}\) results in an unstable system.
Step 3: Compute latency at candidate batch sizes
Under the same Poisson-super-request surrogate and full-batch assumption, for each candidate \(B \in \{B_{\text{min}}, 2B_{\text{min}}, ..., B_{\text{max}}\}\), compute:
\[E[T(B)] = \frac{\lambda_{\text{arr}} \cdot T_{\text{svc}}(B)^2}{2B(1 - \lambda_{\text{arr}} T_{\text{svc}}(B)/B)} + \frac{B-1}{2\lambda_{\text{arr}}} + T_{\text{svc}}(B)\]
Step 4: Account for tail latency
If measured response times are approximately Gaussian, their P99 can be estimated as:
\[T_{\text{P99}} \approx E[T] + 2.33 \cdot \sigma_T\]
where \(\sigma_T\) is the standard deviation of response time. This Gaussian rule is not a general heavy-traffic approximation because queueing response times are commonly skewed. For exponential response times, P99 is \(-\ln(0.01)E[T] \approx 4.6 \cdot E[T]\); use measured percentiles for production sizing.
Step 5: Select optimal batch size
Choose the largest \(B\) such that \(T_{\text{P99}}(B) \leq \text{SLO}\):
\[B = \max\{B : T_{\text{P99}}(B) \leq \text{SLO}\}\]
Operating rules for batch size selection (table 2) balance stability, latency SLOs, and cost efficiency:
| Condition | Recommended Action | Rationale |
|---|---|---|
| \(B < B_{\min}\) | Increase batch size or add replicas | System is unstable |
| \(T_{\text{P99}} > \text{SLO}\) | Reduce batch size or add replicas | Latency exceeds target |
| \(\rho_{\text{serv}} < 0.5\) | Consider reducing replicas to save cost | System is overprovisioned |
| \(\rho_{\text{serv}} > 0.85\) | Add replicas for headroom | Approaching instability |
Applying these operating rules ensures that the serving deployment remains responsive under load while maintaining cost efficiency during low-traffic windows.
Trade-off curves: Visualizing the operating region
Throughput and latency trade-off curves (figure 2) define the viable operating envelope:
The trade-off curve demonstrates several key insights:
- Pareto Frontier: An operating point is Pareto efficient when no other candidate provides at least as much throughput and no more latency, with a strict improvement in at least one objective. The frontier is the set of these nondominated points.
- Knee of the Curve: The optimal batch size often lies at the “knee” where throughput gains diminish while latency continues to increase linearly.
- SLO-Constrained Optimum: When an SLO bounds maximum latency, the optimal point is where the curve intersects the SLO boundary.
- Diminishing Returns: Beyond the knee, doubling batch size may increase throughput by only 10–20 percent while doubling latency.
The queuing-theoretic framework provides the mathematical foundation for the batching strategies introduced in Batching Strategies at Scale. Where intuition might suggest “larger batches are better for throughput,” stability constraints, latency targets, and diminishing returns create a well-defined optimal operating region that varies by model type and deployment requirements.
KV cache fundamentals
The formal definition of the KV cache appears in the main inference memory-management section (as introduced in Memory management: From preallocation to paging). This appendix expands the sizing math behind that definition: why the cache reduces per-token compute, why its memory grows with sequence length and batch size, and why unmanaged allocation can fragment HBM (Kwon et al. 2023).
Autoregressive generation without caching requires \(\mathcal{O}(t^2)\) computation per token because each transformer layer must recompute attention keys and values for all previous tokens. The KV cache stores these computed key and value vectors, reducing generation to \(\mathcal{O}(t)\) per token. For serving at scale, this compute saving creates a critical memory-management challenge since KV cache memory can exceed model weights for long contexts.
The cache size grows with context as calculated by equation 3:
\[M_{\text{KV}} = 2 \times N_L \times d \times S \times B \times s_{\text{elem}} \tag{3}\]
where \(N_L\) is the number of layers, \(d\) is the hidden dimension, \(S\) is sequence length, \(B\) is batch size, \(s_{\text{elem}}\) is storage size per element in bytes, and the factor of 2 accounts for both keys and values.
For the 175B GPT-3 model (\(N_L=96\), \(d=12288\), FP16 \(s_{\text{elem}}=2\) bytes) at sequence length \(S=2048\), each request requires:
\[ M_{\text{KV/req}} = 2 \times 96 \times 12288 \times 2048 \times 2 \text{ B} \approx 9.66 \text{ GB/request} \]
Across 8\(\times\) A100 80-GB GPUs (640 GB total HBM), storing model weights in FP16 consumes 350 GB, leaving 290 GB for activation and KV cache memory. Unmanaged contiguous allocation limits the maximum concurrent batch size to \(B_{\text{max}} \le 290/9.66 \approx\) 30 requests before running out of memory (OOM), demonstrating how KV cache capacity bounds serving throughput.
Summary
Serving production inference requires balancing queueing dynamics against hardware memory capacity. The quantitative relationships derived in this appendix govern batch size selection, latency budgets, and accelerator memory bounds across serving deployments:
Key Takeaways: Serving performance is bounded by queues and memory
- Utilization has a hard ceiling: As utilization \(\rho_{\text{serv}}\) approaches 1, queue depth and latency grow without bound. Production serving targets \(\rho_{\text{serv}} \leq 0.7\) to preserve latency headroom; the remaining 30 percent is not waste but the buffer that keeps tail latency finite.
- Batch size has an optimum, not a maximum: Larger batches raise throughput but add batch-accumulation delay, producing a latency knee rather than monotonic improvement. Beyond the knee, doubling the batch can buy only 10–20 percent more throughput at the cost of doubled latency.
- Little’s Law ties the system together: \(Q_{\text{req}} = \lambda_{\text{arr}} T_{\text{lat}}\) relates the number of in-flight requests to the arrival rate and time-in-system, giving a one-line consistency check on any serving measurement.
- The KV cache is the binding constraint: Cache memory scales linearly with sequence length and batch size and routinely exceeds the model weights, capping concurrent capacity (the autoregressive bottleneck, principle 14). Naive allocation wastes 60–80 percent to fragmentation, which is why production systems manage it with a virtual-memory scheme.