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.
What Is Beam Search?
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.
What Are the Key Differences Between Beam Search and Greedy Search?
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 dimension | Greedy search | Beam Search |
|---|---|---|
| Candidates retained at each step | Usually retains only the one candidate with the highest current probability | Retains multiple candidates with relatively high probabilities |
| Dependence on early choices | Very strong; once an early step is chosen incorrectly, it is hard to correct | Relatively reduces the impact of single-step selection errors |
| Whether all sequences are exhaustively enumerated | No | No |
| Whether model parameters are changed | No | No |
| Usage stage | Prediction or decoding stage | Prediction 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 setting | Meaning | Impact on the search process |
|---|---|---|
| k = 1 | Retains only one candidate at each step | Close to the greedy approach of selecting only the current optimum at each step |
| Smaller k | Retains a small number of candidates | The search space is more restricted, and the impact of early pruning is more obvious |
| Larger k | Retains more candidates | More 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.
The Basic Process of Beam Search
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 need | Solution | Possible effect |
|---|---|---|
| Want to generate a relatively stable translation | Retain multiple high-probability candidates during the decoding stage | Reduces the impact of mistakes in single-path selection |
| The task has a relatively clear target answer | Gradually expand and filter candidate sequences | Makes it easier to retain outputs close to the target among the candidates |
| Need to observe output changes caused by different candidates | Adjust the beam width and compare generated results | Helps 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.
What Are the Limitations and Common Misconceptions of Fixed-Width Beam Search?
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.