Attention Mechanism in NLP

In the plain encoder-decoder model, an encoder (typically an RNN or LSTM) reads the source sequence $x_1, \dots, x_n$ and produces a final hidden state $h_n$, which serves as the sole summary — the context vector $c$ — passed to the decoder. Every output token $y_t$ is generated conditioned on this same fixed $c$, regardless of what part of the input is actually relevant to producing $y_t$. This is the bottleneck problem: information about all $n$ input tokens must be squeezed through one vector of fixed dimensionality, and the squeeze gets worse as $n$ grows.

Attention removes this bottleneck by keeping all encoder hidden states $h_1, \dots, h_n$ around, and computing, at each decoder timestep $t$, a fresh context vector $c_t$ that is a weighted combination of them:

The weights $\alpha_{t,i}$ (the attention weights) form a probability distribution over source positions ($\sum_i \alpha_{t,i} = 1$, $\alpha_{t,i} \ge 0$), computed from a learned alignment score $e_{t,i}$ between the decoder's current state and each encoder state, normalized by a softmax:

The terminology, later standardized by the Transformer paper, casts this as a query/key/value lookup: the decoder state is the query $q_t$, each encoder state serves as both a key $k_i$ (used to compute the score) and a value $v_i$ (used to build the weighted sum). In the vanilla recurrent-attention setting, keys and values are literally the same vectors $h_i$; in self-attention they are separately learned linear projections of the same input. Two scoring functions dominate the literature. Additive attention (Bahdanau et al., 2015) computes the score with a small feedforward network:

Dot-product attention (Luong et al., 2015) computes it more cheaply as an inner product, optionally scaled or bilinear:

Dot-product attention is computationally cheaper (a matrix multiply versus a feedforward pass per pair) and becomes, with a $1/\sqrt{d_k}$ scaling factor, the scaled dot-product attention at the heart of the Transformer. Additive attention can perform better with high-dimensional or dissimilar query/key spaces since it learns a full bilinear-like interaction rather than relying on raw dot products, but at higher parameter and compute cost per pair.

Attention is computed fresh at every decoder timestep. The core loop, for a recurrent encoder-decoder with attention (Bahdanau-style), proceeds as follows.

Step 1 — Encode. Run the encoder (often bidirectional) over the source sequence to obtain hidden states $h_1, \dots, h_n$, one per source token. These are stored and reused at every decoding step — this is the key departure from the bottleneck model.

Step 2 — For each decoder step $t$: 1. Form the query from the decoder's current state, e.g. $q_t = s_{t-1}$ (previous decoder hidden state). 2. Compute alignment scores $e_{t,i}$ between $q_t$ and every encoder state $h_i$, using additive or dot-product scoring. 3. Normalize with softmax to get attention weights $\alpha_{t,i}$. 4. Compute the context vector $c_t = \sum_i \alpha_{t,i} h_i$. 5. Feed $c_t$ (concatenated with the previous output embedding) into the decoder RNN cell to get the new hidden state $s_t$. 6. Use $s_t$ (and often $c_t$ again) to predict the output distribution over the vocabulary for $y_t$. Because $c_t$ is recomputed at every step from a fresh weighting over all encoder states, the decoder can "look at" different parts of the input as it generates different output words — exactly the soft alignment a human translator performs mentally. ``` function ATTENTION_DECODE(source_tokens, target_vocab, encoder, decoder, scorer):

# Step 1: Encode once H = encoder.forward(source_tokens) # H = [h_1, ..., h_n], each h_i in R^d n = length(H) s = decoder.init_state() # s_0 : initial decoder hidden state y_prev = START_TOKEN outputs = [] for t in 1 .. MAX_LEN:

# Step 2.1: form query from current decoder state q = s

# Step 2.2: compute alignment scores against every encoder state e = zeros(n) for i in 1 .. n: e[i] = scorer(q, H[i]) # additive or dot-product scoring

# Step 2.3: normalize to a probability distribution alpha = softmax(e) # alpha[i] >= 0, sum_i alpha[i] = 1

# Step 2.4: weighted sum -> context vector c = zeros(d) for i in 1 .. n: c = c + alpha[i] * H[i]

# Step 2.5: advance the decoder, conditioned on context + previous output s, logits = decoder.step(s, y_prev, c)

# Step 2.6: predict next token y_t = argmax_or_sample(softmax(logits)) outputs.append(y_t) if y_t == END_TOKEN: break y_prev = y_t return outputs

function ADDITIVE_SCORE(q, h; W_a, U_a, v_a): return dot(v_a, tanh(matvec(W_a, q) + matvec(U_a, h))) function DOTPRODUCT_SCORE(q, h): return dot(q, h) function SOFTMAX(e): m = max(e) # numerical stability exps = [exp(e_i - m) for e_i in e] Z = sum(exps) return [x / Z for x in exps] ``` The algorithm handles two important edge cases correctly. If $n = 1$ (a single-token source), softmax degenerates to $\alpha_{t,1} = 1$ and $c_t = h_1$ for all $t$ — attention correctly reduces to the no-attention case. If the encoder states are highly redundant (e.g., a repeated token), the softmax may legitimately spread weight across several equally relevant positions rather than being forced to pick one, which is the intended soft (not hard) alignment behavior.

Time complexity. For a source of length $n$ and target of length $m$, attention adds $O(m \cdot n \cdot d)$ time beyond the base encoder/decoder cost, where $d$ is the hidden dimension: at each of the $m$ decoding steps, scoring against all $n$ encoder states costs $O(n \cdot d)$ (dot-product) or $O(n \cdot d^2)$-ish (additive, due to the projection matrices $W_a, U_a$), and the weighted sum is another $O(n \cdot d)$. This is a genuine quadratic-in-sequence-length cost when $m \approx n$, compared to the $O(n \cdot d)$ or $O(m \cdot d)$ cost of the bottleneck model that discards all but the final encoder state. This is the fundamental compute-for-quality tradeoff attention introduces, one that later motivates approximate/sparse attention variants for very long sequences.

Space complexity. The model must retain all $n$ encoder hidden states throughout decoding, an $O(n \cdot d)$ memory cost (versus $O(d)$ for the bottleneck-only model), plus $O(m \cdot n)$ if attention weight matrices are stored for later inspection or visualization (as in alignment heatmaps).

Correctness — why the bottleneck is actually relieved. Consider the gradient of the loss at decoding step $t$ with respect to an early encoder state $h_i$. In the bottleneck model, this gradient must flow backward through the entire chain of encoder recurrences from $h_i$ to $h_n$ to $c$ to the decoder — a path of length $O(n)$, subject to vanishing-gradient decay at every step. With attention, $h_i$ contributes directly to $c_t$ via the term $\alpha_{t,i} h_i$, so

gives a direct, short path from any input position to any output position, with path length independent of $|t - i|$. This is precisely why attention alleviates the long-range dependency problem: the maximum gradient path length between any input and any output token drops from $O(n)$ (through recurrence) to $O(1)$ (through the attention weights), even though the recurrent encoder/decoder states themselves still exist and can still contribute vanishing gradients along their own path.

Why softmax normalization is the right choice. The weights $\alpha_{t,i}$ must (a) be non-negative, so the context vector is a genuine weighted average and not an extrapolation outside the convex hull of $\{h_i\}$, and (b) sum to 1, so the scale of $c_t$ doesn't depend on $n$ — without normalization, a longer sentence would trivially produce a larger-magnitude context vector for reasons unrelated to relevance. Softmax satisfies both properties while remaining differentiable everywhere, which is required for end-to-end training via backpropagation. Because there is no ground-truth "correct" alignment to supervise against, attention weights are learned purely from the downstream task loss (e.g., translation cross-entropy) — and empirically, the resulting $\alpha_{t,i}$ patterns closely mirror the word alignments produced by classical statistical alignment models (like IBM Model / GIZA++), which is strong empirical evidence that the mechanism is learning a semantically meaningful soft alignment, not an arbitrary weighting.

Tradeoffs, honestly stated. Attention is strictly more expressive than the bottleneck model (it can represent the bottleneck model as a degenerate case where $\alpha_{t,i}$ is always $1/n$ or concentrated on $h_n$), but this expressiveness costs quadratic time in sequence length and additional memory to retain all encoder states. For very long documents, this quadratic cost becomes the dominant bottleneck of Transformer-based systems, motivating sparse and linear-attention approximations — a tradeoff attention itself does not resolve, only shifts.

Consider translating the French sentence "le chat noir dort" ("the black cat sleeps") into English, at the decoding step where the model is about to produce the word "black". Assume the encoder has already produced hidden states $h_1, h_2, h_3, h_4$ for "le", "chat", "noir", "dort" respectively, and the decoder has already emitted "the" with hidden state $s_1$, which becomes the query $q_2 = s_1$. Suppose (illustrative, rounded) dot-product scores between $q_2$ and each $h_i$ come out as:

(Softmax is computed as $\alpha_{2,i} = \exp(e_{2,i}) / \sum_j \exp(e_{2,j})$; the table above illustrates the intended dominant-weight pattern rather than exact arithmetic to the last decimal.) The attention weights correctly concentrate on $h_3$ ("noir" = "black"), which is exactly the source word the decoder needs to correctly produce "black" next — even though "noir" appears after "chat" in French but the decoder needs it before "cat" in the English output. This crossing is precisely why attention outperforms a naive fixed alignment: French adjectives often follow the noun they modify, while English adjectives precede it, so the correct "alignment path" is non-monotonic. A model without attention has no mechanism to reach back selectively to "noir" out of word order; it must hope the single bottleneck vector preserved enough of that signal. The context vector is then:

This $c_2$, heavily weighted toward $h_3$, is fed into the decoder alongside the previous output "the" to produce the hidden state $s_2$, from which the softmax output layer assigns high probability to the word "black." At the next step, the query becomes $q_3 = s_2$, and the attention distribution shifts — now concentrating on $h_2$ ("chat") to correctly produce "cat." This step-by-step re-weighting, visualized as an alignment matrix (rows = output tokens, columns = input tokens), is the signature diagnostic of attention: the heatmap typically shows a roughly diagonal band for similar-word-order language pairs, with visible off-diagonal crossings exactly at points of syntactic reordering, like the noun-adjective swap above.

The idea that a network could learn to "look back" selectively at different parts of an input, rather than compressing everything into one vector, reframed how researchers thought about memory and alignment in neural sequence models — and it did so with a strikingly simple, fully differentiable mechanism trainable end-to-end via ordinary backpropagation, requiring no explicit alignment supervision.

Attention is the mechanism that made modern Neural Machine Translation systems (Google Translate and successors) practically usable on long, syntactically divergent sentence pairs, replacing earlier phrase-based statistical MT pipelines. Its generalization into self-attention, where queries, keys, and values all derive from the same sequence, underlies the Transformer architecture powering essentially every modern large language model — GPT, BERT, T5, and their descendants. The same query/key/value soft-lookup idea appears in image captioning (attending over image regions), speech recognition (attending over acoustic frames), retrieval-augmented generation (attending over retrieved documents), and multimodal models that align text with images or audio. Attention weight visualizations remain a standard interpretability tool, and the query/key/value abstraction is now the lingua franca for describing how Contextual Embeddings are built: each token's representation is recomputed as a weighted function of every other token's representation, layer after layer, rather than fixed once and reused everywhere as in earlier static word-embedding schemes.

Ask the tutor: How does scaled dot-product self-attention in the Transformer differ mechanically from the cross-attention described here, and why is the $1/\sqrt{d_k}$ scaling factor necessary?