Greedy Decoding

The model could append several different pieces. The simplest choice is always to take the most likely one. This saves consideration of alternatives, but does the best first step lead to the best entire sequence?

Greedy Decoding chooses the highest-scoring token, a piece of text, at every step and continues from that choice. It does not sample or return to skipped paths.

If A has probability 0.6 and B 0.4, it chooses A. But if the best next step after A has probability 0.51, the whole path has probability 0.306. A path through B with continuation 0.99 has probability 0.396. The local leader can therefore lose when evaluating two steps together.

The method is simple, but does not guarantee the most probable whole sequence or the best answer for a person. Beam Search keeps more paths at an additional cost.

Mechanism and details

The rule is presented in the Hugging Face documentation, “Greedy search”. Mathematically, we select $\arg\max_v p(v\mid x_{<t})$: among tokens $v$, we take the maximum given the existing sequence $x_{<t}$. A tie requires an established tie-breaking rule. The absence of sampling does not promise an identical result when the model, computation, or configuration changes.

A local winner can lose the whole sequence

This original example has exactly two steps. Initially, A has probability 0.6, and B has 0.4. After A, the best continuation has probability 0.51; after B, it has 0.99. Greedy selects A, then its best continuation: $0{,}6\cdot0{,}51=0{,}306$. However, the skipped path through B has $0{,}4\cdot0{,}99=0{,}396$. All distributions shown are invented and sum to 1; the sequence ends after two tokens.

Beam Search retains several partial sequences to defer such a choice. Top-k Sampling, by contrast, restricts the candidates for sampling the next token. With one unique maximum and $k=1$, token selection matches greedy.

The most probable text need not be true or useful. Holtzman et al., §2.2–3 distinguish probability maximization from the quality of open-ended continuations. This is separate from the search error shown above.

I use AI-generated content as part of my daily learning process.