# On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability

arXiv: https://arxiv.org/abs/2412.18530 · HTML: https://mlsanity.com/paper/2412.18530/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 18 references that are in the map.
- First posted on arXiv 24 Dec 2024.

## Builds on (most cited first, 5 of 5)

- [Towards Principled Methods for Training Generative Adversarial Networks](https://mlsanity.com/paper/1701.04862/) (2017)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Language Generation in the Limit](https://mlsanity.com/paper/2404.06757/) (2024)
- [Generation through the lens of learning theory](https://mlsanity.com/paper/2410.13714/) (2024)
- [Exploring Facets of Language Generation in the Limit](https://mlsanity.com/paper/2411.15364/) (2024)

## Built on by (most cited first, 14 of 14)

- [Generation from Noisy Examples](https://mlsanity.com/paper/2501.04179/) (2025)
- [Representative Language Generation](https://mlsanity.com/paper/2505.21819/) (2025)
- [Language Generation in the Limit: Noise, Loss, and Feedback](https://mlsanity.com/paper/2507.15319/) (2025)
- [Language Generation with Replay: A Learning-Theoretic View of Model Collapse](https://mlsanity.com/paper/2603.11784/) (2026)
- [Characterizing the Effect of Noise in Language Generation in the Limit](https://mlsanity.com/paper/2601.21237/) (2026)
- [Contrastive Identification and Generation in the Limit](https://mlsanity.com/paper/2605.06211/) (2026)
- [On the Price of Privacy for Language Identification and Generation](https://mlsanity.com/paper/2604.07238/) (2026)
- [A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse](https://mlsanity.com/paper/2605.11302/) (2026)
- [On Language Generation in the Limit with Bounded Memory](https://mlsanity.com/paper/2605.30324/) (2026)
- [The Homogenization Problem in LLMs: Towards Meaningful Diversity in AI Safety](https://mlsanity.com/paper/2601.06116/) (2026)
- [Generating in the Limit with Infinitely Many Hallucinations](https://mlsanity.com/paper/2606.28354/) (2026)
- [Hallucination Rates in Language Generation](https://mlsanity.com/paper/2607.23361/) (2026)
- [GenLimitLib: A Formal Library for Language Generation in the Limit and AI-Assisted Mathematical Research](https://mlsanity.com/paper/2609.36663/) (2026)
- [Tracing and Taming Hallucinated Terms via Subsequence-Association Filtering and Breadth-Aware Selection for LLM Query Expansion](https://mlsanity.com/paper/2610.13810/) (2026)

## Abstract (arXiv)

We study language generation in the limit - introduced by Kleinberg and Mullainathan [KM24] - building on classical works of Gold [Gol67] and Angluin [Ang79]. [KM24]'s main result is an algorithm for generating from any countable language collection in the limit. While their algorithm eventually generates unseen strings from the target language K, it sacrifices coverage or breadth, i.e., its ability to generate a rich set of strings. Recent work introduces different notions of breadth and explores when generation with breadth is possible, leaving a full characterization of these notions open. Our first set of results settles this by characterizing generation for existing notions of breadth and their natural extensions. Interestingly, our lower bounds are very flexible and hold for many performance metrics beyond breadth - for instance, showing that, in general, it is impossible to train generators which achieve a higher perplexity or lower hallucination rate for K compared to other languages. Next, we study language generation with breadth and stable generators - algorithms that eventually stop changing after seeing an arbitrary but finite number of strings - and prove unconditional lower bounds for such generators, strengthening the results of [KMV25] and demonstrating that generation with many existing notions of breadth becomes equally hard, when stability is required. This gives a separation for generation with approximate breadth, between stable and unstable generators, highlighting the rich interplay between breadth, stability, and consistency in language generation.