# Language Generation: Complexity Barriers and Implications for Learning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 23 references that are in the map.
- First posted on arXiv 7 Nov 2025.

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

- [Why Language Models Hallucinate](https://mlsanity.com/paper/2509.04664/) (2025)
- [Calibrated Language Models Must Hallucinate](https://mlsanity.com/paper/2311.14648/) (2023)
- [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)
- [Density Measures for Language Generation](https://mlsanity.com/paper/2504.14370/) (2025)
- [Generation from Noisy Examples](https://mlsanity.com/paper/2501.04179/) (2025)
- [Representative Language Generation](https://mlsanity.com/paper/2505.21819/) (2025)
- [On Union-Closedness of Language Generation](https://mlsanity.com/paper/2506.18642/) (2025)
- [(Im)possibility of Automated Hallucination Detection in Large Language Models](https://mlsanity.com/paper/2504.17004/) (2025)

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

- [Mistake-Bounded Language Generation](https://mlsanity.com/paper/2605.10809/) (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)
- [Differentially Private Language Generation and Identification in the Limit](https://mlsanity.com/paper/2604.08504/) (2026)
- [On Language Generation in the Limit with Bounded Memory](https://mlsanity.com/paper/2605.30324/) (2026)
- [Polynomial-Time Mistake-Bounded Language Generation](https://mlsanity.com/paper/2606.16077/) (2026)
- [Why Code, Why Now: An Information-Theoretic Perspective on the Limits of Machine Learning](https://mlsanity.com/paper/2602.13934/) (2026)
- [Hallucination Rates in Language Generation](https://mlsanity.com/paper/2607.23361/) (2026)

## Abstract (arXiv)

Kleinberg and Mullainathan showed that language generation in the limit is always possible at the level of computability: given enough positive examples, a learner can eventually generate data indistinguishable from a target language. However, such existence results do not address feasibility. We study the sample complexity of language generation in the limit for several canonical classes of formal languages. Our results show that infeasibility already appears for context-free and regular languages, and persists even for strict subclasses such as locally threshold testable languages, as well as for incomparable classes such as non-erasing pattern languages, a well-studied class in the theory of language identification. Overall, our results establish a clear gap between the theoretical possibility of language generation in the limit and its computational feasibility.