Foundations of Language Modeling

Foundations of Language Modeling

The fundamental challenge of natural language processing reduces to a deceptively simple question: given a sequence of words, what word comes next? This question, seemingly elementary, encompasses the full complexity of human language—its syntax, semantics, pragmatics, and the intricate web of relationships that bind words across sentences, paragraphs, and documents. Language modeling, at its core, is the formal framework through which we attempt to answer this question with mathematical rigor. The framework we adopt, and the theoretical foundations upon which it rests, determine not merely the performance of our systems but the very nature of what those systems can learn about language.

This chapter establishes the conceptual and mathematical foundations necessary for understanding modern large language models. We begin by formalizing language modeling as a probabilistic task—predicting the likelihood of sequences of tokens—and examining how the chain rule of probability enables us to decompose this seemingly intractable problem into tractable pieces. We then develop the information-theoretic foundations introduced by Claude Shannon in his seminal 1948 paper, establishing entropy, cross-entropy, and perplexity as the fundamental metrics by which we measure the quality of language models. With these foundations in place, we trace the historical evolution from n-gram models through hidden Markov models to early neural approaches, analyzing how each paradigm addressed the fundamental challenge of capturing long-range dependencies in text. We examine the categorical distribution over vocabulary and the computational challenge of softmax normalization at scale, previewing techniques that later chapters address in detail. The chapter concludes by establishing why the autoregressive formulation—predicting each token conditional on all preceding tokens—emerged as the dominant paradigm for modern language models, providing the theoretical motivation that underlies architectures from GPT to Claude.

Language Modeling as Probabilistic Sequence Prediction

The Formal Definition

A language model is a probability distribution over sequences of tokens drawn from a finite vocabulary. Given a vocabulary $\mathcal{V} = \{w_1, w_2, \ldots, w_V\}$ consisting of $V$ distinct tokens, a language model assigns a probability $P(w_1, w_2, \ldots, w_n)$ to any sequence of length $n$. The tokens themselves may represent words, subword units, characters, or any other discrete units of language—the choice of tokenization scheme is a separate design decision that we examine in subsequent chapters, but for now we treat tokens as given atomic units.

The power of this formulation lies in its generality. A perfect language model would assign high probability to fluent, coherent text and low probability to nonsensical or grammatically incorrect sequences. Such a model captures not only the surface statistics of language but implicitly encodes information about syntax, semantics, and pragmatics—the entire linguistic knowledge that humans acquire through exposure to language. This is because the probability of a word sequence reflects how likely native speakers are to produce that sequence, which in turn reflects the full complexity of linguistic structure.

Formally, we define a language model as a function $P: \mathcal{V}^* \rightarrow [0, 1]$ that maps any finite sequence of tokens to a probability value, satisfying the constraint that probabilities sum to one over all possible completions of any given prefix:

$$P(w_1, w_2, \ldots, w_n) \geq 0 \quad \text{for all sequences}$$

$$\sum_{w_{n+1} \in \mathcal{V}} P(w_1, w_2, \ldots, w_n, w_{n+1}) = 1 \quad \text{for all prefixes}$$

These constraints ensure that the language model defines a valid probability distribution over the infinite space of possible text sequences.

The Chain Rule of Probability

Directly modeling the joint probability of a sequence $P(w_1, w_2, \ldots, w_n)$ is computationally intractable for any reasonable vocabulary size and sequence length. For a vocabulary of size $V = 50{,}000$ and a sequence of length $n = 100$, the number of possible sequences is $V^n = 50{,}000^{100}$—a number so vast that it exceeds the number of atoms in the observable universe. We cannot possibly compute or store probabilities for all such sequences.

The chain rule of probability provides the key insight that enables us to break this problem into tractable pieces. The chain rule states that any joint probability distribution can be decomposed into a product of conditional probabilities:

$$P(w_1, w_2, \ldots, w_n) = P(w_1) \cdot P(w_2 \mid w_1) \cdot P(w_3 \mid w_1, w_2) \cdot \ldots \cdot P(w_n \mid w_1, w_2, \ldots, w_{n-1})$$

Written more compactly:

$$P(w_1, w_2, \ldots, w_n) = \prod_{i=1}^{n} P(w_i \mid w_1, w_2, \ldots, w_{i-1})$$

This decomposition is not merely a mathematical convenience—it reflects a fundamental insight about language itself. The probability of each word depends on all preceding words, but in a specific sequential manner. We predict each word based on the words that came before it, and then update our context for the next prediction.

This formulation transforms the language modeling problem from an intractable joint probability problem into a sequence of tractable conditional probability problems. At each position $i$, we need to compute:

$$P(w_i \mid w_1, w_2, \ldots, w_{i-1}) = \frac{P(w_1, w_2, \ldots, w_i)}{P(w_1, w_2, \ldots, w_{i-1})}$$

The task of language modeling thus reduces to predicting the next token given all preceding tokens. This is why we refer to language models as sequence models or sequence-to-sequence predictors—the fundamental operation is always: given a sequence, predict what comes next.

The Categorical Distribution and Softmax

At each position, the conditional probability distribution $P(w_i \mid w_1, \ldots, w_{i-1})$ is a categorical distribution over the vocabulary. A categorical distribution (also called a multinoulli distribution) is a probability distribution over $V$ mutually exclusive outcomes, where exactly one outcome occurs:

$$P(w_i = v_k \mid \text{context}) = \pi_k \quad \text{for } k = 1, 2, \ldots, V$$

where $\pi_k \geq 0$ and $\sum_{k=1}^{V} \pi_k = 1$.

In neural language models, we typically compute an unnormalized score (logit) $z_k$ for each vocabulary item, then convert these logits to probabilities using the softmax function:

$$P(w_i = v_k \mid \text{context}) = \text{softmax}(\mathbf{z})_k = \frac{\exp(z_k)}{\sum_{j=1}^{V} \exp(z_j)}$$

The softmax function is ubiquitous in language modeling because it satisfies the requirements for a categorical distribution: it produces non-negative values that sum to one, and it converts arbitrary real-valued logits into a proper probability distribution. The temperature parameter, which scales the logits before softmax, controls the sharpness of the distribution—lower temperatures produce sharper distributions favoring high-probability tokens, while higher temperatures produce flatter distributions with more entropy.

The denominator of the softmax—the partition function $\sum_{j=1}^{V} \exp(z_j)$—presents a significant computational challenge. Computing this sum requires iterating over the entire vocabulary at every prediction step. For vocabulary sizes in the tens or hundreds of thousands, this computational cost accumulates rapidly during both training and inference. This challenge motivates the approximation techniques discussed in later chapters, including hierarchical softmax, noise contrastive estimation, and approximate softmax methods.

Training Objective: Maximum Likelihood Estimation

Given a corpus of text—say, a collection of documents, books, or web pages—we can train a language model by maximizing the likelihood of the training data under our model. If we have a training corpus consisting of token sequences $\mathcal{D} = \{w_1^{(d)}, w_2^{