Prelude to the Transformer: The Evolution of Neural Language Modeling

The evolution of neural language modeling represents a relentless drive toward architectures capable of capturing the hierarchical, long-range dependencies inherent in human language. This journey began with statistical n-gram models, which, despite their simplicity, formed the backbone of early machine translation and speech recognition systems. The advent of recurrent neural networks (RNNs) and their gated variants, particularly long short-term memory (LSTM) networks, introduced the promise of learning distributed representations and modeling sequences of variable length without explicit Markov assumptions. The sequence-to-sequence (seq2seq) paradigm later unified encoder-decoder frameworks, achieving state-of-the-art results in machine translation when augmented with attention mechanisms. Yet, each of these approaches harbored fundamental limitations—centered on long-range dependency modeling, computational parallelism, and training efficiency—that collectively underscored the need for a radical architectural shift. This chapter reconstructs this historical trajectory, analyzing the technical foundations, empirical benchmarks, and inherent constraints of pre-Transformer models, thereby establishing the conceptual vacuum that the Transformer architecture would ultimately fill.

The n-gram Era: Statistical Foundations and the Sparsity Curse

Markov Assumptions and Finite Contexts

At their core, n-gram language models are grounded in the Markov assumption: the probability of a word depends only on the preceding $n-1$ words. Formally, an n-gram model estimates the joint probability of a word sequence $w_1^T = w_1, w_2, \dots, w_T$ as a product of conditional probabilities:

$$ P(w_1^T) = \prod_{t=1}^{T} P(w_t | w_{t-n+1}^{t-1}) $$

where $w_{t-n+1}^{t-1}$ denotes the $(n-1)$-word history. The maximum likelihood estimate (MLE) for a specific n-gram $w_{t-n+1}^{t}$ is simply its count normalized by the count of its prefix:

$$ P_{\text{MLE}}(w_t | w_{t-n+1}^{t-1}) = \frac{C(w_{t-n+1}^{t})}{C(w_{t-n+1}^{t-1})} $$

This formulation is computationally tractable and interpretable, but it exacts a severe price: context truncation. No matter how large $n$ is chosen, only a fixed, finite window of preceding words influences the prediction. For languages with rich long-distance syntactic and semantic agreements—such as subject-verb agreement across clauses or pronoun resolution spanning multiple sentences—this window is inherently inadequate. A 5-gram model, for instance, cannot capture that a singular subject at the beginning of a paragraph governs a verb hundreds of tokens later.

Smoothing Techniques: Mitigating Data Sparsity

The MLE approach suffers catastrophically from data sparsity: in any realistic corpus, most possible n-grams never occur, leading to zero probabilities for unseen sequences. To address this, a rich taxonomy of smoothing techniques was developed, which redistribute probability mass from observed to unobserved events. Common methods include:

• **Additive (Laplace) smoothing**: Adding a small constant $\delta$ to all counts.

$$ P(w_t | w_{t-n+1}^{t-1}) = \frac{C(w_{t-n+1}^{t}) + \delta}{C(w_{t-n+1}^{t-1}) + \delta V} $$ where $V$ is the vocabulary size. This is simple but overly aggressive, flattening the distribution.

• **Good-Turing smoothing**: Reallocates probability based on the frequency of frequencies, estimating the probability of unseen events by the ratio of once-seen to twice-seen n-grams.

• **Kneser-Ney smoothing**: Perhaps the most effective for language modeling, it interpolates lower-order models with a discounting factor and, crucially, modifies the lower-order distribution to favor words that appear in many *different* contexts (high "continuation probability"). For a bigram model:

$$ P_{\text{KN}}(w_i | w_{i-1}) = \frac{\max(C(w_{i-1} w_i) - D, 0)}{C(w_{i-1})} + \lambda(w_{i-1}) \cdot P_{\text{cont}}(w_i) $$ where $D$ is a discount (typically 0.75), $\lambda$ is a normalization constant, and $P_{\text{cont}}(w_i)$ is the continuation probability proportional to the number of distinct words that follow $w_i$ in the training corpus.

While smoothing mitigates sparsity, it does not solve the fundamental context limitation. Moreover, the computational and memory costs grow exponentially with $n$: a vocabulary of size $V$ requires $O(V^n)$ parameters to store all n-gram probabilities, which becomes prohibitive beyond $n=5$ even for moderate $V$. This curse of dimensionality confines n-gram models to small contexts and necessitates aggressive pruning and data structures like tries or quantized hash tables for feasible deployment.

Empirical Benchmarks and the IBM Models

n-gram models achieved notable success in early machine translation through the IBM Models 1–5 (Brown et al., 1990). These models framed translation as a noisy channel process, modeling the alignment between source and target sentences. IBM Model 1, essentially a word-based n-gram model with uniform alignment probabilities, could be trained via Expectation-Maximization (EM) and produced rudimentary bilingual dictionaries. Subsequent models introduced fertility, distortion, and richer alignment structures, but all remained fundamentally phrase-agnostic and context-limited. On standard benchmarks like the Canadian Hansard corpus, these models plateaued at BLEU scores in the low 20s, with errors in word order, agreement, and lexical choice glaringly apparent.

The practical case of the Candide system (IBM, 1990s) illustrates both the potential and pitfalls. Candide combined IBM Model 4 with a specialized English language model (a trigram model with class-based generalization) and achieved competitive translation quality for its time. Yet, its language model component—a conventional n-gram model—was a primary source of errors: it could not enforce long-range grammatical constraints, leading to outputs that were locally plausible but globally incoherent. This highlighted a critical insight: improving translation required more than better alignment models; it demanded a fundamentally richer representation of linguistic structure and context.

Recurrent Neural Networks: Breaking the Markov Chains

The Recurrence Paradigm

RNNs introduced a paradigm shift by replacing fixed n-gram windows with a recurrent connection that theoretically allows information from arbitrarily far in the past to influence the present. At each time step $t$, an RNN processes an input $x_t$ (e.g., a word embedding) and updates a hidden state $h_t$ based on the previous hidden state $h_{t-1}$:

$$ h_t = f(W_{hh} h_{t-1} + W_{xh} x_t + b_h) $$

where $f$ is typically a non-linear activation such as $\tanh$ or ReLU. The output $y_t$ (e.g., a probability distribution over the vocabulary) is computed from $h_t$ via $y_t = \text{softmax}(W_{hy} h_t + b_y)$. This recurrence forms a directed graphical model over time, where the hidden state acts as a summary of all previous inputs.

The key theoretical advantage is the elimination of fixed context windows. In principle, the hidden state can propagate information across unlimited distances, making RNNs a natural fit for sequential data. Training proceeds via Backpropagation Through Time (BPTT), which unrolls the network for $T$ steps and applies standard gradient descent. The unrolling operation reveals the RNN as a deep network with shared parameters across time, where the depth equals the sequence length.

The Vanishing Gradient Problem

In practice, BPTT encounters severe difficulties due to the vanishing (or exploding) gradient problem. Consider the gradient of the loss $L$ with respect to a parameter $W$ at early time step $k$. Through the chain rule, this gradient involves products of Jacobian matrices $\frac{\partial h_t}{\partial h_{t-1}}$ along the path from $k$ to $T$:

$$ \frac{\partial L}{\partial W^{(k)}} \propto \sum_{t=k+1}