Why Global Attention Runs in Parallel—and What It Costs
The Transformer’s claim to efficiency is easy to compress into a misleading sentence: “attention is faster.” The more useful question is what kind of work becomes parallel, how many dependent steps information must cross, and how much arithmetic is required to make every position available to every other position. This chapter uses the Transformer’s comparison with recurrent and convolutional layers to make those three criteria precise, then shows where global attention’s advantage gives way to quadratic interaction cost and sequential generation.
That distinction matters because “parallel” has several meanings. A layer may perform many calculations at once while still requiring a long chain of layers for two distant positions to influence each other. Conversely, a layer may offer a short path between positions but perform so much pairwise work that long sequences become expensive. The Transformer’s design changes all three dimensions at once, so they must be examined together.
Three ways to measure a sequence layer
The first criterion is per-layer computational complexity: how much arithmetic must a layer perform as the sequence length, representation dimension, or local neighborhood changes? The second is the minimum number of sequential operations: even with enough hardware, how many dependent steps must be completed one after another before the layer can produce its result? The third is maximum path length: how many transformations separate two arbitrary positions when a signal travels from one to the other? The paper uses all three because none is a substitute for the others.
Per-layer complexity describes total work, not elapsed time by itself. A large amount of work can be divided across processors, while a smaller amount may be trapped in a serial dependency chain. Sequential operations describe that second constraint. Path length describes the route through which information or a learning signal travels; it is related to, but not identical with, the number of operations needed to execute the whole layer.
For the layer types compared in the paper, the summary is:
| Layer type | Per-layer complexity | Sequential operations | Maximum path length |
|---|---|---|---|
| Self-attention | O(n² · d) |
O(1) |
O(1) |
| Recurrent | O(n · d²) |
O(n) |
O(n) |
| Convolutional | O(k · n · d²) |
O(1) |
O(logₖ n) |
| Restricted self-attention | O(r · n · d) |
O(1) |
O(n/r) |
Here, n is sequence length, d is representation dimension, k is convolution kernel size, and r is the neighborhood size considered by restricted attention. The table is not a ranking with one winner in every row. It is a map of what each design makes easy and what it makes expensive.
Consider what happens when a sentence becomes longer. In a recurrent layer, the new positions add more state transitions, so both the amount of work and the serial route grow with n. In unrestricted self-attention, the new positions also create new pairs with the positions already present. The layer can still form the score matrix as one batched operation, but the number of relationships represented in that matrix grows quadratically. A longer sequence therefore stresses the two designs differently: recurrence exposes waiting, while global attention exposes pairwise volume.
Path length adds a question about learning rather than only execution. If a word at the beginning must influence a representation near the end, a recurrent route carries that influence through every intervening update.