Neural Machine Translation

Neural Machine Translation frames translation as learning a conditional probability distribution $P(y \mid x; \theta)$ over target-language sentences $y = (y_1, \dots, y_T)$ given a source sentence $x = (x_1, \dots, x_S)$. The distribution factors autoregressively by the chain rule of probability:

An encoder network converts the source sequence into a set of contextualized vector representations; a decoder network, conditioned on those representations through an attention mechanism, generates the target sequence one token at a time. This is precisely the Encoder-Decoder Architecture combined with Attention Mechanism in NLP, applied to the specific task where inputs and outputs are sentences in different languages. Three distinct algorithmic problems sit inside "doing NMT," and it is important to keep them separate. Training is a supervised learning problem: given parallel sentence pairs $(x^{(i)}, y^{(i)})$, adjust $\theta$ to maximize $\sum_i \log P(y^{(i)} \mid x^{(i)}; \theta)$, typically using teacher forcing (feeding the true previous target token as decoder input, rather than the model's own prediction, at each training step). Decoding (also called inference) is a search problem: at test time there is no gold target, so the system must search over the exponentially large space of possible output sentences to find one with high probability under the trained model; beam search is the standard approximate solution. Evaluation is a measurement problem: given a machine-produced translation and one or more human reference translations, produce a number that predicts human judgments of quality; BLEU is the classical automatic metric for this.

Training-time computation. During training, the encoder reads the entire source sentence (usually with a bidirectional recurrent network or a Transformer stack, so each token's representation depends on the whole sentence) and produces representations $h_1, \dots, h_S$. The decoder is unrolled step by step. At step $t$, it computes an attention distribution over the encoder states, forms a context vector $c_t$, and combines $c_t$ with its own hidden state to produce a distribution over the target vocabulary for $y_t$. Teacher forcing means the decoder's input at step $t$ is the gold token $y_{t-1}^{\text{true}}$, not its own previous guess — this stabilizes training and lets the whole sequence be scored in one parallel pass (or one efficient recurrence), but it creates a train/test mismatch called exposure bias, discussed further below.

Decoding-time computation. At inference, there is no gold sequence. The obvious approach — greedily pick $\arg\max_{y_t} P(y_t \mid y_{<t}, x)$ at every step — is fast but can commit to an early token that forecloses a much better full sentence, because local greedy choices are not guaranteed to compose into a globally optimal sequence. Exhaustive search over all $|V|^T$ possible sequences is intractable. Beam search is the practical middle ground: maintain the $k$ most promising partial hypotheses at each step (a "beam" of width $k$), extend each by one token, score all $k \times |V|$ extensions, and keep only the top $k$ again. It is a form of pruned breadth-first search guided by the model's own probability estimates. ``` function BEAM_SEARCH(source x, model M, beam_width k, max_len T): encode source once: enc_states <- M.encode(x)

# each hypothesis: (token_sequence, log_probability, decoder_state, is_finished) beam <- [ ([""], 0.0, M.init_decoder_state(enc_states), false) ] completed <- [] for t in 1 .. T: candidates <- [] for (seq, logp, state, done) in beam: if done: candidates.append( (seq, logp, state, done) ) # keep finished hyps as-is continue

# one decoder step: distribution over next token dist, new_state <- M.decode_step(seq[-1], state, enc_states) top_k_tokens <- TOP_K(dist, k) # cheap local pruning before global pruning for token in top_k_tokens: new_logp <- logp + log(dist[token]) new_seq <- seq + [token] is_end <- (token == "") candidates.append( (new_seq, new_logp, new_state, is_end) )

# normalize by length to avoid favoring short hypotheses (see Complexity section) score(seq, logp) := logp / length_penalty(len(seq)) candidates.sort_by(score, descending) beam <- candidates[0 : k] for hyp in beam: if hyp.is_finished: completed.append(hyp) beam <- [h for h in beam if not h.is_finished] if beam is empty: break all_hyps <- completed + beam return argmax over all_hyps of score(seq, logp) ``` Two design choices deserve emphasis. First, pruning to $k$ before re-expanding at the next step is what keeps the algorithm polynomial rather than exponential — without it, the frontier would grow by a factor of $|V|$ every step. Second, raw log-probability sums are monotonically decreasing (more negative) as sequences get longer, since every factor $P(y_t \mid \dots) \le 1$; without a length correction, beam search is biased toward short, truncated outputs, which is why a length penalty (dividing by $|y|^\alpha$ for some $\alpha \in [0,1]$, or an additive variant) is applied before ranking.

Where BLEU fits. After decoding produces a full hypothesis sentence, BLEU compares it against one or more human reference translations using overlapping n-grams, described precisely in the next section. Together, training (learn $P(y\mid x)$), decoding (search for good $y$ under that model), and evaluation (score the resulting $y$ against references) constitute the complete NMT pipeline.

Training complexity. For a single sentence pair of source length $S$ and target length $T$ with hidden dimension $d$ and vocabulary size $|V|$, one training step costs $O(S \cdot d^2 + T \cdot d^2 + T \cdot S \cdot d)$ for the recurrent/attention computations (encoder self-processing, decoder self-processing, and the $T \times S$ attention score matrix) plus $O(T \cdot d \cdot |V|)$ for the output softmax layers. Since teacher forcing supplies the gold prefix at every step, the entire target sequence's losses can be computed with one forward pass (parallelizable across $t$ for Transformer decoders, sequential but still single-pass for RNN decoders) — there is no search during training, only supervised loss computation, so this cost is polynomial and exact.

Decoding complexity — why beam search, and why it is not exact. The true decoding objective is

over all finite sequences $y$, an exponentially large search space ($|V|^T$ candidates for length-$T$ outputs). Exhaustive maximization is intractable for any realistic vocabulary. Greedy decoding (beam width $k=1$) costs $O(T \cdot |V| \cdot d)$ — linear in output length — but is a purely local heuristic with no lookahead: choosing the highest-probability token at step $t$ can lock in a prefix from which no high-probability continuation exists, even though a slightly lower-probability token at step $t$ would have opened onto a much better full sentence. Beam search with width $k$ costs $O(T \cdot k \cdot |V| \cdot d)$: at each of $T$ steps, each of the $k$ hypotheses is extended over $|V|$ possible next tokens (an $O(k \cdot |V|)$ scoring pass, dominated by $d$-dimensional decode-step computation), then re-pruned to $k$. This is exponentially cheaper than exhaustive search while retaining a bounded amount of lookahead capacity — the $k$ parallel hypotheses act as a beam of alternate futures rather than a single committed path. Correctness argument (approximation, not exactness). Beam search is not guaranteed to find the global maximizer of $P(y\mid x)$; it is a heuristic pruned search, and the pruning at each step is the source of approximation error — a hypothesis that ranks outside the top $k$ at step $t$ is discarded even if some suffix from it would eventually dominate. Formally, larger $k$ can only improve or maintain the achieved score relative to smaller $k$ under the same scoring function, because the set of hypotheses retained by beam width $k$ is a superset of those retained by any $k' < k$ at every step (monotonicity in beam width). This gives a partial correctness guarantee: beam search score is monotonically non-decreasing in $k$, converging to the true $\arg\max$ as $k \to |V|^T$ (impractical) or, more usefully, empirically converging quickly for well-trained models because probability mass concentrates sharply on a small set of plausible continuations. In practice, however, very large $k$ can even hurt end-task quality (measured by BLEU) despite improving the model's own log-probability score, an empirically documented mismatch between what the model considers likely and what humans consider good — a symptom of length bias and calibration issues in the trained distribution, not a bug in the search algorithm itself.

BLEU: definition and correctness as a proxy metric. BLEU (BiLingual Evaluation Understudy) scores a candidate translation $C$ against reference(s) $R$ using modified n-gram precision: for each n-gram (typically $n=1,\dots,4$), count matches between candidate and reference, but clip each n-gram's count in the candidate at the maximum number of times it appears in any single reference (this clipping is essential — without it, a degenerate candidate that repeats one high-frequency word could score perfect precision). Formally, for n-grams:

Precision alone rewards short outputs (a one-word candidate that happens to match can score $p_1 = 1$), so BLEU multiplies by a brevity penalty BP that penalizes candidates shorter than the reference:

where $c$ is candidate length and $r$ is (effective) reference length. The final score combines geometric-mean precision across n-gram orders with the brevity penalty:

Why this is a reasonable (if imperfect) proxy. The geometric mean over multiple n-gram orders rewards both lexical choice (unigrams) and local fluency/word order (higher-order n-grams), since a candidate must reproduce increasingly long contiguous spans of the reference to score well on $p_2, p_3, p_4$. The brevity penalty is a correctness patch closing the "too-short" exploit that unclipped or unpenalized precision would allow. BLEU is not a measure of semantic adequacy — it has no model of synonymy, paraphrase, or meaning beyond surface n-gram overlap — so it systematically under-scores valid paraphrastic translations and is known to correlate imperfectly with human judgment at the sentence level, though correlation is stronger when aggregated over a full corpus.

Beam search trace. Suppose the decoder vocabulary restricted to plausible next tokens gives (toy, illustrative probabilities), decoding "Le chat dort" with beam width $k=2$:

Notice that at step 1 the beam kept "The" and "A" even though "Cat" alone was locally lower-probability — this is the lookahead beam search provides over greedy decoding, which would have committed to "The" alone and never even considered "A" as a competing hypothesis (in this toy case both converge to a sensible answer, but in general only the beam explores enough alternatives to correct an early misstep). After length normalization (dividing by length, here both length 3 excluding ``/`` so ranking is unchanged), the decoder outputs "The cat sleeps."

BLEU trace. Suppose the reference translation is "The cat is sleeping" and the candidate (system output) is "The cat sleeps now":

• Unigram matches (clipped): "The" ✓, "cat" ✓, "sleeps" ✗ (not in reference as exact token — reference has "sleeping"), "now" ✗ → $p_1 = 2/4 = 0.5$
• Bigram matches: "The cat" ✓ (appears in both), "cat sleeps" ✗, "sleeps now" ✗ → $p_2 = 1/3 \approx 0.333$
• Trigram matches: "The cat sleeps" ✗, "cat sleeps now" ✗ → $p_3 = 0/2 = 0$

Because $p_3 = 0$, the raw geometric mean is zero — in practice implementations apply smoothing (e.g., adding a small count to avoid a zero score for otherwise-reasonable short sentences), but working through the unsmoothed math: candidate length $c=4$, reference length $r=4$, so $\text{BP} = 1$ (no penalty, lengths equal). The example shows concretely how BLEU harshly penalizes lexical variation ("sleeps" vs "sleeping") even when the translation is semantically correct — a central, well-documented limitation of surface-level n-gram metrics.

Every major commercial translation product — Google Translate, Microsoft Translator, DeepL, Amazon Translate — runs an NMT pipeline of essentially this shape: an encoder-decoder with attention, a beam-search decoder at inference time, and BLEU (among other metrics) used during development and benchmarking. Multilingual customer support systems, subtitle generation and localization pipelines, and cross-lingual information retrieval all depend on NMT as a core component. The same encoder-decoder-plus-attention architecture, and the same beam-search decoding algorithm, generalize directly to other conditional generation tasks — abstractive summarization, image captioning, speech recognition, and code generation all reuse this machinery essentially unchanged. The Transformer architecture that now dominates large language models grew directly out of NMT research, meaning the training objective (conditional log-likelihood), decoding strategy (beam or sampling-based search), and evaluation-metric mindset (automatic n-gram or learned metrics standing in for human judgment) established in NMT research remain the conceptual template for modern text generation systems broadly.

Ask the tutor: How does the choice of beam width interact with the length penalty to affect final translation quality?