Sequential Computation in Recurrent Networks

Recurrent Neural Networks (RNNs), including their more sophisticated variants like LSTMs and GRUs, are designed around the principle of processing sequences element by element. At each time step $t$, an RNN takes the input $x_t$ and the hidden state from the previous time step $h_{t-1}$ to compute the current hidden state $h_t$. This process can be represented abstractly as:

$$h_t = f(h_{t-1}, x_t; \theta)$$

where $f$ represents the recurrent function (e.g., involving matrix multiplications and activation functions like tanh or sigmoid, or the more complex gating logic of LSTMs/GRUs) parameterized by weights $\theta$. An optional output $y_t$ can also be generated at each time step, often derived from $h_t$.

This formulation reveals the core characteristic of recurrent models: an inherent sequential dependency. The computation of the hidden state at time step $t$ must wait for the completion of the computation at time step $t-1$. This dependency forms a chain stretching across the entire sequence length.

An unrolled RNN illustrating the sequential flow of information. The hidden state $h_t$ depends directly on the previous state $h_{t-1}$ and the current input $x_t$.

While the computations within a single time step (e.g., matrix multiplications inside $f$) can often leverage parallel hardware like GPUs, the computation across time steps cannot be parallelized. You cannot compute $h_t$ and $h_{t+1}$ simultaneously because $h_{t+1}$ requires $h_t$ as input.

This sequential constraint has significant performance implications:

1. Training Time: For a sequence of length $L$, the time complexity for the forward and backward passes scales linearly with $L$. Processing longer sequences directly translates to longer training times, irrespective of the parallel processing power available for intra-step computations.
2. Inference Latency: Similarly, generating an output sequence or making a prediction based on a long input sequence requires iterating through each time step sequentially, increasing latency.

This contrasts sharply with architectures like feed-forward networks or convolutional neural networks (CNNs) applied to sequences (e.g., 1D convolutions). In those models, computations for different parts of the input sequence can often be performed independently and in parallel, leading to greater efficiency, particularly on specialized hardware.

While LSTMs and GRUs introduce sophisticated gating mechanisms to better control information flow and address gradient problems (discussed next), they fundamentally adhere to this same sequential processing approach. The calculation of gates (input, forget, output) and cell states at time $t$ still relies on the hidden state and cell state from time $t-1$.

Therefore, the inability to parallelize computations across the sequence length dimension is a fundamental bottleneck inherent in the core design of recurrent networks. This limitation was a primary motivator for exploring alternative architectures, like the Transformer, capable of processing sequence elements more concurrently.