I01 — Decoding, sampling and the KV cache
← T06 — Core gate · E01 — Reproducible training → · Glossary
Prerequisites: T05, T06. Allow one session.
T05’s MiniGPT.generate draws a fixed number of tokens at one temperature and
nothing else. Every generation loop makes three further decisions: how one row of
logits becomes one token, when the loop stops, and what it keeps between steps.
The code is src/llm_course/decoding.py; read sample_next, decode and
step_logits beside this page. Nothing here trains. The model is read, never
changed, and every function returns a new value instead of editing its input.
From logits to one token
Take five logits [2.0, 1.0, 0.5, 0.0, -1.0]. Softmax divides each exponential by
their sum. At temperature the exponentials are 7.3891, 2.7183, 1.6487,
1.0000 and 0.3679, the sum is 13.1239, and the probabilities follow. At
the logits are divided by 0.5 first, giving [4, 2, 1, 0, -2], exponentials
54.5982, 7.3891, 2.7183, 1.0000, 0.1353 and sum 65.8408:
| Logit | ||
|---|---|---|
| 2.0 | 0.5630 | 0.8292 |
| 1.0 | 0.2071 | 0.1122 |
| 0.5 | 0.1256 | 0.0413 |
| 0.0 | 0.0762 | 0.0152 |
| -1.0 | 0.0280 | 0.0021 |
Temperature never reorders the tokens; it changes their ratios. The first entry
beats the second by at and by at .
As approaches zero the first entry approaches 1, so
sample_next(logits, temperature=0) skips the division and returns the argmax:
that is greedy decoding, and distribution(logits, temperature=0) returns the
matching one-hot vector. For , distribution subtracts the largest logit
before dividing, so a temperature of 0.01 still fits in float64, then
sample_next draws one index with torch.multinomial. The draw takes an optional
torch.Generator; the same seed and the same logits give the same token, which is
what “seed 1” means in the lab output below. tests/test_decoding.py checks both
columns above within 0.001.
Sampling that stays on topic
Sampling at gives the fifth token 2.8 % of the draws. Over a hundred tokens
that tail adds up, and one improbable token drags every later token with it. Two
masks cut the tail. Top-k keeps the largest entries and renormalises: with
the first two entries hold 0.5630 + 0.2071 = 0.7701 of the mass, so they
become 0.5630 / 0.7701 = 0.7311 and 0.2689. Top-p (nucleus) sorts the
probabilities and keeps the shortest prefix whose cumulative mass reaches : the
running sums are 0.5630, 0.7701, 0.8958, 0.9720, so keeps four entries
and drops the fifth. Renormalised by 0.9720 they are 0.5792, 0.2131, 0.1292 and
0.0784. Both exist because they fail differently: top-k keeps two tokens whether
the model is certain or clueless, top-p keeps one token when the first entry
already holds 0.9 and many when the distribution is flat. distribution applies
top-k first and then top-p, and the cumulative masses top-p compares against are
those of the full softmax; the single renormalisation comes last.
Now the real model. examples/run_mini_gpt.py never writes a checkpoint, only
report.json, so the lab trains artifacts/mini-gpt/model.pt itself on first
run — T05’s recipe, seed 7, 120 steps, about a second on CPU — and reuses that
checkpoint on every run after:
python examples/run_decoding_lab.pyThe prompt 'the small model ' becomes 17 tokens with <bos>, which leaves 7 of
the 24 context positions for generation. The printed top-5 after the prompt:
T = 0.0
'f' 1.0000
' ' 0.0000
'!' 0.0000
',' 0.0000
'-' 0.0000
T = 0.7
'f' 0.3076
'p' 0.3031
'r' 0.2944
'l' 0.0911
'o' 0.0008
T = 1.2
'f' 0.2677
'p' 0.2654
'r' 0.2609
'l' 0.1317
'o' 0.0082Three characters are within 0.014 of each other and the temperature only moves the
gap to 'l' and 'o'. The three continuations at with seeds 1, 2 and 3
are follows, reveals and predict, one per leader. At the full softmax
gives 'f' 0.2858, 'p' 0.2829, 'r' 0.2771, 'l' 0.1219 and 'o' 0.0044; the
running sum is 0.8458 after three entries and 0.9677 after four, so top-p = 0.9 keeps
four of 36 tokens and prints 'f' as 0.2858 / 0.9677 = 0.2953. Top-k = 5 keeps
'o' as well and prints it at 0.0045.
When to stop
decode(model, prompt_ids, max_new_tokens=..., eos_id=...) appends one token per
step and stops after it has appended eos_id, so the returned tensor ends with the
EOS token when the stop rule fired. The lab passes CHARACTER_ENCODER.eos_id, and
all three samples still report 7 new tokens, length limit: this checkpoint never
emits <eos>. Every training document is 30 to 40 characters long, longer than the
25-token window T05 trains on, so <eos> was truncated away from every training
target and the model has never seen it as an answer. The rule is wired and never
fires; the test suite proves it by choosing each token of the greedy continuation
as the EOS id in turn. The second limit is max_new_tokens. The third is the
context: decode refuses prompt + max_new_tokens > block_size with a
ValueError, while MiniGPT.generate crops to the last block_size tokens and
restarts the learned positions at zero. A rolling window keeps generating but
silently forgets the prompt.
R01’s default generator, a 4-billion-parameter model, makes the
same choices. TransformersGenerator.generate in src/llm_course/rag/generate.py
calls
model.generate(**inputs, max_new_tokens=max_tokens, do_sample=False) with
max_tokens=300 and renders the chat template with enable_thinking=False.
do_sample=False is greedy decoding, temperature 0 in this lesson’s terms, so the
same prompt gives the same answer on every run, which is what lets R02 measure
rates. Generation stops at the model’s end-of-turn token or after 300 new tokens,
whichever comes first; rule 4 of the system prompt, “at most five sentences”, is
what usually ends it long before 300. Streaming is nothing more than this loop with
the print statement inside it: each step yields one token, and a server can send it
before the next step begins.
Why every step recomputes everything
decode gets its logits from model(ids[None])[0, -1]: the full forward over all
tokens, of which it keeps the last row and discards the rest. Count the work at
prefix length with width . Each block projects positions to queries,
keys and values, multiply-adds, forms a score matrix per head,
and runs the FFN over positions, more. Step does all of it
again for the first positions, although the causal mask guarantees that their
hidden states, keys and values have not changed: position never reads a
position after . Per step the projections cost and the scores ;
summed over generated tokens that is and . With a cache the
projections cost per step, in total, and only the scores keep
per step, in total: against for the term that
dominates at this width. At prefix 96 one
block’s three projections cost multiply-adds
for a step that only needs the newest token’s 3,072.
The KV cache
The cache keeps what the mask makes immutable. KVCache holds, per block, the keys
and values of every token fed so far, each [heads, length, head_dim], here
[4, t, 8]. That is 64 floats per token per block, 128 for both blocks, 512 bytes
in float32; the full 24-token context is 3,072 floats, a tenth of the model’s
28,288 parameters. Queries, hidden states and FFN outputs are not stored: each is
used once. step_logits(model, cache, token_id, position) embeds one token and its
position, then per block runs norm_attention, the block’s own q/k/v projections on
that single token, cache.append(index, key, value), and
scaled_dot_product_attention(query, cache.keys[index], cache.values[index]): one
query against keys, no mask, because only the past is stored. The output
projection, residual, norm_ffn, ffn and second residual follow as in
DecoderBlock.forward; final_norm and lm_head give the logits. append returns
a new KVCache and leaves the other blocks’ tensors shared, so a caller that keeps
the old cache still has it. prefill feeds the prompt one token at a time,
decode_cached prefills prompt_ids[:-1] and then calls step_logits once per
generated token. Dropout is skipped; both decoders demand model.eval().
Two paths through different code must give the same logits. The lab prints
same ids under seed 1: True and
max |cached - full| logit difference over 24 positions: 2.92e-06; the test
asserts a difference below at each of 20 steps. It is not exactly zero because a batched matmul and a
one sum in different orders in float32. The timing table measures a
random-init copy of the T05 architecture with block_size=128, because
measure_decode times prefixes up to 96 tokens plus 8 generated ones and the
values of the weights do not change the cost. Best of three runs, prefill not
timed, milliseconds per generated token on one laptop CPU:
| prefix | uncached ms | cached ms | speed-up |
|---|---|---|---|
| 8 | 0.617 | 0.191 | 3.23x |
| 32 | 0.657 | 0.208 | 3.16x |
| 64 | 0.711 | 0.208 | 3.42x |
| 96 | 0.911 | 0.197 | 4.63x |
The uncached column grows about 1.5× while the prefix grows 12×, and the cached column stays flat. The speed-up at prefix 96 is about 4.6×, not the roughly 96× that a pure count of recomputed positions would predict, because at width 32 each step is dominated by the fixed overhead of a few dozen small tensor ops, and the cached step runs the same number of ops. Your numbers will differ; the shape of the two columns will not.
Predict → Trace → Build → Break → Measure → Explain
- Predict: After the shorter prompt
'the ', how many of the 36 tokens will top-p = 0.9 keep: more or fewer than the four kept after'the small model '? Write the number down before running. - Trace: Run the lab, then
python examples/run_decoding_lab.py --prompt "the ", and compare thetokens keptline with your prediction. - Build: Implement top-p from the description in the second section and compare with
distribution(logits, temperature=1.0, top_p=0.9)on the five logits. - Break: In a copy of
_cached_block, dropblock.norm_attentionand repeat the cache check. The 2.92e-06 becomes a difference of several units; the equality test is the only guard. - Measure: Call
measure_decodeon theblock_size=128timing model (the T05 checkpoint hasblock_size=24and raisesValueError) withmax_new_tokens=16and withtorch.set_num_threads(1). Which column moves? - Explain: Why does R01 decode greedily? Two sentences about reproducible answers and what R02 could not measure with sampling.
Independent exercise
Write penalised(logits, seen_ids, penalty) in artifacts/mini-gpt/penalty.py,
without editing decoding.py: for every id in seen_ids, divide a positive logit
by penalty and multiply a negative one by it, the rule of
CTRL. Feed the result to sample_next. Report
the top-5 at for the lab prompt with penalty 1.0 and 1.5, then the greedy
continuation with penalty 1.5 and 5.
Hint
seen_ids is set(ids.tolist()) and includes the prompt. 'l' occurs in
small and model, so it is penalised; 'f', 'p' and 'r' are not. A
negative logit divided by the penalty would rise, which is why the rule
multiplies it instead.
Reference answer
With penalty 1.5 the logit of 'l' falls from 4.005 to 2.670 and its
probability from 0.1219 to 0.0354; 'f' rises from 0.2858 to 0.3151. The
greedy continuation is still follows, because 'f' was never penalised and
the penalised letters keep their margin at later steps. At penalty 5 it becomes
frnicts: on a character vocabulary the rule punishes letters already used,
which is spelling, not repetition. On a word or BPE vocabulary the same rule
discourages a repeated phrase, which is what it was designed for.
Checkpoint: compute both temperature columns and both masks by hand; state which stop rule ended a sample; name what the cache stores per block and why the mask makes it valid; read the timing table without claiming more than it measured.
← T06 — Core gate · E01 — Reproducible training → · Glossary