The Encoder-Decoder Architecture

The encoder-decoder architecture — also called sequence-to-sequence (seq2seq) modeling — factors the task of transducing one sequence into another into two learned functions. Given a source sequence $x = (x_1, \dots, x_n)$, the encoder $f_{\text{enc}}$ processes it and produces a representation $c$, called the context vector:

In the canonical Sequence-to-Sequence Models formulation, the encoder is a recurrent network (RNN, LSTM, or GRU) run over the input, and $c$ is simply its final hidden state $h_n$. The decoder $f_{\text{dec}}$ is a second recurrent network that is initialized with $c$ and generates the output sequence $y = (y_1, \dots, y_m)$ one symbol at a time, where each symbol's distribution is conditioned on the context and all previously generated symbols:

This factorization is exactly the chain rule of probability applied to the output sequence, with the entire source sequence summarized into the single conditioning variable $c$. Two properties distinguish this from earlier sequence models. First, $n$ and $m$ need not match — this is precisely what makes translation, summarization, and other length-changing tasks tractable. Second, the decoder is itself an autoregressive model: a conditional language model over the target vocabulary, where generation of $y_t$ depends on $y_{<t}$, exactly like the Neural Machine Translation systems that popularized this design. The term information bottleneck refers to the fact that $c$ has fixed dimensionality (say, 512 or 1024 real numbers) regardless of how long the input sequence is. A 5-word sentence and a 50-word sentence are both compressed into a vector of the same size. This is the central structural weakness of the vanilla architecture: as $n$ grows, $c$ must encode proportionally more information in a space that does not grow with it, and empirically translation quality degrades sharply on long sentences. This weakness is precisely the motivation for the attention mechanism, which allows the decoder to look back at all encoder hidden states rather than relying on one compressed summary — but that solution is a separate development built on top of the architecture described here.

The system consists of two coupled recurrent components sharing a training objective but running under different regimes at train versus inference time.

Encoding. The encoder reads the source tokens $x_1, \dots, x_n$ one at a time, updating a hidden state:

with $h_0^{\text{enc}}$ typically initialized to zero. After processing all $n$ tokens, the final hidden state $h_n^{\text{enc}}$ becomes the context vector $c$. (Some variants also use a summary of the cell state in LSTMs, or concatenate forward and backward hidden states from a bidirectional encoder — a detail worth noting but orthogonal to the core mechanism.)

Decoding at training time. The decoder is initialized with $h_0^{\text{dec}} = c$. At each step $t$, it consumes the true previous target token $y_{t-1}$ (not its own prediction) — a technique called teacher forcing — updates its hidden state, and produces a probability distribution over the vocabulary via a softmax layer:

The first input to the decoder is a special `` (beginning-of-sequence) token, and generation is trained to stop by predicting a special `` (end-of-sequence) token. The whole network — encoder and decoder together — is trained by minimizing the cross-entropy loss between the predicted distributions and the true target tokens, summed over the sequence and averaged over a batch.

Decoding at inference time. At test time there is no ground truth to feed in, so the decoder must feed its own previous prediction back as the next input — this is the defining feature of autoregressive decoding. The simplest strategy, greedy decoding, picks the single highest-probability token at each step. Because greedy decoding can lock in an early suboptimal choice, beam search instead tracks the $k$ highest-scoring partial sequences ("beams") at each step, expanding all of them and keeping only the top $k$ overall. ``` function ENCODE(x[1..n]): h ← zero_vector() for t in 1..n: h ← RNN_enc(x[t], h) return h # this is the context vector c function GREEDY_DECODE(c, max_len): y ← [BOS] h ← c for t in 1..max_len: h ← RNN_dec(y[t-1], h) dist ← softmax(W · h + b) y_t ← argmax(dist) append y_t to y if y_t == EOS: break return y[2:] # drop the leading BOS function BEAM_SEARCH(c, k, max_len): beams ← [ (sequence=[BOS], score=0.0, hidden=c, done=false) ] for t in 1..max_len: candidates ← empty list for beam in beams: if beam.done: candidates.add(beam) # frozen: already emitted EOS continue h ← RNN_dec(beam.sequence[-1], beam.hidden) dist ← softmax(W · h + b) for token, prob in top_k_tokens(dist, k): new_score ← beam.score + log(prob) new_seq ← beam.sequence + [token] candidates.add( (new_seq, new_score, h, token == EOS) ) beams ← top_k_by_score(candidates, k) if all beams.done: break return highest_scoring(beams).sequence[1:] # drop BOS function TRAIN_STEP(x[1..n], y[1..m]): c ← ENCODE(x) h ← c loss ← 0 for t in 1..m: prev ← (y[t-1] if t > 1 else BOS) # teacher forcing h ← RNN_dec(prev, h) dist ← softmax(W · h + b) loss ← loss - log(dist[y[t]]) backpropagate(loss) # through decoder AND encoder update_parameters() ``` Three details deserve emphasis. First, `RNN_enc` and `RNN_dec` have separate parameters — they are two distinct networks, not one network reused twice. Second, teacher forcing means the training-time input sequence to the decoder is always the gold target shifted by one position, which decouples training from the model's own (possibly wrong) predictions and stabilizes learning, at the cost of a train/inference mismatch called exposure bias. Third, gradients from the decoder's loss flow backward not just through the decoder but all the way through the context vector into the encoder, so the encoder learns to produce representations useful for decoding, not representations useful in the abstract.

Time complexity. Let $n$ be the source length, $m$ the target length, $d$ the hidden dimension, and $V$ the vocabulary size. Encoding requires $n$ sequential RNN steps, each costing $O(d^2)$ for the recurrent matrix multiplications (for an LSTM, a small constant factor larger due to gates), giving $O(n d^2)$. Decoding requires $m$ sequential steps, each costing $O(d^2)$ for the recurrence plus $O(dV)$ for the softmax projection, giving $O(m(d^2 + dV))$. Training a single example thus costs

and inference under greedy decoding costs the same with $m$ replaced by the number of steps until `` is emitted (bounded by `max_len`). Beam search with beam width $k$ multiplies the decoding cost by $k$, since $k$ hypotheses must be expanded at every step: $O(k \cdot m(d^2 + dV))$. This is the honest tradeoff of beam search — a constant-factor slowdown in exchange for exploring a wider swath of the output space than a single greedy path.

Space complexity. Training must store all intermediate hidden states for backpropagation through time, giving $O((n+m)d)$ activation memory per example (plus $O(d^2)$ for the shared weight matrices, independent of sequence length). Beam search at inference needs $O(k \cdot d)$ memory to track the $k$ active hidden states, plus $O(k \cdot m)$ to store the $k$ candidate sequences.

Why the architecture computes what it claims to compute. The correctness argument is not "does the algorithm terminate correctly" in the classical sense, but "does the model define a valid, learnable probability distribution over target sequences." Three facts establish this: 1. Well-formed distribution. At every decoding step, softmax guarantees $P(y_t = v \mid y_{<t}, c) \geq 0$ for all $v$ and $\sum_v P(y_t = v \mid y_{<t}, c) = 1$. The chain-rule product of these per-step distributions is therefore itself a valid probability distribution over sequences (it sums to 1 over all sequences ending in ``, by induction on sequence length and the law of total probability). 2. The bottleneck is a real information constraint, not a training artifact. Because $c \in \mathbb{R}^d$ has fixed dimensionality, and the decoder's entire access to the source is through $c$, the mutual information $I(x_1,\dots,x_n ; y_1,\dots,y_m)$ that the model can exploit is upper-bounded by $H(c) \le d \cdot \log_2(\text{quantization levels per dimension})$ — a fixed number of bits regardless of $n$. As $n$ grows, the average bits of source information available per source token shrinks, which is precisely why empirical BLEU scores for vanilla encoder-decoder models degrade on long sentences: this is a provable capacity limit, not merely an optimization difficulty. This observation is exactly the gap that attention-augmented decoders close, since attention lets the decoder read from $n$ separate vectors instead of one. 3. Teacher forcing trains a consistent estimator of the true chain-rule factorization, since at training time the model literally sees samples of $P(y_t \mid y_{<t}, x)$ under the true $y_{<t}$, and cross-entropy minimization is the maximum-likelihood estimator for this factorized distribution. The mismatch appears only at inference, when true $y_{<t}$ is replaced by the model's own generated prefix — this is exposure bias, a known and documented gap between training and test-time behavior, not a flaw in the probabilistic derivation itself.

Consider translating the French sentence "Le chat dort" ("The cat sleeps") into English, with a toy vocabulary and $d = 2$ for hand-traceable numbers (real systems use $d$ in the hundreds).

Encoding pass. Source tokens: `Le`, `chat`, `dort`, ``. The encoder RNN updates its hidden state after each token:

The context vector $c = (0.20, 0.61)$ is now the only channel through which the decoder learns anything about the source sentence.

Decoding pass (inference, greedy). The decoder is initialized with $h_0^{\text{dec}} = c$ and fed ``:

Output: "The cat sleeps." — correct, and note each decoder input is the previous output, not the gold token, since this is inference-time autoregressive generation.

Contrast with beam search ($k=2$). Suppose at step 1 the model actually assigns `The`: 0.55 and `A`: 0.40 (a closer call than above). Greedy commits irreversibly to `The`. Beam search keeps both `The` and `A` alive:

Beam 1 remains ahead, and in this trace beam search would ultimately converge to the same "The cat sleeps," but the point is structural: beam search only discards the losing beam ("A cat …") after seeing how both continuations play out over multiple steps, whereas greedy decoding never sees the alternative at all. On sentences where the single best next word leads down a locally-promising but globally-worse path, beam search recovers superior full sequences that greedy decoding cannot.

The architecture crystallized in 2014 through near-simultaneous work by two research groups tackling the same limitation of phrase-based statistical machine translation: its inability to learn end-to-end from data without hand-built alignment and feature engineering.

The encoder-decoder split remains one of the most widely deployed structural ideas in applied NLP and beyond. Neural machine translation systems — from the earliest production deployment of Google Translate's neural backend in 2016 to today's multilingual translation services — are built on this template, now almost universally paired with attention. Abstractive summarization systems encode a long document and decode a shorter summary, facing an even more acute version of the bottleneck problem that motivated attention and later hierarchical and sparse-attention variants. Speech recognition pipelines use an audio encoder (often convolutional or recurrent over spectrogram frames) paired with a text decoder, an architecture sometimes called "listen, attend and spell." Image captioning models replace the sequential encoder with a convolutional network that produces a spatial feature map, still handed to an autoregressive decoder that generates a caption word by word — a design in Show-and-Tell and its successors. Even architectures that appear to have moved past the vanilla design retain its logical skeleton. The Transformer, used in machine translation systems and in encoder-decoder large language models such as T5 and BART, still separates an encoder stack (bidirectional self-attention over the full input) from a decoder stack (causal self-attention plus cross-attention into the encoder), directly inheriting the two-network, context-mediated structure described here — with the fixed-size bottleneck replaced by the attention mechanism's ability to attend over the full set of encoder states. Understanding the vanilla encoder-decoder architecture, its bottleneck, and its autoregressive decoding loop is therefore the necessary foundation before studying Attention Mechanism in NLP and its role in modern Neural Machine Translation systems.

Ask the tutor: How exactly does adding an attention mechanism change the decoder's conditioning to bypass the fixed-size context vector bottleneck?