A persistent tension in theoretical accounts of language generation is that validity and coverage pull in opposite directions. A learner that never produces invalid strings can do so by generating from an arbitrarily small subset of the target language, sacrificing coverage entirely. Conversely, aggressive coverage risks outputting strings outside the target. This paper, available on arXiv, formalises that tension using the classic information-theoretic machinery of recall and precision, and asks what happens when we allow a learner to hallucinate, provided the hallucination rate decays to zero asymptotically.
The work builds directly on the language generation in the limit framework introduced by Kleinberg and Mullainathan (2024), which shifted the objective of the Gold-Angluin identification paradigm from identifying a target language to producing valid, previously unseen strings from it. That framework established tractability for any countable collection of languages, but left coverage largely unaddressed. Subsequent work by Charikar and Pabbaraju (2025) and Kalavasis et al. (2025) showed that full coverage is as hard as identification, and Kleinberg and Wei (2025b) gave partial-enumeration recall bounds of alpha/2 when the adversary reveals a fraction alpha of the target. The present paper asks whether those bounds can be improved, and under what conditions.
Key Contributions
The paper makes three conceptually distinct contributions, each addressing a different axis of the generation problem.
- Precision as a first-class metric. Because standard precision and recall are ill-defined for infinite sets, the authors define them via exhaustions: sequences of finite sets approximating an infinite language. This yields well-behaved asymptotic analogues. They also introduce tail precision, which formalises eventual validity as the finite-time stabilisation of precision to one. This is a cleaner operationalisation than the informal notion used in earlier work.
- Relaxed tail precision and the hallucination dividend. The central technical result shows that allowing infinitely many invalid outputs, provided their frequency tends to zero, can strictly increase recall when the adversary permanently withholds a large portion of the target. In the extreme case where the adversary reveals almost nothing, the no-hallucination bound on recall approaches zero, while the relaxed algorithm achieves recall approaching one. This is not merely an incremental improvement; it is a qualitative change in what is achievable.
- Continuous novelty parameter. The authors introduce a parameter gamma in [0,1) that interpolates between strict novelty (every output must be new) and no novelty constraint. Any fixed allowance of non-novel outputs, however small a fraction, turns out to be sufficient to achieve both precision one and recall one simultaneously, under relaxed tail precision. This is a genuinely new result: the strict novelty boundary is a phase transition, not a smooth degradation.
Methodology
The technical approach generalises the algorithm of Kleinberg and Wei (2025b) to a batched setting where the adversary can reveal multiple strings per round rather than one at a time. This batching is not merely a convenience; it is what enables the exploration rounds that recover strings the adversary has withheld. The algorithm interleaves exploitation of known target strings with controlled exploration, where exploration outputs may be invalid but are produced at a rate that vanishes over time, keeping asymptotic precision at one.
The recall and precision bounds are derived for combinations of three binary axes: full versus partial adversarial exhaustion, strict novelty versus gamma-novelty, and perfect versus relaxed tail precision. Figure 1 of the paper summarises all cases in a single diagram, distinguishing existing results (from Kleinberg and Wei 2025b) from new results. The new lower bounds on recall under relaxed tail precision are of the form max(1 - beta, alpha/3), where alpha and beta are lower and upper bounds on the adversary's revealed fraction. When the adversary is sparse (large 1 - beta), the relaxed learner can substantially outperform the eventually-valid one.
Results and What They Mean
The core finding is that hallucinations, properly controlled, are not just an unavoidable nuisance but can be a resource. The adversarial model here is abstract, but it maps onto a recognisable real-world situation: a language model is trained on a corpus that covers only part of the true distribution, and the withheld portion is exactly what the model needs to generalise to. The theoretical result says that if you are willing to tolerate errors at a vanishing rate, you can recover coverage that is otherwise inaccessible.
The gamma-novelty result is perhaps the more surprising of the two. One might expect that allowing a fixed fraction of repetitions would help only marginally. Instead, any gamma strictly less than one is sufficient to achieve perfect recall and perfect precision simultaneously. The transition from gamma = 1 (strict novelty) to gamma < 1 is sharp: below the boundary, the problem becomes tractable in a much stronger sense.
The batched adversary generalisation is also worth noting as a standalone technical contribution. Prior work assumed the adversary reveals one string per round, which is a significant restriction. The batched setting is closer to how training data is actually presented, and the algorithms developed here remain correct under this more general model.
Limitations and Open Questions
The framework remains firmly in the worst-case, adversarial tradition of learning theory. The adversary is computationally unbounded and can withhold arbitrary portions of the target language indefinitely. This is a useful theoretical baseline but may not capture the statistical structure of real training corpora, where the withheld portion is not adversarially chosen but reflects sampling bias or data availability. Connecting these asymptotic results to finite-sample or PAC-style bounds would be a natural next step.
The precision metric defined via exhaustions is elegant but leaves open the question of how to estimate precision in practice. For a deployed language model, you cannot observe the target language directly, so computing recall or precision in this sense requires knowing what you are trying to cover, which is precisely what is unknown. The theoretical results are therefore best read as existence proofs and impossibility results rather than as algorithmic recipes for practitioners.
There is also a question of whether the vanishing hallucination rate is achievable at a useful rate of decay. The theoretical results guarantee that the rate goes to zero but do not specify how fast. For practical purposes, a hallucination rate that decays as 1/log(t) is very different from one that decays as 1/t, even if both satisfy the asymptotic condition.
Overall, this paper makes a genuine theoretical contribution by introducing precision as a formal metric in the generation-in-the-limit setting and by showing that the recall-precision trade-off has a non-trivial structure that depends on the adversary's behaviour. The result that controlled hallucinations can unlock coverage otherwise blocked by adversarial withholding is both counterintuitive and well-grounded. It gives a theoretical basis for thinking about error rates in language generation as something to be managed rather than simply minimised.