Encoder-Decoder Architectures

An encoder-decoder architecture (sequence-to-sequence, seq2seq) is a composition of two neural networks trained jointly. The encoder $f_{\text{enc}}$ consumes an input sequence $x_1, \dots, x_{T_x}$ and produces a context representation $c$, usually the final hidden state of a recurrent network (or a function of all hidden states, in attention-augmented variants). The decoder $f_{\text{dec}}$ is a separate recurrent network, initialized using $c$, that generates an output sequence $y_1, \dots, y_{T_y}$ autoregressively: each output token is sampled conditioned on $c$ and all previously generated tokens. Formally, the model defines a conditional probability distribution over output sequences given input sequences:

where $c = f_{\text{enc}}(x_1, \dots, x_{T_x})$. Crucially, $T_x$ and $T_y$ need not be equal, and the model need not know $T_y$ in advance — generation stops when the decoder emits a special end-of-sequence token ``. The encoder and decoder are typically both LSTMs or GRUs (or stacks thereof), chosen because they resist vanishing gradients over the long sequences involved, but in principle any differentiable sequence model works, including the Transformer's attention-only encoder and decoder stacks that appear in later architectures. Two design choices define most of the variation among seq2seq systems: how the context $c$ is formed (a single final hidden state, a concatenation of forward/backward final states from a bidirectional encoder, or — in later architectures — a dynamically weighted combination of all encoder states), and how the decoder consumes $c$ (only at initialization, or re-injected at every decoding step). The version described here — a single fixed vector formed once and used to initialize the decoder — is the classical Sutskever–Cho formulation and is the version whose limitations set up the case for attention.

Encoding phase. The encoder RNN processes the input sequence left to right (optionally also right to left, if bidirectional), updating a hidden state at each step:

After consuming the last input token, the final hidden state $h_{T_x}$ (and cell state, for LSTMs) becomes the context vector $c$. All information the decoder will ever have about the input is packed into this one fixed-size vector — this is the defining structural choice and, as later analysis shows, the defining structural weakness.

Decoding phase — training. The decoder is itself an RNN, initialized with $h_0^{\text{dec}} = c$. It is trained to predict each output token given the previous ground-truth output token, a technique called teacher forcing:

using $y_{t-1}$ from the training data rather than the model's own (possibly wrong) previous prediction $\hat{y}_{t-1}$. This decouples each decoding step from the correctness of earlier steps, letting the loss at every position be computed and backpropagated in parallel-ish fashion (still sequential within a sequence, but independent across the batch and not compounding errors sequence-internally during training).

Decoding phase — inference. At test time there is no ground truth to force, so decoding is genuinely autoregressive: the model feeds its own previous output back in. ``` function TRAIN_STEP(x_1..x_Tx, y_1..y_Ty, encoder, decoder):

# ---- Encode ---- h = zero_vector() for t in 1..Tx: h = encoder.step(x_t, h) c = h # context vector

# ---- Decode with teacher forcing ---- s = c loss = 0 y_0 = # beginning-of-sequence token for t in 1..Ty: s, logits = decoder.step(y_{t-1}, s) # y_{t-1} is GROUND TRUTH loss += cross_entropy(logits, y_t) backpropagate(loss) return loss function GENERATE(x_1..x_Tx, encoder, decoder, max_len): h = zero_vector() for t in 1..Tx: h = encoder.step(x_t, h) c = h s = c y_prev = output = [] for t in 1..max_len: s, logits = decoder.step(y_prev, s) y_t = argmax(softmax(logits)) # greedy; beam search generalizes this if y_t == : break output.append(y_t) y_prev = y_t # feed back OWN prediction return output ``` Two edge cases the pseudocode must handle correctly: (1) the decoder must be seeded with a `` (beginning-of-sequence) token before it has produced anything, since $y_0$ does not exist in the data; (2) generation must have a `max_len` cutoff, because a poorly trained model may never emit `` and would otherwise loop forever. Both are visible above as explicit guards, not afterthoughts.

Time complexity. Let $T_x$ and $T_y$ be input and output lengths, $d$ the hidden dimension, and assume the RNN cell (GRU/LSTM) does $O(d^2)$ work per step (matrix-vector products dominate). Encoding costs $O(T_x d^2)$; decoding costs $O(T_y d^2)$; the total forward pass is $O((T_x + T_y) d^2)$, and by symmetry of backpropagation-through-time, training has the same asymptotic cost per example. This is linear in sequence length, which is the main efficiency win over naive alternatives that would need $O(T_x \cdot T_y)$ explicit alignments (an issue attention mechanisms later reintroduce deliberately, in exchange for accuracy).

Space complexity. Storing all encoder and decoder hidden states for backpropagation-through-time costs $O((T_x + T_y) d)$; the context vector itself is $O(d)$ regardless of $T_x$ — this fixed size is the architectural feature (and, as discussed below, the flaw). Parameter count is $O(d^2)$ for the recurrent weight matrices plus $O(d \cdot |V|)$ for input/output embeddings and the softmax projection, where $|V|$ is vocabulary size — independent of sequence length, since weights are shared across time steps.

Inference complexity. Greedy decoding is $O(T_y d^2)$, same order as training. Beam search with beam width $k$ multiplies decoder cost by $k$ (each beam is a separate hypothesis carried forward), giving $O(k \cdot T_y \cdot d^2)$; this is still linear in $T_y$, just with a constant-factor overhead, and is the standard way to approximate the highest-probability output sequence without the intractable $O(|V|^{T_y})$ cost of exhaustive search.

Correctness argument. The claim to justify is not "the algorithm finds the exactly right answer" — there is no ground truth to check against structurally — but rather that the training procedure is a valid maximum-likelihood estimator for the conditional distribution $p(y \mid x)$, and that teacher forcing does not bias this estimator. Because the chain rule factorizes any joint distribution over a sequence exactly,

training the decoder to predict $y_t$ from the true prefix $y_{<t}$ is training it to approximate exactly the factors of this exact factorization — no approximation is introduced by conditioning on ground truth at training time. The subtlety, and the honest caveat, is exposure bias: at test time the decoder conditions on its own generated prefix $\hat{y}_{<t}$, which may lie outside the distribution of true prefixes it was trained on, so errors can compound during generation in a way the training loss does not penalize. This is a real, acknowledged mismatch between the training and inference distributions, not a proof failure — it is mitigated in practice by scheduled sampling, beam search, and (later) attention, but not eliminated by the basic architecture. The context-vector bottleneck is the other honest tradeoff: since $c \in \mathbb{R}^d$ has fixed dimension regardless of $T_x$, a sufficiently long input sequence must eventually lose information to compression, no matter how large $d$ is chosen — a pigeonhole-style argument, since the number of distinguishable input sequences the encoder could ever need to represent grows with $T_x$ while the representational capacity of $c$ does not. Empirically, translation quality measured by BLEU degrades sharply for sentences longer than those seen in training, which is exactly the symptom this argument predicts.

Consider translating the three-word English sentence "she likes tea" into a hypothetical three-word target "elle aime thé", with a toy hidden dimension $d=2$ for illustration (real systems use $d$ in the hundreds to low thousands).

Step 1 — Encode. The encoder GRU processes tokens in order, updating its hidden state:

The final state $c = h_3 = (0.55, 0.30)$ is the context vector. Note that "she" no longer exists as a separately addressable quantity after step 3 — its influence is smeared into $c$ alongside "likes" and "tea".

Step 2 — Decode with teacher forcing (training). The decoder is seeded with `` and $s_0 = c = (0.55, 0.30)$:

Total sequence loss $\approx 1.55$, backpropagated through both decoder and encoder (gradients flow from decoder loss all the way back through $c$ into $h_1, h_2, h_3$ and the encoder weights — this is exactly why the two networks are trained jointly, not independently).

Step 3 — Decode at inference (no ground truth available). Suppose at test time the decoder's own step-1 prediction is wrong — it emits "il" instead of "elle" (a plausible confusion, both mean "he/she" contextually). Under greedy autoregressive decoding, "il" (not "elle") is fed back as $y_1$ for computing $s_2$. If the decoder was never trained on prefixes containing an erroneous "il", $s_2$ may drift into a region of state space the model handles poorly, potentially causing step 2 to also err — this is the exposure-bias phenomenon made concrete: one early mistake propagates because generation, unlike training, has no ground truth to fall back on.

The encoder-decoder pattern for neural sequence transduction crystallized in 2014, when two groups independently proposed essentially the same architecture for machine translation: Cho, Bahdanau, and colleagues at Montreal introduced the RNN encoder-decoder framework alongside the GRU cell, while Sutskever, Vinyals, and Le at Google demonstrated it at scale with stacked LSTMs, showing for the first time that a purely neural system could rival phrase-based statistical machine translation. Both papers observed the same bottleneck — quality collapsing on long sentences — which within a year led Bahdanau, Cho, and Bengio to introduce attention, letting the decoder consult all encoder states rather than a single compressed vector.

Encoder-decoder architectures underpin production machine translation systems (early Google Translate's neural pivot, and the conceptual ancestor of today's Transformer-based translation services), automatic speech recognition pipelines that map audio frames to transcribed text, abstractive text summarization systems that compress documents into shorter summaries, image-captioning systems that pair a convolutional encoder with a recurrent (or Transformer) decoder, and sequence-based time-series forecasting where a variable-length history must produce a variable-length forecast. The pattern also generalizes structurally beyond sequences: any system that "reads everything, then generates" — including retrieval-augmented generation pipelines and code-generation assistants — inherits this two-stage read-then-write design, even where the internals have moved from RNN cells to attention-based Transformer blocks. Recognizing the encoder-decoder skeleton underneath a modern system, even a heavily modified one, is often the fastest way to reason about where its information bottlenecks and failure modes will show up.

Ask the tutor: How does adding attention mathematically change the decoder's conditioning from a single context vector to a weighted sum over all encoder states?