Hallucination as a Computational Boundary: A Hierarchy of Inevitability and the Oracle Escape
This work addresses the core obstacle to reliable LLM deployment, offering foundational theoretical insights with potential broad impact in AI safety and reliability.
The paper tackles the problem of hallucinations in large language models by proving their inevitability through computational theory, and proposes two escape routes: retrieval-augmented generation as oracle machines and continuous learning via neural game theory.
The illusion phenomenon of large language models (LLMs) is the core obstacle to their reliable deployment. This article formalizes the large language model as a probabilistic Turing machine by constructing a "computational necessity hierarchy", and for the first time proves the illusions are inevitable on diagonalization, incomputability, and information theory boundaries supported by the new "learner pump lemma". However, we propose two "escape routes": one is to model Retrieval Enhanced Generations (RAGs) as oracle machines, proving their absolute escape through "computational jumps", providing the first formal theory for the effectiveness of RAGs; The second is to formalize continuous learning as an "internalized oracle" mechanism and implement this path through a novel neural game theory framework.Finally, this article proposes a