14.1 LLM Inference Service: Prefill, Decode, KV Cache, and Capacity

A server can finish a single short request quickly and still develop a long queue under mixed load. Long prompts consume prefill capacity while long answers retain KV blocks. A useful capacity test must exercise both, along with cancellation and bursts.

Autoregressive LLM inference services involve both compute-intensive prefill phases and token-by-token decode steps. Capacity planning must account for queues, GPU memory, input/output lengths, and latency targets, rather than the number of tokens generated per second alone.

Learning Objectives

• Distinguish computation and latency metrics between prefill and decode phases;
• Explain how batching, KV cache, and memory fragmentation affect concurrency;
• Compare replication, tensor/pipeline parallelism, and prefill-decode separation;
• Design admission control, backpressure, cancellation, and degradation strategies;
• Measure goodput and per-success-task cost using representative workloads.

1. First, Define the Request Contract

An inference request is not just a prompt:

model revision + tokenizer/chat template
input tokens / multimodal assets
max output tokens + stop conditions
sampling / structured-output constraints
priority / tenant / deadline
streaming / cancellation
adapter / tool schema / safety policy versions

If the server silently replaces the model, template, or generation parameters without notification, the same API body could produce different semantics. Both requests and traces must be linked to the resolved versions.

2. Prefill and Decode Are Two Types of Workloads

Prefill

The service processes all input tokens, computes hidden states across each layer, and builds a key/value cache for attention. Long prompts increase prefill computation and GPU memory usage. The time users perceive as Time to First Token (TTFT) includes queuing, preprocessing, prefill processing, and the generation of the first output token.

Decode

In subsequent rounds, one or a few additional tokens are appended, reusing the historical key/value cache. However, decoding still proceeds sequentially. The Time Per Output Token (TPOT) or Inter-Token Latency (ITL) determines whether the streaming output feels smooth.

End-to-end latency is approximately given by:

$$T_{e2e}=TTFT+\sum _{t=2}^{N_{out}}IT{L}_t+T_{tail}.$$

A single "P95 latency" metric often conflates long outputs with queuing delays. It's essential to report at least separately: TTFT, TPOT/ITL, E2E latency, queue time, and output length.

Here TTFT ends when the first output token is observed; the usual prefill pass already computes the logits used to select that token. ITL measures gaps between later tokens, and $T_{tail}$ covers work after the last observed token. For more than one output token, average TPOT is $(T_{last}-T_{first})/(N_{out}-1)$; a one-token response has no such interval. TTFT=0.8 s and ten later gaps of 0.02 s put the last token at 1.0 s. Define token timing separately from network chunks, which may contain several tokens.

3. Why Static Batch Is Not Suitable for All Generation Requests

Static batching waits for a group of requests to arrive before processing them together; short requests can be held up by long ones, and new requests must wait until the current batch is complete. Iteration-level or continuous batching introduces new requests at decode iteration boundaries and removes completed ones, improving device utilization.

Larger batches don't necessarily reduce latency, they may increase throughput but also lead to longer queue times, per-step latency, and tail latency. The scheduler must balance trade-offs among throughput, time-to-first-token (TTFT), time per output token (TPOT), request priority, and fairness, while preventing long prompts or long outputs from monopolizing slots for extended periods.

Test mixed workloads (such as short Q&A, long context, long generation, multi-tenant priority, and burst requests) rather than relying solely on fixed-length synthetic prompts.

4. KV Cache Is Often a Concurrency Bottleneck

Each active sequence stores K and V tensors across layers, and the total memory footprint grows with the number of layers, KV heads, head dimension, context length, data type, and batch or concurrency size. Having enough memory to hold the model weights does not guarantee the system can support the desired level of concurrency.

For ordinary full-attention K/V storage, bytes per sequence are approximately $2L{H}_{KV}{d}_{head}Tb$. With 32 layers, 8 KV heads, head dimension 128, 8192 cached positions, and 2 bytes per element, that is 1 GiB. Twenty such unshared sequences need 20 GiB for KV alone. This excludes weights, workspaces, page rounding, and extra generated tokens; sliding-window or compressed latent caches require a different calculation.

Requests of varying lengths cause cache allocation and fragmentation. Designs like PagedAttention divide the KV cache into paginated blocks, reducing the need for large contiguous memory reservations and minimizing fragmentation. This improves memory utilization, though it does not eliminate the fact that KV memory still grows with token count.

Monitoring should include:

• Weight memory versus KV and activation/workspace memory usage;
• Cache block utilization, eviction rates, and allocation failures;
• Active and queued sequence counts and their length distributions;
• Prefix-cache hit rates and the actual reduction in prefill tokens;
• Out-of-memory errors, preemption events, and recomputation occurrences.

5. Prefix Cache: Reusing Computation, Not Answers

When multiple requests share identical system prompts, few-shot examples, or document prefixes, they can share corresponding KV blocks. A cache hit requires both token IDs and associated model state to be compatible; if the text appears identical but the tokenizer, template, adapter, or model revision differs, the cache cannot be shared.

Prefix/KV cache reduces prefill cost, but still performs independent decoding for each request. It is not long-term memory, nor is it a response cache. Cached content may contain tenant-specific data and must be isolated, bounded in lifetime, and invalidated upon version changes.

6. Parallelism and Replication to Address Different Bottlenecks

• Replica / data parallel serving: Each replica holds the full model, enabling horizontal scaling of requests; requires sufficient memory per machine or node.
• Tensor parallelism: Splits a matrix layer across multiple devices; reduces weight memory footprint on a single device, but introduces communication overhead per layer.
• Pipeline parallelism: Distributes different layers across distinct pipeline stages; requires handling pipeline bubbles and microbatch scheduling.
• Expert parallelism: Distributes MoE experts across devices; routing imbalance and all-to-all communication become critical concerns.
• Prefill–decode disaggregation: Separates prefill and decode phases into distinct resource allocations with KV transfer; enables independent optimization of TTFT and TPOT, but introduces KV transfer, routing, and capacity coupling.

The optimal topology depends on model architecture, hardware interconnectivity, input/output sequence lengths, and service level objectives (SLOs). You cannot directly apply a multiplier from a paper or a specific GPU configuration to your own capacity planning.

7. The Benefits of Quantization Must Be End-to-End Validated

Low-bit weight quantization can reduce memory footprint and bandwidth usage, and in some cases improve throughput; however, performance outcomes are influenced by several factors including quality degradation, kernel support, scale/zero-point overhead, KV cache data type, and dequantization costs.

The term "4-bit model" typically refers only to a subset of weight representations and does not imply that activations, KV cache, or all computations are performed in 4-bit precision. Validation must include:

• Latency and throughput under target hardware and specific batch/sequence length conditions;
• Performance on key tasks, languages, long-context scenarios, and safety regression tests;
• Structured output, log probability, and sampling behavior;
• Exact configuration of the quantized artifact and alignment with serving kernels;
• Impact on capacity when falling back to the non-quantized version.

8. Speculative Decoding Is Not Free Parallelism

Speculative decoding enables a smaller draft model to generate multiple tokens in advance, which are then concurrently validated by the target model. When algorithmic conditions are met, the target model's distribution is preserved, while the number of sequential target steps is reduced.

The benefits depend on the acceptance rate, draft model cost, batch size, sequence length, and hardware capabilities. When the draft and target models are misaligned, additional computation can negate any performance gains. Reports should include metrics such as accepted tokens per step, draft overhead, TTFT/TPOT, and quality or distribution validation, rather than peak acceleration alone.

Exact speculative sampling needs an acceptance and correction rule. For target probability $p$ and draft probability $q$, a draft token is accepted with probability $min(1,p/q)$; on rejection the residual distribution is proportional to $max(0,p-q)$. Thus a token with $p=0.1,q=0.2$ is accepted half the time. Simply accepting anything that looks plausible does not preserve the target distribution. See the original algorithm.

9. Admission Control and Backpressure

An unbounded queue turns overload into a storm of timeouts. The entry point evaluates incoming requests based on estimated input/output tokens, deadlines, priority, tenant quotas, and the current KV and compute capacity to decide whether to accept, queue, downgrade, or reject the request.

Essential mechanisms include:

• Request size and maximum output limits;
• Per-tenant concurrency and token budgets;
• Bounded queues with queue timeouts;
• Priority-based anti-starvation;
• Immediate release of decode and KV resources upon client disconnect or cancel;
• Load shedding with Retry-After headers;
• Circuit breakers to prevent upstream retry amplification;
• Streaming backpressure to avoid slow clients from monopolizing resources.

The estimate max_tokens cannot be equated with actual output, but it must be accounted for in the worst-case budget.

10. Capacity: Measure Goodput Alongside Throughput

Throughput measures the number of requests or tokens processed; goodput only counts requests that meet quality standards and service level objectives (SLOs). A system may appear fully loaded, yet if most requests exceed TTFT (time to first token), the throughput metric loses practical meaning for product performance.

A capacity test report should include:

• arrival pattern: steady, burst, or diurnal;
• joint distribution of input and output lengths;
• mix of models, adapters, and structured outputs;
• concurrency levels and their mix across tenants and priority classes;
• P50, P95, and P99 values for TTFT, TPOT (time per output token), and end-to-end latency;
• breakdown of request outcomes: success, cancellation, rejection, timeout, or OOM (out of memory);
• goodput, GPU utilization, and KV (key-value) memory utilization;
• energy, compute, token costs, and cost per successful task;
• warm-start vs. cold-start behavior and failure scenarios.

Synthetic loads should be calibrated using replay data or privacy-processed real-world distributions, preserving peak capacity margins and fault tolerance redundancy.

Common Misconceptions

• A model that fits in GPU memory can serve reliably: Active request KV caches may exhaust memory as concurrency or context length grows.
• Higher tokens per second (tokens/s) always leads to better user experience: TTFT, TPOT, and tail latency may actually degrade under such conditions.
• Continuous batching always improves all performance metrics: Scheduling trade-offs depend heavily on the specific workload.
• Prefix cache hits allow immediate answer return: The cache only reuses computation from prior prefix tokens, not the full response.
• Quantization only affects precision: It also alters kernel behavior, memory usage, throughput, and compatibility.

Exercise

1. Write TTFT/TPOT/E2E SLOs for short-answer and long-form response scenarios.
2. List the parameters required to estimate the memory footprint of a single KV cache.
3. Design a stress test workload that includes burst traffic, long context lengths, and cancellation.
4. Compare the bottlenecks introduced by replica scaling, tensor parallelism, and prefill-decode separation.
5. Define a goodput metric that excludes timeout and quality failure events.

Summary

The core constraints of LLM serving stem from the prefill/decode two-phase process, token-by-token dependencies, KV cache, and request queues. Techniques like batching, paginated caching, parallelism, quantization, and speculative decoding are conditional optimizations, each must be validated against real-world workloads using metrics such as TTFT, TPOT, goodput, and per-success cost.

The next lesson explores routing multiple models and providers through a single entry point, examining fallback strategies and version contracts.

References

• Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models
• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention
• Leviathan et al., Fast Inference from Transformers via Speculative Decoding
• Zhong et al., DistServe: Disaggregating Prefill and Decoding