Characterizing the Effect of Noise in Language Generation in the Limit

Kleinberg and Mullainathan recently proposed a formal framework for studying the phenomenon of language generation, called language generation in the limit. In this model, an adversary gives an enumeration of example strings from an unknown target language, and the algorithm is tasked with correctly generating unseen strings from the target language within finite time. Refined notions of non-uniform and uniform generation were later introduced by Li, Raman, and Tewari (2025), and a noisy model was introduced by Raman and Raman (2025), which allows the adversary to insert extraneous strings. A natural question in the noisy model is to quantify the effect of noise, by studying the impact of each additional extraneous string. We show two complementary results in this setting. We first show that for both uniform and non-uniform generation, a single noisy string strictly reduces the set of collections that can be generated, thus answering an open question in Raman and Raman (2025). Then, we show for both uniform and non-uniform generation that generation with a single noisy string is equivalent to generation with any finite amount of noise, sharply contrasting with the strict hierarchy for noisy generation in the limit shown by Bai, Panigrahi, and Zhang (2026). Finally, we leverage our previous results to provide the first known characterization for non-uniform noise-dependent generatability.

We study the problem of language generation through a formal model that was recently introduced by Kleinberg and Mullainathan. This model captures the fundamental essence of language generation by abstracting the problem into an interaction between an adversary that presents data in the form of examples, and an algorithm that sees the data and tries to eventually generate new correct text based on the data. Within this framework, we specifically investigate the effect of noisy data on the abilities of the algorithm to generate correctly. We show that under certain settings, whether or not noise is present affects the algorithm’s generation abilities, but the specific amount of noise does not. Under the same settings, we also completely characterize when an algorithm can generate correctly with noise.