In plain words: Using ideas from computational complexity, the paper shows that once tasks pass a certain level of complexity, transformer-based language models cannot complete them or check whether their answers are correct. This sets a hard ceiling on what such models and agents can reliably do, including verifying their own work.
Abstract · Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models
In this paper we explore hallucinations and related capability limitations in LLMs and LLM-based agents from the perspective of computational complexity. We show that beyond a certain complexity, LLMs are incapable of carrying out computational and agentic tasks or verifying their accuracy.
Varin Sikka, Vishal Sikka
arXiv:2507.07505 · cs.CL, cs.AI · submitted Jul 10, 2025 · updated Jul 15, 2025
abstract · pdf · 6 pages; to be submitted to AAAI-26 after reviews
