# Density Measures for Language Generation arXiv: https://arxiv.org/abs/2504.14370 ยท HTML: https://mlsanity.com/paper/2504.14370/ ## Key facts - Cited by 21 papers in the map (data through 14 Oct 2026). - Builds on 10 of its 24 references that are in the map. - First posted on arXiv 19 Apr 2025. ## Builds on (most cited first, 10 of 10) - [Towards Principled Methods for Training Generative Adversarial Networks](https://mlsanity.com/paper/1701.04862/) (2017) - [Hallucination is Inevitable: An Innate Limitation of Large Language Models](https://mlsanity.com/paper/2401.11817/) (2024) - [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021) - [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023) - [Calibrated Language Models Must Hallucinate](https://mlsanity.com/paper/2311.14648/) (2023) - [On Limitations of the Transformer Architecture](https://mlsanity.com/paper/2402.08164/) (2024) - [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) - [ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Models](https://mlsanity.com/paper/2405.09220/) (2024) ## Built on by (most cited first, 21 of 21) - [On Union-Closedness of Language Generation](https://mlsanity.com/paper/2506.18642/) (2025) - [Language Generation in the Limit: Noise, Loss, and Feedback](https://mlsanity.com/paper/2507.15319/) (2025) - [Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations](https://mlsanity.com/paper/2511.05295/) (2025) - [Pareto-optimal Non-uniform Language Generation](https://mlsanity.com/paper/2510.02795/) (2025) - [Language Generation: Complexity Barriers and Implications for Learning](https://mlsanity.com/paper/2511.05759/) (2025) - [Safe Language Generation in the Limit](https://mlsanity.com/paper/2601.08648/) (2026) - [Language Generation with Replay: A Learning-Theoretic View of Model Collapse](https://mlsanity.com/paper/2603.11784/) (2026) - [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) - [On Generation in Metric Spaces](https://mlsanity.com/paper/2602.07710/) (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) - [Flood and Harvest: The Provable Necessity of Trivia for Generating Valuable Mathematics via the Lens of Language Generation in the Limit](https://mlsanity.com/paper/2606.14688/) (2026) - [Polynomial-Time Mistake-Bounded Language Generation](https://mlsanity.com/paper/2606.16077/) (2026) - [Space-Efficient Language Generation in the Limit](https://mlsanity.com/paper/2606.25777/) (2026) - [Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy](https://mlsanity.com/paper/2609.10525/) (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) ## Abstract (arXiv) The recent successes of large language models (LLMs) have led to a surge of theoretical research into language generation. A recent line of work proposes an abstract view, called language generation in the limit, where generation is seen as a game between an adversary and an algorithm: the adversary generates strings from an unknown language K, chosen from a countable collection of candidate languages, and after seeing a finite set of these strings, the algorithm must generate new strings from K that it has not seen before. This formalism highlights a key tension: the trade-off between validity (the algorithm should only produce strings from the language) and breadth (it should be able to produce many strings from the language). This trade-off is central in applied language generation as well, where it appears as a balance between hallucination (generating invalid utterances) and mode collapse (generating only a restricted set of outputs). Despite its importance, this trade-off has been challenging to study quantitatively. We develop ways to quantify this trade-off by formalizing breadth using measures of density. Existing algorithms for language generation in the limit produce output sets that can have zero density in the true language, and this important failure of breadth might seem unavoidable. We show, however, that such a failure is not necessary: we provide an algorithm for language generation in the limit whose outputs have strictly positive density in K. We also study the internal representations built by these algorithms, specifically the sequence of hypothesized candidate languages they consider, and show that achieving the strongest form of breadth may require oscillating indefinitely between high- and low-density representations. Our analysis introduces a novel topology on language families, with notions of convergence and limit points playing a key role.