Everything so far has predicted a sequence from its own past. Translation is harder. The input is a sentence in one language, the output is a sentence in another, and the two have different lengths, different word orders, and no one-to-one correspondence between words. "Le chat noir dort" has the adjective after the noun, "the black cat sleeps" has it before. German puts verbs at the end of clauses, Japanese puts them at the end of sentences. Before 2014, the best systems were phrase-based statistical pipelines with separately trained translation tables, reordering models, and n-gram language models, years of engineering in each.

Then two groups showed that a pair of recurrent networks could learn the whole mapping end to end. Sutskever, Vinyals, and Le (2014) and Cho et al. (2014) built encoder-decoder models, also called sequence to sequence or seq2seq. One RNN reads the source sentence into a vector, and a second RNN, a language model conditioned on that vector, writes the translation. The idea is simple and general (it was soon applied to summarization, dialogue, parsing, speech recognition, and image captioning), and it has one flaw so glaring that fixing it gave us attention. This section builds the model, explains how it is trained and why training and generation disagree, shows how to decode with beam search and why beam search needs length normalization, and then measures the flaw.

Encoder-decoder RNNs

Write the source sentence as $\mathbf x = (x_1, \dots, x_{T_x})$ and the target as $\mathbf y = (y_1, \dots, y_{T_y})$, with $y_{T_y} = \texttt{</s>}$. A translation model is a conditional language model. By the chain rule of §3.1, now conditioned on the source,

The encoder is an RNN (in practice an LSTM or GRU) that reads the source and produces states $\mathbf h_1, \dots, \mathbf h_{T_x}$. Its final state becomes a single context vector, $\mathbf c = \mathbf h_{T_x} \in \R^{d_h}$. The decoder is a second RNN with its own weights. Its state $\mathbf s_i$ starts from the context and is updated with the previous target word,

where $y_0 = \texttt{<s>}$ and $\mathbf E^{\text{tgt}}$ is the target-side embedding table. In plain words, the encoder compresses the source into one vector, and the decoder is an ordinary RNN language model of the target language whose memory starts out holding that vector. Cho et al. went a step further and fed $\mathbf c$ into every decoder step and every output, so the decoder could not forget it, but the information still had to pass through the one vector.

   encoder                                    decoder
   le → chat → noir → dort ═══ c ═══▶ s1 → s2 → s3 → s4 → s5
   h1    h2     h3     h4             ↑    ↑    ↑    ↑    ↑
                                     <s>  the black cat sleeps
                                      ↓    ↓    ↓    ↓    ↓
                                     the black cat sleeps </s>

Training maximizes $\sum \log p(\mathbf y \mid \mathbf x)$ over a parallel corpus of sentence pairs. The gradient flows from every target word back through the decoder, through $\mathbf c$, and into every step of the encoder.

Teacher forcing and exposure bias

How exactly is the decoder trained? At step $i$ it needs the previous word $y_{i-1}$ as input. During training we have the true target sentence, so we feed the true previous word, regardless of what the model would have predicted. This is called teacher forcing (Williams and Zipser 1989). The decoder's inputs are the target shifted right by one position, and the loss is the cross-entropy at every position,

Teacher forcing is efficient and stable. Every position's loss can be computed from known inputs, and with a Transformer decoder all positions are computed in parallel, which is precisely how GPT is trained in §6.3. In a minibatch, sentences have different lengths, so they are padded and the padded positions are excluded from the loss.

import numpy as np

def shift_right(Y, bos, pad):
    return Y

def masked_ce(logits, Y, pad):
    z = logits - logits.max(-1, keepdims=True)
    nll = np.log(np.exp(z).sum(-1)) - np.take_along_axis(z, Y[..., None], -1)[..., 0]

Training and generation see different inputs

Here is the catch. At generation time there is no true target to feed. The decoder must condition on its own previous predictions. During training it only ever saw perfect prefixes, so the first time it makes a mistake, it is in a situation it was never trained on. Ranzato et al. (2016) named this mismatch exposure bias. The model is never exposed to its own errors during training, so it has not learned to recover from them, and one wrong word can derail the rest of the sentence.

A toy calculation shows why this matters for long outputs. Suppose that given a correct prefix the model picks a wrong token with probability $\epsilon = 0.02$, but once its prefix contains an error it is confused and errs with probability $\epsilon' = 0.2$ at every later step. Under teacher forcing, the measured per-token error is just $\epsilon$. At generation time the errors compound.

For short outputs the two error rates are close. For a 100-token output, free-running generation makes several times as many errors per token as teacher-forced evaluation suggests, because most sentences contain an early mistake and every later token pays for it. This is why a model can look excellent on teacher-forced loss and still produce bad long generations.

Several remedies have been proposed. Scheduled sampling (Samy Bengio et al. 2015) gradually replaces some true previous tokens with the model's own samples during training, so it learns to continue from imperfect prefixes. Sequence-level training (Ranzato et al. 2016, and minimum risk training) optimizes a score of whole generated sequences, such as BLEU, with reinforcement learning, so training sees exactly the generation process. How much exposure bias hurts large modern models is debated, and teacher forcing remains the default because it is so efficient. But the idea of training on the model's own outputs came back in a big way. It is the core of reinforcement learning from human feedback in §16.4, of RL for reasoning in §18.4, and of on-policy distillation, where a student learns from a teacher's feedback on the student's own samples.

The fixed-vector bottleneck

Now the flaw. Every bit of information about the source sentence must pass through $\mathbf c$, one vector of $d_h$ numbers, no matter how long the sentence is. The decoder cannot look back at the words. It gets one summary, written by an encoder that did not know which details the decoder would need.

How much fits in one vector? The widget below runs an idealized experiment. Each of $n$ words, drawn from a 24-word vocabulary, adds a random position-specific code to a single $d$-dimensional vector, and then we try to read every word back out by matching codes. This is the best case for a linear encoder, with no training noise at all. Compare it with keeping all $n$ vectors, which is what attention will do.

The capacity of one vector is real and finite. Interference grows with every word. With $d = 32$, recovery is already down to about half at $n = 8$, a quarter of $d$, because each stored word adds noise of the same size as the signal of every other word (the matching score of the right code grows like $d$, the noise like $\sqrt{nd}$, so reading back is reliable only while $n$ is well below $d$). And a leaky memory loses the beginning of the sentence first, which is exactly what reversing the source compensated for. A trained LSTM encoder is not a random linear code, but the same pressure applies. Cho et al. (2014) studied this directly in On the Properties of Neural Machine Translation and found that the encoder-decoder's translation quality degraded rapidly as sentences got longer. Bahdanau et al. (2015) showed the same curve for their baseline encoder-decoder trained on sentences of up to 50 words, while their attention model stayed flat.

We can watch it happen in a real model. The PyTorch block below trains a GRU encoder-decoder, with teacher forcing, to reverse sequences of 3 to 12 digits, a task that needs every input token. It then measures token accuracy by length, both teacher-forced and in free-running greedy generation.

Both effects of this section show up in one table. Accuracy falls steadily with length even under teacher forcing, because the context vector cannot hold long inputs, and it falls faster in free-running generation, where every early mistake is fed back in. Exact reversal of a 12-digit sequence essentially never succeeds. Hold on to these numbers, because §3.6 trains the same model with attention.

Decoding means searching

Training gives us $p(\mathbf y \mid \mathbf x)$. To translate, we want the most probable output,

Exact search is hopeless. There are $V^n$ sequences of length $n$, and because each word's probability depends on all earlier words, nothing like dynamic programming applies. We need a heuristic.

Greedy decoding takes the most probable word at every step and never looks back. It is fast, and it is often wrong in a specific way. The most probable first word can lead into a region where every continuation is mediocre, while a slightly less probable first word leads to a far better sentence. Greedy cannot undo a choice.

Beam search keeps several options open. It maintains a beam of the $K$ best partial hypotheses (the beam width). At each step it extends every hypothesis in the beam by every possible next token, scores each extension by its total log-probability, and keeps the $K$ best. When an extension ends in </s>, that hypothesis is complete. It leaves the beam and joins a list of finished candidates. Search stops when no live hypotheses remain or a maximum length is reached, and the best finished candidate wins.

In plain words, beam search is greedy decoding that hedges its bets $K$ ways. With $K = 1$ it is exactly greedy. With $K = V^n$ it would be exhaustive search. Each step costs $K$ forward passes of the decoder (batched together) and a top-$K$ selection over $KV$ candidates, so the total cost is $O(nKV)$ plus $K$ times the cost of greedy decoding. Sutskever et al. found that their model "performs well even with a beam size of 1, and a beam of size 2 provides most of the benefits of beam search". Typical machine translation systems used beams of 4 to 12.

The widget below runs beam search on a tiny hand-built decoder for "le chat noir dort". Each column is one decoding step and each box is a candidate with its total log-probability. Start with $K = 1$, then raise it one step at a time, leaving the length normalization slider at 0.

Three lessons are in the widget. Greedy decoding chooses "the" because it is the most likely first word (0.40 against 0.34 for "a"), but after "the" every continuation is uncertain, and it ends at a total log-probability of $-3.33$. With $K = 2$ the beam keeps "a" alive, and "a black cat sleeps" wins at $-1.93$, a sentence the model likes $e^{1.4} \approx 4$ times more. And at $K = 3$ something strange happens. The empty translation, an immediate </s> with probability 0.18, enters the beam, and with log-probability $\log 0.18 = -1.71$ it beats every real translation.

import numpy as np

def beam_search(step, eos, K, max_len, alpha=0.0):
    prefix, logp = (), 0.0                          # greedy decoding, ignores K and alpha
    for _ in range(max_len):
        lp = step(prefix); t = int(np.argmax(lp))
        prefix, logp = prefix + (t,), logp + lp[t]
        if t == eos:

Why beam search needs length normalization

The empty translation is not a bug in the toy. It is a property of the objective. Every token multiplies in a probability less than one, so every extra token lowers $\log p(\mathbf y \mid \mathbf x)$. Short outputs are favored automatically, and the more thoroughly you search, the more likely you are to find a short output the model scores highly. A wider beam is a better optimizer of a flawed objective.

This is well documented in real systems. Koehn and Knowles (2017) listed it among six challenges for neural translation, finding that beam search "only improves translation quality for narrow beams and deteriorates when exposed to a larger search space". Stahlberg and Byrne (2019) ran exact search for a Transformer translation model on English-German news and found that "for 51.8% of the sentences, NMT assigns the global best model score to the empty translation". Beam search works partly because it fails to find the model's true optimum. The search errors cancel a model error.

The standard fix is to normalize the score by length,

In plain words, compare hypotheses by their (roughly) average log-probability per token instead of their total. The exponent $\alpha \in [0, 1]$ interpolates between no normalization ($\alpha = 0$) and a full per-token average ($\alpha = 1$). The second form is the one Google's neural machine translation system used (Wu et al. 2016), together with a coverage penalty that rewards hypotheses that attend to every source word. Their final setting was $\alpha = 0.2$ for the length penalty and $\beta = 0.2$ for the coverage penalty, tuned on development data. In the widget, dividing by $|\mathbf y|^\alpha$ with any $\alpha$ of 0.1 or more restores "a black cat sleeps" at $K = 3$, while the gentler GNMT penalty needs $\alpha$ of about 0.25.

A worked check by hand. "a black cat sleeps </s>" has probability $0.34 \times 0.85 \times 0.9 \times 0.62 \times 0.9 \approx 0.145$, so $\log p = -1.93$ over 5 tokens, and the empty output has $\log p = \log 0.18 = -1.71$ over 1 token. With $\alpha = 0.6$ the scores are $-1.93/5^{0.6} = -1.93/2.63 = -0.73$ against $-1.71/1 = -1.71$, so the real sentence wins comfortably.

import numpy as np

def greedy_decode(step, eos, max_len):
    raise NotImplementedError

def exhaustive_best(step, eos, max_len, alpha=0.0):
    raise NotImplementedError

BLEU, briefly

How do we score a translation? The dominant automatic metric for a decade was BLEU (Papineni et al. 2002), which compares n-grams of a candidate with those of one or more reference translations. Its two ingredients are modified n-gram precision and a brevity penalty.

For each $n$ from 1 to 4, count the candidate's n-grams, but clip each n-gram's count at the maximum number of times it appears in a reference, so that "the the the the" cannot get credit for one "the" four times. The modified precision $p_n$ is the total clipped count divided by the total number of candidate n-grams, summed over the whole test corpus. Precision alone rewards very short outputs (a one-word candidate can be perfectly precise), so BLEU multiplies by a penalty for candidates shorter than the references. With $c$ the total candidate length and $r$ the total reference length,

In plain words, BLEU is the geometric mean of the 1- to 4-gram precisions, discounted when the output is too short. A worked example with one sentence. Reference "the black cat sleeps on the mat", candidate "the cat sleeps on the mat". Unigrams match 6 of 6, bigrams 4 of 5 ("the cat" is not in the reference), trigrams 3 of 4, and 4-grams 2 of 3, so the geometric mean is $(1 \cdot 0.8 \cdot 0.75 \cdot 0.667)^{1/4} = 0.4^{1/4} \approx 0.795$. The candidate has 6 words against 7, so $\operatorname{BP} = e^{1 - 7/6} \approx 0.846$, and BLEU $\approx 0.673$, usually reported as 67.3.

from collections import Counter
import math

def corpus_bleu(hyps, refs, N=4):
    raise NotImplementedError

BLEU is cheap, language-independent, and correlates with human judgments at the corpus level, which is why it dominated. It is also crude. It rewards surface overlap, so a correct paraphrase scores badly, it says nothing about meaning or fluency at the sentence level, and the same model can get different BLEU from different tokenization and normalization choices, which is why Post (2018) proposed the standardized SacreBLEU. Character-level metrics like chrF and learned metrics like COMET, which compare embeddings with a trained model, correlate better with human judgment and are now preferred in translation research. The broader lesson, that automatic metrics are proxies with blind spots, returns in every evaluation chapter of this book (§6.6, and the difficulty of evaluating language models in general).

The bottleneck, stated plainly

Step back and look at what the encoder-decoder asks of its context vector. The decoder must produce a word-by-word translation, and for each word it needs specific facts about specific source words (which noun this adjective modifies, the tense of that verb, the spelling of a name). All of that must have been packed into $\mathbf c$ in advance, by an encoder that did not know which facts would be needed in which order. When it writes the tenth target word, the decoder cannot go back and reread the source.

That is not how a human translator works. A human reads the sentence, then while writing each target word looks back at the relevant part of the source. Bahdanau, Cho, and Bengio put it precisely in 2014. The fixed-length vector is a bottleneck, and the decoder should be allowed to search the source for the parts relevant to the word it is about to generate. That search is attention, and it is the next section.

Read more

• Sutskever, Vinyals, and Le (2014). Sequence to Sequence Learning with Neural Networks. Deep LSTM encoder-decoders, source reversal, and beam search results.
• Cho et al. (2014). Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation, and Cho et al. (2014), On the Properties of Neural Machine Translation, Encoder-Decoder Approaches. The encoder-decoder with the gated unit, and the analysis of how it degrades with length.
• Ranzato, Chopra, Auli, and Zaremba (2016). Sequence Level Training with Recurrent Neural Networks. Exposure bias, named and attacked with sequence-level training. See also Samy Bengio et al. (2015), Scheduled Sampling.
• Koehn and Knowles (2017). Six Challenges for Neural Machine Translation, and Stahlberg and Byrne (2019), On NMT Search Errors and Model Errors, Cat Got Your Tongue?. Why wider beams can hurt.
• Wu et al. (2016). Google's Neural Machine Translation System. Length and coverage penalties in a production system (Section 7).
• Papineni, Roukos, Ward, and Zhu (2002). BLEU, a Method for Automatic Evaluation of Machine Translation, and Post (2018), A Call for Clarity in Reporting BLEU Scores.
• Jurafsky and Martin. Speech and Language Processing, Chapter 13, Machine Translation. Encoder-decoders, beam search, and MT evaluation.

Watch next

▶

▶

▶