# Hallucination as a Computational Boundary: A Hierarchy of Inevitability and the Oracle Escape

arXiv: https://arxiv.org/abs/2508.07334 · HTML: https://mlsanity.com/paper/2508.07334/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 17 references that are in the map.
- First posted on arXiv 10 Aug 2025.

## Builds on (most cited first, 6 of 6)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Locating and Editing Factual Associations in GPT](https://mlsanity.com/paper/2202.05262/) (2022)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [Editing Factual Knowledge in Language Models](https://mlsanity.com/paper/2104.08164/) (2021)

## Built on by (most cited first, 2 of 2)

- [Hallucination is Inevitable for LLMs with the Open World Assumption](https://mlsanity.com/paper/2510.05116/) (2025)
- [Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing](https://mlsanity.com/paper/2602.00906/) (2026)

## Abstract (arXiv)

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 feasible new principle for artificial intelligence security - Computational Class Alignment (CCA), which requires strict matching between task complexity and the actual computing power of the system, providing theoretical support for the secure application of artificial intelligence.