Learn · Beginner

Beam search: keeping several drafts alive to find a likelier sentence

Beam search is a decoding method that keeps a fixed number of partial answers alive at every step, extends each one, and keeps only the highest-scoring few, so a language model can find a sentence that is more probable overall than the one it gets by grabbing the single likeliest word each time. It became the standard way to decode neural machine translation and still sits behind the num_beams setting in Hugging Face's generation library. Its most useful lesson is a strange one: finding the most probable sentence is often not what you actually want.

The likeliest word is not the likeliest sentence

A language model writes one token at a time, and for each position it produces odds over every possible next token. The simplest way to turn those odds into text is greedy decoding: always take the top choice. The lesson on how an AI picks its next word covers greedy decoding and its dice-rolling alternatives.

Greedy decoding has a blind spot. The probability of a whole sentence is the product of the probabilities of its words, so a word that looks best now can lead into a dead end. Here is an illustrative example. Suppose after "The meeting" the model gives "was" 50% and "ran" 40%. Greedy takes "was." But if every continuation after "was" is weak, say 30% at most, while "ran" is almost always followed by "late" at 90%, then "ran late" (0.4 x 0.9 = 0.36) beats "was" plus its best follower (0.5 x 0.3 = 0.15). Greedy never looks back, so it never finds that out.

Picture a hiker at a series of forks who always takes whichever path looks easiest for the next ten metres. Beam search sends a few scouts down the most promising paths at each fork, and at every junction it keeps only the scouts who have made the best progress so far.

How it works

In their landmark 2014 paper Sequence to Sequence Learning with Neural Networks, Ilya Sutskever, Oriol Vinyals and Quoc Le at Google describe the decoder plainly: it "maintains a small number B of partial hypotheses, where a partial hypothesis is a prefix of some translation."

The loop is simple:

1. Start with one empty hypothesis. 2. Extend every hypothesis in the beam with every possible next token. 3. Score each extension by adding up the log-probabilities of its tokens, which is the same as multiplying the probabilities. 4. Keep only the top B. When a hypothesis produces the end-of-sequence token, move it to the finished pile. 5. Repeat until enough hypotheses have finished, then return the best-scoring one.

B is the beam width. A beam width of 1 is exactly greedy decoding. Small beams go a long way: Sutskever's team found their system "performs well even with a beam size of 1, and a beam of size 2 provides most of the benefits of beam search." The cost grows with the beam, because every beam needs its own slice of the model's working memory, the KV cache.

The short-answer bias, and the length fix

Multiplying probabilities that are all less than one means every extra word drags the score down. Left alone, beam search prefers to stop early. Google's 2016 neural machine translation paper put it bluntly: "Without some form of length-normalization regular beam search will favor shorter results over longer ones on average." Google's system divided each score by a function of length, added a coverage penalty to push the model to translate the whole input, and reported that it "typically" kept 8 to 12 hypotheses, but that using 4 or 2 had "only slight negative effects."

Better search, worse answers

The deepest surprise came when researchers searched harder. In 2019 Felix Stahlberg and Bill Byrne at Cambridge built an exact search that is guaranteed to find the single highest-scoring translation, in On NMT Search Errors and Model Errors: Cat Got Your Tongue?. "For more than 50% of the sentences, the model in fact assigns its global best score to the empty translation." Beam search had been producing good translations precisely because it failed to find the model's true favourite. The authors concluded that translation systems need "just the right amount of beam search errors."

Clara Meister, Tim Vieira and Ryan Cotterell offered an explanation in If beam search is the answer, what was the question?: beam search quietly favours text that spreads information evenly across words, a property people also prefer, so its imperfection acts as a useful bias.

Why open-ended writing mostly samples instead

For translation, speech recognition and summarisation there is roughly one right answer, and beam search does well. Open-ended writing is different. Ari Holtzman and colleagues showed in The Curious Case of Neural Text Degeneration that using likelihood as the decoding goal "leads to text that is bland and strangely repetitive." Beam search is a likelihood maximiser, so it inherits the problem. Its candidates also tend to be near-copies: Diverse Beam Search was proposed because standard beams produce "sequences that differ only slightly from each other."

The idea did not die. Keeping several partial solutions and pruning by score is the skeleton of many test-time compute methods, where the units are reasoning steps instead of words and a process reward model supplies the score. If you need exact formats, beam search also pairs naturally with constrained decoding.

The takeaway

Beam search is a better search over a model's probabilities, and that is exactly why it teaches caution. A search can only find what the model's scores reward. When the scores favour short, safe or bland output, a more thorough search delivers more of it.

Ground Truth. (2026, September 12). Beam search: keeping several drafts alive to find a likelier sentence. Ground Truth. https://groundtruth.day/learn/beam-search.html

@misc{groundtruth:beam-search,
  title  = {Beam search: keeping several drafts alive to find a likelier sentence},
  author = {{Ground Truth}},
  year   = {2026},
  month  = {sep},
  url    = {https://groundtruth.day/learn/beam-search.html}
}

Topics: decoding · beam-search · inference · machine-translation · fundamentals