New paper proves AI can hallucinate infinitely if error rate tends to zero

A new theoretical paper from Irene Strauss, Alexandra Butoi, and Ryan Cotterell tackles the fundamental tension between broad coverage and correctness in language generation models. Building on the classic paradigm of language identification in the limit and its recent generation-in-the-limit extension, the authors recast the problem as a precision-recall trade-off. Their key insight: allowing a model to produce infinitely many hallucinations (false outputs) is acceptable as long as the error rate approaches zero over time, keeping precision at exactly 1. This relaxation strictly increases recall when an adversary permanently withholds a large portion of the target language from the learner.

The paper also examines a continuous formulation of the novelty constraint, requiring only a fixed fraction of outputs to be novel rather than all of them. Together, these contributions move toward a more realistic model of LLM behavior—where occasional hallucinations and repetitions are inevitable but their frequencies can be tightly controlled. The work bridges formal language theory and practical machine learning, offering new theoretical guarantees for generative AI systems that must balance validity, coverage, and novelty in open-ended generation tasks.