Seq2Seq, Attention & Beam Search: Bridging RNNs to Transformers
In September 2016, Google replaced ten years of statistical phrase-table machinery with a single neural network — eight stacked LSTMs wired into an encoder-decoder shape, equipped with attention, and decoded with beam search. Translation error rates dropped by roughly 60 percent on some language pairs overnight. The Google Neural Machine Translation paper became one of the most-cited engineering papers of the decade, and beam search width 12 became the de facto production setting for machine translation. But the real story is the mechanism that powered the leap: a graduate student named Dzmitry Bahdanau had two years earlier asked a very small question — what if the decoder could look back? — and that question quietly invented half of the transformer.
Learning Objectives
After this lesson, you will be able to:
Diagnose the fixed-context-vector bottleneck in vanilla encoder-decoder LSTMs — why compressing a 100-token sentence into one hidden state catastrophically hurts BLEU on long sequences — and articulate the precise fix attention provides
Derive Bahdanau (additive) and Luong (multiplicative) attention from first principles, prove they are computing a learned weighted dictionary lookup over encoder states, and trace the lineage to scaled dot-product self-attention in transformers
Implement scaled dot-product attention from scratch in numpy on a toy 3-token-source / 2-token-target example, and read the resulting alignment matrix
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
Don't worry if the math notation looks dense — every formula in this lesson is doing one thing: computing a similarity score between something the decoder is asking for and every thing the encoder remembers, then averaging the encoder's memories weighted by that similarity. That single sentence is the entire attention mechanism. Once you see it once, you see it everywhere.
The vanilla encoder-decoder architecture, in one picture:
Source: "Le chat noir dort sur le canapé" (7 tokens)
ENCODER (LSTM)
Le → chat → noir → dort → sur → le → canapé
\
c (1000-dim "thought vector")
/
DECODER (LSTM)
<SOS> → "The" → "black" → "cat" → "sleeps" → "on" → "the" → "couch" → <EOS>
The encoder runs left-to-right (or bidirectionally), producing a hidden state at every step. The vanilla seq2seq throws away all of them except the final one. That final hidden state is the "thought vector" — the entire sentence's meaning, compressed.
The decoder is initialized with this thought vector and then generates the target sequence autoregressively: at each step it predicts a token distribution, samples or argmaxes a token, and feeds that token back as input to the next step.
#The Symptom: BLEU Drops Off A Cliff On Long Sentences
Bahdanau et al. ran the experiment that exposed the bottleneck. They trained two systems on the same English-French data: vanilla seq2seq (no attention) and seq2seq with attention. They then plotted BLEU as a function of source-sentence length.
Source length
Vanilla seq2seq BLEU
Seq2seq + Bahdanau attention
Gap
1-15 tokens
28.4
29.3
+0.9
15-30 tokens
24.8
28.1
+3.3
30-50 tokens
18.6
27.4
+8.8
50+ tokens
12.1
25.8
+13.7
(Approximate numbers from Bahdanau et al. 2015, Figure 2 — exact values varied by language pair and corpus, but the shape was identical everywhere they tried.)
The story is unambiguous: as source sentences get longer, vanilla seq2seq collapses. The thought vector cannot hold more information than its dimension, and information loss compounds catastrophically beyond ~30 tokens.
What Do You Think?
The encoder's final hidden state c is a 1000-dimensional vector. Roughly how much information (in bits, naively) can it hold?
Let the decoder look back at every encoder hidden state, not just the last one.
That is it. That is the entire conceptual leap. Once you grant the decoder access to the full sequence of encoder states [h_1, h_2, ..., h_{T_src}], instead of just h_{T_src}, the bottleneck vanishes. The question becomes: at each decoder step, how should the decoder combine those encoder states into a useful summary?
The answer is attention — a learned, content-aware weighted average.
Recap: The LSTM cell that builds the encoder's hidden statesInteractive
Loading visualization...
Before we add attention, ground yourself in what the encoder hidden states are. Each h_i is the LSTM cell's output at source position i — a vector that encodes everything the LSTM saw from position 1 up through position i. Step through the LSTM gates and notice how h_i accumulates context. Attention will treat this entire sequence [h_1, ..., h_{T_src}] as a memory bank the decoder can query.
At each decoder step j, for every encoder position i, compute an alignment score e_ij that measures how well the encoder state h_i matches the decoder's current information need s_:
eij=v⊤tanh(Whhi+Wssj−1)
The matrices W_h and W_s are learned during training. They project both states into a shared attention space of dimension A (typically 256 or 512). The vector v learns to score how aligned the projected states are.
That is the entire algorithm. Three small additions to vanilla seq2seq — score, softmax, weighted sum — gave Bahdanau, Cho, and Bengio +13 BLEU on long sentences.
Watch the decoder's attention shift across the source sentence at each output stepInteractive
Loading visualization...
Step through the decoder one output token at a time. Watch the attention distribution α_ij change — the heatmap should highlight the source word(s) most relevant to the current target word. For translation, attention tends to learn soft alignment: each target word attends to the corresponding source word, with some smearing across nearby positions.
The dot-product variant is computationally trivial — one matrix-vector multiplication gives you all the scores. Compare with Bahdanau's additive form, which requires a tanh and two separate projections.
By 2017, the field had largely converged on dot-product attention because:
Speed. One batched matmul instead of a tanh-MLP per (i, j) pair.
Parallelism. With pre-computed encoder states, you can compute all scores for all decoder steps in a single matmul of shape (T_tgt, H) @ (H, T_src) = (T_tgt, T_src). This is exactly what self-attention does at every layer.
Empirical equivalence. On standard MT benchmarks, dot-product and additive attention scored within noise of each other (Luong 2015, Vaswani 2017).
Hardware fit. GPUs are essentially matmul engines. Anything that reduces to a matmul wins.
What Do You Think?
Bahdanau (additive) vs Luong (dot-product) — which is computationally cheaper, and why does it matter for transformer-scale models?
Here is the conceptual punchline: Luong's dot-product attention is mechanically identical to a single head of self-attention, applied between two sequences (decoder querying encoder). The transformer's contribution was three-fold:
Apply attention within a single sequence — every token attends to every other token (self-attention).
Rescale by 1/sqrt(d_k) to stabilize softmax gradients when hidden dimensions are large.
Use separate learned projections for queries, keys, and values (Q, K, V) instead of using the hidden state directly for all three roles.
Everything else — the softmax, the weighted sum, the parallel matmul — was already in Luong (2015). When we get to the transformers lesson, you will see this same math, the same dataflow, just applied recursively in a different topology. The DNA is identical.
Three small but important refinements appeared between 2015 and 2017, addressing pathologies that vanilla attention suffered from. They are worth knowing because they survive into the LLM era as inductive biases and as architectural ideas.
The pathology: vanilla attention can attend to the same source position repeatedly across many decoder steps. This causes two failure modes:
Over-translation. A single source word generates many target tokens (the model keeps "saying it again").
Under-translation. Some source words are never attended to and get dropped from the output.
The fix: maintain a coverage vector cov_j = Σ_{j' < j} α_{ij'} — a running sum, over all previous decoder steps, of the attention probability assigned to each source position. Feed this coverage vector into the score function as an additional input:
eij=v⊤tanh(Whhi+Wssj−1+Wccovij)
Tu et al. reported BLEU improvements of +1.0 to +1.5 on Chinese-English MT, and qualitatively cleaner output (fewer dropped words). Modern transformer decoders typically don't use explicit coverage — they pick up the same behavior implicitly from scale — but coverage remains a useful inductive bias for low-resource settings.
#Copy Mechanism (CopyNet, See et al. 2017; Pointer Networks, Vinyals et al. 2015)
The pathology: vocabularies are finite. If the source contains a rare named entity ("Tashkent") or a number ("17,432") that the decoder's output vocabulary doesn't contain, the model can't output it — even though the right thing to do is obviously to copy it verbatim.
The fix: at each decoder step, the model learns a soft switch between two modes:
Generate. Sample from the normal output distribution over the target vocabulary.
Copy. Pick a source token directly using the attention distribution as a copy probability.
Copy mechanisms transformed abstractive summarization in 2017 — the See et al. "Get to the Point" paper showed that CopyNet on news summarization beat all prior systems by a wide margin precisely because news articles are full of names, numbers, and quotes that should be copied verbatim. Modern LLMs implicitly learn the same behavior at scale: GPT-4 can copy a name from a 100K-token document because its attention naturally produces high copy-like weights on relevant spans. But the explicit copy switch survives in production code-generation systems and structured-output models where you need to guarantee exact copying.
A close cousin: pointer networks output only indices into the source — useful for problems like sorting, convex hulls, and combinatorial optimization where the output vocabulary IS the input. Mechanically: skip the vocabulary projection entirely, just output argmax_i α_{ij} at each step. Vinyals showed this worked for variable-output-size combinatorial problems where standard seq2seq has no good way to express "the answer is a permutation of the input."
Quick check
You're building a seq2seq model that translates user error reports into structured bug-report JSON. The reports contain product names ('iPhone 17 Pro Max'), error codes ('ERR_NET_503'), and version strings ('v2.7.14-beta') that should appear verbatim in the JSON output. Which mechanism most directly addresses this need?
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.
#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.
Studies on machine translation (Sutskever 2014, Wu et al. GNMT 2016, Koehn & Knowles 2017) consistently find:
Beam width
Typical BLEU on WMT En-Fr
1 (greedy)
26.5
2
28.1
5
28.9
10
28.7
50
28.0
BLEU goes up from beam=1 to beam=5, then goes down for 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 fix is length normalization. The most common form, from Google's GNMT paper:
Without length normalization, beam=5 on a typical MT model produces outputs roughly 30% shorter than the reference. With normalization at α=0.6, lengths match reference within 5%.
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.
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. Empirically, beam search recovers ~95-98% of the score that exact search would find on translation tasks (when exhaustive search is feasible on small toy models, you can compare directly).
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.
#Part 6: MathPlayground: Implement Attention And Beam Search From Scratch
Loading visualization...
Read through the output. Three things should jump out:
The attention distribution is peaked on the source position that matches the decoder's query (h_2 = "chat" matches the decoder's preparation to emit "cat"). This is what learned alignment looks like.
The context vector is not equal to any single h_i. It's a blend, weighted toward h_2 but with non-zero contributions from h_1 and h_3. This blend is what the decoder uses going forward.
The full attention computation reduces to two matmuls (scores = H @ s, context = α @ H) plus a softmax. That's it. The whole transformer revolution is built on this primitive applied at every layer with learned projections.
Visualize a learned MT alignment — how attention naturally recovers word-level alignmentInteractive
Loading visualization...
This is the kind of heatmap Bahdanau et al. published in 2014 that made the field gasp. The diagonal-ish pattern was learned end-to-end from translation pairs alone — no one annotated alignments; the model figured them out as a side effect of getting better at translation. Off-diagonal mass corresponds to genuine syntactic reordering (subject-verb-object swaps, adjective-noun position differences). The model not only translates — it understands word-level correspondences, for free.
Loading visualization...
What you should see in the output:
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.85 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.
The bottleneck. Vanilla seq2seq compresses the entire source into one fixed-size thought vector. Information loss is catastrophic for long sequences — BLEU collapses on sentences over 30 tokens.
Bahdanau additive attention (2014). Let the decoder look back at every encoder hidden state with learned weights computed by a small MLP. Score = v^T tanh(W_h h_i + W_s s_{j-1}). Solved the bottleneck and quietly seeded the transformer.
Luong dot-product attention (2015). Replaced the MLP with a dot product. Same alignment quality, dramatically cheaper, parallelizable as a single matmul. This is the math that survived into self-attention.
Coverage, copy, and pointer mechanisms address attention's pathologies: over/under-translation (coverage), rare-vocabulary copying (CopyNet), and combinatorial outputs (pointer networks). They survive into the LLM era as inductive biases and as explicit features in structured-output systems.
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.
What is the precise computational reason additive (Bahdanau) attention scales worse than multiplicative (Luong) attention as sequence length grows?
Attention gave the decoder a memory of the whole source; beam search gave it a way to look past its first instinct. Up next: how a small team at Google in 2017 noticed you could keep the attention and throw out the recurrence — and ended up inventing the transformer.