RNNs, LSTMs, GRUs, and Sequence Modeling

An on-call assistant sees error logged, then reproduction confirmed, then rollback requested. Reverse those events and the latest evidence changes: an error now arrives after the rollback request. Neither history proves the incident is resolved, but their order matters for the next decision. How can a model track that order without requiring a different architecture for every possible history length?

The previous lesson converted raw class scores, or logits, into a softmax probability distribution. We'll keep that classifier at the tail end, outputting decisions across three actions: ignore, rollback, and escalate. Our job here is to transform a variable-length stream of events into the single, fixed-size vector that the downstream classifier expects.

Order is part of the input

If you shuffle raw event vectors, a bag-of-events sum or average treats the history as identical because those operations are commutative. An order-aware model can distinguish the histories. This doesn't guarantee that every permutation has a different state: compressed representations can collide, and a model may deliberately ignore order that isn't useful for its task.

The tiny accumulator below isn't a trained neural network. Each incoming event updates a running state influenced by earlier events, with older evidence discounted.

Before running it, predict which order leaves the larger final state. The same three values arrive, but the recurrence discounts earlier state by 0.6, so the event in the final position exerts the strongest direct influence:

The incident order computes 0.6 * (0.6 * 1.0 + 0.4) + 0.9 = 1.5. Reversing it puts the largest event 1.0 in the final position, producing 0.6 * (0.6 * 0.9 + 0.4) + 1.0 = 1.564. A simple sum would yield 2.3 in both cases; the recurrent update makes sequence order inseparable from the final value.

One cell, reused at every step

A recurrent neural network (RNN) makes this update rule trainable. Its hidden state ($h_t$) is a running vector of numbers carried from one event to the next, serving as working memory. The update rule is called a recurrent cell, and each new event advances the sequence by one timestep.

Start with a scalar hidden state. Multiply the incoming event by 0.8, multiply the previous hidden state by 0.5, add them, and pass the result through hyperbolic tangent (tanh). Like sigmoid, tanh is a smooth S-shaped activation function, but its output spans $(-1, 1)$ and is zero-centered. With an initial state $h_0 = 0.0$ and a first event of 1.0, the weighted sum is 0.8, giving $h_1 = \tanh(0.8) \approx 0.664$.

For the second event (0.4), combine 0.8 * 0.4 with 0.5 * 0.664. That sum is about 0.652, yielding $h_2 = \tanh(0.652) \approx 0.573$. Run all three steps with these demonstration weights:

Three scalar inputs condense into one final scalar summary. When we expand the hidden state into a vector, different coordinates can track distinct patterns in parallel. The fundamental vector RNN recurrence equation is:

$$h_t = \tanh(W_{xh}x_t + W_{hh}h_{t-1} + b_h)$$

Here $x_t \in \mathbb{R}^{d_x}$ is the current input vector, $h_{t-1} \in \mathbb{R}^{d_h}$ is the prior hidden state, and $b_h \in \mathbb{R}^{d_h}$ is a bias vector. The weight matrices $W_{xh} \in \mathbb{R}^{d_h \times d_x}$ and $W_{hh} \in \mathbb{R}^{d_h \times d_h}$ project the new observation and transition the prior memory, respectively. Tanh applies element-wise to squash each hidden coordinate into $(-1, 1)$.

Notice the core architectural insight: the exact same parameter matrices $W_{xh}$, $W_{hh}$, and bias $b_h$ execute at step 1, step 2, and step 1,000. Parameters are tied across time rather than allocated anew for every token.^{[1]Reference 1On the Difficulty of Training Recurrent Neural Networkshttps://proceedings.mlr.press/v28/pascanu13.html}

Trace a vector RNN

Represent each incident event with three binary features:

These are one-hot event vectors: exactly one coordinate is 1 and all others are 0. They describe the incoming event at the current timestep, not cumulative flags.

Set up a two-dimensional hidden state ($d_h = 2$) and an initial state $h_0 = [0.0, 0.0]^T$, with biases set to zero for clean manual verification. At the first event $x_1 = [1, 0, 0]^T$, the matrix-vector multiplication $W_{xh} x_1$ extracts the first column of $W_{xh}$, which is $[0.8, 0.1]^T$. Since $h_0 = [0, 0]^T$, the recurrent term $W_{hh} h_0$ contributes nothing. The cell computes $[\tanh(0.8), \tanh(0.1)]^T \approx [0.664, 0.100]^T$.

The tensor dimensions dictate how the calculations scale. Let $d_x$ be input feature width and $d_h$ be hidden width:

Each row of $W_{hh}$ and $W_{xh}$ computes one hidden coordinate. Step through all three events in pure Python:

Attach a classification head to that final hidden state: a linear projection followed by softmax. This reuses the multiclass head from the previous lesson, with weight matrix $W_{\text{out}} \in \mathbb{R}^{3 \times 2}$ mapping the 2D summary into 3 action logits.

For row 1 (ignore), the pre-activation logit is $0.7 \times 0.390 - 0.3 \times 0.655 = 0.0765$. Rows 2 and 3 produce $0.368$ (rollback) and $0.170$ (escalate). Because $0.368$ is the largest logit, we know rollback will claim the highest softmax probability before running math.exp:

With these hand-chosen weights and the rounded final state, the head selects rollback with 38.9% probability. This isn't evidence of a trained incident classifier's accuracy. The head receives only $[0.390, 0.655]^T$, rather than the full history or a separate length input; the state may still encode information about length.

Count the parameters in a trainable version with one bias vector per affine block: $W_{xh}$ has 6 weights, $W_{hh}$ has 4, and $b_h$ has 2 biases, giving 12 recurrent parameters. A head with 6 weights and 3 trainable biases adds 9, totaling 21. The manual trace used zero biases. Changing sequence length doesn't change this count:

The final-state interface is a compression bottleneck: useful evidence from the history must be encoded in a fixed-width vector, and some details can be lost. During training, credit assignment to distant events travels backward through the recurrent channel.

Backpropagation through time: why a distant signal can fade

The forward pass assigned its highest softmax probability to rollback. During training, a target label and cross-entropy loss measure the error of that prediction. Backpropagation through time (BPTT) applies the chain rule backward across the unrolled sequence to compute gradients for the shared weight matrices.^{[1]Reference 1On the Difficulty of Training Recurrent Neural Networkshttps://proceedings.mlr.press/v28/pascanu13.html}

Because $W_{hh}$ acts at every timestep, its gradient accumulates local contributions across time. For a summed loss $L=\sum_{t=1}^T L_t(h_t)$, we can write:

$$\frac{\partial L}{\partial W_{hh}} = \sum_{t=1}^T \sum_{k=1}^t \frac{\partial L_t}{\partial h_t} \frac{\partial h_t}{\partial h_k} \frac{\partial^+ h_k}{\partial W_{hh}}$$

Here $\frac{\partial^+ h_k}{\partial W_{hh}}$ is the immediate local derivative at timestep $k$ with previous state $h_{k-1}$ held constant. The key term governing credit assignment over long sequences is the temporal chain:

$$\frac{\partial h_t}{\partial h_k} = J_t J_{t-1}\cdots J_{k+1}, \qquad J_j = \frac{\partial h_j}{\partial h_{j-1}}$$

To see why this chain causes instability, look at the one-dimensional cell we ran earlier: $h_j = \tanh(0.8 x_j + 0.5 h_{j-1})$. The local derivative from one state to the next is:

$$\frac{\partial h_j}{\partial h_{j-1}} = \left(1 - h_j^2\right) w_{\text{state}}$$

Because $\tanh'(z) = 1 - \tanh(z)^2 = 1 - h_j^2$, its mathematical derivative lies in $(0,1]$ for finite inputs. With recurrent weight $0.5$, the local factor is at most $0.5$, attaining that bound at $h_j=0$. Trace the product in our example:

The temporal derivative is $\partial h_3 / \partial h_0 \approx 0.0195$. If a final loss supplies derivative $g = \partial L / \partial h_3$, the gradient that reaches $h_0$ is only 0.0195 * g. That's less than 2% of the learning signal surviving after just three recurrent steps.

When every step compounds a factor of $0.6$, the shrinkage is exponentially steep:

A matrix bound, and what it actually proves

In the general multivariate case, the one-step derivative $J_j = \frac{\partial h_j}{\partial h_{j-1}}$ is a Jacobian matrix. Because $h_j = \tanh(W_{hh} h_{j-1} + W_{xh} x_j + b_h)$:

$$J_j = \frac{\partial h_j}{\partial h_{j-1}} = \operatorname{diag}\left(1 - h_j^2\right) W_{hh}$$

Backpropagating an error gradient column vector from timestep $T$ back to timestep $k$ multiplies by transposed Jacobians in reverse chronological order:^{[2]Reference 2Learning Long-Term Dependencies with Gradient Descent Is Difficulthttps://pubmed.ncbi.nlm.nih.gov/18267787/[1]Reference 1On the Difficulty of Training Recurrent Neural Networkshttps://proceedings.mlr.press/v28/pascanu13.html}

$$\nabla_{h_k} L = J_{k+1}^{\mathsf{T}} J_{k+2}^{\mathsf{T}}\cdots J_T^{\mathsf{T}}\nabla_{h_T} L$$

This expression assumes a loss only at the final state. When intermediate positions have losses, their gradient contributions must also be added. Matrix order matters: apply $J_T^{\mathsf{T}}$ first, then work backward. Using the induced Euclidean norm and its submultiplicative property gives:

$$\left\| \frac{\partial h_T}{\partial h_k} \right\| \le \prod_{j=k+1}^T \left\| \operatorname{diag}\left(1 - h_j^2\right) \right\| \cdot \| W_{hh} \| \le \left( \gamma \, \sigma_{\max}(W_{hh}) \right)^{T-k}$$

where $\gamma = \max_j \|\operatorname{diag}(1 - h_j^2)\| \le 1$, and $\sigma_{\max}(W_{hh})$ is the maximum singular value (spectral norm) of the recurrent matrix.

If one uniform bound satisfies $\gamma\sigma_{\max}(W_{hh})<1$ across the span, the temporal Jacobian contracts exponentially. This is a sufficient condition for a vanishing path. The total parameter gradient can still include strong contributions from recent positions.

If the bound exceeds one, growth is possible, but the upper bound doesn't prove explosion. Direction, successive activations, and alignment matter. For example, a matrix can have a singular value above one while its repeated powers eventually decay. Spectral-radius arguments for constant linear recurrences don't replace the Jacobian-product analysis of a nonlinear, input-dependent RNN.^{[1]Reference 1On the Difficulty of Training Recurrent Neural Networkshttps://proceedings.mlr.press/v28/pascanu13.html}

There is no universal 20- or 50-step float32 cutoff. For our illustrative factor, $0.6^{50}\approx8.08\times10^{-12}$ is still representable in float32. A small gradient may have little optimization effect before it underflows; whether a parameter update rounds away also depends on the parameter's scale and learning rate. In an expanding path, large gradients can instead destabilize updates or become nonfinite.

Truncation and gradient clipping

Two operational techniques manage these dynamics during training:

Truncated BPTT limits how far backward the computational graph extends. Training can split a long sequence into chunks, carrying state values forward while h = h.detach() cuts the graph at each boundary. An LSTM needs both h and c detached. This reduces graph memory but also removes credit assignment across the boundary; the forward state can retain evidence the current loss can no longer train earlier steps to store.

Gradient norm clipping addresses exploding gradients. If the $L_2$ norm of the gradient vector exceeds a threshold $c$, we rescale the vector:

$$g \leftarrow \min\left(1, \frac{c}{\|g\|_2}\right) g$$

For a finite, nonzero gradient, norm clipping rescales its magnitude while preserving direction in exact arithmetic.^{[1]Reference 1On the Difficulty of Training Recurrent Neural Networkshttps://proceedings.mlr.press/v28/pascanu13.html} It bounds the gradient, rather than guaranteeing a safe optimizer update. For plain SGD without momentum or weight decay, the step norm is at most $\eta c$; adaptive optimizers and momentum change that relationship. With $g=0$, leave it unchanged rather than evaluating $c/0$. Nonfinite gradients need detection and diagnosis, not just rescaling.

Clipping doesn't restore a small or vanished signal. Gates offer a different memory path; initialization, regularization, training objectives, and dependency length can also affect gradient flow. None is a guarantee that all long-range dependencies will be learned.

LSTM: Additive cell state and gated memory

Gradient clipping can't create long-term memory. LSTMs provide a path that doesn't force the stored state through a saturating activation at every update.

Long short-term memory (LSTM) addresses this difficulty with two related state vectors:^{[3]Reference 3Long Short-Term Memory.https://doi.org/10.1162/neco.1997.9.8.1735}

• Internal cell state ($c_t \in \mathbb{R}^{d_h}$): An internal gradient superhighway or conveyor belt that updates additively.
• Working hidden state ($h_t \in \mathbb{R}^{d_h}$): The exposed memory vector passed to the next layer and the output classifier.

Information flow is controlled by gates: learned, coordinate-wise affine projections squashed by the sigmoid function ($\sigma(z) \in (0, 1)$). A gate value near 0 acts as a closed valve; a value near 1 leaves the valve fully open. The standard modern formulation includes the forget gate introduced by Gers et al.^{[4]Reference 4Learning to Forget: Continual Prediction with LSTMhttps://doi.org/10.1162/089976600300015015}

Suppose a single coordinate in our cell state holds 0.855 after an error event. A routine health check arrives. We want to retain that earlier error flag while recording almost nothing new from the routine check:

The stored value ($c_t \approx0.840$) differs from the exposed state ($h_t \approx0.549$). Closing the output gate can hide a stored coordinate without immediately erasing it. These states are still coupled: the hidden state depends on the cell, and future gates depend on the hidden state. The values below are hand-chosen controls, not learned gates.

Step through three illustrative transitions in pure Python:

The full LSTM equations

In a trainable LSTM, learned affine projections compute these gate vectors from the concatenation of the prior working state $h_{t-1}$ and the current input $x_t$ (denoted $[h_{t-1}, x_t] \in \mathbb{R}^{d_h + d_x}$):

$$\begin{aligned} f_t &= \sigma(W_f [h_{t-1}, x_t] + b_f) && \text{(Forget gate: what to discard)} \\ i_t &= \sigma(W_i [h_{t-1}, x_t] + b_i) && \text{(Input gate: what to write)} \\ \tilde{c}_t &= \tanh(W_c [h_{t-1}, x_t] + b_c) && \text{(Candidate state: proposed facts)} \\ c_t &= f_t \odot c_{t-1} + i_t \odot \tilde{c}_t && \text{(Cell update: additive memory highway)} \\ o_t &= \sigma(W_o [h_{t-1}, x_t] + b_o) && \text{(Output gate: what to expose)} \\ h_t &= o_t \odot \tanh(c_t) && \text{(Exposed working state)} \end{aligned}$$

Here $\odot$ denotes the element-wise Hadamard product.

Follow the direct cell-state gradient path

In this standard LSTM without peephole connections, the cell receives $(h_{t-1},c_{t-1})$ as separate state inputs. Holding $h_{t-1}$ and $x_t$ fixed also holds the gates and candidate fixed. The direct cell-state Jacobian is:

$$\left.\frac{\partial c_t}{\partial c_{t-1}}\right|_{\text{gates fixed}} = \operatorname{diag}(f_t)$$

The contribution from following only this direct path across several steps is:

$$\text{direct-path factor} = \prod_{j=k+1}^T \operatorname{diag}(f_j) = \operatorname{diag}\left( \prod_{j=k+1}^T f_j \right)$$

Contrast this directly with the vanilla RNN product $\prod \operatorname{diag}(1 - h_j^2) W_{hh}$:

1. No repeated matrix powers: There is no $W_{hh}^{T-k}$ factor acting along this diagonal channel.
2. No saturating derivative: The cell state itself doesn't pass through $\tanh$ during the update.
3. Controllable retention: Forget gates near one slow decay. If every gate on a coordinate is 0.999 for 100 transitions, its direct-path factor is about 0.905, retaining 90.5%. At 0.5, the same product is approximately $7.89\times10^{-31}$.

The original LSTM's unit-weight cell self-connection was called the constant error carousel.^{[3]Reference 3Long Short-Term Memory.https://doi.org/10.1162/neco.1997.9.8.1735} A forget-gated LSTM learns retention instead of always copying the cell.^{[4]Reference 4Learning to Forget: Continual Prediction with LSTMhttps://doi.org/10.1162/089976600300015015} The full gradient also travels through hidden states and gate dependencies; the output readout includes $o_t\odot(1-\tanh^2(c_t))$, which can be small. LSTMs mitigate vanishing gradients rather than eliminating them, and they can still have exploding gradients.

GRU: Unified hidden state and streamlined gating

LSTMs maintain two state vectors ($c_t$ and $h_t$) and four distinct affine transformations per step. The gated recurrent unit (GRU) streamlines this architecture by collapsing the cell state and hidden state into a single vector $h_t$, and replacing the separate forget and input gates with a single update gate ($z_t$).^{[5]Reference 5Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation.https://arxiv.org/abs/1406.1078}

Instead of independent keep and write decisions, the update gate forms a convex combination:

$$h_t = z_t \odot h_{t-1} + (1 - z_t) \odot \tilde{h}_t$$

For an old state of 0.80 and a candidate of -0.20, retaining 95% ($z_t = 0.95$) automatically sets the write weight to 5%: 0.95 * 0.80 + 0.05 * (-0.20) = 0.750. The two mixture fractions always sum to 1.

The second gate is the reset gate ($r_t$), which decides how much of the prior hidden state is visible when computing the proposed candidate $\tilde{h}_t$:

$$\begin{aligned} z_t &= \sigma(W_z [h_{t-1}, x_t] + b_z) && \text{(Update gate: retain vs. overwrite balance)} \\ r_t &= \sigma(W_r [h_{t-1}, x_t] + b_r) && \text{(Reset gate: how much prior history candidate sees)} \\ \tilde{h}_t &= \tanh(W_h [r_t \odot h_{t-1}, x_t] + b_h) && \text{(Candidate state)} \\ h_t &= z_t \odot h_{t-1} + (1 - z_t) \odot \tilde{h}_t && \text{(Unified hidden state)} \end{aligned}$$

When $r_t \to 0$, the candidate calculation ignores past history and acts like a standard feedforward projection of $x_t$. When $z_t \to 1$, the unit ignores the candidate and carries the past state forward unchanged.

Test the convex blend across three update gate settings:

Reset gate placement: Cho et al. versus PyTorch

Here $z$ explicitly means the fraction kept from the old state, matching Cho et al. and PyTorch. Some descriptions give the complementary fraction the name "update gate," so compare equations rather than names. In Cho et al.'s candidate, the recurrent portion is $U_h(r_t\odot h_{t-1})$: reset scales the old state before its recurrent matrix multiplication.^{[5]Reference 5Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation.https://arxiv.org/abs/1406.1078} $U_h$ is the recurrent block of the concatenated matrix $W_h$ above.

PyTorch's nn.GRU applies the reset gate after the linear transformation:^{[6]Reference 6GRUhttps://docs.pytorch.org/docs/2.14/generated/torch.nn.GRU.html}

$$\tilde{h}_t = \tanh\left(W_{in} x_t + b_{in} + r_t \odot (W_{hn} h_{t-1} + b_{hn})\right)$$

PyTorch documents this deliberate change as an efficiency choice: the recurrent projections can be computed together before applying reset. It isn't a promise about a particular GPU kernel count.

Matrix multiplication and coordinate-wise scaling generally don't commute: $U_h(r\odot h)\ne r\odot(U_hh)$. Mixing coordinates can therefore change the output, although equal gates or particular inputs can make the two agree:

The two candidates differ significantly (-0.273 versus 0.040). When porting weights between frameworks, always check the exact candidate formulation.

Parameter auditing and tensor geometry

Every gate and candidate vector in an RNN cell emits $d_h$ values. With concatenated input $[h_{t-1}, x_t]$ of width $d_h + d_x$, each affine transformation requires a weight matrix of shape $(d_h, d_h + d_x)$ and a bias vector of shape $(d_h,)$.

Counting parameters per cell reveals the structural scaling:

For these one-layer cells with equal widths and one bias per block, GRU has three quarters as many parameters as LSTM. Its three affine blocks also require less dense projection work than four equal-sized blocks. Wall-clock speed still depends on batching, kernels, hardware, and other operations.

Why does PyTorch's nn.GRU report 42 parameters instead of 36? In production implementations, PyTorch stores separate input-hidden ($b_{in}$) and hidden-hidden ($b_{hn}$) bias vectors for each gate:^{[6]Reference 6GRUhttps://docs.pytorch.org/docs/2.14/generated/torch.nn.GRU.html}

$$\text{PyTorch GRU parameters} = 3 \times \left[ d_h(d_x + d_h) + 2d_h \right] = 3 \times (10 + 4) = 42$$

The extra biases don't change hidden width. They aren't all merely redundant storage: PyTorch's candidate recurrent bias is multiplied by reset, $r_t\odot b_{hn}$, so it generally can't be merged into a fixed input bias. Porting a textbook GRU requires checking both reset placement and bias placement.

For a one-layer, unidirectional nn.GRU(input_size=3, hidden_size=2, batch_first=True), an input batch tensor of shape (B, T, 3) outputs a tensor of shape (B, T, 2) and a final hidden state of shape (1, B, 2). Here $B$ counts independent sequences and $T$ counts timesteps. The leading dimension in the final hidden state represents $\text{num\_layers} \times \text{num\_directions}$, not sequence position.

Sequence padding and batch masking

In production workloads, sequences within a batch rarely have the same length. Frameworks pad shorter sequences with dummy values (typically zeros) into a uniform rectangular tensor.

A critical failure mode occurs when developers run an unmasked recurrent loop over padded rows. In an RNN, padding is still processed as an event. Even an all-zero input row triggers another state update:

$$h_t = \tanh(W_{hh} h_{t-1} + W_{xh} \mathbf{0} + b_h) = \tanh(W_{hh} h_{t-1} + b_h)$$

This generally differs from $h_{t-1}$, though a fixed-point state can remain unchanged. A zero row doesn't universally rotate or shrink memory; its effect depends on the recurrence. Verify the change for our chosen weights:

The state shifts from [0.494, 0.641] to [0.302, 0.367] on a zero row, and to [1.0, -0.889] on junk values. A classifier reading the post-padding state can therefore change its prediction because of filler rather than real incident data.

PyTorch's pack_padded_sequence packages the valid prefixes and their active batch sizes so the recurrent layer skips padding on CPU or GPU.^{[7]Reference 7torch.nn.utils.rnn.pack_padded_sequencehttps://docs.pytorch.org/docs/2.14/generated/torch.nn.utils.rnn.pack_padded_sequence.html} Lengths must describe right-padded sequences; a tensor of lengths must be on CPU. enforce_sorted=False lets the function sort internally. Each sequence needs a positive length no greater than the available timesteps.

Packing ensures the second sequence halts at $t=2$. Its final representation remains completely immune to whatever values occupy the padded slots.

Sequence compression and the encoder-decoder bottleneck

The vector RNN we built is an encoder: it takes a variable-length sequence of observations and condenses them into a single fixed-width hidden vector $h_T$.

In 2014, Cho et al.^{[5]Reference 5Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation.https://arxiv.org/abs/1406.1078} and Sutskever et al.^{[8]Reference 8Sequence to Sequence Learning with Neural Networks.https://arxiv.org/abs/1409.3215} used recurrent encoders and decoders to model a target sequence conditioned on a source sequence. Their interfaces differ: Cho et al. condition the decoder on a fixed context throughout, while Sutskever et al. use the encoder's state to initialize the decoder. Both communicate the source through a fixed-size representation.

While effective for short sentences, this setup encounters a strict information bottleneck: every nuance, entity, and causal dependency across a 100-word paragraph must fit through that single final hidden vector. The decoder has no direct access to earlier tokens; it can only peer through the keyhole of $h_T$.

The sequential bottleneck, and how attention changes it

Standard nonlinear recurrent cells have a sequential execution bottleneck across timesteps.

For a standard nonlinear RNN, LSTM, or GRU, calculating the new state requires the previous state:

$$s_t = f(s_{t-1}, x_t)$$

Here $s_t=h_t$ for the vanilla RNN or GRU, and $s_t=(h_t,c_t)$ for an LSTM.

The state transition at a position must wait for the previous state. A 4,096-token sequence therefore has 4,096 dependent transitions, not necessarily 4,096 GPU kernel launches. Input projections can be computed across positions in advance, batches run in parallel, and backend kernels may fuse work or use persistent algorithms.^{[9]Reference 9cuDNN Recurrent Neural Network Algorithmshttps://docs.nvidia.com/deeplearning/cudnn/backend/latest/api/cudnn-adv-library.html#cudnnrnnalgo-t}

Accelerators benefit from large matrix multiplications. With a small batch or hidden width, recurrent transitions may expose too little work to use them efficiently. With a batch, these projections are matrix-matrix operations, not just matrix-vector operations. Utilization and memory traffic depend on shapes and kernels; recurrent weights needn't be fetched from HBM anew for every step.

Self-attention breaks the serial chain

A Transformer replaces these recurrent transitions with self-attention and position-wise transformations.^{[10]Reference 10Attention Is All You Need.https://arxiv.org/abs/1706.03762} For tokens already present during training:

1. Parallel projections: Queries, keys, and values can be projected across the sequence together (often with a combined projection): $Q = X W_Q, \quad K = X W_K, \quad V = X W_V$
2. Direct routing: A position can attend directly to any position permitted by the mask: $\operatorname{Attention}(Q, K, V) = \operatorname{softmax}\left(\frac{QK^{\mathsf{T}}}{\sqrt{d_k}}+M\right) V$ A causal mask has $M_{ij}=-\infty$ for future positions $j>i$ and zero for allowed positions. Position 4,096 can receive a weighted value from Position 1 within one layer, instead of 4,095 recurrent relays. That is a constant graph path length, not constant computation time.

Attention also needs information about position to distinguish ordering beyond what the mask supplies. The original Transformer adds positional encodings. During autoregressive generation, future tokens aren't available yet, so generating new tokens still has a sequential dependency.

Fixed-width recurrent state doesn't imply constant training memory. Full BPTT saves intermediate activations across the sequence; truncation or recomputation changes that cost. The table's parallel-operation counts describe a fixed-depth layer's dependency structure, not GPU kernel counts or measured latency.

Full attention's quadratic pairwise work can be expensive for long sequences. FlashAttention avoids materializing the full $T\times T$ score matrix in GPU HBM, while still computing full attention rather than making the pairwise arithmetic linear.^{[11]Reference 11FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.https://arxiv.org/abs/2205.14135}

Some recurrent architectures support a different execution strategy. Mamba's selective state-space recurrence has input-dependent coefficients that can be prepared before its scan, enabling an associative parallel scan during training.^{[12]Reference 12Mamba: Linear-Time Sequence Modeling with Selective State Spaceshttps://arxiv.org/abs/2312.00752} Its recurrent state size and per-token update cost are constant with respect to sequence length for a fixed model. This doesn't make arbitrary nonlinear LSTM or GRU recurrences associative, and a parallel scan still has scheduling and reduction costs.

Diagnosing recurrent failure modes

When debugging sequence models in production, verify these three critical failure points:

When diagnosing training instability, evaluate gradient norms independently from loss values. A model can show stable forward losses while its early-timestep gradients have completely vanished.