Foundation Lab

Beam Search & Structured Decoding

Beam search is standard for machine translation and structured generation tasks

Concept 51 of 100Core TrainingPhase 9

#51Beam SearchCore Training

key equation\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log p(y_i | y_{<i})

Selected Foundation Object

Keep the equation fixed; move through the evidence.

Concept 51 of 100Beam SearchCore Training / Phase 9: Advanced architectures & generation

Current question

Beam search is NOT sampling—it approximates argmax, which can produce boring/repetitive text

\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log p(y_i | y_{<i})

PredictionCommit before the demo.

Ask what should change when the equation is manipulated, then let the visualization test that expectation.

EvidenceCompare local witness and source.

Use the runnable panel, the key equation, and canonical papers as separate forms of evidence for the same object.

InvariantName what survives notation changes.

The useful learning product is the reusable mechanism you can carry into another model, paper, or engineering tradeoff.

Next moveContinue through the atlas.

Use prerequisites, dependents, and semantic links to repair the next gap without leaving the object behind.

Beam search is standard for machine translation and structured generation tasks
Explains the "greedy vs search" tradeoff: greedy is fast but suboptimal, beam explores more
Understanding beam search clarifies why speculative decoding and constrained generation work

What is still poorly explained in textbooks and papers:

Beam search is NOT sampling—it approximates argmax, which can produce boring/repetitive text
Larger beam ≠ always better: "beam search curse" where larger beams give worse translations
For open-ended generation (chat), sampling usually beats beam search for quality

If you want intuition first, start with the key equation and the visualization. Come back here for the full walkthrough.

Key Equation

\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log p(y_i | y_{<i})

Beam search maintains top- $B$ partial sequences:

At step $t$ , expand each beam by all vocab tokens, keep top- $B$ by score:

\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log p(y_i | y_{<i})

Length normalization prevents bias toward short sequences:

\text{score}_{\text{norm}} = \frac{1}{t^\alpha} \sum_{i=1}^{t} \log p(y_i | y_{<i})

Diverse beam search adds diversity penalty to avoid similar beams.

Sutskever, Vinyals, Le2014NeurIPS

Choose the next question to carry this object forward.