Neural NLP: word vectors, attention, and the road to pretrained transformers

Why this subject matters now

It is tempting to treat everything before the transformer as archaeology. That is a mistake for three reasons. First, the concepts did not die, they moved. Every token embedding matrix in a modern language model is a word2vec-style lookup table trained end to end. The softmax-denominator problem that motivated negative sampling reappears in every large-vocabulary output layer. The encoder-decoder bottleneck that attention fixed is the cleanest motivation for why attention exists at all, and the evaluation pathologies documented for BLEU and for NLI datasets are the same pathologies now being rediscovered in LLM benchmark suites. Second, a good fraction of deployed NLP is still pre-transformer or small-transformer machinery. CRF taggers and biaffine parsers run inside production pipelines because they are fast, cheap, and auditable, and BERT-family encoders still serve enormous query volumes in search, ranking, and moderation. Third, the questions a strong practitioner gets asked, why negative sampling works, what an LSTM gate is for, why BERT masks 15% of tokens and then only replaces 80% of those with [MASK], what "attention is not explanation" actually showed, are questions about this material. The end-to-end engineering of a modern LLM (tokenizer training, distributed pretraining, scaling laws, inference) lives on a separate page. Here the subject is representation learning for language and the linguistic ideas that shaped it.

1990s-2012        2013-2014        2014-2017            2017-2018          2018-now
counting          learning         sequence models      one architecture   pretraining
↓                 ↓                ↓                    ↓                  ↓
tf-idf, LSA,      word2vec,        RNN/LSTM LMs,        transformer:       ELMo, GPT, BERT:
PPMI + SVD        GloVe: static    seq2seq + attention  attention only,    pretrain on raw
co-occurrence     word vectors     for translation      parallel training  text, adapt to
matrices                                                                   every task

The representation problem

One-hot vectors and why they fail

A vocabulary of \(V\) word types has an obvious encoding, in which word \(i\) becomes the standard basis vector \(e_i \in \R^V\). Every classical pipeline implicitly used it, because a count of word \(i\) is a dot product with \(e_i\). The encoding has two fatal properties. It is enormous, \(V\) is \(10^5\) to \(10^6\) for real corpora, and it is orthogonal by construction, with \( e_{\text{hotel}}\T e_{\text{motel}} = 0 \), exactly as similar as \(e_{\text{hotel}}\T e_{\text{the}}\). No notion of similarity means no generalization. A model that has seen "the hotel was clean" learns nothing about "the motel was clean".

The way out is a hypothesis older than neural networks, usually credited to Harris (1954) and compressed by Firth (1957) into "you shall know a word by the company it keeps". This is the distributional hypothesis, that words occurring in similar contexts have similar meanings. It converts an unobservable (meaning) into an estimable statistic (context distributions), and everything on this page, from PPMI matrices to masked language models, is a machine for exploiting it. The hypothesis has limits worth remembering. It conflates synonymy with relatedness (good and bad share contexts), it says nothing about grounding words in the world, and it inherits every statistical bias of the corpus. Those limits will resurface in the evaluation and bias sections.

Count-based vectors: PPMI and its SVD

The direct implementation of the hypothesis is a co-occurrence matrix \(X \in \R^{V \times V}\), where \(X_{ij}\) counts how often context word \(j\) appears within a window of \(w\) tokens around center word \(i\). Raw counts are dominated by frequent function words, "the" co-occurs with everything, so the standard reweighting is pointwise mutual information,

which measures how much more often \(i\) and \(j\) co-occur than independence predicts. PMI of an unseen pair is \(\log 0 = -\infty\), and large negative PMI values are mostly noise (they claim confident knowledge of what does not co-occur from finite data), so practice clips at zero, taking \( \mathrm{PPMI}(i,j) = \max(0, \mathrm{PMI}(i,j)) \). The PPMI matrix is sparse and high dimensional. Truncated SVD, \( M_{\mathrm{PPMI}} \approx U_d \Sigma_d V_d\T \), gives the best rank-\(d\) approximation in Frobenius norm, and the rows of \(U_d \Sigma_d^{p}\) (with \(p \in [0,1]\), often \(p{=}0.5\), a tuning choice Levy, Goldberg and Dagan (2015) showed matters) are dense \(d\)-dimensional word vectors. This is latent semantic analysis modernized, and it is not a strawman. With the right hyperparameters, count-based SVD vectors are competitive with word2vec on similarity benchmarks. The vector space model and tf-idf weighting that precede all of this are laid out in Manning, Raghavan and Schütze's information retrieval textbook.

Word2vec

The skip-gram objective

Word2vec (Mikolov et al., 2013) replaces counting with prediction, learning vectors such that a word predicts its neighbors. Each word type gets two vectors, a center vector \(v_w \in \R^d\) and a context vector \(u_w \in \R^d\). The skip-gram model slides over a corpus of \(T\) tokens and, at each position \(t\), tries to predict every context word within a window of size \(m\),

(The companion CBOW model predicts the center from the averaged context. Skip-gram works better for rare words and is the variant everyone analyzes.) The gradient of the log-probability with respect to the center vector has the classic observed-minus-expected form. Writing \(s_w = u_w\T v_c\) and \(p_w = \P(w \mid c)\),

The problem is the denominator. Both the loss and this gradient touch all \(V\) context vectors for every single training pair, which is \(O(Vd)\) work per token, with \(V\) in the hundreds of thousands. At word2vec's intended scale (billions of tokens) the exact softmax is not an option. Word2vec shipped two escapes, and the field learned something from each.

Negative sampling, derived

Negative sampling changes the problem rather than approximating it. Instead of "which of \(V\) words is the context?", train a binary classifier that asks "is this (center, context) pair real, or was the context drawn from a noise distribution?" For a true pair \((c, o)\) and \(k\) noise words \(w_1, \dots, w_k\) drawn i.i.d. from a noise distribution \(P_n\), the per-pair objective (to be maximized) is

The noise distribution is the unigram distribution raised to the 3/4 power, \(P_n(w) \propto \mathrm{count}(w)^{3/4}\), an empirical choice that samples rare words more often than their frequency and frequent words less. The count \(k\) is 5-20 for small corpora and 2-5 for large ones. Each pair now touches \(k{+}1\) context vectors instead of \(V\), so the per-token cost drops from \(O(Vd)\) to \(O(kd)\), a factor of tens of thousands. Negative sampling is a simplification of noise-contrastive estimation (Gutmann and Hyvärinen, 2012, applied to LMs by Mnih and Teh, 2012). NCE's classifier includes the noise probabilities in its posterior and is asymptotically consistent for the softmax LM, while negative sampling drops those terms, so it does not estimate the LM probabilities, but it does not need to. The goal is good vectors, not calibrated probabilities, and the Levy-Goldberg result below says exactly what it estimates instead. Problem 2 derives every gradient.

Hierarchical softmax

The second escape keeps a normalized distribution but changes its factorization. Arrange the vocabulary as leaves of a binary tree. Each internal node \(n\) gets a vector \(u_n\), and a word's probability is the product of binary decisions along its root-to-leaf path, \( \P(w \mid c) = \prod_{j=1}^{L(w)-1} \sigma\!\big( [\![ n_{j+1} = \mathrm{left}(n_j) ]\!] \cdot u_{n_j}\T v_c \big) \), where \([\![\cdot]\!]\) is \(+1\) for a left child and \(-1\) for a right child. Because \(\sigma(x) + \sigma(-x) = 1\), the probabilities of the two children of every node sum to 1, so the leaves sum to 1 by induction. It is a proper softmax computed in \(O(\log V)\) instead of \(O(V)\). Word2vec uses a Huffman tree, which gives frequent words short paths, cutting the average cost further. Hierarchical softmax preserves normalized probabilities (useful when the model must be a real LM), while negative sampling is faster and gives slightly better vectors on most benchmarks. That trade is why negative sampling won for embeddings while tree and sampled softmaxes lived on in early neural LMs.

Subsampling frequent words

Frequent words are a double problem. "The" appears in everyone's window, providing almost no signal about its neighbors while consuming a large fraction of all training pairs. Word2vec discards token occurrences of word \(w\) with probability

where \(f(w)\) is the word's corpus frequency and \(t \approx 10^{-5}\)-\(10^{-4}\) is a threshold. Words rarer than \(t\) are always kept. The square root makes the cut aggressive but not total. At \(t = 10^{-4}\), a word with frequency \(10^{-2}\) keeps \(\sqrt{10^{-4}/10^{-2}} = 10\%\) of its occurrences. Subsampling has a second, subtler effect. Deleting tokens before windows are extracted brings distant content words into each other's windows, effectively widening the context. In the training run reported below, subsampling at \(t = 10^{-4}\) cut text8 from 16.72M to 8.43M tokens, roughly halving training time while improving the learned neighbors.

Window size and dimensionality

Two hyperparameters change what "similarity" the vectors encode. Small windows (2-3) make the model care about immediate syntactic environment, so nearest neighbors are functionally interchangeable words (Hogwarts → Sunnydale, other fictional schools), while large windows (10+) capture topical association (Hogwarts → Dumbledore, Half-Blood). Levy and Goldberg's dependency-based embeddings (2014) push the syntactic extreme by using parse relations as contexts. Word2vec also weights context positions by sampling the effective window uniformly from \(\{1, \dots, m\}\), so nearer words count more. Dimension behaves with diminishing returns. 50 is visibly cramped, 300 was the standard for public releases, and past a few hundred the similarity benchmarks flatten while memory and downstream cost keep growing. The run below uses \(d = 128\), window 5, which is enough for clean structure on a 17M-token corpus.

GloVe and the matrix-factorization view

Deriving the GloVe objective from co-occurrence ratios

GloVe (Pennington, Socher and Manning, 2014) starts from the observation quantified in Problem 1, that meaning lives in ratios of co-occurrence probabilities. With \(P_{ik} = \P(k \mid i) = X_{ik}/X_i\), the ratio \(P_{ik}/P_{jk}\) is large when context \(k\) is diagnostic for \(i\), small when diagnostic for \(j\), and near 1 when \(k\) is irrelevant to the contrast (water, in the example). So ask for a function of word vectors that reproduces ratios,

Three modeling steps pin \(F\) down. First, ratios of scalars should depend on the difference of the word vectors (vector spaces encode contrasts as differences), so \(F(w_i - w_j, \tilde{w}_k)\). Second, the arguments should interact through a dot product, keeping the model bilinear, \(F\big((w_i - w_j)\T \tilde{w}_k\big)\). Third, words and contexts are symmetric roles, and swapping them inverts the ratio. \(F\) must therefore convert subtraction in its argument into division of its values, \( F(a - b) = F(a)/F(b) \), i.e. \(F\) is a homomorphism from \((\R, +)\) to \((\R_{>0}, \times)\). The continuous solutions are exactly \(F = \exp\). Then \( \exp(w_i\T \tilde{w}_k - w_j\T \tilde{w}_k) = P_{ik}/P_{jk} \) is satisfied by matching numerator and denominator separately, \( w_i\T \tilde{w}_k = \log P_{ik} = \log X_{ik} - \log X_i \). The \(\log X_i\) term does not depend on \(k\), so absorb it into a bias \(b_i\), and add \(\tilde{b}_k\) to restore symmetry,

This cannot hold exactly (and \(\log 0\) is undefined for the 98%+ of pairs never seen), so GloVe minimizes a weighted least squares over observed pairs only,

with \(x_{\max} = 100\), \(\alpha = 3/4\). The weighting does three jobs. Unseen pairs get weight \(f(0)=0\) and drop out, rare co-occurrences (noisy log-counts) are down-weighted by the power law, and the cap at \(x_{\max}\) stops "the of" pairs from dominating. Training cost scales with the number of nonzero entries of \(X\) rather than corpus length, which is GloVe's practical selling point, one pass to count, then cheap epochs over the sparse matrix. On benchmarks GloVe and skip-gram are near-equivalent when hyperparameters are matched, which the next result explains. They are secretly factorizing nearly the same matrix.

What negative sampling really factorizes (Levy & Goldberg)

Levy and Goldberg (2014) asked what skip-gram with negative sampling converges to when the dimension is unconstrained. Sum the SGNS objective over the corpus, grouping by word-context type. With \(\#(w,c)\) the number of times the pair occurs, \(\#(w), \#(c)\) the marginal counts, \(|D|\) the number of pairs, and noise drawn from the empirical unigram distribution \(\#(c)/|D|\), the total objective is

For a single pair, write \(x = u_c\T v_w\) and collect its coefficient in both sums, \( \ell(x) = \#(w,c) \log \sigma(x) + k\, \#(w) \frac{\#(c)}{|D|} \log \sigma(-x) \). Setting \(d\ell/dx = 0\) with the derivatives from Problem 2 gives

using \(\sigma(x)/\sigma(-x) = e^x\). Taking logs,

At its optimum, SGNS factorizes the PMI matrix shifted down by \(\log k\). The product of the two embedding matrices, \(W \tilde{W}\T\), approximates \(M^{\mathrm{PMI}} - \log k\) under an implicit weighting that emphasizes frequent pairs. The prediction-versus-counting divide of 2013-2014 largely dissolves. Skip-gram is a scalable, implicitly-weighted, online matrix factorization of the same statistic the count methods used explicitly, and Levy, Goldberg and Dagan (2015) showed that transferring word2vec's design tricks (shifted PMI, context distribution smoothing with the 3/4 power, subsampling) to SVD-based methods closes most of the gap between the families. What actually mattered was the statistic and the hyperparameters, not the neural framing.

Evaluating embeddings, and what that taught the field

Similarity and analogy benchmarks

Intrinsic evaluation came in two flavors. Similarity benchmarks (WordSim-353, MEN, SimLex-999) correlate cosine similarity with human ratings. SimLex-999 was built specifically to separate similarity from relatedness ("coffee" and "cup" are related, not similar), and embeddings score notably worse on it, exposing how much of their signal is topical association. Analogy tasks ask for \(b^* \) such that \(a : b :: a^* : b^*\), answered by the parallelogram rule \( b^* = \argmax_{w \notin \{a, b, a^*\}} \cos(w, v_b - v_a + v_{a^*}) \) (3CosAdd). The Google analogy set made "king − man + woman ≈ queen" the most famous result in NLP, and it deserves its asterisks. Excluding the input words is load-bearing. Linzen (2016) and Nissim et al. (2020) showed that without the exclusion the nearest neighbor of \(v_b - v_a + v_{a^*}\) is usually \(b\) or \(a^*\) itself, so part of the reported accuracy comes from the constraint, not the geometry. Accuracy is also wildly uneven across relation types (capital-country works, derivational morphology largely does not), and the training run below reproduces the honest version, in which "queen" ranks second, not first, for the king analogy on a 17M-token corpus. Extrinsic evaluation, plugging embeddings into a downstream tagger or classifier, is the measure that actually predicted practical value, and its verdict was consistent. Pretrained vectors helped everything in the pre-BERT era, typically by 1-3 points.

Bias in embeddings, and the debiasing debate

The distributional hypothesis has no notion of "should". Bolukbasi et al. (2016) found that the analogy machinery completes "man is to computer programmer as woman is to ?" with "homemaker", and proposed hard debiasing, which identifies a gender direction from definitional pairs (he-she, man-woman), then zeroes out the projection of gender-neutral words onto it. Caliskan, Bryson and Narayanan (2017) made the measurement systematic with WEAT, importing the design of implicit association tests. Word2vec and GloVe embeddings reproduce essentially every documented human association bias, including race and age effects, with large effect sizes. The follow-up work matters as much as the original. Gonen and Goldberg ("Lipstick on a Pig", 2019) showed that after hard debiasing, the removed information is still recoverable, biased words still cluster together, and a classifier can still predict the original gender association from the "debiased" vectors, because bias is distributed across many directions rather than living in one. The honest summary is that projection-based debiasing changes what one probe measures without removing the underlying structure, and any claim that a representation "has been debiased" needs to specify the measurement it is debiased against. The same critique now applies, with the same force, to bias mitigation in contextual models.

Subword models: dissolving the vocabulary problem

The OOV problem

A fixed word vocabulary fails on contact with real text. Novel words, inflected forms, typos, names, code, and any morphologically rich language (a Finnish or Turkish verb has thousands of surface forms) all map to a single UNK token that carries no information. The structural fix is to stop pretending words are atoms. Three families emerged, character-level models, character-augmented word vectors, and learned subword vocabularies. The third won, and the modern tokenizer, with all its own pathologies, is its direct descendant.

Character-level models and FastText

Pure character models (Sutskever et al.'s character RNNs, 2011, and Kim et al.'s character-CNN language model, 2016) give up the vocabulary entirely. No OOV is possible and morphology is learnable, but sequences get 4-5× longer, which for an RNN means 4-5× more sequential steps and much longer-range dependencies to carry. Kim's compromise, characters in, words out, used a CNN over characters plus a highway network to build word representations for a word-level LSTM LM, matching word-level perplexity with far fewer parameters. ELMo later adopted exactly this input encoder. FastText (Bojanowski et al., 2017) is the minimal change to word2vec. It represents a word as the sum of vectors of its character n-grams (n = 3-6) plus the word itself, \( v_w = \sum_{g \in G(w)} z_g \), with n-grams hashed into a fixed table. Skip-gram training is unchanged. "Where" shares the n-grams ‹wh, whe, her, ere, re› with related forms, so rare and unseen words get sensible vectors composed from their pieces. For morphologically rich languages the gains are large, and FastText's released 157-language vectors made it the default static embedding for a decade.

BPE, WordPiece, unigram LM

Byte-pair encoding (Sennrich, Haddow and Birch, 2016, adapting a 1994 compression algorithm) learns a vocabulary from data. Start with characters, repeatedly merge the most frequent adjacent symbol pair, and stop after a budget of merges. On the classic toy corpus {low×5, lower×2, newest×6, widest×3} with an end-of-word marker, the first pair counts are (e,s) with frequency 9 (from newest and widest), (s,t) 9, (l,o) 7, (o,w) 7. Merging (e,s) creates the symbol "es", the next count finds (es,t) at 9 and merges to "est", and then "est•" merges with the boundary marker. Three merges in, the corpus already tokenizes "lowest", a word it never saw, as low + est. Frequent words become single tokens, rare words decompose, and nothing is ever OOV as long as the base alphabet is covered (GPT-2 pushed the base to bytes so that literally any input tokenizes).

WordPiece (used by BERT) differs only in the merge criterion. Instead of the most frequent pair, it merges the pair that most increases the likelihood of the corpus under a unigram LM over the current vocabulary, i.e. it maximizes \( \mathrm{count}(ab) / (\mathrm{count}(a)\,\mathrm{count}(b)) \)-style gain rather than raw \(\mathrm{count}(ab)\), a PMI-flavored choice. The unigram LM method (Kudo, 2018) inverts the direction entirely. Start with a large candidate vocabulary, model a word's probability as the sum over segmentations of products of piece probabilities, run EM to fit piece probabilities, and iteratively prune the pieces whose removal least hurts corpus likelihood. Because it is probabilistic it supports sampling segmentations, which gives subword regularization, a data augmentation that samples different tokenizations of the same text during training. SentencePiece packages both BPE and unigram with whitespace treated as an ordinary symbol, removing the need for language-specific pre-tokenization.

The comparison worth internalizing is that all three optimize compression of the training corpus, so all three inherit its distribution. Text unlike the corpus, other languages, other scripts, code, fragments into many short tokens. That observation returns with measurements in the multilinguality section.

Language models before neural networks, and the first neural one

n-grams and smoothing

A language model assigns probability to a sequence via the chain rule, \( \P(w_1, \dots, w_N) = \prod_t \P(w_t \mid w_{<t}) \), and an n-gram model truncates the history to \(n{-}1\) words. Maximum likelihood estimates are ratios of counts, and the entire engineering of the field circa 1980-2010 was fighting zeros. A trigram never seen in training gets probability 0, which makes the whole sequence probability 0 and perplexity infinite. Add-one (Laplace) smoothing is catastrophically blunt at vocabulary scale, it moves most of the probability mass to unseen events. The workable ideas were discounting (subtract a little from seen counts, redistribute to unseen), interpolation (mix trigram, bigram, unigram estimates), and backoff (use the longest history with support). Chen and Goodman's 1999 empirical study crowned the combination still worth knowing, interpolated Kneser-Ney.

Kneser-Ney, explained properly

Kneser-Ney (1995) has two components. The first is absolute discounting, subtracting a fixed \(D \approx 0.75\) from every nonzero count, which empirically matches how held-out counts shrink relative to training counts. The second is the clever part, that the lower-order distribution should not be the unigram frequency. The standard example is "Francisco", a frequent word that occurs almost exclusively after "San". If a bigram model backs off from an unseen context, say "reading ___", plain unigram frequency would propose "Francisco", which is absurd, "Francisco" never starts fresh contexts. What the backoff distribution should measure is how likely a word is to appear in a new context, its continuation probability, proportional to the number of distinct contexts it follows,

the count of distinct bigram types ending in \(w\) over the count of all bigram types. "Francisco" follows one word type, so its continuation probability is tiny regardless of its token frequency, while "glasses" follows many ("reading glasses", "wine glasses", "his glasses") and scores high. The interpolated bigram model is then

where \(\lambda\) is exactly the mass freed by discounting, so the distribution normalizes. Modified Kneser-Ney (Chen and Goodman) uses three discounts depending on the count being 1, 2, or more. This was the state of the art that neural LMs had to beat, and for years, with orders of magnitude less compute, it did not lose by much.

Perplexity, derived from cross-entropy

The evaluation metric needs its derivation because it is routinely misread. The cross-entropy of a model \(q\) on a held-out sequence \(w_1 \dots w_N\), in bits per word, is the average negative log-likelihood \( H = -\frac{1}{N} \sum_{t=1}^{N} \log_2 q(w_t \mid w_{<t}) \), which by the Shannon-McMillan-Breiman theorem converges (for stationary ergodic sources, as \(N \to \infty\)) to the cross-entropy rate between the true source and the model, an upper bound on the source's entropy rate that is tight exactly when the model is correct. Perplexity exponentiates it,

the inverse geometric mean of the per-token probabilities. The interpretation that makes it concrete is that a perplexity of \(K\) means the model is, on average, as uncertain as if it were choosing uniformly among \(K\) options at each step, an effective branching factor. Three cautions. Perplexity is only comparable over the same tokenization and the same test set (per-subword and per-word perplexities differ mechanically, which is why fair comparisons renormalize to bits per character or bits per byte). It is a teacher-forced quantity, computed with the true prefix, so it measures next-token prediction, not generation quality. And a uniform model over vocabulary \(V\) has perplexity exactly \(V\), which sets the scale. Text8-style English with a 70k vocabulary is around 100-250 for good n-gram models and far lower for modern transformers.

The first neural language model

Bengio, Ducharme, Vincent and Jauvin (2003) built the model that connects the two halves of this page. Concatenate learned embeddings of the previous \(n{-}1\) words, pass them through a tanh hidden layer, and softmax over the vocabulary. The architectural details aged, the argument did not. An n-gram model cannot generalize from "the cat is walking in the bedroom" to "a dog was running in a room" because it has no notion that cat and dog are similar. A model with shared continuous word representations gets that generalization automatically, because probability is a smooth function of the embeddings, and moving one word's vector moves the probability of exponentially many related sentences. The paper named the fight ("fighting the curse of dimensionality with distributed representations"), identified the softmax over \(V\) as the bottleneck, and anticipated both the embedding layers of everything since and the sampled/hierarchical softmax literature. What it lacked was a way to consume unbounded context, which is what recurrence is for.

Recurrent networks, derived

Forward pass and backpropagation through time

A simple (Elman) RNN consumes a sequence \(x_1, \dots, x_T\) and maintains a hidden state

with the same weights at every step, a deep network in time whose depth is the sequence length, with tied layers. Training unrolls it and backpropagates through the unrolled graph (backpropagation through time). Let \(\L = \sum_t \L_t\) with per-step losses. The subtlety is that \(W_{hh}\) affects \(\L_t\) through every earlier state, so the total derivative sums over the step \(k\) at which the weight is "used",

where \(\partial^{+}\) denotes the immediate (single-step) partial with \(h_{k-1}\) treated as constant. The inner factor is a product of step Jacobians. Writing \(z_j = W_{hh} h_{j-1} + W_{xh} x_j + b\), one step gives \( \frac{\partial h_j}{\partial h_{j-1}} = \diag\!\big(1 - h_j^{\odot 2}\big)\, W_{hh} \) (the elementwise \(\tanh'\) times the recurrent matrix), so

In practice the sums are computed by one reverse pass that carries \(\delta_t = \partial \L / \partial h_t\) backward via \( \delta_{t-1} \mathrel{+}= W_{hh}\T \diag(1 - h_t^{\odot 2})\, \delta_t \), accumulating weight gradients as it goes, which is \(O(T)\) like the forward pass. Truncated BPTT stops the backward recursion after \(\tau\) steps to bound memory and compute, at the cost of never learning dependencies longer than \(\tau\).

The vanishing/exploding gradient analysis

Everything about RNN training difficulty is in that product of Jacobians. Bound its norm using submultiplicativity, with \(\gamma = \max_j \|\diag(1 - h_j^{\odot 2})\|_2 \le 1\) for tanh (and \(\le 1/4\) for sigmoid) and \(\sigma_{\max}\) the largest singular value of \(W_{hh}\),

If \(\gamma\, \sigma_{\max} < 1\) the gradient contribution from step \(k\) to loss at step \(t\) shrinks exponentially in the gap \(t - k\), a sufficient condition for vanishing (Pascanu, Mikolov and Bengio, 2013). Conversely, \(\sigma_{\max} > 1/\gamma\) is a necessary condition for exploding gradients. Growth requires the linear map to expand faster than the nonlinearity contracts, and it happens along the expanding singular directions when the states stay in the unsaturated region. The eigenvalue picture makes it geometric. Iterating a fixed matrix \(W\) drives any vector toward the dominant eigenspace, scaling by \(|\lambda_1|^{t-k}\), and with \(|\lambda_1| \ne 1\) the only long-horizon options are decay to zero or blow-up, while the saturating nonlinearity only makes decay more likely. The two failure modes are asymmetric in practice. Explosion is visible (loss spikes, NaNs) and has a cheap fix, gradient norm clipping, \( g \leftarrow g \cdot \min(1, \tau / \|g\|) \), which preserves direction while capping magnitude, rescuing SGD from the cliffs in the loss surface that Pascanu et al. visualized. Vanishing is silent. Training proceeds, loss falls, and the model simply never learns dependencies longer than a few dozen steps. That failure needed an architectural fix.

The LSTM, gate by gate

The long short-term memory cell (Hochreiter and Schmidhuber, 1997, with the forget gate added by Gers, Schmidhuber and Cummins, 2000) splits state in two, a cell state \(c_t\) that acts as protected memory, and a hidden state \(h_t\) that is the cell's exposed, squashed view. Four learned functions of \((x_t, h_{t-1})\) control it.

        c_{t-1} ───────×──────────(+)──────────────→ c_t
                        ↑           ↑                 │
                       f_t       i_t × g_t           ↓ tanh
                        ↑           ↑                 ×──→ h_t
                 ┌──────┴───────────┴──────┐         ↑
    x_t, h_{t-1} ┤  four learned gates      ├──── o_t
                 └─────────────────────────┘
    the c-path has no weight matrix and no squashing between steps

Each gate answers a failure of the simple RNN. The simple RNN is forced to overwrite its entire state through \(W_{hh}\) at every step, so keeping information means learning a transformation that happens to preserve it while everything else changes, exactly the fragile eigenvalue balancing act of the analysis above. The input gate makes writing optional, so irrelevant steps can leave memory untouched instead of diluting it. The forget gate makes erasure explicit and learnable. A close-bracket token can clear the "inside brackets" feature, and the original 1997 cell, which lacked this gate, had cell states that could only grow, which breaks on continual input. The candidate is tanh-bounded so a single write cannot blow the state up. The output gate decouples what is stored from what is broadcast, so a fact can be carried silently for a hundred steps without contaminating every intermediate prediction. And the update being additive, \(c_t = f_t \odot c_{t-1} + i_t \odot g_t\), is the fix for vanishing gradients. Differentiating along the cell path,

whose leading term is a diagonal of gate activations, not a product with \(W_{hh}\) followed by \(\tanh'\). Where the simple RNN multiplies the error by \(\diag(\tanh')\,W\) every step, the LSTM multiplies by \(f_t\), a quantity the network itself sets, and can hold near 1 (the "constant error carousel" of the original paper). This is the same trick residual networks later applied in depth, make identity the default and learn the deviations. It mitigates rather than abolishes the problem, the gate pathways still leak, and exploding gradients still require clipping, but in practice LSTMs learn dependencies of hundreds of steps where simple RNNs manage tens.

GRU, bidirectionality, depth

The gated recurrent unit (Cho et al., 2014) is the LSTM simplified to two gates and a single state,

The update gate \(z_t\) plays forget-and-input in one (interpolation makes the two complementary), the reset gate \(r_t\) controls how much history the candidate sees, and there is no output gate and no separate cell, so a GRU has 3 weight blocks to the LSTM's 4, about 25% fewer parameters at equal width. A decade of head-to-head comparisons (including Jozefowicz, Zaremba and Sutskever's 2015 search over thousands of gate variants) delivered the anticlimax that neither dominates. The search's most robust finding was that initializing the LSTM forget bias to 1 matters more than the choice of cell. Two structural extensions matter for what came later. Bidirectional RNNs run a second recurrence right-to-left and concatenate states, giving every position a view of the full sequence, essential for tagging and encoding, impossible for autoregressive generation, and the direct ancestor of the "bidirectional encoder" framing that BERT made central. Stacked RNNs feed each layer's state sequence to the next layer. 2-4 layers was the practical ceiling before optimization pain, and ELMo's finding that layers specialize (syntax lower, semantics higher) previewed the layerwise analyses of BERT.

Sequence to sequence and attention

The encoder-decoder bottleneck

Sequence-to-sequence learning (Sutskever, Vinyals and Le, 2014, and Cho et al., 2014) maps input to output through a fixed-size vector. An encoder LSTM reads the source and its final state becomes the initial state of a decoder LSTM that emits the target token by token, trained by teacher forcing (condition on the gold prefix, maximize the log-likelihood of each next token). The design is clean and it translated. It also has an information bottleneck a sentence wide. A 50-word sentence and a 5-word sentence both compress into the same few-thousand-float vector, and the encoder must decide what to keep before knowing what the decoder will need. The measurable symptom is that translation quality degraded sharply with sentence length (Bahdanau et al.'s figures show the fixed-vector model's BLEU collapsing beyond roughly 20-30 words while the attention model stays flat). Sutskever et al.'s own best trick, reversing the source sentence, is a confession of the problem. It shortens the distance between the start of the source and the start of the target, easing the credit assignment the bottleneck makes hard.

Attention: Bahdanau and Luong

Attention removes the bottleneck by letting the decoder consult all encoder states \(h_1, \dots, h_{T_x}\) at every output step, through a learned, content-based weighting. At decoder step \(i\), score each source position, normalize, and take the expectation,

with the context \(c_i\) fed into the decoder's state update and output layer. The scoring function \(a\) is where the two classic designs differ. Bahdanau, Cho and Bengio (2015) use an additive (concat) scorer, a one-hidden-layer MLP,

computed from the previous decoder state \(s_{i-1}\) before the state update, with a bidirectional GRU encoder so each \(h_j\) summarizes both directions around word \(j\). Luong, Pham and Manning (2015) simplified this. They score with the current state \(s_i\) after the update, then combine \([c_i; s_i]\) through a tanh layer before the softmax, and use multiplicative scorers,

Empirically the two score families are close, with additive slightly better at large dimensions unless dot products are scaled, exactly the \(\sqrt{d}\) analysis on the attention page. The multiplicative form won history because it is one matmul, the operation hardware is best at. The conceptual reading matters more than the scores. Attention computes a soft, differentiable alignment between target and source, learned end to end from the translation objective alone, replacing the explicit alignment models of statistical MT. And the attention maps it produced, diagonal-ish for French-English with clean crossings for adjective-noun reordering, were the first widely-circulated "look what it learned" visualizations, a genre the interpretability section treats with suspicion.

encoder (bi-RNN)        h_1   h_2   h_3   h_4     source states
                          ↓     ↓     ↓     ↓
                        scores e_ij = a(s_{i-1}, h_j)
                          ↓ softmax over j
                        α_i1  α_i2  α_i3  α_i4     alignment weights
                          ↓ weighted sum
                              c_i                  context vector
                               ↓
decoder:  s_{i-1} ──────→ s_i ──→ y_i             one target token
          (the bottleneck is gone: every step re-reads the source)

Coverage and copying

Two systematic decoder failures got mechanism-level fixes that survive in modern systems' vocabularies. The first is repetition and omission. Nothing in the attention equations remembers what has already been attended, so decoders re-translate some source words and skip others. Coverage (Tu et al., 2016) accumulates \( \mathrm{cov}_i = \sum_{i' < i} \alpha_{i'} \), feeds it to the scorer so past attention suppresses future attention, and See, Liu and Manning (2017) added a coverage penalty \( \sum_j \min(\alpha_{ij}, \mathrm{cov}_{ij}) \) that directly punishes re-attending. The second is rare and out-of-vocabulary content. Names and numbers should often be copied verbatim, which a closed-vocabulary softmax cannot do. The pointer-generator (See et al., building on Vinyals et al.'s pointer networks, 2015) computes a soft switch \(p_{\text{gen}} \in (0,1)\) and mixes generating from the vocabulary with copying from the source via the attention distribution itself,

Subword vocabularies later dissolved most of the OOV motivation, but the failure modes themselves, repetition, omission, hallucinated entities, did not disappear with transformers. They are the same behaviors now discussed under "faithfulness" in summarization and RAG systems.

Beam search and length normalization

Decoding wants \( \argmax_y \log \P(y \mid x) \) over all sequences, which is intractable. Greedy decoding (take the best token each step) is cheap but cannot recover from a locally attractive token that leads to a bad continuation. Beam search keeps the \(B\) best partial hypotheses at each step. Expand each by all tokens, score by summed log-probability, keep the top \(B\), and move completed hypotheses (those emitting end-of-sequence) to a done list. Cost is \(O(B \cdot V)\) scoring per step. Beams of 4-10 capture most of the gain, and very large beams famously make neural MT worse, exposing the model's length bias. That bias is structural. Every added token multiplies in another probability \(< 1\), so summed log-probability always prefers shorter hypotheses, and an unnormalized beam search systematically truncates. The standard fix divides by a length penalty, either plain \( \mathrm{score}(y) = \log \P(y \mid x) / |y|^{\alpha} \) or the GNMT variant \( \big( (5 + |y|) / 6 \big)^{\alpha} \) with \(\alpha \approx 0.6\)-\(0.7\) tuned on dev data. Problem 5 runs the full algorithm by hand and shows the ranking flip.

Machine translation evaluation

BLEU, defined and computed

BLEU (Papineni et al., 2002) scores a candidate translation by modified n-gram precision against one or more references. For each order \(n \in \{1,\dots,4\}\), count candidate n-grams that appear in a reference, clipping each n-gram's credit at its maximum reference count (so "the the the the" cannot farm precision), and divide by the number of candidate n-grams. Combine by geometric mean, and multiply by a brevity penalty that punishes candidates shorter than the reference (precision alone would reward outputting one safe word),

with \(c, r\) the candidate and (effective) reference lengths. Problem 6 computes it fully by hand and hits BLEU's most notorious edge case on the way.

Failure modes, and the learned metrics that replaced it

BLEU's known failures follow from its definition. It is blind to synonymy and paraphrase (any correct wording absent from the references scores zero), insensitive to meaning-inverting small edits (dropping a "not" costs one unigram), dependent on tokenization to the point that scores across papers were incomparable until sacreBLEU (Post, 2018) standardized it, weakly correlated with human judgments at the sentence level, and, most damningly for its modern use, unable to rank strong systems. The WMT metrics shared tasks found BLEU's correlation with human judgment collapsing precisely in the high-quality regime where decisions matter, and Freitag et al.'s analyses with professional MQM annotations showed BLEU preferring the wrong system in a substantial fraction of head-to-head comparisons of top systems. Two successors matter. chrF (Popović, 2015) stays surface-level but switches to character n-gram F-score, which forgives morphological variation and tokenization choices and is the robust cheap baseline. The learned metrics embed candidate and reference (and for COMET, the source) with a pretrained multilingual encoder and predict human scores directly. BLEURT (Sellam, Das and Parikh, 2020) fine-tunes BERT on synthetic perturbations then human ratings, while COMET (Rei et al., 2020) regresses from XLM-R representations of (source, hypothesis, reference) onto human assessment scores. They win the WMT metrics evaluations by wide margins because they measure adequacy through representations rather than string overlap. Their costs are opacity, potential biases of the underlying encoder (including preferring fluent hallucination over awkward accuracy if trained data leans that way), and the general hazard of optimizing against a learned metric, which invites metric gaming. The methodological lesson generalizes far beyond MT. Overlap metrics (ROUGE for summarization included) were adequate when systems were bad and are actively misleading when systems are good, and the same arc is now replaying with LLM-as-judge evaluation.

The transformer, briefly

The mechanism itself, scaled dot-product attention, the \(\sqrt{d}\) analysis, multi-head structure, and the residual block, is derived and implemented on the attention page, so this section only places it in the story. Relative to the recurrent seq2seq models above, the transformer (Vaswani et al., 2017) makes three changes. It deletes recurrence. Self-attention connects any two positions in one step, so the maximum path length for information and gradients drops from \(O(T)\) to \(O(1)\), attacking directly the long-dependency problem that the LSTM only mitigated. It restores order through positional encodings, since attention alone is permutation-equivariant. And, the change that decided history, it makes training parallel. An RNN must compute \(h_t\) after \(h_{t-1}\), so training a length-\(T\) sequence costs \(T\) sequential steps no matter how many processors are available, while a transformer under teacher forcing computes every position's prediction simultaneously, as a stack of matmuls over the whole sequence. The compute is \(O(T^2 d)\) versus recurrence's \(O(T d^2)\), more FLOPs at long lengths, but they are parallel FLOPs of exactly the shape GPUs deliver best, and wall-clock training time is what determines how much data a model can see. The original model is an encoder-decoder for translation, bidirectional encoder over the source, causal decoder with cross-attention, and that split previews the pretraining menu below. Encoder-only (BERT), decoder-only (GPT), and encoder-decoder (T5, BART) are the three ways to cut the same block diagram, distinguished by their masking. Decoder-only won the generative era for a systems reason as much as a modeling one, with one stream, one causal mask, every token both context and training target, and a KV cache that makes incremental generation cheap.

Pretraining paradigms, compared rigorously

Contextual representations: ELMo as the hinge

Static embeddings assign "bank" one vector for river and finance alike, and the obvious fix is to let context disambiguate. ELMo (Peters et al., 2018) trained a 2-layer bidirectional LSTM language model (forward and backward LMs with tied character-CNN inputs) on 1B words and handed downstream tasks a learned weighted combination of its layer representations. Every token's vector now depends on its sentence, and six diverse tasks improved by large margins overnight. ELMo is the hinge in the story because it changed the unit of transfer from a lookup table to a full pretrained network, while still being feature-based, meaning the LSTM stayed frozen and task models trained on top. The next step, fine-tuning the whole network (pioneered at scale by ULMFiT and GPT), is a transfer question taken up in the next section. Here the question is what objective to pretrain with, and the 2018-2020 literature is a controlled experiment on exactly that.

Masked language modeling: BERT

BERT (Devlin et al., 2019) wanted a deep bidirectional encoder, and a bidirectional network cannot train as a standard LM. With both directions visible, predicting token \(t\) from a stack of layers lets information about \(t\) flow around through other positions ("see itself"), collapsing the task. Masked language modeling makes prediction well-posed by deletion. Select 15% of token positions, replace them, and train the encoder to recover the originals from full two-sided context, a Cloze task. The celebrated detail is what "replace" means. Of the selected positions, 80% become [MASK], 10% become a uniformly random token, and 10% are left unchanged. The reason is a train-test mismatch. [MASK] never occurs in downstream text, so a model that only ever predicts at [MASK] positions could learn representations of real tokens that are never trained as prediction targets. Random replacement forces the encoder to treat every position as potentially corrupted, keeping representations of observed tokens honest, and the unchanged 10% anchors the target distribution toward copying when the token is in fact correct. The known costs of MLM are that only 15% of positions produce loss per pass (a sample-efficiency handicap ELECTRA later attacked), that pretraining sees [MASK] tokens fine-tuning never does despite the 80/10/10 mitigation, and that masked targets are predicted independently given the context, ignoring dependencies between masked positions (the explicit motivation for XLNet).

Next-sentence prediction and its refutation

BERT also trained a second objective, next-sentence prediction, a binary classifier on sentence pairs, half actually consecutive, half random, intended to teach discourse-level relations for QA and NLI. RoBERTa (Liu et al., 2019) ran the ablation properly and found that dropping NSP while packing full-length contiguous text matches or improves every downstream result. The likely post-mortem is that the random-pair negatives make NSP mostly a topic classification task (random sentences come from different documents), too easy to teach much, while the segment-pair format halves the usable context length. RoBERTa's larger lesson was uncomfortable for architecture papers. With the same architecture, training longer, on more data (160GB vs 16GB), with bigger batches and dynamic masking (resampling masks per epoch rather than freezing them in preprocessing), it simply outperformed BERT, meaning a good fraction of the apparent objective and architecture progress of 2019 was under-training. ALBERT's sentence-order prediction (swap two sentences, detect the swap) is the salvaged version of NSP, hard enough to teach coherence rather than topic.

Permutation LM, denoising seq2seq, replaced-token detection

XLNet (Yang et al., 2019) set out to get bidirectional context without masking corruption, maximizing the expected AR log-likelihood over random permutations of the factorization order, \( \E_{z \sim \mathcal{Z}_T} \sum_t \log \P(x_{z_t} \mid x_{z_{< t}}) \). Each token is predicted from a random subset of the others, so the model learns from two-sided context while remaining a proper product of conditionals with no [MASK] symbol and no independence assumption among targets. Implementation needs two-stream attention (a query stream that knows position but not content of the target, a content stream for everything else) because a standard transformer's hidden state at a position both must and must not contain that position's identity. XLNet beat BERT, then RoBERTa showed matched-scale training closes most of that gap, an instructive case study in how compute confounds objective comparisons.

The denoising seq2seq family corrupts text and trains a full encoder-decoder to restore it. BART (Lewis et al., 2020) corrupts with span deletion, infilling, sentence shuffling and trains the decoder to regenerate the original, making it natively a conditional generator, strong at summarization and generation while its encoder still serves classification. T5 (Raffel et al., 2020) is both an objective and a systematic study. The objective is span corruption (mask contiguous spans, replace each with a single sentinel token, train the decoder to emit the sentinels with their contents, cheaper than full reconstruction because the target is short) plus the text-to-text framing in which every task, translation, classification, regression-as-string, becomes text in, text out. The T5 paper's ablation grid, objectives, architectures, corpus sizes and cleanups (introducing C4), under matched compute, is the closest thing the era produced to a fair comparison, and its conclusions, denoising beats plain LM for downstream fine-tuned quality at these scales, span corruption about ties other denoisers while being cheapest, presaged the later consensus that objective differences shrink as scale grows.

ELECTRA (Clark et al., 2020) reframed pretraining as discrimination. A small generator MLM proposes plausible replacements at masked positions, and the main model, a discriminator, predicts for every token whether it is original or replaced. The sample-efficiency argument is arithmetic. MLM back-propagates loss from 15% of positions, replaced-token detection from 100%, so each sequence yields roughly 6-7× more learning signal per pass, and binary detection over the full sequence avoids the [MASK] mismatch entirely (the discriminator never sees [MASK], only fluent text with subtle substitutions). The reported results were that a small ELECTRA trained on one GPU outperformed GPT, and that ELECTRA-Large matched RoBERTa and XLNet with under a quarter of their pretraining compute. The generator must be weak, a strong generator's replacements are too hard to detect and the task degenerates. This adversarial-flavored setup is trained jointly but with the generator's own MLM loss, not GAN-style.

What each objective buys

The unifying view is that every objective is a choice of corruption process plus a choice of what to predict, and the choice shapes the representation. Bidirectional denoisers build the best encoders per parameter because every prediction uses full context. Autoregressive models build generators, and at sufficient scale their representations turn out to transfer well anyway, which, combined with the systems advantages of one causal stream, is why the frontier consolidated on decoder-only AR models and relegated the rest to encoder niches. Those niches are large. Retrieval, reranking, and classification fleets still run on MLM-family encoders.

Transfer: from frozen features to prompting

Feature-based versus fine-tuning, and instability

The feature-based recipe (ELMo) freezes the pretrained network and trains a task head, while fine-tuning (ULMFiT, GPT, BERT) updates everything, and won on accuracy nearly everywhere, at a price that took two years to document properly. Fine-tuning BERT-class models on small datasets is unstable. Dodge et al. (2020) showed that across random seeds (which control both data order and head initialization), final accuracy on small GLUE tasks varies by many points, with some seeds failing to learn at all, and that published comparisons between models were often within seed noise. Mosbach, Andriushchenko and Klakow (2021) traced the failed runs to optimization, vanishing gradients early in training and the bias-correction details of Adam variants, rather than to the folk explanation of catastrophic forgetting, and showed the fix is mundane. Smaller learning rates with warmup and longer training make fine-tuning stable and make many published "stabilization" techniques unnecessary. The practical residue is to report mean and spread over seeds, never a single run, a norm the evaluation section returns to.

Parameter-efficient fine-tuning: adapters, LoRA, prompts

Full fine-tuning writes a complete model copy per task, which at modern scales is untenable for storage and serving. Adapters (Houlsby et al., 2019) insert small bottleneck MLPs (down-project, nonlinearity, up-project, residual) after each sublayer and train only them, roughly 3% of parameters for near-parity, at the cost of extra inference depth. LoRA (Hu et al., 2021) removes even that cost with a low-rank argument. The hypothesis, supported by Aghajanyan, Zettlemoyer and Gupta's (2021) measurements that fine-tuning has low intrinsic dimension, is that the update to a pretrained weight matrix, not the matrix itself, is approximately low-rank. So parameterize it that way. Freeze \(W_0 \in \R^{d \times k}\) and learn

with \(A\) initialized Gaussian and \(B\) initialized to zero so training starts exactly at the pretrained model (\(\Delta W = 0\)). The \(\alpha/r\) scaling keeps the update magnitude comparable across ranks. The forward pass computes \( h = W_0 x + \frac{\alpha}{r} B (A x) \), two thin matmuls. The parameter arithmetic is the selling point. A \(4096 \times 4096\) attention projection has 16.8M parameters. At \(r = 8\), \(A\) and \(B\) together have \(2 \times 8 \times 4096 = 65{,}536\), a 256× reduction, and applying LoRA only to \(W_Q, W_V\) across layers trains a fraction of a percent of the model. Because \(\Delta W\) is an ordinary matrix, it merges into \(W_0\) by addition at deploy time, with zero added latency, unlike adapters, and a server can hot-swap tasks by swapping small \(\{A, B\}\) pairs. Prefix tuning (Li and Liang, 2021) instead learns virtual key-value vectors prepended at every layer. Prompt tuning (Lester, Al-Rfou and Constant, 2021) learns only soft input embeddings and showed a clean scaling result. It lags full fine-tuning at small scale and matches it beyond roughly 10B parameters, evidence that big models need steering more than rewriting.

Prompting and in-context learning

GPT-3 (Brown et al., 2020) demonstrated that a large enough AR model performs new tasks from instructions and a few examples placed in the context window, with no gradient updates at all. This is not "learning" in the parameter sense. The weights are frozen, and the mechanism is the model's forward pass conditioning on the demonstrations. As adaptation regimes, the progression is coherent. Fine-tuning moves all weights, LoRA moves a low-rank slice, prompt tuning moves only inputs, and in-context learning moves nothing, trading update capacity for immediacy at each step. Analyses complicated the picture usefully. Min et al. (2022) showed that replacing demonstration labels with random labels often barely hurts few-shot performance, implying demonstrations largely communicate format and domain rather than the input-output mapping, and the induction-head line of work discussed below is the leading mechanistic account of how copying-and-completing patterns in context is implemented. Instruction tuning and RLHF, which turn raw LMs into assistants, belong to the LLM-systems page. The point here is that prompting completed a transition in what "solving an NLP task" means, from designing a model to specifying a task in-band.

Core NLP tasks under the new regime

Sequence labeling and the CRF layer

Named entity recognition and POS tagging assign a tag per token, with segment structure encoded by schemes like BIO (B-PER, I-PER, O). Per-token softmax classification over contextual features handles most of it, but tags interact. I-PER cannot follow B-ORG, and enforcing that at decode time beats hoping the classifier notices. A linear-chain conditional random field (Lafferty, McCallum and Pereira, 2001) models the joint tag sequence globally. Given per-position emission scores \(\phi_t(y_t)\) (from a BiLSTM or BERT encoder) and a learned transition matrix \(A_{y, y'}\), define

Training minimizes \(-\log \P(y^* \mid x) = \log Z(x) - s(x, y^*)\), and the whole difficulty is \(Z(x)\), a sum over \(|\mathcal{T}|^T\) sequences. The forward algorithm computes it in \(O(T\,|\mathcal{T}|^2)\) by dynamic programming on the lattice. Define \(\alpha_t(y)\) as the log-sum-exp of scores of all length-\(t\) prefixes ending in tag \(y\),

The recursion is correct because every prefix ending in \(y\) at time \(t\) decomposes uniquely into a prefix ending in some \(y'\) at \(t{-}1\) plus one transition and one emission, and log-sum-exp distributes over that decomposition exactly as summation does over products. Decoding replaces log-sum-exp with max, which is the Viterbi algorithm, the same lattice, the \((\max, +)\) semiring instead of \((\mathrm{logsumexp}, +)\), plus back-pointers to recover the argmax path. With modern encoders the CRF's measured gains over independent softmax have shrunk to a point or less on English NER, but it remains the standard way to make structurally invalid outputs impossible rather than merely unlikely, which schema-bound production systems care about.

Parsing: transition-based and graph-based

Dependency parsing produces a directed tree over words (each word has one head, with labels like nsubj, obj on the arcs), while constituency parsing produces nested phrases. The transition-based approach treats parsing as a sequence of shift-reduce actions over a configuration (stack, buffer, arc set). The arc-standard system has three actions. SHIFT moves the front of the buffer onto the stack. LEFT-ARC makes the top of the stack the head of the second item (which is popped). RIGHT-ARC makes the second item the head of the top (which is popped). Parsing "She ate fish" runs as follows.

Exactly \(2n\) transitions parse an \(n\)-word sentence, so parsing is \(n\) classification decisions at \(O(n)\) total cost. Chen and Manning (2014) replaced the classical million-feature sparse classifiers with a small feedforward network over embeddings of the top stack/buffer words, their POS tags and arc labels, and got a faster, more accurate parser. It is the paper that convinced the parsing community embeddings were not optional. The costs of transition parsing are greedy error propagation (an early wrong pop is unrecoverable, though beam training and dynamic oracles patch this) and, for arc-standard, no non-projective trees. The graph-based alternative scores all \(n^2\) head-dependent pairs and finds the maximum spanning tree. Dozat and Manning's biaffine parser (2017) is the standard form, a BiLSTM (now BERT) encoder, separate MLP projections of each word as head \(h^{\text{head}}_j\) and as dependent \(h^{\text{dep}}_i\) (decoupling the two roles, same reasoning as attention's Q/K split), and a biaffine score

softmaxed over candidate heads \(j\) per dependent \(i\), with a second small biaffine for labels. Decoding takes each word's argmax head, falling back to Chu-Liu-Edmonds MST when the greedy graph has cycles, and handles non-projectivity natively. Constituency parsing followed the same arc, with span-based scorers and CKY-style decoding over \(s(i, j, \ell)\) span scores replacing grammar-driven chart parsers. Parsing accuracy on English benchmarks is high (mid-90s UAS) and parsers are now mostly infrastructure, features for downstream systems and probes for what neural models know, rather than an end in themselves.

Coreference, SRL, and question answering

Coreference resolution clusters mentions referring to the same entity. The end-to-end model of Lee et al. (2017) removed the mention-detection pipeline. Enumerate spans up to a width, score each for mention-hood \(s_m(i)\), prune, then score antecedent pairs \(s(i, j) = s_m(i) + s_m(j) + s_a(i, j)\) with a learned pairwise term, each mention selecting an antecedent or a dummy (cluster start), and training marginalizes over the correct antecedents. The task's hard core is world-knowledge cases, Winograd-style "the trophy does not fit in the suitcase because it is too big", which resisted surface features for decades and fell to large pretrained models, one of the cleaner demonstrations that pretraining absorbs commonsense-adjacent regularities. Semantic role labeling recovers predicate-argument structure (who did what to whom, when, where) in PropBank's frame inventory. The neural treatment (He et al., 2017) is BIO tagging conditioned on a marked predicate, and its role today is mostly as structured supervision and probing target, since QA formats (QA-SRL) and plain generation cover the use cases. Extractive question answering, SQuAD-style, reduces to span prediction. Two vectors \(w_s, w_e\) score every token position, \( \P(\text{start} = i) = \softmax_i(w_s\T h_i) \), likewise for end, and decoding takes the argmax valid span. BERT's QA head is exactly this, and SQuAD 2.0's unanswerable questions add a null-span calibration problem. Generative QA (T5, GPT family) frees the answer from being a source substring, which is both the feature (abstraction, multi-hop synthesis) and the bug (hallucinated answers, and evaluation that can no longer be exact-match string comparison). The trajectory across all these tasks is uniform, specialized architecture, then pretrained encoder plus thin task head, then, for many uses, a prompted generalist model, with the specialized stack surviving where latency, cost, or structural guarantees bind.

Interpretability and analysis

Probing classifiers and their confounds

A probe trains a small classifier to predict a linguistic property (POS, dependency relations, coreference) from frozen representations, and success is read as "the representation encodes the property". The confound is that the probe itself learns. An expressive probe can extract a property from representations that encode it only trivially, or memorize the task outright. Hewitt and Liang (2019) formalized the check with control tasks, the same probe trained to predict random but consistent word-type labels, and defined selectivity as the gap between task and control accuracy. A probe result without a control is uninterpretable. Voita and Titov (2020) recast probing as minimum description length, measuring how cheaply a property can be extracted rather than whether it can. The most striking positive result is Hewitt and Manning's structural probe (2019), a single linear projection under which squared distances between BERT word vectors approximate parse-tree distances, evidence that something tree-shaped is linearly present, with the standard caveat that presence under a probe is not evidence the model uses it. On the accumulated evidence (surveyed as "BERTology" by Rogers, Kovaleva and Rumshisky, 2020), BERT-like models encode surface features in lower layers, syntax in middle layers, and semantic/task features in upper layers, and Tenney, Das and Pavlick (2019) showed the expected layer of each property ordering itself like the classical pipeline, POS before parsing before SRL before coreference.

The attention-explanation debate

Attention weights look like explanations, and the field spent 2019 arguing about whether they are. Jain and Wallace ("Attention is not Explanation", 2019) showed, for BiLSTM-attention text classifiers, that attention weights correlate weakly with gradient-based feature importance and that one can often find alternative attention distributions producing the same predictions, concluding the weights cannot be read as faithful importance. Wiegreffe and Pinter ("Attention is not not Explanation", 2019) answered on methodology. The counterfactual distributions were constructed per-instance with the rest of the model frozen, so they are not attentions the trained model would produce. When an adversary must train end-to-end to produce deviant attention with matched predictions, it often fails or pays in performance, and attention may still be a plausible (useful to humans) if not faithful (causally accurate) explanation, a distinction the debate forced the field to make precise. The reasonable synthesis is that attention weights are one causal variable among many (values, residual stream, other heads), useful as hypotheses and diagnostics, unreliable as verdicts, and any explanation claim needs a stated faithfulness test.

Mechanistic interpretability's newer results

Mechanistic work aims at circuits rather than correlations. Induction heads (Elhage et al., 2021, and Olsson et al., 2022, at Anthropic) are a two-head circuit implementing in-context copying, a previous-token head writes "token B followed A" into B's residual stream, and an induction head at a later A queries for that pattern and predicts B, i.e. the rule [A][B] … [A] → [B]. The suggestive finding is a phase change early in training where induction heads form at the same time as in-context learning ability appears, across model sizes, with intervention evidence in small models. At frontier scale the link remains a strong hypothesis rather than a proven mechanism. Sparse autoencoders attack superposition, the observation (Elhage et al., 2022, toy models) that networks pack more features than dimensions into non-orthogonal directions. Train an overcomplete sparse dictionary on residual-stream activations so each direction activates rarely and, one hopes, monosemantically. Bricken et al. (2023) established this on small models. Templeton et al. (2024) scaled it to a production model (Claude 3 Sonnet), extracting millions of features including abstract, multilingual, multimodal ones, and demonstrated causal handles by clamping features (the Golden Gate Bridge demonstration), with follow-on work at Google DeepMind (Gemma Scope) releasing open SAE suites. Feature-circuit methods (Marks et al., 2024) connect SAE features into causal graphs for specific behaviors. The honest caveats, stated plainly in the papers themselves, are that SAE reconstructions are lossy, feature inventories are incomplete and not unique, naming features by inspection invites the same illusions probing suffered, and circuit-level accounts verified end-to-end exist mostly for small models and narrow behaviors. It is the most promising program in interpretability, not a solved one.

Multilinguality

Multilingual pretraining, one model, many languages, mostly shared parameters, produced one of the field's genuine surprises, zero-shot cross-lingual transfer. Fine-tune multilingual BERT on English NER and it performs credibly on German or Hindi NER despite mBERT having no parallel data and no explicit alignment objective (Pires, Schlinger and Garrette, 2019, and Wu and Dredze, 2019). Shared subwords help but transfer survives even across scripts with near-zero lexical overlap (K et al., 2020), implying the model aligns languages through structural similarity alone. XLM-R (Conneau et al., 2020) scaled the recipe to 100 languages on 2.5TB of CommonCrawl and named the central tension, the curse of multilinguality. At fixed capacity, adding languages first helps low-resource ones (positive transfer) and then hurts everyone (capacity dilution). Per-language performance degrades as the language count grows unless parameters scale with it, which is why high-resource languages prefer monolingual models and why later multilingual systems (NLLB's 200-language translation model at Meta, the Aya models at Cohere) mix language-specific capacity, careful sampling temperatures, and participatory data collection (the Masakhane community's work on African languages being the model example) rather than naive pooling.

Tokenization is where multilingual inequity becomes mechanically measurable. A subword vocabulary trained on web-frequency text over-fragments underrepresented languages and scripts. Petrov et al. (2023) measured token-count inflation for the same translated content and found some language pairs differing by up to 15× in token length, with non-Latin scripts systematically inflated, in the worst cases fragmenting to multiple tokens per character. The consequences are not cosmetic. API cost per unit of meaning, effective context length, and latency all scale with token count, so the same model is measurably worse and more expensive for speakers of inflated languages, and few-shot prompts fit fewer examples. Fixes under study include byte-level and tokenizer-free models (ByT5, Meta's Byte Latent Transformer), vocabulary re-balancing with per-language sampling temperature, and per-script vocabulary allocation. Low-resource NLP more broadly (Joshi et al., 2020, taxonomize the resource distribution's brutal skew) remains the clearest case where the field's "scale the web corpus" default simply does not apply. The web text does not exist, the benchmarks encode religious-text domain skew, and the annotation must be built with speaker communities, which is a scientific and logistical program, not a modeling trick.

Evaluation and its crisis

NLP's evaluation regime broke in slow motion, in public, with each failure documented. The first failure was benchmark saturation. GLUE reached "human parity" within about a year of release and SuperGLUE, built harder in response, was passed within two, and a benchmark near its ceiling stops discriminating between systems and starts rewarding overfitting to its quirks. The second was annotation artifacts. Gururangan et al. (2018) and Poliak et al. (2018) showed a model seeing only the hypothesis, no premise, gets around 67% on SNLI against a 34% majority baseline, because crowdworkers generating contradictions reached for negation and generating entailments reached for generic words, leaving class-conditional lexical fingerprints. A dataset can therefore be largely solved without performing the task it claims to measure, and headline NLI numbers of that era partly measured artifact exploitation. The third was adversarial evaluation. Jia and Liang (2017) appended one distracting but non-contradicting sentence to SQuAD passages and the average F1 of sixteen published models fell from 75% to 36%, a distribution shift no larger than a determined test-taker would produce. The fourth was contamination. With web-scale pretraining, benchmark test sets leak into training corpora, and n-gram overlap audits (which GPT-3's paper ran on itself) are necessary but insufficient, since paraphrased leakage evades them. Contamination checking is now a standard component of evaluation harnesses.

The constructive responses define current practice. Contrast sets (Gardner et al., 2020) have the original annotators minimally perturb test instances across the decision boundary, measuring whether the model tracks the feature that defines the task. Hypothesis-only and partial-input baselines are run before publishing a dataset. Behavioral test suites (Ribeiro et al.'s CheckList, 2020) probe capabilities like negation and entity swaps directly. Adversarially collected benchmarks (ANLI, Dynabench) keep humans in the loop generating failures against current models. An honest evaluation today reports multiple seeds with variance (the fine-tuning instability result makes single runs uninterpretable), a contamination audit, in-distribution and out-of-distribution/adversarial slices, partial-input baselines for the dataset itself, per-slice results rather than one aggregate, and, for generation, learned metrics plus some human or rubric evaluation, with the metric's own failure modes acknowledged. The through-line from BLEU to SNLI to LLM leaderboards is the same lesson. A benchmark is a proxy, proxies saturate and leak, and the moment a number becomes a target it stops measuring what it was built to measure.

Implementation

Everything in this section was run on this machine (NVIDIA H100 80GB HBM3, PyTorch 2.7, CUDA 12.8, JAX 0.6). The printed outputs are pasted from the actual runs, not typed from expectation.

Skip-gram with negative sampling, trained for real

The trainer below implements exactly the objective and gradients of Problem 2 (via autograd), with the unigram-to-the-3/4 noise distribution, subsampling at \(t = 10^{-4}\), and a per-position random window of 1-5. It was trained on the first 100MB of cleaned Wikipedia text (text8, 17,005,207 tokens, 71,290 words with count \(\ge 5\), 8.43M tokens after subsampling, 50.6M (center, context) pairs), with \(d = 128\), 5 negatives, batch 8192, Adam at \(2 \times 10^{-3}\). Three epochs took 52 seconds on the H100. The PyTorch tab is the version that produced the output below. The JAX tab is the same model as a pure-functional training step.

import collections, numpy as np, torch, torch.nn as nn
import torch.nn.functional as F

rng = np.random.default_rng(0)
text = open("text8").read().split()          # 17,005,207 tokens
counts = collections.Counter(text)
vocab = [w for w, c in counts.most_common() if c >= 5]   # 71,290 types
stoi = {w: i for i, w in enumerate(vocab)}
V = len(vocab)
ids = np.array([stoi[w] for w in text if w in stoi])

# subsampling of frequent words: keep with prob min(1, sqrt(t/f))
freq = np.bincount(ids, minlength=V) / len(ids)
keep = np.minimum(1.0, np.sqrt(1e-4 / freq[ids]))
ids = ids[rng.random(len(ids)) < keep]       # 16.72M -> 8.43M tokens

# noise distribution: unigram^(3/4), renormalized
p_neg = np.bincount(ids, minlength=V).astype(np.float64) ** 0.75
p_neg = torch.tensor(p_neg / p_neg.sum(), dtype=torch.float32, device="cuda")

def make_pairs(ids, window, rng):             # random window in [1, window]
    n, b = len(ids), rng.integers(1, 6, size=len(ids))
    cs, os_ = [], []
    for off in range(1, window + 1):
        m = (b >= off)[: n - off]
        idx = np.arange(n - off)[m]
        cs += [ids[idx], ids[idx + off]]      # both directions
        os_ += [ids[idx + off], ids[idx]]
    return np.concatenate(cs), np.concatenate(os_)

centers, contexts = make_pairs(ids, 5, rng)   # 50.6M pairs

d, K, B = 128, 5, 8192
v_in = nn.Embedding(V, d).cuda()              # center vectors
u_out = nn.Embedding(V, d).cuda()             # context vectors
nn.init.uniform_(v_in.weight, -0.5 / d, 0.5 / d)
nn.init.zeros_(u_out.weight)
opt = torch.optim.Adam([*v_in.parameters(), *u_out.parameters()], lr=2e-3)

cen, con = torch.from_numpy(centers), torch.from_numpy(contexts)
for ep in range(3):
    perm = torch.randperm(len(cen))
    for i in range(0, len(cen) - B + 1, B):
        j = perm[i : i + B]
        c, o = cen[j].cuda(), con[j].cuda()
        neg = torch.multinomial(p_neg, B * K, replacement=True).view(B, K)
        v_c, u_o, u_n = v_in(c), u_out(o), u_out(neg)   # (B,d) (B,d) (B,K,d)
        pos = F.logsigmoid((v_c * u_o).sum(-1))          # log sigma(u_o . v_c)
        negs = F.logsigmoid(-(u_n @ v_c.unsqueeze(-1)).squeeze(-1))
        loss = -(pos + negs.sum(-1)).mean()              # Problem 2 objective
        opt.zero_grad(set_to_none=True); loss.backward(); opt.step()

# nearest neighbors by cosine over the center vectors
W = v_in.weight.detach()
Wn = W / W.norm(dim=1, keepdim=True)
def neighbors(w, k=8):
    sims = Wn @ Wn[stoi[w]]
    top = sims.topk(k + 1).indices.tolist()
    return [(vocab[i], round(sims[i].item(), 3)) for i in top if i != stoi[w]][:k]

# epoch losses: 2.3527, 2.1538, 2.1029      (52 s total, one H100)
# physics -> electromagnetism .716, electrodynamics .715, mechanics .705,
#            chemistry .695, quantum .681, fermi .672, dirac .661
# monday  -> sunday .687, thanksgiving .678, friday .670, wednesday .665
# three   -> four .911, five .902, two .891, seven .882, one .874
# guitar  -> guitars .798, bass .780, acoustic .744, vocals .712, drums .700
# king    -> kings .624, shalmaneser .615, sobieski .612, reigned .606

import jax, jax.numpy as jnp

def init_params(key, V, d=128):
    k1, _ = jax.random.split(key)
    return {
        "v_in": jax.random.uniform(k1, (V, d), minval=-0.5 / d, maxval=0.5 / d),
        "u_out": jnp.zeros((V, d)),      # zero init: first loss = (K+1) ln 2
    }

def sgns_loss(params, center, context, negs):
    """center, context: (B,) int ids; negs: (B, K) int ids."""
    v_c = params["v_in"][center]                      # (B, d)
    u_o = params["u_out"][context]                    # (B, d)
    u_n = params["u_out"][negs]                       # (B, K, d)
    pos = jax.nn.log_sigmoid(jnp.sum(v_c * u_o, -1))               # (B,)
    neg = jax.nn.log_sigmoid(-jnp.einsum("bkd,bd->bk", u_n, v_c))  # (B, K)
    return -jnp.mean(pos + neg.sum(-1))               # Problem 2 objective

@jax.jit
def sgd_step(params, center, context, negs, lr=0.05):
    loss, grads = jax.value_and_grad(sgns_loss)(params, center, context, negs)
    params = jax.tree.map(lambda p, g: p - lr * g, params, grads)
    return params, loss

# pair generation, subsampling, and the unigram^0.75 sampler are identical
# to the PyTorch tab (numpy on the host); the update itself is 3 gathers,
# 2 einsums, and a tree_map. Sanity check at init: with u_out = 0 every
# logit is 0, so loss = -(K+1) log sigma(0) = 6 ln 2 = 4.1589, and the
# first printed loss of an untrained step is exactly 4.158883.

The learned space is worth examining. Function words were subsampled away and content structure dominates. Number words form a tight cluster (three-four at cosine 0.911), weekday names find each other, and "physics" retrieves its subfields. The analogy results are the honest version of the famous demo. "man is to king as woman is to ?" ranks a Polish king (sobieski) first and queen second at cosine 0.494, and "france is to paris as germany is to ?" ranks leipzig, then berlin. On 17M tokens with \(d = 128\), the geometry is real but noisy. The textbook-clean analogies come from 100B-token training runs, and even there the input-exclusion caveat from the evaluation section applies.

An LSTM cell from primitives, checked against nn.LSTM

One function, the six equations from the derivation, using PyTorch's gate ordering (i, f, g, o stacked along the first axis of the weight matrices) so the reference module's own weights can drive it. Run in float64 so any disagreement is a logic bug rather than accumulation order.

import torch, torch.nn as nn

def lstm_cell(x, h, c, w_ih, w_hh, b_ih, b_hh):
    """x: (B, D); h, c: (B, H). Weights in nn.LSTM layout: [i, f, g, o]."""
    gates = x @ w_ih.T + h @ w_hh.T + b_ih + b_hh    # (B, 4H)
    i, f, g, o = gates.chunk(4, dim=1)
    i = torch.sigmoid(i)      # input gate: whether to write
    f = torch.sigmoid(f)      # forget gate: what to keep of c_{t-1}
    g = torch.tanh(g)         # candidate: bounded write content
    o = torch.sigmoid(o)      # output gate: what to expose as h
    c_new = f * c + i * g     # the additive path; dc_t/dc_{t-1} ~ diag(f)
    h_new = o * torch.tanh(c_new)
    return h_new, c_new

torch.manual_seed(0)
B, T, D, H = 4, 12, 16, 32
ref = nn.LSTM(D, H, batch_first=True).double()
x = torch.randn(B, T, D, dtype=torch.float64)
out_ref, _ = ref(x)

h = torch.zeros(B, H, dtype=torch.float64)
c = torch.zeros(B, H, dtype=torch.float64)
outs = []
for t in range(T):
    h, c = lstm_cell(x[:, t], h, c, ref.weight_ih_l0, ref.weight_hh_l0,
                     ref.bias_ih_l0, ref.bias_hh_l0)
    outs.append(h)
ours = torch.stack(outs, dim=1)
print((ours - out_ref).abs().max())   # tensor(1.6653e-16): exact to float64
assert torch.allclose(ours, out_ref, atol=1e-12)

import jax, jax.numpy as jnp
jax.config.update("jax_enable_x64", True)

def lstm_cell(params, carry, x):
    h, c = carry
    w_ih, w_hh, b = params
    gates = x @ w_ih.T + h @ w_hh.T + b              # (B, 4H), order i,f,g,o
    i, f, g, o = jnp.split(gates, 4, axis=1)
    i, f, o = jax.nn.sigmoid(i), jax.nn.sigmoid(f), jax.nn.sigmoid(o)
    g = jnp.tanh(g)
    c = f * c + i * g                                # additive cell path
    h = o * jnp.tanh(c)
    return (h, c), h

def lstm(params, x):                                 # x: (B, T, D)
    B, T, D = x.shape
    H = params[1].shape[1]
    carry = (jnp.zeros((B, H)), jnp.zeros((B, H)))
    _, hs = jax.lax.scan(lambda ca, xt: lstm_cell(params, ca, xt),
                         carry, x.swapaxes(0, 1))    # scan over time
    return hs.swapaxes(0, 1)                         # (B, T, H)

# driving it with the same nn.LSTM weights (biases summed into one term):
# params = (W_ih, W_hh, b_ih + b_hh) exported from the PyTorch reference
# max |ours - nn.LSTM| = 1.3878e-16 in float64.
# The scan makes the sequential dependency explicit: XLA cannot
# parallelize over T, which is the whole training-speed argument
# for attention in one line of code.

Additive and multiplicative attention

Both scorers from the seq2seq section, shape-annotated, with masking done the only correct way (minus infinity before the softmax). The additive scorer materializes a \((B, T, d_{\text{att}})\) tensor per decoder step, while the multiplicative scorer is one batched matmul, which is the entire efficiency argument that carried into the transformer.

import torch, torch.nn as nn

class AdditiveAttention(nn.Module):
    """Bahdanau: score(s, h_j) = v^T tanh(W s + U h_j)."""
    def __init__(self, d_dec, d_enc, d_att):
        super().__init__()
        self.W = nn.Linear(d_dec, d_att, bias=False)
        self.U = nn.Linear(d_enc, d_att, bias=False)
        self.v = nn.Linear(d_att, 1, bias=False)

    def forward(self, s, H, mask=None):
        # s: (B, d_dec) decoder state; H: (B, T, d_enc) encoder states
        scores = self.v(torch.tanh(self.W(s).unsqueeze(1) + self.U(H)))
        scores = scores.squeeze(-1)                        # (B, T)
        if mask is not None:                               # pad positions
            scores = scores.masked_fill(~mask, float("-inf"))
        a = torch.softmax(scores, dim=-1)                  # (B, T)
        ctx = torch.bmm(a.unsqueeze(1), H).squeeze(1)      # (B, d_enc)
        return ctx, a

class MultiplicativeAttention(nn.Module):
    """Luong general: score(s, h_j) = s^T W h_j. One matmul, no tanh."""
    def __init__(self, d_dec, d_enc):
        super().__init__()
        self.W = nn.Linear(d_enc, d_dec, bias=False)

    def forward(self, s, H, mask=None):
        scores = torch.bmm(self.W(H), s.unsqueeze(-1)).squeeze(-1)  # (B, T)
        if mask is not None:
            scores = scores.masked_fill(~mask, float("-inf"))
        a = torch.softmax(scores, dim=-1)
        ctx = torch.bmm(a.unsqueeze(1), H).squeeze(1)
        return ctx, a

# both return rows summing to exactly 1, with zero weight on masked
# positions; drop the W in Multiplicative and add a 1/sqrt(d) factor
# and you have written scaled dot-product attention.

import jax, jax.numpy as jnp

def additive_scores(params, s, H):
    """W: (d_dec, d_att); U: (d_enc, d_att); v: (d_att,)."""
    W, U, v = params
    t = jnp.tanh(s[:, None, :] @ W + H @ U)      # (B, T, d_att)
    return t @ v                                 # (B, T)

def mult_scores(W, s, H):
    """W: (d_enc, d_dec). One einsum: batches to a matmul."""
    return jnp.einsum("bd,btd->bt", s, H @ W)    # (B, T)

def attend(scores, H, mask=None):
    if mask is not None:
        scores = jnp.where(mask, scores, -jnp.inf)
    a = jax.nn.softmax(scores, axis=-1)          # (B, T), rows sum to 1
    return jnp.einsum("bt,btd->bd", a, H), a     # context: (B, d_enc)

# usage: ctx, a = attend(additive_scores(pa, s, H), H, mask)
#        ctx, a = attend(mult_scores(Wm, s, H), H, mask)
# The additive path builds a (B, T, d_att) intermediate every decoder
# step; the multiplicative path is one contraction, which is why the
# transformer kept the dot product and paid for it with 1/sqrt(d).

Beam search

Framework-agnostic by design (it consumes any function mapping a prefix to next-token log-probabilities), run here on the toy LM of Problem 5. The printed output reproduces the hand trace to four decimals, including the length-normalization flip.

import math

def beam_search(step_logprobs, bos, eos, beam=4, max_len=32, alpha=1.0):
    """step_logprobs(prefix) -> {token: logprob}. Returns completed
    hypotheses sorted by length-normalized score, best first."""
    live = [([bos], 0.0)]
    done = []
    for _ in range(max_len):
        cands = []
        for toks, lp in live:
            for tok, tlp in step_logprobs(toks).items():
                cands.append((toks + [tok], lp + tlp))
        live = []
        for toks, lp in sorted(cands, key=lambda c: c[1], reverse=True):
            if toks[-1] == eos:
                done.append((toks, lp))       # completed: out of the beam
            elif len(live) < beam:
                live.append((toks, lp))       # keep top-`beam` live
        if not live:
            break
    def norm(c):
        toks, lp = c
        return lp / (len(toks) - 1) ** alpha  # exclude BOS from length
    return sorted(done, key=norm, reverse=True)

P = {                                          # the toy LM of Problem 5
    "BOS": {"a": 0.6, "b": 0.3, "EOS": 0.1},
    "a":   {"a": 0.1, "b": 0.65, "EOS": 0.25},
    "b":   {"a": 0.4, "b": 0.3, "EOS": 0.3},
}
toy_lm = lambda prefix: {t: math.log(p) for t, p in P[prefix[-1]].items()}

for toks, lp in beam_search(toy_lm, "BOS", "EOS", beam=2, max_len=3):
    n = len(toks) - 1
    print(" ".join(toks[1:]), f"logp={lp:.4f}", f"norm={lp / n:.4f}")

# a b EOS  logp=-2.1456  norm=-0.7152     <- normalized winner
# a EOS    logp=-1.8971  norm=-0.9486     <- raw-logprob winner
# b a EOS  logp=-3.5066  norm=-1.1689
# b EOS    logp=-2.4079  norm=-1.2040
# EOS      logp=-2.3026  norm=-2.3026

A CRF layer with the forward algorithm

The forward recursion, Viterbi decoding, and the training loss \(\log Z - s(x, y^*)\), for one sequence (batching adds a leading dimension and masking, and the allennlp implementation linked below is the production version). Fed the scores from Problem 7, both frameworks print \(\log Z = 11.1783\) and the path N V N with score 11, matching the hand computation.

import torch, torch.nn as nn

class CRF(nn.Module):
    """Linear-chain CRF head. Emissions come from any encoder."""
    def __init__(self, n_tags):
        super().__init__()
        self.trans = nn.Parameter(torch.zeros(n_tags, n_tags))  # [from, to]

    def log_partition(self, emissions):          # emissions: (T, n_tags)
        alpha = emissions[0]                     # alpha_1(y) = phi_1(y)
        for t in range(1, emissions.size(0)):
            # logsumexp over source tag: (from, 1) + (from, to)
            alpha = torch.logsumexp(alpha.unsqueeze(1) + self.trans,
                                    dim=0) + emissions[t]
        return torch.logsumexp(alpha, dim=0)     # log Z

    def score(self, emissions, tags):            # s(x, y) for a tag path
        s = emissions[0, tags[0]]
        for t in range(1, emissions.size(0)):
            s = s + self.trans[tags[t - 1], tags[t]] + emissions[t, tags[t]]
        return s

    def nll(self, emissions, tags):              # training loss
        return self.log_partition(emissions) - self.score(emissions, tags)

    def viterbi(self, emissions):                # same lattice, (max, +)
        delta, back = emissions[0], []
        for t in range(1, emissions.size(0)):
            scores = delta.unsqueeze(1) + self.trans
            best, idx = scores.max(dim=0)
            delta = best + emissions[t]
            back.append(idx)
        path = [delta.argmax().item()]
        for idx in reversed(back):               # follow back-pointers
            path.append(idx[path[-1]].item())
        return path[::-1], delta.max().item()

crf = CRF(2)
with torch.no_grad():                            # Problem 7's numbers
    crf.trans.copy_(torch.tensor([[1., 2.], [2., 1.]]))
E = torch.tensor([[3., 1.], [1., 2.], [2., 0.]])
print(crf.log_partition(E))    # tensor(11.1783)
print(crf.viterbi(E))          # ([0, 1, 0], 11.0)  = N V N
print(crf.nll(E, torch.tensor([0, 1, 0])))   # tensor(0.1783) = -ln 0.837

import jax, jax.numpy as jnp

def crf_log_partition(emissions, trans):
    """emissions: (T, n_tags); trans: (n_tags, n_tags) [from, to]."""
    def step(alpha, e_t):
        alpha = jax.nn.logsumexp(alpha[:, None] + trans, axis=0) + e_t
        return alpha, None
    alpha, _ = jax.lax.scan(step, emissions[0], emissions[1:])
    return jax.nn.logsumexp(alpha)

def crf_score(emissions, trans, tags):
    e = emissions[jnp.arange(emissions.shape[0]), tags].sum()
    t = trans[tags[:-1], tags[1:]].sum()
    return e + t

def crf_nll(emissions, trans, tags):             # differentiable loss
    return crf_log_partition(emissions, trans) - crf_score(
        emissions, trans, tags)

def crf_viterbi(emissions, trans):               # (max, +) semiring
    def step(delta, e_t):
        scores = delta[:, None] + trans          # (from, to)
        return scores.max(axis=0) + e_t, scores.argmax(axis=0)
    delta, back = jax.lax.scan(step, emissions[0], emissions[1:])
    last = jnp.argmax(delta)
    def walk(tag, idx):
        return idx[tag], idx[tag]
    _, path = jax.lax.scan(walk, last, back[::-1])
    return jnp.concatenate([path[::-1], jnp.array([last])]), delta.max()

E = jnp.array([[3., 1.], [1., 2.], [2., 0.]])
T = jnp.array([[1., 2.], [2., 1.]])
print(crf_log_partition(E, T))   # 11.178321
print(crf_viterbi(E, T))         # ([0 1 0], 11.0)  = N V N
# gradients of log Z w.r.t. emissions are the marginals P(y_t | x):
# jax.grad(crf_log_partition)(E, T) gives the forward-backward result
# for free, which is the elegant fact hiding inside this loss.

How it is done in practice

The gap between these derivations and production is mostly about what runs where. Static embeddings survive as infrastructure. FastText-style vectors still back lightweight classifiers, typo-tolerant search, and cold-start recommender features, because a hash lookup plus a dot product costs microseconds on a CPU. The word2vec lineage's real production descendant, though, is the embedding layer. Every LLM's token embedding matrix is the same object trained end to end, usually weight-tied to the output softmax, and at a 128k-token vocabulary and \(d = 4096\) it is over 500M parameters, a nontrivial slice of small models. Sequence labeling in industry looks like the CRF section. spaCy and stanza pipelines (transition parsers, tagger heads) process document firehoses where an LLM call per document would be three orders of magnitude too expensive, and BERT-family encoders with task heads remain the workhorse for search ranking, moderation queues, and PII detection, distilled and quantized to hit single-digit-millisecond latency budgets.

The hardware numbers explain the architectural history better than any argument. On this machine's H100 80GB, a dense bf16 matmul at \(n = 4096\) sustains 744.6 TFLOP/s against 51.3 for fp32 and about 3.0 TB/s of memory bandwidth. The chip is built to do enormous parallel matmuls and starves on anything sequential or memory-bound. An LSTM's time steps are an irreducible serial chain of small matmuls (the lax.scan in the JAX tab is that chain made explicit), so it cannot fill the machine, while a transformer's training pass is a handful of huge matmuls that can. The same measurements show the second-order story. Naive attention at sequence length 2048 takes 5.309 ms and 2.32 GB of peak memory for the score matrix where the fused FlashAttention kernel takes 0.299 ms and 0.17 GB (17.8× faster), and at 16k the naive version simply OOMs while the fused kernel runs in 13.7 ms. Attention won because it converts sequence modeling into the operation hardware rewards, and then kernel engineering kept it viable as contexts grew. The details of that engineering live on the attention page and the LLM systems page.

The current research frontier

The representation-learning questions of this page are still open, in new clothes. Tokenization is being attacked directly. Byte-level models without a fixed vocabulary (ByT5 at Google, with MegaByte and the Byte Latent Transformer at Meta, the latter allocating compute by byte-entropy patches rather than tokens) aim to delete the tokenizer and its multilingual inequities, trading longer sequences for learned segmentation. Recurrence returned as state-space models. Mamba (Gu and Dao, 2023) and its successors get attention-competitive quality at linear cost with a selective state that is a direct descendant of the gating analysis above, and hybrid attention-SSM stacks now ship in production models (Jamba at AI21, among others). The interpretability program is racing to make SAE-scale feature analysis rigorous. Anthropic's circuit-tracing work, Google DeepMind's open Gemma Scope suite, and EleutherAI and academic replications are converging on shared tooling while the evaluation of interpretability itself (do features predict causal behavior?) remains unsettled. Multilingual equity work continues at Meta (NLLB), Cohere (the Aya models and their open multilingual instruction data), and the grassroots Masakhane collective. And evaluation reform is its own subfield, spanning holistic multi-metric harnesses (HELM, with EleutherAI's lm-evaluation-harness as the de facto standard), adversarial and dynamic collection, contamination forensics, and the uncomfortable study of LLM-as-judge biases, which is the BLEU story of this decade playing out in real time. The synthesis worth betting on is that the pendulum between "learn everything end to end" and "build in structure" that swung from n-grams to LSTMs to transformers has not stopped swinging, and knowing why each previous swing happened is the best predictor of the next one.

Open source to read

Each of these repays a focused read. The file listed is the right first door.

huggingface/transformers — the reference implementations of everything in the pretraining section. Open src/transformers/models/bert/modeling_bert.py and read BertSelfAttention through BertForMaskedLM. The 80/10/10 masking lives in the data collators, and the model file shows how thin every task head really is.

huggingface/tokenizers — production BPE/WordPiece/unigram in Rust. Start at tokenizers/src/models/bpe/trainer.rs, which is the merge loop from the subword section with real-world details (frequency thresholds, alphabet limits) attached.

explosion/spaCy — what industrial pipeline NLP looks like when latency matters. Start at spacy/language.py to see the pipeline architecture, then the transition parser under spacy/pipeline/.

stanfordnlp/stanza — neural pipelines (tagger, biaffine parser, NER) for 70+ languages. Start at stanza/pipeline/core.py and follow a document through the processors.

flairNLP/flair — the cleanest readable BiLSTM-CRF sequence tagger in the wild. Start at flair/models/sequence_tagger_model.py and compare its Viterbi and forward passes with the CRF block above.

facebookresearch/fastText — subword embeddings and the negative-sampling loop in C++. Start at src/fasttext.cc. The hierarchical-softmax and negative-sampling losses side by side in src/loss.cc are the two escapes from the softmax denominator, in code.

allenai/allennlp — archived but still the best-documented research NLP codebase. Start at allennlp/modules/conditional_random_field.py, the batched, masked, constrained CRF this page's single-sequence version simplifies.

UKPLab/sentence-transformers — where the embedding story ends up, contrastively trained sentence encoders for retrieval. Start at sentence_transformers/SentenceTransformer.py, then the losses directory for the modern relatives of the SGNS objective.

EleutherAI/lm-evaluation-harness — the standard evaluation harness, and a working museum of the evaluation-crisis section. Start at lm_eval/evaluator.py and note how much machinery exists purely to make comparisons fair.

Common misconceptions

"Word2vec is a deep learning model." It is a log-bilinear model with no hidden layer, just two embedding tables and a dot product. Its power came from the objective, the negative-sampling trick that made web-scale training feasible, and the data, not depth, and the Levy-Goldberg result makes the point sharply by showing an SVD of shifted PMI learns nearly the same thing.

"king − man + woman = queen shows embeddings encode linear relational structure." Partially, at best. The standard evaluation excludes the input words from the answer set. Without that exclusion the nearest neighbor is usually an input word, and with it, accuracy varies enormously by relation type. The run on this page ranks queen second on a 17M-token corpus. The parallelogram is a real but weak regularity that the benchmark's design flatters.

"Negative sampling is just a fast approximation to the softmax." It optimizes a different objective (binary classification against noise) whose optimum is shifted PMI, not the LM softmax. Unlike NCE it is not a consistent estimator of the softmax distribution. It happens that for representation learning the different objective is equally good, but a model needing calibrated probabilities cannot use it as a drop-in.

"LSTMs solved the vanishing gradient problem." They rerouted it. The additive cell path with \(f_t \approx 1\) preserves gradient flow along one channel, but gate pathways still attenuate, effective context in trained LSTMs is typically a few hundred tokens, and exploding gradients still require clipping. "Mitigated, on one designed path" is the defensible claim, and it is also the honest framing for residual networks.

"BERT masks 15% of tokens with [MASK]." It selects 15% of positions as prediction targets. Only 80% of those become [MASK], with 10% random tokens and 10% left unchanged, specifically so that representations of real, unmasked tokens stay trained and the encoder cannot treat non-[MASK] positions as guaranteed correct. Collapsing this detail loses the reason the trick exists, the train-test mismatch of a symbol that never appears downstream.

"Attention weights explain model decisions." The 2019 debate ended somewhere precise. Weights are not reliably faithful (alternative distributions can yield the same predictions, and correlation with other importance measures is weak), but the strongest negative claims used per-instance counterfactuals a trained model would not produce. Treat attention as a hypothesis generator, and require a stated faithfulness test, ablation, patching, or trained adversary, before any explanation claim.

"BLEU measures translation quality." BLEU measures clipped n-gram overlap with specific references. At sentence level it is noise (this page computes a reasonable translation to a score of 0.0 at order 4), it cannot see synonymy or a deleted negation, and at the quality frontier its system rankings disagree with professional human judgment often enough that WMT now leads with learned metrics. It survives as a cheap regression test, not a measure of quality.

"Encoders are obsolete, everything is a decoder-only LLM now." Generation consolidated on decoder-only models. Understanding workloads did not. Retrieval and reranking run on bidirectional encoders (the entire sentence-transformers ecosystem), classification and extraction fleets run distilled MLM-family models for cost and latency, and ELECTRA-style pretraining remains the compute-efficient way to build them. The paradigms specialized, they did not merge.

Self-check

References

1. Jurafsky, D. and Martin, J. H. Speech and Language Processing, 3rd edition draft. The standard reference for n-grams, smoothing, sequence labeling, and MT evaluation, freely available online.
2. Goldberg, Y. (2017). Neural Network Methods for Natural Language Processing. Morgan & Claypool.
3. Eisenstein, J. (2019). Introduction to Natural Language Processing. MIT Press.
4. Manning, C., Raghavan, P. and Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press.
5. Mikolov, T. et al. (2013). Efficient Estimation of Word Representations in Vector Space, and Distributed Representations of Words and Phrases and their Compositionality. arXiv:1301.3781, arXiv:1310.4546.
6. Pennington, J., Socher, R. and Manning, C. (2014). GloVe: Global Vectors for Word Representation. ACL Anthology D14-1162.
7. Levy, O. and Goldberg, Y. (2014). Neural Word Embedding as Implicit Matrix Factorization. NeurIPS 2014. See also Levy, Goldberg and Dagan (2015), TACL.
8. Bojanowski, P., Grave, E., Joulin, A. and Mikolov, T. (2017). Enriching Word Vectors with Subword Information. arXiv:1607.04606.
9. Sennrich, R., Haddow, B. and Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. arXiv:1508.07909. Kudo, T. (2018). Subword Regularization. arXiv:1804.10959.
10. Bengio, Y., Ducharme, R., Vincent, P. and Jauvin, C. (2003). A Neural Probabilistic Language Model. JMLR 3:1137-1155.
11. Hochreiter, S. and Schmidhuber, J. (1997). Long Short-Term Memory. Neural Computation 9(8):1735-1780.
12. Pascanu, R., Mikolov, T. and Bengio, Y. (2013). On the difficulty of training recurrent neural networks. arXiv:1211.5063.
13. Sutskever, I., Vinyals, O. and Le, Q. (2014). Sequence to Sequence Learning with Neural Networks. arXiv:1409.3215. Cho, K. et al. (2014). Learning Phrase Representations using RNN Encoder-Decoder. arXiv:1406.1078.
14. Bahdanau, D., Cho, K. and Bengio, Y. (2015). Neural Machine Translation by Jointly Learning to Align and Translate. arXiv:1409.0473.
15. Luong, M.-T., Pham, H. and Manning, C. (2015). Effective Approaches to Attention-based Neural Machine Translation. arXiv:1508.04025.
16. Papineni, K., Roukos, S., Ward, T. and Zhu, W.-J. (2002). BLEU: a Method for Automatic Evaluation of Machine Translation. ACL Anthology P02-1040.
17. Rei, R. et al. (2020). COMET: A Neural Framework for MT Evaluation. arXiv:2009.09025. Sellam, T., Das, D. and Parikh, A. (2020). BLEURT. arXiv:2004.04696.
18. Vaswani, A. et al. (2017). Attention Is All You Need. arXiv:1706.03762.
19. Peters, M. et al. (2018). Deep Contextualized Word Representations (ELMo). arXiv:1802.05365.
20. Devlin, J., Chang, M.-W., Lee, K. and Toutanova, K. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. arXiv:1810.04805.
21. Liu, Y. et al. (2019). RoBERTa: A Robustly Optimized BERT Pretraining Approach. arXiv:1907.11692.
22. Yang, Z. et al. (2019). XLNet: Generalized Autoregressive Pretraining. arXiv:1906.08237. Lewis, M. et al. (2020). BART. arXiv:1910.13461.
23. Raffel, C. et al. (2020). Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer (T5). arXiv:1910.10683.
24. Clark, K., Luong, M.-T., Le, Q. and Manning, C. (2020). ELECTRA: Pre-training Text Encoders as Discriminators. arXiv:2003.10555.
25. Conneau, A. et al. (2020). Unsupervised Cross-lingual Representation Learning at Scale (XLM-R). arXiv:1911.02116. Petrov, A. et al. (2023). Language Model Tokenizers Introduce Unfairness Between Languages. arXiv:2305.15425.
26. Lafferty, J., McCallum, A. and Pereira, F. (2001). Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. ICML 2001.
27. Chen, D. and Manning, C. (2014). A Fast and Accurate Dependency Parser using Neural Networks. ACL Anthology D14-1082. Dozat, T. and Manning, C. (2017). Deep Biaffine Attention for Neural Dependency Parsing. arXiv:1611.01734.
28. Hu, E. et al. (2021). LoRA: Low-Rank Adaptation of Large Language Models. arXiv:2106.09685.
29. Jia, R. and Liang, P. (2017). Adversarial Examples for Evaluating Reading Comprehension Systems. arXiv:1707.07328. Gururangan, S. et al. (2018). Annotation Artifacts in Natural Language Inference Data. arXiv:1803.02324.
30. Jain, S. and Wallace, B. (2019). Attention is not Explanation. arXiv:1902.10186. Wiegreffe, S. and Pinter, Y. (2019). Attention is not not Explanation. arXiv:1908.04626.
31. Rogers, A., Kovaleva, O. and Rumshisky, A. (2020). A Primer in BERTology. arXiv:2002.12327. Tenney, I., Das, D. and Pavlick, E. (2019). BERT Rediscovers the Classical NLP Pipeline. arXiv:1905.05950.
32. Olsson, C. et al. (2022). In-context Learning and Induction Heads. Anthropic. transformer-circuits.pub. Templeton, A. et al. (2024). Scaling Monosemanticity. Anthropic. transformer-circuits.pub.