Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

Sequence-to-Sequence Models

Encoders, decoders and the birth of attention.

In 2014 a pair of LSTMs, one reading English and one writing French, outscored a phrase-based statistical translation system. A year later, attention let the decoder look back at every source word, and soft alignments learned from scratch captured how word order differs between languages. This lesson makes the encoder–decoder precise, proves why training on gold prefixes lets errors compound, shows why the most probable output is often not the best one, and dissects the BLEU score that measured it all.

What you’ll learn

  • Define encoder–decoder models as conditional language models, and explain the fixed-vector bottleneck.
  • Write Bahdanau attention as soft alignment, compare score functions, and explain why it shortens gradient paths.
  • Prove the T2ϵT^2\epsilon compounding-error bound behind exposure bias, and describe its remedies.
  • Implement beam search, explain length bias and the beam search curse, and compute BLEU while knowing its limits.

Encoder–decoder models

Sutskever, Vinyals and Le (2014) used two 4-layer LSTMs with 1,000 units per layer, vocabularies of 160,000 source and 80,000 target words, and one trick: reverse the source sentence (but not the target). An ensemble of five such models with beam search scored 34.8 BLEU on WMT'14 English→French, against 33.3 for a phrase-based baseline. Cho et al. (2014) introduced the related RNN encoder–decoder with gated recurrent units. The weak point is the single vector c\mathbf c: Cho et al. and later Bahdanau et al. found the quality of fixed-vector models dropping sharply as sentences grew longer, although Sutskever et al.'s deep LSTMs held up better.

Check your understanding

Reversing the source sentence leaves the average distance between corresponding source and target words unchanged. Why did it still help the LSTM encoder–decoder?

  1. Reversed sentences are shorter after tokenization
  2. The first target words now sit close to the first source words, so some dependencies become short and easy to learn first
  3. It removes the need for an end-of-sentence symbol
  4. It lets the model attend to the source sentence
Show the answer

B. The first target words now sit close to the first source words, so some dependencies become short and easy to learn first

The first source words are read last, right before decoding starts, so the gradient paths between them and the first target words are short. Sutskever et al. argued that this reduced "minimal time lag" lets optimization get started, after which longer dependencies follow.

Attention as soft alignment

Bahdanau, Cho and Bengio (2015) let the context vary with the output step. A bidirectional encoder gives one annotation per source word, hj=[h→j;h←j]\mathbf h_j=[\overrightarrow{\mathbf h}_j;\overleftarrow{\mathbf h}_j]. Before emitting yiy_i, the decoder scores every annotation against its previous state, normalizes the scores with a softmax, and reads a weighted average:

eij=va⊤tanh⁡(Wasi−1+Uahj),αij=eeij∑k=1Txeeik,ci=∑j=1Txαij hje_{ij}=\mathbf v_a^\top\tanh\big(W_a\mathbf s_{i-1}+U_a\mathbf h_j\big),\qquad\alpha_{ij}=\frac{e^{e_{ij}}}{\sum_{k=1}^{T_x}e^{e_{ik}}},\qquad\mathbf c_i=\sum_{j=1}^{T_x}\alpha_{ij}\,\mathbf h_j
αi⋅\alpha_{i\cdot} is a probability distribution over source positions: a soft alignment, learned with no alignment labels, where classical statistical translation models treated alignments as discrete latent variables. In the paper's visualizations, "European Economic Area" aligns with "zone économique européenne" in reversed order.
Score score⁡(s,h)\operatorname{score}(\mathbf s,\mathbf h)FormUsed in
Additive (concat)va⊤tanh⁡(Was+Uah)\mathbf v_a^\top\tanh(W_a\mathbf s+U_a\mathbf h)Bahdanau et al. (2015)
Dots⊤h\mathbf s^\top\mathbf hLuong, Pham & Manning (2015)
General (bilinear)s⊤Wah\mathbf s^\top W_a\mathbf hLuong, Pham & Manning (2015)
Scaled dot productq⊤k/dk\mathbf q^\top\mathbf k/\sqrt{d_k}, with separate value vectorstransformers (Attention & Transformers)
In query–key–value language, the decoder state is the query and the encoder annotations are the keys and values. Vaswani et al. (2017) made attention the whole architecture.
DerivationShorter gradient paths, at quadratic cost
  1. ∂ci∂hj=αij I+∑khk ∂αik∂hj\frac{\partial\mathbf c_i}{\partial\mathbf h_j}=\alpha_{ij}\,I+\sum_k\mathbf h_k\,\frac{\partial\alpha_{ik}}{\partial\mathbf h_j}

    Without attention, the loss at output ii reaches the annotation hj\mathbf h_j only through the final encoder state: a chain of Tx−jT_x-j encoder steps and ii decoder steps, each multiplying by a Jacobian that can shrink the gradient. With attention, differentiating ci=∑kαikhk\mathbf c_i=\sum_k\alpha_{ik}\mathbf h_k gives a direct term:

  2. cost per sentence pair=O(Tx Ty d)  scores (with d-dimensional states)\text{cost per sentence pair}=\order{T_x\,T_y\,d}\ \text{ scores (with }d\text{-dimensional states)}

    So every source word is one step away from every output step, whatever the sentence length. The price is computing TxTyT_xT_y scores per sentence pair, quadratic in length, a cost that self-attention later inherits within a single sequence:

Teacher forcing and the compounding of errors

Maximum-likelihood training conditions every prediction on the gold prefix y<ty_{<t}, a scheme called teacher forcing (Williams & Zipser, 1989). At test time the decoder conditions on its own earlier outputs, prefixes it never saw in training. Ranzato et al. (2016) named the mismatch exposure bias. Imitation learning, where a policy trained on an expert's states must act in its own, gives a theorem that quantifies it.

DerivationProof sketch
  1. 1−pt ≤ ∑s≤tϵs1-p_t\ \le\ \sum_{s\le t}\epsilon_s

    Couple the two policies and let ptp_t be the probability that π\pi has agreed with π⋆\pi^\star at every step up to tt. While no mistake has occurred, π\pi visits exactly the expert's states, so a mistake at step tt on that event has probability at most ϵt\epsilon_t, and

  2. Ct(π)−Ct(π⋆) ≤ ϵt+(1−pt−1) ≤ ∑s≤tϵsC_t(\pi)-C_t(\pi^\star)\ \le\ \epsilon_t+(1-p_{t-1})\ \le\ \sum_{s\le t}\epsilon_s

    At step tt, π\pi's expected cost exceeds the expert's by at most the chance of a mistake now plus the chance of having already left the expert's states, where nothing is guaranteed and the cost can be the maximum, 11:

  3. J(π)−J(π⋆) ≤ ∑t=1T∑s≤tϵs ≤ T∑s=1Tϵs=T2ϵ■J(\pi)-J(\pi^\star)\ \le\ \sum_{t=1}^T\sum_{s\le t}\epsilon_s\ \le\ T\sum_{s=1}^T\epsilon_s=T^2\epsilon\qquad\blacksquare

    Summing over the TT steps, each ϵs\epsilon_s is counted at most TT times:

Teacher forcing is exactly this setting: the reference text plays the expert, the prefix is the state, and the training loss measures ϵ\epsilon on gold prefixes only. Remedies train on the model's own prefixes:

  • DAgger (Ross, Gordon & Bagnell, 2011) queries the expert on states the learner visits, giving bounds linear in TT when mistakes are recoverable.
  • Scheduled sampling (Bengio et al., 2015) feeds the model's own predictions with a probability that grows during training; Huszár (2015) showed that its objective is not a proper scoring rule.
  • Sequence-level training optimizes the test metric directly, with REINFORCE in MIXER (Ranzato et al., 2016) or by minimum risk training (Shen et al., 2016).

The analogy is loose for open-ended text, where many continuations are acceptable and there is no single "mistake", and how much exposure bias matters in practice is debated: degenerate, repetitive text has been traced largely to maximization-based decoding rather than to training (Holtzman et al., 2020).

Decoding: beam search and its failures

The mode arg max⁡ypθ(y∣x)\argmax_{\mathbf y}p_\theta(\mathbf y\mid\mathbf x) ranges over ∣V∣T|V|^{T} sequences, and the model has no Markov structure to exploit, so exact search is infeasible in general. Greedy decoding commits to the best token at each step. Beam search keeps the BB highest-scoring prefixes:

text
BEAM-SEARCH(x, beam size B, max length T)
  beams ← { (⟨s⟩, 0) }                         // (prefix, log-probability)
  finished ← ∅
  for t = 1..T:
      candidates ← { (y·w, score + log p(w | y, x)) : (y, score) ∈ beams, w ∈ V }
      beams ← the B best candidates
      move every hypothesis ending in ⟨/s⟩ from beams to finished
      if beams = ∅ or the best finished score ≥ the best live score: stop
  return the best hypothesis in finished, by score / length penalty

Each step runs the decoder on BB prefixes and selects the top BB of B∣V∣B|V| candidates, O(B∣V∣)\order{B|V|} with a selection algorithm; greedy decoding is B=1B=1. Stopping early is safe because log-probabilities only decrease as a prefix grows.

Predict before you look

Using the probabilities in the bars, how many times more probable is the sentence " sunny." than the greedy output " sunny and warm."?

Show the answer

6.3 ×

P(" sunny.")=0.313×0.30≈0.094P(\text{" sunny."})=0.313\times0.30\approx0.094 and P(" sunny and warm.")=0.313×0.34×0.20×0.70≈0.015P(\text{" sunny and warm."})=0.313\times0.34\times0.20\times0.70\approx0.015. The shared first factor cancels: 0.30/(0.34×0.20×0.70)≈6.30.30/(0.34\times0.20\times0.70)\approx6.3. A locally better step (34%>30%34\%>30\%) led to a globally worse sentence.

The widget's last observation is general. Every token multiplies in a factor below one, so the mode is biased toward short outputs. In translation, larger beams find higher-probability but shorter and worse translations, the beam search curse (Koehn & Knowles, 2017). With exact search, Stahlberg and Byrne (2019) found that for more than half of the sentences of a WMT test set, a transformer translation model's single most probable output was the empty translation. Beam search works partly because it fails to find the mode.

Practical fixes rescore with a length penalty, log⁡p(y∣x)/lp(y)\log p(\mathbf y\mid\mathbf x)/\mathrm{lp}(\mathbf y) with lp(y)=((5+∣y∣)/6)α\mathrm{lp}(\mathbf y)=\big((5+|\mathbf y|)/6\big)^{\alpha} in Google's system (Wu et al., 2016), add coverage penalties, or abandon the mode: minimum Bayes risk decoding samples candidates and picks the one with the highest expected metric against the others.

BLEU and its critics

Think first The candidate "the the the the the the the" is scored against the references "The cat is on the mat" and "There is a cat on the mat". What is its plain unigram precision, and what is its modified unigram precision?

Plain precision is 7/77/7: every word of the candidate appears in a reference. Clipping counts "the" at most twice, its maximum count in a single reference, so the modified precision is 2/72/7. This example from the BLEU paper shows why clipping is needed; the brevity penalty plays the complementary role, since precision alone would reward outputting only a few safe words.

BLEU was designed for comparing systems on whole corpora, and its weaknesses show elsewhere:

  • Blind to meaning: synonyms and paraphrases score zero unless they appear in a reference, and many permutations of a sentence's n-grams score the same (Callison-Burch, Osborne & Koehn, 2006).
  • Sentence level: with no matching 4-gram, the geometric mean makes a sentence's BLEU zero, so sentence-level use needs smoothing and remains unreliable (Reiter, 2018).
  • Reproducibility: tokenization and normalization choices shift scores by amounts comparable to claimed improvements; SacreBLEU standardizes them (Post, 2018).
  • Correlation: learned metrics such as BERTScore (2020) and COMET (2020) agree better with expert error annotations of translations than BLEU does (Freitag et al., 2021).

Key takeaways

  • An encoder–decoder is a conditional language model p(y∣x)=∏tp(yt∣y<t,x)p(\mathbf y\mid\mathbf x)=\prod_tp(y_t\mid y_{<t},\mathbf x); a single context vector is a bottleneck for long inputs.
  • Attention computes a softmax over source positions at every output step: a soft alignment learned without labels, with O(1)\order{1} gradient paths at O(TxTy)\order{T_xT_y} cost.
  • Teacher forcing trains on gold prefixes only; by Ross–Bagnell, per-step error ϵ\epsilon can compound to T2ϵT^2\epsilon, which motivates DAgger, scheduled sampling and sequence-level training.
  • Beam search approximates the mode, but the mode favors short outputs: larger beams can hurt, and exact search often returns the empty translation, hence length penalties and MBR decoding.
  • BLEU combines clipped n-gram precisions with a brevity penalty; it is a corpus-level system comparison, blind to paraphrase and weaker than learned metrics at matching expert judgment.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A decoder makes a mistake with probability ϵ\epsilon per step on gold prefixes, and outputs have length TT. In the worst case, how does its excess expected cost over the reference scale?

  1. TϵT\epsilon
  2. ϵ\epsilon, independent of TT
  3. T2ϵT^2\epsilon
  4. eTϵe^{T\epsilon}
Show the answer

C. T2ϵT^2\epsilon

After a first mistake the model may sit on prefixes it never trained on and pay the maximum cost at every remaining step; summing the chance of having left the expert's states over TT steps gives ∑t∑s≤tϵs≤T2ϵ\sum_t\sum_{s\le t}\epsilon_s\le T^2\epsilon, and some tasks attain this order.

Question 2

Increasing the beam size of a translation model from 5 to 100 lowers its BLEU score. What is the most likely explanation?

  1. The larger beam finds outputs of higher model probability, which tend to be too short: a model error that the small beam's search errors had hidden
  2. The larger beam has more search errors
  3. Beam search with large beams samples randomly
  4. BLEU cannot be computed for long outputs
Show the answer

A. The larger beam finds outputs of higher model probability, which tend to be too short: a model error that the small beam's search errors had hidden

Larger beams are better at finding high-probability sequences, and under the model those are often short or even empty. The quality drop exposes the model's length bias, which is why length normalization is standard.

Question 3

A system's output totals c=10,000c=10{,}000 words on a test set whose effective reference length is r=20,000r=20{,}000. What is BLEU's brevity penalty?

  1. 0.50.5
  2. 11
  3. e−2≈0.14e^{-2}\approx0.14
  4. e−1≈0.37e^{-1}\approx0.37
Show the answer

D. e−1≈0.37e^{-1}\approx0.37

BP=e1−r/c=e1−2=e−1≈0.37\mathrm{BP}=e^{1-r/c}=e^{1-2}=e^{-1}\approx0.37. The exponential penalizes brevity more steeply than the ratio c/rc/r would.

Question 4

Which statement about the attention weights αi1,…,αiTx\alpha_{i1},\dots,\alpha_{iT_x} in Bahdanau et al.'s model is correct?

  1. They are learned from human word-alignment annotations
  2. They are fixed once per sentence, before decoding starts
  3. They are a distribution over source positions, recomputed at every output step from the previous decoder state and each annotation, and learned with no alignment labels
  4. They select exactly one source word per output word
Show the answer

C. They are a distribution over source positions, recomputed at every output step from the previous decoder state and each annotation, and learned with no alignment labels

A softmax over eij=va⊤tanh⁡(Wasi−1+Uahj)e_{ij}=\mathbf v_a^\top\tanh(W_a\mathbf s_{i-1}+U_a\mathbf h_j) gives non-negative weights summing to one, recomputed for every ii; the alignment emerges from maximizing the translation likelihood alone.

Further reading

  • I. Sutskever, O. Vinyals & Q. V. Le, "Sequence to sequence learning with neural networks," NeurIPS (2014).
  • D. Bahdanau, K. Cho & Y. Bengio, "Neural machine translation by jointly learning to align and translate," ICLR (2015).
  • S. Ross & J. A. Bagnell, "Efficient reductions for imitation learning," AISTATS (2010).
  • K. Papineni, S. Roukos, T. Ward & W.-J. Zhu, "BLEU: A method for automatic evaluation of machine translation," ACL (2002).
  • P. Koehn, Neural Machine Translation (Cambridge University Press, 2020).