Exercises — Beam search decoding

$k=1$. With a beam of width one we keep only the single highest-scoring partial sequence at every step. That is exactly the rule "pick the highest-probability token each step" — which is greedy decoding. So beam search with $k=1$ is greedy decoding; nothing else can happen because there is no second candidate to keep alive.

$T=\text{len(seq)}-1=3-1=2$. We drop the leading <START> because it is a fixed marker the model did not predict — it carries no predicted probability. The two generated tokens are Bonjour and <END>.

$\log 0.6=-0.5108\approx -0.51$. Note it is negative: any probability below 1 has a negative log, so all sequence scores are negative and "less negative = better".

We add the new log-probability (that is why we work in log space): $-0.51+\log 0.9=-0.51+(-0.1054)=-0.6154\approx -\mathrm{0.62.}$

Normalize by $T^{\alpha }=2^1=2$:

• $-0.62/2=-0.31$
• $-1.21/2=-0.605$

Higher (less negative) wins: the first sequence, score $-0.31$. This reproduces the "Bonjour wins" result from the parent worked example.

Expand every beam by every candidate token, adding the new log-prob:

Sort by normalized score, keep top 2: Bonjour <END> ($-0.310$) and Salut <END> ($-0.605$).

Look at the figure: four orange candidate branches fan out, but only the two teal-highlighted paths pass the top-$k$ cut. The two branches ending in Salut/Bonjour (plum, dashed) are pruned — the model gave them tiny probabilities, so their cumulative scores plunged.

Salut <END> survived because at $k=2$ we keep the top two sequences, and its normalized score $-0.605$ was the second best of the four candidates. It did not win because Bonjour began with a higher first-token probability ($0.6$ vs $0.35$), giving a less-negative starting score that its ending never overcame: $-0.310>-0.605$.

Generated lengths: $T_A=2$, $T_B=4$. Normalized score $=\text{score}/T^{\alpha }$.

Reading it: with $\alpha =0$ (no normalization) the shorter A wins easily — raw sums always favour fewer negative terms. With full $\alpha =1$ the longer B wins because we divide by the full length, rewarding B's good per-token average. At $\alpha =0.7$ we sit in between: A still edges out here, but the margin has shrunk dramatically. That is exactly why practitioners pick $\alpha \in (0.6,0.7)$ — enough length reward to stop the decoder emitting <END> too early, without over-rewarding rambling.

The figure plots each sequence's normalized score as $\alpha$ sweeps $0\to 1$. The two curves cross near $\alpha \approx 0.85$: left of the crossing the short sequence wins, right of it the long one does.

• Exhaustive: every position can be any of $V$ tokens, so there are $V^{T_{\max }}=30000^{40}$ possible sequences — astronomically intractable.
• Beam search: each of $T_{\max }$ steps expands $k$ live beams by $V$ tokens, i.e. $k\cdot V=5\times 30000=150000$ candidate-expansions per step, giving $O(k{T}_{\max }V)=5\times 40\times 30000=6,000,000$ expansions total. Beam search replaces an exponential $V^T$ with a linear-in-$T$ cost — that is the whole point of pruning to $k$ survivors each step.

At this step we sort the live partial candidates by their cumulative log-prob and keep the top $k=2$ (all three partials have the same length $T=3$, so comparing cumulative scores is fair here):

I have a is only the third-best partial, so with $k=2$ it is discarded. Since it is gone, beam search can never extend it to I have a cat, even though that completed sequence would have been the global optimum. The high-probability word cat arrives too late to rescue a prefix that already fell outside the beam.

Therefore beam search is an approximate (heuristic) search, not an exact/optimal one: it can permanently prune the prefix of the true best sequence whenever an early token sits outside the top $k$.

1. Length penalty $\alpha$ → increase (toward $\sim 1.0$). Larger $\alpha$ divides by a bigger $T^{\alpha }$, which rewards longer sequences' per-token averages, so premature short sequences stop dominating (exactly the flip we saw in L4.1 as $\alpha \to 1$).
2. Min length → set to ~15 (or some floor $n$). This hard-forbids <END> before $n$ tokens are generated, directly banning the "quit after 3 tokens" behaviour regardless of score. (A supporting third fix: n-gram blocking if the longer outputs start repeating phrases.)

Beam search with $k=1$ reduces to greedy decoding. We work with log-probabilities so that products become sums and small numbers don't underflow. Length normalization divides the score by ==$T^{\alpha }$== where $T$ = number of generated tokens. Why don't we count <START> in $T$? ::: Because it is a fixed marker the decoder never predicted, so it contributes no $\log P$ term. Beam search is approximate because it can prune the prefix of the true-best sequence if an early token falls outside the top $k$.