Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Self-Attention Concept › Self-Attention vs Recurrence

Michael BrenndoerferUpdated February 6, 20266 min read

Language AI HandbookAll chapters

Part 13 of 67Self-Attention

Chapter 90Self-Attention Concept › Self-Attention vs Recurrence

Reading section 7 of 13 · Self-Attention vs Recurrence · 6 minSection 7 of 13 · 6 min

Section 7 of 13 · 6 min read

Self-Attention Concept › Self-Attention vs RecurrenceOne section · Sections in this chapter7 / 13 ↓

Sections in this chapter13

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Self-attention and recurrence represent fundamentally different approaches to sequence modeling. Understanding their trade-offs clarifies why transformers have largely replaced RNNs for most NLP tasks.

Parallelization: RNNs process tokens sequentially because each hidden state depends on the previous one. Self-attention computes all pairwise interactions simultaneously, enabling massive parallelization on GPUs. This difference dramatically accelerates training on modern hardware.

Long-range dependencies: In an RNN, information must flow through many timesteps to connect distant positions. Gradients can vanish or explode along this path. Self-attention connects any two positions directly, making it easier to learn long-range dependencies.

Computational complexity: Self-attention computes $n^2$ pairwise interactions for a sequence of length $n$ , where $n$ is the number of tokens. RNNs have linear complexity, meaning their computational cost grows proportionally to $n$ . For very long sequences, the quadratic cost of self-attention becomes prohibitive: doubling the sequence length quadruples the computation. This motivates efficient attention variants.

Positional information: RNNs inherently encode position through their sequential processing. Self-attention treats all positions symmetrically and requires explicit positional encodings to distinguish word order. We'll cover positional encodings in a later chapter.

It is worth pausing on the parallelization advantage, because it is easy to underestimate how important it is. The difference between $O(n)$ and $O(n^2)$ operations sounds like RNNs should be faster, but this analysis ignores the sequential bottleneck. An RNN processing a sequence of length $n$ must execute $n$ sequential steps, because step $t$ depends on the output of step $t-1$ . No amount of hardware parallelism can overcome this dependency. A modern GPU with thousands of cores cannot use most of them to process a single RNN sequence, because at each step, only one computation is active.

Self-attention, by contrast, computes all $n^2$ pairwise interactions simultaneously. With sufficient hardware, these can all be computed in parallel, making the wall-clock time essentially constant regardless of sequence length (up to memory constraints). In practice, the $n^2$ operations are organized as two matrix multiplications, each of which maps perfectly onto GPU tensor cores. This is why transformers can be trained on sequences of thousands of tokens in reasonable time, while training deep RNNs on sequences longer than a few hundred tokens was extremely slow.

The practical consequence of this difference was the scaling revolution. Transformers could be trained on much larger datasets in less time than RNNs, because more of the compute could be utilized in parallel. This, combined with the architectural improvements from self-attention, is why models like BERT and GPT-2 represented such dramatic jumps in capability compared to their RNN-based predecessors.

Memory requirements: Self-attention must store the entire $n \times n$ attention weight matrix during computation, requiring $O(n^2)$ memory. For a sequence of 10,000 tokens, this is 100 million weights, which requires several gigabytes of memory even in 16-bit precision. RNNs require only $O(nd)$ memory, where $d$ is the hidden state dimension, because only the current hidden state needs to be stored. This memory bottleneck is one of the key practical constraints on self-attention and has motivated research into memory-efficient attention variants.

Inductive biases: RNNs have a strong inductive bias toward local, recency-weighted processing. They naturally place more emphasis on recent tokens (the hidden state is more directly influenced by recent inputs) and require explicit mechanisms like LSTMs to maintain long-term information. Self-attention has a weaker, more uniform inductive bias: all positions are treated symmetrically, and the model must learn from data which positions are relevant. This makes self-attention more flexible but also means it requires more data to learn good patterns from scratch.

In[11]:

Code

# Compare computational patterns
def analyze_complexity(seq_lengths):
    """Compare RNN vs self-attention complexity."""
    results = []
    for n in seq_lengths:
        rnn_ops = n  # Sequential, linear in sequence length
        self_attn_ops = n * n  # All-pairs, quadratic
        results.append(
            {
                "seq_len": n,
                "rnn": rnn_ops,
                "self_attention": self_attn_ops,
                "ratio": self_attn_ops / rnn_ops,
            }
        )
    return results


seq_lengths = [10, 50, 100, 500, 1000]
complexity = analyze_complexity(seq_lengths)

Out[12]:

Visualization

Line plot showing linear RNN complexity and quadratic self-attention complexity diverging as sequence length increases. — Computational complexity scaling: RNN (linear O(n)) vs self-attention (quadratic O(n^2)). While self-attention requires dramatically more operations for long sequences, these operations are fully parallelizable. The quadratic curve illustrates why processing very long documents requires either hardware with large memory or efficient attention approximations.

The quadratic growth of self-attention is dramatic: at sequence length 1000, self-attention requires 1 million operations compared to just 1000 for an RNN. However, self-attention's operations are independent and can run in parallel on GPUs, while RNN operations must be sequential. This trade-off explains why transformers dominate despite higher theoretical complexity: parallelism wins on modern hardware.

To put concrete numbers on this: a typical transformer layer with sequence length 512 and embedding dimension 768 spends roughly 40% of its compute on the attention matrix multiplication and 60% on the feed-forward layers. The quadratic bottleneck is real but manageable for sequences of a few hundred to a few thousand tokens. For the long-context models that have emerged recently, with context windows of 32,000 or 128,000 tokens, efficient attention algorithms (such as FlashAttention, which reorganizes the computation to minimize memory bandwidth rather than total operations) are essential.