Sequence-to-Sequence Models

A sequence-to-sequence model learns a conditional distribution $P(y_1, \dots, y_m \mid x_1, \dots, x_n)$ over output sequences $y$ given input sequences $x$, where $n$ and $m$ need not be equal and need not correspond position-by-position. This distinguishes seq2seq from sequence labeling tasks (like part-of-speech tagging), where each input token gets exactly one aligned output label. The architecture that realizes this is the encoder-decoder pair. The encoder is a recurrent network (originally an LSTM or GRU) that processes the input tokens $x_1, \dots, x_n$ one at a time, updating a hidden state at each step. After consuming the last input token, the encoder's final hidden state $c$ — the context vector — is taken as a compressed summary of the entire input sequence. Crucially, $c$ has a fixed dimensionality regardless of $n$: a 50-word sentence and a 5-word sentence are both squeezed into the same size vector. The decoder is a separate recurrent network that generates the output sequence autoregressively: it predicts $y_1$ conditioned on $c$, then predicts $y_2$ conditioned on $c$ and $y_1$, and so on, until it emits a special end-of-sequence token. Formally, the decoder factors the joint output distribution using the chain rule:

Each factor is computed by a softmax over the vocabulary, taking as input the decoder's current hidden state, which itself depends on the previous output token and the running decoder state initialized from $c$. This factorization is exact by the chain rule of probability — no independence assumption is smuggled in, since each term conditions on all previous outputs. The key architectural commitment of the vanilla seq2seq model is that all information the decoder ever receives about the input must pass through the single vector $c$. This is both the elegance and the weakness of the design, discussed under complexity and pitfalls below.

Training phase. Given a paired dataset of $(x, y)$ sequences, the encoder processes $x$ to produce $c$. The decoder is then run in teacher-forcing mode: at each decoding step $t$, instead of feeding back its own (possibly wrong) prediction from step $t-1$, it is fed the true token $y_{t-1}$ from the training pair. This stabilizes training because errors do not compound — the decoder always sees a "clean" history — and it allows the whole sequence to be processed as one parallelizable forward pass with a single backward pass for gradient computation (backpropagation through time, across both networks). The loss is the sum (or average) of per-token cross-entropy losses:

summed over training pairs and minimized by gradient descent, exactly as in standard Recurrent Models for NLP language modeling, but now conditioned on an external context vector $c$.

Inference phase. At test time, the true output sequence is unknown, so teacher forcing is impossible. Decoding proceeds autoregressively: generate a token, feed it back as input to generate the next token, and repeat until an end-of-sequence marker is produced or a maximum length is reached. Two common strategies:

• Greedy decoding: at each step, pick the single highest-probability token. Fast, $O(m)$ decoder calls, but can commit to locally optimal but globally suboptimal choices.
• Beam search: maintain the $k$ highest-scoring partial sequences ("beams") at each step, expanding each by all vocabulary tokens and pruning back to the top $k$. This better approximates the sequence with highest total log-probability, at $k\times$ the computational cost.

``` function TRAIN_SEQ2SEQ(dataset, encoder, decoder, epochs, learning_rate): for epoch in 1..epochs: for (x, y) in dataset: # x = x_1..x_n, y = y_1..y_m

# ---- Encode ---- h = encoder.init_hidden() for t in 1..n: h = encoder.step(x[t], h) c = h # final hidden state = context vector

# ---- Decode with teacher forcing ---- h_dec = c loss = 0 prev_token = START_TOKEN for t in 1..m: logits, h_dec = decoder.step(prev_token, h_dec) probs = softmax(logits) loss += -log(probs[y[t]]) prev_token = y[t] # feed TRUE token, not prediction gradients = backprop(loss, encoder.params + decoder.params) update(encoder.params, decoder.params, gradients, learning_rate) function GREEDY_DECODE(x, encoder, decoder, max_len): h = encoder.init_hidden() for t in 1..length(x): h = encoder.step(x[t], h) c = h h_dec = c output = [] prev_token = START_TOKEN for t in 1..max_len: logits, h_dec = decoder.step(prev_token, h_dec) prev_token = argmax(softmax(logits)) if prev_token == END_TOKEN: break output.append(prev_token) return output function BEAM_SEARCH_DECODE(x, encoder, decoder, max_len, k): h = encoder.init_hidden() for t in 1..length(x): h = encoder.step(x[t], h) c = h beams = [ (score=0.0, tokens=[START_TOKEN], hidden=c) ] completed = [] for t in 1..max_len: candidates = [] for (score, tokens, h_dec) in beams: if tokens[-1] == END_TOKEN: completed.append((score, tokens, h_dec)) continue logits, h_new = decoder.step(tokens[-1], h_dec) logp = log_softmax(logits) for token in vocabulary: candidates.append((score + logp[token], tokens + [token], h_new)) beams = top_k(candidates, k) # keep k highest-scoring partials if all beams end in END_TOKEN: break completed.extend(beams) return argmax_by_score(completed) # or length-normalized score ```

Time complexity. Let $n$ be input length, $m$ output length, $d$ hidden dimension, and $|V|$ vocabulary size. Encoding is $O(n \cdot d^2)$ time (each RNN step costs $O(d^2)$ for the matrix multiplications inside the recurrence). Decoding during training (teacher forcing) is $O(m \cdot (d^2 + d|V|))$, where the $d|V|$ term is the cost of the output softmax at each step. Both phases are linear in sequence length, and the two RNNs run sequentially, so total training time per example is $O((n+m)(d^2 + d|V|))$. At inference, greedy decoding costs the same $O(m(d^2+d|V|))$. Beam search with beam width $k$ multiplies the decoder cost by $k$, giving $O(k \cdot m \cdot (d^2 + d|V|))$, since at each of the $m$ steps we expand $k$ beams and score $|V|$ continuations for each.

Space complexity. Storing hidden states for backpropagation through time requires $O((n+m)d)$ space for a single example (one hidden vector per timestep must be retained for the backward pass), plus $O(d^2 + d|V|)$ for the model parameters themselves, independent of sequence length. Beam search adds $O(k \cdot m \cdot d)$ space to track $k$ hypotheses' hidden states.

Why teacher forcing is correct as a training procedure. The maximum-likelihood objective factorizes exactly via the chain rule shown above — this is not an approximation, it is an algebraic identity for any joint distribution over a sequence. Teacher forcing implements maximum likelihood by plugging in the ground-truth prefix $y_{<t}$ at every step, so the gradient of the loss with respect to parameters exactly matches the gradient of the true log-likelihood objective evaluated on the training pair. The mismatch this introduces is only at inference time: the model is trained conditioned on true prefixes but must generate conditioned on its own (possibly imperfect) prefixes, an issue known as exposure bias. This does not make training incorrect — it correctly optimizes likelihood under teacher forcing — but it does mean training loss is not a perfectly faithful proxy for generation quality, a known and studied gap.

Why greedy/beam decoding is a reasonable approximation. Exact inference would require computing

which is intractable to search exhaustively (exponential in $m$, since the number of possible sequences is $|V|^m$). Beam search is a bounded-width approximate dynamic-programming-style search: because the RNN decoder's state is not Markovian over a small fixed window (it depends on the whole generated prefix), true dynamic programming with polynomial states is not directly available, so we resort to keeping only the $k$ best partial hypotheses at each depth — a standard heuristic that provably contains the greedy solution as the special case $k=1$, and that empirically improves log-likelihood of the returned sequence monotonically in $k$ up to diminishing returns.

The bottleneck problem — an honest tradeoff. The context vector $c$ has fixed dimensionality $d$, independent of $n$. As $n$ grows, $c$ must represent proportionally more information in the same number of dimensions, so information loss becomes unavoidable for long inputs. Empirically, translation quality (measured by BLEU score) degrades sharply for sentences beyond roughly 20–30 tokens in the original architecture. This is not a bug fixable by better optimization; it is a structural property of forcing all input information through one vector, and it is precisely the limitation that the Attention Mechanism in NLP is designed to remove by letting the decoder access all encoder hidden states, not just the last one.

Consider a toy translation task: English "the cat sat" → French "le chat assis" (a simplified gloss, ignoring real French grammar, for pedagogical tracing). Vocabulary indices: `the=1, cat=2, sat=3, =0` (input side); `le=1, chat=2, assis=3, =0` (output side). Hidden dimension $d=2$ for hand-traceability.

Encoding pass (illustrative hidden-state values, not from a real trained model):

Context vector $c = h_3 = (0.42, 0.31)$. Note: tokens 1 and 2 ("the", "cat") no longer exist as separate accessible states for the decoder — only their residue inside $c$ remains.

Decoding pass with teacher forcing (training):

Total sequence loss $\approx 0.29 + 0.25 + 0.19 + 0.15 = 0.88$, backpropagated through both decoder and encoder.

Decoding pass at inference (greedy, no teacher forcing): suppose the decoder's step-1 prediction were wrong — say it predicted "chat" instead of "le" (probability mass slightly favoring the wrong token due to an undertrained model). Because there is no ground truth to correct it, step 2 now conditions on the wrong token "chat" as if it were the first output word, and the error can propagate through the rest of the sequence. This is exposure bias made concrete: the training procedure never showed the decoder what to do after its own mistake, only after the correct prefix.

Beam search trace (k=2) for the same first step: keep the top two candidates "le" (score $\log 0.75$) and "chat" (score $\log 0.10$). Expanding both one more step and re-pruning to the top 2 by cumulative score is what lets beam search recover from a locally tempting but globally wrong first guess, something greedy (k=1) cannot do.

The encoder-decoder framework for sequences was crystallized by researchers extending recurrent language modeling to conditional generation, most prominently in the neural machine translation literature of the early 2010s, building on decades of work on recurrent networks and sequence learning.

Seq2seq established the template underlying essentially all modern text generation systems, even after the underlying encoder and decoder were reengineered from RNNs to Transformers. Neural machine translation systems in production (used in large-scale translation services) are seq2seq models at their core, conditioning an output-language decoder on a source-language encoding. Automatic speech recognition systems frame "audio in, transcript out" as sequence-to-sequence, with the encoder consuming acoustic features and the decoder producing text tokens. Text summarization, image captioning (encoder over image features, decoder over words), and code-generation assistants all reuse the same encode-then-autoregressively-decode template. Even the largest modern language models, though architecturally Transformer-based rather than recurrent, inherit the autoregressive decoding discipline pioneered in the seq2seq framework: generate one token at a time, conditioned on everything generated so far. Studying seq2seq is therefore the natural bridge from Recurrent Models for NLP to the attention-augmented and fully attention-based architectures — The Encoder-Decoder Architecture and the Attention Mechanism in NLP — that dominate contemporary NLP.

Ask the tutor: How does the attention mechanism modify the encoder-decoder pipeline to remove the fixed-size bottleneck?