Beam search decoding: Question bank — AI-ML deep dive

Intuition How to use this page

Each line below is a trap — a place where intuition about beam search quietly breaks. Read the question side, commit to an answer out loud, then reveal. If your reason differs from the given reason (even when the yes/no matches), that gap is the thing to fix.

Before you start, these symbols must be crystal clear, or the traps won't land:

$k$ = beam width = how many partial sentences we keep alive at once. $k = 1$ is greedy, $k = \infty$ is exhaustive.
$V$ = vocabulary size = how many distinct tokens (words / word-pieces) the model can emit.
$score (y) = \sum_{t} lo g P (y_{t} ∣ y_{< t}, x)$ = sum of log-probabilities of every chosen token. It is always $\leq 0$ because probabilities are $\leq 1$ , so their logs are $\leq 0$ . A "higher" (less negative) score is better.
$α$ = length penalty exponent: we divide the score by $T^{α}$ where $T$ is the number of generated tokens (not counting <START>).
<START> = the fixed start marker placed in every beam before any word is generated. It carries no predicted probability, so it adds no log-prob term and is not counted in $T$ .
<END> = the end-of-sequence token the model may emit to declare a sentence finished. Once a beam emits <END>, that beam is complete and is carried along unchanged instead of being expanded further.
max_length = a safety cap on the number of decoding steps, used to stop sequences that never emit <END> from running forever.

Notation convention on this page: the special tokens <START> and <END> are always written in code font, whether inline in prose or inside code blocks, so they never get confused with ordinary vocabulary words.

Prerequisites worth re-linking if a trap trips you: 3.5.12-Sequence-to-sequence-models, 3.4.8-Temperature-sampling, 4.2.5-BLEU-score. (Beam search operates purely on the decoder's per-step probability distribution, so it does not require attention — attention only improves the probabilities being searched, it is not part of the search itself.)

See the algorithm before you trap yourself

The traps below hinge on three moving parts — expansion, scoring, and pruning. Look at them first as a picture, then as a flowchart, so the words "beam", "candidate", and "the normalization step" have concrete meaning.

Figure 1 — one step of beam search. The left column is the current beam ( $k = 2$ live sequences). Each is expanded by all $V$ vocabulary tokens (middle), producing $k \times V$ candidates. We score them, sort, and keep only the top $k$ (right); the faded rows are pruned — gone forever.

Figure 2 — where normalization lives. The cumulative value carried inside each beam is the raw running sum $\sum lo g P$ . Normalization by $T^{α}$ is applied only as the sort key at the pruning gate — it never overwrites the stored cumulative score. This figure shows exactly that split.

Figure 3 — the control flow. The same procedure as a flowchart, so you can point to "the normalization step" and "the early-stop test" precisely.

Figure 4 — why the length penalty exponent $α$ matters. The raw sum $\sum lo g P$ drops with length purely because more negative terms are added. Dividing by $T^{1}$ removes that slope but can over-reward short high-average fragments; a fractional $α$ sits between. The curves make the trade-off visible.

True or false — justify

Beam search with a large enough

k

is guaranteed to find the globally most probable sequence.

False — unless

k \geq V^{T}

(exhaustive), beam search still prunes. Any true-best sequence whose early token falls outside the current top

k

is dropped forever (see the faded rows in Figure 1), so it stays an approximate search.

Greedy decoding is just beam search with

k = 1

True — with only one beam kept, "expand and keep the top 1" is exactly "pick the single most probable next token", which is the definition of greedy.

Increasing

k

can never make the returned sequence worse in log-probability.

True for the raw un-normalized score — a bigger beam is a superset of a smaller one's survivors, so the max-scoring survivor can only stay the same or improve. But translation quality (BLEU) can drop, because the extra survivors are often mediocre.

The score of a partial sequence is a probability between 0 and 1.

False — the score is a sum of logs, which is

\leq 0

and unbounded below. Only

exp (score)

is the probability in

[0, 1]

Two sequences of different lengths can be fairly compared by their raw summed log-probability.

False — every extra token adds a negative term (Figure 4's falling raw curve), so longer sequences are systematically penalized; that is exactly why we divide by

T^{α}

before comparing.

With

α = 0

the length penalty term

T^{α}

equals 1, so scoring reduces to the raw sum.

True —

T^{0} = 1

for any

T

, so dividing by it changes nothing;

α = 0

means no normalization.

Beam search always runs for exactly max_length steps.

False — it stops early once all live beams have emitted <END> (the "yes" branch in Figure 3); max_length is only a safety cap for sequences that never terminate.

A sequence that has already emitted <END> still keeps getting expanded token-by-token.

False — finished beams are set aside (carried as-is into candidates); expanding past <END> would waste compute and produce meaningless tail tokens.

Spot the error

"We normalize by dividing the score by len(seq), counting <START>."

Error: <START> is a fixed marker with no predicted probability, so it contributes no log-prob term. We divide by len(seq) - 1 (the generated-token count

T

), else the divisor and the number of summed terms disagree.

"Since

ar g max P = ar g max lo g P

, taking logs changes which sequence wins."

Error: it's the opposite — because

lo g

is monotonic increasing, taking logs preserves the ranking. We use logs only for numerical stability (avoiding underflow), not to change the winner.

"Beam search at step

t

keeps the top

k

of the

k

sequences, one best next token each."

Error: it keeps the top

k

out of

k \times V

candidates (each of the

k

beams tries all

V

tokens, as in Figure 1's middle column). Keeping the best token per beam would just be

k

parallel greedy runs and could never let one beam overtake another.

"With

k = 100

we explore more, so we always get a higher BLEU than

k = 5

Error: quality typically peaks around

k = 4 - 10

; beyond that, near-duplicate long sequences crowd out better short ones and BLEU can fall. More search

\neq =

better output.

"Length penalty with

α = 1

divides by

T

, so it always prefers longer sentences."

Error:

α = 1

takes the average log-prob per token, which removes the length bias but does not add a preference for length. Fractional

α < 1

divides by a smaller number than

T

, so it cancels less of the length penalty than full averaging — leaving a residual reward for length. This is a tuning heuristic, not a law: the GNMT paper (Wu et al., 2016) reports

α \approx 0.6 - 0.7

working well for their translation setup, and it must be re-tuned per task.

"We should compute the normalized score at every expansion inside the loop and use it as the running cumulative value."

Error: the cumulative value stored per beam is the un-normalized running sum (Figure 2, left); normalization by

T^{α}

is applied only as the sorting key at the pruning gate (Figure 2, right), so early tokens aren't repeatedly re-scaled.

"Complexity is

O (V^{T})

because there are

V^{T}

possible sequences."

Error: the whole point of beam search is that it never enumerates all

V^{T}

sequences. It touches

O (k T V)

candidates — the pruning is what makes it tractable.

Why questions

Why use log-probabilities instead of multiplying raw probabilities?

Products of many small probabilities underflow to 0 in floating point; summing their logs stays in a representable range, and since

lo g

is monotonic the ranking is unchanged.

Why does numerical stability ever need the log-sum-exp trick if beam search only adds log-probs?

The addition of log-probs is safe on its own, but the softmax that produces each token's probability sums exponentials over the whole vocabulary; log-sum-exp shifts by the max first so no

e^{x_{i}}

overflows or underflows to 0.

Why does a purely greedy path fail on "Je suis étudiant"?

Greedy is myopic — it locks in the locally best token at step 2 ("student" directly), never seeing that the slightly-less-obvious "a … student" phrasing yields higher total probability. Local optima ≠ global optimum.

Why divide by

T^{α}

rather than by

T

or not at all?

Dividing by

T

(

α = 1

) over-corrects and lets deceptively-high-average short fragments win; not dividing (

α = 0

) crushes long sequences. A fractional

α

interpolates to balance the two failure modes (Figure 4).

Why can "The dog ran" survive in a

k = 3

beam even though "The dog" started worse than "The cat"?

Beam search scores whole partial sequences, not per-step ranks. A high

lo g P (ran ∣ The dog)

can lift the cumulative score of a weaker prefix back into the top

k

— this is beam search's ability to recover from a bad early choice.

Why not just set

k = V^{T}

and get the exact answer?

V^{T}

is astronomically large (e.g.

50, 00 0^{20}

), so exhaustive search is intractable. Beam search deliberately trades exactness for a fixed

O (k T V)

cost.

Why might a min-length constraint be needed?

Length normalization plus the <END> token can make premature termination score well, so the model emits <END> too early. Forcing at least

n

generated tokens blocks this collapse into empty or stub outputs.

Why does n-gram blocking help in summarization but matter less in short translation?

Long generations tend to loop, repeating a phrase; blocking repeated

n

-grams breaks the loop. Short outputs rarely have room to repeat, so the fix is mostly unnecessary there.

Edge cases

What does the beam contain at step 0, before any token is generated?

A single entry: ([<START>], 0.0) — one beam holding just the start marker with cumulative log-prob 0 (since

lo g 1 = 0

, "we're certain we started").

What happens when

k > V

You cannot keep more distinct sequences than there are tokens to expand at the first step, so at step 1 you have at most

V

candidates; effective beam width is capped by the number of available continuations.

If every next-token probability is exactly equal (a uniform distribution over

V

), how does beam search behave?

All expansions get identical log-prob

lo g (1/ V)

, so the top-

k

selection is a tie — the algorithm falls back to arbitrary tie-breaking and explores

k

essentially random paths.

What is the score of a sequence containing a token with predicted probability 0?

lo g 0 = - \infty

, so that whole partial sequence gets score

- \infty

and is pruned immediately — a zero-probability token is effectively forbidden.

If a beam emits <END> at step 1 (a length-1 output), what is its

T

for normalization?

T = 1

generated token (the <END>), since <START> is not counted; its normalized score is just its single log-prob divided by

1^{α} = 1

What does a negative length penalty exponent

α < 0

do?

Dividing by

T^{α}

with

α < 0

is the same as multiplying by

T^{∣ α ∣}

, which makes longer (already-negative) scores even more negative — it actively punishes length. It is the wrong sign for encouraging complete sentences and is essentially never used.

Is dividing by

T^{α}

the only length-normalization scheme?

No — an alternative is the GNMT penalty function

lp (T) = \frac{( 5 + T ) ^{α}}{( 5 + 1 ) ^{α}}

, which smooths the divisor so very short sequences aren't over-rewarded; another is a simple additive per-token reward

+ β

at each step. All aim at the same length-bias problem via different curves.

When all

k

beams end with <END> at the same step, what does the algorithm return?

It stops and returns the

k

finished sequences, ranked by their length-normalized scores — the top one is the final decoded output.

How does temperature sampling differ from beam search at a conceptual level?

3.4.8-Temperature-sampling randomly samples tokens (introducing diversity/creativity), whereas beam search deterministically searches for high-probability sequences; one optimizes surprise, the other optimizes likelihood.