Worked examples — Beam search decoding

This page is a drill. We take the machinery from Beam search decoding and run it through every kind of situation it can meet: normal cases, tie cases, the special zero/degenerate inputs, the limiting values of the beam width $k$ and the penalty $\alpha$, a real-world word problem, and an exam-style trap. If you have not yet seen the algorithm, read the parent first — here we assume you know what beam search does and we practise doing it.

One symbol appears in every formula, so we name it before anything else:

Three quantities we lean on constantly, restated in plain words so no symbol is unearned:

The scenario matrix

Every worked example below is tagged with one of these cells. Together they cover the whole table.

Cell	What makes it special	Example
A. Baseline	Normal $k=2$, all beams finish, one clear winner	Ex 1
B. Greedy vs beam disagree	The path beam finds beats the greedy path	Ex 2
C. Length matters	$\alpha$ flips the winner between a short and a long sequence	Ex 3
D. Tie	Two candidates share a score — how ties are broken	Ex 4
E. Degenerate $k=1$	Beam collapses to greedy	Ex 5
F. Limiting $k=\infty$	Exhaustive search — beam finds the true optimum	Ex 5
G. Zero-probability token	$\log 0=-\infty$, a token is effectively forbidden	Ex 6
H. Premature <END>	Min-length forcing changes the answer	Ex 7
I. Real-world word problem	Captioning with $n$-gram blocking	Ex 8
J. Exam twist	"Beam search is optimal?" — prove it is not	Ex 9

We use natural logs everywhere. Handy reference values: $\log 0.9\approx -0.105$, $\log 0.8\approx -0.223$, $\log 0.7\approx -0.357$, $\log 0.6\approx -0.511$, $\log 0.5\approx -0.693$, $\log 0.4\approx -0.916$, $\log 0.35\approx -1.050$, $\log 0.1\approx -2.303$.

---

Example 1 — Baseline run (Cell A)

Forecast: Guess now — will A <END> or B <END> win, and roughly what score?

The figure below is the tree we build: <START> at the left, its three children in the middle (two blue = kept, one red = pruned), and the two finished sequences on the right with the winner arrowed in yellow. Trace it as you read the steps.

1. Expand <START>. Scores: A $=\log 0.6=-0.511$, B $=\log 0.35=-1.050$, <END> $=\log 0.05=-2.996$. Why this step? Beam search always tries all $V$ next tokens (here $V=4$, minus <START> which cannot be re-emitted), then prunes — this is the left fan-out in the figure.
2. Apply $\text{top\_}k$ with $k=2$. Keep A ($-0.511$) and B ($-1.050$); drop the immediate <END> (the greyed red node in the figure). Why this step? $k=2$ means only the two best partial sequences survive; $\text{top\_}k$ is exactly the sort-and-cut operation from the preliminaries.
3. Expand both survivors. A <END> $=-0.511+\log 0.9=-0.616$. B <END> $=-1.050+\log 0.85=-1.212$ (the two green paths on the right). Why this step? Each surviving beam is extended by one more token.
4. Normalize ($T=2$, $\alpha =1$, so divide by $2$). A <END> $=-0.308$; B <END> $=-0.606$. Why this step? We compare finished sequences by average log-prob per token, not raw sum — the numbers printed beside the green nodes.

Answer: A <END> wins with normalized score $-0.308$ (the yellow arrow in the figure).

Verify: $-0.616/2=-0.308$ and $-1.212/2=-0.606$; the more-probable first word wins, as expected. ✓

---

Example 2 — Greedy loses, beam wins (Cell B)

Forecast: Greedy takes the single best next word at each step. At I am, the biggest single token is cat ($0.4$). Will greedy's early commitment to cat beat beam's willingness to also explore the lower-probability a branch? Guess before reading. (All numbers are now used exactly as stated — nothing is silently changed.)

1. Beam step at I am — actually run $\text{top\_}k$. The three candidate partial sequences and their raw scores (each $=\log 0.7+\log P(\cdot )$):

   • I am a: $-0.357+\log 0.3=-0.357-1.204=-1.561$
   • I am cat: $-0.357+\log 0.4=-0.357-0.916=-1.273$
   • I am <END>: $-0.357+\log 0.3=-1.561$

   Sort by score: I am cat ($-1.273$) best, then I am a and I am <END> tied at $-1.561$; the tie-break (lower vocab index — say a precedes <END>) keeps a. $\text{top\_}2$ keeps I am cat and I am a. Why this step? This is the heart of "doing beam search": we generate every child, score it, sort, and cut to $k=2$. Greedy ($k=1$) would keep only I am cat and lose the a branch entirely — that is the difference we are about to exploit.

2. Greedy path commits to I am cat, then ends: I am cat <END> raw $=-1.273+\log 0.4=-1.273-0.916=-2.189$. Normalized ($T=3$): $-2.189/3=-0.730$. Why this step? Greedy kept only cat at I am; from cat the end probability is a mediocre $0.4$, so its sentence is short and not very probable.

3. Beam expands the surviving I am a branch. I am a cat: $-1.561+\log 0.95=-1.561-0.051=-1.612$; then I am a cat <END>: $-1.612+\log 0.95=-1.612-0.051=-1.663$. Normalized ($T=4$): $-1.663/4=-0.416$. Why this step? By keeping the lower-probability a, beam discovered the excellent tail a → cat → <END> (each $\ge 0.95$), a completion greedy never saw.

4. Compare normalized scores. Beam's I am a cat <END> = $-0.416$ beats greedy's I am cat <END> = $-0.730$. Why this step? Beam wins because a cheap early token (a, prob $0.3$) unlocked a high-probability tail, and length normalization rewards the more complete sentence. This is the exact condition under which beam pays off.

Answer: Beam outputs I am a cat (normalized $-0.416$); greedy outputs I am cat (normalized $-0.730$). Beam wins.

Verify: greedy raw $-0.357-0.916-0.916=-2.189$, norm $-0.730$; beam raw $-0.357-1.204-0.051-0.051=-1.663$, norm $-0.416$; $-0.416>-0.730$. ✓ This is a different answer to the myopia problem than temperature sampling (which is stochastic).

---

Example 3 — Length penalty flips the winner (Cell C)

Forecast: The short one wins with no penalty. Does the long one ever win?

The figure plots each candidate's normalized score as $\alpha$ increases: blue = short Hi, green = long Hello there friend. Watch where the green curve crosses above the blue — that crossing is the tie we solve for.

1. $\alpha =0$ (divide by $T^0=1$): Hi $=-0.36$, Hello there friend $=-1.20$. Short wins (left edge of the plot). Why this step? Raw sums punish long sequences: more negative terms.
2. $\alpha =1$ (divide by $T$): Hi $=-0.36/1=-0.36$; Hello there friend $=-1.20/3=-0.40$. Short still wins, barely — the curves have nearly met. Why this step? Full normalization averages per token — now they are close.
3. Find the tie (the red dot in the figure). Solve $\frac{-0.36}{1^{\alpha }}=\frac{-1.20}{3^{\alpha }}$. Since $1^{\alpha }=1$: $-0.36=\frac{-1.20}{3^{\alpha }}\Rightarrow 3^{\alpha }=\frac{1.20}{0.36}=3.333\Rightarrow \alpha =\frac{\ln 3.333}{\ln 3}=1.096$. Why this step? We want the exact $\alpha$ at which the long sentence starts to win.

Answer: For $\alpha <1.096$ the short wins; for $\alpha >1.096$ the long wins; equality at $\alpha \approx 1.096$.

Verify: at $\alpha =1.096$: $-1.20/3^{1.096}=-1.20/3.333=-0.36=$ short's score. ✓ This is why practitioners pick $\alpha \in (0.6,0.7)$: they don't want length to dominate.

---

Example 4 — A tie (Cell D)

Forecast: Two candidates, identical score, but $k=1$ keeps only one. Which?

1. Both score $\log 0.5=-0.693$. Truly equal. Why this step? Ties are legal; the model genuinely can't distinguish.
2. Apply the tie-break rule of $\text{top\_}k$. As defined in the preliminaries, on equal scores $\text{top\_}k$ keeps the token with the lower vocabulary index. Say Blue has the lower index; it survives. Why this step? The rule was fixed up front precisely so this output is deterministic and reproducible.

Answer: Output is Blue <END> (whichever token has the lower index); score $-0.693$ either way.

Verify: $\log 0.5=-0.6931$; both candidates equal to 4 dp. ✓ Lesson: always fix the tie-break for reproducibility.

---

Example 5 — $k=1$ and $k=\infty$ (Cells E, F)

Forecast: Which value of $k$ reproduces greedy, and which is guaranteed optimal?

1. (a) $k=1$. Only one beam survives each step $\Rightarrow$ pure greedy. At I am it keeps only the local max cat ($0.4$), giving I am cat <END> (raw $-2.189$, normalized $-0.730$). Why this step? $k=1$ is greedy by definition; $\text{top\_}1$ = $\arg \max$, so the beam collapses to a single path and the a branch is lost.
2. (b) $k=\infty$. Keep every partial sequence, never prune, then compare all finished sequences by (normalized) score. It considers both I am cat <END> (norm $-0.730$) and I am a cat <END> (norm $-0.416$) and returns the higher, I am a cat. Why this step? With no pruning ($\text{top\_}\infty$ keeps everything) no sequence is ever lost, so the global optimum is found — at cost $O(V^T)$, intractable in practice.

Answer: $k=1\Rightarrow$ greedy I am cat (norm $-0.730$); $k=\infty \Rightarrow$ exhaustive, I am a cat (norm $-0.416$). Here $k=2$ already matched the exhaustive optimum (Ex 2). Real beam search lives strictly between $1<k<\infty$.

Verify: definitionally $\text{top\_}1$ = $\arg \max$, $\text{top\_}\infty$ = keep-all; and $-0.416>-0.730$, so I am a cat is the normalized optimum. ✓

---

Example 6 — A zero-probability token (Cell G)

Forecast: What is $\log 0$? Can a forbidden token appear in the beam?

1. Score of Maybe $=\log 0=-\infty$. Why this step? The model assigned it zero probability; the log sends it to negative infinity.
2. Effect on pruning. A score of $-\infty$ can never be in the top $k$ of any finite candidate list, so $\text{top\_}k$ always discards it. Maybe is effectively banned for all time — and any sequence passing through it inherits $-\infty$. Why this step? This is how hard constraints ($n$-gram blocking, min-length, forbidden words) are implemented: set the log-prob to $-\infty$.
3. Survivors: Yes $=\log 0.7=-0.357$, No $=\log 0.3=-1.204$. Why this step? With only two finite-scoring tokens and $k=2$, both survive and Maybe cannot displace either — this confirms the $-\infty$ trick truly removes a token from all future search.

Answer: Maybe gets $-\infty$ and is unreachable; beam holds Yes and No.

Verify: $\log 0.7=-0.3567$, $\log 0.3=-1.2040$, and any candidate with a $-\infty$ term is worse than every finite one. ✓

---

Example 7 — Premature <END> and min-length (Cell H)

Forecast: Without the rule, what does the model output? With it?

1. No min-length: $k=1$ takes <END> (0.4 > 0.35), producing the empty translation [<START>, <END>], $T=1$, score $\log 0.4=-0.916$. Why this step? Premature <END> is a real failure mode — an empty output.
2. Apply min-length 1: we force $\log P(\text{<END>})=-\infty$ until at least 1 real token exists. Now Hello ($\log 0.35=-1.050$) is the best legal token. Why this step? Min-length is a hard constraint implemented exactly like the $-\infty$ trick of Ex 6.
3. Continue to a finished sequence: from Hello, emit <END> with $P(\text{<END>}\mid \text{Hello})=0.9$, giving $-1.050+\log 0.9=-1.155$. Why this step? We must run the beam to a completed sequence (ending in <END>) before we can report a final score; this step closes the sentence and gives the number to compare.

Answer: Without the rule: empty output ($-0.916$). With min-length 1: Hello <END>, raw score $-1.155$.

Verify: $\log 0.4=-0.9163$; $\log 0.35=-1.0498$; $-1.0498+\log 0.9=-1.0498-0.1054=-1.1552$. ✓

---

Example 8 — Real-world word problem: captioning with $n$-gram blocking (Cell I)

Forecast: Blocking sets a token's log-prob to $-\infty$ if it would recreate a forbidden 2-gram. Who wins?

1. Check the block. The current last word is dog. Emitting a next would form the 2-gram $(\text{dog},\text{a})$. Since $(\text{dog},\text{a})$ already appeared, it is blocked $\Rightarrow \log P(\text{a})=-\infty$. Why this step? $n$-gram blocking forbids repeating any bigram, stopping the "dog a … dog a …" loop that plagues captioning/summarization.
2. Legal candidates: running $=\log 0.4=-0.916$, sitting $=\log 0.1=-2.303$. Why this step? With a set to $-\infty$, $\text{top\_}k$ must choose among the remaining finite-scoring tokens, forcing diversity.
3. Keep top $k=2$: both running and sitting survive; the caption continues "a dog running…" instead of "a dog a…". Why this step? There are only two legal candidates and $k=2$, so both are retained; the best (running) leads the surviving beams.

Answer: Blocking removes a (→ $-\infty$); the caption continues with running ($-0.916$) as the best.

Verify: $\log 0.4=-0.9163$, $\log 0.1=-2.3026$, and the blocked $-\infty$ can never be top-$k$. ✓ Better, loop-free captions here would show up as a higher BLEU score against references.

---

Example 9 — Exam twist: "Beam search is optimal?" — disprove it (Cell J)

Forecast: $C$ starts worst. Can beam even keep it alive to discover its brilliant continuation?

The figure shows all three first-step children: $A,B$ kept (blue), $C$ pruned (red). The green solid path is beam's actual output; the red dashed path is the true optimum that pruning threw away. Compare the two printed scores.

1. Step 1 scores: $A=\log 0.4=-0.916$, $B=\log 0.35=-1.050$, $C=\log 0.25=-1.386$. Why this step? $C$ has the lowest first-token probability.
2. Prune with $\text{top\_}k$, $k=2$: keep $A$ and $B$; drop $C$ (the red node). Why this step? Beam keeps only the top two — $C$ falls outside and is gone forever.
3. Beam continues the two survivors to completion: A <END> $=-0.916+\log 0.5=-0.916-0.693=-1.609$; B <END> $=-1.050+\log 0.5=-1.050-0.693=-1.743$. Beam's best finished sequence is A <END> ($-1.609$). Why this step? Beam can only finish the branches it kept; among $A$ and $B$, $A$ wins.
4. The true optimum (the dashed branch beam never explored) is C great <END>: $-1.386+\log 0.99+\log 0.99=-1.386-0.0101-0.0101=-1.406$. Why this step? We must compute the pruned branch's score to prove it beats what beam returned.
5. Compare: true best $-1.406>$ beam's best $-1.609$. Beam returned the worse sequence. Why this step? The optimum hid behind a low first-token probability that pruning discarded — the definitive proof beam search is approximate.

Answer: Beam outputs A <END> ($-1.609$), but the global optimum is C great <END> ($-1.406$). Beam search is approximate, not optimal — exactly the parent's warning. Only $k\ge 3$ (which keeps $C$ alive at step 1) recovers the optimum.

Verify: $-1.386-0.0101-0.0101=-1.406$; $-0.916-0.693=-1.609$; $-1.050-0.693=-1.743$; $-1.406>-1.609$. ✓ This is the "larger beams can help, but only if they keep the right branch" trade-off in one clean picture.

---

Recall Self-test

Why do we compare finished sequences by normalized score, not raw score? ::: Raw log-prob sums grow more negative with length, so without dividing by $T^{\alpha }$ short sequences almost always win. What log-prob does a forbidden/zero-probability token receive, and why does that ban it? ::: $\log 0=-\infty$; a $-\infty$ term can never be in any finite top-$k$, so it is permanently pruned by $\text{top\_}k$. Give one concrete tree where beam search misses the global optimum. ::: Ex 9: the best sequence C great <END> ($-1.406$) starts with a low first-token prob, so $C$ is pruned at step 1 under $k=2$, leaving beam with A <END> ($-1.609$).