CoChat
Sign Up
Cited by 53Topic ModelingNatural Language Processing TechniquesLogic, Reasoning, and Knowledge

The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity

Open access
Shojaee, Parshin, Mirzadeh, Iman, Alizadeh vahid, Keivan, Horton, Maxwell, Bengio, Samy, Farajtabar, Mehrdad·2025·Advances in Neural Information Processing Systems 38
DOI 10.52202/085713-3603
Open this paper in CoChat — free accountOpen PDF

Abstract

Recent generations of language models have introduced Large Reasoning Models (LRMs) that generate detailed thinking processes before providing answers. While these models demonstrate improved performance on reasoning benchmarks, their fundamental capabilities, scaling properties, and limitations remain insufficiently understood. Current evaluations primarily focus on established math and coding benchmarks, emphasizing final answer accuracy. However, this evaluation paradigm often suffers from contamination and does not provide insights into the reasoning traces. In this work, we systematically investigate these gaps with the help of controllable puzzle environments that allow precise manipulation of complexity while maintaining consistent logical structures. This setup enables the analysis of not only final answers but also the internal reasoning traces, offering insights into how LRMs think. Through extensive experiments, we show that LRMs face a complete accuracy collapse beyond certain complexities. Moreover, they exhibit a counterintuitive scaling limit: their reasoning effort increases with problem complexity up to a point, then declines despite having remaining token budget. By comparing LRMs with their standard LLM counterparts under same inference compute, we identify three performance regimes: (1) low-complexity tasks where standard models outperform LRMs, (2) medium-complexity tasks where LRMs demonstrates advantage, and (3) high-complexity tasks where both models face complete collapse. We found that LRMs have limitations in exact computation: they fail to use explicit algorithms and reason inconsistently across scales. We also investigate the reasoning traces in more depth, studying the patterns of explored solutions and analyzing the models' computational behavior, shedding light on their strengths, limitations, and raising questions about their reasoning capabilities.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper uses controllable puzzle environments to test frontier large reasoning models (LRMs) across problem complexity, finding three regimes: non-thinking models win at low complexity, thinking models win at medium complexity, and both collapse at high complexity. It also reports a counterintuitive decline in reasoning effort near collapse and limitations in exact algorithmic execution.

Key findings

  • Across puzzles, the authors identify three regimes: at low complexity, non-thinking models are more accurate and token-efficient; at medium complexity, thinking models gain an advantage; at high complexity, both model types collapse to near-zero accuracy.
  • Reasoning models initially increase thinking tokens with complexity, but after a model-specific threshold they counterintuitively reduce reasoning effort despite ample token budget, suggesting an inference-time scaling limit.
  • Providing the explicit solution algorithm does not improve performance on Tower of Hanoi or Checker Jumping; collapse occurs at roughly the same points, indicating limitations in executing prescribed logical steps.
  • Trace analysis shows complexity-dependent patterns: “overthinking” on simple problems, correct solutions emerging later after incorrect exploration at medium complexity, and fixation on early errors at high complexity. For example, Tower of Hanoi with N≈10 requires ∼10³ moves but first failure typically occurs within ∼100 moves (10% of solution length); River Crossing with N=3 requires 11 moves but first failure can occur as early as move 4.

Methods

  • Controlled puzzle environments: Tower of Hanoi, Checker Jumping, River Crossing, and Blocks World, with complexity manipulated by problem size N; custom simulators validate each move and final goal state.
  • Models and setup: Claude 3.7 Sonnet (thinking/non-thinking), DeepSeek-R1/V3, o3-mini, DeepSeek-R1-Distill-Qwen-32B, and QwQ-32B vs Qwen2.5-32B; 25 samples per puzzle instance and complexity level; maximum generation budget up to 64k tokens; default temperature 1.0 for API runs.
  • Analysis: compare pass@k under equivalent inference compute, accuracy and thinking-token usage versus complexity, intermediate solution positions and correctness within reasoning traces, and first failure move across models and puzzles.

Limitations

  • Stated in the paper: the puzzle environments represent a narrow slice of reasoning tasks and may not capture real-world or knowledge-intensive reasoning; most experiments rely on black-box API access to closed frontier LRMs, limiting mechanistic analysis; deterministic simulators assume step-by-step validation that may not transfer to less structured domains.
  • Evident from the text: the study covers only four puzzle families and primarily closed models; the authors also note that model difficulty may reflect training-data familiarity rather than intrinsic computational complexity, which complicates cross-puzzle comparisons.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.52202/085713-3603

Cites

0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

14 of 20 cited sources checked · 7 supported · 0 flagged · accuracy not yet measured

  • Premisecitation
    § 3 Math and Puzzle Environments · p. 5

    Recent studies have shown that under equivalent inference token budgets, non-thinking LLMs can eventually reach performance comparable to thinking models on benchmarks like MATH500 and AIME24.

    “Recent studies [35, 41] have explored this question with established math benchmarks by comparing the upper-bound capabilities (pass@k) of RL-based reasoning (thinking) models with their non-reasoning (non-thinking) standard LLM counterparts. They have shown that under equivalent inference token budgets, non-thinking LLMs can eventually reach performance comparable to thinking models on benchmarks”
    Quote in the paperSubstantial claim3 of 4 sources checked
    • cites [35] [35] Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Shiji Song, and Gao Huang. Does reinforcement learning really incentivize reasoning capacity in llms beyond the base model? arXiv preprint arXiv:2504.13837 , 2025. - source

      Section 3.1 (p. 6) reports that base models catch up to and eventually surpass RL-trained models as pass@k increases, including in comparisons covering MATH500 and AIME24. The evaluation protocol (p. 5) uses the same maximum generation length for both, but the paper compares equal numbers of samples, not explicitly equivalent total inference-token budgets; that qualifier is not established. (LLM, conf=0.85)

      Experimental — accuracy not yet measured
    • cites [41] [41] Wenjie Ma, Jingxuan He, Charlie Snell, Tyler Griggs, Sewon Min, and Matei Zaharia. Reasoning models can be effective without thinking. arXiv preprint arXiv:2504.09858 , 2025. - source

      Section 3.3 and the ‘Thinking vs. NoThinking’ results support comparable or better pass@k performance under controlled token budgets for NoThinking, which prompts the same reasoning model to skip explicit thinking. They do not establish that a separate standard LLM reaches comparable performance: Section 3.3 says both reasoning-model modes significantly outperform the Qwen-Instruct baseline on AIME 2024. The cited results also do not identify MATH500 as a benchmark. (LLM, conf=0.87)

      Experimental — accuracy not yet measured
    • cites [42] [42] Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint arXiv:2305.20050 , 2023. - source

      Section 3 (Large-scale Supervision) compares process-supervised and outcome-supervised reward models as they search over increasing numbers of solutions; Appendix C describes evaluation on 500 held-out MATH problems. Neither passage compares thinking with non-thinking LLMs under equivalent inference-token budgets or reports comparable performance on MATH500 and AIME24 (searched: pass@k, inference budget, MATH500, AIME24). (LLM, conf=0.76)

      Experimental — accuracy not yet measured
    • cites [43] [43] Mathematical Association of America. American invitational mathematics examination (aime). https://maa.org/math-competitions/ american-invitational-mathematics-examination-aime , 2025. Accessed: 2025-05-15. -

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Findingnone given
    § 4.3 What Happens Inside the Thoughts of Reasoning Models? · p. 10

    For more complex problems, solution accuracy increases with thinking progression up to a certain threshold.

    “However, this trend changes for more complex problems, where solution accuracy increases with thinking progression-up to a certain threshold.”
    Quote in the paperSubstantial claim
  • Findingown data
    § 4.4 Open Questions: Puzzling Behavior of Reasoning Models · p. 11

    Models exhibit inconsistencies in how they apply learned solution strategies across different problems and scales.

    “we observe inconsistencies in how models apply learned solution strategies across different problems and scales.”
    Quote in the paperSubstantial claim
  • Findingown data
    § Abstract · p. 1

    LRMs exhibit a counterintuitive scaling limit: their reasoning effort increases with problem complexity up to a point, then declines despite having an adequate token budget.

    “they exhibit a counterintuitive scaling limit: their reasoning effort increases with problem complexity up to a point, then declines despite having an adequate token budget.”
    • Also stated in: § LLM Response · p. 3 · plain
      “near this collapse point, LRMs begin reducing their reasoning effort (measured by inference-time thinking tokens) as problem complexity increases, despite operating well below generation length limits”
    • Also stated in: § 5 Conclusion · p. 12 · plain
      “counterintuitive reduction in reasoning effort as problems approach critical complexity”
    Quote in the paperSubstantial claim
  • Findingown data
    § 4.2.2 Collapse of Reasoning Models · p. 8

    All reasoning models exhibit a similar pattern with respect to complexity: accuracy progressively declines as problem complexity increases until reaching collapse (near-zero accuracy) beyond a model-specific complexity threshold.

    “Results show that all reasoning models exhibit a similar pattern with respect to complexity: accuracy progressively declines as problem complexity increases until reaching collapse (near-zero accuracy) beyond a model-specific complexity threshold.”
    Quote in the paperSubstantial claim
  • Classified as probably not a substantial claim. 20
  • May combine two claims. 39
  • The quote only partly states this claim. 2

  • Classified as probably not a substantial claim. May combine two claims.

    Premisecitation
    § 2 Related Works · p. 4

    Large Reasoning Models have shown emergent behaviors such as discrepancy between thought traces and final answers and efficiency concerns through the 'overthinking phenomenon'.

    “Large Reasoning Models have shown emergent behaviors such as discrepancy between thought traces and final answers [28, 29] as well as efficiency concerns through what researchers term the 'overthinking phenomenon' [30, 31, 32, 33]”
    Quote in the paperSubstantial claim6 of 6 sources checked
    • cites [28] [28] Yanda Chen, Joe Benton, Ansh Radhakrishnan, Jonathan Uesato, Carson Denison, John Schulman, Arushi Somani, Peter Hase, Misha Wagner, Fabien Roger, et al. Reasoning models don't always say what they think. arXiv preprint arXiv:2505.05410 , 2025. - source
    • cites [29] [29] Dacheng Li, Shiyi Cao, Tyler Griggs, Shu Liu, Xiangxi Mo, Eric Tang, Sumanth Hegde, Kourosh Hakhamaneshi, Shishir G Patil, Matei Zaharia, et al. Llms can easily learn to reason from demonstrations structure, not content, is what matters! arXiv preprint arXiv:2502.07374 , 2025. - source

      The Introduction describes long chains of thought, and the Shuffled reasoning steps section reports incoherent reasoning after training on reordered traces. Neither passage establishes a discrepancy between thought traces and final answers or identifies an efficiency concern called the “overthinking phenomenon.” Searches for both points found no supporting passage in our copy. (LLM, conf=0.72)

      Experimental — accuracy not yet measured
    • cites [30] [30] Xingyu Chen, Jiahao Xu, Tian Liang, Zhiwei He, Jianhui Pang, Dian Yu, Linfeng Song, Qiuzhi Liu, Mengfei Zhou, Zhuosheng Zhang, et al. Do not think that much for 2+ 3=? on the overthinking of o1-like llms. arXiv preprint arXiv:2412.21187 , 2024. - source
    • cites [31] [31] Yang Sui, Yu-Neng Chuang, Guanchu Wang, Jiamu Zhang, Tianyi Zhang, Jiayi Yuan, Hongyi Liu, Andrew Wen, Hanjie Chen, Xia Hu, et al. Stop overthinking: A survey on efficient reasoning for large language models. arXiv preprint arXiv:2503.16419 , 2025. -
    • cites [32] [32] Sara Vera Marjanović, Arkil Patel, Vaibhav Adlakha, Milad Aghajohari, Parishad BehnamGhader, Mehar Bhatia, Aditi Khandelwal, Austin Kraft, Benno Krojer, Xing Han Lù, et al. Deepseek-r1 thoughtology: Let's< think> about llm reasoning. arXiv preprint arXiv:2504.07128 , 2025. - source
    • cites [33] [33] Yuxiao Qu, Matthew YR Yang, Amrith Setlur, Lewis Tunstall, Edward Emanuel Beeching, Ruslan Salakhutdinov, and Aviral Kumar. Optimizing test-time compute via meta reinforcement fine-tuning. arXiv preprint arXiv:2503.07572 , 2025. - source

  • Classified as probably not a substantial claim.

    Premisecitation
    § 2 Related Works · p. 4

    Recent works have demonstrated that in newer LRMs accuracy generally declines when thinking increases in math problems.

    “Recent works [34, 33, 32] have demonstrated that in newer LRMs accuracy generally declines when thinking increases in math problems”
    Quote in the paperSubstantial claim2 of 3 sources checked
    • cites [34] [34] Marthe Ballon, Andres Algaba, and Vincent Ginis. The relationship between reasoning and performance in large language models-o3 (mini) thinks harder, not longer. arXiv preprint arXiv:2502.15631 , 2025. - source
    • cites [33] [33] Yuxiao Qu, Matthew YR Yang, Amrith Setlur, Lewis Tunstall, Edward Emanuel Beeching, Ruslan Salakhutdinov, and Aviral Kumar. Optimizing test-time compute via meta reinforcement fine-tuning. arXiv preprint arXiv:2503.07572 , 2025. - source

      Not checked in the free run.

    • cites [32] [32] Sara Vera Marjanović, Arkil Patel, Vaibhav Adlakha, Milad Aghajohari, Parishad BehnamGhader, Mehar Bhatia, Aditi Khandelwal, Austin Kraft, Benno Krojer, Xing Han Lù, et al. Deepseek-r1 thoughtology: Let's< think> about llm reasoning. arXiv preprint arXiv:2504.07128 , 2025. - source

      Section 12.2 reports that, for Qwen3 and gpt-oss on math benchmarks, accuracy rises as thought length increases, reaches a maximum, and then falls with longer thoughts. The claim captures the decline after that sweet spot but omits the initial increase, making a general decline sound too broad. (LLM, conf=0.88)

      Experimental — accuracy not yet measured

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation
    § 2 Related Works · p. 4

    Two closely related studies demonstrated that reasoning models such as o1 show significant performance improvements compared to previous models on puzzles and decision-making tasks.

    “Two closely related studies by Valmeekam et al. [40] and Ruoss et al. [39] demonstrated that reasoning models such as o1 show significant performance improvements compared to previous models on puzzles and decision-making tasks.”
    Quote in the paperNot a substantial claim1 of 2 sources checked
    • cites [40] [40] Karthik Valmeekam, Kaya Stechly, and Subbarao Kambhampati. Llms still can't plan; can lrms? a preliminary evaluation of openai's o1 on planbench. 2024. - source
    • cites [39] [39] Anian Ruoss, Fabio Pardo, Harris Chan, Bonnie Li, Volodymyr Mnih, and Tim Genewein. Lmact: A benchmark for in-context imitation learning with long multimodal demonstrations. arXiv preprint arXiv:2412.01441 , 2024. - source

      Sections 3.1 and 3.2 report that o1 models performed especially well on simple crosswords and tic-tac-toe compared with other evaluated models. The claim overgeneralizes those results to puzzles and decision-making tasks broadly: Section 3.2 also reports that the models almost always lost at chess, with GPT-4o performing best in that setting. (LLM, conf=0.87)

      Experimental — accuracy not yet measured

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation
    § A.2.4 Blocks World · p. 25

    The Blocks World puzzle design is motivated by recent works [40, 49] but is set to be more challenging for recent reasoning models, requiring more disassembly and reassembly of stacks.

    “Our design of this puzzle is motivated by recent works in literature [40, 49], but it's set to be more challenging for the recent reasoning models requiring more disassembly and reassembly of the stacks (eg. alternating between blocks from different stacks to reach target).”
    Quote in the paperNot a substantial claim1 of 2 sources checked
    • cites [40] [40] Karthik Valmeekam, Kaya Stechly, and Subbarao Kambhampati. Llms still can't plan; can lrms? a preliminary evaluation of openai's o1 on planbench. 2024. - source
    • cites [49] [49] Xinran Zhao, Hanie Sedghi, Bernd Bohnet, Dale Schuurmans, and Azade Nova. Improving large language model planning with action sequence similarity. arXiv preprint arXiv:2505.01009 , 2025. - source

  • Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

    Premisecitation
    § 2 Related Works · p. 4

    Yue et al. have questioned whether reinforcement learning elicits novel reasoning patterns, observing that the pass@k performance of reasoning and non-reasoning models ultimately converge with larger samples.

    “Yue et al. [35] have questioned whether reinforcement learning elicits novel reasoning patterns, observing that the pass@k performance of reasoning and non-reasoning models ultimately converge with larger samples.”
    Quote in the paperNot a substantial claim1 of 1 sources checked
    • cites [35] [35] Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Shiji Song, and Gao Huang. Does reinforcement learning really incentivize reasoning capacity in llms beyond the base model? arXiv preprint arXiv:2504.13837 , 2025. - source

      The Introduction (p. 3) and Conclusion (p. 12) support the claim that current reinforcement-learning methods rarely elicit fundamentally new reasoning patterns. But the Results (Section 3.1, p. 6) say base models catch up to and eventually surpass RL-trained models as k increases, rather than ultimately converging with them. (LLM, conf=0.90)

      Experimental — accuracy not yet measured

  • May combine two claims.

    Findingown data
    § LLM Response · p. 3

    Under equivalent inference compute, comparing LRMs with standard LLM counterparts reveals three performance regimes: low complexity standard models outperform LRMs; medium complexity additional thinking in LRMs demonstrates advantage; high complexity both models experience complete collapse.

    “our comparison between LRMs and standard LLMs under equivalent inference token compute reveals three distinct reasoning regimes”
    • Also stated in: § 5 Conclusion · p. 12 · plain
      “We identified three distinct reasoning regimes: standard LLMs outperform LRMs at low complexity, LRMs show advantage at moderate complexity, and both collapse at high complexity.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.3 What Happens Inside the Thoughts of Reasoning Models? · p. 10

    For problems with higher complexity, collapse emerges: the model fails to recover any correct solutions within the thought and often fixates on early incorrect solutions, wasting the remaining thought token budget.

    “Finally, for the problems with higher complexity, collapse emerges, meaning that the model fails to recover any correct solutions within the thought and it often fixates on an early incorrect solutions, wasting the remaining thought token budget.”
    Quote in the paperSubstantial claim

  • The quote only partly states this claim.

    Findingown data
    § 4.3 What Happens Inside the Thoughts of Reasoning Models? · p. 10

    For simpler problems, reasoning models often find the correct solution early in their thinking but then continue exploring incorrect solutions (overthinking), leading to waste of compute.

    “For simpler problems, reasoning models often find the correct solution early in their thinking but then continue exploring incorrect solutions.”
    • Also stated in: § 4.3 What Happens Inside the Thoughts of Reasoning Models? · p. 10 · plain
      “This phenomenon, referred to as 'overthinking' in the literature, leads to the waste of compute.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.2.2 Collapse of Reasoning Models · p. 8

    The phenomenon of reducing reasoning effort near collapse is most pronounced in o3-mini variants and less severe in Claude-3.7-Sonnet (thinking).

    “This phenomenon is most pronounced in o3-mini variants and less severe in the Claude-3.7-Sonnet (thinking) model.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.2.2 Collapse of Reasoning Models · p. 8

    Reasoning models initially increase their thinking tokens proportionally with problem complexity; upon approaching a critical threshold corresponding to their accuracy collapse point, they counterintuitively begin to reduce their reasoning effort despite increasing problem complexity.

    “We observe that reasoning models initially increase their thinking tokens proportionally with problem complexity. However, upon approaching a critical threshold-which closely corresponds to their accuracy collapse point-models counterintuitively begin to reduce their reasoning effort despite increasing problem complexity.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § Abstract · p. 1

    LRMs have limitations in exact computation: they fail to use explicit algorithms and reason inconsistently across scales and problems.

    “We found that LRMs have limitations in exact computation: they fail to use explicit algorithms and reason inconsistently across scales and problems.”
    • Also stated in: § LLM Response · p. 4 · plain
      “We uncover surprising behaviors in LRMs' ability to perform exact computation, including their failure to benefit from explicit algorithms and their inconsistent reasoning across problems and scales.”
    • Also stated in: § 5 Conclusion · p. 12 · plain
      “we observed their limitations in performing exact computation; for example, when we provided the solution algorithm of puzzle to the models, their performance on this puzzle did not improve.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.2.1 Three Regimes of Complexity · p. 8

    In high-complexity problems, the performance of both thinking and non-thinking models collapses to zero; thinking models delay this collapse but ultimately encounter the same fundamental limitations.

    “The most interesting regime is the third regime where problem complexity is higher and the performance of both models have collapsed to zero. Results show that while thinking models delay this collapse, they also ultimately encounter the same fundamental limitations as their non-thinking counterparts.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.4 Open Questions: Puzzling Behavior of Reasoning Models · p. 11

    The model achieves near-perfect accuracy when solving Tower of Hanoi with N=5 (31 moves), while it fails to solve River Crossing puzzle when N=3 (11 moves).

    “Note that this model also achieves near-perfect accuracy when solving the Tower of Hanoi with (N=5), which requires 31 moves, while it fails to solve the River Crossing puzzle when (N=3), which has a solution of 11 moves.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.2.1 Three Regimes of Complexity · p. 8

    In medium-complexity problems, the advantage of reasoning models capable of generating long chain-of-thought begins to manifest, and the performance gap between model pairs increases.

    “In the second regime with medium complexity, the advantage of reasoning models capable of generating long chain-of-thought begin to manifest, and the performance gap between model pairs increases.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 3 Math and Puzzle Environments · p. 5

    The performance gap between thinking and non-thinking models slightly widens on AIME24 and widens further on AIME25.

    “However, we observed that this performance gap slightly widens on the AIME24 benchmark and widens further on AIME25.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § 4.4 Open Questions: Puzzling Behavior of Reasoning Models · p. 11

    In Tower of Hanoi, failure happens at below 50 moves for N=12 but the model succeeds through more than 100 moves for N=10.

    “For example, Figure 9 shows that in Tower of Hanoi, failure happens at below 50 moves for N = 12 but the model succeeds through more than 100 moves for N = 10”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingown data
    § 4.4 Open Questions: Puzzling Behavior of Reasoning Models · p. 11

    Models sometimes exhibit non-monotonic failure behavior with respect to problem complexity: they fail earlier in the solution sequence for higher N values despite requiring longer overall solutions.

    “Sometimes, models exhibit a non-monotonic failure behavior with respect to problem complexity-instances where models fail earlier in the solution sequence for higher N values despite requiring longer overall solutions.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 4.4 Open Questions: Puzzling Behavior of Reasoning Models · p. 11

    Even when provided the algorithm in the prompt so that the model only needs to execute prescribed steps, performance does not improve, and collapse still occurs at roughly the same point in Tower of Hanoi and Checker Jumping.

    “As shown in Figure 8, in the Tower of Hanoi and Checker Jumping puzzle environments, even when we provide the algorithm in the prompt-so that the model only needs to execute the prescribed steps-performance does not improve, and the observed collapse still occurs at roughly the same point on both puzzle environments.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § A.6 Extended Results and Analysis · p. 32

    Removing sampling (temperature zero) does not prevent collapse; failure occurs at roughly the same points across all puzzles, including Tower of Hanoi.

    “The results demonstrate that removing sampling does not prevent collapse-we observe failure at roughly the same points across all puzzles, including Tower of Hanoi.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § A.4.2 Performance vs Compositional Depth · p. 31

    Across different puzzle types, the negative correlation between compositional depth and model accuracy does not hold; models may struggle with puzzles of lower compositional depth while succeeding on different puzzles with higher compositional depth.

    “However, across different puzzle types, this relation does not hold. Models may struggle with puzzles of lower compositional depth while succeeding on different puzzles with higher compositional depth.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based). May combine two claims.

    Findingnone given
    § A.2.4 Blocks World · p. 26

    As the number of blocks N increases in Blocks World, the state space grows factorially and the minimum solution length increases approximately linearly.

    “As N increases, the state space grows factorially, and the minimum solution length increases approximately linearly.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § A.6 Extended Results and Analysis · p. 32

    In Blocks World, DeepSeek-R1 with temperature 0 collapses at N=4, whereas with sampling enabled it maintains 44.1% accuracy at N=4 and delays collapse until N=30.

    “In Blocks World also the R1 model with temperature 0 collapses at N=4, whereas with sampling enabled, it maintains 44.1% accuracy at N=4 and delays collapse until N=30.”
    Quote in the paperSubstantial claim

  • The quote only partly states this claim.

    Findingown data
    § Question: Does River Crossing with N ≥ 6 invalidate our core findings on this puzzle? · p. 20

    Results in Figure 8 show very similar patterns for both Tower of Hanoi and Checker Jumping puzzles when given explicit algorithm steps.

    “However, our results in Figure 8 show very similar patterns for both puzzles.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § A.6 Extended Results and Analysis · p. 32

    In Tower of Hanoi, DeepSeek-R1 with temperature 0 collapses at N=8, whereas with sampling enabled it maintains 18.2% accuracy at N=8 and delays collapse until N=9.

    “For instance, in Tower of Hanoi, the R1 model with temperature 0 collapses at N=8, whereas with sampling enabled, it maintains 18.2% accuracy at N=8 and delays collapse until N=9.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § A.6 Extended Results and Analysis · p. 34

    Providing explicit solving algorithms to both reasoning (DeepSeek-R1) and non-reasoning (DeepSeek-V3) models does not change their collapse points, despite modest accuracy gains at certain complexity levels.

    “As shown in Figure 17, both reasoning (DeepSeek-R1) and non-reasoning (DeepSeek-V3) models demonstrate unchanged collapse points despite modest accuracy gains from algorithm provision at certain complexity levels.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § A.6 Extended Results and Analysis · p. 33

    The distribution shape of thinking models mostly shows higher variance in failure patterns, suggesting that while these models can reach deeper into solution sequences on average, their reasoning processes seem more unstable and prone to inconsistent performance.

    “However, the distribution shape of thinking models mostly show higher variance in the failure patterns. This suggests that while these models can reach deeper into solution sequences on average, their reasoning processes seem to be more instable and prone to inconsistent performance.”
    Quote in the paperNot a substantial claim
    • Rests on an assumption: The intermediate reasoning traces (thinking tokens) provided by the models accurately reflect their internal reasoning processes.

  • Probably not a substantial claim: may not pass S4 (based).

    Findingown data
    § Question: Are failures on Tower of Hanoi due to context limit issues rather than reasoning limitations? · p. 19

    Model failures observed in the experiments occur within the context limits in all puzzles.

    “Our empirical evidence demonstrates that model failures observed in experiments occur within the context limits in all puzzles.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § A.6 Extended Results and Analysis · p. 31

    For the QwQ-32B/Qwen2.5-32B pair, collapse points occur around N = 7 for Tower of Hanoi, N = 2 for Checker Jumping, N = 10 for Blocks World, and N = 3 for River Crossing.

    “Quantitatively, the collapse points occur around N = 7 for Tower of Hanoi, N = 2 for Checker Jumping, N = 10 for Blocks World, and N = 3 for River Crossing.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § A.6 Extended Results and Analysis · p. 31

    The Qwen backbone family (QwQ-32B vs Qwen2.5-32B) exhibits similar trends to DeepSeek-R1 vs V3 and Claude-3.7-Sonnet pairs, with three distinct regimes of reasoning behavior with respect to problem complexity.

    “As shown in Figure 12, this additional model pair exhibits similar trends with those observed for the DeepSeek-R1 vs V3 and Claude-3.7-Sonnet (w./w.o. thinking) pairs. Specifically, three distinct regimes of reasoning behavior emerge with respect to problem complexity.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § 2 Related Works · p. 4

    In math datasets like MATH-500, pass@k is close for reasoning versus non-reasoning models, but different patterns are observed under medium and high complexity of puzzles.

    “We also observe that in math datasets like MATH-500, pass@k is close for reasoning versus non-reasoning models but we observed different patterns under medium and high complexity of puzzles, which is not easily observable on established math benchmarks used in common evaluations.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § A.4.2 Performance vs Compositional Depth · p. 31

    Models achieve >50% accuracy on Tower of Hanoi instances requiring approximately 10^2 moves, yet consistently fail on River Crossing or Cross Jumping puzzles with substantially lower compositional depth (~10^1 moves).

    “For instance, models achieve >50% accuracy on Tower of Hanoi instances requiring approximately ∼ 10 2 moves, yet consistently fail on River Crossing or Cross Jumping puzzles with substantially lower compositional depth ( ∼ 10 1 moves).”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § A.6 Extended Results and Analysis · p. 33

    For Tower of Hanoi with N=10, which requires ~10^3 moves, the first failure move typically occurs ~10^2 moves (approximately 10% of solution length); for N=8, which requires 255 moves, the first failure typically occurs around move 50 (approximately 20% of solution length).

    “For example, the Tower of Hanoi with N=10 requires ∼ 10 3 moves, but the first failure move typically occurs ∼ 10 2 moves (approximately 10% of the solution length), or N=8 requires 255 moves to complete, but the first failure move typically occurs around move 50 (approximately 20% of the solution length).”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Findingnone given
    § A.4.2 Performance vs Compositional Depth · p. 31

    The search space for a valid 11-move (N=3) River Crossing solution is vastly smaller than the search space for a 255-move (N=8) Tower of Hanoi solution.

    “The search space for a valid 11-move (N=3) River Crossing solution is vastly smaller than the search space for a 255-move (N=8) Tower of Hanoi solution where models start to struggle.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data
    § A.5 Inference Compute vs Compositional Depth · p. 31

    Compute allocation across puzzles is not monotonic with respect to compositional depth; models sometimes spend more tokens on problems with lower compositional depth and vice versa.

    “Interestingly, compute allocation across puzzles is not monotonic with respect to compositional depth. We also observe inconsistent compute allocation across puzzles, with models sometimes spending more tokens on problems with lower compositional depth and vice versa”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationnone given
    § 4.4 Open Questions: Puzzling Behavior of Reasoning Models · p. 11

    The search space for a valid 11-move (N=3) River Crossing solution is vastly smaller than the search space for a 255-move (N=8) Tower of Hanoi solution where models begin to fail.

    “The search space for a valid 11-move (N=3) River Crossing solution is vastly smaller than the search space for a 255-move (N=8) Tower of Hanoi solution where models begin to fail.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning
    § 3 Math and Puzzle Environments · p. 5

    Models perform worse on AIME25 than AIME24, suggesting potential for some degree of data contamination in the training of frontier LRMs.

    “Yet models perform worse on AIME25 than AIME24-suggesting potential for some degree of data contamination in the training of frontier LRMs.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning
    § 4.4 Open Questions: Puzzling Behavior of Reasoning Models · p. 11

    How LRMs approach complexity does not necessarily correspond to the actual computational complexity of the problem and more to the learned solution distributions.

    “How they approach complexity does not necessarily corresponds to the actual computational complexity of the problem and more to the learned solution distributions.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Interpretationcitation
    § 3 Math and Puzzle Environments · p. 5

    AIME25 might be less complex than AIME24.

    “Interestingly, human performance on AIME25 was actually higher than on AIME24 [44, 45], suggesting that AIME25 might be less complex.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning
    § 4.4 Open Questions: Puzzling Behavior of Reasoning Models · p. 11

    Examples of River Crossing puzzle with larger N are likely less familiar for the model, meaning LRMs may not have frequently encountered such instances during training.

    “This likely suggests that examples of River Crossing puzzle with larger N are less familiar for the model, meaning LRMs may not have frequently encountered such instances during training.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data
    § Question: Are failures on Tower of Hanoi due to context limit issues rather than reasoning limitations? · p. 19

    Model failures happen much earlier and are not due to context limits.

    “This indicates that model failures happen much earlier and are not due to context limits.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim.

    Study design and conductown data
    § Requirements: · p. 27

    The evaluation framework uses a custom simulator for validating Blocks World solutions that enforces movement constraints and verifies the final configuration matches the goal state.

    “Our evaluation framework employs a custom simulator for validating Blocks World puzzle extracted solutions. The simulator manages the state of all blocks across stacks while enforcing the puzzle's movement constraints.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Study design and conductnone given
    § A.3 Implementation Details · p. 27

    A custom extraction pipeline processed model responses and intermediate reasoning traces, using regex-based extractors, cleaning, normalizing, validating format, and filtering duplicate solutions.

    “A custom extraction pipeline was developed to process model responses and intermediate reasoning traces (thoughts). The pipeline consists of several key components. We implemented a flexible regex-based extractors to identify potential solution attempts in both the final response and thinking trace.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Study design and conductnone given
    § A.3 Implementation Details · p. 28

    Each extracted solution candidate was passed to the corresponding puzzle simulator for verification and failure analysis, with the final state compared to the goal state.

    “After extraction, each solution candidate is passed to the corresponding rigorous puzzle simulator for fine-grained verification and failure analysis.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductnone given
    § A.3 Implementation Details · p. 27

    For each puzzle instance and complexity level, results are reported on 25 samples per model.

    “For each puzzle instance and complexity level, the results are reported on 25 samples per model.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data
    § A.3 Implementation Details · p. 28

    The limitation of reasoning models is not just in problem-solving and solution strategy discovery but also in consistent logical verification and step execution throughout generated reasoning chains.

    “This finding strengthens evidence that the limitation is not just in problem-solving and solution strategy discovery but also in consistent logical verification and step execution limitation throughout the generated reasoning chains.”
    Quote in the paperSubstantial claim
    • Rests on an assumption: The intermediate reasoning traces (thinking tokens) provided by the models accurately reflect their internal reasoning processes.

  • Classified as probably not a substantial claim.

    Study design and conductreasoning
    § Abstract · p. 1

    The setup enables analysis of not only final answers but also internal reasoning traces.

    “This setup enables the analysis of not only final answers but also the internal reasoning traces, offering insights into how LRMs 'think'.”
    • Also stated in: § LLM Response · p. 3 · plain
      “inspect both solutions and internal reasoning”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Study design and conductreasoning
    § LLM Response · p. 3

    The puzzles create a new controlled setting that avoids contamination common in established benchmarks.

    “These puzzles: (1) offer fine-grained control over complexity; (2) require only the explicitly provided rules, emphasizing algorithmic reasoning; (3) create new controlled setting that avoid contamination common in established benchmarks;”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationreasoning
    § A.4.2 Performance vs Compositional Depth · p. 31

    LLMs and LRMs' problem-solving capabilities cannot be predicted solely from computational complexity without considering their training data exposure; their approach to handling complexity aligns more closely with solution patterns learned during training rather than actual computational complexity.

    “Ultimately, LLMs and LRMs represent complex systems whose problem-solving capabilities cannot be predicted solely from computational complexity without considering their training data exposure. Their approach to handling complexity aligns more closely with the solution patterns they learned during training rather than the actual computational complexity of the problems themselves.”
    Quote in the paperSubstantial claim
    • Rests on an assumption: The puzzles used (Tower of Hanoi, Checker Jumping, Blocks World, River Crossing) are valid measures of compositional reasoning capabilities.

  • May combine two claims.

    Interpretationown data
    § A.6 Extended Results and Analysis · p. 33

    Beyond certain complexity thresholds, models not only fail to solve problems but counterintuitively reduce their inference compute despite facing more difficult problems and being well below context and generation limits.

    “This suggests an interesting and fundamental scaling limit in LRM thinking process for reasoning where beyond certain complexity thresholds, models not only fail to solve problems but counterintuitively reduce their inference compute despite facing more difficult problems and being well below the context and generation limits.”
    Quote in the paperSubstantial claim
    • Rests on an assumption: The intermediate reasoning traces (thinking tokens) provided by the models accurately reflect their internal reasoning processes.

  • Classified as probably not a substantial claim.

    Study design and conductown data
    § 4.3 What Happens Inside the Thoughts of Reasoning Models? · p. 9

    The study uses puzzle simulators to validate intermediate solutions within reasoning traces.

    “We extract and analyze the intermediate solutions explored within the thoughts of a model with the help of puzzle simulators.”
    • Also stated in: § 4.3 What Happens Inside the Thoughts of Reasoning Models? · p. 9 · plain
      “its correctness and specific failure move as validated by our puzzle simulators”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Study design and conductreasoning
    § LLM Response · p. 3

    The puzzles support rigorous, simulator-based evaluation, enabling precise solution checks and detailed failure analyses.

    “These puzzles: (1) offer fine-grained control over complexity; (2) require only the explicitly provided rules, emphasizing algorithmic reasoning; (3) create new controlled setting that avoid contamination common in established benchmarks; and (4) support rigorous, simulator-based evaluation, enabling precise solution checks and detailed failure analyses.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationown data
    § Question: Does River Crossing with N ≥ 6 invalidate our core findings on this puzzle? · p. 20

    The results validate findings regarding limitations in the execution of logical steps and suggest a more fundamental failure mode in reasoning models, rather than one specific to Tower of Hanoi.

    “These results further validate our findings regarding limitations in the execution of logical steps and suggest a more fundamental failure mode in reasoning models, rather than one specific to the Tower of Hanoi.”
    Quote in the paperSubstantial claim

  • Classified as probably not a substantial claim. May combine two claims.

    Study design and conductnone given
    § LLM Response · p. 3

    The puzzles require only the explicitly provided rules, emphasizing algorithmic reasoning.

    “These puzzles: (1) offer fine-grained control over complexity; (2) require only the explicitly provided rules, emphasizing algorithmic reasoning;”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Study design and conductnone given
    § A.3 Implementation Details · p. 27

    A filtering process was applied to ensure all analyzed samples followed the requested response format, including move sequences and reasoning steps.

    “We apply a filtering process to ensure all analyzed samples are following the requested response format, including move sequences and reasoning steps as specified.”
    Quote in the paperNot a substantial claim
54 of 54

  • The authors state this as an assumption.

    The use of deterministic puzzle simulators assumes that reasoning can be perfectly validated step by step.

    “Furthermore, the use of deterministic puzzle simulators assumes that reasoning can be perfectly validated step by step.”

  • The paper relies on this without support.

    The reasoning traces generated by the models faithfully reflect their internal reasoning processes.

    “This setup enables the analysis of not only final answers but also the internal reasoning traces, offering insights into how LRMs 'think'.”

  • The paper relies on this without support.

    Algorithmic solutions for the puzzles in the study are very well-established and likely exist in models' training data as standard implementations.

    “For the puzzles in our study, algorithmic solutions are very well-established and likely exist in models' training data as standard implementations.”

  • The paper relies on this without support.

    The intermediate reasoning traces (thinking tokens) provided by the models accurately reflect their internal reasoning processes.

    “We specifically selected Claude 3.7 Sonnet (thinking/non-thinking) and DeepSeek-R1/V3 due to their ability to provide access to intermediate reasoning traces (thinking tokens), a critical requirement for our analysis.”

  • The paper relies on this without support.

    The puzzles used (Tower of Hanoi, Checker Jumping, Blocks World, River Crossing) are valid measures of compositional reasoning capabilities.

    “These varying compositional depth profiles enable us to better evaluate how reasoning models approach different types of sequential reasoning challenges and if their accuracy is always correlated with the computational complexity required to solve the puzzle.”
5 of 5

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The cost of improved performance through extended internal reasoning scales poorly.

    “Frontier reasoning-tuned language models still fail on deductive tasks at depth, and the cost of improved performance through extended internal reasoning scales poorly.”

    From PrologMCP: A Standardized Prolog Tool Interface for LLM Agents (2026) · cites this paper as [8]

  • Current reasoning-tuned models attempt to improve reliability by allocating more internal reasoning, or thinking, tokens.

    “Current reasoning-tuned models attempt to improve reliability by allocating more internal reasoning, or thinking , tokens.”

    From PrologMCP: A Standardized Prolog Tool Interface for LLM Agents (2026) · cites this paper as [8]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Tower of Hanoi is not at complete collapse at N=8

    Minor

    The failure analysis uses N ≥ 8 as an example of complete accuracy collapse for both model variants. Elsewhere, the paper reports 18.2% accuracy for sampled DeepSeek-R1 at N=8.

  • Figure 11 is described as covering both two and three models

    Minor

    The text says Figure 11 demonstrates results for three named models, including o3-mini, while its caption lists only DeepSeek-R1 and Claude-3.7-Sonnet.

  • River Crossing annotation names the wrong bank

    Minor

    The annotation says a1 and A2 are on the left bank after Move 3. The trace's own state for that move places both on the right bank.

  • Sampling shifts Blocks World collapse from N=4 to N=30

    Minor

    The paper says removing sampling leaves collapse at roughly the same points across all puzzles. Its Blocks World results instead place collapse at N=4 without sampling and N=30 with sampling.

4 of 4

Cites

The publisher hasn’t deposited this paper’s reference list.

Research works printed but not linked: 4

  1. [20][20] Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , pages 5315-5333, 2023. -
  2. [46][46] Gary F Marcus. The algebraic mind: Integrating connectionism and cognitive science . MIT press, 2003. -
  3. [47][47] Saul Amarel. On representations of problems of reasoning about actions. In Readings in artificial intelligence , pages 2-22. Elsevier, 1981. -
  4. [48][48] Günter Rote. Crossing the bridge at night. Bulletin of the EATCS , 78:241, 2002. -

Cited by

Sorted by citations

Authors
Shojaee, P., Mirzadeh, I., Alizadeh vahid, K., Horton, M., Bengio, S., & Farajtabar, M.
Affiliations
  • Virginia Tech (US)
  • Apple (United States) (US)
  • Apple
ORCID
Farajtabar, Mehrdad
Venue
Advances in Neural Information Processing Systems 38
Publisher
Neural Information Processing Systems Foundation, Inc. (NeurIPS)
Published
2025
Pages
119605-119646
ISSN
1049-5258 (ISSN-L)
DOI
10.52202/085713-3603
OpenAlex
W4417097899
Cited by
47
References
0
Citations by year
2026: 34 · 2025: 13
FWCI
46.23
Type
conference paper
Language
en
Open access
Locations
  • neural information processing systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) (submittedVersion, cc-by)
  • arXiv (Cornell University) (cc-by)
  • Leibniz international proceedings in informatics (cc-by)
  • Zenodo (CERN European Organization for Nuclear Research) (cc-by)
Funders
Austrian Science Fund (P36420, 10.55776/COE12)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
Keywords
large reasoning models, problem complexity, reasoning traces, scaling limits, exact computation, large language models, token budget

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-23.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-23.

Cited sources are checked by gpt-6-sol.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review