The O(N²·d) Cage: Why AI Hallucination is a Mathematical Certainty
CATEGORY: Computational Theory / Policy Analysis
DATE: April 28, 2026
AUTHOR: Yoshimichi Kumon / Organizer, LSI
- Preface: A Mathematical Proof of What We Suspected
- 1. The Boundary: Computational Complexity as a “Physical Law”
- 2. The Three Walls Where LLMs Fail
- 3. The Illusion of “Reasoning Models”
- 4. The Governance Implication: Why This Matters Beyond Computer Science
- Conclusion: Intelligence Must Be Verified at the Physical Layer
Preface: A Mathematical Proof of What We Suspected
A pivotal paper by Varin Sikka (Stanford University) and Vishal Sikka, titled “Hallucination Stations,” was published in 2025 and has gained renewed attention in the AI governance community in early 2026. It provides cold, mathematical proof of the limitations of the Logical Layer that LSI has been examining in our Neuro-Sovereignty series.
AI hallucinations are not merely the result of insufficient training or a lack of ethics. They are a physical inevitability born from the computational cage of the Transformer architecture itself.
1. The Boundary: Computational Complexity as a “Physical Law”
The inference of Transformer-based Large Language Models (LLMs) is bound by a mathematical constraint. When the number of input tokens is N and the model dimension is d, the computational complexity is fixed at O(N²·d).
The intuition presented in the paper is strikingly simple:
“If the computational complexity of a given task is higher than O(N²·d), the LLM is physically incapable of executing that task correctly.”
This is not a software limitation that can be patched. It is not a training failure that can be corrected with more data. It is a structural ceiling — as fixed as the speed of light, as unavoidable as entropy.
2. The Three Walls Where LLMs Fail
The paper identifies specific scenarios where LLMs are guaranteed to produce hallucinations:
The Wall of Matrix Multiplication
Even simple matrix multiplication becomes impossible for an LLM once the size exceeds the model’s fixed capacity. The required complexity reaches O(n³) — beyond the transformer’s ceiling. The model does not refuse. It confabulates a plausible-looking answer.
The Wall of Combinatorial Optimisation
For problems like the Travelling Salesperson Problem (TSP), which require factorial (n!) or exponential computation, LLMs can neither produce the correct answer nor verify a correct answer provided by others. The verification step itself exceeds the model’s complexity budget.
The Limit of Self-Verification
This is the most consequential finding. Even when LLM-based agents are tasked with “verifying” a response, they will generate hallucinations if the complexity of the verification itself exceeds their own computational bounds.
The paper formalises this as:
Theorem 1: If a task’s complexity is O(n³) or higher, an LLM will inevitably hallucinate.
3. The Illusion of “Reasoning Models”
Models like OpenAI’s o3 or DeepSeek’s R1, which generate Chain-of-Thought “thinking processes” before answering, are currently attracting significant attention. They appear to have bypassed the complexity ceiling. The paper remains sceptical for two reasons.
First: the underlying operation — Self-Attention — remains trapped within the same O(N²·d) cage. The chains of thought are generated by the same constrained mechanism.
Second: the “budget” of thinking tokens provided to these models is often mathematically insufficient compared to the steps required for genuinely complex tasks. As Apple ML Research noted in 2025, these models suffer from what they term “Reasoning Collapse” when faced with high-complexity problems — not gradually degrading, but failing suddenly when the problem crosses their hidden threshold.
The reasoning model is not an escape from the cage. It is a larger cage that takes longer to reach its walls.
4. The Governance Implication: Why This Matters Beyond Computer Science
The theorem has a direct and underappreciated implication for AI governance.
If an LLM cannot verify outputs that exceed its own complexity threshold — and if the model itself cannot know when it has crossed that threshold — then no software-layer governance mechanism that relies on AI self-reporting can be trusted for high-complexity tasks.
An AI system tasked with monitoring another AI system faces the same ceiling. A governance AI asked to verify a frontier AI’s outputs may itself be operating in a regime where it cannot detect the hallucination it is looking for.
This is not a hypothetical concern. It is a mathematical certainty.
Conclusion: Intelligence Must Be Verified at the Physical Layer
The “intelligence” of an LLM is bounded by its computational complexity threshold. No matter how plausible an AI’s response may seem, if the problem possesses non-trivial complexity, its accuracy cannot be confirmed within the Logical Layer — not by the AI itself, and not by another AI operating under the same constraints.
What we need is not to make AI “think deeper.” We need a Physical Layer Governance that verifies AI outputs against the physical truths of base reality: thermodynamics, electromagnetism, and the sovereign observation of a conscious human.
The O(N²·d) cage is not a temporary limitation waiting to be engineered away. It is a structural feature of the architecture. While the AI reasons within its cage — producing outputs that may be correct, may be plausible, or may be mathematical fiction — the Sovereign Observer must hold the physical breaker, grounded in a reality the model cannot reach.
The cage is elegant. The physics outside it is not negotiable.
✒️ Signature
April 28, 2026
Yoshimichi Kumon
Organizer, LSI — Logos Sovereign Intelligence
Inventor, ARDS/ARKS (PCT GA26P001WO)
📚 References
Sikka, Varin & Sikka, Vishal (2025). Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models. Stanford University / Vianai Systems.
Hartmanis, J. & Stearns, R. E. (1965). “On the computational complexity of algorithms.” Transactions of the American Mathematical Society.
Apple ML Research (2025). “The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity.”
Kumon, Yoshimichi (2026). Physical Layer AI Governance via Sovereignty Residual (Rsovereign). PCT International Patent Application No. GA26P001WO. Japan Patent Office.
Ⅽomment