Pith. sign in

REVIEW 5 major objections 4 minor 26 references

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

T0 review · 5 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper's central claim is that any LLM, when prompted with a task whose textbook complexity exceeds its O(N²·d) inference budget, will unavoidably hallucinate; exact computation and verification are out of reach.

desk verdict A clear but mathematically broken attempt to prove LLMs hallucinate on complex tasks; Theorem 1's proof collapses on the N-vs-n mismatch, so the formal claim does not hold. read the letter →

arxiv 2507.07505 v3 pith:75TNJW2L submitted 2025-07-10 cs.CL cs.AI

Varin Sikka , Vishal Sikka This is my paper · ORCID
classification cs.CLcs.AI MSC 68Q1568Q25
keywords hallucinationcomputationalcomplexitytransformerinferenceself-attentionagenticAIverificationtimehierarchytheoremLLMlimitations
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish a hard computational ceiling for transformer-based language models. It claims that an LLM processing a prompt of N tokens has a fixed inference budget of O(N²·d) operations, and that any prompt embedding a task whose textbook algorithm needs O(n³) or more operations, with n < N, cannot be executed correctly — so the model's response is a hallucination. The same ceiling is claimed to apply to LLM-based agents and to the verification of one agent's work by another, because exact verification is often at least as hard as the task itself. If true, this gives a formal reason why exact high-complexity computation and reliable verification are outside the reach of individual LLMs.

What carries the argument

The load-bearing mechanism is the transformer's self-attention complexity bound, O(N²·d) for N tokens with d-dimensional embeddings, which the paper treats as a fixed budget per response. The other half is the time-hierarchy theorem, the standard result that there exist decision problems solvable with more time but not with less. The paper compares the prompt length N with the size parameter n of the embedded task and its textbook complexity O(n³) or higher, arguing that since n < N and the budget grows only quadratically in N, the task's required operations outrun the model's fixed allowance. That comparison is what converts an asymptotic statement about complexity classes into a claim about every concrete LLM response.

What would settle it

A reproducible experiment in which a transformer, given fresh random instances and no external tools, returns exact answers to a task whose textbook complexity exceeds its measured O(N²·d) budget would contradict the theorem's 'unavoidably hallucinate' claim; for example, exact verification of a claimed shortest route over enough cities, repeated across fresh instances that cannot have been memorized. If such correctness persists across instances, the model has either beaten the budget or used a shortcut, and the load-bearing assumption is false.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: given a prompt of length N that includes a computational task of complexity O(n³) or higher, with the task's size parameter n smaller than N, an LLM or LLM-based agent will unavoidably hallucinate in its response. The proof relies on the time-hierarchy theorem, which guarantees that some problems require asymptotically more time than others, and on the known O(N²·d) cost of the transformer's self-attention computation. Because the LLM's operations per prompt are bounded by this cost, any task whose minimal execution requires more operations cannot be carried out within the model's budget; the authors count even an accidentally correct answer as a hallucination, since the computation was not actually performed. They extend this conclusion to agentic settings and to verification: a second LLM agent checking a solution faces the same-or-larger complexity, so exact verification is also out of reach.

Load-bearing premise

The argument assumes an LLM must execute the full textbook algorithm for the stated task to answer correctly, and that its complexity O(n³) can be compared directly with the model's O(N²·d) inference budget using prompt length N, ignoring both the cost of encoding the task instance and possible memorized or heuristic shortcuts.

Editorial extensions

If this is right

  • Individual LLMs cannot be relied on for exact execution of operations such as matrix multiplication, all-pairs shortest paths, or subset enumeration when the textbook complexity is cubic or higher.
  • LLM-based agents inherit the ceiling: any agentic task whose exact solution needs O(n³) or more operations cannot be performed correctly by an LLM agent alone.
  • Verification chains between LLM agents are not a fix, since verifying a solution to a hard task generally costs at least as much computation as solving it.
  • Hallucinations of this kind would not be a data or fine-tuning artifact; they would be forced by the inference-time budget.
  • Raising the context window N raises the budget only quadratically, so longer prompts do not lift the ceiling for cubic-or-higher tasks.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An inference the paper does not spell out: the claimed ceiling is encoding-sensitive, since tasks like matrix multiplication must write the instances into the prompt, making N grow with the square of the dimension; restating the theorem in terms of encoded prompt length would change where the bound bites.
  • Another extension: the same budget argument suggests that offloading the hard step to an exact external solver or calculator evades the limit, a direction the paper only gestures at in its discussion of composite systems.
  • One testable prediction that follows from the paper's logic: if the bottleneck is truly the attention budget, giving a model a much larger token budget for reasoning steps should not turn it into a reliable solver of cubic-or-harder tasks; a demonstration that extended reasoning reliably fixes correctness would undercut the claim.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 4 minor

Summary. The paper argues that transformer-based LLMs have a per-prompt inference complexity of O(N^2 d), and claims that any prompt containing a computational task of complexity O(n^3) or higher, with n < N, will cause the LLM, or an LLM-based agent, to 'unavoidably hallucinate.' A corollary states that such tasks cannot be verified by LLMs or LLM-based agents. The argument compares the task's asymptotic complexity to the LLM's inference budget and invokes the Hartmanis--Stearns time-hierarchy theorem. The paper supports the claim with examples (token composition, matrix multiplication, TSP verification) and discusses consequences for agentic AI.

Significance. If the central theorem were correct, it would supply a clean complexity-theoretic upper bound on the exact computational and verification tasks that LLMs can perform, with substantial practical implications for agentic deployments. The paper is clearly written, identifies a real and timely question, gives concrete examples, and even ships a code-backed FLOP measurement for a specific model, which is a commendable effort at grounding. However, the claimed result is much stronger than what the arguments support, and the proof's key comparison is flawed. The paper does not engage with existing formal work on transformer computational capacity, and its main theorem, as stated, is not defensible.

major comments (5)
  1. [Example 2: Matrix Multiplication; Theorem 1 proof] The comparison of task complexity f(n) with the LLM's O(N^2 d) budget is invalid because N is the prompt length, not the task's input length. For the paper's own matrix multiplication example, specifying two n×n matrices requires N = Ω(n^2) tokens, so the LLM budget is O(N^2 d) = Ω(n^4 d), which asymptotically exceeds the claimed task complexity O(n^3). Thus the flagship example does not lie above the threshold, and the theorem's premise is not met for the paper's own examples.
  2. [The paragraph beginning 'Our intuition in this paper is...' and the proof of Theorem 1] The proof assumes that an LLM must execute the canonical textbook algorithm for the stated task in order to answer correctly. This is not justified: an LLM may answer specific instances from memory, from pattern matching, or via a heuristic shortcut, and the time-hierarchy theorem guarantees only the existence of some hard inputs for a harder-time language, not that every prompt describing a worst-case-hard task is itself a hard instance. Therefore the inference from the theorem to 'any task that requires time greater than O(N^2 d)' is a non sequitur.
  3. [Theorem 1 (quantification of N)] The theorem is internally inconsistent because N is not fixed or bounded. Since N is the prompt length, any prompt can be padded with irrelevant tokens, which increases N and therefore increases the O(N^2 d) budget while leaving the underlying task and its parameter n unchanged. For any fixed n and any claimed hard instance, one can pad the prompt until N^2 d ≫ f(n), making the theorem's claim self-refuting. The theorem must specify how N relates to the task encoding and must rule out padding, but the manuscript states only that n < N.
  4. [Traveling Salesperson Problem paragraph and the corollary to Theorem 1] The claim that verifying a claimed TSP route requires comparing it against all (n−1)!/2 routes is incorrect for the standard decision version of TSP, where a candidate tour of length at most k is a certificate verifiable in polynomial time. The optimality-verification variant (is a given tour shortest?) is a different problem, and the paper does not show that an LLM verifier must use exhaustive search or that no certificate (e.g., duality bounds) can make verification cheap. Thus the corollary that LLM agents cannot verify tasks beyond the complexity threshold is unsupported.
  5. [Agentic AI example and the proof of Theorem 1 applied to agents] The paper asserts that all of an agent's operations are limited to O(N^2 d) complexity, but an LLM-based agent can invoke external tools, calculators, code interpreters, or databases whose computations are not transformer forward passes. The manuscript's own Discussion acknowledges 'composite systems' as a potential mitigation, which contradicts the blanket impossibility claim for agents. The theorem does not cover such systems, so the agentic conclusion as stated is not established.
minor comments (4)
  1. [Throughout] There are frequent typographical errors (e.g., 'diTerent' for 'different', 'diTerences' for 'differences') and grammatical issues (e.g., 'a size n set of tokens') that should be corrected before any resubmission.
  2. [Computational Complexity of LLMs, and its Implications] The notation uses n both for the vocabulary size and for the task parameter; footnote 1 clarifies the distinction, but this overloaded notation is confusing and should be changed (e.g., use V for vocabulary size).
  3. [Computational Complexity of LLMs, and its Implications] The statement that an LLM 'performs approximately N^2·d floating-point operations' is imprecise: the cited O(N^2 d) result refers to self-attention, not to the entire transformer inference pass, which includes feed-forward layers, layer normalization, and autoregressive generation over output tokens. This does not invalidate the conceptual point, but the numerical basis of the threshold needs clarification.
  4. [References] The reference list has inconsistent formatting (e.g., [4] contains stray spaces and initials, [7] is a personal webpage, and several references lack page numbers or publisher details); the list should be formatted according to the journal's style.

Circularity Check

1 steps flagged · score 6.0 of 10

Theorem 1 is a restatement of the paper's 'Our intuition' premise; the time-hierarchy theorem is not bridged to LLM behavior, so the 'unavoidable hallucination' conclusion reduces to the paper's own assumption.

  1. self definitional [Section 'Computational Complexity of LLMs, and its Implications', 'Our intuition' paragraph; Theorem 1 and its proof.]
    "Our intuition in this paper is: if there is an input string that expresses a task with computational complexity is higher than O(N².d), then an LLM cannot correctly carry out that task. ... Proof: Hartmanis and Stearns ... Consequently, any task that requires time greater than O(N².d), such as the ones in our examples above, but indeed infinitely many such tasks, will not be correctly carried out by LLMs."

    The theorem concludes 'will unavoidably hallucinate,' and the Discussion defines hallucination to cover any case where the response is not produced by correctly carrying out the task, including accidentally correct answers. Under that definition, the theorem's conclusion is the same proposition that was introduced as 'Our intuition': a task above O(N².d) cannot be correctly carried out by an LLM. The Hartmanis-Stearns citation only adds that some decision problems require more than O(N².d) Turing-machine time; it does not show that an LLM must execute the textbook algorithm, that heuristics/memorization are impossible, or that the prompt length N is the task's input length.

full rationale

The paper's central theorem is circular in the narrow sense that its conclusion is the same as its labeled 'intuition' premise, with no independent argument connecting the time-hierarchy theorem to actual LLM behavior. However, the paper does rely on external, non-self-cited support for the LLM complexity bound (Vaswani et al.; Keles et al.) and on the Hartmanis-Stearns theorem, so the circularity is partial rather than total. No load-bearing self-citation was found: the reference to the first author's website [7] is an illustrative FLOPS measurement, and the Vianai citation [24] is not used in the proof. The deeper problem with the proof—comparing O(n³) evaluated at n<N with O(N²d) evaluated at the full prompt length, ignoring that specifying n×n matrices needs N=Ω(n²) tokens—is primarily a correctness/invalidity issue rather than a circularity issue, and is reflected in the score of 6 rather than 8.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new entities and no fitted numeric constants. The argument rests entirely on the time-hierarchy theorem plus two informal domain assumptions: that the model must run the textbook algorithm, and that input encoding does not change the complexity comparison. Both assumptions are load-bearing and both are violated by standard encodings.

assumptions (3)
  • standard math Time-hierarchy theorem (Hartmanis-Stearns)
    Invoked in the proof of Theorem 1 to assert that any O(N^2 d)-time machine fails on some problems requiring more time.
  • domain assumption An LLM must execute the canonical algorithm of the stated task to answer correctly
    Stated as 'Our intuition' before Example 1; it rules out memorization, heuristics, and approximate reasoning.
  • domain assumption The length N of the prompt does not grow with task size n in a way that breaks the comparison n^3 > N^2 d
    Used in Examples 1-3 and Theorem 1; for matrix multiplication the input contains all entries, so N is quadratic in n, making N^2 d dominate n^3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models." pith.science (2026). https://pith.science/paper/75TNJW2L

@misc{pith2026250707505,
  author       = {Pith},
  title        = {Pith review of: Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/75TNJW2L}},
  note         = {Machine review of arXiv:2507.07505}
}
read the original 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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 18 canonical work pages

  1. [2]

    (2024, January 22)

    Xu, Z., Jain, S., & Kankanhalli, M. (2024, January 22). Hallucination is Inevitable: An Innate Limitation of Large Language Models. arXiv.org. https://arxiv.org/abs/2401.11817

    arXiv 2024

  2. [3]

    (2017, June 12)

    Vaswani, A et al. (2017, June 12). Attention Is All You Need. https://arxiv.org/pdf/1706.03762v5

    arXiv 2017

  3. [4]

    4 Duman Keles, F ., Mahesakya Wijewardena, P ., & Hegde, C. (2023). On the computational complexity of Self-Attention. In Shipra Agrawal & Francesco Orabona (Eds.), Proceedings of Machine Learning Research (Vol. 201, pp. 1–23)

    work page 2023

  4. [6]

    (2025, April 14). Introducing GPT-4.1

    OpenAI. “(2025, April 14). Introducing GPT-4.1” https://openai.com/index/gpt-4-1/

    work page 2025

  5. [7]

    (2025, July 7)

    Varin Sikka. (2025, July 7). https://varinsikka.github.io/

    work page 2025

  6. [8]

    (2025, July 7)

    Wikipedia. (2025, July 7). Petri net Reachability. wikipedia.org/wiki/Petri_net#Reachability

    work page 2025

  7. [9]

    Vector Addition System Reachability Problem (A Short Self-Contained Proof)

    Jérôme Leroux. Vector Addition System Reachability Problem (A Short Self-Contained Proof). Principles of Programming Languages, Jan 2011, Austin, TX, United States. pp.307–316, 10.1145/1926385.1926421.hal-00502865v4

    arXiv 2011

  8. [10]

    Li, S., Ju, L., & Si, H. (2020). Adaptive exponential time integration of the Navier-Stokes equations. AIAA SCITECH 2022 Forum. https://doi.org/10.2514/6.2020-2033

    doi:10.2514/6.2020-2033 2020

Show all 26 references
  1. [11]

    (2025, February 12)

    Pounds, E. (2025, February 12). What is Agentic AI? | NVIDIA blog. NVIDIA Blog. https://blogs.nvidia.com/blog/what-is-agentic-ai/

    2025

  2. [12]

    (2025, June 12)

    Goode, L., Calore, M., & Knight, W. (2025, June 12). Unpacking AI agents. WIRED. https://www.wired.com/story/uncanny-valley-podcast-unpacking-ai-agents/

    2025

  3. [13]

    Sager, P. J., et. al. (2025, January). A comprehensive survey of agents for computer use: foundations, challenges, and future directions. arXiv. https://arxiv.org/abs/2501.16150

    2025 arXiv

  4. [14]

    (2025, April 30)

    Visa wants to give artificial intelligence “agents” your credit card. (2025, April 30). AP News. https://apnews.com/article/ai-artificial-intelligence-5dfa1da145689e7951a181e2253ab349

    2025

  5. [15]

    (2025, April 10)

    Wassel, B. (2025, April 10). Amazon pilots AI that can buy items from third-party sites. Retail Dive. https://www.retaildive.com/news/amazon-buy-for-me-agentic-ai-third-party-sites/745047/

    2025

  6. [17]

    (2025, June 18)

    Various Authors. (2025, June 18). KPMG launches KPMG Workbench: a multi-agent AI platform, transforming client delivery and ways of working across the global organization: https://kpmg.com/xx/en/media/press-releases/2025/06/kpmg-launches-a-multi-agent-ai-platform-transforming-...

    2025

  7. [18]

    (2025, June 5)

    Kessel, A. (2025, June 5). Amazon launches Agentic AI Group to enhance its warehouse robots. Investopedia. https://www.investopedia.com/amazon-launches-agentic-ai-group-to-enhance-its-warehouse-robots-reports-say-11749004

    2025

  8. [19]

    Loiola, Eliane & Abreu, Nair & Boaventura-Netto, Paulo & Hahn, Peter & Querido, Tania. (2011). An Analytical Survey for the Quadratic Assignment Problem. European Journal of Operational Research

    2011

  9. [20]

    Clarke, E.M., et al. (2012). Model Checking and the State Explosion Problem. In: Meyer, B., Nordio, M. (eds) Tools for Practical Software Verification. LASER

    2012

  10. [21]

    (2025, May 8)

    Sullivan, Mark. (2025, May 8). Coding Emerges and Generative AI’s Breakout Star. https://www.fastcompany.com/91330342/coding-emerges-as-generative-ais-breakout-star

    2025

  11. [22]

    Hartmanis, J., & Stearns, R. E. (1965). On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117(0), 285–306. https://doi.org/10.1090/s0002-9947-1965-0170805-7

    1965 doi

  12. [23]

    (2024, November 20)

    Potts, C. (2024, November 20). Large Language Models Get the Hype, but Compound Systems Are the Future of AI. https://www.youtube.com/watch?v=vRTcE19M-KE

    2024

  13. [25]

    Chervonyi, Y ., et. al. (2025). Gold-medalist Performance in Solving Olympiad Geometry with AlphaGeometry2. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2502.03544

    2025 doi

  14. [26]

    Lenat, D., & Marcus, G. (2023). Getting from Generative AI to Trustworthy AI: What LLMs might learn from Cyc. (Cornell University). https://doi.org/10.48550/arxiv.2308.04445

    2023 doi arXiv

  15. [27]

    The Sciences of the Artificial – Third Edition

    Simon, H.A. (1996). “The Sciences of the Artificial – Third Edition”. M I T P r e s s B o o k s

    1996

  16. [28]

    The Society of Mind

    Minsky, M. (1986). “The Society of Mind”. Simon & Schuster

    1986

  17. [29]

    Parshin Shojaee, Samy Bengio, et. al. (2025 June). The Illusion of thinking: understanding the strengths and limitations of reasoning models via the lens of problem complexity. (n.d.). Apple ML Research. https://machinelearning.apple.com/research/illusion-of-thinking

    2025

  18. [7682]

    https://doi.org/10.1007/978-3-642-35746-6_1

    Springer. https://doi.org/10.1007/978-3-642-35746-6_1

    doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.