Uploaded October 2026 | Updated November 2026, 3 days ago
Debmalya Panigrahi (Duke University)
https://simons.berkeley.edu/talks/debmalya-panigrahi-duke-university-2026-10-05
Trustworthy AI: From Hallucinations to Reliable Autonomy
Language generation in the limit provides an elegant framework for studying the algorithmic problem of generating unseen valid strings from an unknown target language given example strings from that language. In the original formulation of Kleinberg and Mullainathan and nearly all subsequent work, all errors made by the language generator must be confined to a finite prefix of its infinite output. This contrasts with our experience with modern language models which repeatedly hallucinate in practice.
We study the complementary setting in which the language generator may hallucinate infinitely often and investigate how the rate of hallucination affects the class of languages that can be generated. We show that some language collections cannot be generated with finitely many hallucinations but can be generated with infinitely many, even when the hallucinations form a measure-zero subset of the output. More generally, we establish a strict hierarchy of (uncountable) language collections characterized by hallucination rate. This hierarchy also extends to the width of language generation, i.e., the fraction of the target language generated. These results identify hallucination rate as a fundamental parameter in the theory of language generation.
This talk is based on joint work with Fan Wei and Ian Zhang.
Debmalya Panigrahi (Duke University)
https://simons.berkeley.edu/talks/debmalya-panigrahi-duke-university-2026-10-05
Trustworthy AI: From Hallucinations to Reliable Autonomy
Language generation in the limit provides an elegant framework for studying the algorithmic problem of generating unseen valid strings from an unknown target language given example strings from that language. In the original formulation of Kleinberg and Mullainathan and nearly all subsequent work, all errors made by the language generator must be confined to a finite prefix of its infinite output. This contrasts with our experience with modern language models which repeatedly hallucinate in practice.
We study the complementary setting in which the language generator may hallucinate infinitely often and investigate how the rate of hallucination affects the class of languages that can be generated. We show that some language collections cannot be generated with finitely many hallucinations but can be generated with infinitely many, even when the hallucinations form a measure-zero subset of the output. More generally, we establish a strict hierarchy of (uncountable) language collections characterized by hallucination rate. This hierarchy also extends to the width of language generation, i.e., the fraction of the target language generated. These results identify hallucination rate as a fundamental parameter in the theory of language generation.
This talk is based on joint work with Fan Wei and Ian Zhang.










