Abstract
We study language generation in the limit, where an algorithm observes anadversarial enumeration of strings from an unknown target language $K$ and musteventually generate new, unseen strings from $K$. Kleinberg and Mullainathan[KM24] proved that generation is achievable in surprisingly general settings.But their generator suffers from ``mode collapse,'' producing from anever-smaller subset of the target. To address this, Kleinberg and Wei [KW25]require the generator's output to be ``dense'' in the target language. Theyshowed that generation with density, surprisingly, remains achievable at thesame generality. Both results assume perfect data: no noisy insertions and no omissions. Thisraises a central question: how much contamination can generation tolerate?Recent works made partial progress on this question by studying (non-dense)generation with either finite amounts of noise (but no omissions) or omissions(but no noise). We characterize robustness under contaminated enumerations: 1. Generationunder Contamination: Language generation in the limit is achievable for allcountable collections iff the fraction of contaminated examples converges tozero. When this fails, we characterize which collections are generable. 2.Dense Generation under Contamination: Dense generation is strictly less robustto contamination than generation. As a byproduct, we resolve an open questionof Raman and Raman [ICML25] by showing that generation is possible with onlymembership oracle access under finitely many contaminated examples. Finally, we introduce a beyond-worst-case model inspired by curriculumlearning and prove that dense generation is achievable even with infinitecontamination provided the fraction of contaminated examples converges to zero.This suggests curriculum learning may be crucial for learning from noisy webdata.