Chapter 3: Numerical Formats and Transformer Workloads

Prefill and decode workloads

Explain with shapes, timelines, and cache bytes why prompt processing and one-token generation require separate performance models

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.

Transformer workload graph
Autoregressive generation
Latency versus throughput

The recurring inference request supplies 2,048 prompt tokens to the 7-billion-parameter decoder and permits up to 256 generated tokens on one 80 GiB GPU. The serving engine first feeds all 2,048 prompt positions through the decoder layers. A GPU timeline shows relatively large matrix multiplications during this prompt-processing interval. After the first output token, each scheduler iteration advances the active request by only one new token and launches much narrower matrix operations.

Engine logs commonly label the first interval `prefill` and the repeated one-token intervals `decode`. Both phases read the same model parameters, but their tensor shapes and data reuse differ. Prefill exposes thousands of token rows to a matrix multiplication at once. One decode iteration exposes one new row per active sequence while repeatedly reading learned weights and the retained attention history.

The lesson measures the phases separately. CUDA events record uninterrupted prefill and decode iteration durations, scheduler logs record waiting between iterations, and allocator statistics record bytes used by the key-value cache. Separate evidence explains why a batching change can raise aggregate output tokens per second while also delaying the next token for a user who is already reading the response.

Prefill processes the complete prompt

For a batch of B prompts with sequence length S, prefill passes approximately B×S token activations through each projection. Flattening tokens gives an M dimension proportional to the total prompt tokens in the batch. The resulting relatively large GEMMs can provide enough work to use matrix instructions efficiently.

Attention must also relate prompt positions. In full causal self-attention, work grows approximately with the square of sequence length for each head, although an IO-aware implementation avoids storing the complete score matrix. Long prompts can therefore create long, compute-intensive prefill intervals.

Decode advances one position per active sequence

After prefill, each active sequence produces one next-token distribution per iteration. If the scheduler advances A sequences, many projection GEMMs have an effective M dimension near A rather than B×S. At low A, the matrices are narrow and can underuse the available matrix pipelines.

The model weights must still be available for every layer and every iteration. A small decode batch performs relatively little arithmetic for the weight bytes that it reads, so weight bandwidth and launch overhead can become important. Increasing active sequences reuses weights across more token calculations and improves arithmetic intensity.

The KV cache preserves attention history

For each standard attention layer and retained token, inference stores key and value vectors so later decode steps do not recompute them from the complete prefix. A basic cache-payload model is 2 × attention layers × tokens × Hkv × Dh × bytes per element for one sequence. The leading two represents K and V. Add block rounding, allocator metadata, alignment, and any unsharded or temporary copies separately.

Cache size grows linearly with retained context, active sequences, layer count, key/value heads, head dimension, and element width. Grouped-query attention reduces Hkv and therefore reduces cache capacity and traffic. Quantized cache formats can reduce bytes but add conversion and accuracy considerations.

Allocation determines how much cache capacity is usable

Sequence lengths are not known in advance and change one token at a time. Reserving one contiguous maximum-length buffer per request wastes memory when outputs end early. Requiring contiguous growth can also create external fragmentation that prevents a large allocation even when total free bytes are sufficient.

PagedAttention divides KV storage into fixed-size blocks and maps logical sequence positions to non-contiguous physical blocks. This limits unused space to the final partially filled block and allows sharing in selected decoding patterns. The indirection changes address calculation and kernel structure, so evaluate both capacity and access cost.

Batching exchanges latency for efficiency

Adding active decode sequences increases the M dimension of projection GEMMs and reuses model weights across more output tokens. Aggregate output-token throughput usually improves until another resource reaches capacity. The scheduler can also admit new prefill work to use otherwise idle capacity.

Larger batches increase the time of an iteration and can make an active request wait behind more work. They also consume more KV cache and can delay admission for new requests. Report time per output token and its tail distribution beside aggregate tokens per second.

Chunked prefill limits long uninterrupted intervals

A single long prompt can occupy the device for a substantial prefill interval. Existing decode requests then wait, increasing their time per output token. Chunked prefill divides the prompt into smaller token ranges and schedules decode work between them.

Chunking adds scheduler decisions and can repeat or reduce some efficiencies depending on the implementation. Chunking can increase the long request's own time to first token while improving decode latency for other users. Select chunk size from the joint service objective, not from prefill throughput alone.

Use phase-specific metrics

Measure prefill with input tokens per second and time to first token across the prompt-length distribution. Measure decode with output tokens per second and time per output token across active-sequence and retained-context distributions. Record queueing separately or include it explicitly in the end-to-end metric.

Input and output tokens are not interchangeable units of work. Prefill handles many prompt positions in parallel, while decode repeatedly traverses model layers and cache history for one new position. A total-token rate can be useful only after the workload mix is fixed and the two components are also disclosed.

Worked example: Prefill and decode for one request

A request with an 8,192-token prompt asks for up to 256 output tokens. The request enters a GPU service that is already decoding short interactive requests with a p99 time-per-output-token objective of 80 milliseconds.

Calculate the prompt's prefill shapes. Each projection sees 8,192 token rows for this request before batching with other prefill work. Estimate projection arithmetic and attention work separately because their scaling with sequence length differs.
Measure uninterrupted prefill duration. Suppose processing the complete prompt in one scheduled unit takes 310 milliseconds. Existing decode sequences would receive no device iteration during much of this interval and would violate the 80-millisecond tail objective.
Test prefill chunks of 512, 1,024, and 2,048 tokens. Between chunks, schedule decode iterations for active requests. Record the long request's time to first token, existing requests' time per output token, aggregate throughput, and scheduler overhead.
Calculate KV-cache payload for the long sequence. For a model with 32 standard attention layers, Hkv = 8, Dh = 128, and BF16 cache entries, one token requires 2×32×8×128×2 bytes = 131,072 bytes, or 128 KiB. The 8,192-token prompt therefore requires approximately 1 GiB before output tokens, block rounding, allocator metadata, and temporary workspace are added.
During decode, this request adds one token per iteration and reads attention history from the retained context. Track how its long cache affects attention time and how cache capacity limits the number of other active sequences.
Sweep active decode sequences. Increasing the count should improve weight reuse and aggregate output tokens per second until matrix, memory, or cache capacity limits the system. Mark the highest point that still satisfies time-per-output-token and admission requirements.

Conclusion: The selected schedule must balance the long request's time to first token, existing requests' decode cadence, aggregate throughput, and approximately 1 GiB of cache required by the long prompt. One combined token rate cannot express these constraints.

Common errors

Benchmarking prefill and extrapolating the result to decode. Their matrix shapes, cache traffic, and latency objectives differ.
Reporting total tokens per second without separating input and output tokens and fixing the workload mix.
Calculating KV cache from query-head count when the model uses fewer key/value heads. Use Hkv from the actual architecture.
Maximizing decode batch without measuring queue delay, iteration latency, cache capacity, and fairness among active sequences.

Reference summary

Autoregressive inference has two computational phases. During prefill, the model processes all prompt tokens and creates the initial key-value cache. Many prompt positions participate in each projection, which produces relatively large matrix multiplications. During decode, each active sequence contributes one new token per iteration. The projection matrices become much narrower, while the system repeatedly reads model weights and the retained key-value history.

Time to first token includes admission delay, queueing, prompt preprocessing, prefill, first-token sampling and postprocessing, and delivery to the selected measurement boundary.
Time per output token measures the cadence of decode for an active request. Report its distribution because other requests can interrupt or delay that cadence.
Aggregate output tokens per second measures completed decode work across all active sequences. The completion rate must be paired with prompt lengths, output lengths, offered requests per second, and latency limits.
KV-cache payload grows with active sequence count and retained context. Block rounding, allocator metadata, temporary copies, fragmentation, and conservative reservation further reduce the number of sequences that fit.
Chunked prefill divides a long prompt into smaller scheduled units. Interleaving decode work between the chunks can reduce delays for existing requests, but chunking adds scheduling overhead and can increase the long request’s own time to first token.

Knowledge check

When the scheduler advances more active requests in each decode iteration, why can output tokens per second increase while the interval between tokens for one active request also increases? Name the expected matrix-shape and scheduler-timeline changes.

Show the answer guide

A decode iteration advances each selected request by one token. Increasing the active-request count changes linear-layer input shapes from approximately `[1, hidden]` toward `[B, hidden]`, so GEMM's M dimension and the number of output token rows increase.
The larger token matrix reuses one traversal of each weight tile across more rows. Weight bytes per produced token fall, and output tokens per second can rise until compute, KV traffic, memory capacity, or another limit takes over.
The GPU timeline should show fewer underfilled matrix operations and larger or longer GEMM kernels for each decode iteration. Kernel efficiency can improve even as one iteration takes more elapsed time.
Each active request ordinarily receives only one new token per decode iteration. Longer iterations, scheduler batch-formation delay, or skipped iterations therefore increase the gap between successive tokens for an individual request.
The scheduler timeline should show more sequences assigned to each iteration, a changed prefill/decode mix if applicable, longer iteration intervals, and the per-request sequence IDs receiving progress less frequently in wall-clock time.
Measure total output tokens/s together with per-request time per output token (TPOT) or inter-token-gap distributions, queue delay, context lengths, and KV-cache occupancy; throughput alone cannot choose the operating point.

Practice

Model decode batching and token cadence

Use the simple iteration-time model `t(B) = 1.2 ms + 0.08 ms × B` for decode batch sizes 1, 2, 4, 8, 16, and 32. Calculate output tokens/s as `B/t(B)` and the per-request token interval as `t(B)`. Assume every selected request receives exactly one token per iteration.

Evidence to keep: Keep the calculation table, a two-axis plot of total tokens/s and per-request token interval against batch size, the inferred `[B, hidden]` matrix-shape change, and a written explanation of why both metrics rise together in this model.

The foundation chapters have defined objectives, quantitative models, measurement methods, numerical formats, and transformer workloads. Part II maps these workloads to accelerator execution and memory behavior.

References

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.