Beam search is a heuristic decoding algorithm that looks for a probable whole sequence in autoregressive models, rather than merely the most probable next token. The motivation is the short-sightedness of greedy decoding: the token that looks best at a given step may lead into a dead end from which every continuation only worsens the overall probability. Beam search therefore keeps several of the best partial variants at once – their number is the beam width – weighs the possible continuations of each at every step, and again retains only the best k of the resulting set according to the sum of log probabilities. Because longer sequences necessarily receive lower scores, length normalization is applied. The method is standard for tasks with one correct answer where fidelity matters – machine translation, speech transcription, summarization. For open-ended generation, by contrast, it proved unsuitable: the most probable text tends to be dull, generic and prone to repetition, because human speech is not an exercise in maximizing probability. There, sampling with temperature and nucleus sampling is used instead.
It is like planning a game of chess against a greedy opponent. The greedy player grabs the highest-value piece available on every move and is checkmated two moves later. The prudent player holds the three most promising lines in mind at once, extends each by one move, then again picks the best three out of nine. He does not calculate the whole game – nobody could – but he does not walk into a trap on the very first move either. For translation that is ideal. For telling a story, however, the prudent player writes desperately lifeless prose, because the “most probable” sentence is usually a cliche.