Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models

2025/07/10 by Varin Sikka, Vishal Sikka, Sikka, Varin +1 · 30 voices
#cs.CL #cs.AI

paper · pdf · doi:10.48550/arxiv.2507.07505

Abstract

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.

Citations

• Gold-medalist Performance in Solving Olympiad Geometry with AlphaGeometry2
• Hallucination is Inevitable: An Innate Limitation of Large Language Models
• Attention Is All You Need

Discussions

• i do not understand how you could write an article on this "paper" (which appears to be from a guy who has never worked on machine learning) without asking even another skeptic "does this make any sen [bsky, 134 points, 9 comments]
• So first thing to note is that it's an Arxiv preprint, meaning it has no peer review. Also, it's the only paper by the two coauthors. (Gotta give props to Gizmodo, at least they linked the paper. Some [bsky, 33 points, 2 comments]
• arxiv.org/abs/2507.07505 [bsky, 9 points, 1 comments]
• Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models [lobsters, 4 points, 2 comments]
• It may be that LLMs have a complexity barrier according to a paper posted to Arxiv: arxiv.org/pdf/2507.07505 [bsky, 3 points, 1 comments]
• Here is the link to the original paper: arxiv.org/pdf/2507.07505 [bsky, 3 points, 2 comments]
• Hallucination Stations: On Some Basic Limitations of Transformer-Based Language [hn, 2 points, 1 comments]
• Its extremely short and extremely bad, and coding agents instantly break their analysis [bsky, 2 points, 1 comments]
• Here's the paper: arxiv.org/abs/2507.07505 [bsky, 2 points, 1 comments]
• Full agentic workloads are not mathematically possible - arxiv.org/pdf/2507.07505 Folks are chasing phantoms. Instead, use LLMs to build secure services using Claude Code. [bsky, 2 points, 1 comments]
• Ran across this beautiful piece of science. It's simplistic and kind of assumes language models are perfect problem solvers instead of being next word predictors, but it illustrates really nicely how [bsky, 2 points, 0 comments]
• Mathematical proof that large language models (LLMs) have a limit to their ability to give accurate answers and thus hallucinations are impossible to prevent. Number of computations proportional to th [bsky, 2 points, 0 comments]
• Hallucination Stations: Limitations of Transformer-Based Language Models (2025) [hn, 1 points, 0 comments]
• Some Basic Limitations of Transformer-Based Language Models [hn, 1 points, 0 comments]
• 円積問題に挑むのがいつも成り上がりの素人と同じようなことですね。今度は「AIならきっと」という点だけが違います 出展を読みましたが、簡潔で説得力があります。しかも、人間がコンピューターではないことも読み取れます arxiv.org/pdf/2507.07505 [bsky, 1 points, 2 comments]
• The short paper in question is here: arxiv.org/pdf/2507.07505 [bsky, 1 points, 1 comments]
• Yup, and this one. (I have been beating the “stop wasting resources trying to figure out how to stop them from hallucinating because they can’t, build verification systems instead” drum since 2023 and [bsky, 1 points, 0 comments]
• いま機械翻訳を駆使して元論文を読んでいます。あまり理解できていませんが、なかなか面白い。 AIが応答において幻覚（ハルシネーション）を示す条件の数学的な「定理」が書かれています。 他にも…… 「LLMへの指示がLLMの中核動作よりも複雑な計算（または計算タスク）を指定している場合、LLMは一般的に誤った応答をする」 「LLM または LLM ベースのエージェントは、この複雑度を超えるタスクの正しさ [bsky, 1 points, 0 comments]
• Geilo 🤭 Hat jemand mal bei den Investoren und Geldgebern von OpenAI und Co. Bescheid gegeben? „Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models“ arxiv.org/abs/25 [bsky, 1 points, 0 comments]
• Heh... What we can instinctively sense already Think how poor AI is at even simple, constrained things like "in context spell checking" (esp. with screen-keyboard proximity errors). #AwarenessMatters [bsky, 1 points, 0 comments]
• Operationalizing this insight in #AI systems could be tricky... [darn character limits] arxiv.org/pdf/2507.07505 [bsky, 1 points, 0 comments]
• arxiv.org/pdf/2507.07505 [bsky, 1 points, 2 comments]
• arxiv.org/pdf/2507.07505 [bsky, 0 points, 0 comments]
• 覚書。今訳してる時間ないから。 "Hallucination Stations On Some Basic Limitations of Transformer-Based Language Models" arxiv.org/pdf/2507.07505 短いな。 [bsky, 0 points, 0 comments]
• New paper "Hallucination Stations" argues LLMs have inherent O(N²d) complexity ceiling - tasks exceeding this can't be reliably executed *or verified*. Connects to Anti's "subprime code" thesis: the l [bsky, 0 points, 1 comments]
• arxiv.org/pdf/2507.07505 [bsky, 0 points, 0 comments]
• This research proves that for complex jobs—like optimizing a delivery route or finding a needle-in-a-haystack error in software—the AI literally runs out of 'thinking power' before it can reach the ri [bsky, 0 points, 1 comments]
• Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models https://lobste.rs/s/xm5n6w #pdf #vibecoding [bsky, 0 points, 0 comments]
• Hallucination Stations On Some Basic Limitations of Transformer-Based Language Models arxiv.org/pdf/2507.07505 [bsky, 0 points, 0 comments]
• Hallucination Stations On Some Basic Limitations of Transformer-Based Language Models arxiv.org/pdf/2507.07505 [bsky, 0 points, 1 comments]

Related

• Hallucination is Inevitable: An Innate Limitation of Large Language Models
• LLMs Will Always Hallucinate, and We Need to Live With This
• On Limitations of the Transformer Architecture
• Hallucination is Inevitable for LLMs with the Open World Assumption
• HEAL: An Empirical Study on Hallucinations in Embodied Agents Driven by Large Language Models