Transformer parallelism

Why did reading every word of a sentence at once beat reading them in order?

Language arrives in order. We speak in order, we read in order, and for most of the 2010s the models that handled language processed it in order too — recurrent networks, taking one word, updating a hidden state, taking the next. It matched the phenomenon so naturally that the design felt almost forced.

Then in 2017 a paper called "Attention Is All You Need" removed the recurrence entirely, processed the whole sentence at once, and won. The strange part is that the new design is, per sentence, more arithmetic, not less. So the interesting question is not "why is it faster?" but something sharper: how can doing more total work be the thing that made larger models possible?

Separate two quantities that our intuition keeps welding together. One is total work: how many multiplications must happen. The other is depth: how many of those must happen strictly one after another, because each needs the previous one's result.

For a recurrent network reading a sentence of length n, total work is proportional to n, which sounds excellent. But the depth is also n — state 40 cannot be computed until state 39 exists. Now ask the question that decides everything: what does a machine with thousands of parallel arithmetic units do with a chain of 40 dependent steps? Nothing useful. It performs one small step, waits, performs the next. The hardware idles.

Attention makes the opposite trade. Every position attends to every other, so the work grows with n squared — for a sentence of 64 words, roughly four thousand pairwise scores instead of 64 updates. But the sequential depth is one. All those scores depend only on inputs that already exist, so they can be computed simultaneously. And they are not merely parallel in principle: the whole operation is a matrix multiplication, which is precisely the shape modern accelerators are built to execute at their peak rate.

So the trade is: multiply the work by n, divide the depth by n. On hardware whose parallel capacity vastly exceeds what a serial chain can use, that is a superb bargain — and it is a bargain that gets better as chips get wider, which is the direction chips have been getting.

Push on a second consequence, which mattered as much. In a recurrent network, information from word 3 reaches word 60 by passing through 57 successive state updates, each one a lossy squeeze through the same fixed-size vector. Gradients flowing back along that chain shrink or explode; LSTMs and GRUs were built to mitigate this and only partly succeeded. In attention, word 60 reads word 3 directly. The path length between any two positions is constant. Both the forward signal and the training gradient travel one hop instead of fifty-seven — which is why long-range dependencies became learnable rather than merely representable.

Now the objection you should raise: if all positions are processed simultaneously, how does the model know the order of the words? It does not, and that is a real hole in the design. Attention is permutation-equivariant — shuffle the inputs and you shuffle the outputs identically. Order has to be injected separately, as positional encoding: a signal added to or folded into each token's representation that says where it sits. The original paper used fixed sinusoids; today rotary embeddings are common. Order became a piece of content rather than a property of the process, and that substitution is the deepest change the architecture made.

Is the quadratic cost a problem? Yes, eventually. At a few thousand tokens it is comfortably affordable; at a hundred thousand it dominates, and a large research literature — sparse attention, linear approximations, state-space models such as Mamba — exists to attack precisely that term. It is worth being honest that the quadratic cost was never a virtue. It was an acceptable price at the sequence lengths of 2017, and the architecture won because that price bought parallelism at exactly the moment when hardware had parallelism to sell.

Three refinements.

First, the parallelism belongs to training and prompt processing, not to generation. When a transformer writes, it produces one token at a time and each depends on the last, so the serial chain that recurrence imposed on reading returns in full for writing. The architecture parallelised the half of the problem where the answer was already known.

Second, "n squared" is worth keeping in perspective. Attention is quadratic in sequence length, but the feed-forward layers — which hold most of a model's parameters — are linear in it and have a large constant. For typical sequence lengths, the feed-forward layers, not attention, consume most of the compute. Attention dominates only when contexts grow long.

Third, correct a tempting inference. Transformers did not beat recurrent networks because attention is a better model of language. Both are universal enough in practice. Transformers won because their computation graph is wide and shallow rather than narrow and deep, and that shape is what turns more GPUs into a better model. The architecture was, in effect, chosen by the hardware — and much of what followed, including the scaling laws that made large models a deliberate engineering programme, rests on that fit.

• Why generation loses this parallelism entirely, and what speculative decoding does about it.
• How rotary positional embeddings encode relative distance rather than absolute position, and why that extrapolates better.

Every term the collection defines is gathered in the glossary.