# Generation from Noisy Examples

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

## Key facts

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

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

- [Transformers in Vision: A Survey](https://mlsanity.com/paper/2101.01169/) (2021)
- [Weak-to-Strong Generalization: Eliciting Strong Capabilities With Weak Supervision](https://mlsanity.com/paper/2312.09390/) (2023)
- [Large Language Models Suffer From Their Own Output: An Analysis of the Self-Consuming Training Loop](https://mlsanity.com/paper/2311.16822/) (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)
- [Exploring Facets of Language Generation in the Limit](https://mlsanity.com/paper/2411.15364/) (2024)
- [On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability](https://mlsanity.com/paper/2412.18530/) (2024)
- [Forcing Generative Models to Degenerate Ones: The Power of Data Poisoning Attacks](https://mlsanity.com/paper/2312.04748/) (2023)
- [Robust Generative Adversarial Network](https://mlsanity.com/paper/2004.13344/) (2020)

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

- [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)
- [(Im)possibility of Automated Hallucination Detection in Large Language Models](https://mlsanity.com/paper/2504.17004/) (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)
- [Characterizing the Effect of Noise in Language Generation in the Limit](https://mlsanity.com/paper/2601.21237/) (2026)
- [Agnostic Language Identification and Generation](https://mlsanity.com/paper/2601.23258/) (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)
- [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)
- [Space-Efficient Language Generation in the Limit](https://mlsanity.com/paper/2606.25777/) (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)

We continue to study the learning-theoretic foundations of generation by extending the results from Kleinberg and Mullainathan [2024] and Li et al. [2024] to account for noisy example streams. In the noiseless setting of Kleinberg and Mullainathan [2024] and Li et al. [2024], an adversary picks a hypothesis from a binary hypothesis class and provides a generator with a sequence of its positive examples. The goal of the generator is to eventually output new, unseen positive examples. In the noisy setting, an adversary still picks a hypothesis and a sequence of its positive examples. But, before presenting the stream to the generator, the adversary inserts a finite number of negative examples. Unaware of which examples are noisy, the goal of the generator is to still eventually output new, unseen positive examples. In this paper, we provide necessary and sufficient conditions for when a binary hypothesis class can be noisily generatable. We provide such conditions with respect to various constraints on the number of distinct examples that need to be seen before perfect generation of positive examples. Interestingly, for finite and countable classes we show that generatability is largely unaffected by the presence of a finite number of noisy examples.