Hallucination Rates in Language Generation @SimonsInstitute
Hallucination Rates in Language Generation  @SimonsInstitute
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.
Hallucination Rates in Language GenerationExplicit Almost-Optimal ε-Balanced Codes via Free Expander WalksKikuchi Graphs: A Spectral Method for HypergraphsA survey on PIT for read-once algebraic branching programsNew directions in catalytic derandomizationPolar Codes IFourier quasicrystals from stable polynomials and beyondAlgebraic Geometry and Discrete Periodic OperatorsFinite free information inequalitiesCompressed timestamps and efficient random walks in catalytic spaceRandom unitary circuits with constant spectral gapFrom local discrete curvature notions of graphs to global properties of the underlying spaces
Simons Institute for the Theory of Computing |

Hallucination Rates in Language Generation

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER