Abstract: Large language models have become one of the most commonly deployed NLP inventions. In the past half-decade, their integration into core natural language processing tools has dramatically increased the performance of such tools, and they have entered the public discourse surrounding artificial intelligence. Consequently, it is important for both developers and researchers alike to understand the mathematical foundations of large language models, as well as how to implement them. These notes are the accompaniment to the theoretical portion of the ETH Zürich course on large language models, covering what constitutes a language model from a formal, theoretical perspective.
Introduction
In the current "gold rush" of Large Language Models (LLMs), focus often gravitates toward empirical scaling: increasing parameter counts, dataset sizes, and compute budgets. However, beneath the surface of architectures like GPT-4 or Claude lies a complex mathematical structure. Formal Aspects of Language Modeling provides a rigorous, measure-theoretic foundation for the field, bridging the gap between empirical deep learning and formal language theory.
Theoretical Framework
The work addresses the lack of mathematical rigor in common LLM discourse. A primary concern is tightness: whether a model that predicts tokens sequentially represents a valid probability distribution over finite strings. If a model predicts the next word indefinitely without a guaranteed termination, it may "leak" probability mass to infinite sequences, rendering it mathematically invalid as a distribution over a finite vocabulary space.
To analyze these properties, the authors employ:
- Measure Theory: Utilizing $\sigma$-algebras and Carathéodory’s Extension Theorem to define probability measures over the space of all possible strings.
- Automata Theory: Comparing neural architectures to classical machines such as Finite-State Automata (FSA) and Pushdown Automata (PDA).
- Minsky’s Construction: Demonstrating how neural networks can simulate the states and transitions of formal machines.
- Tightness Analysis: Applying Borel-Cantelli lemmata to derive conditions under which locally normalized models (like autoregressive LLMs) are guaranteed to terminate.
Representational Capacity and Computational Limits
A central question in this formalization is the representational capacity of specific architectures—defining what patterns a model can theoretically learn.
RNNs and Finite-State Automata
The analysis reveals that under the constraints of finite-precision arithmetic, Recurrent Neural Networks (RNNs) are essentially compact FSAs. However, with theoretical infinite precision, RNNs are shown to be Turing complete, capable of simulating any standard computer.
The Transformer Architecture
Transformers present unique theoretical challenges. Being inherently "position-agnostic," they require positional encodings to recognize even basic regular languages. Without these, they cannot distinguish between permutations of the same token set (e.g., "The dog bit the man" vs. "The man bit the dog"). The paper demonstrates that while Transformers can be powerful, they require specific configurations, such as averaging hard attention, to reach higher levels of the Chomsky hierarchy.
The Decidability Gap
A significant theoretical result involves the connection to the Halting Problem. The authors prove that determining if a general, rational-weighted RNN is "tight" is undecidable. This implies there is no universal algorithm to verify if every possible RNN configuration will eventually stop generating tokens.
Key Results
- Equivalence Proofs: The text formalizes the conversion of globally normalized (energy-based) models with finite partition functions into locally normalized models.
- Softmax Tightness: Theorem 5.3.2 proves that any fixed-depth Transformer utilizing soft attention is inherently "tight," ensuring it defines a valid probability distribution over finite strings.
- Capacity Mapping: The work maps neural architectures against the Chomsky hierarchy, providing a roadmap for understanding the computational limits of modern NLP tools.
Conclusion and Future Directions
While providing a robust theoretical base, the authors acknowledge the gap between mathematical theory and empirical practice. Real-world models operate with limited precision (e.g., 16-bit floats), which constrains their theoretical Turing completeness. Furthermore, much of the current analysis relies on "Hard Attention" or "Heaviside" activations to facilitate proofs. Extending this level of rigor to the "soft" continuous functions used in production environments remains a critical area for future research.
Summary updated