Attention: The Mechanism That Changed Everything

Introduction

MLPs are powerful function approximators, but they have a fundamental limitation: they operate on fixed-size inputs. Feed an MLP a sentence of 10 words, it produces an output. Feed it 11 words, it breaks. Real-world sequences, text, audio, time series, vary in length. An architecture that handles sequences needs to process variable-length inputs and, crucially, understand the relationships between elements at different positions.

Recurrent Neural Networks (RNNs) solved the variable-length problem by processing sequences one element at a time, maintaining a hidden state that summarizes everything seen so far. But this sequential bottleneck introduced its own problems: vanishing gradients over long sequences, inability to parallelize, and a hidden state that had to compress an entire sequence into a single fixed-size vector.

The attention mechanism solved all of these problems. Instead of compressing the entire sequence into one vector, attention lets the model look back at every previous element and decide, dynamically, which elements are relevant for the current computation. This is the single most important architectural innovation in the history of deep learning.

The Sequence Problem

Consider translating a sentence from English to French. An MLP takes a fixed-size input, so you would need to pad or truncate every sentence to the same length. Worse, an MLP treats each input position independently, so it has no way to learn that "the" in position 1 relates to "cat" in position 3.

Sequences have structure that matters:

• Order matters: "dog bites man" is different from "man bites dog"
• Long-range dependencies: In "The cat that sat on the mat was orange," the verb "was" depends on "cat" across 6 intervening words
• Variable length: Sentences range from 1 word to hundreds

Recurrent Neural Networks (RNNs)

RNNs process sequences by maintaining a hidden state that gets updated at each time step:

h_t = activation(W_h . h_{t-1} + W_x . x_t + b)
y_t = W_y . h_t + b_y

At each step, the RNN takes the current input x_t and the previous hidden state h_{t-1}, combines them, and produces a new hidden state h_t. The hidden state is the network's memory of everything it has seen so far.

The Vanishing Gradient Problem in RNNs

Training an RNN means backpropagating through time (BPTT). The gradient at time step 1 requires multiplying gradients through every intermediate step. For a sequence of length T, the gradient is a product of T Jacobian matrices. If the largest eigenvalue of these matrices is less than 1, the product shrinks exponentially. If it is greater than 1, it explodes.

For long sequences (T > 20-50), the gradient signal from the end of the sequence to the beginning is effectively zero. The RNN cannot learn long-range dependencies. It forgets.

LSTMs (Long Short-Term Memory) and GRUs (Gated Recurrent Units) mitigate this with gating mechanisms that control information flow. But they do not eliminate the fundamental problem: processing is sequential. Each step depends on the previous step, so the computation cannot be parallelized. Training on long sequences is slow.

The Bottleneck Problem

In sequence-to-sequence tasks (like translation), the standard RNN approach was the encoder-decoder architecture:

1. An encoder RNN processes the input sequence, compressing it into a final hidden state (the "context vector")
2. A decoder RNN generates the output sequence from this context vector

The problem: the entire input sequence, regardless of length, must be compressed into a single fixed-size vector. For short sequences, this works. For long sequences, information is inevitably lost. The context vector becomes a bottleneck.

Bahdanau Attention (2014)

Dzmitry Bahdanau proposed a solution in 2014: instead of compressing the input into a single vector, let the decoder look at all encoder hidden states and learn which ones are relevant for each output step.

The idea: at each decoder step, compute a relevance score between the current decoder state and every encoder state. Use these scores as weights to create a weighted combination of encoder states. This weighted combination is the context for the current step.

score(s_t, h_i) = v^T . tanh(W_s . s_t + W_h . h_i)   # alignment score
alpha_i = softmax(score(s_t, h_i))                       # attention weights
context = sum(alpha_i * h_i)                              # weighted sum of encoder states

Where s_t is the decoder state at step t, h_i are the encoder states, and alpha_i are the attention weights.

The attention weights alpha_i form a probability distribution over the input sequence. They tell the decoder: "for this output word, focus mostly on these input words." The model learns these weights during training.

Self-Attention: Attending to Yourself

Bahdanau attention lets a decoder attend to an encoder. Self-attention generalizes this: every position in a sequence attends to every other position in the same sequence.

This is the key insight of the transformer. Instead of processing the sequence step by step (like an RNN), self-attention processes all positions simultaneously. Each position directly sees every other position. No information bottleneck. No vanishing gradients through time. Full parallelization.

The QKV Formulation

The transformer's attention mechanism uses three learned projections of each input: queries (Q), keys (K), and values (V).

The analogy: think of a database lookup. You have a query (what you are looking for), a set of keys (labels for the stored items), and values (the stored items themselves). The attention mechanism scores how well each key matches the query, then returns a weighted sum of the values.

Given an input matrix X (one row per position, one column per feature):

Q = X . W_Q    # queries: "what am I looking for?"
K = X . W_K    # keys: "what do I contain?"
V = X . W_V    # values: "what do I provide?"

The attention computation:

Attention(Q, K, V) = softmax(Q . K^T / sqrt(d_k)) . V

Step by step:

1. Compute scores: Q . K^T produces a matrix of dot products between every query and every key. Entry (i, j) measures how much position i should attend to position j.
2. Scale: Divide by sqrt(d_k) where d_k is the dimension of the keys. Without scaling, for large d_k the dot products become large, pushing softmax into regions with tiny gradients.
3. Normalize: Apply softmax row-wise, converting scores to probabilities. Each row sums to 1.
4. Aggregate: Multiply by V, producing a weighted sum of values for each position.

Why sqrt(d_k)?

Without the scaling factor, the dot products Q . K^T grow proportionally to d_k. When d_k = 64 (the per-head size in the base transformer), the scores already have a standard deviation around 8, and for larger d_k they can reach the hundreds. Softmax of large values produces near-one-hot distributions with near-zero gradients. Dividing by sqrt(d_k) keeps the variance of the scores around 1, maintaining healthy gradients.

Multi-Head Attention

A single attention head can only learn one type of relationship. "Multi-head attention" runs multiple attention heads in parallel, each with its own Q, K, V projections, then concatenates and projects the results:

head_i = Attention(X . W_Q_i, X . W_K_i, X . W_V_i)
MultiHead(X) = Concat(head_1, ..., head_h) . W_O

With 8 heads (typical for base models) and d_model = 512, each head works with d_k = 512/8 = 64 dimensions. Different heads learn different types of attention patterns:

• One head might attend to the previous word (syntactic adjacency)
• Another might attend to the subject of the sentence (semantic role)
• Another might attend to the verb (predicate structure)
• Another might learn positional patterns

The concatenation and output projection W_O combine these different views into a unified representation.

What Attention Actually Learns

Attention patterns in trained models reveal interpretable structure. In language models:

• Syntactic heads: Attend to the syntactic parent/child of each word. Verbs attend to their subjects.
• Positional heads: Attend to the previous or next position, implementing local context.
• Rare word heads: Attend backward to infrequent tokens that carry high information content.
• Separator heads: Attend to punctuation and sentence boundaries.
• Induction heads: Detect repeated patterns. If "A B ... A" appears, attend from the second A back to B to predict what comes next.

These patterns emerge from training, not from any explicit programming. The network discovers that these attention strategies are useful for predicting the next token.

Computational Complexity

Self-attention has a critical trade-off. Computing Q . K^T produces an n x n matrix where n is the sequence length. This means:

• Time complexity: O(n^2 * d) per layer
• Memory complexity: O(n^2) for storing the attention matrix

For a sequence of 1000 tokens, the attention matrix has 1,000,000 entries. For 10,000 tokens, 100,000,000 entries. This quadratic scaling is the primary bottleneck for processing long sequences.

Various approaches address this:

• Sparse attention: Only compute attention for a subset of position pairs
• Linear attention: Approximate the softmax with kernel functions to achieve O(n) complexity
• Flash Attention: Exact attention computed in a memory-efficient way using tiling and recomputation
• Sliding window attention: Only attend within a fixed-size window around each position

Key Takeaways

RNNs process sequences step by step and suffer from vanishing gradients over long sequences. The encoder-decoder bottleneck forces the entire input into a single vector. Attention eliminates both problems by letting every position directly access every other position. The QKV formulation provides a learnable, differentiable mechanism for dynamic information retrieval. Multi-head attention runs multiple attention patterns in parallel. The cost is O(n^2) computation, which is the defining constraint of transformer architectures.