SESKStuff Everyone Should Know
SESK: Stuff Everyone Should Know · sesk.info/ai-rnn-sequential-bottleneck

Why are ordinary RNN time steps difficult to parallelize within one sequence?

Each step needs the previous step's state.

Start playing free

  1. Steps depend sequentially ✔
  2. Weights are always integers
  3. Sequences contain only images

Why: An RNN cannot generally compute time step t before obtaining the state from t minus 1. A length n sequence therefore needs O(n) sequential operations.

Huh, didn't know that: Self-attention connects sequence positions with O(1) sequential operations per layer, though its total work can grow quadratically with length.

The dad joke
The RNN formed a line because every step waited its turn.
Like this card?
Play the game

References

Answer: Steps depend sequentially. An RNN cannot generally compute time step t before obtaining the state from t minus 1. A length n sequence therefore needs O(n) sequential operations.

  1. Attention Is All You Need (Vaswani et al., 2017) arxiv.org/html/1706.03762
    a self-attention layer connects all positions with a constant number of sequentially executed operations, whereas a recurrent layer requires
    Checked 2026-10-11.

Think this answer is wrong? Tap "Challenge this answer" on the card in the game and tell us why.

Test yourself in the game

Artificial IntelligenceWhat lets a recurrent neural network carry information through a sequence?Artificial IntelligenceHow does backpropagation through time treat a recurrent network?Artificial IntelligenceHow do AI, machine learning and deep learning fit together?

That's stuff everyone should know.