Does width one resemble greedy decoding?

Yes, under the usual consistent single-prefix procedure.

Is beam search exact in general?

No; pruning can discard a prefix leading to the best complete solution.

AI Glossary / Natural language and speech / Advanced

Beam width

Definition

Beam width is the maximum number of candidate partial solutions retained at a step of a beam-search procedure. In language generation, these candidates are usually output sequences constructed so far. A width of k allows the search to carry forward up to k competing prefixes according to its scoring rule. The parameter controls search breadth, rather than the length of the generated text or the number of words in the vocabulary.

What it means

Choosing the most attractive next token can discard a prefix that would later lead to a better complete sequence. Keeping several prefixes gives the search additional possibilities to develop. Beam width specifies how many of those possibilities survive each pruning step.
The tradeoff is computation and memory against the chance of preserving useful alternatives. A wider beam is not a guarantee of the globally best sequence, nor of better results according to human judgment. The search follows its scoring function, and a high model score is not identical to factual accuracy, readability or task success.

How it works

At each decoding step, extend each retained prefix with possible next tokens. Score the resulting candidates, then keep the best k across the combined candidate pool. Keeping k children separately for every parent would produce a different and potentially much larger frontier.
For probability-based decoding, a sequence probability is the product of conditional token probabilities. Implementations commonly add log probabilities instead. The score may also include length normalization or other adjustments, so the exact ranking rule must be stated.
Completed sequences and end-of-sequence tokens require a completion policy. Some procedures move completed candidates into a separate set; others reduce the active beam as candidates finish. These details affect stopping and output selection. In the usual single-prefix version with consistent local scoring, width one behaves like greedy decoding. A beam width is distinct from top-k sampling, which restricts token choices for a sampling step rather than retaining k competing sequence prefixes.

Three practical examples

A translation system retains several partial translations so that an initially less likely beginning can survive long enough to reveal a strong continuation.
A speech recognizer searches among possible transcriptions. Candidate scores may combine different components, so comparing widths is meaningful only alongside the scoring and pruning rules actually used.
A structured-generation system explores alternative valid prefixes under grammar constraints. Increasing width changes search effort, while the grammar independently determines which extensions are allowed.

Think of it this way

Think of following several possible routes through a branching map. At each checkpoint, you keep a limited number of promising routes and abandon the rest. A wider search leaves more options open, but a route discarded earlier is no longer available. The ranking used at checkpoints may also differ from what makes the completed journey useful.

Worked example

Consider an invented model that generates exactly two tokens and then ends with probability one. The first token is A with probability 0.6 or B with probability 0.4. After A, the second token is x or y, each with probability 0.5. After B, it is x with probability 0.9 or y with probability 0.1.
The four complete two-token sequences have probabilities:
Ax: 0.6 × 0.5 = 0.30.
Ay: 0.6 × 0.5 = 0.30.
Bx: 0.4 × 0.9 = 0.36.
By: 0.4 × 0.1 = 0.04.
All sequences have equal length, and the certain final termination contributes a factor of one, so no length correction is needed for this illustration.
With width one, the first step retains A because 0.6 exceeds 0.4. The second step considers Ax and Ay, both scoring 0.30. A declared alphabetical tie rule selects Ax. Bx cannot be recovered because its prefix B was already removed.
With width two, the first step retains both A and B. Their four extensions are compared together. Bx, scoring 0.36, ranks first. Ax and Ay tie at 0.30 for the second retained position; the same tie rule selects Ax. The best completed result is Bx.
Here the wider beam finds the globally highest-probability sequence because the example has only four complete possibilities and both first-step prefixes survive. This does not prove width two is sufficient for arbitrary models. It also does not establish which sequence would be the best answer to a real user's question; the example specifies probabilities, not a task-specific meaning for the tokens.

Illustrative case study

In a fictional decoder comparison, a team uses the worked model to diagnose why its width-one output scores below an exhaustively checked optimum. It initially suspects an arithmetic error. Inspecting the retained prefixes shows that the calculations are correct: pruning B prevents the later discovery of Bx.
The team adds width two to its comparison and records the improvement from 0.30 to 0.36 in complete-sequence probability. It does not report this as a twenty-percent improvement in translation quality. That percentage describes the relative increase in this toy model score, and no translation-quality assessment has occurred.
For its actual application, the team compares task outcomes and measured runtime under documented scoring and stopping rules. It keeps the model fixed during the comparison so that changes can be attributed to the decoding configuration rather than a different model.

Common misconceptions and mistakes

Beam width does not specify the number of final answers that must be returned. A decoder may retain multiple candidates internally and still return only one result.
Do not confuse local next-token probability with the score of an entire prefix. In the example, B's weaker initial score is outweighed by its strong continuation. Also, a larger search budget cannot repair every mismatch between a model's preferred sequence and the application's desired outcome. Measure the outcome that matters instead of assuming a larger width is always better.

Business use

Document beam width together with model version, scoring adjustments, constraints and stopping policy. Compare quality, latency and memory on representative inputs. Select a supported operating point for the application, and report whether an observed improvement concerns model score or an independently assessed task metric.

Check your understanding

Which prefix does width one discard?

Answer: B.

What is Bx's complete probability?

Answer: 0.36.

Why can width two find it here?

Answer: Both first-token prefixes survive to be extended.

Related terms

Beam search
Greedy decoding
Hypothesis
Pruning
Log probabilities
Top-k sampling
search frontier
sequence probability
log probability
length normalization

Learn next

Compare beam search with greedy and sampling-based decoding, then examine completion policies and length-adjusted scoring.

Beam search

Sources

Jurafsky and Martin, Speech and Language Processing, chapter 13, section 13.4: beam search, width, hypothesis scoring and completion. https://web.stanford.edu/~jurafsky/slp3/13.pdf The two-token model, tie rule and fictional decoder comparison are original teaching illustrations.

Previous: Beam search Next: Behavior-based robotics