Seq2Seq, Attention & Beam Search, Part 2: Decoding, Beam Search and Where It Lives Today
A trained translation model does not hand you a sentence. At every step it hands you a list that says how likely each possible next word is, and something else has to pick. That pick decides whether you get a careful translation, a dull loop of repeated phrases, or a surprising and useful suggestion. Part 1 built the attention model that produces the list. This part is about the choice made on top of it.
Learning Objectives
After this lesson, you will be able to:
Compare greedy, beam search, and sampling decoders — including length normalization, coverage penalty, and no-repeat-ngram tricks — and pick the right decoder for the right task in 2026
Explain why beam search is a heuristic approximation to exact MAP decoding (which is exponential), why beam=5 is the empirical sweet spot for MT, and why modern LLM inference uses sampling instead
Trace how the next-word probabilities from the attention model in Part 1 become a finished sentence, one decoding step at a time
Run greedy and beam search on a toy model and read why they disagree
In plain words: after training, the model does not give you a sentence. At each step it gives you a list of how likely every possible next word is, and something else has to pick. Picking the single best word every time is quick but can paint you into a corner. Beam search keeps a few options open. Sampling adds controlled randomness when there is no single right answer. This part shows when each one wins and why.
Words you need10 terms
Turning the model's word probabilities into one output sentence.
At every step take the single most likely next word and never look back.
Keep the best k partial sentences alive at every step, extend all of them, and prune back to k.
The number k of partial sentences kept alive. Width 1 is greedy decoding.
The logarithm of a probability. It is never above 0, and adding log-probabilities is the same as multiplying the probabilities.
Dividing a sentence's score by a length penalty so that short sentences do not win just for being short.
Choosing the next word at random, weighted by the model's probabilities, so repeated runs give different text.
A dial that sharpens the probabilities (below 1) or flattens them (above 1) before sampling.
Sampling only from the smallest set of words whose probabilities add up to p, such as 0.9.
Blocking words that would break a rule, such as invalid JSON, by giving them zero probability at each step.
Part 1 ended with a trained model that, at each step, gives a probability to every word in the vocabulary, using attention over the source. A table of probabilities is not a sentence. The step from one to the other is called decoding, and it is a separate engineering choice from the model itself. If you have not read Part 1, the only things you need from it are these: the decoder writes one word at a time, each word is conditioned on the words already written and on a fresh attention-weighted view of the source, and the probability of a whole sentence is the product of its next-word probabilities.
The decoder has learned a distribution p(y_t | y_{<t}, x) over the target vocabulary at every step. Decoding is the process of turning that distribution into an actual output sequence. This is where theory meets production: a model can have perfect cross-entropy loss and still produce garbage at inference time if the decoder is wrong.
At each step, pick the highest-probability token. Repeat until you emit <EOS>.
yt=argymaxp(y∣y<t,x)
Greedy decoding is fast (one forward pass per token) and deterministic. But it commits to each choice irrevocably. There's no looking back when a locally-best token leads to a globally-bad sentence.
Why can a decoder that makes the best choice at every step still miss the best sentence? Open the derivation for a worked case with numbers.
#Beam Search: Approximate Best-First Search Over Sequences
The fundamental observation: at each step, instead of keeping only the single best token, keep the top-k partial sequences, expand each, and prune back to the top-k.
The algorithm:
Start with one beam: [<SOS>], score 0.
At step t, for each of the k current beams: compute the distribution over next tokens. For each beam, generate k candidate extensions (one for each top-k next token). You now have k² candidates.
Score each candidate as the sum of log-probabilities of its tokens.
Prune to the top k candidates. These become the new beams.
When a beam ends with <EOS>, set it aside as a completed hypothesis. Continue until k completed hypotheses or max length.
Return the highest-scoring completed hypothesis.
score(y)=t=1∑∣y∣logp(yt∣y<t,x)
Why sum logs instead of multiplying probabilities? Open the derivation to see that the ranking is identical and the arithmetic is safer.
Small beams such as 4 to 8 are common production defaults, but the best width depends on the language pair and the model. Koehn & Knowles (2017) found that quality rises with the beam only up to an optimal size and then falls: in their experiments the optimum ranged from 4 (Czech-English) to around 30 (English-Romanian), and with length normalisation it was 30 to 50 in almost all cases. The main cause of the fall was shorter translations under wider beams. Stahlberg & Byrne (2019) measured one case directly, an English-German Transformer: greedy search scored 29.3 BLEU and beam 10 scored 30.3.
BLEU rises with a modest beam, then falls for much larger beams. This is the "beam search curse" — bigger beams should be strictly better according to MAP-optimization theory, but empirically they aren't. The cause:
Bigger beams more accurately approximate the MAP solution. That's what the theory says.
But the MAP solution under a trained model isn't actually the best translation. The model is mis-calibrated — its highest-probability output isn't its best translation. Bigger beams find the model's "true" preference, which is often shorter, vaguer, and more generic than the optimal translation.
Practical sweet spot is beam=4 to beam=8 depending on the model and corpus.
This is one of the most studied empirical phenomena in NLP. Stahlberg & Byrne ("On NMT Search Errors and Model Errors", EMNLP 2019) showed that when you actually find the true MAP solution (using exhaustive search), the result is empty sequences — the model assigns higher probability to empty output than to any real translation. Beam=5 is a useful bug, not a feature.
A pure log-probability score systematically prefers short sequences. Why? Each token contributes a negative log-probability (since p < 1, log p < 0). More tokens = more negative additions = lower total score.
The result: beam search will happily output truncated, ungrammatical short outputs rather than full grammatical translations.
The claim that longer sequences always score lower deserves a proof, because it explains the whole need for length normalisation. Open the derivation.
The fix is length normalization. The most common form, from Google's GNMT paper:
Koehn & Knowles (2017) found that shorter translations under wider beams were the main cause of quality loss, and that normalising scores by length helps. In the extreme, Stahlberg & Byrne (2019) found that exact search on an English-German Transformer returned the empty translation for 51.8% of sentences.
Where does the (5 + n) to the power alpha over 6 to the power alpha form come from? Open the derivation to see each piece earn its place.
A second GNMT-style trick: at the end of decoding, penalize hypotheses whose attention distribution didn't cover the source uniformly. This is decode-time coverage (vs the train-time coverage attention of Section 4).
cp(x,y)=βi=1∑Tsrclogmin1,j=1∑∣y∣αij
Combined: final_score = score_norm + cp. This is the formula Google used for production NMT in 2016-2018.
Open the derivation to see exactly what the coverage penalty can and cannot do, and how it links to the output length.
A third production trick: forbid generating any n-gram that has already appeared in the current hypothesis. This prevents the infamous "repetition collapse" where a beam ends up emitting "the the the the the..." or "I'm sorry, I'm sorry, I'm sorry..."
Mechanically: at each decoding step, for each beam, scan the partial hypothesis for n-grams ending at the previous token; mask out any token that would complete a repeated n-gram.
pythonrunnable cell
1
2
3
4
5
6
7
8
9
10
11
def no_repeat_ngram_filter(logits, tokens, n=3):
if len(tokens) < n - 1:
return logits
prefix = tuple(tokens[-(n - 1):])
banned = set()
for i in range(len(tokens) - n + 1):
if tuple(tokens[i:i + n - 1]) == prefix:
banned.add(tokens[i + n - 1])
for tok in banned:
logits[tok] = float("-inf")
return logits
n=3 is standard. This is in HuggingFace's generate() as no_repeat_ngram_size=3 and is the default for many production systems.
What Do You Think?
Without length normalization, beam search consistently prefers shorter outputs. Why?
#Sampling: The Modern Default For Open-Ended Generation
For machine translation, beam search is correct: there is typically one (or a few) best translations and you want to find them. For open-ended generation (story writing, chat, brainstorming) beam search produces dull, generic, repetitive output. The reason is the same beam-search curse: high-probability text is boring text.
Sampling methods (covered in depth in the NLP track's "Decoding Strategies" lesson) trade determinism for diversity:
Temperature sampling. Sample from softmax(logits / T). T=1.0 is normal; T<1.0 makes output more deterministic (sharper distribution); T>1.0 makes output more random.
Top-k sampling. Restrict to the top-k tokens; renormalize; sample. k=40 to k=100 typical.
Top-p (nucleus) sampling. Restrict to the smallest set of tokens whose cumulative probability exceeds p; renormalize; sample. p=0.9 to p=0.95 typical. Holtzman et al. 2019 showed this is better than top-k for open-ended text because it adapts the candidate set size to the entropy of the distribution.
Repetition penalty. Multiply logits of already-emitted tokens by 1/penalty (typical penalty=1.1 to 1.3) to discourage exact repetition.
GPT, Claude, Gemini, and every chat-style LLM in 2026 uses some combination of top-p, temperature, and repetition penalty by default. Beam search is reserved for tasks where there is a clear "right answer": MT, summarization, structured output.
Sometimes you need to guarantee a particular output structure: valid JSON, a regex match, a list from a fixed enum, syntactically-valid code, sentences ending with a specific phrase. Constrained decoding modifies the per-step distribution to enforce these constraints.
The general pattern: at each step, mask out (set to -∞) any token that would violate the constraint, then renormalize and pick (greedy / beam / sample) over the remaining tokens.
JSON schema decoding. At each token position, only allow tokens that are valid continuations of a JSON syntax tree consistent with the schema. Libraries like Outlines, Guidance, and JSONFormer implement this.
Regex-constrained decoding. Only allow tokens that keep the output matching a regular expression. Implemented via finite-state automata.
Forced phrases. If you must emit certain text verbatim, force the corresponding tokens during decoding.
Banned tokens. Prevent emission of specific tokens (profanity filters, name redaction).
Production LLM APIs (OpenAI's response_format, Anthropic's tool-use schema, llama.cpp's grammar parameter) all implement constrained decoding under the hood. It's essentially beam search with a per-token mask.
Quick check
Your team is shipping two features: (a) a Spanish-to-English news translator, (b) a chatbot that writes blog post ideas. Which decoding strategy do you choose for each?
The ideal: find argmax_y p(y | x) over all possible sequences. This is maximum a posteriori (MAP) decoding and would give the model's true best output.
Why we can't: at each step the vocabulary is, say, |V| = 32,000 tokens. A 30-token output has |V|^30 = 32000^30 ≈ 10^135 possible sequences. Even with the universe's age and every atom as a transistor, you can't enumerate this. Exact MAP decoding is NP-hard in general (proof: reduces to weighted Boolean satisfiability).
Beam search is a heuristic approximation. It explores only the top-k extensions at each step, throwing away exponentially many branches. The good branches usually survive because they correspond to common linguistic patterns the model has learned. The bad ones get pruned early. It does not always find the best-scoring sequence: Stahlberg & Byrne (2019) ran exact search on an English-German Transformer and found that beam 10 missed the global best model score on 57.7% of sentences and greedy search on 73.6%, yet beam 10 still scored higher BLEU (30.3 against 29.3 for greedy), because the model's best-scoring output is often the empty string.
The size of the search space deserves a calculation, not just an adjective. Open the derivation to count it, and to count beam search's work for comparison.
Beyond length, beam search has a more subtle bias: it prefers generic, high-frequency outputs. The reason is the same shape of distribution that makes it work — common phrasings have high probability at every step, so they survive every pruning. Distinctive, unusual, or creative phrasings have lower per-step probability and get pruned even when their full-sequence score would be higher.
This is fine for MT (you usually want the standard translation, not a creative one) but is exactly why beam search produces bland chatbot replies. Sampling escapes this by, well, sampling — sometimes the unusual continuation wins, sometimes the common one does, and the distribution over outputs matches the model's actual learned distribution rather than collapsing onto the mode.
Greedy picks A first (because p(A | SOS) = 0.60 > p(B | SOS) = 0.35) and gets a worse total log-probability.
Beam k=1 behaves identically to greedy. Beam=1 is greedy decoding.
Beam k=3 keeps both A and B alive after step 1, then discovers that the B branch has a much better continuation (p(C | B) = 0.95 vs p(C | A) = 0.50), and ends with a higher global probability.
This is the textbook case for beam search. In real MT, the pathology is subtler — instead of a single 0.60 vs 0.35 fork at step 1, there are thousands of forks throughout the decoding tree, and beam search prunes most of them. But the principle is identical: keep alive several mediocre-but-promising prefixes, expand them, and pick the globally best.
What Do You Think?
Beam search with width k=1 is equivalent to what other decoding algorithm?
Self-attention took over the encoder-decoder pattern, but the seq2seq + attention concept is unchanged under the hood of every modern foundation model:
Machine Translation. Meta's NLLB (No Language Left Behind, 200 languages, 2022) uses a transformer encoder-decoder with beam=5 decoding plus length normalization plus coverage penalty. Architecturally it is Bahdanau-2014 with the LSTM replaced by self-attention blocks. Production rule of thumb: beam=4-8 for any translation system.
Speech-to-Text. OpenAI's Whisper (2022) is a transformer encoder-decoder with beam=5 decoding. Same shape as a 2016 LSTM seq2seq, but with self-attention.
Summarization. Google's PEGASUS and Meta's BART are transformer encoder-decoder models. They use beam search with length penalty and trigram-blocking.
Structured generation. JSON-schema-constrained decoding, regex-constrained decoding, and tool-use schemas all run beam search (or sampling) with per-step masking against a finite-state automaton or grammar.
Decoder-only LLMs. GPT, Claude, Gemini, Llama collapse the encoder-decoder split into a single decoder that attends to a context. The cross-attention from decoder-to-encoder becomes self-attention within the prompt. But the math is identical to Luong 2015. When you call an LLM, you are calling beam-search-with-attention's grandchild.
Beam search where it still wins. Code generation (Copilot uses beam-like reranking), formal-verification proof search, structured-output JSON, and machine translation. Anywhere "there is a right answer" the beam wins. Anywhere "there are many valid answers" the sampler wins.
The single biggest shift from 2016 to 2026 is what is being decoded: in 2016 we beam-searched 30-token sentences; in 2026 we sample 100,000-token reasoning traces. But the algorithms (score, softmax, weighted sum, argmax) are identical.
Greedy decoding is myopic. Argmax at every step commits to local optima even when globally-worse than picking the second-best token early.
Beam search keeps top-k partial sequences alive, expands, prunes. Width 4-8 is the empirical sweet spot for MT. Length normalization ((5+|y|)^α / 6^α with α≈0.6) prevents the bias toward shorter outputs. Coverage penalty and no-repeat-ngram are standard production tricks.
Beam search systematically prefers generic, common, shorter outputs. For open-ended generation (chat, creative writing), use sampling (top-p with temperature) instead. For structured/MT/summarization, beam wins.
Exact MAP decoding is intractable. Exponential in sequence length. Beam search is a heuristic approximation. It works because the model has learned distributions where the good prefixes are also high-probability prefixes.
The seq2seq + attention pattern is unchanged in 2026. Transformers replaced LSTMs but kept the math. Every LLM you call today is, mechanically, a descendant of Luong 2015 dot-product attention.
You're decoding from a trained NMT model. Without length normalization, what bias does beam search exhibit?
Where to next. Go to Transformers & Self-Attention to see what happens when you keep the attention and throw out the recurrence entirely: every position looks at every other position in parallel, and that one change produced the architecture behind today's language models. If any step in this part felt shaky, the model that feeds it is in Part 1.