Beam Search: Decoding and Sequence Generation

When a sequence model generates text, it faces a combinatorial explosion. At every time step, the vocabulary might contain 30,000 tokens. After just 10 steps, the number of possible sequences is $30{,}000^{10}$, a number so large it dwarfs the atoms in the observable universe. You obviously cannot evaluate all of them. The decoder must make choices, and those choices determine whether the final output is fluent, accurate, or coherent.

As we covered in the Encoder-Decoder Framework chapter, the decoder operates autoregressively: it consumes its own previous output to predict the next token. And in the Teacher Forcing chapter, we saw that during training the decoder receives ground-truth tokens as input. But at inference time, ground-truth tokens are unavailable. The decoder must choose which token to feed itself next based purely on its probability estimates.

This chapter is about how to make that choice well. We will start with the simplest strategy, show why it systematically fails, and then build up to beam search, the approximate best-first algorithm that has powered machine translation, summarization, and caption generation for years. Along the way, we will examine length normalization, diversity mechanisms, stochastic alternatives, and the practical engineering realities of running beam search at scale. Understanding beam search deeply means understanding how it works, why those design choices exist, and what tradeoffs they reflect.

The most natural strategy is greedy decoding: at each step, pick the highest-probability token and move on.

At time step $t$, the decoder outputs a probability distribution over the vocabulary $V$. Greedy decoding selects:

where:

• $\hat{y}_t$: the token selected at step $t$
• $w$: a candidate token from vocabulary $V$
• $P(w \mid \hat{y}_1, \ldots, \hat{y}_{t-1}, \mathbf{c})$: the model's probability for token $w$ given all previously generated tokens and the context vector $\mathbf{c}$

This is fast and simple. The problem is that it maximizes local probability at each step, but local optima do not stack into a global optimum.

Consider translating the German sentence "Ich habe gestern das Buch gelesen" (I read the book yesterday). Suppose at step 1, the model assigns probability 0.45 to "I" and probability 0.40 to "Yesterday". Greedy decoding commits to "I" immediately. But "Yesterday I read the book" and "I read the book yesterday" are both valid translations with similar quality. If choosing "Yesterday" at step 1 leads to a sequence where all subsequent tokens are extremely high probability, then the full "Yesterday I read the book" sequence might have higher joint probability than "I read the book yesterday". Greedy decoding, having committed to "I" on step 1, will never discover this.

The fundamental issue is that greedy decoding makes irrevocable decisions without considering the downstream consequences. A choice that looks locally optimal may close off globally better paths. The metaphor of hiking comes to mind: if you always walk in the direction that appears to go uphill right now, you will quickly reach a local peak, but you may have missed the real summit by choosing poorly at an early fork in the trail.

There is a deeper pathology here that connects to the exposure bias problem we discussed in the Teacher Forcing chapter. The model was trained on human-generated sequences, where high-probability next tokens also tend to lead to high-probability continuations. But once the model starts generating its own output, errors compound. A greedy choice at step 3 that was slightly suboptimal might, by step 7, have led the model into a distribution that looks very different from anything in training. The model then has no good options and starts producing incoherent text. Greedy decoding is the strategy most vulnerable to this failure mode.

During training, every prefix the model sees is drawn from the training data. The decoder never observes what happens when it makes a mistake because the teacher-forced input always provides the correct previous token. At test time, the model is operating from a distribution it was never explicitly trained to handle: sequences that contain its own errors. Greedy decoding amplifies this mismatch because each step further diverges the model's current state from anything it encountered during training. Beam search partially mitigates this by keeping several paths alive, which provides a form of error recovery: if one hypothesis drifts into a bad region, another hypothesis in the beam may still be in a high-quality region.

The alternative would be to consider all possible sequences. Given a vocabulary of size $|V|$ and a maximum output length of $T$, the total number of sequences is $|V|^T$. For typical NLP settings ($|V| = 30{,}000$, $T = 50$), this is $30{,}000^{50}$, which is completely intractable.

What we need is an algorithm that explores more than one path without requiring exponential computation. Beam search achieves this by committing to a controlled level of exploration, keeping the $k$ best hypotheses at each step and discarding the rest. It does not guarantee finding the globally optimal sequence, but in practice it finds sequences that are significantly better than greedy decoding at a fraction of the cost of exhaustive search.

Beam search is a heuristic that maintains a fixed number of candidate hypotheses at each step. This number is called the beam width, written $k$. Instead of greedily committing to the single best token, beam search tracks the $k$ best partial sequences at every time step, extending each one by one step, and then pruning back to the $k$ best again.

The name "beam" is a spatial metaphor. Imagine the search space as a tree where the root is the start token and each level corresponds to one decoding step. The branches fan out to all $|V|$ possible next tokens. Greedy search follows a single path down this tree. Exhaustive search explores every path. Beam search illuminates $k$ paths at once, like a beam of light of fixed width sweeping across the tree. When a path scores poorly, it falls out of the beam. When a path scores well, it continues.

Beam search operates on log-probabilities rather than raw probabilities. Multiplying many probabilities together quickly underflows to zero in floating-point arithmetic. Log-probabilities transform multiplication into addition, solving the underflow problem while preserving the ordering (since logarithm is monotonically increasing).

The joint probability of a sequence $\mathbf{y} = (y_1, y_2, \ldots, y_T)$ is:

Taking the log:

where:

• $P(\mathbf{y})$: the joint probability of the complete sequence
• $P(y_t \mid y_1, \ldots, y_{t-1}, \mathbf{c})$: the conditional probability of token $y_t$ given previous tokens and context
• $\log P(\mathbf{y})$: the log-probability of the sequence, computed as a sum of per-step log-probabilities

Since log-probabilities are negative (the log of a probability between 0 and 1 is always negative), higher (less negative) log-probabilities indicate better sequences.

The beam search procedure is:

1. Initialize the beam with one hypothesis: the start token with log-probability 0.
2. For each step $t = 1, 2, \ldots, T$: a. For each hypothesis in the beam (up to $k$ hypotheses), run the decoder forward to get a distribution over the next token. b. Generate all $k \times |V|$ candidate extensions (each hypothesis extended by each token). c. Score each candidate: add the new token's log-probability to the hypothesis's current score. d. Prune: keep only the top $k$ candidates by score. These become the new beam. e. If a hypothesis produces the end token (EOS), move it to the "completed" list and remove it from the beam.
3. When the beam is empty or a maximum length is reached, return the completed hypothesis with the highest score (or the best hypothesis remaining in the beam if none completed).

Consider a toy vocabulary of five tokens: {A, B, C, D, EOS} and a beam width of 2.

At step 0, the beam contains one hypothesis: [<START>] with score 0.

The decoder outputs probabilities for the first token:

• A: 0.45
• B: 0.35
• C: 0.15
• D: 0.04
• EOS: 0.01

In log-space: log(0.45) = -0.80, log(0.35) = -1.05, log(0.15) = -1.90, etc.

With beam width 2, we keep A (score -0.80) and B (score -1.05). The beam now contains two hypotheses.

At step 1, each hypothesis is extended by all 5 tokens. We have 10 candidates. Suppose the decoder, after seeing A, assigns probability 0.60 to EOS (score: $-0.80 + \log 0.60 = -0.80 + (-0.51) = -1.31$) and 0.25 to B (score: $-0.80 + (-1.39) = -2.19$). After seeing B, the decoder assigns probability 0.50 to A (score: $-1.05 + (-0.69) = -1.74$) and 0.30 to C (score: $-1.05 + (-1.20) = -2.25$).

The best 2 candidates from all 10 are A-EOS (score -1.31) and B-A (score -1.74). A-EOS is a completed sequence (it produced EOS), so it moves to the completed list. The beam now contains only B-A.

The process continues until either all hypotheses complete or the maximum length is reached. The final answer is the completed sequence with the best score, which here is A-EOS.

Notice what happened: greedy decoding would have generated A at step 1, gotten EOS at step 2, and returned A. But if B-A-EOS had a higher joint probability than A-EOS, beam search with width 2 would have found it, while greedy search would not.

A key property to notice is that the beam at any given step may contain hypotheses of different lengths, all anchored at the same decoding step. The pruning compares raw cumulative log-probabilities across these hypotheses. This is why length normalization matters: a hypothesis that has accumulated more log-probability simply by being shorter is not necessarily better. We will return to this in the length normalization section.

The beam width $k$ is the central hyperparameter of beam search. It controls a direct tradeoff between the quality of the search and the computational cost.

With $k = 1$, beam search reduces exactly to greedy decoding. With $k = |V|^T$, it becomes exhaustive search. In practice, values between 4 and 10 are common for machine translation; some summarization models use 4, and neural machine translation systems often use 5 or 6.

Increasing beam width has diminishing returns in practice. The gain from going from $k = 1$ to $k = 4$ is typically much larger than from $k = 4$ to $k = 10$. Beyond a certain width, the model has already found most of the high-probability paths, and adding more beams just increases computation without improving output quality.

More surprisingly, very large beam widths can degrade output quality on some tasks. Researchers have found that in neural machine translation, BLEU scores sometimes peak around $k = 4$ to $k = 8$ and then decline for larger beams. The reason is related to the model's training distribution: a model trained with maximum likelihood estimation (MLE) learns to assign high probability to sequences that start similarly to the training data. When the beam is large enough to explore low-probability starts, the model encounters territory far from its training distribution, and the output quality degrades. This phenomenon is sometimes called the "beam search curse".

The beam search curse reveals a deep tension in how neural sequence models are trained and how they are evaluated. During training, the model's objective is to assign high probability to the correct next token given the ground-truth prefix. This is a local, next-step objective. At test time, beam search tries to find the globally most probable sequence, which is a different objective. The model was not trained to optimize global sequence probability; it was trained to optimize step-wise conditional probabilities. For well-distributed training data, these two objectives are roughly aligned. But at the edges of the distribution, they diverge, and beam search with a very wide beam will faithfully optimize the wrong objective.

A related concern is that for certain models, specifically language models trained on extremely large corpora, even greedy decoding may produce excellent outputs because the model has learned such a well-calibrated distribution over text. For these models, beam search still helps but the margin over greedy is smaller than for older, weaker models.

Each step of beam search requires $k$ decoder forward passes (one per hypothesis in the beam). With a vocabulary of size $|V|$, you compute $k \times |V|$ scores at each step, then sort to find the top $k$. The total computation is $O(k \cdot T \cdot d)$ where $d$ is the cost of a single decoder forward pass. In practice, the $k$ forward passes are batched together, so the overhead relative to greedy is roughly $k \times$ the cost per step.

The memory overhead is also non-trivial. Each beam hypothesis maintains its own key-value cache (in transformer models, this stores the attention key and value tensors for all previous tokens). With $k$ hypotheses, you hold $k$ separate KV caches simultaneously. For long sequences and large models, this can dominate memory usage. Some systems reduce this overhead by sharing computation across hypotheses when they share a common prefix, a technique called hypothesis sharing or tree-structured KV caching.

Raw log-probability scores are biased against longer sequences. Since every additional token adds a negative log-probability term, longer sequences accumulate more negative contributions and systematically score lower than shorter ones. A model using raw scores will prefer short outputs, sometimes generating incomplete or truncated translations.

To see why this matters, imagine two candidate translations of a German sentence: a five-word English translation and a ten-word English translation. If each token has an average log-probability of -0.7 (a reasonable value for a good translation), the five-word translation scores -3.5 and the ten-word translation scores -7.0. The model will always prefer the five-word translation, even if the ten-word one is linguistically better. The model effectively penalizes every word added to the output.

The length penalty addresses this by normalizing the score by sequence length. One common formulation, introduced by Wu et al. in Google's Neural Machine Translation system, uses:

where the length penalty $\text{lp}(\mathbf{y})$ is:

where:

• $|\mathbf{y}|$: the length of the generated sequence (number of tokens)
• $\alpha$: a hyperparameter controlling how strongly length is penalized, typically set to 0.6 or 0.7
• The constant 5 is a smoothing term that prevents the penalty from being too aggressive for very short sequences

When $\alpha = 0$, the penalty is 1.0 for all lengths, and there is no length normalization (equivalent to raw log-probability). When $\alpha = 1$, the penalty is approximately linear in length, giving nearly equal footing to sequences of different lengths. Values in between, such as 0.6, provide a moderate preference for longer outputs without going all the way to strict length normalization.

Why not simply divide by $|\mathbf{y}|$ directly? The constant 5 in the numerator and denominator prevents very short sequences from being penalized too heavily and provides a smoother transition. Without it, the difference between length 1 and length 2 would be enormous (a factor of 2), while the difference between length 50 and length 51 would be negligible.

The choice of $\alpha$ has practical consequences. A value of $\alpha = 0.6$ was calibrated empirically on production MT systems. For summarization, where you generally want outputs shorter than the source, a lower $\alpha$ (or even $\alpha = 0$) may be more appropriate. For caption generation, where captions should have a natural length, $\alpha$ around 0.5 to 0.8 tends to work well. Tuning $\alpha$ on a validation set is standard practice.

The core mechanics of beam search involve two repeated operations: expansion and pruning.

At each step, every hypothesis in the beam is extended by every possible token. If the beam has $k$ hypotheses and the vocabulary has $|V|$ tokens, expansion produces $k \times |V|$ candidates. For $k = 5$ and $|V| = 30{,}000$, that is 150,000 candidates per step.

In modern implementations, this is done efficiently using batched matrix operations. The $k$ partial sequences are fed through the decoder in a single batch, producing a $k \times |V|$ score matrix. The scores are added to the current hypothesis scores to get candidate scores.

One important subtlety is that the decoder has state. For RNN-based models, the state is the hidden vector; for transformer-based models, the state is the key-value cache. When you batch the $k$ hypotheses together, you need to maintain separate states for each hypothesis. If two hypotheses share a common prefix (which is common early in decoding, when the beam is initialized from a single start token), you can share their cached keys and values to save memory. As the hypotheses diverge, the caches diverge too.

From the $k \times |V|$ candidates, pruning selects the top $k$ by score (accounting for length normalization if used). This is a partial sort, which is more efficient than a full sort of 150,000 elements. Libraries like NumPy and PyTorch provide highly optimized topk operations that perform this partial sort in $O(N \log k)$ time rather than $O(N \log N)$ for a full sort, where $N = k \times |V|$.

When a candidate ends with EOS, it is moved from the beam to the completed hypotheses list. This is important because once a hypothesis completes, it should not continue accumulating log-probability terms. If a completed hypothesis stayed in the beam, its score would keep growing more negative with each additional step (since log-probabilities are negative), even though the sequence is done. Removing completed hypotheses from the beam ensures they are scored at their natural endpoint.

The beam continues with the remaining hypotheses until either the beam is full of EOS-completing sequences, the maximum length is reached, or the beam is empty. In some implementations, the search terminates early when the best completed hypothesis has a higher score than the best remaining hypothesis in the beam, since no future extension can improve upon it.

Several practical considerations modify the basic algorithm. A minimum output length can be enforced by setting the probability of EOS to zero until a minimum length is reached. This prevents degenerate outputs where the model immediately predicts EOS. Without this guard, models that have learned to assign high probability to EOS from short sequences (a training artifact) will produce one- or two-token translations.

Similarly, certain repeated phrases can be suppressed using n-gram blocking: if a bigram or trigram has already appeared in a hypothesis, its continuation tokens are penalized or zeroed out. This is particularly effective for summarization, where models sometimes fall into repetition loops, generating the same phrase multiple times. N-gram blocking was popularized by the FAIRSEQ library and is now a standard option in most sequence generation frameworks.

Another common modification is early stopping: once the first completed hypothesis is produced, the search continues for a fixed number of additional steps (rather than until the beam is exhausted). This balances thoroughness with efficiency in production deployments.

Standard beam search tends to produce hypotheses that are very similar to each other. When the model is confident about the first few tokens, all $k$ beam hypotheses will start with the same token, diverging only in later positions. The beam is homogeneous rather than diverse.

This is a problem in applications that need multiple distinct outputs, such as generating several translation candidates for a human post-editor to choose from, or generating multiple image captions and selecting the best one. When a human reviewer receives five near-identical outputs, the "top-k best" functionality provides little benefit. What is needed is outputs that represent clearly different ways of completing the task.

Diverse beam search (Vijayakumar et al., 2018) addresses this by partitioning the $k$ beams into $G$ groups, each of size $k/G$. Within each group, standard beam search runs. Between groups, a diversity penalty discourages groups from producing similar tokens.

At each step $t$, for group $g$, the score for token $w$ is:

where:

• $\log P(w \mid \cdot)$: the model's log-probability for token $w$
• $\lambda$: the diversity strength hyperparameter
• $\mathcal{D}(w, \mathcal{B}_{1:g-1})$: a diversity penalty measuring how many hypotheses in earlier groups already chose token $w$ at this step

The penalty encourages each group to select tokens that prior groups have not chosen, spreading the search across different parts of the output space. The first group runs without penalty. The second group is penalized for tokens chosen by the first group. The third group is penalized for tokens chosen by the first two, and so on.

With $\lambda = 0$, diverse beam search reduces to standard beam search. Larger values of $\lambda$ force more diversity but may reduce the individual quality of each output.

The grouping mechanism has an intuitive interpretation. Think of each group as a different "opinion" about how the sequence should start. Group 1 follows the most probable path. Group 2 is forced to explore a different starting direction. Group 3 explores a third direction. By the end of decoding, you have $G$ distinct hypotheses, one from each group, that cover a broader range of the output space than $k$ hypotheses from standard beam search.

Another approach to diversity is stochastic beam search, which introduces randomness into the candidate selection step. Instead of deterministically keeping the top $k$ candidates, stochastic beam search samples the $k$ survivors according to their scores, using a Gumbel noise perturbation. Concretely, it adds i.i.d. Gumbel noise $g_i \sim \text{Gumbel}(0, 1)$ to each candidate score before selecting the top $k$:

This corresponds to sampling without replacement from the categorical distribution defined by the candidates' scores. The result is a diverse set of hypotheses while still being biased toward high-scoring candidates. Stochastic beam search interpolates between deterministic beam search (no noise) and pure sampling (infinite noise).

Machine translation is the canonical application of beam search. The encoder reads the source sentence and produces hidden states. The decoder generates the translation token by token, and beam search determines which partial translations to keep exploring. The combination of a strong encoder-decoder model and beam search was the backbone of Google Translate, Microsoft Translator, and virtually every production neural MT system from 2016 onward.

In practice, the beam search procedure is tightly integrated with the encoder-decoder architecture.

At inference time, the encoder runs once to produce the source representations. These are then queried by the decoder's attention mechanism (which we will explore in depth in the Attention Intuition chapter) at every step for every beam hypothesis. Since all beam hypotheses share the same source representation, the encoder computation is not repeated. Only the decoder must be run repeatedly.

The decoder, however, must run $k$ times per step (once per beam hypothesis), or equivalently, the decoder is batched with a batch size of $k$. Each batch element corresponds to a different beam hypothesis. The $k \times |V|$ score matrix is computed in one batched forward pass, exploiting GPU parallelism to keep the overhead manageable.

At the end, the beam contains up to $k$ completed translations (or partial translations if the maximum length was reached). After applying length normalization, the highest-scoring translation is returned as the system output. Some systems also return the top-N translations (n-best list) for downstream reranking: a separate reranker model can score the n-best candidates using additional features (e.g., a language model score, a roundtrip translation score) and select the best one.

The importance of beam search to machine translation is hard to overstate. The first widely deployed neural MT systems achieved competitive quality in part because beam search found translations that greedy decoding missed. The gap between greedy and beam search output quality was large enough that early practitioners considered beam width a first-class hyperparameter alongside learning rate and model size.

Beam width has a measurable impact on BLEU scores in machine translation. The relationship is roughly: wider beams improve BLEU up to a point, then plateau or slightly decline. For English-German translation with a strong transformer model, going from $k = 1$ (greedy) to $k = 4$ typically improves BLEU by 1-2 points. Going from $k = 4$ to $k = 10$ may add another 0.2-0.5 BLEU. The marginal gain diminishes rapidly.

BLEU is a reference-based metric that compares the model's output to human-written reference translations. The fact that beam search improves BLEU does not mean it produces the "best" translation in some objective sense; it means it produces translations more similar to human references. For tasks where the reference distribution is highly multimodal (many equally valid outputs), BLEU may not fully capture quality differences between decoding strategies, and human evaluation often shows a different picture than automatic metrics.

Beam search extends naturally to other seq2seq tasks, though the optimal hyperparameter settings vary. For abstractive summarization, models like BART and PEGASUS typically use beam widths of 4 to 8, with no-repeat-ngram-size set to 3 to prevent repetitive phrases. The length penalty is often set lower than in translation, because summaries should be concise and the model may need less encouragement to generate longer outputs.

For image captioning, beam search with width 3 to 5 is standard. The encoder here is a visual feature extractor (a convolutional network or a vision transformer) rather than a text encoder, but the decoder runs identically to the text case. Beam search ensures that the caption is coherent and grammatically complete rather than trailing off after the first few high-probability words.

For question answering with extractive or generative models, the situation differs. Extractive QA systems that select spans from a passage do not need beam search. Generative QA systems do, but the beam is often narrow (width 2 to 4) because the answer space is more constrained and the model is typically more confident.

Beam search maximizes probability. For some applications, this is exactly what you want: the most likely translation, the most probable answer. But for creative text generation, the most probable text is often the least interesting. When a language model assigns high probability to the same few words repeatedly, the output becomes repetitive and bland.

Consider generating a short story. The highest-probability continuation of "She walked into the dark room and saw" might be "a light" because those two words appear frequently in the training data after similar contexts. But "a light" is boring. The story might be much more interesting if the model picked a lower-probability but more unexpected continuation, like "her reflection looking back at her from a shattered mirror". Maximizing probability produces the average, the statistically most typical continuation. Creative writing, by definition, should not be average.

Sampling-based methods introduce stochasticity to break this pattern.

Top-k sampling restricts the sampling pool to the $k$ most probable tokens at each step, then samples from that restricted distribution:

where:

• $P(w)$: the model's original probability for token $w$
• $\text{Top-}k$: the set of the $k$ tokens with highest probability
• $P'(w)$: the renormalized probability used for sampling

The problem with top-k is that the appropriate value of $k$ varies with context. If the model is very confident (the top-1 probability is 0.99), then sampling from the top-50 includes many very unlikely tokens and can produce incoherent output. If the model is very uncertain (probabilities are nearly uniform), then restricting to top-5 throws away most of the valid continuations.

Nucleus sampling (Holtzman et al., 2020) addresses this by sampling from the smallest set of tokens whose cumulative probability exceeds a threshold $p$:

where:

• $V_p$: the nucleus, the minimal set of tokens covering cumulative probability mass at least $p$
• $V'$: a candidate subset of the vocabulary, sorted by descending probability
• $p$: the probability threshold, typically 0.9 or 0.95

The set is constructed by sorting all tokens in descending probability order and including tokens one by one until the running sum of probabilities reaches $p$.

Tokens outside the nucleus receive zero probability. Those inside are renormalized.

The key advantage is adaptivity. When the model is confident, the nucleus is small (a few tokens cover 0.9 of the probability mass). When the model is uncertain, the nucleus is large (many tokens are needed to accumulate 0.9). The sampling pool automatically adjusts to the local probability distribution.

Nucleus sampling is the default choice for open-ended text generation tasks: story writing, dialogue systems, creative applications. Beam search is better suited for constrained generation tasks where there is a specific correct answer: translation, summarization, question answering. The choice between them reflects a deeper question about what "good output" means for a given task.

Temperature is a parameter $\tau$ that reshapes the probability distribution before sampling:

where:

• $\tau$: the temperature parameter
• $P(w)^{1/\tau}$: the unnormalized probability with temperature scaling applied

For $\tau < 1$, the distribution sharpens: high-probability tokens become even more likely, low-probability tokens shrink. This makes output more focused and repetitive. For $\tau > 1$, the distribution flattens: probabilities become more uniform, and sampling becomes more exploratory and unpredictable. At $\tau = 1$, sampling is from the unmodified distribution. Temperature is often combined with top-k or nucleus sampling.

In modern large language model APIs, you typically encounter all three of these controls: temperature, top-k, and top-p. A common practical recipe for creative generation is temperature around 0.8 to 1.0 combined with top-p around 0.9. For factual generation, temperature near 0.2 to 0.5 with greedy or small beam search tends to produce more reliable outputs.

A more recent alternative, contrastive decoding (Li et al., 2022), generates text by contrasting the outputs of a strong model and a weak model. At each step, the score for a token is computed as the log-probability difference between the expert (strong) model and the amateur (weak) model:

The intuition is that tokens that are highly probable under both models are likely to be generic, high-frequency words that appear frequently in training data regardless of context. Tokens that are much more probable under the expert than the amateur are the ones that reflect the expert's superior understanding of the context. By amplifying this contrast, contrastive decoding produces output that is more informative and contextually appropriate, avoiding the repetition and generic phrasing that characterize maximum-probability decoding.

Contrastive decoding has shown promising results on long-form question answering and knowledge-intensive tasks, where avoiding generic outputs is especially important.

A clean beam search implementation uses a priority queue (min-heap) to efficiently maintain the top-k hypotheses. The data structures involved are:

• A hypothesis object containing the current token sequence and the cumulative log-probability.
• A priority queue indexed by negative log-probability (since Python's heapq is a min-heap, we negate scores so the highest-scoring hypotheses are at the top when popped).
• A completed list for hypotheses that have produced EOS.

Let's implement beam search from scratch on a toy language model.

With no normalization ($\alpha = 0$), the algorithm often prefers shorter sequences because each additional token adds a negative contribution. With $\alpha = 0.6$, sequences of moderate length are rewarded, and the top hypotheses tend to be longer and more complete.

The key parameters for beam search are:

• beam_width (k): Number of hypotheses maintained at each step. Larger values explore more of the search space but increase computation by a factor of $k$. Common values: 4-6 for translation, 1-4 for large language model inference.
• alpha (length penalty): Controls how strongly length is penalized. 0 means no normalization; 1 means full normalization; 0.6 is a common practical default.
• max_length: Maximum output length. Usually set to 1.5 to 2 times the source length for translation.
• min_length: Minimum output length. Set to prevent degenerate EOS predictions.
• no_repeat_ngram_size: Block repeated n-grams to reduce repetition. Setting this to 3 or 4 prevents the model from repeating trigrams or 4-grams.

Let's build a visualization of the beam search tree to see how hypotheses are expanded and pruned.

The visualization shows how each decoding strategy selects from the probability distribution. Beam search takes only the peak. Top-k always samples from the top 5, even if those tokens span a wide range of probabilities. Nucleus sampling adapts: here, with a peaked distribution, only 3 tokens are needed to cover 90% of the mass, so the nucleus is smaller than top-k.

The adoption of large language models (LLMs) trained on massive text corpora has shifted the dominant decoding paradigm in some applications. GPT-style models are typically used with sampling-based methods rather than beam search for open-ended generation, but beam search remains relevant for constrained tasks even with LLMs.

Large language models trained on diverse, massive datasets have well-calibrated distributions over text. At any given position, there are often many plausible continuations, and the model's probability is spread across a wide range of good options. In this setting, deterministically selecting the maximum-probability continuation may not produce the most natural or interesting text. Sampling from the distribution, possibly with temperature or nucleus constraints, tends to produce outputs that feel more human-like.

There is also a practical consideration: when you use an LLM as a general-purpose assistant, you often want different outputs for the same prompt on different runs. Deterministic decoding (beam search or greedy) always produces the same output for the same input and the same model weights. Stochastic sampling introduces the variability that makes repeated queries useful.

Despite the prevalence of sampling for LLMs, beam search remains the standard choice in several LLM-driven scenarios. When an LLM is used to perform a constrained task such as structured data extraction, code generation for a specific schema, or translation, beam search with a moderate beam width often outperforms sampling methods because the correct output is more narrowly defined.

For machine translation with transformer-based LLMs (such as NLLB or M2M-100), beam search is still the default inference method. The task has a right answer (the correct translation), and the correctness criteria are well-defined enough that maximizing probability is beneficial.

Code generation models like Codex or Code Llama also benefit from beam search when the task involves generating syntactically correct code for a test case. The constraints on code (it must parse, compile, and produce correct output) make the search space more restricted, and beam search explores that space more systematically than sampling.

One of the major practical challenges with beam search for large transformer models is that decoding is inherently sequential: each step requires a forward pass through the full model, and you cannot parallelize across steps because each step depends on the output of the previous one. This is in contrast to training, where all tokens in a sequence can be processed in parallel using the attention mask.

Speculative decoding (Leviathan et al., 2023; Chen et al., 2023) addresses this bottleneck by using a small draft model to propose multiple tokens at once, then using the full model to verify the proposed tokens in a single batched forward pass. If the draft model's proposals are accepted (according to the full model's distribution), multiple tokens are committed simultaneously. If a proposal is rejected, the algorithm falls back to sampling from the full model at the rejection point.

The key insight is that verifying a sequence of $k$ tokens with the large model takes roughly the same compute as generating a single token (because the transformer can process all $k$ tokens in parallel). So if the draft model's acceptance rate is high, you generate multiple tokens per large-model forward pass, achieving significant speedups without changing the output distribution.

Speculative decoding is not a new decoding algorithm in the beam search sense; it is a computational acceleration technique that produces the same distribution over outputs as standard sampling from the large model. But it highlights how the sequential nature of autoregressive decoding is a practical bottleneck, and how the field is actively working to overcome it.

Deploying beam search in production requires attention to several engineering details that are easy to overlook when studying the algorithm in isolation.

In training, sequences are batched together to exploit parallelism. At inference time, beam search complicates batching in two ways. First, each input sequence in a batch generates $k$ beam hypotheses, so the effective batch size grows from $B$ to $B \times k$. Second, different sequences in a batch may complete at different steps, leading to variable-length computation. Libraries like Hugging Face Transformers handle this through careful batch management, padding finished beams with EOS tokens so they can remain in the batch without contributing to score updates.

Transformer models use key-value caches to avoid recomputing attention keys and values for all previous tokens at each decoding step. For beam search with $k$ beams, you maintain $k$ separate KV caches. When the beam is pruned, the surviving hypotheses may come from different parent hypotheses; the corresponding KV caches must be reindexed (not just truncated). This reindexing step is a nontrivial engineering concern in high-performance implementations.

Some frameworks implement "beam search with shared KV caches" where all $k$ hypotheses share prefixes of the KV cache and only diverge where the hypotheses diverge. This is especially effective early in decoding when all hypotheses have the same start token. As the beams diverge, the shared portion shrinks, but the early savings can still be significant.

For large models with long context windows, the memory required to maintain $k$ KV caches can be substantial. A model with 32 layers, 32 attention heads, and a head dimension of 128, decoding a sequence of length 512 with beam width $k = 5$, needs to store:

of KV cache (2 for keys and values, in float16). For very large models or very long sequences, this memory constraint can be the binding factor limiting beam width in practice.

In production MT systems, beam search is often used to generate an n-best list of candidate translations rather than a single output. A second-stage reranker, which may be a separate model or a heuristic scoring function, then selects the best candidate from the list. The reranker has access to the full candidate sequence and can apply features that are expensive to compute during decoding (e.g., roundtrip translation, language model score, length-to-source-ratio check). This two-stage pipeline often outperforms single-stage beam search with a wider beam, because the reranker can apply richer features than the sequence probability alone.

Beam search has served the NLP community well, but it carries several important limitations.

The most fundamental is the label bias problem. At each step, beam search scores sequences using a locally normalized probability (the decoder outputs a softmax, which sums to 1 over all next tokens). This means a model can "hide" probability by distributing it among many similar continuations, making it harder for beam search to discover sequences that diverge significantly from common patterns. Maximum Entropy Markov Models (MEMMs) have a well-known variant of this problem, and neural seq2seq models are not fully immune.

A second limitation is that beam search finds the maximum a posteriori (MAP) sequence under the model. For tasks where the model has a sharp, well-peaked distribution (like factual question answering), MAP decoding gives the right answer. But for tasks where many good outputs exist (like open-ended dialogue or creative writing), MAP decoding returns the one sequence the model assigns highest probability to, which tends to be generic and safe rather than interesting and varied. The sampling methods discussed above address this but introduce their own challenges.

A third limitation is computational: beam search is sequential. Each step depends on the previous one because the decoder must consume its own output. This makes it incompatible with the kind of fully parallelized computation that made transformers so efficient during training. Speculative decoding and parallel decoding methods attempt to address this, but they require significant engineering and approximate the beam search guarantee rather than preserving it exactly.

Finally, beam search is sensitive to the model's calibration. If the model systematically assigns incorrect probabilities (overconfident or underconfident), beam search faithfully optimizes those incorrect probabilities. A poorly calibrated model with wider beams may produce confidently wrong outputs. Sampling from a well-calibrated model might outperform beam search from a miscalibrated one.

These limitations are not just academic concerns. The NLP community has moved toward sampling-based decoding for many applications partly because beam search's commitment to maximum probability produces outputs that, while internally coherent, feel stilted and over-optimized. The "degenerate text" problem, where very long beam-search outputs fall into repetition, was a major practical problem in early neural MT systems. Solutions like no-repeat-ngram blocking were developed specifically because the MAP sequence under many models includes repeated n-grams, which are penalized by beam search's length normalization but not eliminated.

Despite these limitations, beam search remains a foundational algorithm. Understanding its mechanics is essential for understanding why models behave the way they do at inference time, and for diagnosing problems when output quality is poor. Every practitioner who works with sequence generation models will encounter beam search in some form, whether tuning the beam width for a translation task, debugging a repetition problem in a summarization model, or choosing between beam search and sampling for a generative application.

Beam search sits between the extremes of greedy decoding (single path, no backtracking) and exhaustive search (all paths, computationally infeasible). By maintaining a beam of $k$ candidate hypotheses and pruning at each step, it explores the probability space efficiently and usually finds significantly better sequences than greedy decoding.

The key ideas to take away are:

• Greedy decoding fails because locally optimal choices lead to globally suboptimal sequences. Irrevocable step-wise decisions close off globally better paths.
• Beam search maintains $k$ hypotheses, expands each by the full vocabulary, and keeps the top $k$ at every step, trading compute for a more thorough search.
• Beam width trades quality for compute; values of 4-6 work well for translation, larger values show diminishing returns and can even hurt quality due to the beam search curse.
• Length normalization corrects the score bias against longer sequences using the penalty $\text{lp}(y) = (5 + |y|)^\alpha / 6^\alpha$, with $\alpha = 0.6$ being a common default.
• Diverse beam search partitions the beam into groups with inter-group diversity penalties to produce varied outputs, useful when multiple distinct hypotheses are needed.
• Nucleus sampling is the preferred alternative for creative generation, adapting the sampling pool to the local probability distribution and producing more natural, varied text.
• Large language models often use sampling rather than beam search for open-ended generation, but beam search remains the standard for constrained tasks like translation and structured generation.
• Engineering details such as KV cache management, batched inference, and n-best reranking matter significantly in production deployment and often determine whether beam search is practical at a given scale.

In the next chapter, we will explore the Attention Intuition that allows seq2seq models to align source and target sequences more effectively, moving away from the fixed-size context vector bottleneck that constrains the encoder-decoder models we have studied so far.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about beam search and sequence decoding strategies.