How does beam search work?

Beam search works by expanding several candidate sequences at each generation step and retaining only the highest-scoring ones. The number of candidates kept is called the beam width.

Step 1: Choose a beam width

Suppose beam width = 2. The decoder keeps two candidate sequences instead of committing to a single next token.

Step 2: Generate initial candidates

Imagine the model assigns the first token probabilities:

A → 0.60
B → 0.40

Both A and B remain because the beam width is two.

Step 3: Expand every retained candidate

The model predicts another token separately for each candidate:

A → X: 0.50  → sequence score 0.60 × 0.50 = 0.30
A → Y: 0.40  → sequence score 0.60 × 0.40 = 0.24
B → Z: 0.90  → sequence score 0.40 × 0.90 = 0.36
B → Q: 0.05  → sequence score 0.40 × 0.05 = 0.02

These numbers are illustrative. Actual implementations normally add log-probabilities rather than multiply probabilities directly.

Step 4: Keep the best two sequences

The decoder compares all expanded candidates and retains:

B → Z: 0.36
A → X: 0.30

Notice that B was less likely than A initially, but its continuation B → Z now scores highest. This is why beam search can outperform choosing the best immediate token.

Step 5: Repeat until stopping

Each retained sequence is expanded again. The process continues until an end token or configured length/stopping condition is reached. Finished candidates are tracked, and the final output is selected from completed sequences using the decoding score.

How are sequences scored fairly?

Raw sequence probabilities shrink as text gets longer. Implementations often apply length penalties or normalization so that very short answers do not always win.

Important trade-offs

• Increasing beam width explores more candidate paths but uses more memory and computation.
• Beam search is not guaranteed to find the globally best sequence: discarded paths cannot be recovered.
• High model probability does not guarantee factual accuracy or engaging wording.

For the overall concept, see “What is beam search in language models?”

In short: beam search repeatedly expands candidate responses, scores the resulting sequences, and keeps only the best few until generation finishes.