Generating in the Limit with Infinitely Many Hallucinations
For theoretical computer science and language modeling, this work provides a more realistic model of language generation where occasional errors and repetitions are unavoidable but controlled.
This paper extends the language generation in the limit framework to allow infinitely many hallucinations (invalid strings) as long as their frequency tends to zero, showing that this relaxation can strictly increase recall when the adversary withholds a large portion of the target language. It also studies a continuous relaxation of the novelty constraint requiring only a fixed fraction of outputs to be novel.
The classic paradigm of language identification in the limit models learning as a game between an adversary, who reveals strings from an unknown target language, and a learner tasked with identifying that language. The recently introduced framework of language generation in the limit shifted the objective to better reflect modern language modeling, requiring the learner to produce valid, unseen strings from the target language. Related work highlighted a fundamental tension: a broad coverage of the target often comes at the cost of validity. We introduce a new notion of precision and recast this problem as the classic recall-precision trade-off. We analyze generation in the limit under varying constraints on enumeration, novelty, and validity, aimed at reflecting settings closer to those encountered by large language models. A key contribution is our analysis of learners that are not eventually valid: we allow infinitely many mistakes, provided their frequency tends to zero so that precision remains one. We show that this relaxation can strictly increase recall when the adversary permanently withholds a large portion of the target language. We also study a continuous relaxation of the novelty constraint that requires only a fixed fraction of outputs to be novel. Taken together, our results move toward a more realistic model of language generation where occasional errors and repetitions are unavoidable, but their rates are controlled.