about
Some Basic Limitations of Transformer-Based Language Models (arxiv.org)
1 point by RansomStark 251 days ago | hide | past | pdf | discuss on HN

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

add comment on HN
Also discussed: Jan 2026 (2 points, 1 comment) · Jan 2026 (1 point, 0 comments)