Does the $O(N^2 \cdot d)$ computational complexity of Transformers pose a...

taco_truck_tom

I recently came across a preprint paper titled "H allucination Stations: On Some Basic Limitations of Transformer-Based Language Models " by Varin Sikka and Vishal Sikka ( https://arxiv.org/abs/2507.07505 ).The preprint argues that hallucinations are not just training flaws, but a mathematical necessity when the task's complexity exceeds the model's architecture. The core argument is based on the computational complexity of the Transformer's...

Originally asked by Humberto José Bortolossi on Stack Exchange (ai) (CC BY-SA 4.0).

uphilltech

Great question — answering as the UphillTech team:

It can be tempting to describe a Transformer as a machine with one dominant cost, and to treat that cost as the model’s limit on reasoning. In the standard implementation, full attention scales roughly like the square of the sequence length, and that matters for speed. Still, a runtime formula for one forward pass is not the same thing as a complexity bound in the sense used by theory. Note also that Chain of Thought (CoT) changes the picture because it turns the model into an iterative process. Each new token is not only an output. It also becomes part of the next input, so it can act like a scratchpad. If you allow more reasoning tokens, you allow more sequential steps of computation....

Full answer by Sanchayan Dutta: https://ai.stackexchange.com/a/50327 (CC BY-SA 4.0).

Need it done for your business? UphillTech.