Answers · How models work

Why isn't picking the most likely word at each step the best way to write a sentence?

In shortBecause the most likely word now can lead to a much worse sentence than a slightly less likely word that sets up a better continuation.

Picking the most likely token at each step maximises each conditional probability separately, and a product of separate maxima is not the maximum of the product. The sequence with the highest overall probability can begin with a token that is not the most likely one at that position. Greedy decoding answers the question 'which word now' and not the question 'which sentence overall'.

P(y_1,\dots,y_n) = \prod_{t=1}^{n} P(y_t \mid y_{<t})

Greedy decoding takes $y_t = \arg\max_w P(w \mid y_{<t})$ for each $t$ in turn. That is exactly right for one factor. It is not right for the product, because the factor at step $t+1$ depends on the token chosen at step $t$ . The choice changes the distribution that the next choice is drawn from. A token that looks slightly worse now can make a much better continuation available, and greedy has no way to ask about a continuation it has not yet reached.

FIG 1A two-token decision where greedy loses

A is the more likely first token, but B commits to a much better continuation. Greedy never evaluates B's continuation because B is discarded at the first step.

The two-step failure

Take two tokens at the first step. Token A has probability 0.60 and its best continuation has probability 0.30. Token B has probability 0.40 and its best continuation has probability 0.80. Greedy takes A, because 0.60 is larger than 0.40, then takes A's continuation, giving $0.60 \times 0.30 = 0.180$ . The sequence beginning with B has probability $0.40 \times 0.80 = 0.320$ , which is larger by a factor of $0.320 / 0.180 = 1.777\ldots$ , nearly 1.8. Greedy has produced a sequence the model itself considers substantially less likely.

0.60 \times 0.30 = 0.180, \qquad 0.40 \times 0.80 = 0.320

The natural guess is that a token that is best now must be part of the best continuation. It fails because the decision is made before the evidence for it exists. Greedy discards B at the first step; the 0.80 continuation is never computed. For greedy to be right, the continuation after A would need to reach a break-even value. If A has probability $a$ , B has probability $b$ , B's best continuation has probability $v$ , and A's best continuation has probability $u$ , the two paths tie when $a u = b v$ , so $u = b v / a$ . With $a = 0.60$ , $b = 0.40$ and $v = 0.80$ , the break-even is $u = 0.32 / 0.60 = 0.533\ldots$ , and A's actual continuation is 0.30, well below it. Greedy cannot check this because it has already thrown B away. The condition involves a quantity that arrives after the choice has to be made.

u = \frac{b v}{a} = \frac{0.40 \times 0.80}{0.60} = 0.533\ldots

The gap compounds. A sentence of twenty tokens is a product of twenty conditionals, and a locally best choice at any one of them can lock out a continuation that would have been better two or three tokens later. There is no finite bound on the ratio between the greedy sequence's probability and the best sequence's probability. Stacking two-step failures with slightly different numbers can make the ratio as large as you like.

Why exact search is not available

The obvious repair is to score every possible sequence. With a vocabulary of $K$ tokens and a sequence of $n$ tokens there are $K^n$ sequences. For $K = 50{,}257$ and $n = 20$ , $\log_{10}(K^n) = 20 \log_{10}(50{,}257) \approx 20 \times 4.701 = 94.02$ , so about $10^{94}$ sequences. The observable universe contains about $10^{80}$ atoms. This is not a matter of faster hardware or a better optimiser. Exact search is permanently out of reach.

N = K^n = 50257^{20} \approx 10^{94}

What beam search changes

Beam search keeps $b$ partial sequences rather than one. At each step it extends all $b$ by every token, scores the results, and keeps the best $b$ . In the two-token example, a beam of width two carries both A and B past the first step, so B's 0.80 continuation is scored and the better sequence is found. Beam search therefore recovers some of the lost lookahead. It does not remove pruning: everything outside the $b$ survivors is discarded at every step, permanently. The cost per step is $b \times K$ scores, linear in $b$ rather than exponential in $n$ .

There is a stronger reason not to equate high probability with good text. Exact search for the most probable sequence under a trained translation model often returns the empty sequence. The model assigns the empty sequence the highest probability, and beam search had been preventing that answer from being found. Widening the beam improves the model score and can degrade the text. The highest-probability sequence is not automatically the sentence you want, so a decoder that finds it more thoroughly can produce worse writing.

Greedy decoding and beam search are worth their cost when the distribution is sharp and there is something close to a single right answer: a fixed translation, a transcription, a structured extraction. They stop being adequate when there are many acceptable continuations, because the highest-probability continuation of open-ended prose is typically bland and repetitive. In that regime the right move is not to search harder but to sample, which changes which sequence you get rather than trying to find the single best one. If you only need a reasonable sentence and not the most probable one, greedy can be adequate; the failure is specifically in the claim that it finds the best sentence.

Worth keeping

Greedy decoding maximises each conditional probability separately, which is not the same as maximising their product.
A token that is best at one step can throw away a much better continuation two or three tokens later.
Exact search over all sequences grows as the vocabulary raised to the sequence length, so beam search is an approximation that still discards candidates permanently.

Where this goes next

This question is one step of How a Model Picks Its Next Word, a course that works through its subject from the beginning. The page that teaches this part of it is The Likeliest Word Is Not the Likeliest Sentence, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course