Introduction
Large Language Models (LLMs) are defined by a dual nature: their remarkable creative range and their propensity for "hallucinations"—the generation of invalid or factually incorrect outputs. In 2024, Kleinberg and Mullainathan [KM24] formalized this phenomenon within a "generation in the limit" framework, building on the classical learning theory of Gold [Gol67] and Angluin [Ang79]. They demonstrated that it is mathematically possible to construct a generator that eventually ceases to hallucinate for any countable collection of languages.
However, the KM24 algorithm achieved consistency at the cost of breadth. To avoid hallucinations, the model became extremely conservative, eventually outputting only a narrow subset of the target language—a theoretical version of "mode collapse." This research addresses the fundamental trade-off between consistency (avoiding hallucinations) and breadth (ensuring diversity), while introducing the critical dimension of stability.
Theoretical Framework: Generation in the Limit
The study utilizes a formal game-theoretic model. An adversary provides a generator with a stream of strings from an unknown target language $K$ belonging to a known collection $\mathcal{L}$. The generator’s task is to eventually produce new, unseen strings that are also members of $K$.
To analyze the limits of this process, the authors introduce several novel theoretical tools:
- Weak Angluin’s Condition: A relaxation of the classic 1980s condition for language identification. This new condition allows languages that differ only by a finite number of strings to be treated as equivalent for the purposes of generation.
- Universal Diagonalization: A proof technique used to demonstrate that if a language collection lacks specific structural properties, no algorithm can achieve high breadth without eventually hallucinating.
- Lazy Analysis of Diagonalization: A specialized technique for handling stable generators, where the proof must account for the model's behavior over an infinite time horizon.
Key Concepts and Definitions
The paper categorizes generation based on the relationship between the output set and the target language:
- Exact Breadth: The generator eventually outputs every valid string in the target language.
- Approximate Breadth: The generator outputs all but a finite number of strings in the target language.
- Stability: A generator is stable if it eventually stops changing its internal "support" (the set of strings it is capable of generating).
Main Results
The Equivalence of Breadth and Identification
The authors provide a complete characterization of what is required to achieve different levels of breadth. The most significant finding is that achieving Exact Breadth is mathematically equivalent to the task of Language Identification.
Theorem 3.3: A generator can achieve Exact Breadth if and only if the language collection satisfies Angluin’s Condition.
This implies that for many complex language families (such as regular languages), generating the entire language without hallucinations is impossible, as they do not satisfy Angluin's condition for identification from positive examples.
The "Approximate" Loophole
If the requirement is relaxed to Approximate Breadth—allowing the model to miss a finite number of valid strings—the task becomes significantly easier. This level of generation is characterized by the authors' newly defined Weak Angluin’s Condition (Theorem 3.8). This suggests that "near-perfect" diversity is achievable for a broader class of languages than perfect diversity.
The Impact of Stability
A pivotal contribution of this work is the analysis of Stable Generators. The authors show that when a generator is required to be stable, the distinction between exact and approximate breadth disappears.
Theorem 3.15: For stable generators, both exact and approximate breadth require the full Angluin’s Condition.
This result reveals a fundamental separation: while unstable generators can exploit the "approximate loophole," stable generators are bound by the stricter requirements of perfect identification. This suggests that the requirement for a model to "settle down" and stop shifting its output distribution significantly increases the difficulty of the generation task.
Conclusion and Future Directions
This research provides a comprehensive taxonomy of language generation, mapping the boundaries between hallucinations, stability, and coverage. It proves that while generating some valid text is feasible, generating a diverse range of valid text is a high-order difficulty task that often requires solving the problem of perfect language identification.
Future work remains in extending these characterizations to uncountable collections of languages and exploring the role of negative examples (informing the model what is not in the language). Additionally, while this work focuses on the "in the limit" setting, the authors have begun extending these results to statistical settings, showing that for non-identifiable languages, no error rate faster than $e^{-n}$ is achievable.
Summary updated