Attention Complexity › Attention vs. RNN Complexity

To appreciate why the quadratic cost matters, let's compare attention to recurrent neural networks. Both architectures process sequences, but their computational patterns differ fundamentally. Understanding this comparison is important for two reasons. First, it contextualizes when attention's quadratic cost is a problem versus when it is irrelevant. Second, it makes precise the trade-off that motivated the transformer architecture: you pay more computation per token in exchange for dramatically shorter information paths.

Before transformers, recurrent networks (LSTMs and GRUs) were the dominant architecture for sequence modeling. These networks processed sequences token by token, maintaining a fixed-size hidden state that summarized everything seen so far. This sequential nature made them efficient in terms of total operations, but it created a critical weakness: information from early in the sequence had to propagate through many time steps to influence late positions. In a 1000-token sequence, information from the first token must survive 999 update steps to reach the last position. Each step involves a learned transformation, and information tends to degrade through this chain, a problem known as the vanishing gradient.

Attention sidesteps this problem entirely by connecting any two positions directly in a single operation. The cost of this directness is the quadratic scaling. Whether this trade-off is worth it depends on the sequence length, the nature of the task, and whether the long-range dependencies you care about are dense enough to justify the overhead.

The recurrent architecture's cost structure is fundamentally different from attention's. Rather than computing all pairwise interactions at once, an RNN processes tokens one at a time, updating a hidden state at each step. This sequential structure has practical consequences for both complexity and parallelizability.

An RNN with hidden dimension $d$ processes each of $n$ tokens sequentially. At each timestep $t$, the hidden state update follows:

$$h_t = \sigma(W_h h_{t-1} + W_x x_t + b)$$

where:

• $h_t$: hidden state at timestep $t$ (dimension $d$)
• $W_h$: hidden-to-hidden weight matrix (shape $d \times d$)
• $h_{t-1}$: previous hidden state (dimension $d$)
• $W_x$: input-to-hidden weight matrix (shape $d \times d$, assuming input dimension matches $d$)
• $x_t$: input at timestep $t$
• $\sigma$: activation function (e.g., tanh)

The computational cost per timestep is:

• Matrix-vector multiplication $W_h h_{t-1}$: $O(d^2)$ operations
• Matrix-vector multiplication $W_x x_t$: $O(d^2)$ operations
• Activation function: $O(d)$ operations

Total per step: $O(d^2)$. For $n$ tokens: $O(nd^2)$.

RNN complexity is linear in sequence length and quadratic in hidden dimension. This is a notable contrast with attention: the RNN pays its quadratic cost in the model dimension, while attention pays its quadratic cost in the sequence length. The choice of architecture is essentially a choice about which resource you can afford to spend quadratically.

Summarizing the complexity of each architecture:

• Attention: $O(n^2 d)$
• RNN: $O(nd^2)$

where $n$ is sequence length and $d$ is the hidden/model dimension.

The key insight is that these two complexities share the same functional form with $n$ and $d$ swapped. Attention is quadratic in $n$, linear in $d$. RNN is linear in $n$, quadratic in $d$. This symmetry is not coincidental: it reflects the fundamental trade-off between sequential processing (which pays a fixed cost per step but must be sequential) and parallel processing (which can run in parallel but must examine all pairs).

To find when these costs are equal, we set $n^2 d = nd^2$ and solve for $n$:

$$n^2 d = nd^2$$

Dividing both sides by $nd$ (assuming $n, d > 0$):

$$n = d$$

This crossover point has a clear interpretation: when sequence length exceeds model dimension ($n > d$), attention becomes more expensive. When model dimension exceeds sequence length ($n < d$), RNN becomes more expensive. In practice, modern language models have dimensions of 512 to 4096, meaning that attention is more expensive than RNN for any sequence longer than a few hundred to a few thousand tokens. Since many practical tasks involve sequences longer than that, this crossover is reached regularly in real workloads.

The crossover behavior has practical implications. For short sequences (a few hundred tokens), attention's overhead is minimal and often smaller than the equivalent RNN. For long documents, books, or conversation histories spanning thousands of tokens, the quadratic cost becomes the dominant bottleneck. This explains the historical dominance of transformers for classification and short generation tasks, alongside early proposals to handle long sequences through hierarchical chunking: run attention on small windows, then run attention again over the chunk summaries. The quadratic cost was "tamed" rather than solved until more principled efficient attention methods arrived.

Why use attention despite its higher cost at long sequences? The answer lies in path length, a concept that quantifies how "far" information must travel to flow from one part of a sequence to another. In an RNN, information from token $i$ to token $j$ must traverse $|j - i|$ sequential steps, each involving a learned transformation that can potentially lose or distort information. In attention, any two tokens connect in a single step, with no intermediaries.

Think of it as the difference between a telephone game and a conference call. In the telephone game (RNN), a message passes through a chain of people, each one rephrasing it before passing it on. After 50 iterations, the message may be unrecognizable. In a conference call (attention), everyone hears the original speaker directly, regardless of how far apart they are. The conference call is more expensive to organize for large groups, but it preserves message fidelity perfectly.