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

• URL: http://arxiv.org/abs/2508.07334v1
• Date: Sun, 10 Aug 2025 13:26:36 GMT
• Title: Hallucination as a Computational Boundary: A Hierarchy of Inevitability and the Oracle Escape
• Authors: Quan Shi, Wang Xi, Zenghui Ding, Jianqing Gao, Xianjun Yang,
• Abstract summary: The illusion phenomenon of large language models (LLMs) is the core obstacle to their reliable deployment.<n>This article formalizes the large language model as a probabilistic Turing machine by constructing a "computational necessity hierarchy"<n>We propose two "escape routes": one is to model Retrieval Enhanced Generations (RAGs) as oracle machines, proving their absolute escape through "computational jumps"
• Score: 9.737202904844562
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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

Related papers

• Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models [61.55758048622473]
  We introduce Neural Chain-of-Thought Search (NCoTS), a framework that reformulates reasoning as a dynamic search for the optimal thinking strategy.<n>By quantitatively characterizing the solution space, we reveal the existence of sparse superior reasoning paths that are simultaneously more accurate and concise than standard outputs.
  arXiv  Detail & Related papers  (2026-01-16T14:38:18Z)
• Digital Metabolism: Decoupling Logic from Facts via Regenerative Unlearning -- Towards a Pure Neural Logic Core [4.073707521515039]
  "Digital metabolism" is a hypothesis suggesting that targeted forgetting is necessary for distilling a pure neural logic core.<n>We introduce the Regenerative Logic-Core Protocol (RLCP), a dual-stream training framework that renders specific factual dependencies linearly undecodable.<n> Empirical analysis on GSM8K reveals that the "metabolized" model spontaneously adopts Symbolic chain-of-thought scaffolding.
  arXiv  Detail & Related papers  (2026-01-15T19:21:16Z)
• Geometrically-Constrained Agent for Spatial Reasoning [53.93718394870856]
  Vision Language Models exhibit a fundamental semantic-to-geometric gap in spatial reasoning.<n>Current paradigms fail to bridge this gap.<n>We propose a training-free agentic paradigm that resolves this gap by introducing a formal task constraint.
  arXiv  Detail & Related papers  (2025-11-27T17:50:37Z)
• Think Visually, Reason Textually: Vision-Language Synergy in ARC [94.15522924153264]
  ARC-AGI is a rigorous testbed for conceptual rule induction and transfer to novel tasks.<n>Most existing methods treat ARC-AGI as a purely textual reasoning task, overlooking the fact that humans rely heavily on visual abstraction.<n>We introduce two synergistic strategies: Vision-Language Synergy Reasoning (VLSR) and Modality-Switch Self-Correction (MSSC)<n>Our findings suggest that unifying visual abstraction with linguistic reasoning is a crucial step toward achieving generalizable, human-like intelligence.
  arXiv  Detail & Related papers  (2025-11-19T18:59:04Z)
• AI Agents as Universal Task Solvers [94.49762121230042]
  We show that the optimal speed-up that a universal solver can achieve using past data is tightly related to their algorithmic information.<n>We argue that the key quantity to optimize when scaling reasoning models is time, whose critical role in learning has so far only been indirectly considered.
  arXiv  Detail & Related papers  (2025-10-14T02:17:54Z)
• Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey [92.71325249013535]
  Deliberative tree search is a cornerstone of Large Language Model (LLM) research.<n>This paper introduces a unified framework that deconstructs search algorithms into three core components.
  arXiv  Detail & Related papers  (2025-10-11T03:29:18Z)
• How LLMs Learn to Reason: A Complex Network Perspective [14.638878448692493]
  Training large language models with Reinforcement Learning from Verifiable Rewards exhibits a set of puzzling behaviors.<n>We propose that these seemingly disparate phenomena can be explained using a single unifying theory.<n>Our work provides a new physical intuition for engineering the emergent reasoning capabilities of future AI systems.
  arXiv  Detail & Related papers  (2025-09-28T04:10:37Z)
• Beyond Turing: Memory-Amortized Inference as a Foundation for Cognitive Computation [5.234742752529437]
  We introduce Memory-Amortized Inference (MAI) as a formal framework in which cognition is modeled as inference over latent cycles in memory.<n>We show that MAI provides a principled foundation for Mountcastle's Universal Cortical Algorithm.<n>We briefly discuss the profound implications of MAI for achieving artificial general intelligence.
  arXiv  Detail & Related papers  (2025-08-19T15:10:26Z)
• Bridging Formal Language with Chain-of-Thought Reasoning to Geometry Problem Solving [9.550050299909184]
  We present a new approach that integrates Chain-of-Thought (CoT) with formal language.<n>The model interleaves natural language reasoning with incremental emission of solver-executable code.<n>Built on Qwen2.5-VL-7B, our new model, GF-Reasoner, achieves up to 15% accuracy improvements on standard GPS benchmarks.
  arXiv  Detail & Related papers  (2025-08-12T17:26:23Z)
• Training Cross-Morphology Embodied AI Agents: From Practical Challenges to Theoretical Foundations [16.735655028118817]
  This article shows that theoretical insight is essential for overcoming real-world engineering barriers.<n>We formalize the Heterogeneous Embodied Agent Training (HEAT) problem and prove it reduces to a structured Partially Observable Markov Decision Process (POMDP) that is PSPACE-complete.<n>We also explore Collective Adaptation, a distributed learning alternative inspired by biological systems.
  arXiv  Detail & Related papers  (2025-06-04T06:44:49Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  We train and evaluate neural networks directly as binary classifiers of strings.<n>We provide results on a variety of languages across the Chomsky hierarchy for three neural architectures.<n>Our contributions will facilitate theoretically sound empirical testing of language recognition claims in future work.
  arXiv  Detail & Related papers  (2024-11-11T16:33:25Z)
• Interpretability at Scale: Identifying Causal Mechanisms in Alpaca [62.65877150123775]
  We use Boundless DAS to efficiently search for interpretable causal structure in large language models while they follow instructions. Our findings mark a first step toward faithfully understanding the inner-workings of our ever-growing and most widely deployed language models.
  arXiv  Detail & Related papers  (2023-05-15T17:15:40Z)
• Multimodal Chain-of-Thought Reasoning in Language Models [94.70184390935661]
  We propose Multimodal-CoT that incorporates language (text) and vision (images) modalities into a two-stage framework. Experimental results on ScienceQA and A-OKVQA benchmark datasets show the effectiveness of our proposed approach.
  arXiv  Detail & Related papers  (2023-02-02T07:51:19Z)
• Deep learning applied to computational mechanics: A comprehensive review, state of the art, and the classics [77.34726150561087]
  Recent developments in artificial neural networks, particularly deep learning (DL), are reviewed in detail. Both hybrid and pure machine learning (ML) methods are discussed. History and limitations of AI are recounted and discussed, with particular attention at pointing out misstatements or misconceptions of the classics.
  arXiv  Detail & Related papers  (2022-12-18T02:03:00Z)
• Explainable AI via Learning to Optimize [2.8010955192967852]
  Indecipherable black boxes are common in machine learning (ML), but applications increasingly require explainable artificial intelligence (XAI) This work provides concrete tools for XAI in situations where prior knowledge must be encoded and untrustworthy inferences flagged.
  arXiv  Detail & Related papers  (2022-04-29T15:57:03Z)
• Neural Unification for Logic Reasoning over Natural Language [0.28675177318965034]
  Automated Theorem Proving deals with the development of computer programs being able to show that some conjectures (queries) are a logical consequence of a set of axioms (facts and rules) Recent approaches have proposed transformer-based architectures for deriving conjectures given axioms expressed in natural language (English) In this work we propose a new architecture, namely the Neural Unifier, which achieves state-of-the-art results in term of generalisation.
  arXiv  Detail & Related papers  (2021-09-17T10:48:39Z)
• A Study of the Mathematics of Deep Learning [1.14219428942199]
  "Deep Learning"/"Deep Neural Nets" is a technological marvel that is now increasingly deployed at the cutting-edge of artificial intelligence tasks. This thesis takes several steps towards building strong theoretical foundations for these new paradigms of deep-learning.
  arXiv  Detail & Related papers  (2021-04-28T22:05:54Z)
• Realising Active Inference in Variational Message Passing: the Outcome-blind Certainty Seeker [3.5450828190071655]
  This paper provides a complete mathematical treatment of the active inference framework -- in discrete time and state spaces. We leverage the theoretical connection between active inference and variational message passing. We show that using a fully factorized variational distribution simplifies the expected free energy.
  arXiv  Detail & Related papers  (2021-04-23T19:40:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.