Language Generation with Infinite Contamination

A recent line of work studies language generation in the limit, a formal model of language learning where an algorithm observes an adversarially generated enumeration of strings from an unknown target language $K$ and must eventually generate new, unseen strings from $K$. In this model, Kleinberg and Mullainathan (2024) proved that generation is achievable in surprisingly general settings; whenever $K$ belongs to a known countable collection of languages. However, their generator, while quite general, suffers from “mode collapse:” it generates from an ever-smaller subset of the target. To address this, Kleinberg and Wei (2025a) introduced a stronger notion of dense generation, requiring the output to asymptotically cover a positive fraction of the target, and showed it remains achievable for all countable collections. Both of these works rely on the crucial assumption of \textit{perfect} data: the adversary can neither insert strings from outside the target language (i.e., noise) nor omit strings from it (i.e., omissions). In practice, training data for language models is notoriously noisy, raising the fundamental question: \begin{center} \emph{How much contamination (either omissions or insertions) can language generation tolerate?} \end{center} Recent works have made partial progress on this question by studying (non-dense) generation with either finite amounts of noise (but no omissions) (Raman and Raman, 2025) or omissions (but no noise) (Bai et al., 2026). We characterize the contamination tolerance of both types of generation by proving the following results: \begin{itemize} \item \textbf{Generation under Contamination:} Language generation in the limit is achievable for all countable collections if and only if the fraction of contaminated examples converges to zero. When this condition fails, we characterize the collections which remain generable. \item \textbf{Dense Generation under Contamination:} Dense generation is achievable for all countable collections