Lesson 1 - Greedy Decoding & Its Limits

Welcome to Greedy Decoding & Its Limits#

Across the last seven modules you built a transformer from nothing but NumPy: token and position embeddings, scaled dot-product attention, the causal mask, multi-head attention, the feed-forward block, layer norm, the full backward pass, and finally a training loop that drives the loss down. By the end of Module 7 you had a trained MiniGPT sitting in memory. But a trained model is only half the story. A language model does not “know” text, it defines a probability distribution over the next character, and to turn that distribution into actual writing you need a decoding strategy: a rule for choosing the next token, appending it, and repeating.

This module is about those rules. We start with the simplest one imaginable: at every step, just take the single most likely next character. This is greedy decoding, and it is the natural first thing to try. It also has two flaws that will motivate everything else in the module, so we will look at them honestly with real output from your own model.

By the end of this lesson, you will be able to:

• Describe the autoregressive generation loop: keep the last block_size tokens as context, forward, pick a token, append, repeat
• Implement generate_greedy(model, prompt, n_new) in pure NumPy using argmax over the final-position logits
• Explain why greedy decoding is fully deterministic and demonstrate that the same prompt yields byte-identical output every time
• Recognize the failure modes of greedy decoding: repetition, getting stuck in high-probability loops, and parroting training text on a small corpus

You should be comfortable with the trained MiniGPT from Module 7 and with softmax, encode, and decode from earlier lessons. Let’s generate some text.

From logits to a next token#

Recall what a single forward pass gives you. Feed the model a context of T token ids (with T <= block_size) shaped (1, T), and it returns logits shaped (1, T, vocab_size). Each position t holds an unnormalized score for every possible next character given everything up to and including position t. When we generate, we only care about the prediction for the next character, which lives at the last position: logits[0, -1], a vector of length vocab_size.

A decoding strategy is simply a function that maps that length-vocab_size logit vector to one chosen id. Greedy decoding uses the most obvious mapping: pick the index with the highest score.

Notice we do not even need softmax here. Softmax is monotonic, so the largest logit corresponds to the largest probability; argmax of the logits and argmax of the probabilities are the same index. Greedy decoding is “give me the token the model is most confident about, and nothing else.”

To generate more than one character we work autoregressively: append the chosen token to our running sequence, then use the extended sequence (trimmed to the last block_size tokens) as the context for the next step. Every generated character becomes part of the input for the character after it.

Training the MiniGPT for this module#

So we have something to sample from, we train the same char-level MiniGPT you built in Module 7 on the Lantern Bay corpus. The setup below is exactly the canonical corpus, tokenizer, and config from earlier lessons, trained briefly with Adam. We keep the run short (1000 steps) because greedy decoding does not need a perfectly converged model to make its point, it only needs a model that has clearly learned the text.

import numpy as np, time, warnings
warnings.filterwarnings("ignore")

CORPUS = (
    "the lamp keeper walks the shore at dusk. "
    "the lamp keeper lights the lantern when the fog rolls in. "
    "the boats come home when the lantern glows. "
    "the boats wait outside the bay when the fog is thick. "
    "a small boat drifts near the rocks at dawn. "
    "the keeper rings the bell when a boat drifts near the rocks. "
    "the tide rises at dusk and falls at dawn. "
    "the gulls call over the bay when the tide is low. "
    "the keeper counts the boats and writes the count in a book. "
    "the lantern burns all night and rests at dawn. "
) * 20

chars = sorted(set(CORPUS)); vocab_size = len(chars)
stoi = {c: i for i, c in enumerate(chars)}; itos = {i: c for i, c in enumerate(chars)}
encode = lambda s: [stoi[c] for c in s]
decode = lambda ids: "".join(itos[i] for i in ids)
data = np.array(encode(CORPUS), dtype=np.int64)

# MiniGPT, Adam, softmax, get_batch are the pieces you built in Modules 1-7.
# (Imported here unchanged from your module code.)
from minigpt import MiniGPT, Adam, softmax, get_batch

block_size, n_embd, n_head, n_layer = 32, 64, 4, 3
np.random.seed(42)
rng = np.random.default_rng(42)

model = MiniGPT(vocab_size, block_size, n_embd, n_head, n_layer, seed=42)
opt = Adam(model.P, lr=3e-3)
train_data = data[: int(len(data) * 0.9)]

t0 = time.time()
for step in range(1000):
    xb, yb = get_batch(train_data, block_size, 32, rng)
    _, loss = model.forward(xb, yb)
    grads = model.backward()
    opt.step(model.P, grads)
    if step % 200 == 0 or step == 999:
        print(f"step {step:4d}  loss {loss:.4f}")
print("trained in", round(time.time() - t0, 1), "s")

step    0  loss 3.2026
step  200  loss 0.1894
step  400  loss 0.1510
step  600  loss 0.1522
step  800  loss 0.1272
step  999  loss 0.1170

The loss falls from 3.2026 (close to ln(24) ≈ 3.18, the entropy of guessing uniformly among 24 characters) to about 0.12 in around 20 seconds on CPU. The model has learned the corpus well. Now let us make it write.

Implementing generate_greedy#

The generation function is short. We encode the prompt into ids, then loop n_new times. On each iteration we slice the last block_size ids as context, add a batch dimension, run one forward pass, take the argmax of the final-position logits, and append it. At the end we decode the whole id list back into a string.

def generate_greedy(model, prompt, n_new):
    block_size = model.cfg[1]          # (vocab_size, block_size, n_embd, n_head, n_layer)
    ids = encode(prompt)               # start from the prompt characters
    for _ in range(n_new):
        context = np.array([ids[-block_size:]])   # (1, T), T <= block_size
        logits, _ = model.forward(context)        # (1, T, vocab_size)
        next_id = int(logits[0, -1].argmax())     # single most likely next char
        ids.append(next_id)                        # feed it back in
    return decode(ids)

Three details are worth pausing on. First, ids[-block_size:] is what keeps context bounded: the model can only attend to block_size positions, so we never pass it more than that. Second, we read logits[0, -1], the prediction for the character after the current context, and ignore every earlier position. Third, argmax returns one index with no tie-breaking randomness, which is exactly why greedy is deterministic. Let us run it on a few Lantern Bay prompts.

for prompt in ["the lamp keeper ", "the boats ", "the tide "]:
    print(repr(generate_greedy(model, prompt, 70)))

'the lamp keeper walks the shore at dusk. the lamp keeper lights the lantern when the f'
'the boats wait outside the bay when the fog is thick. a small boat drifts near t'
'the tide is low. the keeper counts the boats and writes the count in a book. th'

The output is genuinely coherent Lantern Bay prose. Given "the lamp keeper " the model continues with a sentence it learned; given "the tide " it picks up a different thread. Character by character, greedy decoding is following the highest-probability path the model learned from the corpus. So far, so good, this is a working text generator built entirely from NumPy. The trouble shows up when we ask what greedy cannot do.

Limit 1: greedy is deterministic#

The most immediate limitation is that greedy decoding can only ever give you one completion per prompt. There is no randomness anywhere in the loop, argmax always returns the same index for the same logits, and the logits are fixed once the weights are. Generate from the same prompt twice and you get byte-identical output.

a = generate_greedy(model, "the lamp keeper ", 70)
b = generate_greedy(model, "the lamp keeper ", 70)
print("run 1:", repr(a))
print("run 2:", repr(b))
print("identical:", a == b)

run 1: 'the lamp keeper walks the shore at dusk. the lamp keeper lights the lantern when the f'
run 2: 'the lamp keeper walks the shore at dusk. the lamp keeper lights the lantern when the f'
identical: True

identical: True is not a bug, it is the definition of greedy decoding. But it is a real problem for most uses of a language model. If you want three different ways to continue a sentence, or a bit of variety in a chatbot’s replies, greedy gives you nothing to work with, the model has far more in its distribution than the single top token, and greedy throws all of it away. Every alternative continuation the model considered plausible is discarded the instant argmax runs.

Limit 2: repetition and getting stuck#

The second limitation is subtler. Greedy decoding is locally optimal, it takes the best next character at each isolated step, but a sequence of locally-best choices is not globally best. The model can walk into a region of high-probability text and then cycle through it, because the very-likely next token keeps leading back to a very-likely earlier state. Let us generate a longer passage and watch what happens.

long = generate_greedy(
    model,
    "the keeper counts the boats and writes the count in a book. ",
    150,
)
print(repr(long))

'the keeper counts the boats and writes the count in a book. the lantern burns all night and rests at dawn. the lamp keeper walks the shore at dusk. the lamp keeper lights the lantern when the fog rolls in. the '

Look closely at where the generated text goes. Starting from the last sentence of the corpus, greedy reproduces the corpus sentences in order, and then, after "...rests at dawn.", it wraps around to "the lamp keeper walks the shore at dusk.", which is the first sentence of the corpus. Greedy has walked straight into a loop: it is cycling through the entire Lantern Bay passage and will keep doing so forever. Because our corpus is that passage repeated 20 times, the highest-probability path is simply “recite the corpus again,” and greedy has no mechanism to break out.

On a small, low-entropy corpus like this one, that shows up as parroting: greedy reproduces training text verbatim and loops it. On a larger model and corpus the same mechanism produces the familiar degenerate output of greedy decoding, a phrase or clause that repeats endlessly ("...and the boats and the boats and the boats..."), because once the model is confident about a short cycle, argmax marches around it indefinitely. The locally-most-likely token has trapped the generation in a high-probability rut.

This is the core tension. Greedy is faithful to the model’s single best guess at every step, and that is exactly why it is dull and repetitive. To get varied, non-looping text we need to sometimes not take the top token, to sample from the distribution instead of maximizing it. That is what the rest of this module builds.

Practice Exercises#

Exercise 1. Modify generate_greedy to also return the probability the model assigned to each token it chose (apply softmax to logits[0, -1] and record probs[next_id] before appending). Generate 40 characters from "the " and print the average chosen-token probability. What does a very high average (near 1.0) tell you about how “confident”, and how deterministic, greedy decoding is on this corpus?

Exercise 2. Demonstrate determinism does not depend on the prompt length. Pick three different prompts of different lengths (for example "a", "the boats ", and a full sentence), and for each one call generate_greedy twice with n_new=50 and assert the two runs are equal with assert run1 == run2. Confirm all three assertions pass. Why does prompt length have no effect on determinism?

Exercise 3. Detect the loop programmatically. Generate 200 characters from "the gulls ", then check whether the first full corpus sentence, "the lamp keeper walks the shore at dusk.", appears more than once in the generated string (use str.count). Explain why a count greater than one is direct evidence that greedy decoding has entered a cycle rather than composing new text.

Summary#

Greedy decoding is the simplest bridge from a trained language model to actual text: run one forward pass, take the argmax of the final-position logits, append it, and repeat autoregressively while keeping the last block_size tokens as context. You implemented it in a handful of NumPy lines on your own MiniGPT and got coherent Lantern Bay prose out of it. But the same simplicity that makes greedy easy also makes it limited: it is fully deterministic, so one prompt yields exactly one completion, and it is locally rather than globally optimal, so it drifts into repetition and, on a small corpus, parrots and loops the training text. Those two limits are the reason the rest of this module exists.

Key Concepts#

• Decoding strategy — the rule that turns a next-token distribution into a chosen token; greedy decoding is the simplest such rule.
• Autoregressive loop — append each chosen token to the running sequence and feed the last block_size tokens back as the next context.
• Argmax selection — next_id = logits[0, -1].argmax(); no softmax needed because softmax is monotonic, and no randomness because argmax is deterministic.
• Determinism — with fixed weights, greedy gives byte-identical output for a given prompt every time; you confirmed this with identical: True.
• Repetition and looping — a chain of locally-best tokens can cycle through high-probability text; on the Lantern Bay corpus greedy recites the passage and wraps around to its start.

Why This Matters#

Every real language model, from the tiny one on your laptop to the largest deployed systems, sits behind a decoding strategy, and greedy is the baseline all the others are measured against. Understanding exactly why greedy repeats and cannot vary its output is what makes the alternatives make sense: temperature, top-k, top-p, and beam search are all direct responses to the two limits you just watched in real output. Building greedy from scratch in NumPy also demystifies “generation,” there is no magic in text generation, just a forward pass and a choice function in a loop. Once you can see that loop clearly, controlling how the choice is made becomes the entire craft of sampling.

Continue Building Your Skills#

You have seen the problem sharply: greedy decoding is faithful to the model’s single best guess and, for exactly that reason, deterministic and repetitive. The fix is to stop always maximizing and start sampling from the distribution the model produces, and the first and most important knob for that is temperature. In the next lesson you will apply softmax to the logits, divide them by a temperature T before the softmax to sharpen or flatten the distribution, and draw the next token with np.random.choice instead of argmax. You will watch a single prompt produce several different, less repetitive Lantern Bay continuations, and see how temperature trades off coherence against variety, turning the flat, looping output you got here into text with genuine choice behind every character.