Attention Is All You Need — how deleting recurrence still won

Read "The animal didn't cross the street because it was too tired" and translate it word by word into German. By the time you reach it, animal is seven tokens back, and the decoder still has to know which noun the pronoun points to before it can choose the right German word. Nothing about the sentence changes this: the model has to carry that link forward across every intervening token.

A recurrent encoder does this by keeping one running summary. At each step $t$ it computes a hidden state $h_t$ from the current token and the previous state $h_{t-1}$, so information about animal survives only by being folded into $h_t$ at every subsequent step until it is reached ^[1][1] Introduction“they generate a sequence of hidden states $h_t$, as a function of the previous hidden state $h_{t-1}$ and the input for position $t$. This inherently sequential nature precludes parallelization wit…”Open source. This is what recurrence provides: a single evolving memory, threaded token by token, that can in principle hold a dependency of any length.

The same rule that makes this memory possible also makes it slow to train. Computing $h_t$ requires $h_{t-1}$ to already exist, which requires $h_{t-2}$, back to the start of the sentence. That dependency chain cannot be broken by adding more compute: a second GPU cannot compute step 6 before step 5 has finished, because step 6's input does not exist yet. Training is forced into $O(n)$ sequential updates per example, however many positions $n$ the sentence has, and this sequential requirement is exactly what limits parallelization within a training example ^[1][1] Introduction“they generate a sequence of hidden states $h_t$, as a function of the previous hidden state $h_{t-1}$ and the input for position $t$. This inherently sequential nature precludes parallelization wit…”Open source.

Suppose the recurrent chain is deleted outright and every position is exposed to the network simultaneously. The serialization problem disappears: all $n$ hidden states can now be computed in one parallel pass. But it still needs to know that animal, not street, is the word it refers to, and simultaneous visibility of every token says nothing yet about which one to use.

By the time self-attention runs, "animal" and "street" are both already sitting in view of the position representing "it" — recurrence's step-by-step handoff is gone, so nothing has to wait its turn. But visible is not the same as read. Suppose "it" just averaged every position's vector with equal weight: the result blends "animal" and "street" into one smeared vector, which is exactly the ambiguity the pronoun needed resolved, not an answer to it. Something has to decide, position by position, how much of "animal" versus how much of "street" belongs in the vector eventually assigned to "it" — and that something can no longer be a hidden state passed down a chain.

The fix is to give each position three learned projections of its embedding: a query $Q$ describing what that position is searching for, a key $K$ describing what it offers to be matched against, and a value $V$ holding the content actually retrieved. The output at a position becomes a weighted sum of every position's value, where the weight comes from a compatibility score between that position's query and each other position's key ^[2][2] Attention“The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key.”Open source. For "it", the query encodes something like "what was tired"; the key for "animal" is built to score high against that question, and the key for "street" is not.

Turning those raw scores into an actual read requires normalizing them: softmax converts the row of scores belonging to "it" into a distribution over positions, and that distribution weights the corresponding values ^[2][2] Attention“The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key.”Open source. The result is scaled dot-product attention, $\mathrm{Attention}(Q,K,V)$: if the score between "it" and "animal" dominates its row, "it" reads back mostly "animal"'s value and "street" contributes almost nothing to the sum. No step here depends on a previous step's output — the row for "it" is computed independently of, and in parallel with, every other row.

Nothing so far bounds how large one raw dot product can get. As the query and key dimensions grow, a handful of coordinates lining up between $Q$ and $K$ can push a single score far above its neighbors, and softmax's response to a runaway score is not sharper selection — it is a saturated, nearly one-hot distribution with almost no gradient left for training to use ^[2][2] Attention“The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key.”Open source.

Suppose the raw dot product between the query for $it$ and the key for $animal$ comes out largest simply because $d_k$ is large, not because $animal$ is semantically the better antecedent: summing across many independent coordinates makes an extreme value more likely by chance alone as $d_k$ grows ^[3][3] Attention“has mean $0$ and variance $d_k$”Open source. Feed that raw score $QK^T$ straight into $\mathrm{softmax}$, which weights each value by a compatibility score between query and key ^[2][2] Attention“The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key.”Open source, and the exponential turns a modest gap over the smaller score for $street$ into a near one-hot weight: $animal$ gets almost all the mass, everything else almost none.

That near one-hot outcome looks correct here only by luck, and the same mechanism will misfire whenever the true antecedent is not the accidental maximum. The cause is structural: if each of the $d_k$ components of $q$ and $k$ is an independent random variable with mean $0$ and variance $1$, the dot product $q\cdot k=\sum_{i=1}^{d_k}q_ik_i$ has mean $0$ and variance $d_k$ ^[3][3] Attention“has mean $0$ and variance $d_k$”Open source. Larger $d_k$ spreads scores wider, pushing more of them into the region where softmax has extremely small gradients ^[4][4] Attention“pushing the softmax function into regions where it has extremely small gradients”Open source. The fix divides every score by $\sqrt{d_k}$ before the softmax, producing the scaled score, which rescales variance back to roughly $1$ regardless of $d_k$ and keeps scores in the region where softmax's gradient still carries signal.

Scaling fixes the gradient problem, not the underlying constraint: scaled or not, the weights out of $\mathrm{softmax}(\cdot)$ still sum to one, so one softmax distribution can only spend its whole probability mass on a single blended view of every other token. The vector for $it$ still gets exactly one weighted mixture of $animal$, $street$, and everything else at once, never several independent judgments.

Go back to the sentence about the tired animal. The vector for "it" has two jobs to do at once: find its antecedent ($animal$) and pick up the modifier that describes it ($tired$). A single scaled dot-product attention pass ^[2][2] Attention“The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key.”Open source produces exactly one softmax distribution over every position. Whatever routing pattern that one distribution learns has to carry both relations at once, so the weight mass meant for coreference and the weight mass meant for the modifier get folded into the same blended value vector. There is no slot inside one softmax to keep those two relations separate.

The fix is not a bigger or smarter single attention function. It is several smaller ones run side by side. $Q$, $K$, and $V$ are each linearly projected $h$ times into their own subspaces, $d_k$-dimensional for queries and keys and value dimension-dimensional for values, using separate learned matrices per head. Each head then runs its own scaled dot-product attention independently and in parallel: one head can learn to track "it" back to "animal" while a different head learns to track "it" forward to "tired", instead of one softmax averaging both into a single view, and because each head works in its smaller $d_k$/$d_v$-dimensional subspace rather than the full $d_{model}$ dimension, running $h$ heads in parallel costs about the same as one full-dimensional head would ^[5][5] Attention“Multi-head attention allows the model to jointly attend to information from different representation subspaces at different positions.”Open source.

Eight heads now resolve coreference and modifier attachment as separate, parallel routing patterns instead of one blended average. But every one of those heads still computes its weights from a set of keys and values with no sense of order attached to them: swap $animal$ and $street$ in the input and a head that routes purely by content produces the identical attention pattern on the swapped sentence. Multi-head attention fixes the averaging problem and leaves the ordering problem exactly where it was.

Run the sentence through everything built so far, then swap two words: "The street didn't cross the animal because it was too tired." Every content-based score $QK^T$ comes out identical, because query-key-value routing compares only what each token contains, never where it sits ^[2][2] Attention“The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key.”Open source. "It" attends to "animal" or "street" with the same weights in both sentences. The two sentences mean different things and produce identical attention. Nothing built so far can see word order at all.

The fix does not touch attention. Before the first layer, a fixed vector is added directly to each token's embedding at position index $pos$, the token's index in the sequence, so an early position and a late position start from different vectors before any query or key is ever computed ^[6][6] Positional Encoding“we add "positional encodings" to the input embeddings at the bottoms of the encoder and decoder stacks”Open source.

Low $i$ gives short wavelengths near $2\pi$; high $i$ stretches toward $10000\cdot2\pi$, so the $d_{model}$ dimensions sweep a whole range of frequencies. That range is what makes offsets recoverable: for any fixed fixed offset $k$, trigonometric addition turns $PE_{pos+k}$ into a linear function of $PE_{pos}$, with coefficients depending only on $k$, not on $pos$ ^[7][7] Positional Encoding“since for any fixed offset $k$, $PE_{pos+k}$ can be represented as a linear function of $PE_{pos}$”Open source. A single linear map can convert "eight tokens back" into an operation a query can act on, without the model learning a separate vector per absolute position.

Adding $PE_{(pos,2i)}$ leaves the embedding's dimension at $d_{model}$ unchanged: the encoding has the same dimension as the embedding so the two can be summed rather than concatenated ^[6][6] Positional Encoding“we add "positional encodings" to the input embeddings at the bottoms of the encoder and decoder stacks”Open source, and every later sublayer still receives the same $d_{model}$-wide input it expected before position was added.

The encoder can now tell "animal" from "street" and knows "it" sits eight positions past "animal." But positional encoding only says where each token is; it says nothing about direction. Left unmasked, the decoder's self-attention still lets "it" attend to every position, including words the translation has not produced yet.

Picture the decoder midway through producing the German sentence, having just emitted the word for tired. Its self-attention sub-layer is built exactly like the encoder's: every query forms a compatibility score against every key at every position in the sequence ^[2][2] Attention“The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key.”Open source. During training the entire target sentence already sits in memory at once, so nothing stops the query at this step from reading a key several words ahead, at a token the model has not actually generated yet. A model that can see its own future output does not learn to translate; it learns to copy.

The fix is arithmetic, not new architecture. Before the softmax inside decoder self-attention, every score for a connection from position $i$ to a later position $j>i$ is overwritten with $-\infty$ ^[8][8] Attention“We implement this inside of scaled dot-product attention by masking out (setting to $-\infty$) all values in the input of the softmax which correspond to illegal connections.”Open source. Softmax turns that entry into weight $0$, so no value from an unseen future token ever reaches the output; the causal mask $M$ records exactly this pattern of legal and illegal connections. Combined with shifting the target sequence right by one position before it enters the decoder, so the input consumed at step $i$ is the ground-truth token from step $i-1$, this guarantees the prediction for position $i$ depends only on positions earlier than $i$ ^[9][9] Encoder and Decoder Stacks“This masking, combined with fact that the output embeddings are offset by one position, ensures that the predictions for position $i$ can depend only on the known outputs at positions less than $i$.”Open source.

Apply this to the German sentence: at the step producing the word for tired, the mask zeroes out every score pointing to positions still to come, leaving only words already emitted, plus — through the separate encoder-decoder attention sub-layer — the whole source sentence, animal included ^[10][10] Attention“In "encoder-decoder attention" layers, the queries come from the previous decoder layer, and the memory keys and values come from the output of the encoder.”Open source. Training and inference now match: at both, position $i$ only ever sees what came before it. Correctness is settled. What is not yet settled is cost: this masked self-attention still scores every pair of positions at every layer ^[2][2] Attention“The output is computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key.”Open source, the same all-pairs computation recurrence was built to avoid — is that trade actually cheaper?

Line up the two costs and self-attention looks like it lost the trade. A self-attention layer costs $O(n^2 \cdot d)$ per layer; a recurrent layer costs $O(n \cdot d^2)$ ^[11][11] Why Self-Attention“Self-Attention & $O(n^2 \cdot d)$ & $O(1)$ & $O(1)$ \\ Recurrent & $O(n \cdot d^2)$ & $O(n)$ & $O(n)$ \\”Open source. Read that literally: for long enough sequences, deleting recurrence should have made training slower, not faster. Here $n$ is the sequence length, the number of tokens the layer processes.

"Long enough" is carrying the whole argument, and it never arrives for this running example. Translating the tired-animal sentence as a single sentence produces a token count far below $d_{model}=512$ in this model, and that gap between $n$ and $d_{model}$ is the ordinary case for sentence-level machine translation with word-piece or byte-pair vocabularies ^[11][11] Why Self-Attention“Self-Attention & $O(n^2 \cdot d)$ & $O(1)$ & $O(1)$ \\ Recurrent & $O(n \cdot d^2)$ & $O(n)$ & $O(n)$ \\”Open source. When $n<d_{model}$, the squared factor in $n^2 \cdot d$ is attached to the smaller quantity, so self-attention's per-layer cost is actually lower than recurrence's $n \cdot d^2$, not higher. The naive read of the table, extrapolated to sentence-length inputs, gives the wrong answer.

Per-layer FLOPs are only one column of the table. Self-attention connects every position to every other position in a single matrix multiply, so it needs only $O(1)$ sequential operations regardless of $n$; recurrence needs $O(n)$ steps, one hidden state at a time, before position $n$ can see position $1$. The same gap shows up in path length: the maximum distance a signal travels between any two positions is $O(1)$ for self-attention against $O(n)$ for recurrence, so resolving "it" back to "animal" costs one hop instead of one hop per intervening word ^[11][11] Why Self-Attention“Self-Attention & $O(n^2 \cdot d)$ & $O(1)$ & $O(1)$ \\ Recurrent & $O(n \cdot d^2)$ & $O(n)$ & $O(n)$ \\”Open source. Three separate numbers in the table (cost, parallelism, path length) all favor self-attention once $n<d$, which is exactly why a per-layer exponent that looks worse in isolation does not settle the question.

None of this is a measured result. Fewer sequential steps and shorter paths are architectural properties read off a complexity table, not observed training time or translation quality. Whether they convert into faster wall-clock training and higher BLEU on an actual model is a separate claim the table cannot make on its own.

Every property established so far — $O(1)$ sequential steps, $O(1)$ path length between "it" and "animal", cheaper per-layer cost when sequence length stays below $d_{model}$ — describes what the connection graph allows, not what training actually produced. The hook that opened this page was exactly this kind of promise: a per-layer cost of $O(n^2 \cdot d)$ that looks worse than recurrence's $O(n \cdot d^2)$, redeemed only if shorter paths and full parallelism translate into faster training and better translations. A favorable complexity table does not guarantee a better translation: architectures with appealing asymptotic bounds have failed to beat a well-tuned recurrent baseline once real optimization, vocabulary, and decoding costs enter the picture. The claim needs a number, not a table.

The number arrived. Training the big Transformer for $3.5$ days on $8$ P100 GPUs produced $28.4$ BLEU on WMT14 English-to-German, more than $2$ BLEU above the strongest previously published ensemble, and $41.8$ BLEU on WMT14 English-to-French, a new single-model state of the art ^[12][12] Machine Translation“outperforms the best previously reported models (including ensembles) by more than $2.0$ BLEU, establishing a new state-of-the-art BLEU score of $28.4$”Open source ^[13][13] Abstract“our model establishes a new single-model state-of-the-art BLEU score of 41.8 after training for 3.5 days on eight GPUs”Open source. The base model — smaller and far cheaper to train — still surpassed every earlier single model and ensemble at a fraction of their training cost ^[14][14] Machine Translation“Even our base model surpasses all previously published models and ensembles, at a fraction of the training cost of any of the competitive models.”Open source.

That result settles translation. It does not settle whether $O(1)$ path length is doing something general or just something German-and-French-shaped. The same architecture, four layers, with only dropout, learning rate, and beam size tuned on a held-out set, was then pointed at English constituency parsing — a task whose output is a tree, not a sentence, and whose length dwarfs its input. It reached $92.7$ F1 in the semi-supervised setting, beaten only by a purpose-built recurrent grammar model ^[15][15] English Constituency Parsing“despite the lack of task-specific tuning our model performs surprisingly well, yielding better results than all previously reported models with the exception of the Recurrent Neural Network Grammar”Open source. A mechanism built to shorten the path between "it" and "animal" turned out to shorten paths generally: that is the sense in which deleting recurrence, not just approximating it more cheaply, is what won.