What happens with beam width 1?

In a simple layer-by-layer setup with the corresponding scoring and stopping rules, it reduces to keeping one greedy candidate.

Can beam search miss a valid solution?

Yes. Pruning can remove the branch that would lead to it, so the method is generally incomplete.

Does it require neural networks?

No. It is a general search idea, although neural sequence generation is a prominent application.

AI Glossary / Graphs and symbolic AI / Intermediate

Beam search

Definition

Beam search is a search strategy that keeps only a limited number of promising partial candidates and discards the rest. The limit is called the beam width. It trades more comprehensive exploration for reduced memory and computation, without generally guaranteeing the best complete solution.

What it means

A search problem may offer several choices at every step. Keeping every possible continuation quickly becomes expensive. Beam search preserves a small collection judged promising by a scoring rule, giving it more alternatives than a single greedy path while avoiding exhaustive enumeration.

The method is used in sequence generation and other search tasks. A candidate might be a partial translation, a sequence of actions or a path through a graph. “Promising” depends entirely on the chosen score, which may not align perfectly with the ultimate user objective.

Implementations differ in how they organize the frontier, score candidates and handle completed solutions. A common layer-by-layer form expands the current candidates and retains the best fixed number for the next step.

How it works

Begin with an initial candidate. Generate its permitted extensions and score them. Retain only the candidates allowed by the beam width, then repeat the expansion and selection process until the stopping conditions are met.

For language generation, scores often build from conditional token probabilities, usually accumulated as log probabilities. Length adjustments and completion rules can affect which sequences are preferred. Comparing a short finished answer with a long partial answer requires a clearly specified convention.

Once a branch is discarded, ordinary beam search does not automatically recover it. A candidate with a weak early score can therefore be lost even if it would eventually lead to the strongest complete result. Increasing the beam width permits more alternatives but raises resource use and does not guarantee better human-perceived quality. Search quality and model quality remain separate issues.

Three practical examples

A translation system retains several partial sentence candidates while deciding how to continue each one.
A structured generation tool explores alternative valid outputs under a grammar and keeps a limited set according to its scoring rule.
A planning prototype searches through action sequences with a fixed frontier budget when exhaustive search would exceed available resources.

Think of it this way

Think of a competition that advances only a few contestants after each round. Keeping several contestants avoids betting everything on the first apparent leader, but an eliminated contestant cannot win a later round.

The analogy has a limit: partial search scores may be poor predictors of final quality. Advancing the current leaders is a computational compromise, not a proof that eliminated possibilities could never have succeeded.

Worked example

Keeping an alternative to the greedy choice

Consider an invented generator producing exactly two tokens. At the first step, token A has probability 0.6, B has 0.3 and C has 0.1. Greedy search selects A immediately. A beam of width 2 retains both A and B.

After A, the most likely second token has conditional probability 0.4, giving the best A-starting sequence probability 0.6 × 0.4 = 0.24. After B, the most likely second token has probability 0.9, giving 0.3 × 0.9 = 0.27.

With complete two-token candidates compared by their joint probabilities, the beam can select the B-starting sequence, which greedy search missed. This example shows one benefit of retaining alternatives. It does not show that width 2 always finds the global optimum: in a different tree, a discarded prefix could lead to the strongest eventual completion.

Illustrative case study

Fictional case: Birch Summaries increases beam width because its team expects every increase to improve summaries. The generated text receives higher model scores on some examples, but reviewers find that important qualifications are still missing.

The team separates decoding experiments from content evaluation. It measures factual support, coverage and usefulness as well as model score, and records the length and stopping settings used in each experiment. It also compares resource use rather than treating wider search as free.

The lesson is that beam search optimizes an encoded scoring process. If the score rewards a fluent but incomplete answer, exploring that score more thoroughly does not automatically repair the mismatch with the reader's needs.

Common misconceptions and mistakes

Beam search is exhaustive. It deliberately discards candidates.
A wider beam always produces a better answer. It changes the search budget, while quality depends on the score and task.
Beam width is the number of final answers returned. The number of retained partial candidates and the number of returned outputs are separate settings.
Beam search is random sampling. Standard beam search selects by score, although related methods can introduce randomness.
A high sequence probability establishes factual truth. It is a model-based score, not evidence verification.

Business use

Beam search is useful when a system needs a manageable set of alternative sequences under a clear scoring rule. Business teams may encounter it in translation, structured generation and planning discussions.

Evaluate the complete output against the operational task, including important omissions and constraint violations. Record beam width, score adjustments and stopping behavior so that comparisons can be reproduced. Consider whether extra search cost improves the metric users actually care about. A strong decoding configuration cannot compensate for missing source information or an unsuitable model objective.

Check your understanding

A partial candidate is ranked fourth when the beam width is 3. Its eventual completion would be best. Will ordinary beam search necessarily discover that completion?

Answer: No. If the candidate is discarded at that step, its continuation is not explored. The fixed beam trades that possibility for bounded search effort.

Related terms

Learn next

Draw a two-level search tree and assign scores to every partial and complete path. Trace greedy search and beam search with widths 2 and 3. Construct a case where an early low-ranked path becomes the best completion. Then inspect how different stopping and length rules affect sequence comparisons.

Sources

AIMA glossary, beam search, describes the limited-frontier search principle and its completeness limitation: https://github.com/aimacode/aima-glossary/blob/master/glossary.md?plain=1

Hugging Face Transformers, generation strategies, provides a primary implementation-oriented reference: https://github.com/huggingface/transformers/blob/main/docs/source/en/generation_strategies.md

The two-token calculation and fictional summarization case are original illustrations.

Previous: BCPNN Next: Beam width