L8.1 · LESSON 1 OF 6

Greedy selection

Compute temperature and candidate filtering, and distinguish sampling from greedy and beam decoding.

THE IDEA

Picking the top token

A language model outputs a probability for every possible next token. Decoding is the rule that turns those probabilities into text. The simplest rule is greedy selection: at every step take the single most probable token. It is deterministic, and when two tokens tie you need a stated rule (for example, the lowest index).

But the best choice at each step does not guarantee the best whole sequence: an early choice can lead into a poor continuation.

A tiny model. Step 1: a 0.6, b 0.4. After a: c 0.5, d 0.5. After b: c 0.9, d 0.1. Every sequence then ends.

complete sequence	probability	greedy?
<s> b c </s>	0.36	← best
<s> a c </s>	0.3	← greedy
<s> a d </s>	0.3
<s> b d </s>	0.04

greedy picks the top token at every step: a (0.6), then c (tie with d: the first alphabetically) greedy sequence probability = 0.6 · 0.5 = 0.3 best sequence <s> b c </s> = 0.4 · 0.9 = 0.36

Greedy is deterministic (the same input gives the same output), unlike sampling, but a locally best step need not lead to the best whole sequence. Ties need a stated rule.

A four-sequence model. Greedy's path is not the most probable sequence.

Predict first. Is greedy selection the same as drawing a random token?

Chapter context

Decoding chooses tokens from the model's output distribution. It changes generated behavior without retraining the model. Sampling settings influence diversity and concentration, but they do not independently guarantee correctness or creativity.

TRY IT YOURSELF

Part 1. Do it hands-on

Follow greedy through the tiny model and compare it with the best whole sequence, then code greedy decoding and exhaustive search.

A tiny model. Step 1: a 0.6, b 0.4. After a: c 0.5, d 0.5. After b: c 0.9, d 0.1. Every sequence then ends.

complete sequence	probability	greedy?
<s> b c </s>	0.36	← best
<s> a c </s>	0.3	← greedy
<s> a d </s>	0.3
<s> b d </s>	0.04

greedy picks the top token at every step: a (0.6), then c (tie with d: the first alphabetically) greedy sequence probability = 0.6 · 0.5 = 0.3 best sequence <s> b c </s> = 0.4 · 0.9 = 0.36

Greedy is deterministic (the same input gives the same output), unlike sampling, but a locally best step need not lead to the best whole sequence. Ties need a stated rule.

first token greedy picks P(<s> b c </s>) P(greedy's sequence)

To do: A model's first-step probabilities are a = 0.6, b = 0.4. Then after a: c = 0.5, d = 0.5; after b: c = 0.9, d = 0.1. Greedy picks the top token at each step. Type the first token it picks
To do: The probability of the best complete sequence <s> b c </s> is 0.4 · 0.9. Type it
To do: Greedy's own sequence <s> a c </s> has probability 0.6 · 0.5. Type it

Part 2. Do it in code

greedy_token(probs): the index of the largest probability; the first index wins a tie (define and keep this rule).
greedy_decode(lm, start="<s>", end="</s>", max_len=20): lm maps a token to a dict {next: probability}. Repeatedly take the most likely next token (ties: the alphabetically first) until end or max_len tokens. Return the list of tokens including start and end.
sequence_prob(lm, seq): the product of the transition probabilities along seq (0 if a transition is missing).
best_sequence(lm, start="<s>", end="</s>"): enumerate all complete paths (the model has no cycles) and return (sequence, probability) of the most probable one.

def greedy_token(probs):
    pass

def greedy_decode(lm, start="<s>", end="</s>", max_len=20):
    pass

def sequence_prob(lm, seq):
    pass

def best_sequence(lm, start="<s>", end="</s>"):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Is greedy selection the same as drawing a random token?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

p_i(T)=\frac{\exp(z_i/T)}{\sum_j\exp(z_j/T)},\quad T>0.

Top-p retains a probability-sorted prefix with cumulative mass at least p, then renormalizes the retained entries. Specify tie handling and any minimum-candidate rule in implementation.

Worked example

For logits [2,1,0] at temperature one, probabilities are approximately [0.665241,0.244728,0.090031]. With top-p=0.8, keep the first two because the first alone is below the threshold. Their renormalized probabilities are approximately [0.731059,0.268941].

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import exp,isclose
weights=[exp(v-2) for v in [2,1,0]]
probs=[w/sum(weights) for w in weights]
assert probs[0] < .8 < sum(probs[:2])
retained=[p/sum(probs[:2]) for p in probs[:2]]
assert isclose(probs[0],.6652409557748218)
assert isclose(retained[0],.7310585786300049)
assert isclose(sum(retained),1)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Top-p=.8 does not mean keeping 80% of vocabulary items. A high temperature does not create new factual knowledge. Filter-and-renormalize order must be explicit.