Greedy decoding answers a slightly wrong question. It picks the most probable next token, every step, but what you usually want is the most probable whole sequence, and those are not the same thing. A word can be the single best continuation right now while everything that follows it is mediocre.
This tree is built so that happens immediately. The first token "cat" has probability 0.5 against "dog" at 0.32, so greedy takes it, and everything under "cat" turns out flat and indecisive. Under "dog" hides a spine of high-probability continuations whose product beats anything "cat" can reach. Play the search at width 1 and watch it walk into the trap; widen to 2 and the runner-up stays alive just long enough for its subtree to win.
The mechanism is worth watching step by step. Every live beam proposes all of its children; the pool of candidates is ranked by cumulative log-probability, which is where a strong past can subsidise a weak present; and only the best k survive. The crossed-out boxes are real candidates that were considered and pruned, which is exactly what a finished-looking diagram of beam search hides. Widths three and four are on the slider too: on a tree this small they converge on the same answer as width two, which is itself a lesson in diminishing returns.
Two honest limits. Beam search is not exhaustive: even here, a width of 2 explores a fraction of the tree, and there exist trees that fool any fixed width. And in open-ended generation, maximising sequence probability is often not what you want at all: the highest-probability continuation of a chat prompt is repetitive and dull, which is why beam search rules translation and speech recognition, where there is a right answer, and sampling rules creative generation, where there is not.
The maths
- The objective
The best sequence maximises the SUM of log-probabilities, not each term separately. Greedy maximises term by term, which is exactly the difference this tree exploits.
- One step of the search
Every beam is extended by every token, and the pooled candidates are cut back to k. With k = 1 this is greedy; with k equal to the whole vocabulary raised to the depth, it is exhaustive search. Everything practical sits in between.
- Why the trap works
The concrete numbers from this tree: a strong first step followed by weak ones loses to a weaker first step followed by strong ones. The right side is only reachable if something other than the argmax survives level one.
Related terms
- Next-token predictionNext-token prediction is the one job a language model does: given the text so far, predict the most likely next token, add it, and repeat. It is both the training objective and what runs at inference.
- InferenceInference is the act of running a trained model to get an answer: text goes in, a prediction comes out. Every message you send to a coding agent is an inference. It is the opposite end of the lifecycle from training.
- TokenA token is the unit of text a model reads and writes: a chunk that is usually part of a word, not a whole word or a single character. Everything is measured in tokens, including your context window and your bill.