Can think tokens bridge the complexity gap? A rigorous complexity-theoretic account of reasoning models' ability to exceed per-inference transformer computation

Derived from the open question posed by Sikka and Sikka in 'Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models' (2025): whether reasoning models that emit long internal 'think' token chains before answering can bridge the complexity gap between a transformer's per-inference computation of roughly $O(N^2\cdot d)$ floating-point operations (for a prompt of $N$ tokens and token-vector dimension $d$) and tasks of higher inherent computational complexity. The authors state an informal intuition that think tokens cannot bridge the gap and defer a rigorous analysis to subsequent work, which has not appeared. The idealized expressivity ladder is settled — transformers without intermediate generation lie in the small parallel class $\mathrm{TC}^0$, while $T$ decoding steps of chain-of-thought buy roughly $T$-step sequential computation, so polynomial-length reasoning captures all of $P$ but the time-hierarchy theorem bounds any finite budget. What remains open is the question as actually posed: a rigorous analysis deciding, under the correct resource accounting for autoregressive reasoning models, to what extent think-token generation bridges the complexity gap — which higher-complexity task families it can and cannot solve within a given think budget, and whether trained reasoning models realize the budget-bounded power.

Background

Hallucination in large language models (LLMs) refers to fluent but spurious, incorrect, or nonsensical output. Modern LLMs are transformer networks that generate text autoregressively: given a prompt of $N$ tokens, each subsequent token is produced by one forward pass whose dominant cost is self-attention — the mechanism that lets every token attend to every other token — requiring on the order of $O(N^2\cdot d)$ floating-point operations per pass for token representations of dimension $d$. Large reasoning models (LRMs), such as OpenAI's o3 and DeepSeek's R1, are LLMs additionally trained to emit long internal 'think' token sequences (chain-of-thought, CoT — explicit intermediate steps generated before the final answer) before responding.

Sikka and Sikka (2025), the source of this problem, argue that a prompt embedding a computational task whose inherent complexity exceeds the model's per-inference budget — for example, enumerating all length-$k$ strings over an $n$-token vocabulary, which costs $O(n^k)$, or exhaustively verifying a claimed optimal Traveling Salesperson route over $n$ cities, which requires comparing against all $(n-1)!/2$ routes — cannot be correctly carried out by the model. Their argument invokes the time-hierarchy theorem of Hartmanis and Stearns (1965), which guarantees that strictly more computation time buys strictly more decidable problems; they conclude that a fixed inference budget induces unavoidable errors, a complexity-driven form of hallucination, and that LLM-based agents likewise cannot correctly verify solutions of such tasks because verification can be inherently harder than solving. The paper then poses, but does not answer, the question that defines this problem: to what extent does a reasoning model's generation of additional think tokens bridge this complexity gap — can the additional tokens 'provide the necessary complexity to correctly solve a problem of higher complexity'? The authors give two informal reasons for skepticism (the per-step computation is unchanged, and practical think budgets are far smaller than what complex tasks require) and defer a rigorous analysis to subsequent work.

A mature formal literature brackets the idealized version of this question. Two complexity classes orient the discussion: $\mathrm{TC}^0$, the class of problems solvable by constant-depth threshold circuits (a model of highly parallel, shallow computation), and $P$, the class of problems solvable in polynomial time on a sequential machine. Merrill and Sabharwal (2022) showed that log-precision transformers — models whose arithmetic precision grows only logarithmically with the input length — that answer immediately after reading the input, without generating intermediate tokens, can only recognize languages in (uniform) $\mathrm{TC}^0$, a hard ceiling strictly below many natural serial reasoning tasks. Subsequent work established that intermediate generation strictly increases power in proportion to the number of decoding steps: transformers with $T$ chain-of-thought steps can simulate roughly $T$-step sequential computation, so logarithmic-length CoT reaches small classes such as logspace (problems solvable with logarithmic working memory), and polynomial-length CoT captures all of $P$ (Feng et al. 2023; Merrill and Sabharwal 2023; Li et al. 2024); appending blank padding tokens alone does not increase power (Merrill and Sabharwal 2025), and adding logarithmic depth yields a quantitatively characterized jump (Merrill and Sabharwal 2025, log-depth). Under these idealizations, think tokens bridge the complexity gap exactly up to the sequential computation the token budget affords — and never beyond it, by the time-hierarchy theorem.

Three gaps separate this settled idealized picture from the question actually posed. First, resource accounting: the source's $O(N^2\cdot d)$ figure counts a single inference, whereas an autoregressive model emitting $T$ think tokens performs roughly $T$ passes with a context that grows toward $N+T$ — a rigorous treatment must pin down the correct total-computation and sequential-depth accounting before 'bridging' can be decided. Second, model realism: the expressivity results are existence-of-parameters results for idealized log-precision (or real-valued) models, while deployed reasoning models are trained by supervised fine-tuning and reinforcement learning on outcome rewards, use low (8–16 bit) numerical precision, and must generalize to problem sizes beyond those seen in training — a regime where length-generalization barriers are now proven (Kraus et al. 2026), provable learning results exist only for specific tasks (Joshi et al. 2025; Huang et al. 2025), and lower bounds on the necessary CoT length for natural tasks are known only for restricted hard-attention architectures, in which each position attends to exactly one other position (Amiri et al. 2025; Yehudai et al. 2025), with low-precision softmax models only partially characterized (Brösamle and Eckstein 2026). Third, the empirical evidence that motivated the source's skepticism is contested: Shojaee et al. (2025) documented a striking accuracy collapse and a counterintuitive decline of thinking effort as puzzle complexity grows (e.g., Towers of Hanoi), but subsequent comments showed that large parts of this collapse are output-token-limit and output-parser artifacts (Lawsen 2025; Khan et al. 2025), and later mechanistic work attributes the failures to underuse of emergent internal world models rather than a complexity wall (Pereira and Zuidema 2026). Separately, learning-theoretic arguments show hallucination is inevitable on statistical and computability grounds (Xu et al. 2024) — a complementary axis to the complexity axis studied here. Whether trained reasoning models realize the computational power their token budget affords — the question the source actually asks — remains without a rigorous answer.

Problem Statement

Sikka and Sikka (2025) ask: to what extent does the generation of additional 'think' tokens by reasoning models bridge the complexity gap between a transformer's per-inference computation (roughly $O(N^2\cdot d)$ floating-point operations for prompt length $N$ and token-vector dimension $d$) and computational tasks of higher inherent complexity embedded in the prompt — and can the additional think tokens provide the necessary computation to correctly solve such problems? The authors defer rigorous analysis; the open problem is to deliver it, at the question's full generality, as one coherent account encompassing:

1. Resource accounting. Formalize the computation of an autoregressive reasoning model — a transformer of dimension $d$ that, given a prompt of $N$ tokens, emits at most $T$ think tokens before its answer, with the context growing during generation and arithmetic at a specified finite precision — and settle the correct total-computation and sequential-depth accounting that replaces the per-inference $O(N^2\cdot d)$ figure under which the 'complexity gap' is defined.

2. Characterization. For that model, characterize which task families become correctly solvable as a function of the think-token budget $T$, the dimension $d$, and the numerical precision — with matching upper bounds (budgets that suffice, e.g., by explicit simulation of sequential algorithms) and lower bounds (budgets provably necessary). The task families the characterization must cover are fixed as: (a) exhaustive enumeration of all length-$k$ strings over an $n$-token vocabulary; (b) exhaustive verification of a claimed optimal Traveling Salesperson route over $n$ cities; and (c) the serial-composition, arithmetic, and dynamic-programming families whose necessary chain-of-thought length is the subject of the existing hard-attention lower-bound results (Amiri et al. 2025; Yehudai et al. 2025). This item is resolved once, for each listed family, either matching upper and lower bounds are established or it is shown that the family lies outside the model class fixed in part 1; covering further families is welcome but not required. In particular, determine for which of the listed task families the think-token mechanism provably bridges, and provably cannot bridge, the complexity gap identified in the source.

3. Realized power of trained reasoning models. Because the question is posed about deployed systems such as o3 and R1 rather than idealized constructions alone, address whether models trained by standard procedures (supervised fine-tuning and reinforcement learning on outcome rewards) actually realize the budget-bounded power from part 2. The item admits two answer forms, and an unsupported or citation-only discussion discharges neither: (i) a learning-theoretic result — a guarantee or an impossibility — for a stated model class, training procedure, and data distribution, under which the part-2 power is or is not attained; or (ii) an empirical protocol that pre-declares the model class, training procedure, task distribution, and success criterion, reported together with positive or negative evidence obtained under it. Either form must state the training regime and the numerical precision to which the claim applies.

References

1. Varin Sikka and Vishal Sikka (2025). Hallucination Stations: On Some Basic Limitations of Transformer-Based Language Models. arXiv:2507.07505, DOI 10.48550/arxiv.2507.07505. https://arxiv.org/abs/2507.07505
2. J. Hartmanis and R. E. Stearns (1965). On the computational complexity of algorithms. Transactions of the American Mathematical Society 117, 285-306. DOI 10.1090/S0002-9947-1965-0170805-7. https://doi.org/10.1090/S0002-9947-1965-0170805-7
3. William Merrill and Ashish Sabharwal (2022). The Parallelism Tradeoff: Limitations of Log-Precision Transformers. arXiv:2207.00729. https://arxiv.org/abs/2207.00729
4. William Merrill and Ashish Sabharwal (2023). The Expressive Power of Transformers with Chain of Thought. arXiv:2310.07923 (ICLR 2024). https://arxiv.org/abs/2310.07923
5. Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang (2023). Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective. arXiv:2305.15408 (NeurIPS 2023). https://arxiv.org/abs/2305.15408
6. Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma (2024). Chain of Thought Empowers Transformers to Solve Inherently Serial Problems. arXiv:2402.12875 (ICLR 2024). https://arxiv.org/abs/2402.12875
7. Ziwei Xu, Sanjay Jain, and Mohan Kankanhalli (2024). Hallucination is Inevitable: An Innate Limitation of Large Language Models. arXiv:2401.11817. https://arxiv.org/abs/2401.11817
8. Parshin Shojaee, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, and Mehrdad Farajtabar (2025). The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity. arXiv:2506.06941 (NeurIPS 2025). https://arxiv.org/abs/2506.06941
9. A. Lawsen (2025). Comment on The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity. arXiv:2506.09250. https://arxiv.org/abs/2506.09250
10. Sheraz Khan, Subha Madhavan, and Kannan Natarajan (2025). A Comment On 'The Illusion of Thinking': Reframing the Reasoning Cliff as an Agentic Gap. arXiv:2506.18957. https://arxiv.org/abs/2506.18957
11. William Merrill and Ashish Sabharwal (2025). A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers. arXiv:2503.03961 (NeurIPS 2025). https://arxiv.org/abs/2503.03961
12. William Merrill and Ashish Sabharwal (2025). Exact Expressive Power of Transformers with Padding. arXiv:2505.18948 (NeurIPS 2025). https://arxiv.org/abs/2505.18948
13. Alireza Amiri, Xinting Huang, Mark Rofin, and Michael Hahn (2025). Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers. arXiv:2502.02393 (ICML 2025). https://arxiv.org/abs/2502.02393
14. Gilad Yehudai, Noah Amsel, and Joan Bruna (2025). Compositional Reasoning with Transformers, RNNs, and Chain of Thought. arXiv:2503.01544 (NeurIPS 2025), DOI 10.52202/085713-1825. https://arxiv.org/abs/2503.01544
15. Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro (2025). A Theory of Learning with Autoregressive Chain of Thought. arXiv:2503.07932. https://arxiv.org/abs/2503.07932
16. Yu Huang, Zixin Wen, Aarti Singh, Yuejie Chi, and Yuxin Chen (2025). Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization. arXiv:2511.07378 (NeurIPS 2025), DOI 10.52202/085713-4230. https://arxiv.org/abs/2511.07378
17. Oliver Kraus, Yash Sarrof, Yuekun Yao, Alexander Koller, and Michael Hahn (2026). Barriers to Universal Reasoning With Transformers (And How to Overcome Them). arXiv:2604.25800 (COLM 2026). https://arxiv.org/abs/2604.25800
18. Moritz Brösamle and Stephan Eckstein (2026). The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought. arXiv:2605.18079 (ICML 2026). https://arxiv.org/abs/2605.18079
19. Devin Pereira and Willem Zuidema (2026). Transformers Struggle to Use Their Emergent World Models: Revisiting the Tower of Hanoi, and the Illusion of Thinking. arXiv:2608.07077. https://arxiv.org/abs/2608.07077