# Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations

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

## Key facts

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

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

- [Towards Principled Methods for Training Generative Adversarial Networks](https://mlsanity.com/paper/1701.04862/) (2017)
- [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)
- [Physics of Language Models: Part 1, Learning Hierarchical Language Structures](https://mlsanity.com/paper/2305.13673/) (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)
- [Density Measures for Language Generation](https://mlsanity.com/paper/2504.14370/) (2025)
- [Generation from Noisy Examples](https://mlsanity.com/paper/2501.04179/) (2025)
- [ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Models](https://mlsanity.com/paper/2405.09220/) (2024)
- [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)

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

- [Safe Language Generation in the Limit](https://mlsanity.com/paper/2601.08648/) (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)
- [Differentially Private Language Generation and Identification in the Limit](https://mlsanity.com/paper/2604.08504/) (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)
- [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 success of large language models (LLMs) has motivated formal theories of language generation and learning. We study the framework of language generation in the limit, where an adversary enumerates strings from an unknown language K drawn from a countable class, and an algorithm must generate unseen strings from K. Prior work showed that generation is always possible, and that some algorithms achieve positive lower density, revealing a validity--breadth trade-off between correctness and coverage. We resolve a main open question in this line, proving a tight bound of 1/2 on the best achievable lower density. We then strengthen the model to allow partial enumeration, where the adversary reveals only an infinite subset C subseteq K. We show that generation in the limit remains achievable, and if C has lower density α in K, the algorithm's output achieves density at least α/2, matching the upper bound. This generalizes the 1/2 bound to the partial-information setting, where the generator must recover within a factor 1/2 of the revealed subset's density. We further revisit the classical Gold--Angluin model of language identification under partial enumeration. We characterize when identification in the limit is possible -- when hypotheses Mt eventually satisfy C subseteq M subseteq K -- and in the process give a new topological formulation of Angluin's characterization, showing that her condition is precisely equivalent to an appropriate topological space having the TD separation property.