Before transformers — the sequential bottleneck
Before transformers — the sequential bottleneck
A recurrent neural network processes tokens one at a time. At each step t, the network takes the current input x_t and the previous hidden state h_{t-1}, and produces a new hidden state: h_t = tanh(W_xh * x_t + W_hh * h_{t-1} + b). The hidden state h_t is a fixed-size vector — typically 256 to 1024 floats — that serves as the network's entire memory of everything it has read so far. Every token the model has ever seen must be compressed into this single vector before the next token arrives.
This creates an immediate problem: information from early tokens must survive through many sequential matrix multiplications. Each step transforms h through a nonlinearity, and the gradient of the loss with respect to an early input must backpropagate through every intervening step. For a sequence of length T, the gradient signal passes through T matrix multiplications by W_hh. If the largest singular value of W_hh is less than 1, gradients shrink exponentially — the vanishing gradient problem (Bengio et al. 1994). If the largest singular value exceeds 1, gradients explode. In practice, standard RNNs fail to learn dependencies beyond approximately 20 tokens.
The vanishing gradient in practice
The exponential decay is easy to observe. A single-layer RNN with hidden_dim=64 and input_dim=32, processing sequences of increasing length, shows the gradient of the final output with respect to the first input token decaying toward zero:
import torch
import torch.nn as nn
class SimpleRNN(nn.Module):
def __init__(self, input_dim, hidden_dim):
super().__init__()
self.W_xh = nn.Linear(input_dim, hidden_dim, bias=False)
self.W_hh = nn.Linear(hidden_dim, hidden_dim, bias=False)
def forward(self, x_seq):
h = torch.zeros(self.W_hh.in_features)
for x_t in x_seq:
h = torch.tanh(self.W_xh(x_t) + self.W_hh(h))
return h
rnn = SimpleRNN(input_dim=32, hidden_dim=64)
torch.manual_seed(42)
for seq_len in [5, 10, 20, 50, 100, 200]:
x = torch.randn(seq_len, 32, requires_grad=True)
h_final = rnn(x)
h_final.sum().backward()
grad_first = x.grad[0].norm().item()
grad_last = x.grad[-1].norm().item()
ratio = grad_first / grad_last if grad_last > 0 else 0.0
print(f"T={seq_len:3d} |grad_first|={grad_first:.6f} "
f"|grad_last|={grad_last:.6f} ratio={ratio:.6f}")
x.grad = NoneTypical output:
T= 5 |grad_first|=0.412831 |grad_last|=1.283049 ratio=0.321753
T= 10 |grad_first|=0.098234 |grad_last|=1.304217 ratio=0.075323
T= 20 |grad_first|=0.003841 |grad_last|=1.291534 ratio=0.002975
T= 50 |grad_first|=0.000002 |grad_last|=1.278903 ratio=0.000002
T=100 |grad_first|=0.000000 |grad_last|=1.285612 ratio=0.000000
T=200 |grad_first|=0.000000 |grad_last|=1.290178 ratio=0.000000The gradient at the last token stays roughly constant regardless of sequence length — the output always depends strongly on the most recent input. But the gradient at the first token drops by orders of magnitude. At T=50, the model is effectively blind to the first token. No amount of training will teach it to use information from 50 steps ago, because the gradient signal that would teach it is numerically zero.
LSTMs — gated memory cells
The Long Short-Term Memory network (Hochreiter & Schmidhuber 1997) addresses vanishing gradients by introducing a separate cell state c_t that flows through the network with only element-wise operations — no matrix multiplications that compound exponentially. Three gates control information flow:
The forget gate decides which information to discard from the cell state: f_t = sigmoid(W_f * [h_{t-1}, x_t] + b_f). Values near 1 mean "keep this"; values near 0 mean "forget this."
The input gate decides which new information to write: i_t = sigmoid(W_i * [h_{t-1}, x_t] + b_i). A candidate cell update is computed as c_hat_t = tanh(W_c * [h_{t-1}, x_t] + b_c).
The cell state updates via element-wise operations: c_t = f_t ⊙ c_{t-1} + i_t ⊙ c_hat_t. The ⊙ denotes element-wise multiplication. When f_t ≈ 1 and i_t ≈ 0, the cell state passes through unchanged — gradients flow backward without decay. This is the "highway" that makes long-range learning possible.
The output gate controls what the hidden state exposes: o_t = sigmoid(W_o * [h_{t-1}, x_t] + b_o), and the hidden state is h_t = o_t ⊙ tanh(c_t).
Each gate has its own weight matrices W and biases b, so an LSTM layer has 4x the parameters of a simple RNN layer. For input_dim=512 and hidden_dim=512:
- Simple RNN:
512 * (512 + 512) = 524,288parameters - LSTM:
4 * 524,288 = 2,097,152parameters
The cost buys effective memory. Empirically, LSTMs can learn dependencies up to roughly 200–500 tokens — a 10–25x improvement over vanilla RNNs. But the computation is still sequential: h_t depends on h_{t-1}, which depends on h_{t-2}, all the way back to h_0. Every token must wait for the previous token to finish processing. On a GPU with thousands of cores, this sequential dependency means most cores sit idle while the network crawls through the sequence one step at a time.
import torch.nn as nn
lstm = nn.LSTM(input_size=512, hidden_size=512, num_layers=2, batch_first=True)
print(f"LSTM parameters: {sum(p.numel() for p in lstm.parameters()):,}")
# LSTM parameters: 4,198,400 (2 layers × ~2.1M each)
x = torch.randn(1, 200, 512) # batch=1, seq_len=200, input_dim=512
output, (h_n, c_n) = lstm(x)
print(f"Output shape: {output.shape}") # (1, 200, 512) — one hidden state per position
print(f"Final h shape: {h_n.shape}") # (2, 1, 512) — final hidden state per layer
print(f"Cell state shape: {c_n.shape}") # (2, 1, 512) — final cell state per layerGRUs — a lighter alternative
The Gated Recurrent Unit (Cho et al. 2014) simplifies the LSTM by merging the cell state and hidden state into a single vector and reducing four gates to two:
The reset gate controls how much of the previous state to use when computing the candidate: r_t = sigmoid(W_r * [h_{t-1}, x_t]).
The update gate controls the interpolation between old and new state: z_t = sigmoid(W_z * [h_{t-1}, x_t]).
The new hidden state is: h_t = (1 - z_t) ⊙ h_{t-1} + z_t ⊙ tanh(W * [r_t ⊙ h_{t-1}, x_t]).
When z_t ≈ 0, the hidden state passes through unchanged (similar to the LSTM's forget gate holding at 1). With only 3 weight matrices instead of 4, a GRU has 75% of the LSTM's parameters: 3 * 524,288 = 1,572,864 for the same dimensions. Performance on most benchmarks is comparable to LSTM (Chung et al. 2014), and the reduced parameter count means faster training per step — though the sequential bottleneck remains identical.
In practice, the choice between LSTM and GRU is empirical. Jozefowicz et al. (2015) evaluated over 10,000 RNN architectures and found no consistent winner — LSTMs had a slight edge on some language modeling tasks, GRUs on some translation tasks, but the differences were within noise for most benchmarks. The critical limitation shared by both is the same one: strictly sequential computation.
The seq2seq bottleneck
For machine translation, Sutskever et al. (2014) introduced the encoder-decoder (seq2seq) architecture: an encoder LSTM reads the source sentence token by token, compressing it into the final hidden state vector, then a decoder LSTM generates the target sentence conditioned on that vector.
The problem is acute: the entire meaning of a 50-word German sentence must fit into a single 1024-dimensional vector. That's 4 KB of floating-point numbers encoding grammar, word order, named entities, coreference, tense, and every other linguistic property the decoder needs to produce a correct English translation. For short sentences this works. For sentences beyond 20–30 words, BLEU scores degrade sharply — the fixed-length vector cannot hold enough information (Cho et al. 2014).
Google's production NMT system (Wu et al. 2016) used an 8-layer LSTM encoder-decoder with 1024-dim hidden states — roughly 210M parameters. Even at this scale, the bottleneck constrained translation quality on long sentences.
Bahdanau attention — attention as an add-on
Bahdanau, Cho & Bengio (2014) proposed a direct fix: instead of forcing the decoder to work from a single summary vector, let it look at all encoder hidden states at every decoding step. The encoder produces a hidden state h_i for each source position i. At each decoder step t, the model computes attention scores over all encoder positions:
score(s_t, h_i) = v^T * tanh(W_s * s_t + W_h * h_i)
where s_t is the decoder's hidden state and v, W_s, W_h are learned parameters. The scores are normalized via softmax to produce attention weights alpha_{t,i}, and the context vector is the weighted sum: c_t = sum(alpha_{t,i} * h_i for all i).
The decoder then uses both c_t and s_t to predict the next target token. Attention weights are different at every decoding step — when generating an English verb, the model can attend to the German verb; when generating a noun, it attends to the corresponding German noun. The fixed-length bottleneck is eliminated.
Results were immediate: on English-French translation (WMT 2014), Bahdanau attention improved BLEU by 5+ points over the non-attentive baseline on sentences longer than 30 words. Performance no longer degraded with sentence length. The attention weights also turned out to be interpretable — visualizing alpha_{t,i} showed the model learning a soft alignment between source and target positions, often matching the alignments that human translators would produce.
Luong et al. (2015) simplified Bahdanau's additive attention to a dot-product variant: score(s_t, h_i) = s_t^T * h_i, which is cheaper to compute and performs comparably. They also introduced "local attention" — attending to a window around the predicted alignment position rather than the full source sequence. These attention variants were adopted widely and refined through 2016, but the underlying architecture remained unchanged.
But the architecture still uses an RNN. The encoder LSTM processes the source sequentially. The decoder LSTM generates tokens sequentially. Attention helps the decoder access information, but the sequential computation remains the throughput bottleneck. On 8 GPUs, Google's NMT system (Wu et al. 2016) took about a week to train on the WMT dataset. Most of that time was spent waiting for sequential RNN steps to complete while thousands of GPU cores sat idle.
This was the state of the art in 2016: powerful attention mechanisms bolted onto fundamentally sequential architectures. The question that the next paper would answer: if attention does the heavy lifting for long-range dependencies, why keep the recurrence at all?