Beam search is a heuristic decoding algorithm that generates text by keeping the k most probable partial sequences, called the beam, at every step and extending each of them, rather than committing to a single choice. In language models it sits between greedy decoding, which keeps only one candidate, and an exhaustive search over every possible output, which is computationally impossible for real vocabularies.
The method searches for an output with a high total log-probability under the model. It became the standard decoder for machine translation, speech recognition and summarization in sequence-to-sequence systems, and it remains relevant in artificial intelligence wherever a single, faithful, high-likelihood answer matters more than variety.
How beam search expands and prunes candidates
Beam search works by expanding every hypothesis in the beam with all possible next tokens, scoring the results and keeping only the best k. The score of a hypothesis is the sum of token log-probabilities, so a sequence is ranked by how likely the model considers the whole prefix, not only its latest token.
- Start with one hypothesis containing the start token and a score of zero.
- For each hypothesis, take the model’s logits for the next position and convert them to log-probabilities.
- Form all extensions, add each token’s log-probability to the parent score and collect the candidates.
- Keep the top k candidates as the new beam; move any hypothesis that emits the end token to a finished list.
- Stop when k finished hypotheses exist, the max tokens limit is reached or no active hypothesis can beat the best finished one.
The algorithm is called heuristic because pruning discards candidates permanently. A sequence that starts with a low-probability token but would have become the best overall is lost once it falls outside the beam, so beam search finds a good approximation, not the guaranteed most probable sequence.
The following table shows how one decoding step changes the beam with a width of 2.
| Candidate | Log-probability | Kept in beam |
|---|---|---|
| The cat sat | -1.9 | Yes, rank 1 |
| The dog sat | -2.3 | Yes, rank 2 |
| The cat ran | -2.8 | No, pruned |
| A cat sat | -3.4 | No, pruned |
Key parameters that shape beam search output
The behavior of beam search depends on a small set of parameters, and the beam width dominates both quality and cost. Compute and memory grow roughly linearly with k, because each hypothesis needs its own forward pass and key-value cache, although batching hides part of the latency.
| Parameter | Typical values | What it controls |
|---|---|---|
| Beam width (k) | 4 to 10 in translation | Breadth of the search and compute cost |
| Length penalty | Exponent of 0.6 to 1.2 | Bias toward shorter or longer outputs |
| No-repeat n-gram size | 2 to 4 tokens | Blocks repeated phrases |
| Early stopping | On or off | When the search ends after finished hypotheses |
| Number of returned sequences | 1 up to k | How many ranked outputs are exposed |
The length penalty matters because every additional token adds a negative log-probability, so raw scores always favor shorter sequences. Normalizing the score by length, or by a length term raised to an exponent, counters this bias. Without it, beam search often ends sentences too early or returns truncated summaries.
Larger beams do not reliably produce better text. In neural machine translation, quality typically peaks at a moderate width and then declines, a pattern often called the beam search curse, because wider searches find short or generic outputs the model scores highly but humans rate poorly.
Beam search compared with other decoding strategies
Beam search is one decoding strategy among several, and the main division is between deterministic search and stochastic sampling. Search methods try to maximize likelihood, while sampling methods such as top-k sampling, top-p sampling and min-p sampling draw tokens at random from a reshaped distribution controlled by temperature.
| Method | Determinism | Typical strength | Typical weakness |
|---|---|---|---|
| Greedy decoding | Deterministic | Fastest, simple | Misses better sequences |
| Beam search | Deterministic | High-likelihood, faithful output | Repetitive, generic text |
| Top-p sampling | Stochastic | Natural, varied prose | Can drift or invent details |
| Diverse beam search | Deterministic | Several distinct candidates | Lower top-1 likelihood |
| Constrained decoding | Either | Guaranteed formats or terms | Extra implementation effort |
Greedy decoding is simply beam search with k equal to 1. Diverse beam search splits the beam into groups and penalizes groups that choose the same tokens, which helps when an application needs several meaningfully different alternatives. Lexically constrained beam search forces chosen words or terminology into the output and is common in professional translation.
When to use beam search in practice
Beam search suits tasks with a narrow set of correct answers, where the input largely determines the output. It is a poor fit for open-ended generation such as dialogue, storytelling or brainstorming, where human readers prefer variety and the most probable text tends to be bland.
| Situation | Recommended choice | Reason |
|---|---|---|
| Machine translation | Beam width 4 to 6 | Output is tightly bound to the source |
| Speech recognition | Beam with a language model | Combines acoustic and text scores |
| Abstractive summarization | Beam with n-gram blocking | Faithfulness with less repetition |
| Chat assistant replies | Top-p sampling | Beam output sounds flat and repetitive |
| Structured output such as JSON | Constrained or greedy decoding | Validity matters more than search |
Modern chat-oriented large language models rarely use beam search by default. Instruction-tuned models already concentrate probability on good continuations, and the extra cost of k parallel hypotheses is hard to justify for long responses. Beam search does reappear in test-time compute methods, where a reasoning model explores several step-by-step solution paths scored by a verifier.
Limitations and common mistakes
The most important limitation is that high probability is not the same as high quality. Language models assign high likelihood to repetitive loops and generic phrases, and beam search, being an optimizer of likelihood, finds them efficiently.
- Repetition loops: the beam converges on phrases that repeat; n-gram blocking or a repetition penalty reduces the problem.
- Low diversity within the beam: the k hypotheses often differ by one token, so returning all of them gives little real choice.
- Empty or short outputs: without a length penalty the end token can win too early.
- Assuming wider is better: raising k from 5 to 50 usually costs ten times more compute for equal or worse quality.
- Mixing with sampling carelessly: combining beams with high temperature removes the predictability that justified beam search.
Beam search also offers no protection against hallucination. A fluent but false statement can carry high likelihood, and beam search will select it as readily as a correct one.
A plain-language summary
A language model writes one word piece at a time. The simplest approach always picks the single best next piece, but an early choice that looks good can lead to a weak sentence later.
Beam search keeps a few of the best drafts open at once. Imagine a hiker who keeps track of the five most promising trails instead of following only the first one that looks good. At each fork, the hiker drops the weakest trails and continues with the best five. In the end, the route with the best overall score wins. This usually gives more accurate and reliable text, although it can sound plain and repetitive.
An example from practice
A localization team at a software company runs a neural translation model to translate user interface strings and help articles from English into German. With greedy decoding, the system sometimes chose an early word that forced an awkward sentence structure, and long German compounds were occasionally cut off.
The engineers switched to beam search with a width of 5, a length penalty exponent of 1.0 and a no-repeat n-gram size of 3. They also used lexically constrained decoding so that approved product terminology always appeared in the output. Decoding time per sentence rose by roughly a factor of three on the same GPU, which was acceptable for batch processing overnight.
In a blind review of several hundred segments, professional translators edited noticeably fewer sentences, and truncated outputs largely disappeared. When the team tested a width of 20, scores did not improve and some translations became shorter and less complete, so they kept the width at 5.