Historical Context and Foundational Concepts

The evolution of natural language processing (NLP) has been punctuated by several paradigm shifts, each addressing the fundamental limitations of its predecessor while introducing new capabilities. The current era of large language models (LLMs), exemplified by systems like GPT-4 and PaLM, did not emerge ex nihilo; rather, they represent the culmination of a historical progression from simple statistical estimators to complex neural architectures. Understanding this trajectory is essential not only for appreciating the architectural innovations of models like the Transformer but also for contextualizing the persistent challenges of scaling, alignment, and efficiency that define contemporary research. This chapter reconstructs this lineage, beginning with the sparse, count-based models of the 1990s, moving through the neural renaissance of the 2010s, and culminating in the 2017 Transformer paper that catalyzed the modern LLM revolution. We will formalize the core probabilistic framework of language modeling, dissect the evaluation metrics that have guided progress, and analyze the specific architectural choices—such as autoregressive decoding and pre-training—that have become standard. By the chapter’s end, the reader will possess a coherent technical narrative that connects foundational concepts to the cutting-edge challenges explored in subsequent chapters.

The Era of Statistical Language Models: n-grams and Sparse Representations

Before the dominance of neural networks, statistical language models were the cornerstone of NLP, particularly in speech recognition and machine translation. The most influential of these were *n-gram models*, which approximate the probability of a word sequence by factoring it into conditional probabilities of limited context length. Formally, an *n*-gram model estimates: $$ P(w_1, w_2, \dots, w_T) = \prod_{t=1}^{T} P(w_t | w_{t-n+1}, \dots, w_{t-1}) $$ where the condition depends on the previous $n-1$ words. This factorization relies on the *Markov assumption*: the next word depends only on a fixed-size history. For a bigram model ($n=2$), we have $P(w_t | w_{t-1})$. Probabilities are derived from *maximum likelihood estimation* (MLE) on a training corpus: $$ P(w_t | w_{t-1}) = \frac{C(w_{t-1}, w_t)}{C(w_{t-1})} $$ where $C(\cdot)$ denotes raw counts. This simplicity is both a strength and a fatal flaw. The primary limitation is the *curse of dimensionality*: as $n$ increases, the number of possible $n$-grams grows exponentially ($|V|^n$ for vocabulary size $|V|$), making it impossible to observe sufficient counts for all but the smallest $n$ and $|V|$. Even with large corpora, most plausible $n$-grams are unseen, leading to zero probabilities for any test sentence containing them. *Smoothing techniques* such as Kneser-Ney smoothing or Good-Turing discounting were developed to redistribute probability mass to unseen events, but they are essentially heuristic patches on a fundamentally inadequate representation.

Beyond data sparsity, *n*-grams fail to capture any notion of semantic or syntactic similarity. The model treats “cat” and “kitten” as entirely unrelated symbols because they never share the same context in the count matrix. There is no generalization across words. Furthermore, the fixed context window $n$ severely restricts *long-range dependencies*. Consider the sentence: “The bank of the river was steep, so we went to the financial institution to deposit money.” The word “institution” depends on “bank” many tokens earlier, but a 3-gram or even 5-gram model has no direct path to connect them. The dependency must be carried through intermediate words, which attenuates the signal exponentially with distance. This inability to model phenomena like coreference, agreement, and discourse structure is intrinsic to the local conditioning of *n*-grams.

Evaluation of these early models centered on *perplexity*, a metric derived from the test set log-likelihood. For a test corpus $W = w_1^T$, perplexity is defined as: $$ PP(W) = P(W)^{-1/N} = \exp\left(-\frac{1}{N} \sum_{t=1}^{T} \log P(w_t | w_{<t})\right) $$ where $N$ is the total number of words (or tokens). Perplexity can be interpreted as the exponential of the average cross-entropy between the model’s distribution and the empirical distribution, effectively measuring the “average branching factor” or uncertainty the model assigns to the next word. Lower perplexity indicates a better model. On the Penn Treebank dataset, a well-tuned 5-gram model with Kneser-Ney smoothing might achieve a perplexity around 100–120. While useful for relative comparison, perplexity has limitations: it is corpus-dependent and does not directly correlate with downstream task performance. Nevertheless, it remains a fundamental diagnostic for language models.

The *n*-gram era established the probabilistic formulation of language modeling as next-token prediction, a perspective that persists in modern LLMs. However, its representation—sparse, discrete counts—precluded learning from raw text in a way that captures meaning. The next revolution would come from representing words as dense, continuous vectors.

Neural Language Models: Embeddings and Sequential Processing

The early 2010s witnessed a shift from count-based models to *neural language models* (NLMs), driven by the insight that words could be represented as learned, dense vectors—*word embeddings*—that capture semantic and syntactic relationships. The breakthrough came with models like Word2Vec (Mikolov et al., 2013) and GloVe (Pennington et al., 2014), which trained shallow networks on large corpora to predict a word from its context (CBOW) or its context from the word (skip-gram). These embeddings exhibited remarkable linear regularities: for example, the vector operation $\text{king} - \text{man} + \text{woman} \approx \text{queen}$. This *distributional hypothesis*—words occurring in similar contexts have similar meanings—became a cornerstone of modern NLP.

The first neural language models incorporated these embeddings into probabilistic models. The seminal work by Bengio et al. (2003) introduced the *neural probabilistic language model* (NPLM). It mapped a context of $n-1$ words to a concatenated embedding vector, passed it through a feed-forward hidden layer, and produced a probability distribution over the vocabulary via a softmax: $$ P(w_t | w_{t-n+1}^{t-1}) = \frac{\exp(h^\top \mathbf{v}_{w_t} + b_{w_t})}{\sum_{w' \in V} \exp(h^\top \mathbf{v}_{w'} + b_{w'})} $$ where $h = \tanh(W \mathbf{E}(w_{t-n+1}^{t-1}) + d)$ is the hidden representation, $\mathbf{E}$ is the embedding matrix, and $\mathbf{v}_{w}$ is the output embedding for word $w$. The model was trained to maximize the log-likelihood on a corpus. While this allowed for generalization via shared embeddings, it still suffered from a fixed context window and did not inherently handle variable-length dependencies.

The next major step was the adoption of *recurrent neural networks* (RNNs), particularly the long short-term memory (LSTM) variant (Hochreiter & Schmidhuber, 1997) and gated recurrent units (GRUs). RNNs process sequences token by token, maintaining a hidden state $h_t$ that summarizes all previous tokens: $$ h_t = f_\theta(h_{t-1}, x_t) $$ where $x_t$ is the embedding of $w_t$, and $f_\theta$ is a parametric function (e.g., LSTM cell). In theory, this recurrent connection allows information from arbitrarily distant tokens to propagate forward, addressing the fixed-context limitation of *n*-grams and feed-forward NLMs. The LSTM introduced gating mechanisms—input gate $i_t$, forget gate $f_t$, output gate $o_t$—to regulate information flow into and out of a cell state $c_t$, mitigating the *vanishing/exploding gradient* problem that plagued simple RNNs. The equations for an LSTM cell are: $$ \begin{aligned} i_t &= \sigma(W_i \cdot [h_{t-1}, x_t] + b_i) \\ f_t &= \sigma(W_f \cdot [h_{t-1}, x_t] + b_f) \\ \tilde{c}_t &= \tanh(W_c \cdot [h_{t-1}, x_t