A request becomes tokens, and tokens become two different workloads

TL;DR: The model first processes the prompt to choose an output token. It then feeds generated tokens back through the model to choose the ones that follow. These phases, called prefill and decode, offer different opportunities to reuse weights. Measure their time separately before deciding which to optimize.

Where you are. Second module of the foundations course. You have met bandwidth and compute limits. Start here with two numbers and calculate an output by hand; then follow a request through a small Transformer. Both examples have optional CPU checks. You can follow the diagrams and arithmetic without running code.

Tokens first, because the unit matters

A short chat message and a request containing a long document each count as one request. They can require very different amounts of work. To understand that difference, we need to follow the text into the model.

A tokenizer turns text into a sequence of token IDs, integers that identify entries in its vocabulary. Each ID selects a row of numbers from a learned embedding table. The model transforms these rows through its layers and produces logits: scores for the possible next tokens. A selection rule chooses one token, which can then be converted back to text. Generation repeats this process to build the response.

The learned values used in these transformations are the model's weights. The intermediate values computed for this particular input are activations. During ordinary inference, the activations change while the weights stay fixed. Tensors, Shapes and Dtypes explains how to describe the dimensions and storage of these arrays.

This gives us two useful ways to count demand. Requests per second tell us how often new work arrives. Prompt and output lengths help us estimate how much work each arrival creates and how much state it retains. We also need to know which lengths occur together, how arrivals bunch up, and how often cached state can be reused. Request rate alone leaves those questions unanswered.

Calculate one prediction before following a whole request

Suppose a model receives the feature vector x = [2, -1]. A vector is an ordered list of numbers. These two features have no assigned word meanings: this is an original, hand-chosen toy network, with no trained checkpoint, tokenizer or attention. We use it to see the arithmetic inside a forward pass.

A linear layer multiplies inputs by weights and adds a bias. Each output has its own weights; its bias is an extra fixed offset. With a bias, the mathematical operation is affine, although libraries still call it a linear layer. Here the first output uses weights [1, 1] and bias 0; the second uses [-1, 2] and bias 1:

first output  = 2 × 1 + (-1) × 1 + 0 = 1
second output = 2 × (-1) + (-1) × 2 + 1 = -3
result = [1, -3]

Next apply ReLU, an activation function that replaces each negative value with zero. The intermediate vector becomes h = [1, 0]. An activation function is an operation; an activation is a changing value produced during computation. Neither is an update to the weights.

The final layer produces three scores, called logits, for candidate IDs 0, 1 and 2. Its weight rows are [2, 0], [0, 1] and [-1, 1], with biases [0, 1, 0]. Reuse the same multiply-and-add rule:

score for ID 0 = 1 × 2 + 0 × 0 + 0 =  2
score for ID 1 = 1 × 0 + 0 × 1 + 1 =  1
score for ID 2 = 1 × (-1) + 0 × 1 + 0 = -1
logits = [2, 1, -1]

Softmax exponentiates scores and divides by their sum. Subtracting the largest score first avoids large exponentials without changing the distribution:

shifted logits = [0, -1, -3]
exponentials ≈ [1, 0.367879, 0.049787]
sum of unrounded exponentials ≈ 1.417667
probabilities ≈ [0.705385, 0.259496, 0.035119]
sanity: all are nonnegative and their unrounded sum is 1.

Greedy selection takes ID 0, the largest score; it can do so without computing softmax. Sampling could choose another candidate. The 70.5% value describes this toy distribution, not confidence that an answer is true.

Why add ReLU between layers? A chain of only affine operations can be combined into one affine operation. ReLU changes which intermediate coordinates contribute as the input changes. Here it suppresses -3; removing it would produce logits [2, -2, -4]. Other architectures use different nonlinear functions or gates, so this toy is not a full Transformer.

Try x = [0, 1] with all the same weights and biases. The first layer gives [1, 3], ReLU leaves it unchanged, and the logits become [2, 4, 2]. Greedy selection now chooses ID 1. A different answer does not mean the model learned new weights during the request. Forward Pass, Backpropagation and Optimizer Steps explains when parameter updates actually happen.

Optional check, using only Python's standard library:

from math import exp, isclose

def linear(x, rows, biases):
    return [sum(a*w for a, w in zip(x, row)) + b
            for row, b in zip(rows, biases)]

def predict(x):
    raw = linear(x, [[1, 1], [-1, 2]], [0, 1])
    hidden = [max(0, value) for value in raw]
    logits = linear(hidden, [[2, 0], [0, 1], [-1, 1]], [0, 1, 0])
    terms = [exp(v - max(logits)) for v in logits]
    probs = [v / sum(terms) for v in terms]
    assert isclose(sum(probs), 1.0)
    return raw, hidden, logits, max(range(3), key=lambda i: logits[i])

assert predict([2, -1]) == ([1, -3], [1, 0], [2, 1, -1], 0)
assert predict([0, 1]) == ([1, 3], [1, 3], [2, 4, 2], 1)
print("both forward passes checked")

These fixed shapes are intentional; the helper is an arithmetic check, not a general tensor library. In a language model, learned embedding vectors enter a much larger computation. A forward pass computes scores from its available inputs. Choosing a token and feeding it back is an additional step in the generation loop below.

Follow three positions through a small Transformer

Now follow those changing values through a small Transformer whose weights also stay fixed. This is an untrained example with prompt IDs [1, 4, 6] and a vocabulary of eight entries. The IDs have no assigned word meanings.

Each position is represented by four numbers, so the model's hidden width H is four. Those representations pass through two Transformer blocks. Within each block, two attention heads work with two coordinates each, and a feed-forward network temporarily expands each row to eight coordinates. These dimensions are small enough to follow by hand; they do not predict a trained model's speed or quality.

The embedding table maps the three IDs to three four-number rows. Add a learned position vector to each row so positions differ even when their IDs match. This example uses additive position embeddings; a rotary architecture instead transforms query/key coordinates at the appropriate attention boundary. Never add both treatments to a deployed checkpoint without checking its architecture.

The working tensor now has shape [3, 4]: three positions, four features each. These rows change through the model. The parameter tables used to transform them remain fixed during inference. Tokens, Embeddings and Logits explains the representation names; the task here is to follow their dimensions and dependencies.

One block, with the dimensions exposed

Within a block, attention lets a position use information from the positions it is allowed to see. It starts by computing three representations: a query (Q) for the position seeking information, keys (K) to compare that query against, and values (V) to combine according to those comparisons.

This example normalizes each row's features using root-mean-square (RMS) normalization before computing Q, K and V. Each is produced by a projection, a matrix multiplication that forms new features from old ones. The projected coordinates are split into two heads, each with its own query–key comparisons. The table follows the shapes through the rest of the block.

The residual adds the earlier vector to the sublayer's output, so their shapes must match. After attention, the feed-forward network processes each row separately. Our fixture uses a two-projection network with ReLU, which sets negative intermediate values to zero; gated or expert-routed blocks require different parameter and compute counts. The next block receives the updated [3, 4] representation and uses its own parameters. Inside a Transformer Block explains these operations and their alternatives.

The mask carries the dependency

The model must preserve the order of the sequence even when it processes several positions together. Number the positions from zero: the query at position one may use keys from positions zero and one, but not position two. A causal mask enforces this restriction, including when all three prompt IDs are already available.

For each query, softmax converts the permitted comparison scores into nonnegative weights that sum to one. Attention uses those weights to combine the corresponding values. Softmax therefore runs over keys within each query row; combining scores across different queries or requests would perform a different calculation.

A masked entry receives no probability. Numerically it is often represented by adding negative infinity before softmax, not by replacing its score with zero: exp(0) is one and still contributes. In the third row of the first head, the executable fixture gives approximately:

scaled scores = [-0.048852, -0.110654, -0.042627]
softmax weights = [0.339407, 0.319066, 0.341527]
weighted value result = [-0.088750, -0.066273]
sanity: the three weights sum to 1; the two-value result is not a token ID.

Heads join their results; the output projection returns four features. The residual and feed-forward operations update those features before the next block. After both blocks, the final prompt row produces eight vocabulary logits. In this untrained fixture, ID 2 has score about 0.892225 and ID 5 about 0.872022. Greedy selection chooses ID 2. This is an arithmetic result, not a meaningful text prediction or a factual-confidence score.

All prompt rows can be computed together within a layer because their inputs are known and the mask prevents future access. Block two still waits for the required block-one outputs. The next generated ID is unknown until selection finishes; that is the dependency behind the next decode step.

The two phases

Prefill processes the uncached prompt positions. In a causal transformer these positions can run in parallel within each layer because the prompt tokens are already known; a causal mask prevents access to future positions. A scheduler may split that work into chunks. Large linear layers often have high arithmetic intensity, but small prompts and attention kernels need their own measurements.

Decode ordinarily adds one generated position per active sequence per iteration. At batch one, dense linear work resembles matrix-vector multiplication. For two-byte weights its weight-only intensity is approximately 1 FLOP/byte, before activation and attention traffic. A mixed batch processes multiple sequences, and speculative decoding may accept several generated tokens in an iteration. MoE routing also changes which weights participate.

For full causal attention, the KV cache stores earlier key and value vectors so later steps can reuse them. Each new processed position adds state, and attention reads the relevant history. Sliding windows bound some layers’ retained history; recurrent or hybrid architectures use different state layouts. The cache makes generation cheaper; generation without caching remains possible.

How the phases compete for a device

Consider a GPU that is streaming responses when a new, long prompt arrives. Processing a large part of that prompt at once gives the linear layers more opportunities to reuse weights. But the existing responses may wait longer for their next decode step. Dividing prefill into smaller chunks gives the scheduler more chances to resume those responses, at the cost of extra scheduling and potentially less efficient kernels.

Prefill contributes to time to first token, alongside queueing, tokenization and transport. Decode cadence contributes to streaming smoothness. Improving one metric does not guarantee improvement in the other; compare both under the same arrivals.

The following techniques change different parts of this schedule and its memory budget:

• Batching groups decode passes so one weight read serves many sequences.
• Paging allocates cache in blocks as state grows, reducing unused reservations.
• Prefix reuse reuses compatible cached state for matching token prefixes.
• Chunking creates opportunities to schedule decode between smaller prompt work units.
• Splitting the phases across separate machines lets each be tuned alone.

For each technique, ask which time or memory term it changes and what it costs elsewhere.

Decide what to measure first

Start a serving discussion by describing the requests: their prompt and output lengths, how many are active together, and how long users can wait. Cache-hit rates and measured prefill and decode times help turn that description into a tuning decision.

A long prompt might suggest starting with prefill, but token counts alone cannot settle the question. Prefill and decode process tokens at different rates, and a request may spend more time waiting in a queue than in either phase. The exercise below shows why you need the timings as well as the lengths.

Verify the small model on a CPU

This optional check uses NumPy float64. The fixed random seed constructs untrained weights, additive positions and two bias-free blocks. RMS normalization has unit gain; there is no dropout, quantization or sampling randomness. It prints 2 2: the first two generated IDs. The assertion compares one cached decode step with recomputing the entire four-position sequence. It tests semantics, not GPU performance.

import numpy as np

rng = np.random.default_rng(19)
H, heads, d, F, vocab = 4, 2, 2, 8, 8
E, P, out = [rng.normal(0, .3, (8, 4)) for _ in range(3)]
layers = [tuple(rng.normal(0, .3, shape) for shape in
          [(4, 12), (4, 4), (4, 8), (8, 4)]) for _ in range(2)]

def norm(x):
    return x / np.sqrt(np.mean(x*x, axis=-1, keepdims=True) + 1e-6)

def forward(ids, cache=None, offset=0):
    x = E[np.array(ids)] + P[offset:offset+len(ids)]
    states = []
    for i, (qkv, wo, up, down) in enumerate(layers):
        q, k, v = [a.reshape(-1, heads, d).transpose(1, 0, 2)
                   for a in np.split(norm(x) @ qkv, 3, axis=-1)]
        if cache is not None:
            k = np.concatenate([cache[i][0], k], axis=1)
            v = np.concatenate([cache[i][1], v], axis=1)
        scores = (q @ k.transpose(0, 2, 1)) / np.sqrt(d)
        allowed = np.arange(k.shape[1])[None, :] <= (offset + np.arange(len(ids)))[:, None]
        scores = np.where(allowed[None, :, :], scores, -np.inf)
        probs = np.exp(scores - scores.max(axis=-1, keepdims=True))
        probs /= probs.sum(axis=-1, keepdims=True)
        joined = (probs @ v).transpose(1, 0, 2).reshape(-1, H)
        x = x + joined @ wo
        x = x + np.maximum(0, norm(x) @ up) @ down
        states.append((k, v))
    return norm(x) @ out.T, states

ids = [1, 4, 6]
logits, cache = forward(ids)
first = int(logits[-1].argmax())
next_logits, _ = forward([first], cache, offset=3)
full_logits, _ = forward(ids + [first])
np.testing.assert_allclose(next_logits[-1], full_logits[-1],
                           rtol=1e-12, atol=1e-12)
print(first, int(next_logits[-1].argmax()))

The causal mask makes earlier positions independent of later tokens. Changing the third input ID must leave the first two output rows unchanged. In a packed batch of separate documents, add a same-document condition to allowed; the single-sequence function above deliberately does not implement packing. Reusing its triangle for unrelated requests would let one request read another's state.

Do this before moving on

First cover the worked variation and calculate the toy network for [0, 1]. Check that you get [1, 3] after ReLU and [2, 4, 2] as logits, with ID 1 selected. The weights stay fixed.

In the Transformer fixture, predict the effect of changing the third input ID: the first two output rows stay fixed, while the third may change. Then take two workloads and decide which phase dominates each:

1. A code assistant that receives 8,000 tokens of context and returns a 40-token completion.
2. A chat product that receives 200 tokens and streams back 800.

Compute the ratio of prompt tokens to output tokens for each, then say which phase you would optimize first and what you would expect to gain. Those ratios are 200:1 and 1:4, but they are token counts, not time ratios. Use the hypothetical measured rates below to check the conclusion. Assume no prefix hits or queueing and a constant 30 ms between output tokens:

code assistant: prefill = 8,000 / 20,000 tokens/s = 0.400 s
remaining output = (40 - 1) × 0.030 s = 1.170 s
phase total = 0.400 + 1.170 = 1.570 s
chat: prefill = 200 / 5,000 tokens/s = 0.040 s
remaining output = (800 - 1) × 0.030 s = 23.970 s
phase total = 0.040 + 23.970 = 24.010 s
sanity: prefill already samples token one, so use output length minus one

The long-prompt example still spends more elapsed time generating output under these assumptions. Prioritize decode for completion latency here; reverse the choice if the product’s failing metric is time to first token or measured prefill is slower. These rates are illustrative, not portable capacity numbers. The Orca paper explains why iteration-level scheduling matters when request lengths differ.

Go deeper

• Tokens, Embeddings and Logits extends the trace into a Premium exercise on vocabulary projection, batching and logit memory.
• Inside a Transformer Block separates attention, feature transformations and the residual paths between them.
• Prefill vs Decode derives the mechanics of the split, with the arithmetic for each phase written out.
• The KV Cache explains what is stored and why it grows the way it does, which is the next thing you need.
• Continuous Batching shows how changing batch membership reuses capacity as requests finish.
• Chunked Prefill explains how smaller prompt work units let the scheduler resume ongoing responses sooner.
• Prefill vs decode: why they need different hardware is the interview version of this lesson.
• What is the KV cache and why does it grow? works through the cache-size derivation as an interview exercise.

Key takeaways

• The toy input changes from [2, -1] to [0, 1] and selects a different output with unchanged weights. Inference recomputes activations.
• Prefill processes uncached positions, possibly in chunks, and produces logits used to sample the first output token.
• Ordinary decode then needs O − 1 iterations for O output tokens; batching and speculation change work per iteration.
• Full-attention KV state grows with processed positions; sliding-window and recurrent state require different accounting.
• Batching, paging, prefix reuse, chunking and phase splitting are all responses to the same asymmetry.

Check yourself

Answer before you look. Recalling it is what makes it stick; recognising it does not.

1. 1A request has 0.4 s prefill and then emits the remaining 39 tokens at 30 ms each. Which phase contributes more completion time?

   Neither; they are balanced because both run once per requestPrefill: the prompt contains more tokensDecode: its remaining iterations take 1.17 sDecode, because the KV cache is largest during generation

2. 2Why does low-batch dense decode usually have less weight reuse than prefill?

   Answer it, then reveal

3. 3The toy network receives [0, 1] instead of [2, -1]. What changes?

   The weights must be retrained before another output is possibleActivations become [1, 3], logits become [2, 4, 2], and greedy selection chooses ID 1The output stays ID 0 because the weights did not changeReLU turns every intermediate value into a probability

4. 4The prompt has three known IDs. Can all positions run together, and can both Transformer blocks run independently?

   Answer it, then reveal

5. 5Why is setting a forbidden attention score to zero not a causal mask?

   Softmax exponentiates it to one, so it can still influence the resultA mask can only be applied after samplingThe vocabulary projection fixes the leakZero always becomes zero probability