In plain words
A language model writes one word at a time. At each step it has a list of possible next words, each with a chance. The simplest plan is to always take the top word. That is called greedy search.
The catch: a word that looks best now can lead somewhere weak. A slightly worse word might open the way to a much better sentence.
Beam search hedges. Instead of one draft, it keeps the few best drafts so far, say two or five, and grows each by one word. It scores every grown draft, keeps the best few again, and repeats. At the end it returns the draft with the best overall score.
It works well when there is roughly one right answer, like translating a sentence. For chat and stories, most apps pick words with some randomness instead.
Everyday example
Booking a train trip with one change
You need to get from Pune to Jaipur with a change of train. Grabbing the fastest first train feels smart, until you see its connection leaves six hours later. So you shortlist the two best first legs, check the onward trains from each, and only then choose. The shortlist size is the beam width. The best trip is judged as a whole, not by its first leg.
Where the example breaks: You can see every timetable. Beam search only ever sees its shortlist, so it can still miss the best answer if that answer starts with a word it dropped early.
How it actually works
Beam search is a decoding method: a rule for turning the model's next-word chances into finished text. It changes how the model picks, not what the model knows.
Score each next token
At every step the model gives a probability to every token it could write next. That comes from next-token prediction over its logits.
Keep the top B drafts
B is the beam width. Each kept draft is extended by its likely next tokens, and every new draft is scored by multiplying the chances along its path (in practice, adding their logs). Only the best B survive to the next step.
Stop and choose
A draft finishes when it writes an end-of-text token or hits a length limit. The highest scoring finished draft wins. Systems often divide the score by length, because every extra word lowers a product of chances and would otherwise favour short answers.
Why chatbots mostly skip it
Research on story writing found beam search tends to give short, generic and repetitive text. Human writing is rarely the single most probable sequence. Open-ended apps usually sample instead, using settings like temperature.
- Greedy search
- The same idea with a beam width of 1
- Classic use
- Google's 2014 sequence-to-sequence translation paper found a beam of 2 gave most of the benefit
- Common today in
- Translation and summarising, where output length is fairly predictable
- Known weakness
- Repeats phrases. Rules that block repeated word pairs help, but can hurt (a story about New York could mention it only once)
Questions people ask
What is the difference between greedy search and beam search?
Greedy search keeps only one draft and always adds the single most likely next word. Beam search keeps several drafts at once and compares them as they grow, so it can recover from a first word that looked best but led nowhere good.
What does beam width mean?
It is how many drafts are kept at each step. A width of 1 is greedy search. Wider beams explore more and cost more computing, and past a small number the gains often fade.
Does ChatGPT use beam search?
Chat apps do not publish every setting, but open-ended chat generally samples words with some randomness rather than using beam search, because beam search tends to sound flat and repetitive. Beam search is more common in translation and summarising.
Does beam search always find the best answer?
No. It only explores its shortlist, so it is not guaranteed to find the most likely sentence. It can even end up with a less likely sentence than greedy search, if the greedy path drops off the shortlist early.
Was this clear?
1 is confusing, 5 is crystal clear. One tap, no account needed.
Spotted something wrong, or know a better example? Suggest a change
Further reading
- How to generate text: using different decoding methods for language generation with TransformersHugging Face, 2020
- Sequence to Sequence Learning with Neural Networks (Sutskever, Vinyals, Le)arXiv, 2014
- Hierarchical Neural Story Generation (Fan, Lewis, Dauphin)arXiv, 2018
- The Curious Case of Neural Text Degeneration (Holtzman et al.)arXiv, 2019