Pre-Transformer Sequence Modeling: Foundations and Limitations

Sequence modeling has served as the cornerstone of natural language processing (NLP) for over half a century, evolving from hand-engineered statistical models to end-to-end neural architectures. Before the 2017 introduction of the Transformer architecture, the field relied on a series of iterative innovations in recurrent and encoder-decoder designs, each addressing critical limitations of its predecessors while laying the technical groundwork for the self-attention mechanisms that would later revolutionize large language models. This chapter systematically traces this evolutionary path, from n-gram statistical models to attention-augmented sequence-to-sequence (Seq2Seq) systems, with rigorous mathematical derivations, implementation examples, and empirical performance comparisons on the WikiText-2 benchmark[^1] to highlight both the progress and inherent constraints of pre-Transformer sequence modeling.

Statistical Language Models: The N-gram Foundation

The earliest formalized sequence models for NLP were n-gram statistical language models, built on the Markov assumption that the probability of a word depends only on the preceding $n-1$ words. For a sequence of tokens $w_1, w_2, ..., w_T$, the joint probability is factorized as: $$P(w_1, w_2, ..., w_T) = \prod_{t=1}^T P(w_t | w_{t-n+1}, w_{t-n+2}, ..., w_{t-1})$$ where $n$ is the order of the n-gram model, and $w_{t-n+1}^{t-1}$ denotes the context window of the preceding $n-1$ tokens. Parameters are estimated via maximum likelihood estimation (MLE): $$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})}$$ where $C(\cdot)$ counts the frequency of the n-gram in the training corpus.

A critical challenge for n-gram models is the zero-probability problem: any n-gram unseen in the training data will be assigned a probability of 0, leading to infinite perplexity on test sets. This is addressed via smoothing techniques, the most widely used being Kneser-Ney smoothing, which interpolates between higher-order and lower-order n-gram probabilities while discounting frequent n-grams to allocate probability mass to unseen sequences: $$P_{\text{KN}}(w_t | w_{t-n+1}^{t-1}) = \frac{\max\left(C(w_{t-n+1}^t) - \delta, 0\right)}{C(w_{t-n+1}^{t-1})} + \lambda(w_{t-n+1}^{t-1}) P_{\text{KN-1}}(w_t | w_{t-n+2}^{t-1})$$ where $\delta$ is a discount parameter (typically 0.75) and $\lambda(\cdot)$ is a normalization constant.

Despite their simplicity, n-gram models suffer from two fundamental limitations that prevent them from scaling to real-world NLP tasks. First, the Markov assumption imposes a hard limit on the length of dependencies that can be modeled: a 5-gram model can only capture relationships between tokens up to 4 positions apart. For example, in the sentence *“The researchers who published the 2024 climate study concluded that sea levels will rise by 0.8 meters by 2100 unless emissions are cut by 45% before 2030”*, a 5-gram model cannot associate the subject *“The researchers”* with the verb *“concluded”* 24 tokens later, or link *“sea levels”* to *“rise”* 6 tokens later. Second, the curse of dimensionality makes n-gram models infeasible for large vocabularies: a 5-gram model with a 100k token vocabulary requires storing up to $(10^5)^5 = 10^{25}$ possible n-grams, far exceeding the capacity of any modern storage system.

Empirically, a 5-gram model with Kneser-Ney smoothing trained on WikiText-2 achieves a test perplexity[^2] of 182.3, a baseline that later neural models will drastically improve upon. A minimal implementation of a 5-gram model for text generation is shown below, using backoff smoothing for simplicity: ```python from collections import defaultdict, Counter

class NGramModel: def __init__(self, n=5): self.n = n self.ngram_counts = defaultdict(Counter) self.context_counts = defaultdict(int)

def train(self, corpus): for sentence in corpus: tokens = ["<s>"] * (self.n - 1) + sentence + ["</s>"] for i in range(len(tokens) - self.n + 1): context = tuple(tokens[i:i+self.n-1]) target = tokens[i+self.n-1] self.ngram_counts[context][target] += 1 self.context_counts[context] += 1

def generate(self, context, max_len=50): output = list(context) for _ in range(max_len): ctx = tuple(output[-(self.n-1):]) if ctx not in self.ngram_counts or sum(self.ngram_counts[ctx].values()) == 0:

Backoff to lower-order n-gram

ctx = ctx[1:] if len(ctx) > 1 else () if not ctx: break total = sum(self.ngram_counts[ctx].values()) probs = {w: c/total for w, c in self.ngram_counts[ctx].items()} next_token = max(probs, key=probs.get) output.append(next_token) if next_token == "</s>": break return output ``` When generating text with the prompt *“The cat sat on the”*, the 5-gram model outputs *“mat.”* but fails to generate coherent longer continuations, as it cannot generalize to unseen n-gram combinations that share semantic meaning with training examples.

> 💡 Sidebar: The Curse of Dimensionality in Practice > For context, even a small 3-gram model trained on a 10k token vocabulary requires storing up to $10^{12}$ n-gram counts, which would take ~4TB of storage using 32-bit integers. This is why n-gram models were never feasible for large-scale open-domain language modeling, even before the rise of neural alternatives.

Recurrent Neural Networks: Breaking the Markov Limit

Recurrent Neural Networks (RNNs) emerged in the 1980s as a neural alternative to n-gram models, designed explicitly to model sequential data by maintaining a hidden state that evolves over time. Unlike feedforward networks, RNNs share parameters across all time steps, allowing them to process sequences of arbitrary length and capture dependencies beyond the fixed window of n-gram models.

The core computation of a vanilla RNN at time step $t$ is defined as: $$h_t = \phi(W_{hh} h_{t-1} + W_{hx} x_t + b_h)$$ $$y_t = W_{hy} h_t + b_y$$ where $x_t$ is the input token embedding at time $t$, $h_t$ is the hidden state, $y_t$ is the output, $W_{hh}, W_{hx}, W_{hy}$ are shared weight matrices, $b_h, b_y$ are bias terms, and $\phi$ is a non-linear activation function (typically $\tanh$ or ReLU). To train RNNs, we use Backpropagation Through Time (BPTT), which unrolls the RNN across all time steps of the input sequence and applies standard backpropagation to the unrolled deep network.

The critical flaw of vanilla RNNs is the vanishing/exploding gradient problem, which arises from the chain rule applied during BPTT. For a loss function $L$ (typically cross-entropy for language modeling), the gradient of the loss with respect to the hidden state at time $t-1$ is: $$\frac{\partial L}{\partial h_{t-1}} = \frac{\partial L}{\partial h_t} \cdot \text{diag}\left(\phi'(W_{hh} h_{t-1} + W_{hx} x_t)\right) \cdot W_{hh}$$ Unrolling this across $T$ time steps, the gradient of the loss with respect to the initial hidden state $h_0$ is a product of $T$ Jacobian matrices: $$\frac{\partial L}{\partial h_0} = \frac{\partial L}{\partial h_T} \cdot \prod_{k=1}^T \left( \text{diag}\left(\phi'(W_{hh} h_{k-1} + W_{hx} x_k)\right) \cdot W_{hh} \right)$$ If the spectral radius (maximum absolute eigenvalue) of $W_{hh}$ is less than 1, the product will decay exponentially to 0 as $T$ increases, leading to

vanilla RNN's gradient dynamics create a hard ceiling on sequence length that can be effectively modeled. When the spectral radius of the recurrent weight matrix $W_{hh}$ is less than 1, the product of Jacobian matrices during backpropagation through time (BPTT) decays exponentially: for a sequence of length $T=100$, a per-time-step gradient scaling factor of 0.9 reduces the gradient at the first time step to $0.9^{99} \approx