Beam Search Explained: How Beam Width Affects Generation

Beam Search is an improved decoding method over greedy search. During the prediction stage, it retains multiple high-probability candidate sequences according to the beam width, making it suitable for understanding machine translation generation, how beam width affects prediction, and the limitations of pruning.

Beam Search is a search method used for sequence prediction or the decoding stage, and it is usually regarded as an improved version of greedy search. It does not change the model training process, nor does it require retraining the model. Instead, during prediction, it determines how to select a more promising output from multiple candidate sequences.

Intuitively, greedy search is like taking only the path that currently looks best at each step; Beam Search keeps several paths that look relatively good at the same time and continues comparing them until generation ends.

In sequence generation tasks such as machine translation, a model usually needs to generate the next word or token step by step. The core idea of Beam Search is: do not compress the search space into a single candidate too early; instead, retain a group of high-probability candidate sequences at each time step.

Key point: Beam Search is a decoding strategy in the prediction stage, not a training algorithm. It affects how candidates are selected during generation, not the model parameters themselves.

Both greedy search and Beam Search can be used for decoding during the prediction stage, but they retain candidates in different ways. Greedy search usually keeps only one currently optimal choice at each step, while Beam Search retains multiple candidate paths according to the beam width.

Comparison dimensionGreedy searchBeam Search
Candidates retained at each stepUsually retains only the one candidate with the highest current probabilityRetains multiple candidates with relatively high probabilities
Dependence on early choicesVery strong; once an early step is chosen incorrectly, it is hard to correctRelatively reduces the impact of single-step selection errors
Whether all sequences are exhaustively enumeratedNoNo
Whether model parameters are changedNoNo
Usage stagePrediction or decoding stagePrediction or decoding stage

The advantage of Beam Search is that it does not lock onto a single path too early the way greedy search does, so it is more robust in some sequence generation tasks. However, it is still not exhaustive search: a fixed beam width will prune away some candidates, and pruned sequences will not automatically return to the candidate set in later steps.

How Does Beam Width Determine the Number of Candidate Sequences?

Beam width is the key hyperparameter of Beam Search. It indicates how many candidate sequences are retained at each time step. When the beam width is set to k, Beam Search selects the k candidates with the largest conditional probabilities at the first time step.

After that, each candidate continues to expand into new possible results, and the search process then retains the k candidates with higher probabilities or scores. In this way, Beam Search makes a trade-off between “keeping multiple possible paths” and “preventing the search space from expanding without limit.”

Beam width settingMeaningImpact on the search process
k = 1Retains only one candidate at each stepClose to the greedy approach of selecting only the current optimum at each step
Smaller kRetains a small number of candidatesThe search space is more restricted, and the impact of early pruning is more obvious
Larger kRetains more candidatesMore candidate paths can be observed, but it still does not exhaustively enumerate all possible sequences

Beam width affects prediction results, so it is often used as an important parameter for observing generation quality. It is important to note that changes in beam width may change the output, but this should not be simply understood as meaning that a larger beam width will definitely produce a more suitable result.

Beam Search can be understood as a process of gradual expansion and gradual pruning. At each time step, it generates possible next-step results based on the current candidates, and then retains candidates with higher probabilities or scores according to the beam width.

Initialize Candidates

At the start of generation, the search process begins from the initial state. At this point, there is no complete output yet, and the model predicts candidates for the first time step based on the input and the current state.

Expand Candidates by Conditional Probability

At the first time step, if the beam width is k, the k candidates with the largest current conditional probabilities are selected. After that, each retained candidate sequence continues to expand, forming a new set of candidate sequences.

Retain Candidates According to Beam Width

After expansion, the number of candidates increases. Beam Search compares these candidates again and keeps only the k candidates with higher probabilities or scores to continue generation.

Repeat Until the Termination Condition

The above process is repeated in subsequent time steps until the task’s termination condition is reached, such as generating an end token or satisfying the output length requirement.

Output the Final Candidate

After the search ends, the system selects the final output from the retained candidate sequences. Taking machine translation as an example, after a source-language sentence is input, the model gradually generates a target-language word sequence, and Beam Search is used to select among multiple candidate translation paths.

What Application Scenarios Is Beam Search Suitable For?

Beam Search is commonly found in sequence generation tasks such as machine translation. In such tasks, the input is a piece of source-language text, and the model needs to generate a target-language sequence; the generation process is not completed all at once, but unfolds word by word or token by token.

User needSolutionPossible effect
Want to generate a relatively stable translationRetain multiple high-probability candidates during the decoding stageReduces the impact of mistakes in single-path selection
The task has a relatively clear target answerGradually expand and filter candidate sequencesMakes it easier to retain outputs close to the target among the candidates
Need to observe output changes caused by different candidatesAdjust the beam width and compare generated resultsHelps understand the impact of beam width on prediction

In tasks with relatively clear correct answers, Beam Search can often be more effective. For example, machine translation usually has relatively clear target semantics, and retaining multiple candidate paths can reduce the risk of misjudgment caused by early single-step selections.

Fixed-width beam search is a heuristic approximation method. It controls the search range by retaining a limited number of candidates, but this also means that it does not traverse all possible sequences.

One important limitation is: sequences pruned early will not return to the candidate set. A sequence may not score highly in the first few time steps, but it may later form a more suitable complete output; if it has already been pruned, Beam Search can no longer continue exploring that path.

Key point: Beam Search is not global optimal search. It performs approximate search within a limited candidate range, and its results are affected by beam width and early pruning.

Common misconceptions include:

  • Mistakenly believing that Beam Search traverses all possible results. In fact, it only retains a fixed number of candidates.
  • Mistakenly believing that the larger the beam width, the better the result will definitely be. Beam width affects prediction, but whether the result is more suitable must be observed in combination with the task and output quality.
  • Mistakenly believing that using Beam Search requires retraining the model. Beam Search is used during the prediction stage and does not change the model training process.
  • Mistakenly believing that Beam Search can completely avoid the problems of greedy search. It can reduce the risk of single-step greedy selection, but pruning still occurs.

How Should Beam Width Be Understood and Chosen?

When choosing beam width, you can think of it as controlling the search range: the smaller the beam width, the fewer candidates are retained; the larger the beam width, the more candidates are retained. However, because fixed-width beam search is still an approximate search, beam width should not be understood as a one-way parameter where larger means more reliable.

You can use the following checklist to help make a judgment:

  • Does the current task have a relatively clear target output, such as a sequence-to-sequence task like machine translation?
  • Is it necessary to retain multiple candidates during generation rather than trusting only the current highest-probability step?
  • Are the generated results clearly affected by early token or word choices?
  • After adjusting the beam width, does the final output change?
  • Do the output changes meet the task requirements, rather than merely involving different candidate paths?

A more prudent approach is to adjust the beam width slightly within a controllable range and observe changes in the prediction results. For introductory understanding, the focus is not on memorizing a fixed value, but on understanding how beam width determines the number of candidates retained at each step, and why this pruning method affects the final generated result.