Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Beam Search › Visualizing Beam Search

Michael BrenndoerferMay 22, 20257 min read

Language AI HandbookAll chapters

Part 12 of 67Sequence-to-Sequence

Chapter 85Beam Search › Visualizing Beam Search

Reading section 12 of 17 · Visualizing Beam Search · 7 minSection 12 of 17 · 7 min

Section 12 of 17 · 7 min read

Beam Search › Visualizing Beam SearchOne section · Sections in this chapter12 / 17 ↓

Sections in this chapter17

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Let's build a visualization of the beam search tree to see how hypotheses are expanded and pruned.

Out[8]:

Visualization

Tree diagram of beam search with colored and gray nodes representing kept and pruned hypotheses. — Beam search tree showing hypothesis expansion and pruning over three steps with beam width k=2. Each node represents a partial sequence; blue nodes survived into the next beam while gray nodes were pruned. The log-probability score is shown beneath each node, illustrating how the beam keeps only the highest-scoring hypotheses at each step.

Out[9]:

Visualization

Line chart showing beam search score vs sequence length for three normalization settings. — Effect of length normalization on beam scores across sequence lengths from 1 to 20 tokens. Without normalization (red), cumulative log-probability decreases monotonically with length, biasing the search toward shorter outputs. With alpha=0.6 (blue), the penalty is moderated and mid-length sequences become competitive. Full normalization with alpha=1.0 (green dashed) nearly equalizes all lengths.

Out[10]:

Visualization

Line chart of BLEU score vs beam width showing a peak around k=4 to k=6. — Simulated BLEU score vs. beam width for a neural machine translation system. Performance improves sharply from k=1 (greedy) to k=4, then plateaus and slightly declines for very large beams, illustrating the beam search curse where wide beams explore low-probability territory outside the training distribution.

Bar chart of relative decoding time vs beam width showing near-linear growth. — Relative decoding time normalized to greedy (k=1) as beam width increases. Computation scales approximately linearly with k, though GPU batching reduces the constant factor compared to sequential decoding.

These plots illustrate the beam search quality-compute curve directly. BLEU improves rapidly for small $k$ but plateaus and slightly reverses for large $k$ . Computation grows approximately linearly. The sweet spot for most production systems is $k = 4$ to $k = 6$ .

Out[11]:

Visualization

Bar chart of a peaked token distribution, coloring the top token red, the additional nucleus token blue, the additional top-k tokens orange, and excluded tokens gray. — Comparison of nested decoding-strategy coverage on a peaked vocabulary distribution with 20 tokens. Beam search selects the top token (red). Nucleus sampling with p=0.9 adds one token (blue), reaching two tokens total. Top-k with k=5 adds three more tokens (orange), reaching five total. Tokens outside the top five are gray.

The visualization shows how each decoding strategy selects from the probability distribution. Beam search takes only the peak. Top-k always samples from the top 5, even if those tokens span a wide range of probabilities. Nucleus sampling adapts: here, with a peaked distribution, only 3 tokens are needed to cover 90% of the mass, so the nucleus is smaller than top-k.