Self-Attention Concept › All-Pairs Interaction

The defining characteristic of self-attention is all-pairs interaction. For a sequence of $n$ tokens, self-attention computes interactions between all $n^2$ pairs of positions. Why $n^2$? Each of the $n$ tokens must compute its relationship with every other token, including itself. Token 1 interacts with tokens 1 through $n$ (that's $n$ interactions), token 2 does the same (another $n$ interactions), and so on for all $n$ tokens, giving us $n \times n = n^2$ total interactions.

This is fundamentally different from recurrent models, which process tokens sequentially and must pass information through intermediate states.

In an RNN, if you want information from position 1 to reach position 100, it must flow through 99 intermediate hidden states. Each step risks losing or distorting information. Self-attention eliminates this problem by computing direct connections between any two positions.

The all-pairs property gives self-attention its expressive power. Consider trying to model long-distance syntactic agreement. In English, a subject and verb must agree in number: "The keys to the cabinet are on the table" versus "The key to the cabinets is on the table." The head noun "keys" or "key" determines the verb form, but in a complex sentence with intervening phrases, the distance between them can be substantial. An RNN must carry the number information through every intervening token without losing it, relying on the hidden state to serve as a memory buffer. Self-attention can compute a direct edge from the subject to the verb, regardless of distance.

Similarly, consider coreference: understanding that "it" in "The cat knocked over the vase because it was clumsy" refers to the cat, not the vase. The model needs to compare "it" to all potential antecedents simultaneously, evaluate which one fits semantically, and link the pronoun's representation to the correct noun's representation. An RNN would need to carry candidate antecedent information through the hidden state until the pronoun is encountered. Self-attention computes this comparison directly.

Notice that all-pairs interaction implies that self-attention is permutation equivariant without additional components. If you shuffled the order of tokens in the input, you would get the same attention weights between the same pairs of tokens, just in a different arrangement. This is why positional encodings are necessary: self-attention itself contains no positional information, and we must add it externally. We will return to this point in later sections and chapters, but the result follows directly from the all-pairs design.

The contrast is striking. In the RNN heatmap (left), path lengths grow with distance: connecting position 0 to position 9 requires 9 steps, shown by the dark red corners. The self-attention heatmap (right) is nearly uniform: every position connects to every other position in exactly 1 step (with 0 for self-connections on the diagonal). This constant path length helps capture long-range dependencies without information degradation.

The path length difference has a deeper implication for gradient flow during training. In an RNN trained with backpropagation through time, gradients must also flow backward through these same long paths. If a gradient signal needs to travel from position 100 back to position 1 to update early weights, it must pass through 99 matrix multiplications, each potentially shrinking it toward zero (vanishing gradient) or inflating it toward infinity (exploding gradient). LSTM and GRU cells were invented specifically to alleviate this problem, and they help substantially, but they do not eliminate it. Self-attention, because it computes direct connections, gives gradients equally short paths in both the forward and backward passes. The model can update its parameters based on distant dependencies just as easily as local ones.