Subscribe
AI
6 min read

What Is Beam Search? The Decoding Trick Language Models Learned and Then Mostly Abandoned

Every large language model ends the same way: it predicts a probability for the next token, picks one, and repeats. But between the model and the sentence sits a decision most explainers skip. Which token you pick, and how many candidates you keep while picking, is a search problem, and for a decade the default answer was an algorithm called beam search. Modern chatbots have mostly dropped it. Understanding why is a fast tour of how decoding works, how it broke, and where it quietly survives.

What Is Beam Search? The Decoding Trick Language Models Learned and Then Mostly Abandoned

Every large language model ends the same way: it predicts a probability for the next token, picks one, and repeats. But between the model and the sentence sits a decision most explainers skip. Which token you pick, and how many candidates you keep while picking, is a search problem, and for a decade the default answer was an algorithm called beam search. Modern chatbots have mostly dropped it. Understanding why is a fast tour of how decoding works, how it broke, and where it quietly survives.

The problem decoding actually solves

A trained language model does not give you an answer. It gives you a distribution over its vocabulary for the next token, conditioned on everything so far. Producing a whole sentence means choosing a sequence, and the principled way to frame that is: find the sequence the model assigns the highest total probability.

That principled goal is unreachable in practice. The number of candidate sequences grows exponentially with length, so even a modest model defines a search space far too large to enumerate. Every decoding strategy is a shortcut through that space. The two classic ones mark the extremes.

Greedy decoding takes the shortcut at every step: pick the single most likely next token and never look back. It is fast, one model call per token, and it can miss. The most likely next word is not always part of the most likely sentence. The model might say a slightly less probable word now to earn a much more probable continuation three words later, and greedy decoding never considers that trade.

Exhaustive search is the other extreme: evaluate everything. It finds the true maximum-probability sequence, and on any real model it takes until the heat death of the universe.

How beam search works

Greedy, beam, and exhaustive search compared

Beam search is the compromise that ran a decade of sequence models. You pick a beam width, usually written k. At every step you keep exactly k partial sentences alive instead of one. Each of the k candidates proposes its k most likely extensions, you score all of the resulting k times vocabulary possibilities, and you prune back down to the overall best k. Repeat until the candidates stop. Return the highest-scoring survivor.

The formal picture is simple enough that recent papers still restate it this way: beam search generalizes greedy decoding by keeping the top-k tokens at each step, while exhaustive search has no width limit at all (On the Depth between Beam Search and Exhaustive Search). The price is linear in k: you pay roughly k times the model calls of greedy decoding, and in a transformer every live beam needs its own key-value cache, so memory and compute scale with the beam width too (Efficient Beam Search for LLMs Using Trie-Based Decoding).

The idea is older than neural networks. It comes from 1970s speech recognition, and the standard citation is Reddy's 1977 review of speech recognition by machine, as noted in the EMNLP 2021 survey on decoding beyond beam search. When neural machine translation took over in the mid-2010s, beam search came along. Google's 2016 GNMT paper, the system that brought neural translation into production, used a beam search decoder with length normalization and a coverage penalty, and that recipe defined the field: beam search plus small corrections, everywhere.

The curse: more search, worse text

Beam search pruning at each step

Then researchers ran the obvious experiment. If beam search is a better approximation of the best sequence, a bigger beam should be better, right?

It is not. Widening the beam past a small range, typically four to ten, makes output quality go down. This got a name, the beam search curse, and Koehn and Knowles listed it in 2017 as one of six central challenges in machine translation. The 2018 study that followed up on it found larger beams produce shorter, more repetitive translations, because wider search finds the end-of-sentence token earlier: it is often cheap to stop.

The anomalies got weirder. Stahlberg and Byrne reported in 2019 that if you actually find the maximum-probability sequence, exact search returns the empty string in as much as half of translations (numbers discussed in the Meister et al. EMNLP 2020 paper and this lecture summary from Charles University). The single most likely output of a trained translator is sometimes nothing at all. And when beam search does return text with a large beam, the text degenerates: loops, repetitions, hypotheses that begin with a low-probability token the model never should have kept. Cohen and Beck's ICML 2019 analysis traced this to large search discrepancies: big beams entertain early tokens with terrible scores that later recover, and those recovered sequences are the ones that read like a broken record.

So what is beam search actually doing?

The resolution that reframed the whole debate is this: beam search works despite being a bad approximation, not because it is a good one. The Meister, Cotterell and Vieira paper titled the problem perfectly: if beam search is the answer, what was the question? Their finding is that a small beam hides an inductive bias. By pruning aggressively and keeping hypotheses similar in length and structure, beam search quietly applies a length penalty and favors uniformly informative sentences, properties the raw maximum-probability objective does not express at all. The model's own best guess is bad text. Beam search is a slightly worse guess, filtered through a human-sounding constraint, and wins.

That reading explains why the fix to the curse was never a bigger beam. Once you see the pruning as the real product, you can replace it with explicit penalties, reranking, or better objectives, which is exactly what the field did.

Why your chatbot does not use it

Three reasons, all structural.

Cost scales with the beam. Chat models produce long outputs, and each extra beam duplicates decode compute and KV cache memory, as the trie-based beam search work spells out. For thousand-token answers, k times everything is a hard sell, and the sampling-based alternatives need no extra passes at all.

The jobs changed. Beam search was built for translation and captioning, short outputs with one correct shape. Open-ended dialogue and code have no maximum-probability sentence worth hunting for; diversity is a feature. Temperature and top-p sampling, which we covered separately, fit that goal better, and where a provider does want many candidates, sampling n times and reranking beats one shared beam (see the vLLM beam search RFC discussion).

The defaults moved. Hugging Face Transformers' generate() runs with num_beams=1, meaning greedy or sampling, unless you explicitly ask for beams (generation docs). vLLM, the serving engine most open models run on, deprecated use_beam_search as a sampling parameter in version 0.6.3 (issue) and in 2023 proposed dropping beam support outright to simplify the engine (RFC); community pushback kept a separate beam path alive, but it stopped being first-class in the V1 rewrite (discussion). No major chat API exposes a beam width anymore.

Where it survives

Beam search never died, it just got specialized. Speech recognition still runs it on transducer models, with active work on making it fast enough for production (arXiv 2506.00185). Machine translation still uses n-best lists plus reranking, the descendant of the GNMT recipe. And reasoning models have brought search back by another door: pruning low-quality reasoning paths early is exactly what a beam does, and 2025 work showed beam-width-style search raising Llama 3.1 8B accuracy from 0.23 under top-sampling to 0.40 on math tasks by merging shared prefixes into a trie (arXiv 2502.00085). Newer theory work argues beam search over reasoning paths scales better at test time than best-of-N sampling, because the error term grows polynomially with answer length instead of exponentially (arXiv 2609.38672).

The lesson generalizes past one algorithm. The model's probability table is not the product. What you do at decoding time, whether you search, sample, or prune, changes what the model is, and the history of beam search is a decade of finding that out the hard way.

Sources

AILLMexplainer