Beam search: keep a path that greedy decoding would discard

Beam search keeps several high-scoring partial sequences instead of committing to one token choice. Each step expands the retained paths and prunes the candidates back to the beam width.

Sequence scores commonly sum token log probabilities. Real implementations also handle completed sequences and may normalize for length.

A locally worse start can win

This fixed two-step model illustrates the distinction without downloading weights. All paths end after two tokens, so their lengths are equal.

from math import log

transitions = {
    (): {"A": 0.6, "B": 0.4},
    ("A",): {"x": 0.5, "y": 0.5},
    ("B",): {"x": 0.99, "y": 0.01},
}
def search(width):
    beam = [((), 0.)]
    for _ in range(2):
        candidates = [(path + (token,), score + log(probability))
                      for path, score in beam
                      for token, probability in transitions[path].items()]
        beam = sorted(candidates, key=lambda item: item[1], reverse=True)[:width]
    return beam[0]

greedy = search(1)
wider = search(2)

Width one chooses A first and reaches probability 0.30. Width two retains B and discovers the B–x path with probability 0.396. Keeping alternatives avoids this particular greedy mistake.

A finite beam still discards paths and does not guarantee a globally optimal result. Moreover, the most likely sequence is not necessarily the most interesting or useful text. Beam search is a search policy over model scores, not a correction to the model's knowledge.