Foundations — Beam search decoding

This page assumes you have seen none of the notation in the parent note. We build every symbol from scratch, in an order where each one leans only on the ones before it. If a picture defines an idea better than words, we draw it.

1. What is a "sequence"? The symbol $\mathbf{y}$

A sequence is just an ordered list of things — here, a list of words (or word-pieces) that the model produces one at a time, left to right.

The picture: think of a row of boxes filled left to right. Box number $t$ holds token $y_t$.

Why the topic needs it. Beam search is a way of choosing which sequence $\mathbf{y}$ to output. Before we can score or search over sequences, we need a name for one — that name is $\mathbf{y}$, and its parts are the $y_t$.

2. The input we translate from: $\mathbf{x}$

The model does not invent text from nothing. It reads an input — the English sentence to translate, the image to caption, the article to summarize — and we call that whole input $\mathbf{x}$ (bold again, because it is also a list).

This machinery — read $\mathbf{x}$, write $\mathbf{y}$ one token at a time — is exactly the sequence-to-sequence model. The reading half compresses $\mathbf{x}$ into an internal summary (often written $\mathbf{h}$, the encoder output), and the attention mechanism lets the writing half look back at the useful parts of $\mathbf{x}$ at each step. For this page you only need one fact from all that: the model can, at any step, hand us a probability for every possible next token.

3. Probability: $P(\text{something})$

A probability is a number between $0$ and $1$ that measures how much the model believes something. $0$ = "no way", $1$ = "certain", $0.6$ = "fairly likely".

So $P(\mathbf{y}\mid \mathbf{x})$ is "the probability that the model produces sentence $\mathbf{y}$, given it read input $\mathbf{x}$". That is the exact number beam search is trying to make large.

The picture: a probability is a slice of a full pie of size $1$. All possible next tokens split that pie; a bigger slice = a more likely token.

Why the topic needs it. Beam search's whole job is to hunt for the $\mathbf{y}$ with the biggest $P(\mathbf{y}\mid \mathbf{x})$. Without probabilities there is nothing to compare candidates by.

4. Building a sentence's probability: the product $\prod$

The model does not score a whole sentence in one shot. It writes token by token, and at each step it gives the probability of the next token given everything so far.

So the per-step number is $P(y_t\mid y_{<t},\mathbf{x})$ = "probability of the token in slot $t$, given the words already written and the input".

To get the probability of the whole sentence, we multiply these step-probabilities together:

Why multiply, and not add? Because each step is a separate choice that must all happen. The probability of "this word AND then that word AND then that word" is the product of the individual probabilities. Think of flipping a coin heads three times: $\frac{1}{2}\cdot \frac{1}{2}\cdot \frac{1}{2}$, not $\frac{1}{2}+\frac{1}{2}+\frac{1}{2}$.

The picture: a chain of links. Each link is one step-probability; the strength of the whole chain is all links multiplied.

5. Picking the biggest: $\arg \max$

We want the best sentence. Two related symbols:

Beam search's dream target is ${\mathbf{y}}^{\ast }=\arg {\max }_{\mathbf{y}}P(\mathbf{y}\mid \mathbf{x}),$ where the little star ${}^{\ast }$ just marks "the optimal one". In words: out of all possible sentences, hand me the one with the highest probability.

Why we can't just compute it directly. If the vocabulary has $V$ tokens and sentences are length $T$, there are $V^T$ possible sentences — astronomically many. We cannot check them all, so we need a clever partial search. That search is beam search.

6. The vocabulary size $V$ and the branching problem

At every step the model could pick any of $V$ tokens. So from one half-sentence there are $V$ ways to continue; from each of those, $V$ more; the tree of possibilities branches by $V$ at every level and explodes as $V^T$.

Why the topic needs $V$. Beam search's cost is governed by $V$ (it must consider all $V$ next tokens for each kept candidate). Understanding that the space is $V^T$ is why we prune instead of search everything.

7. The special markers <START> and <END>

Two tokens are not real words — they are punctuation for the machine:

• <START> — a fixed marker placed before position 1 so the model always has "something to condition on" at the first step. It is given, never predicted, and so carries no probability of its own.
• <END> — the token the model emits when it thinks the sentence is finished. Once a candidate produces <END>, that candidate is complete and stops growing.

Why this matters for counting length. When we later divide by the length $T$, we count only the generated tokens — the ones the model actually predicted. The <START> marker is not counted: $T=(\text{number of tokens in the list})-1.$ For example the finished list [<START>, Bonjour, <END>] has $T=3-1=2$ generated tokens.

8. Logarithms: turning products into sums

Multiplying many small probabilities (each below 1) gives a tiny number that a computer can round down to zero — this is called underflow. The logarithm rescues us.

Because probabilities are between $0$ and $1$, their logs are negative (or zero). A probability of $1$ gives $\log 1=0$; smaller probabilities give more-negative logs. So "less likely" = "more negative score". Keep that sign in mind — it explains why every score in the parent note is a negative number, and why closer to zero is better.

Applying fact 1 to our chain-rule product turns it into a friendly sum: $\log P(\mathbf{y}\mid \mathbf{x})={\sum }_{t=1}^T\log P\left(y_t\mid y_{<t},\mathbf{x}\right).$

This sum-of-logs is the score beam search actually adds up step by step.

9. Length normalization and the exponent $\alpha$

A longer sentence has more negative terms in its sum, so raw score punishes length — a good long sentence loses to a mediocre short one. The fix is to divide by length, softened by an exponent $\alpha$ (Greek "alpha"):

${\text{score}}_{\text{norm}}(\mathbf{y})=\frac{1}{T^{\alpha }}{\sum }_{t=1}^T\log P\left(y_t\mid y_{<t},\mathbf{x}\right).$

• $\alpha =1$: divide by full length → the plain average log-prob per token.
• $\alpha =0$: $T^0=1$, so no normalization at all (raw sum).
• $\alpha \in (0.6,0.7)$: a gentle in-between used in practice — some, but not full, forgiveness for length.

This $\alpha$ is a decoding-time knob, cousin to the temperature knob you meet in sampling — both reshape how we choose from the model's probabilities without changing the model itself. The quality of the final $\mathbf{y}$ is then judged against reference translations with a metric like the BLEU score.

10. Beam width $k$

Beam search's rhythm: keep $k$ candidates → expand each into $V$ continuations ($k\times V$ in total) → keep only the best $k$ → repeat. The "beam" is that surviving handful, like a flashlight beam of width $k$ sweeping through the giant tree of sentences.

Prerequisite map

Read it bottom-up: probabilities and the vocabulary feed the branching tree; logs turn the probability product into an addable score; normalization and the width $k$ tame that score; all of it flows into beam search.

Equipment checklist

Cover the right side and answer aloud. If any stumps you, reread its section.