Continuous FunctionStart learning

Foundation Lab

Beam Search & Structured Decoding

Beam search is standard for machine translation and structured generation tasks

Concept 51 of 100Core TrainingPhase 9
Inspect equationAll Foundations
#51Beam SearchCore Training
key equation
score(y1:t)=∑i=1tlog⁡p(yi∣y<i)\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log p(y_i | y_{<i})
Reading map and next steps

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

score(y1:t)=∑i=1tlog⁡p(yi∣y<i)\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log p(y_i | y_{<i})
PredictionCommit before tracing the equation.

Ask what should change under a concrete input, then trace that expectation through the equation.

EvidenceCompare the equation and source.

Use the key equation and canonical papers as the available witnesses, without implying that a runnable panel exists.

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.

Inspect equationBrowse atlasNext foundation

Why It Matters for Modern Models

  • 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 Tutorials Skip

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

Visualization Status

Core Math (Optional Deep Dive)

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

Key Equation
score(y1:t)=∑i=1tlog⁡p(yi∣y<i)\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log p(y_i | y_{<i})

Beam search maintains top-BB partial sequences:

At step tt, expand each beam by all vocab tokens, keep top-BB by score:

score(y1:t)=∑i=1tlog⁡p(yi∣y<i)\text{score}(y_{1:t}) = \sum_{i=1}^{t} \log p(y_i | y_{<i})

Length normalization prevents bias toward short sequences:

scorenorm=1tα∑i=1tlog⁡p(yi∣y<i)\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.

Canonical Papers

Sequence to Sequence Learning with Neural Networks

Sutskever, Vinyals, Le2014NeurIPS
Read paper →

Connections

Prerequisites

🎲DecodingℒML/CE/KL

Next Moves

Choose the next question to carry this object forward.