The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity
Authors: Parshin Shojaee
Seyed Iman Mirzadeh
Keivan Alizadeh
Maxwell Horton
Samy Bengio
Mehrdad Farajtabar
Venue: NeurIPS 2025 poster ()
Keywords: Reasoning
Large Language Models
Primary area: deep_learning
TL;DR: We examine how problem complexity affects reasoning models' behavior in controlled test settings, revealing key strengths and limitations of their reasoning capabilities.

Abstract: Recent generations of frontier 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 mathematical and coding benchmarks, emphasizing final answer accuracy. However, this evaluation paradigm often suffers from data contamination and does not provide insights into the reasoning traces' structure and quality. In this work, we systematically investigate these gaps with the help of controllable puzzle environments that allow precise manipulation of compositional 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 experimentation across diverse puzzles, we show that frontier 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 an adequate token budget. By comparing LRMs with their standard LLM counterparts under equivalent inference compute, we identify three performance regimes: (1) low-complexity tasks where standard models surprisingly outperform LRMs, (2) medium-complexity tasks where additional thinking in LRMs demonstrates advantage, and (3) high-complexity tasks where both models experience complete collapse.
We found that LRMs have limitations in exact computation: they fail to use explicit algorithms and reason inconsistently across scales and problems. 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 ultimately raising questions about the nature for their reasoning capabilities.

The Illusion of Thinking:
Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity
Parshin Shojaee*
Iman Mirzadeh
Keivan Alizadeh Vahid
Maxwell Horton
Samy Bengio
Mehrdad Farajtabar
Apple
Abstract
Recent generations of frontier language models have introduced Large Reasoning Models (LRMs) that generate detailed thinking processes before providing answers. While these models demonstrate improved performance reasoning benchmarks, their fundamental capabilities, scaling properties, and limitations remain insuffi- ciently understood. Current evaluations primarily focus established mathemati- cal and coding benchmarks, emphasizing final answer accuracy. However, this eval- uation paradigm often suffers from data contamination and does not provide insights into the reasoning traces' structure and quality. In this work, we systematically investigate these gaps with the help of controllable puzzle environments that allow precise manipulation of compositional 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 LRMss "think". Through extensive experimentation across diverse puzzles, we show that frontier LRMs face complete accuracy collapse beyond certain complexities. Moreover, they exhibit a counterintuitive scaling limit: their reasoning effort increases with problem com- plexity up to a point, then declines despite having adequate token budget. By comparing LRMs with their standard LLM counterparts under equivalent infer- ence compute, identify three performance regimes: (1) low-complexity tasks where standard models surprisingly outperform LRMs, (2) medium-complexitg tasks where additional thinking LRMs demonstrates advantage, and (3) high- complexity tasks where both models experience complete collapse. We found that LRMs have limitations in exact computation: they fail to use explicit algorithms and reason inconsistently across scales and problems. 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 ultimately raising questions about the nature for their reasoning capabilities.
Introduction
Large Language Models (LLMs) have recently evolved to include specialized variants explicitly designed for reasoning tasks-Large Reasoning Models (LRMs) such as OpenAl's ol/o3 [ 22. DeepSeek-RI (3. Claude Sonnet Thinking (4. and Gemini Thinking (5). These models are new artifacts, characterized by their "thinking" mechanisms such as long Chain-of-Thought (CoT) with
"Equal contribution.
Work done during internship Apple.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Response
Peg
Pog
Pag
<thinks
noves peg pag
2],
[a, 2]
[2, 8, 1],
from thoughts
[2, 0, 1]
3],
(for analysis)
[1,
1]
[3, 8, 2],
[3.
[A, 1, 8],
2],
Middle State
[A, 0, 2],
Let ne double-check this...
[2,
1,
2]
</thinko
extract final answer measuring accuracy)
[1,
canswer> the final answer is novesa...
</ </answer>
Target State
Chuude Sonnet
(Tokosss)
26k
Poalition Witaii Thooughts
(+thinking)
Claede Somnet (+thinlsng)
Correct Solutions
Accurncy
50
2.5
Rasanning
Incorrect Solutions
20
Clonde 3.7 Sonnet
8 10
Complexity (number
Complesity (oumber of
Complesiy tnumber of
Our setup enables verification of both final answers and intermediate reasoning traces, allowing detailed analysis of model thinking mechanisms. Bottom left & middle: At low complexity, non-thinking models are more accurate and loken-efficient. As complexity increases, reasoning models outperform but require more tokens-until both collapse beyond critical threshold, with shorter traces. Bottom right: For correctly solved cases, Claude 3.7 Sonnet (Thinking) tends to find answers early at low complexity and later at higher complexity. In failed cases, it often fixates on an early wrong answers, wasting the remaining token budget. Both cases reveal inefficiencies in the reasoning process.
Figure 1: Top:
self-reflection, and have demonstrated promising results across various reasoning benchmarks. Their emergence suggests potential paradigm shift in how LLM systems approach complex reasoning and problem-solving tasks, with some researchers proposing them as significant steps toward more general artificial intelligence capabilities.
Despite these claims and performance advancements, the fundamental benefits and limitations of LRMs remain insufficiently understood. Critical questions still persist: Are these models capable of generalizable reasoning, or are they leveraging different forms of pattern matching 6 How does their performance scale with increasing problem complexity? How do they compare their standard LLM (non-rcasoning) counterparts when provided with the same inference token compute? Most importantly, what are the inherent limitations of current reasoning approaches, and what improvements might be necessary to advance toward more robust reasoning capabilities?
We believe the lack of systematic analyses investigating these questions is due to limitations in current evaluation paradigms. Existing evaluations predominantly focus on established mathematical and coding benchmarks, which, while valuable, often suffer from data contamination issues and do not allow for controlled experimental conditions across different settings and complexities. Moreover, these evaluations do not provide insights into the structure and quality of intermediate reasoning traces. To understand the reasoning behavior these models more systematically, we need environments that enable controlled experimentation.
In this study, probe the reasoning mechanisms of frontier LRMs through the lens of problem complexity. Instead of the standard and common math benchmarks, we adopt controllable puzzle environments that let us vary complexity systematically- by adjusting puzzle elements while preserving the core logic-and and inspect both solutions and internal reasoning (Fig. top). 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.

---

Our empirical investigation reveals several key findings about current Language Reasoning Models (LRMs): First, despite their sophisticated self-reflection mechanisms learned through reinforcement learning, we observe that these models still fail to develop generalizable for planning tasks, with performance collapsing to near-zero beyond a certain complexity threshold. Second, our comparison between LRMs and standard LLMs under equivalent inference token compute reveals three distinct reasoning regimes (Fig. | bottom). For simpler, low-compositional problems, standard LLMs demonstrate greater efficiency and accuracy. As problem complexity moderately in- creases, reasoning (thinking) models gain advantage. However, when problems reach high complexity with longer compositional depth, both model types experience complete performance collapse (Fig. [ bottom left). Counterintuitively, near this collapse point, LRMs begin reducing their reasoning effort (measured by inference-time thinking tokens) problem complexity increases, despite operating well below generation length limits (Fig. D bottom middle). This suggests a fundamental inference-time scaling limitation in LRMs' reasoning capabilities relative problem complexity. Finally, our anal- ysis of intermediate reasoning traces or thoughts reveals complexity-dependee
sobblem-solving capabilities
patterns: In simpler problems, reasoning models often identify correct solutions early but inefficiently continue exploring incorrect alternatives- "overthinking" phenomenon. At moderate complexity, correct solutions emerge only after extensive exploration of incorrect paths. Beyond a certain complexity threshold, models completely fail to find correct solutions and fixate on early incorrect attempts which leads to wasting the remaining inference token budget (Fig. | bottom right). This indicates LRMs possess lim- ited self- coffectoret capabilities that, while valuable, show clear inefficiencies and scaling limitations.
These findings highlight both the strengths and limitations of existing LRMs, raising questions about the nature of reasoning in these systems with important implications for their design and deployment. Our key contributions are follows:
We question the current evaluation paradigm of reasoning models on established math benchmarks and design a controlled experimental testbed by leveraging algorithmic puzzle environments that enable controllable experimentation with respect to problem complexity.
We show that frontier LRMs (e.g., 03-mini, DeepSeek-R1, Claude-3.7-Sonnet- -Sonnet-Thinking still fail develop generalizable problem-solving capabilities, with accuracy ultimately collapsing to near-zero beyond certain complexities across different environments.
We find that there exists a scaling limit in the LRMs' reasoning effort with respect to problem complexity, evidenced by the counterintuitive decreasing trend in the thinking tokens after specific complexity points.
We question the current evaluation paradigm based on final accuracy and extend our evaluation to intermediate reasoning traces using rigorous puzzle simulators. Our findings show that as complexity increases, LRMs locate correct solutions later than incorrect ones within their thought, but beyond a complexity point, they fixate on early errors and cannot recover. This provides quantitative insights into LRMss self-correction mechanism and its scaling limits with complexity.
We uncover surprising behaviors in LRMs' ability to perform exact computation, including their fail- ure to benefit from explicit algorithms and their inconsistent reasoning across problems and scales.
2 Related Works
Reasoning in Language Models. Large Language Models (LLMs) undergo multiple costly training phases using vast amounts of training data. While these LLMs demonstrate promising language understanding with strong compression capabilities, their intelligence and reasoning abilities remain a critical topic of scientific debate 7
Earlier iterations of LLMSs @IIT exhibited poor performance To address these shortcomings. several approaches have been explored with the common theme among them being "scaling" " both the training data and test-time computation. For instance, generating a Chain of Thought (CoT) (1SHI8) and incorporating self-verification [1-21 prior to the final answer have been shown to improve model performance. However, obtaining high-quality and scalable CoT data is quite expensive due to its scarcity. Another line of research focuses on compensating for the lack of supervised data by teaching models to think more effectively through supervised learning or reinforcement learning [2). A notable open-source example of these improvements Deepseek-RI (3] which demonstrated that applying RL with verifiable rewards can significantly enhance model reasoning performance, matching that of closed models like Apen ol 2. leading to a new generation of language models referred to as
g
on reasoning benchmarks 12
6
Large Reasoning Models (LRMs) such as Gemini flash thinking (5), Claude Sonnet thinking [4] etc.
3

---

SLNTH-000
AIME24
Abbile26
Cr
passs
chmate Poptea---ottaa--------- Linking
200 109 Lsee 30x Zoe Jo0 100
5000
1000
2000
1000
1980
1000
2000
Infervnce: Compute Bodgee (Tolora)
Inference Chmpgre Budget (Tukme))
Infermnon Compute Budge (Tolons))
AIME21
AbblRe25
pooo
passoli
DeppGei:111
Deppoek
Dey88r3-V8
DeyShek
1080
2000
2000
2000
346
2000
50000
2000
136K
2000
0000
B.X
5000 1X00 12000
Inberaus Compuise Budlys (Tilons)
Infreenco Compusa Balget (Tiikmms)
Enfennsoo Compule Budge (Tioons)
Figure 2: Comparative analysis of reasoning (thinking) versus non-reasoning (no-thinking) model variants across math benchmarks reveals inconsistent performance patterns.
Understanding Large Reasoning Models. Recent studies have explored various aspects of rea- soning behavior: Large Reasoning Models have shown emergent behaviors such discrepancy between thought traces and final answers (28, [29] as well as efficiency concerns through what re- searchers term the "overthinking phenomenon" B0 33), where models produce verbose, redundant outputs, even after finding the solution, creating significant inference computational overhead. In this work, systematically analyze how much the model thinks with respect task complexity. Recent works [34, 33 32 have demonstrated that in newer LRMs accuracy generally declines when thinking increases in math problems, in contrast observe that the opposite correlation of thinking and accuracy actually depends on the problem complexity and only happens up to some complexity threshold in controlled puzzle environments. Yue 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. We also observe that in math datasets like MATH-500, pass @k 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.
Controllable Evaluation Environments. Unlike earlier studies that are mostly focused on mathe- matical benchmarks evaluate the reasoning capabilities of language models, this work introduces controllable puzzle environments. These environments allow for precise manipulation of problem complexity while maintaining consistent logical processes, enabling more rigorous analysis of reasoning patterns and limitations. Controllable environments are not uncommon in the relevant theoretical (36] and empirical studies in recent literature 112 37] However, our primary aim to propose a new benchmark; instead, we use similar benchmarks as tools for designing experiments better understand the reasoning behavior of language models. Two closely related studies by Valmeekam et al. [40] and Ruoss et al. [39] demonstrated that reasoning models such as ol show significant performance improvements compared previous models on puzzles and decision making tasks. Our work offers additional insights, such as examining pairs of prasoning/non-reasonni els (e.g., DeepSeek-Ree -1/V3, Claude 3.7 Sonnet moakking/non-thiniigg traces of the LRMs in more depth, revealing different cunplexity-dependee the promising results from recent LRMs raise a critical question: how much have the previously reported limitations of LLMs been improved? In this work, we move beyond only measuring the final accuracy and analyze how well these LRMs tackle problems of varying complexities with controllable experiments, examining the properties of their reasoning processes.
mod- We also study the reasoning behaviors. Overall,
3
Math and Puzzle Environments
Currently, it is not clear whether the performance enhancements observed in recent RL-based reasoning (thinking) models are attributable to increased exposure to established mathematical reasoning data, to the significantly greater inference compute allocated to longer thinking tokens, or
to reasoning capabilities developed by RI-based training? Recent studies [35] 41 have explored this
question with established math benchmarks by comparing the upper-bound capabilities (pass @k)

---

Tower of Hanoi
Checkers Jumping
River Crossing
Blocks World
Initial State
moves
Middle State
moves
Target State
Figure 3: Illustration of the four puzzle environments. Rows show the progression from initial state (top) through intermediate state (middle) to target state (hottom) for puzzles: Tower of Hanoi (disk transfer across pegs), Checkers Jumping (position swapping of colored tokens), River Crossing (transporting entities across river), and Blocks World (stack reconfiguration).
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 like MATH500 [42] and AIME24 [43]. We also conducted our comparative analysis of frontier LRMs like Claude-3.7-Somen (with vs. without thinking) and Deep (R/ vs. V3). Our results (shown in Fig. 2 confirm that, on the MATH500 dataset, the pass @ performance of thinking models is comparable to their non- thinking counterparts when provided with the same inference token budget. However, we observed that this performance gap slightly widens on the AIME24 benchmark and widens further on AIME25, This widening gap presents an interpretive challenge. It could be attributed to either: (1) increasing complexity requiring more sophisticated reasoning processes, thus revealing genuine advantages of the thinking models for more complex problems, or (2) reduced data contamination in newer benchmarks (particularly AIME25). Interestingly, human performance on AIME25 was actually higher than on AIME24 44 45), suggesting that AIME25 might be less complex. Yet models perform worse on AIME25 than AIME24 Sugggssigg potential for some degree of data contamination in the training of frontier LRMs. Given these non-justified observations and the fact that mathematical benchmarks do not allow for controlled experimentation and manipulation of complexity, we turned to puzzle environments that enable more precise and systematic experimentation.
3.1 Puzzle Environments
We evaluate LRM reasoning on four controllable puzzles spanning compositional depth, planning complexity, and distributional settings. The puzzles are defined below and schematic illustration is provided in Fig
Tower Hanoi is a puzzle featuring three pegs and disks of different sizes stacked on the first peg in size order (largest at bottom). The goal is to transfer all disks from the first peg to the third peg. Valid moves include moving only one disk time, taking only the top disk from a peg, and never placing a larger disk top of smaller one. The difficulty in this task can be controlled by the number of initial disks as the minimum number of required moves with n initial disks will be 2n - 1. However, in this work we do not grade for optimality of final solution and only measuring the correctness of each move and reaching the target state.
Checker Jumping is -ieddnnenioonal puzzle arranging red checkers, blue checkers, and single empty space in a line. The objective is to swap the positions of all red and blue checkers, effectively mirroring the initial configuration. Valid moves include sliding checker into adjacent empty space or jumping over exactly one checker of the opposite color to land in an empty space. No checker can move backward in the puzzle process. The complexity of this task can be controlled by the number of checkers: with 2n checkers, the minimum number of moves required will be (n + 1)2 1 1.
River Crossing is constraint satisfaction planning puzzle involving n actors and their correspond- ing agents who must cross river using a boat. The goal is to transport all 2n individuals from the left bank to the right bank. The boat can carry at most & individuals and cannot travel empty. Invalid situations arise when actor is in the presence of another agent without their agent present, as
5

---

0-0
100
100
80
(+hinkkng))
80
Claude Sonnet (*thinkcng)
pazsoglle
40
40
Sonnet
O+ - 4
Claudo Sonnet
Claude 3.7 Sonnet
Claude 3.7 Sonnet
(-thinking)
201000
c0000
60000
500000
00000
60000
130000
160000
50000
160000
240000
Inforunce Compute Budget (Tukens]
Interence Compute Budget (Tokens)
Inference Compute Bucget (Tokens)
100
100
100
DeepSwokeRt
60
pansgple
60
DeepSeek-Rt
passeei
60
DeepSeek-V3
DeepSeek-V33
20
20
20
SeekV3
DeepSenkeRR
20000)
40000
83000
25000
75000
1000000
90000 1200000
Inference Compute Budget (Tokens)
Inference Comgute Budget (Toleens)
Inference Compute Budget (Tokens)
Figure 4: Pass@k performance of thinking models (Claude 3.7 Sonnet with extended thinking, DeepSeek-RI) versus their non-thinking counterparts (Claude 3.7 Sonnet, DeepSeek-V33 V3) across equivalent inference compute budgets in puzzle environments of low medium and high com- plexity. Non-thinking models outperform in simple problems, thinking models show advantages at medium complexity, while both approaches fail at high complexity regardless of compute allocation.
each agent must protect their client from competing agents. The complexity of this task can also be controlled by the number of actor/agent pairs present. For n = 2, n 3 pairs, we use boat capacity of k: = 2 and for larger number of pairs we use
Blocks World is block-stacking puzzle requiring rearrangement of blocks from an initial configu- ration into a specified goal configuration. The objective to find the minimum number of moves needed for this transformation. Valid moves are restricted to the topmost block of any stack, which can be placed either on an empty stack or on top of another block. The complexity in this task can also be controlled by the number of blocks present.
4 Experiments & Results
4.1 Experimental Setup
Most of our experiments are conducted on reasoning models and their non-reasoning counterparts, such as Claude 3.7 Sonnet thinnknng/oo-thinkingg and DeepSeek-RI 1/V3. We chose these models because they allow access the thinking traces, unlike models such OpenAl's o-series. For experiments focused solely on final accuracy, we also report results on the 03-mini model. For Claude 3.7 Sonnet models, allow the maximum token budget (64k). Similarly, for PeepSeck-R1/V3 models on local servers, we allow the maximum length to be up to 64k tokens. For each puzzle instance and complexity level, analyze 25 samples per model. We apply filtering process to ensure the analyzed samples follow the requested response format (including sequence of moves in the specified format, reasoning steps, etc.). Comprehensive details of our experimental setup and results are provided in the Appendix.
4.2 How Does Complexity Affect Reasoning?
4.2.1 Three Regimes of Complexity
Motivated by the observations in Fig. to systematically investigate the impact of problem complexity on reasoning behavior, we conducted experiments comparing thinking (reasoning model with long CoT enabled by RL) and non-thinking (standard) model pairs across our controlled puzzle environments. Our analysis focus on matched pairs of LLMs with same model backbones, specifically Claude-3. 3.7-onnee (w. vs. w/o thinking) and DeepSeek (RI vs. V3). In each puzzle, we vary the complexity by manipulating problem size N (representing disk count, checker count, block count, or crossing elements).

---

Tower of Hanoi
Checker Jumping
Blocks World
River Crossing
110
Accuncc 1980
Cloudo 2.7 Stueet
Clasde Bonnet
Claads 3-7 sexaad
20
20
O
10
12
Comppienty
Cocplandty Inamber Medal
Compiesty
100
100
100
Ireedloii H!l
Acarwcy
DesgSesk-tt::
Dospiontett
Deck
Complesiy Conntierro Bockal
Oanpleuly foamber cleellos
Oosploaly Inanber of Machl
Oxspbosity Inualer of paaro)
Figure Accuracy of thinking models (Claude 3.7 Sonnet with extended thinking. DeepSeek- R1) versus their non-thinking counterparts (Claude 3.7 Sonnet, DeepSeek- -V3) across all puzzle environments and varying levels of problem complexity.
Fig. 4 shows the upper bound performance capabilities (pass@k) of these model pairs under equivalent inference token compute (averaged across all puzzles), extending earlier analyses from mathematical benchmarks (Fig. 2 to the controlled puzzle environments. Complementing this, Fig.
3 presents the accuracy of both model types function of problem complexity across each puzzle environment. Results from both these figures demonstrate that, unlike observations from math, there exists three regimes in the behavior of these models with respect to complexity. In the first regime where problem complexity is low, we observe that non-thinking models are capable of obtaining perfor- mance comparable to, or even better than thinking models with more token-efficient inference. In the second regime with medium complexity, the advantage of reasoming models capable of generating long chain-of-though begin to manifest, and the performance gap between model pairs increases. 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.
Additional results comparing the QwQ-32B and Qwen2.5-32B model pairs under the same thinking vs. non- thinkiinnkin setup are provided in Appendix A.6
4.2.2 Collapse of Reasoning Models
We next examine how different specialized reasoning models equipped with thinking tokens respond to increasing problem complexity. Our experiments evaluate five thinking models: 03-mini (medium and high configurations), DeepSeek-RI, DeepSeek-RR RI-Disiil Sestill--Qee-326-- and Claude-3.7-Somen (thinking). Fig. 6 demonstrates these models' performance in terms of accuracy (top) and thinking token usage (bottom) across varying complexity levels. 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 model-specific complexity threshold. Analysis of inference thinking token compute also reveals an intriguing pattern in thinking token allocation learned by these models. We observe that reasoning models initially increase their thinking tokens proportionally with problem complexity. However, upon approaching critical threshold-which closely corresponds their accuracy collapse point-models counterintuitively begin to reduce their reasoning effort despite increasing problem complexity. This phenomenon is most pronounced in o3-mini variants and less severe in the Claude-3.7-Sonnet (thinking) model. Notably, despite mostly operating well below their generation length limits with ample inference budget available these models fail to take advantage of additional inference compute during the thinking phase as problems become more complex. This behavior suggests fundamental scaling limitation in the thinking capabilities of current reasoning models relative to problem complexity.
4.3 What Happens Inside the Thoughts of Reasoning Models?
To gain deeper insights into the thinking processes of reasoning models, we conducted fine-grained analysis of their reasoning traces. As shown in Fig. [ our setup with puzzle environments allows us to look beyond final answer and obtain more detailed insight into the reasoning traces ("thoughts"")
7

---

Tower of Hanol
Chacker jumping
Blocks World
River Crossing
1.0
1011
1.5-
Edo-
Accuracy No
10
Cumplesity (ourtbue disko)
Cumplesity chackars)
Complesity (number block)
Cumplesity (sumber purs)
200
Thiniing Tokeres
Trinking Tokerns
220
Thinking
Complecity fnomber diolod
Complesity (number checkero
Comylectly (numbber of bloclod
Complecity tnumber pains]
DeepSock--R
(thinking)
DeepSeek Distill-ween
(bigh)
(medium)
Figure 6: Accuracy and thinking tokens versus problem complexity for reasoning models across puzzle environments. As complexity increases, reasoning models initially spend more tokens while accuracy declines gradually, until critical point where reasoning cellapses-performmanc drops sharply and reasoning effort counterintuitively decreases.
Checker Tamping
(wits Takkng (emrennnn)
Hanei
100
83
Gonglectty
Complestty
Blocks World
to Thniin
&
Postion Barradtee
N-10
Ned
Neb Nez Ne10 Awtb N-20 Ne2b
2002 Postioc Thinking Clikken)
Oampkouly
Complosily
(b)
Figure 7: (a) Position and correctness of intermediate solutions within reasoning traces across four puzzles at varying complexity levels. / indicates correct solutions, X indicates incorrect solutions, with distribution density shown by shading; (b) Solution accuracy versus position thinking for Tower of Hanoi at different complexity levels. Simple problems (N=1-4) show early accuracy declining over time (overthinking). moderate problems (N=5-7) show slight improvement in accuracy with continued reasoning, and complex problems (N28) exhibit consistently near-zero accuracy, indicating complete reasoning failure.
produced by these models. We extract and analyze the intermediate solutions explored within the thoughts of model with the help of puzzle simulators. Our investigation examines the patterns and characteristics of these intermediate solutions, their correctness relative to their sequential position in the reasoning process, and how these patterns evolve with increasing problem complexity. For this analysis, we focus on the reasoning traces generated by Soneull-.7-Soone-TThhee our puzzle suite. For each unique intermediate solution identified within the traces, we recorded: (1) its relative position within the reasoning trace (normalized by total thought length), (2) its correctness and specific failure move validated by puzzle simulators. and (3) the complexity of the corresponding problem. This allows to characterize the progression and accuracy of solution development throughout the reasoning process.
across
Fig. demonstrates the relation between the position of intermediate solutions within thoughts, their correctness, and problem complexity across all puzzle environments. Our analysis from intermediate reasoning traces also further validates three regimes of complexity discussed above. For simpler problems, reasoning models often find the correct solution early in their thinking but then continue exploring incorrect solutions. Note the distribution of incorrect solutions (red) comparable or shifted more upward towards end of thinking compared to correct solutions (green). This phenomenon,

---

Townr Htunci
Towar Hanui
Chacker junping
Checkar Jumpung
Despdrskat Algoritian Ghae
DeepSedkett:
Claases Seezac
Agueiia Greaz
Dellazz
Noturnyy CNO
Detsall
Accunsey (V8))
Nonurac
Dedvak
Civude
15
Aper Thoes
Complexiyy (Numbeer of Diskst
Complexity (Sumber of Disls)
Complexity (Sumber of Checkers)
Complexity (Number of Chockers)
Figure 8: Performance comparison between default problem-solving and algorithm-guider execution across Tower of Hanoi and Checker Jumping puzzles. Even when given the solution algorithm and only needing to execute prescribed steps, failures occur similar points, highlighting reasoning models' limitations in following logical procedures.
referred to as ""veertinkkin"" in the literature, leads to the waste of compute. As problems become moderately more complex, this trend reverses: models first explore incorrect solutions and mostly later in thought arrive at the correct ones. This time the distribution of incorrect solutions (red) is shifted more downward compared to correct ones (green). Finally, for the problems with higher complexity, collapse emerges, meaning that the model fails to recover any correct solutions within the thought early incorrect solutions, wasting the remaining thought token budget.
and it often fixates
Fig. 7b presents complementary analysis of solution accuracy within sequential segments (bins) of the thoughts in the Tower of Hanoi environment. It can be observed that for simpler problems (smaller N), solution accuracy tends to decrease or oscillate as thinking progresses, providing further evidence of the overthinking phenomenon. However, this trend changes for more complex problems, where so- lution accuracy increases with thinking progression- up to certain threshold. Beyond this complex- ity threshold, in the "collapse mode", accuracy is zero and model fail to recover any incorrect solution.
4.4 Open Questions: Puzzling Behavior of Reasoning Models
In this section, we present surprising results concerning the limitations of reasoning models in executing exact problem-solving steps, well as demonstrating different behaviors of the models based on the failure moves. As shown in Figure in the Tower of Hanoi and Checker Jumping puzzle environments, even when we provide the algorithm in the prompt- that the model only needs to exccute the prescribed steps per--prrffomcee does not improve, and the observed collapse still occurs roughly the same point on both puzzle environments. This is noteworthy because finding and devising a solution should require substantially more computation (e.g.. for search and verification) than merely executing given algorithm. This further highlights the limitations of reasoning models in verification and in following logical steps to solve a problem, suggesting that further research might be needed to better understand the symbolic manipulation capabilities of such models 46
Moreover, by looking deeper into failure cases, shown in Figure 9 for Claude- 3.7-Sonnet think- ing as well as Figures [14 and 15 in Appendix for other models, we observe inconsistencies in how models apply learned solution strategies across different problems and scales. Some- times, models exhibit a non-monotonic failure behavior with respect problem complex- ity-instances where models fail earlier in the solution sequence for higher N values despite requiring longer overall solutions. 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, contradicting the expectation that effective algorithmic planning and execution for the same puzzle should maintain consistent fail- ure patterns. Also, we observe longer error-free sequences in some puzzle environments com- pared to others. For example, in the Tower of Hanoi environment, the model's first error in the
Tower of Hanol
Checlerr Jumping
100
Chasda T.Sona
Thre Pinn More
Thlter
Chidk& 26mmnt Gettaigg
Completity DNumber Bisloo
Complosty (Number of Chardoess)
River Crorking
Clocde-3, 3.2 Sonait Entkakkng!
Caeles
mhd Tathor Monn
Sae sanng C. 2000
10 20
Complestty (Number of Blocks)
Complextty (Namber Pains)
Figure 9: First failure move versus problem com- plexity for Claude 3.7 Sonnet (thinking) across four puzzle environments.

---

proposed solution often occurs much later, e.g., around move 100 for (N=10), compared to the River Crossing environment, where the model can only produce a valid solution until move 4. 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. Although the branching factor for solution exploration in River Crossing is larger than in Tower of Hanoi, this malysis on the comparison of computational complexity between puzzles is asymptotic and doesn't 't hold for the small values of N in our experiments where collapse happens. The search space for a valid mmve (N=3) River Crossing solution is vastly smaller than the search space for 255-move (N=8) Tower of Hanoi solution where models begin to fail. 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. At the end, LLMs (or LRMs) are complex artifacts and we cannot easily say which problem is easier or more complex for them only based on computational complexity and without knowing about their training data distribution. How they approach complexity does not necessarily corresponds to the actual computational complexity of the problem and more to the learned solution distributions. That's ss why our focus complexity is mostly to track model behavior within each puzzle setting rather than between the puzzles.
Conclusion
In this paper, we systematically examine frontier Large Reasoning Models (LRMs) through the lens of problem complexity using controllable puzzle environments. Our findings reveal several strengths and limitations in current models: despite sophisticated self-reflection mechanisms learned by reinforcement learning, these models still fail develop generalizable reasoning capabilities beyond certain complexity thresholds. 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. We observe the counterintuitive reduction in reasoning effort as problems approach critical complexity, suggesting an inherent compute scaling limit in LRMs. Our detailed analysis of reasoning traces further exposed complexity complexity-dependen dependent reasoning patterns, from inefficient "overthinking" on simpler problems to complete failure on complex ones. These insights help us to better understand the nature reasoning in LRMs and challenge some of the prevailing assumptions about LRM's 's capabilities. Finally, we presented some of our surprising observations on LRMs that lead to several open questions for future research. Most notably, 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. Investigating the first failure move of the models also revealed some surprising and inconsistent behaviors. Our results show that models sometimes fail earlier harder instances despite requiring longer overall solutions. They also show very different error- sequence lengths across puzzles, c.g., performing up to 100 correct moves in Tower of Hanoi but only 4 in River Crossing. This disparity likely reflects differences in the models' familiarity with each setting based on the distribution of training data rather than intrinsic differences in problem's 's computational complexity. We hope that these findings can pave the way for future investigations into better understanding the reasoning process of these systems.
Limitations
We acknowledge that our work has limitations. While our puzzle environments enable controlled experimentation with fine-grained control over problem complexity, they represent narrow slice of reasoning tasks and may not capture the diversity of real-world or knowledge-intenss inteneivn reasoning problems. is notable that most of our experiments rely on black-box API access to the closed frontier LRMs, limiting our ability to mechanistically analyze internal states or architectural components. Furthermore, the use of deterministic puzzle simulators assumes that reasoning can be perfectly validated step by step. However, in less structured domains, such precise validation may not be feasible, limiting the transferability of this analysis to other more generalizable and open-ended reasoning.
Acknowledgments
The authors would like to thank Scott Hoang, Yichen Jiang, Minsik Cho, Mohammad Sekhavat, David Harrison, Mohammadreza Armandpour and Devi Krishna for the valuable feedback and support.
10

---

References
[1] Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed EI-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, al. Openai ol system card. arXiv preprint arXiv:2412.167200 2024.
[2] OpenAl. Introducing openai ol. Jan 2024.
[3] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang. Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. arXiv preprini arXiv:2501. 122448 2025.
[4] Anthropic. Claude 3.7 sonnet. Feb 2025.
[5] Google. Gemini flash thinking. Google Al Blog, Jan 2025.
[6] Seyed Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. GSM-symbolie: Understanding the limitations of mathematical reasoning in large language models. In The Thirleenth International Conference on Learning Representations, 2025.
[7] Emily M Bender, Timnit Gebru, Angelina SeMillan-Majon and Shmargaret Shmitchell. the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 202 ACM conference on fairness, accountability, and transparency, pages 610-623, 2021.
[8] Francois Chollet, Mike Knoop, Gregory Kamradt, Bryan Landers, and Henry Pinkard. Arc- agi-2: A new challenge for frontier ai reasoning systems. arXiv preprint arXiv:2505. 1883,, 2025.
[9] Marah I Abdin, Sam Ade Jacobs, Ammar Ahmad Awan, Jyoti Aneja, Ahmed Awadallah, Hany Awadalla, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Harkirat S. Behl, and et. al. Phi-3 technical report: A highly capable language model locally your phone. CoRR, abs/2404. 14219, 2024.
[10] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chap- lot, Diego de Las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b. CoRR, 10./2330.06825, 2023.
(11) Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshom, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurélien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Rozière, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong, Cristian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius. Daniel Song, Danielle Pintz, Danny Livshits, David Esiobu, Dhruv Choudhary, Dhruv Mahajan, Diego Garcia-Olano, Diego Perino. Dicuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Anderson, Graeme Nail, Grégoire Mialon, Guan Pang, Guillem Cucurell, Hailey Nguyen, Hannah Korevaar, Hu Xu, Hugo Touvron, and et al. The llama 3 herd of models. CoRR, abs/2407.21788 2024.
[12] Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaïd Harchaoui, and Yejin Choi. Faith and fate: Limits of transformers on compositionality. In Alice Oh, Tristan Naumano, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.

---

[13] R. Thomas McCoy, Shunyu Yao, Dan Friedman, Matthew Hardy, and Thomas L. Griffiths. Embers of autoregression: Understanding large language models through the problem they are trained to solve, 2023.
[14] Marianna Nezhurina, Lucia Cipolina-Kuu Kun, Mehdi Cherti, and Jenia Jitsev. Alice in wonderland: Simple tasks showing complete reasoning breakdown in state-of-the-aus large language models. arXiv preprint arXi::2406.02066 02061, 2024.
[15] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain tftuuhtt prompting elicits reasoning in large language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35; Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
[16] Mchran Kazemi, Najoung Kim, Deepti Bhatia, Xin Xu, and Deepak Ramachandran. Lam bada: Backward chaining for automated reasoning in natural language. arXiv preprint arXiv:2212.1 13894, 2022.
[17] Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanie Sedghi. Teaching algorithmic reasoning via in-context learning. arXiv preprint arXiv:2211.099 2022.
[18] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural info information processing systems, 35:22199-2222 22213, 2022.
[19] Yixuan Weng, Minjun Zhu, Fei Xia, Bin Li, Shizhu He, Shengping Liu, Bin Sun, Kang Liu, and Jun Zhao. Large language models better reasoners with seff-verification. In Houda Bouamor, Juan Pino, and Kalika Bali, editors, Findings of the Association for Computational Linguistics: EMNLP 2023, pages 1550-2575, Singapore, December 2023, Association for Computational Linguistics.
[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 61 Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages
2023.
[21] Eric Zhao, Pranjal Awasthi, and Sreenivas Gollapudi. Sample, scrutinize and scale: Effective inference-time search by scaling verification. arXiv preprint arXiv:2502.01883 2025.
[22] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. STar: Bootstrapping reasoning with reasoning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[23] Sachin Goyal, Ziwei Ji, Ankit Singh Rawat, Aditya Krishna Menon, Sanjiv Kumar, and Vaishnavh Nagarajan. Think before you speak: Training language models with pause tokens. In The Twelfth International Conference on Learning Representations, 2024.
[24] David Herel and Tomas Mikolov. Thinking tokens for language modeling. ArXiv, his/2405.086444 2024.
[25] Zhihong Shao, Peiyi Wang, Runxin Xu Qihao Zhu, Junxiao Song, Mingchuan Zhang, Y.K. Li, Y. Wu, and Daya Guo. Deepseckmath: Pushing the limits of mathematical reasoning in open language models, 2024.
[26] Amirhossein
Kazemnejad, Milad Aghajohari, Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville, and Nicolas Le Roux. Vineppo: Unlocking rl potential for Ilm reasoning through refined credit assignment, 2024.
[27] Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, Yuling Gu, Saumya Malik, Victoria Graf, Jena D. Hwang, Jiangjiang Yang, Ronan Le Bras, Oyvind Tafjord, Chris
12

---

Wilhelm, Luca Soldaini, Noah A. Smith, Yizhong Wang, Pradeep Dasigi. and Hannaneh Ha- jishirzi. Tülu 3: Pushing frontiers open language model post- wost-training, ArXiv, abs/2411.15124. 2024.
[28] Yanda Chen, Joe Benton, Ansh Radhakrishnan, Jonathan Uesato, Carson Denison, John Schul- man, Arushi Somani, Peter Hase, Misha Wagner, Fabien Roger, et al. Reasoning models don't t always say what they think. arXiv preprint arXiv:2505.08:. 10, 2025.
[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.
[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 ol-like llms. arXiv preprint arXiv:24/2.21187, 2024.
[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 vrXiv:2503.164111 2025.
[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-rl thoughtology: Let's< think> about IIm reasoning. arXiv preprint arXiv:2504.07128. 2025.
[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.
[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.
[35] Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang, Shiji Song, and Gao Huang. Does reinforcement learning really incentivize reasoning capacity in Ilms beyond the base model? arXiv preprini arXiv:2504. 1 2025.
[36] Nikola Zubić, Federico Soldá, Aurelio Sulser, and Davide Scaramuzza. Limits of deep learning: Sequence modeling through the lens of complexity theory. arXiv preprint arXiv:2405. 16674, 2024.
[37] Benjamin Estermano, Luca A. Lanzendörfer, Yannick Niedermayr, and Roger Wattenhofer. Puzzles: A benchmark for neural algorithmic reasoning. 2024.
[38] Karthik Valmeekam, Alberto Olmo Hernandez, Sarath Sreedharan, and Subbarao Kambhampati. Large language models still can't plan (A benchmark for llms on planning and reasoning about change). CoRR, abs/2206.10499 2022.
[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 arX1vv2412.014441, 2024.
[40] Karthik Valmeekam, Kaya Stechly, and Subbarao Kambhampati. Llms still can't plan; can Irms? a preliminary evaluation of openai's ol on planbench. 2024.
[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.09M) 009558 2025.
[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 200552230 2023.
13

---

[43] Mathematical Association
of America.
American invitational mathe-
matics examination (aime).
attps://mas /aa. org arg/math- competitions/
american- - inviiaatiional-mmthhmaaiiic. -n o aime 2025. Accessed: 2023-05-
15.
[44] Art of Problem Solving. Ame
historical
results aime (february 2024).
http:://aatodfrrooleessddtgg com www.woiiii..........ooo....oewoe /ttp//iiiiiiineeeeee php/ AMC bistorical_rreslssaa
AIME 2.0.......2.br 2C_ 2022 29 2024. Accessed: 2025-05-15.
[45] Art of Problem Solving.
Ame historical results aime (february 6, 2025).
wtw.:hiitorrialrreulll.l AIME I_. 2ww.ereFeerrrrreee 6. 2C 2025. 29 2025. Accessed: 2025-05-15.
https://artoffproleemsll. cettroblemoolvimee com/wikiiindee. wttp:/ppphhAMmaaaaaaaA0
[46] Gary F Marcus. The algebraic mind: Integrating connectionism and cognitive science. MIT press, 2003.
[47] Saul Amarel. On representations of problems of reasoning about actions. In Readings in artificial intelligence, pages 2-22. Elsevier, 1981.
[48] Günter Rote. Crossing the bridge at night. Bulletin of the EATCS, 78:241, 2002.
[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.0/000 2025.
[50] Xiaomin Li, Zhou Yu, Zhiwei Zhang, Xupeng Chen, Ziji Zhang, Yingying Zhuang, Narayanan Sadagopan, and Anurag Beniwal. When thinking fails: The pitfalls of reasoning for instruction- following in llms, arXiv preprint arXiv:2505.11422 2025.
14

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
15

---

Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The paper describes the full experimental setup in Section 4 and Section 3.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [Yes]
Justification: We can not release the code at this stage, but, we plan to release the full code and experiments upon paper acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https /nipss.cc/pulli//guuu guwde//ddee/ee/ Cot//ooodeeeiiseeeeeeee hwtpbbmmsssioooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Same as Q4.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Thinking models are compute heavy and pretty expensive due very long tokens for each sample. It was not economically feasible to run many experiments to compute error bars too.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: the detailed computer resources and GPU hours will be reported in Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http:::////uuriii http:pp......bcccccccccccceeeee.
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We thoroughly discussed benefits and impacts of this work introduction and discussion sections
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risk
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
21

---

A Appendix
In this appendix, we provide details supplementing the main text, including our response alternative critics, experimental setup specifications, additional results, and extended analysis.
Response to Main Criticisms
Details on Puzzle Environment Specifications and Design Comprehensive descriptions of all four puzzle environments, including their problem descriptions, prompt designs, and simulators.
A.2.J
Tower of Hanoi
Checker Jumping
A.2.3
River Crossing
A.2.4
Blocks World
Implementation Details Full experimental setup specifications, model configurations,
extraction pipeline details, and prescribed algorithm execution experiments.
Details Computational Complexity
1.4.1
Compositional Depth Characterization
A.4.2
Performance and Inference Compositional Depth
A.6
Additional Results and Analysis Extended analysis including additional Qwen model pairs, sampling effects, reasoning effort patterns, and detailed failure analysis across all models and puzzle environments.
22

---

A.1 Response to Main Criticisms
This section addresses critiques raised regarding our paper and provides our responses to these concerns. We appreciate the engagement from the research community and have incorporated several modifications to address valid points while clarifying misunderstandings where appropriate.
Question: Are failures on Tower of Hanoi due context limit issues rather than reasoning limitations?
Response: Our empirical evidence demonstrates that model failures observed in experiments occur within the context limits in all puzzles. For the Tower of Hanoi, with its exponential growth raising questions of context-limit failures, reasoning models begin to collapse at N=7 and 8, corresponding to ~100-200 moves (as shown in Figures 5 6 and [T) which is well within the context limits. More importantly, if we look deeper into the failure cases (like in Figures 9 14 and
[5]. we see that the first failure move actually happens much sooner than the final move. For example, for Tower of Hanoi with No/10 (requiring ~ 103 moves), failure typically occurs within the first 1~0 moves (10% of solution length); for N=8, which requires 255 moves, failure occurs around ~40 moves (15% of solution length). This indicates that model failures happen much earlier and are not due to context limits. To account for context limit concerns for large values of N in Tower of Hanoi, have removed N>12 from the experiments on this puzzle.
Question: Do models collapse primarily due to the sampling of large number of moves (particularly on Tower of Hanoi)?
Response: Some crities argue that sampling is the primary cause of the observed collapse behavior (particularly on Tower of Hanoi). While we acknowledge that longer move sequences may reduce the chance of correct reasoning chains due to sampling, our experiments demonstrate that sampling not the primary factor underlying these failures. To investigate this, we conducted additional ablation experiments using temperature zero to remove sampling effects on solution length. These experiments were performed on the DeepSeek-R2 reasoning model to ensure precise temperature control on local servers. Results show that eliminating sampling does not change the collapse across any the puzzles, including Tower of Hanoi, indicating that sampling long sequences is not causing the observed collapse behavior. In fact, in Tower of Hanoi and Blocks World, sampling actually helps delay collapse. For example, in Blocks World, RI with temperature zero collapses at N=4, but sampling delays the collapse until N=30 (details in Figure 13 of Appendix (A.6). Similar collapse behavior in much shorter sequences where sampling has less impact like River Crossing (11 moves, N=3) and Checker Jumping (24 moves, N=4) also further supports this conclusion.
Question: Does River Crossing with N26 6 invalidate our core findings on this puzzle?
Upon further experiments, we found that the puzzle dynamics shift considerably for N26, where the optimal boat capacity (k: 4) fundamentally changes the problem structure, making it less suitable for evaluating planning capabilities. This insight led us to refine our analysis by focusing on the cases where N<6. However, this modification does not invalidate our core findings, as performance of models mostly collapse earlier from N=3, which requires only an 1 1-move solution for basic constraint satisfaction. This early performance collapse particularly noteworthy and suggests that current frontier reasoming models may have limited capability for constraint verification and satisfaction while planning.
Response:
Question: Is the finding that providing algorithms doesn't improve performance specific to Tower of Hanoi due to its well-known recursive algorithm or reflecting a general limitation of reasoning models?
The critic suggests that the findings of algorithm execution limitation in LRMs (Sec- tion 4.4) may be only an artifact of the Tower of Hanoi's well-known recursive algorithm being already memorized by models, rather than indicating general limitation in algorithm execution. To investigate this, we conducted additional experiments on Checker Jumping puzzle, with some different characteristics: it requires fewer moves than Tower of Hanoi, exhibits carlier collapse behavior, and
Response:
23

---

appears to have less algorithmic familiarity. If the critic's ss hypothesis were correct, we should observe clear benefits from algorithm provision in this problem. However, our results Figure show very similar patterns for both puzzles. Even when given explicit algorithm show no meaningful improvement on
requiring only execution
rather than croblem-solving and solution discovery-mode either puzzle, with collapse happening at similar points. 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.
Question: Why not use tools for solving these puzzles?
We would like to highlight that our objective is to assess models' reasoning thee ability to understand problems, explore solution spaces, and execute logical than merely achieving correct final answers. For the puzzles in our study, algorithmic solutions are very well-established and likely exist in models' training data as standard implemen- tations. Allowing tool use would tell us nothing about their capacity for problem understanding, constraint reasoning, or multi-step logical execution. Tool usage becomes valuable when algorithmic codes for solving the problem are unknown and require compositional reasoning to be developed.
Response:
We believe it's crucial to separate tool use from understanding when evaluating reasoning capabilities. As the Chinese room argument illustrates, it's entirely possible to use tools effectively without any real comprehension of the underlying problem. Consider a student who complains about a math exam requiring integration by hand, arguing that software can produce correct answers instantly. The teacher's goal isn't 't to find the they already know it-but to assess the student's s conceptual understanding. The same principle applies to LLM evaluation. Furthermore, if an LLM cannot reliably perform sequential reasoning steps on its own, how can we expect it to write complex code or coordinate multiple tools correctly for even more challenging problems? Reliable tool use requires the same systematic thinking and logical exccution that these simple puzzles assess.
A.2 Details on Puzzle Environment Specifications and Design
A.2.1 Tower of Hanoi
Problem Description. The Tower of Hanoi is a classic recursive puzzle that serves as a great problem for evaluating sequential reasoning and planning capabilities in reasoning models. The puzzle consists of three pegs (labeled 0, I, and 2 from left to right) and N disks of varying sizes, where each disk is uniquely numbered from 1 (smallest) to N (largest). In the initial configuration, all N disks disk at the bottom and the smallest at the top. The remaining two pegs (1 and 2) are initially empty. The goal is to transfer all disks from peg 0 to peg 2, maintaining the same size ordering (largest at bottom, smallest at top). This puzzle is governed by three fundamental constraints: (1) Single Disk Movement: Only one disk may be moved
stacked on the leftmost peg (peg 0) in descending order of size, with the largest
time; (2) Top Disk Access: Only the topmost disk from any peg can be selected for movement; and (3) Size Ordering Constraint: A larger disk may never be placed on top of a smaller disk. This puzzle a good evaluation testbed for reasoning and planning capabilities of models as it requires models to demonstrate key cognitive demands such as breaking down the problem into subproblems (recursive thinking), tracking multiple states and disk positions simultaneously (working memory management), adhering to movement rules and constraints while planning ahead (constraint satisfaction), and determining the correct order of operations achieve the final goal (sequential planning).
The minimum number of moves required to solve the Tower of Hanoi recursive puzzle with N disks is N - 1, making it an exponentially scaling problem. This property allows for fine-grained difficulty control by adjusting the problem size with number of initial disks. However, in our evaluation framework, we focus on solution correctness rather than optimality, assessing each of the move's validity and the model's ability reach the target state as the success criteria.
Prompt Design. The system prompt begins with a clear problem statement describing the puzzle setup. It explicitly states the movement rules and the objective of transferring all disks to the third peg. To facilitate understanding, the prompt includes example demonstrations as well as the critical formatting and reasoning expectations.
24

---

System Prompt- Tower of Hanoi
You are helpful assistant. Solve this puzzle for me. There are three pegs and disks of different sizes stacked the first peg. The disks numbered from (smallest) to n (largest). Disk moves in this puzzle should follow:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one stack and placing it on top of another stack.
3. A larger disk may not be placed on top of smaller disk.
The goal is move the entire stack to the third peg. Example: With disks numbered (smallest), 2, and 3 (largest), the initial state is [[3, 2, 1J.
[. [].. and solution might be:
moves
[[1, 2] [2, 0, 11 [1, 2, 11, [3, o, 2].
[1, 1, 0]. [2, 1, 2]. [1. 0, 2]]
This means: Move disk from peg 0 to peg 2, then move disk 2 from peg 0 to peg I, and so on. Requirements:
When exploring potential solutions in your thinking process, always include the corresponding complete list of moves.
The positions are O-indexed (the leftmost peg is 0).
Ensure your final answer includes the complete list of moves in the format: moves [[disk id, from peg, to peg], ...]
The user prompt after the system prompt presents the specific puzzle instance with current configura- tion showing the distribution of disks across pegs and the goal configuration specifying the target state,
User Prompt Template for $N$ Disks Tower Hanoi
have puzzle with SNS disks of different sizes with Initial configuration:
Peg SN$ (bottom), ... 2, (top)
Peg I: (empty)
Peg 2: (empty)
Goal configuration:
Peg O: (empty)
Peg 1: (empty)
Peg 2: SN$ (bottom), ... 2, (top)
Rules:
Only one disk can be moved time.
Only the top disk from any stack can be moved.
A larger disk may not be placed on top of a smaller disk.
Find the sequence of moves to transform the initial configuration into the goal configuration.
Simulator. Our evaluation framework employs separate puzzle simulators for each puzzle to ensure consistent assessment and rigorous failure analysis of solutions obtained from LRMs. The Tower of Hanoi simulator designed as stateful environment that tracks disk configurations across three pegs and validates each proposed move against the puzzle's fundamental constraints. The simulator architecture follows a modular design pattern with clear separation between state management, move validation, and solution verification. In this simulator, we have puzzle class which tracks the current
25

---

disk configuration and enforces the puzzle's fundamental constraints. We also have method to execute each move in the puzzle setup and perform four-layer validation: checking peg boundary conditions (0-2), verifying source pegs contain disks, confirming the specified disk is topmost, and enforcing the size ordering constraint that prevents larger disks from being placed on smaller ones. Upon successful validation, the method executes the disk transfer and updates the puzzle state. Finally, the complete solution validation processed by sequentially processing move lists, and verifying goal state achievement.
A.2.2 Checker Jumping
Problem Description. Checker Jumping is one-dimensional cattrrainn-satssfactiion puzzle de- signed to test sequential reasoning, planning, and rule understanding capabilities. The puzzle consists of a linear arrangement of red checkers ('R'), blue checkers ('B'), and single empty space ("""). In the standard configuration, NV red checkers are positioned on the left side, followed by an empty space in the middle, and N blue checkers on the right side, forming linear board of length 2N + The objective is to swap the positions of all red and blue checkers, effectively mirroring the initial configuration, where red checkers end up on the right and blue checkers on the left. Movement in this puzzle is governed by two fundamental rules: (1) Slide Movement: checker can slide forward into an adjacent empty space; and (2) Jump Movement: A checker can jump forward over exactly one checker of the opposite color to land in an empty space. Therefore, checkers cannot move backward toward their starting side-red checkers can only only move leftward from the initial configuration. This puzzle presents cognitive challenges that make it good testbed for reasoning models. For example, models must demonstrate some aspect of spatial reasoning (tracking checker positions and possible moves), constraint satisfaction (adhering to movement rules during puzzle), lookahead planning (anticipating how current moves affect future possibilities towards goal), and state-space exploration (searching through possible move sequences to find valid solution path).
rightward, and blue checkers can
The difficulty of the Checker Jumping puzzle scales with the number of checkers: with N checkers of each color, the minimum solution requires (N + 1) 1 moves, creating a quadratic relationship between problem size and solution complexity. In our evaluation framework, we mainly focus on solution correctness rather than optimality, evaluating each move against the puzzle constraints and confirming that the final state matches the goal configuration. This approach allows us to precisely identify reasoning failures and constraint violations that might occur during the solution process.
Prompt Design. The system prompt begins with clear problem statement describing the puzzle setup and movement rules. It explicitly states the objective and provides a concrete example with a small board configuration illustrate how moves should be represented.
System Prompt Checker Jumping
You are helpful assistant. Solve this puzzle for me. On one-dimensional board, there are red checkers ("R'), blue checkers ('B'), and one empty space ("_)). A checker can move by either:
1. Sliding forward into an adjacent empty space, or
2. Jumping exactly checker of the opposite color to land in empty space.
The goal is to swap the positions of all red and blue checkers, effectively mirroring the initial state.
Example: If the initial state is I'R', 'B'], the goal is to reach ['B', 'B', 'R']. Your solution should be list of moves where each move is represented as [checker_color position_fron position_to), For example:
[[>R², 0, 1]. ['B', 2, 0]. [RR,, 1, 2]]
This means: Move the red checker from position to 1, then move the blue checker from position 2 to 0, and Requirements:
26

---

When exploring potential solutions your thinking process, always include the corresponding complete list of moves.
The positions are O-indexed (the leftmost position is 0).
Ensure your final answer includes the complete list of moves for final solution in the format: moves [[checker_colon) position_from, position_tol, ....
The user prompt presents the specific puzzle instance with the initial board configuration, and the goal state.
User Prompt Template for $N$ Checkers Checker Jumping
have puzzle with 2SN$+1 positions, where SN$ red checkers ("R') on left, $NS blue checkers ("B') on right, and one empty space ("_") in between are arranged in a line.
Initial board: R R ... R
Goal board: B B B R..... Rules:
A checker can slide into an adjacent empty space.
A checker can jump exactly one checker of the opposite color to land in empty space.
Checkers cannot move backwards (towards their starting side).
Find the sequence of moves transform the initial board into the goal board.
Simulator. Our evaluation framework employs custom simulator for validating Checker Jumping puzzle solutions. The simulator implements a comprehensive validation system that enforces all puzzle constraints while tracking the state evolution throughout the solution path. The Checker Jumping simulator designed as a stateful environment that tracks the position all checkers and the empty space, validating each move of a given solution against the puzzle's 's movement rules. The simulator begins by validating that both the initial and goal states are generally well-formed, containing the same number of red and blue checkers and exactly one empty space. Then, each move is executed with method that performs multi-layer validation: verifying position boundaries, confirming correct checker color at source, ensuring target positions are empty, and validating move types as either slides (distance=1) or jumps (distance=2). The simulator enforces directional constraints preventing backward movement (red checkers only move right, blue checkers only move left) and validates jump moves by confirming the presence of an opposite-colore checker in the middle position. Upon successful validation, the method executes the checker transfer by updating positions and clearing the source. Then, the complete move sequences are processed with final goal state verification.
A.2.3 River Crossing
Problem Description. River Crossing is a constraint satisfaction planning puzzle that tests multi- agent coordination and constraint management. This puzzle is generalization of classic problems such as the Missionaries and Cannibals problem and the Bridge and Torch problem, which have been widely studied in planning literature [47 48). The river crossing puzzle involves N actors (denoted by 42 ... aN) and their corresponding N agents (denoted by Ai, A2, .... AN) who must cross river using a boat. In the initial state, all 2.V individuals are on the left bank of the river. The goal is to transport everyone safely to the right bank. The puzzle operates under several key movement constraints: (1) Boat Capacity Constraint: The boat can carry most individuals at time, where k is typically set to 2 for smaller puzzles (N < 3) and 3 for larger puzzles; (2) Non- Non-Empty Boat Con- straint: The boat cannot travel empty and must have at least one person aboard; (3) Safety Constraint: An actor cannot be in the presence of another agent unless their own agent is also present, as agents must protect their clients from competing agents. This safety constraint applies both on the banks and in the boat. This puzzle requires complex planning and state tracking as participants must carefully
27

---

coordinate their crossings while maintaining safety constraints at all times. The solver must reason through different combinations of individuals who can safely travel together, determine who should return with the boat after crossing, and strategically plan sequence that eventually brings everyone the right bank without violating any constraints. The complexity of this task can be controlled by adjusting the number of actor-agent pairs, creating a scalable challenge for reasoning models.
Prompt Design. The system prompt introduces the notation for representing actors and agents, establishes the solution format as a list of boat moves, and provides simple example to demonstrate the format.
System Prompt
River Crossing
You are helpful assistant. Solve this puzzle for me. You can represent actors with al, a2, ... and agents with A1, A2, Your solution must be a list of boat moves where each move indicates the people the boat. For example, if there were two actors and two agents, you should return:
moves= [[" A2", "a2"], [] ["A1", "A2"], ["A1"], ["A1", "a1 "]]
which indicates that in the first move, A2 and a2 from left to right, and in the second move, A2 rows from right to left and so on.
Requirements:
When exploring potential solutions in your thinking process, always include the corresponding complete list of boat moves.
The list shouldn't have comments.
Ensure your final answer also includes the complete list of moves for final solution.
The user prompt presents the specific puzzle instance with N actor-agent pairs, and the boat capacity k. and the safety constraint that must be maintained throughout the solution.
User Prompt Template for SN$ Pairs River Crossing
SNS actors and their $NS agents want to cross river in boat that is capable of holding only Sk$ people at time, with the constraint that no actor can be in the presence another agent, including while riding the boat, unless their agent is worried their rivals will poach their client. Initially, all actors and agents are on the left side of the river with the boat. How should they cross the river? (Note: the boat cannot travel empty)
agent is also present, because each
Simulator. Our evaluation framework employs custom simulator for validating River Crossing puzzle extracted solutions. The simulator tracks the state of individuals (actors and agents) and the boat position while enforcing all puzzle constraints. Each move is executed with multi-step validation: checking boat capacity limits, verifying all passengers are on the boat's 's current side, and enforcing the critical safety constraint that actors cannot be in the presence of other agents without their agent present, both on the boat and on each bank after the move. The simulator manages dynamic boat positioning, automatically switching sides after each crossing, and validates the complete state after each move to ensure no safety violations occur on either bank. Then, the complete crossing sequences are verified that all 2N individuals successfully reach the right bank.
A.2.4 Blocks World
Problem Description. Blocks World a classical planning puzzle that has been recently studied for
analyzing the planning capabilities of LLMs 38 40 The puzzle involves multiple stacks of blocks
(A, B, C, etc.) that must rearranged from an initial configuration to a specified goal configuration. Each block is uniquely identified by its letter, and the objective is to find the sequence of valid moves
28

---

needed to transform the initial state exactly into the goal state. The puzzle operates only under two fundamental constraints: (1) Top Block Movement: Only the topmost block from any stack can be moved; and (2) Valid Placement: A block can only be placed either on empry position or top of another block. These constraints create planning problem where the order of operations becomes critical, as some configurations may require temporary placement of blocks to access those beneath them later. Blocks World serves as a good testbed for evaluating planning capabilities reasoning models because it requires forward thinking. and state tracking. Recent studies have examined this puzzle various configurations, including simplified settings with as few as 3 to blocks, to evaluate LLM performance sequential planning tasks [38 40 49 Models must demonstrate the ability to decompose complex state transformations into valid sequential moves, reason about dependencies between blocks (e.g., unblocking lower blocks before accessing them), and efficiently plan paths to the goal state without illegal moves. Our design of this puzzle is motivated by recent works in literature [40 [49] but it's set 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).
The difficulty of this puzzle can be scaled by adjusting several parameters: the number of blocks, the number of stacks, and the complexity of the initial and goal configurations. We primarily control complexity through the block count N, while following clear structural patterns in the initial and goal configurations. In our experimental design, the initial configuration consistently divides the N blocks between two stacks in alphabetical order, with the third stack empty as workspace. The goal configuration consolidates all blocks onto the first stack in a systematic interleaved pattern that alternates between blocks from the two initial stacks, with specific positioning that requires complete disassembly and reassembly of the existing stacks. For example, for N 4, the initial state has blocks divided between two stacks [["A", "B"], ["C", "D"], []] and the goal state [["D", "B" "C", "A"], [], []] requires interleaving blocks from both stacks; and for N 6, the initial state [["A", ; "B", "C"]. ["D", "E", "F"), []] must be transformed to [["F", "c", "E", "B", "D", "A"], O []], forming complex alternating pattern. As N increases, the state space grows factorially, and the minimum solution length increases approximately linearly.
Prompt Design. The system prompt introduces the fundamental rules of the Blocks World puzzle, establishes the move representation format, and provides simple example demonstrate the solution structure.
System Prompt- Blocks World
You are helpful assistant. Solve this puzzle for me. this puzzle, there are stacks blocks, and the goal is to rearrange them into a target configuration using sequence of moves where:
Only the topmost block from any stack can be moved.
A block can be placed either on an empty position or on top of another block.
Example: With initial state [["A", "B"], ["C"], []] and goal state [["A"], ["B"], ["C"]], a solution might be:
moves [["C", 1, 2]. ["B", 0, 1]]
This means: Move block C from stack I to stack 2, then move block from stack to stack 1. Requirements:
When exploring potential solutions in your thinking process, always include the corresponding complete list of moves.
The positions are O-indexed (the leftmost position is 0).
Ensure your final answer also includes the complete list of moves for final solution in the format: moves [[block, from stack, to stack], ...]
The user prompt presents the specific puzzle instance with the initial and goal configurations provided, and explicitly reminds the model about the movement constraint.
29

---

User Prompt Template for $N$ Blocks- Blocks World
I have puzzle with SNS blocks.
Initial state:
Stack 0: Sblocks_dd 0$ (top)
Stack 1: $blocks 1$ (top)
Stack $mS $blocks_me (top)
Goal state:
Stack 0: Sgoal_blocks_ 0$ (top)
Stack 1: blocksoookhsoo 1$ (top)
Stack $mS
Sgoal blocks mS (top)
Find the sequence of moves to transform the initial state into the goal state. Remember that only the topmost block of each stack be moved.
Simulator. Our evaluation framework employs 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. Each move is executed in the puzzle setup with three-layer validation: verifying stack indices are within bounds, confirming the source stack contains blocks, and ensuring the specified block is at the top of its stack (enforcing the top-block-only movement rule). Upon successful validation, the block transfer is executed and the block is popped from the source stack and appended to the destination stack. Finally, the complete solution sequences of block movements are processed and verified that the resulting configuration matches the target goal state.
A.3 Implementation Details
Configurations. Our experiments primarily utilized reasoning models and their corresponding non-reasoning counterparts to enable thorough analysis of the RL-enabled long CoT (i.e.. thinking process). We specifically selected Claude 3.7 Sonnet (tinnkingnoon-thinknng)) and DeepSeek-R1/V due to their ability to provide access to intermediate reasoning traces (thinking tokens), a critical requirement for our analysis. For experiments focused solely on final accuracy metrics, we also included results from OpenAl's 03-mini models. For Claude 3.7 Sonnet (w. and w/o extended thinking) models we used maximum generation budget of 64,000 tokens, accessed through the API interface. Temperature is the default 1.0 for all API rus (Claude-3,)) 3.7-oonnee and 03-mini runs). The experiments with DeepSeek-R1, DeepSeek- V3, and DeepSeek-BB DeepSeek-Rl-Disillll on local servers with maximum generation length set to 64,000 and temperature set to 1.0. For each puzzle instance and complexity level, the results are reported on 25 samples per model. We apply a filtering process to ensure all analyzed samples are following the requested response format, including move sequences and reasoning steps as specified.
are conducted
Solution Extraction. A custom extraction pipeline was developed process model responses and intermediate reasoning traces (thoughts). The pipeline consists of several key components. We implemented flexible regex-based extractors to identify potential solution attempts in both the final response and thinking trace. The extraction process identify solution patterns using regular expressions (both explicit "moves =" patterns and alternative bracket-based solutions). We process and clean each extracted candidate solution by (i) Removing comments from the list (text following "y" in any line), and (ii) Normalizing move formats to what suggested in context ensure consistent structure. Then, we validate solution format and structure to filter out invalid matches. During the extraction, we also capture metadata of token position for each extracted solution. Notably, for accurate position tracking within thinking traces, we employed the same tokenizer (cls0Okbbase) as the corresponding model to count tokens across all experiments. Token positions were also normalized with respect to thought length enable cross-sample comparison. Finally, make sure
30

---

that the recorded solutions within the thought trace are unique and duplicate solutions (identical move sequences) were filtered. In case of duplicate solutions, only the first solution is recorded for analysis.
Solution Evaluation. After extraction, each solution candidate is passed to the corresponding rigorous puzzle simulator for fine-grained verification and failure analysis. The simulator takes solution as list of moves and evaluate that with respect to the puzzle (check App. A.2 for details of each puzzle simulator). Each move the compositional solution executed sequentially according to previous moves and the puzzle rules. At the end, the final state obtained from all moves in the sequence is compared to the goal state puzzle to determine full solution correctness. For incorrect solutions, details of first failure move and the type of failure is also collected during the move verification with puzzle simulator.
Execution of Prescribed Steps. addition to open-ended problem solving across different puzzles, we also conducted focused experiments to test how providing the explicit solving algorithm guidance with prescribed steps would affect behavior of these reasoning models (Sec.
We expected that finding and devising solution from scratch should require substantially more computation for model (e.g., for search and verification) than just following given algorithm's 's steps. However, results over two puzzles (Tower of Hanoi and Checker Jumping) in Figures g show that reasoning models' behavior does change that much and the collapse still occurs at roughly same points as before with this setting. This finding strengthens evidence that the limitation not just in problem-solving and solution strategy discovery but also in consistent logical verification and step execution limitation throughout the generated reasoning chains.
For example, models are provided with complete recursive algorithm of solving Tower of Hanoi and Checker Jumping puzzles as follows. These algorithm scratchpads were appended to the standard problem prompt test its impact reasoning behavior.
Example of Prescribed Algorithm for Tower of Hanoi
Here a pseudocode of recursive algorithm to solve the puzzle:
ALGORITHM Solve (n, source, target, auxiliary, moves)
// number of disks
// source = starting peg (0, 1, or 2)
// target destination peg (0, 1, or
// auxiliary = the unused peg (0, 1, or 2)
// moves = list store the sequence of moves
IF n equals 1 THEN
// Get the top disk from source peg disk the top disk on the source peg // Add the move to our list: [disk_id, source, target] ADD [disk, source, target] to moves RETURN
END IF
// Move n-1 disks from source to auxiliary peg Solve(n-1 source, auxiliary, target, moves)
// Move the nth disk from source target disk the top disk on the source peg ADD [disk, source, target] to moves
// Move n-1 disks from auxiliary target Solve Solve(n-1, auxiliary, target, source, moves) END ALGORITHM
31

---

Note: When executing this pseudocode, track which disk is currently on top of each peg. The disk IDs in the moves list should correspond the actual disk being moved. You can use this algorithm as scratchpad to help you solve the problem step by step.
Example of Prescribed Algorithm for Checker Jumping
Here is a pseudocode of recursive algorithm to solve the puzzle:
ALGORITHM Solve (board, goal, moves)
// board = current state (string with 'R' 'B', P_))
// goal target configuration
// moves = list to store the sequence of moves
IF board equals goal THEN RETURN moves
END IF
FOR each position i in board DO
IF [oard[i] is 'R' THEN
// Try moving R piece right (step jump) TryMove('R', i, i+1, board, goal, moves) TryMove('R', i, i+2, board, goal, moves) END IF
IF [oard[i] is 'B' THEN
// Try moving B piece left (step or jump) TryMove('B', i, i-1, board, goal, moves) TryMove('B', i, 1-2, board, goal, moves)
END IF END FOR
RETURN null // No solution found END ALGORITHM
FUNCTION PryMove(piece. from, to, board, goal, moves) IF to is valid position AND board[to] is ?_ THEN // Make the move nev_board copy of board SET new_board [from] '_ SET new_board
piece
// Recursively solve result Solve (new_board, goal, moves [piece, from, tol)
RETURN result
END IF END FUNCTION
Note: When executing this pseudocode, use backtracking and use TryMove function to validate that moves follow the rules (R moves right, B moves left, jumps are over opposite colors). You can use this algorithm scratchpad to help you solve the problem step by step.
A.4 Details on Computational Complexity
A.4.1 Compositional Depth Characterization
32

---

DeepSeokk
Claude 3.7 Sonnett (thinkinng)
Infermnce Compute (Tolems))
DeepS
Infermncc Computee (Toltems)
Claude-3. 3-nSonee (thinking)
Accutsay (S)
13300
4x0
Compesitional Depth (6 of Mieoo)
Compositional Depth @o of Moveal
Compostional Depth (4 Marwa))
10
10
Composttinal Depth (4 Marsns)
10
10
Tower Hanoi
Checker Jumping
River Crossing
Blockss World
Figure 11: Inference compute (tokens) and accuracy versus compositional depth (number of required moves) across puzzle environments for DeepSeck- RI and Claude 1oade-3.7-- 3.7-Sonnet (thinking).
Compositional depth is the number of sequential op- erations (i.e.. moves) required to completely solve the puzzle. Figure I0 demonstrates how this depth scales with problem size (N) across our four puz- zle environments. Each puzzle has a distinct growth pattern, reflecting its underlying computational com- plexity. For example, Tower of Hanoi shows exponen- tial growth (2 1), and Checker Jumping displays quadratic scaling ((N + 1)² - 1). The River Cross- ing and Blocks World puzzles show more moderate, near-linear growth with N. These varying compo- sitional depth profiles enable us to better evaluate how reasoning models approach different types of se- quential reasoning challenges and if their accuracy is always correlated with the computational complexity required to solve the puzzle. More details regarding this analysis is provided in Figure 11
Blocks World
60
Compositional Depth 6# Moves)
Checker jumping
Crossing
50
Tower Hanoi
30
20
10
Problem Size (N)
Figure 10: Compositional depth (number of moves required) across different problem sizes for our four puzzle environments.
A.4.2 Performance vs Compositional Depth
While intuition suggests negative correlation between problem computational complexity and model accuracy, our analysis reveals a more nuanced relationship between compositional depth and LRM performance which needs deeper discussion. Figure demonstrates this across three state-of-the-an reasoning models Claude-3.7-Sonne w. thinking, DeepSeek-R1, I, and o3-mini) on our puzzle suite. Within individual puzzle types, we observe the expected negative correlation: compositional depth increases, model accuracy consistently decreases. 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. For instance, models achieve >50% accuracy on Tower of Hanoi instances requiring approximately 102 moves, yet consistently fail on River Crossing or Cross Jumping puzzles with substantially lower compositional depth (~ 10 moves).
Although River Crossing may generally have higher branching factor than Tower of Hanoi, this comparison of computational complexity is asymptotic and does not hold for the small N values used in our experiments where collapse occurs. The search space for valid 11-move (N=3) River Crossing solution is vastly smaller than the search space for 255-move (N=8) Tower of Hanoi solution where models start to struggle. This might reflect the limited availability of River Crossing examples with larger N values in web-based training data, meaning LRMs encountered fewer such instances during their training phase. Ultimately, LLMs and LRMs represent complex systems whose problem-solving capabilities сannot 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. That's why our focus on complexity is mostly to track model behavior within each puzzle setting rather than between the puzzles.
33

---

Tower Hanoo
Checker jumping
Blocks World
River Crossinn
100
Acuunyy (4)
Owo AGR
S
Aouunny (990
0
OwneR
Owned 20n
Complexity (number of disksi
Raasca titen makion
Ranmanre Oifuce (7 (7dkoos
Owt 323
Def 201
Owe)
Owen 568
10
Complectt aonteraaaaai
Dorplnily ctercii
Comploily Oottber df
Componiy CEumbeEr poist
Figure 12: Comparison of reasoning ("thinking") and non-reasoning ("non-thinking") models for the QwQ-32B and Qwen2.5-32B backbone pair across all the controlled puzzle environments. Top: task accuracy (%) as function of problem complexity. Bottom: reasoning effort (measured by the number of thinking tokens) versus problem complexity. Shaded regions correspond to the three observed regimes of reasoning behavior low-complexity, mid-complexity and high-complexity Similar other model pairs (DeepSeek-RI V3 and Claude-3.7 3.nnontt w./w.o. thinking), QwQ-32B demonstrates an initial advantage in the mid-complexity regime but ultimately exhibits collapse behavior higher complexity levels with the counterintuitive decrease of reasoning effort after the collapse.
A.5 Inference Compute vs Compositional Depth
We extend analysis by examining how inference compute (i.e., the number of inference generated tokens) scales with compositional depth-a proxy for the number of reasoning steps/moves required reach a solution. Figure II presents this relation alongside task accuracy for the DeepSeek-RI and Claude-3.7-Sone 7-Sonnet (thinking) models across the four puzzle environments. Interestingly, compute allocation across puzzles is monotonic with respect 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 further supporting that their approach to complexity doesn't It necessarily align with the actual computational complexity of the problem.
A.6 Extended Results and Analysis
Additional Model Pairs (QwQ-32B vs Qwen2.5-32B). further validate the generality of our findings, we extended our experiments to include the Qwen backbone family, comparing the wwwtrrrrreennn-etaainnneeeeeeeee reasoning/non-thinkke
reasoning/thinking model QwQ-32B with its standard non- counterpart Qwen2.5-32B, These models follow the same experimental setup as in the main paper, evaluated across the four controlled puzzle environments: Tower of Hanoi, Checker Jumping, Blocks World, and River Crossing. As shown in Figure 12 this additional model pair exhibits similar trends with those observed for the DeepSeek-RR R1 vs V and Claude-3.7-Sond (w./w.o. thinking) pairs. Specifically, three distinct regimes of reasoning behavior emerge with respect to problem complexity. Quantitatively, the collapse points occur around N = for Tower of Hanoi, N 2 for Checker Jumping, N 10 for Blocks World, and N 3 for River Crossing. QwQ-32B also shows a counterintuitive reduction in reasoning effort (token count) near and beyond the collapse point, suggesting the similar scaling limit behavior with respect complexity.
Eliminating Sampling Effects. To examine whether sampling causes collapse behavior, we con- ducted ablation experiments using temperature zero eliminate sampling effects on solution length. These experiments used the DeepSeek-RR R1 reasoning model on local servers to ensure precise tem- perature control. 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. This indicates that sampling of long sequences is not the primary cause of the observed collapse behavior. In fact, sampling actually helps delay collapse slightly in Tower of Hanoi and Blocks World puzzles, as
34

---

Tower Hanoo
Checken Jumping
Blocks World
River Crossing
100
Degile Daerly
Dranly
Avcurac 196
Accuracc 180
Aucuracy
beedneoft:
Complesity Inamber Basao
Complesity (sumber checloeno
Complestty (number blocks)
Complesity (number of poors)
Figure 13: Performance comparison of the DeepSeek-RI model with sampling versus greedy generations (temperature=0) across all puzzles.
Tower of Hanoi
Checker Jumping
Blocks World
River Crossing
Claude33 3.0-l-37--oone (dusking)
Claude 3.7-tonnet C
250
Palture
100
10
bood
Complesity ONumber of Disko)
Complesity Oumber of Cherkers)
Compleciy (Number of Warke)
Complecty (Numbr of Pairs)
202
< DerpSink-R
+Ox Vo
Fullure Mave
150
100
10
15
1o0 o Ooo G
Complesly (Nuther of Dikaa
Camplesit (amberr of Chickers)
Complexit (Numbar Black))
Complexity (Number of Paina
Figure 14: The first failure move versus problem complexity (N) comparison for thinking and non-thinking models across puzzle environments. Top: Claude-3.7-Sonne comparison; Bottom: DeepSeek-R1 vs DeepSeek-V3.
For instance, in Tower of Hanoi, the R1 model with temperature 0 collapses N=8, whereas with sampling enabled, maintains 18.2% accuracy at N=8 and delays collapse until N=9, In Blocks World also the RI 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.
shown in Figure 13
Failure Analysis. Understanding where models fail within the compositional reasoning steps provides insights beyond binary success metrics. Our accuracy evaluation requires perfect execution of entire move sequences-a single incorrect move results in failure. To examine failure patterns more granularly, we analyze the compositional depth at which models first make incorrect moves across varying problem complexity levels.
Figures 14 and 15 show the failure move ID versus problem complexity (N) within the solution sequence across different models. In Figure 14, the top row compares Claude-3.7 3.ndee-.7--oneet with and without extended thinking capabilities, while the bottom row compares deepseek model variants: DeepSeek-R1 1 (thinking) with DeepSeek-V3 (non-thinking). Figure 15 also shows this for the 03-mini model variants. These comparisons demonstrates how thinking mechanisms of LRMs influence failure patterns in compositional reasoning tasks of puzzles with respect to complexity. Our analysis reveals several interesting findings. First, we observe that the failure move usually happens much earlier than the final move required to solve the puzzle across all environments. For example, the Tower of Hanoi with N=10 requires 103 moves, but the first failure move typically occurs 102 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). Similarly, the River Crossing puzzle with N=3 requires 11 moves to solve, but the first failure move happens as early as move Second, models exhibit inconsistent and mon-oonoooiic failure behavior with respect to problem complextty-instannee where models fail earlier in the solution sequence
35

---

Towar of Hamoi
Checker jumping
Blocks World
River Crossing
100
22
-d- a3-min (medium)
140
abomin Dhigh
120
100
Fallure
00
30
15
20 Complextyy (Number Blocka)
Complesity (Number of Disaa)
Complexiy (Number of Chockerss)
Compleaity (Number Pains)
Figure 15: The first failure move versus problem complexity (N) comparison for 03-mini model variants across puzzle environments.
Tower of Tanci
Checker Jump
Dlocksworld
River Cressing
Clanke 1.2 Sonnet (Linaasgh: 65.9
Clu Soaset (lannasgh: 9.5
614 Chands 5 7-5ccapot (taniaagi 8.4
"Chunse 3.P Sounsot (täikkagg: 3.4
Clrake-3 S-sonnet:: 27.7
C12
-osppptt 4.1
exe Cloude Preccioot: 6.7
Clarode-3 3. 7--eonze: 2:0
611
0
0.5
07
Fallure Move
Fallure Move
Fullure Move
Fulluro Move
0:00
Di 73.5
Dewf 9.9 Y3:
Seep-- 12.8
179 DieeSensk-t11 2.9
Vesp 40.8
V33 8/7
Doug Seap 3::2 2:3.
oxc
4.7
Futlure Move
Fallure Stove
Fuluure Move
Fature Move
Figure 16: Density distribution of first failure moves for thinking and non-thinking models across puzzle environments. Top: Claude-3.7-Sonnet comparison; Bottom: DeepSeek-RI vs DeepSeek-V3. V3.
for higher N values despite requiring longer overall solutions. For example, in Tower of Hanoi, models sometimes fail at below 50 moves for N 12 but succeed through more than 100 moves for N = 10, contradicting the expectation that effective algorithmic planning and exccution for the same puzzle should maintain consistent failure patterns relative solution progress. This suggests fundamental inconsistencies in how models (both LRMs and their non-thinking standard L.M counterparts) apply learned solution strategies across different problem scales. Also, observe that in the high-complexity regimes where both model variants experience complete accuracy collapse, e.g., Tower of Hanoi with N 2 8 and Blocks World with N > 30, non-thinking models occasionally sustain performance deeper into the solution sequence and are able to fail at later moves than thinking- enabled variants. This is interesting as it shows that compositional reasoning failures in LLMs are not simply due to insufficient context length or inference compute, but rather reflect fundamental limitations in how models apply maintain and apply algorithmic consistency across problem scales.
We also analyze the distributional characteristics of failure moves to understand the consistency and reliability of model reasoning. Figure 16 presents the density distributions of failure move positions aggregated across all problem complexities for each puzzle environment, comparing thinking and non-thinking models within the same family. Based on the figure, thinking models (Claude-3.7- Sonnet with thinking and DeepSeek-R1) consistently show higher mean failure positions across all puzzles, indicated by the dashed vertical lines showing mean of first failure in sequence of moves. 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.
Reasoning Effort Dynamics. Figure demonstrates the reasoning effort (measured by inference thinking tokens) versus problem complexity across our puzzle environments. Green dots indicate correct solutions, red crosses show incorrect ones, and blue lines track average thinking token usage at each complexity level (N) across different puzzles and LRMs. We observe a common pattern across most experiments with three reasoning models (eeepSeek-R1, Claude-3. -.i.e....-Snnee-tthiiii 03-mini) where thinking token usage, i.c. reasoning effort, initially scales with problem complexity
36

---

Thoerr Hanel
Chocker Junging
of Hanni
Checker jamppnn
Pecpdreol
parsspotttt Defaelt
Abymntur cive
Debutt
Accursss (N5)
Accurscy (182
12 15
Complettyy
Diskst
Complestty (Number Disks)
Complextyy Ohumber
Complestty Chockers)
Effect of algorithm provision on both reasoning (thinking) and non-reasoning (non- thinking) models (DeepSeek RI V3) across the Tower of Hanoi and Checker Jumping puzzles. "Default" denotes the original task prompt, while "Algorithm Given" includes the explicit step-by-step solving procedure the input.
Figure 17:
but later counterintuitively declines after reaching model-specific complexity threshold. This suggests an interesting and fundamental scaling limit 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.
Algorithm Provision Non- non-Reasoning Model. In addition the algorithm-provision experi- ments on reasoning models in Figure 8 we tested whether providing explicit solving algorithms could change collapse behavior in non-reasoning models, given recent evidence that RL-induced reasoning in LRMs may impair their instruction-folloving abilities [50]. As shown in Figure [7] both reasoning (DeepSeck-R) and non-reasoning (DeepSeck- V3) models demonstrate unchanged collapse points despite modest accuracy gains from algorithm provision at certain complexity levels. This indicates that while explicit instructions might improve local execution in some cases, the collapse most likely arises from deeper limitations in compositional representation and planning rather than the instruction-follle folllwwng deficiencies.
37

---

DeepSeek-RI
Claude-3.7 Baaude-37-Sonnet (+thinking)
03-mini (high)
Tower of Hanoi
Thinking Tokees
Thinktng Tokans
20,000
6.000
15,000
Thinking
33,000
4,000
10,000-
10.000
2,000
5,000
3,000
Complexity (Number of Disks)
Complexity (Number of Disks)
Complexity (Number Disks)
14,000
40,000
35,000
12,000
35,000
30,000
"ie Sr Whee miit
Chockor Jumping
Thinking Tokenss
10,000-
Thinking Tokens
30,0000
25,000
Thinking
6.000-
15,000
15,000
4,000
10,000
10,000
2,000
5,000
Complexity (Number Checksors)
Complexity (Number Checkers)
Complexity (Number Checkers)
16.000
14,000
River Crossing
Thinking Tokooss
12.000
Tokons
25,000-
Thinking Tokeens
66,000
10.000
20.000
80,000
8,000
15,000-
38,000
4.000
10,000
20,000
5,000
36,000
Complexity (Number of Pairs)
Complexity (Number of Pairs]
Complexity (Number of Paies)
14.000
30,000
Blocks World
Thinking Tokeets
12.000
Thinking Tokees
25.000
23,000
20,000-
20,000
8,000
15,000-
25,000
6,000-
8.000
10.000-
10,000
2,000
5,000-
5,000
10
d0
10
d0
10
30
Complexity (Number Blocks)
Complextty (Number Blocks)
Complexity (Number Blockss
Correct solutions
Incorrect solutions
Figure 18: Detailed results on reasoning effort (measured in inference thinking tokens) versus problem complexity (N) for three LRMs (DeepSeek-Ri R1, Claude-3. 3,7 --Sonnet with thinking, and o3- m3-min) across four puzzle environments.
38

---

Qualitative Examples of Thoughts in LRMs. Here are some qualitative examples of thinking traces for the Claude-3.7-Sonnee (thinking) reasoning model.
Example of failures in constraint understanding and verification for River Crossing with N 2:
<think>
Comprchension
Ok, this is constraint- puzzle. Let try understand the puzzle. We have actors: al and a2, two agents: Al and A2 where The constraints are: (1) no actor can be in the presence of another agent unless their own agent is also present, (2) the boat cannot travel empty... Let's understand the constraints more clearly Wait, I'm realizing that the constraint is clear to me. Let me restate it.. Actor al cannot be the presence of agent A2 unless agent A is also present.
Given these constraints, let's think through the solution.
Solution
Now let's start solving. First move: Two people have to cross from left to right. Let's try with Move I: [al, a2] cross from left to right Left side: A1, A2 Right side: al, a2.
False violation alarm! (Both agents still in the left bank)
Hmm, but now have problem. We need send someone back from the right to the left, but neither actor can go back alone (because they's d meet the other agent without their own).
Let's try another approach with Move 1: [A1, A2] cross from left to right, Left side: al, a2, Right side: A1, A2, Now, one agent has come back so Move 2: [A1] comes back from right to left, Left side: al, a2, A1, Right side: A2. But now we have a problem on the left side: a2 is with A1 but without A2, which violates constraint..
Let's try another approach with Move I: [al, A1] cross from left to right, Left side: a2, A2, Right side: al, A1. Move 2: [AI] comes back from right to left Left side: a2, A2, Al Right side: al.
False violation alarm! (Agent A2 is still in the left bank)
But now a2 is with Al without A2, which violates our constraint.
Let's try another approach with Move 1: [a2, A2] cross from left to right, Left side: al, Al, Right side: a2, A2. Move 2: [A2] comes back from right to left, Left side: al, A1, A2, Right side: a2
False violation alarm! (Agent A1 still in the left bank) But now al is with A2 without A1, which violates our constraint.
Let me try cross one actor-agent pair at time. Initial state: al: I., a2: L, A1: L, A2: L, boat on Left.;
Move 1: [al, A1] cross from left to right. State after Move 1: al: R, a2: L, A1: R, A2: L, boat
on Right;
Move 2: [A1] comes back from right to left State after Move 2: al: R, a2: L, Al: :: L, A2: L,
boat on Left;
Move 3: [a2, A2] cross from left to right. State after Move 3: al: R, a2: R, A1: L, A2: R.
boat on Right;
Move 4: [A2] comes back from right to left. State after Move 4: al: R, a2: R. Al: L, A2: L.
boat on Left;
Move 5: [A1, A2] cross from left right. State after Move 5: al: a2: R, A1: R. A2: R, boat
on Right.
Violation missed in Move 3! (A2 and al are in the left bank without Al).
39

---

Perfect! Everyone is now on the right side, and no actor was ever in the presence of another agent without their own agent also being present.
So this solution correct. All right, I'll make this solution my final answer: moves=[["al', 'AI"], [*A1"], ['a2", 'A2"), ['A2"], ['A1', 'A2']]
</think>
Final Answer
Final solution for the sequence of boat moves is: moves=[['al', ['A',,'' ['a2", 'A2'], ['A2'], ['AI', 'A2']]"
Wrong conclusion! The final solution incorrect. This solution fulfills all requirements everyone starts on the left side and ends on right side, the boat always carries or 2 people, and no actor is ever in the presence of another agent without their own agent also being present.
Example of overthinking in the thinking traces of model for Tower of Hanoi with N
<think>
Comprehension
Ok, let me try to understand this problem. I'm given Tower of Hanoi puzzle with 2 disks.
This is classic problem with well-known solution algorithm. Initial configuration:
Peg O: [2. 1J (bottom to top) Peg 1: [] Peg 2: []
Goal configuration:
Peg 0: [] Peg I: [] Peg 2: [2, 1] (bottom to top)
For Tower of Hanoi with disks, the minimum number of moves 2" 1. So with 2 disks, we need moves.
Solution
Let me solve this step by step:
First move: Move disk 1 from peg 0 to peg 1.
Peg 0: [2] Peg 1: [1] Peg
Second move: Move disk 2 from peg 0 to peg 2.
Peg 0: [] Peg I: [1] Peg [2]
Third move: Move disk 1 from peg 1 to peg 2.
Peg O: [] Peg 1: [] Peg 2: [2. 1]
So the solution is: moves [[1, 0, 11, [2, 0, 2], [1, 1, 2JJ This means:
Move disk from peg 0 to peg 1; Move disk from peg to peg 2: Move disk from peg to
peg 2;
Repeating the same solution (#1)
Let me double-check this solution: Initial state:
Peg 0: [2. 1] Peg I: [] Peg 2: []
After move
Move disk 1 from peg 0 to peg
Peg 0: [2] Peg 1: [1] Peg 2: []
After move Move disk 2 from peg 0 to peg
Peg 0: Peg 1: [1] Peg 2: [2]
After move Move disk from peg to peg
Peg 0: [] Peg 1: Peg 2: [2, 1]
Final state:
Peg 0: Peg 1: Peg 2: [2, 1]
This matches our goal configuration, so our solution is correct.
Repeating the same solution (#2)
40

---

Double checking:
Disk 1 (smallest) on top of Disk 2 (largest) on Peg 2. This looks correct, but let's look more closely at the specified goal configuration.
Goal configuration: Peg O: (empty) Peg 1: (empty) Peg 2: (bottom) I (top) There seems be a typo or incomplete information the goal configuration description. Let me assume that the goal is to move all disks Peg 2, with the smallest disk (1) on top of the largest disk (2), which is the standard Tower of Hanoi goal. This would match my solution above. But if read it literally, it says: Peg 2: (bottom) I (top) This could be interpreted as only having disk on peg 2, which doesn't I account for disk 2. Since this doesn't t make sense for Tower of Hanoi (we need move all disks), I'll assume the goal is have both disks on peg 2, with disk 2 the bottom and disk on top, which matches my solution.
So the answer is: moves [[1, 0, 11, [2, 2], [1, 1,
Repeating the same solution (#3)
Actually, let me carefully review the problem statement once more to make sure understand correctly. The goal is to: Move the entire stack the third peg (peg 2). Follow the Tower of Hanoi rules (no larger disk on smaller disk).
This confirms that want both disks peg with disk 2 the bottom and disk 1 on top. So my solution is correct. Let me follow the step-by-step instructions once more:
Move disk from peg 0 to peg 1: Peg O: [2] Peg 1: [1] Peg 2: []
Move disk from peg to peg 2: Peg O: [] Peg I: [1] Peg 2: [2]
Move disk from peg to peg 2:
Peg O: Peg I: Peg 2: [2, 1]
So the sequence of moves is: moves = [[1, 0, 1], [2, 0, [1,
Repeating the same solution (#4) Actually, just noticed an ambiguity. The problem statement says the goal configuration has: Peg 2: (bottom) (top) This could be interpreted having disk 1 (the smallest) both the bottom and top disk on peg 2, which would mean only disk on peg 2, and disk somewhere else. But this can't be the case because the problem statement also mentions "move the entire stack to the third peg". which means all disks should be on peg 2. Letts assume the goal configuration description meant say: Peg 2: 2 (bottom) (top)] This would be consistent with the standard Tower of Hanoi goal. Let me ensure haven't misunderstood the problem. The problem statement says the goal is to move the entire stack to the third peg. This means all disks should be on peg 2 at the end. Following the Tower of Hanoi rules, the disks should be arranged in ascending order from bottom top, which means: Peg [2. (bottom to top)
This is consistent with my solution: moves [[1, 0, 11, [2, 0, 21, [1, 1, 2]]
Repeating the same solution (#5) Actually, I'm second-guessing myself because the problem mentioned "find the minimum sequence of moves." For Tower of Hanoi with disks, the minimum number of moves is indeed 3, which matches our solution.
Let's be sure we' ve interpreted the notation correctly: "[disk id, from peg id, to peg id]" disk refers to the disk number (I for the smallest, for the next, and so on). from peg refers to the peg id from which the disk is being moved (0, 1, 2). to peg refers the peg id to which the disk is being moved (0, 1, or 2).
In our solution: 1. Move Disk 1 from Peg 0 to Peg 1: [1, 0, 1) Move Disk 2 from Peg 0 to Peg 2: [2. 0, 2] 3. Move Disk from Peg to Peg 2: [1, 1 So the final solution is: moves = [[I, 1 0, 1]. [2, 0, 2). [1, 2]]
I'm reassured that this is correct.
Repeating the same solution (#6)
41

---

Actually, I'm overthinking this. Let me just follow the standard algorithm for Tower Hanoi. For n=2 disks, the minimum number of moves is 2**2 = moves. The algorithm to move disks from source to target using auxiliary: Move n-1 disks from source auxiliary. Move the largest disk from source target. Move n-1 disks from auxiliary to target.
Applying this to our problem with n=2:
Move disk from peg 0 to peg 1; Move disk from peg 0 to peg 2; Move disk from peg to peg 2:
I'm confident this is the correct solution. This gives us: moves = [[I, 0, 11. 12, 0, 2], [1, 1, 2]] So in summary, the answer is: moves [[1, 0, 1J, [2, 21, [1. 2]]
</think>
42


Reviews:
[{"review_id": "pmPXhwZuSb", "reviewer": "Reviewer_3cZ8", "summary": "This paper provides a systematic evaluation of the reasoning ability of LLMs. In its settings of puzzle problems, the unique point about its problem setting is that its complexity can be manipulated, and reasoning traces can be explicitly analyzed. Based on the experiments, the paper shows that standard language models outperform LRMs at low complexity, thinking models excel at medium complexity, and both collapse at high complexity. Such results indicate unexpected scaling phenomena in reasoning learning and find that there is somewhere a boundary for the current reasoning model, regardless of computational cost.", "questions": "Could you provide the results for Qwen and QwQ on the puzzle problems?\nI noticed that Qwen appears only in Figure 6 and is not included in earlier figures. Is there a particular reason for this omission?\n\nCould you clarify how the algorithm is incorporated into the prompt?\nIt seems that providing the algorithm does not lead to significant performance differences in your results. However, as mentioned in [2], supplying correct exemplars can substantially improve performance on tasks like BlockWorld. Providing the algorithm should have similar effects. Could you share more details about your approach?\n\n\n\n[1] Anil et al. Exploring Length Generalization in Large Language Models\n\n[2] Zhao at al. Improving Large Language Model Planning with Action Sequence Similarity", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "strengths:\n\n(1) Controllable Task Complexity:\nThe use of controllable puzzle environments enables systematic adjustment of problem complexity while preserving logical consistency. This allows for more principled experimental design compared to standard math benchmarks, which are often affected by data contamination and uncontrolled variability.\n\n(2) Interesting and Timely Findings:\nThe discovery of the high-complexity collapse phenomenon in reasoning models is both interesting and relevant. The claim is carefully supported with experimental results, and the finding ties into current discussions on long-range modeling (LRM).\n\n\n\nweaknesses:\n\n(1) Lack of Theoretical Analysis on Complexity:\nThe paper does not clearly define task difficulty or provide theoretical assumptions about problem complexity. Different tasks may follow different scaling laws as their difficulty increases considering their parameters. Some problems like River Crossing can even suddenly becomes unsolvable when increasing its number of problem settings. Even though this is an empirical study, offering at least a provisional analytical model—such as relating compositional depth to compute scaling, or explaining reduced token usage as problems become harder—would strengthen the explanation of the observed collapse phenomenon. \n\n(2) Confounding Variable: LLMs’ Long-Context Length Ability:\nThe collapse in model reasoning may be partially due to limitations in the model’s long-context understanding. Since the models were not trained on sequences of this length, they may lose track of earlier information. Exploring strategies such as dynamically summarizing previous history or breaking problems into step-by-step segments could help address these issues. Prior work [1] also suggests that performance collapse can occur when models hit output length limits or fail to generalize to longer contexts.\n\n(3) Confounding Variable: Output Length Constraints:\nLLMs sometimes terminate generation prematurely if the output is too long, which might contribute to the observed collapse in reasoning. This tendency to stop early should be considered as a potential explanation.\n\n(4) Lower-than-Expected Blocksworld Performance:\nIn Figure 6 of [2], blocksworld performance is reported to be much higher than in this paper. More details on the experimental settings and possible reasons for this discrepancy would be helpful.\n\n[1] Anil et al. Exploring Length Generalization in Large Language Models\n\n[2] Zhao at al. Improving Large Language Model Planning with Action Sequence Similarity", "was_revised": true, "final_justification": "Most of my concerns are well-discussed by the authors, but I do think the problem settings need to be improved, and its claim is a little bit too strong.", "rebuttal": "Thank you for dedicating your time and expertise to review our submission. Please find our responses below. \n\n> Output Length Constraints: LLMs sometimes terminate generation prematurely if the output is too long, which might contribute to the observed collapse in reasoning. This tendency to stop early should be considered as a potential explanation.\n\nOur empirical evidence demonstrates that collapse behavior observed in experiments occur within the output limits in all puzzles. For the Tower of Hanoi specifically, with its exponential growth raising questions of context-limit failures, reasoning models begin to collapse at N=7-8, corresponding to 127-255 moves (as shown in Figure 4 and 10 in appendix) which is well within the context limits. More importantly, if we look deeper into the failure cases (like in Figure 8c and 11 in appendix), we see that the first failure move actually happens much sooner than the final move. For example, for ToH with N=10 (requiring 1023 moves), failure typically occurs within the first $\\sim$100 moves (10% of solution length); for N=8, which requires 255 moves, failure occurs around $\\sim$40 moves (15% of solution length). This indicates that model failures and particularly collapse behavior happen much earlier and are not due to premature outputs because of generation limits. To account for context limit concerns for large values of N in ToH, we have excluded N>12 from experiments. We do plan to update the camera-ready accordingly. \nNotably, N>12 lies within the third region, post-collapse (N=8), so this modification does not affect our core findings for this puzzle.\n\n> The paper does not clearly define task difficulty or provide theoretical assumptions about problem complexity. ... Different tasks may follow different scaling laws as their difficulty increases considering their parameters.\n\nThe theoretical scaling of computational complexity for puzzles in terms of compositional depth with respect to parameter N are already provided in the Appendix A.3 (e.g. Figure 9 shows the compositional depth with N for puzzles). You are correct that different tasks may follow different theoretical scaling with respect to N (as shown in Figure 9), however, theoretical computational complexity does not help here as it does not reflect the model behavior. LLMs (or LRMs) are complex artifacts and how they approach complexity does not necessarily correspond to the actual theoretical computational complexity of the problem and more to the learned solution distributions from their training data.\n\n> Even though this is an empirical study, offering at least a provisional analytical model—such as relating compositional depth to compute scaling, or explaining reduced token usage as problems become harder—would strengthen the explanation of the observed collapse phenomenon.\n\nThank you for the helpful suggestion. We have already examined accuracy vs. compositional depth in Appendix A.3 (Figure 10). Following your suggestion, we also analyzed inference compute (tokens) vs. compositional depth and found very similar patterns to Figure 6: models increase compute up to a complexity point, then counterintuitively decrease it for higher compositional depths. We also observe inconsistent compute allocation across puzzles, with models sometimes spending more tokens on problems with lower compositional depth and vice versa—further supporting that their approach to complexity doesn't necessarily align with actual computational complexity. We will make sure to include this analysis in the camera ready.\n\nRegarding reduced reasoning effort on harder problems, we hypothesize this happens when harder problems fall outside the frequent training distribution, causing uncertainty and scaling limits in compute allocation. While we cannot verify this without access to training data, our empirical results support this speculation. \n\n> LLMs’ Long-Context Length Ability: The collapse in model reasoning may be partially due to limitations in the model’s long-context understanding.. strategies such as dynamically summarizing previous history or breaking problems into step-by-step segments could help.. Prior work [1] also suggests that performance collapse can occur when models hit output length limits or fail to generalize to longer contexts.\n\nThank you for the suggestion. While we acknowledge that longer move sequences may reduce the chance of correct reasoning chains, our experiments and others' findings confirm that long context is not the primary cause for the observed collapse behavior in these puzzles. First of all, collapse also occurs in short-context tasks—e.g., River Crossing with N=3 (11 moves) and Checker Jumping with N=4 (24 moves)—indicating that failure is not solely due to sequence length.\nSecond, our ablations using deterministic decoding ($\\tau=0$) on open-source DeepSeek-R1 also show that removing sampling does not prevent collapse. In fact, sampling often delays it: eg ToH collapses at N=8 with $\\tau=0$ but extends to N=9 with sampling (18.2% accuracy at N=8). In Blocks World also $\\tau=0$ collapses at N=4 versus N=30 with sampling. These results suggest that sampling over long contexts is not the primary cause of collapse.\n\nAlso, a recent paper (Varela et al., 2025) has explored stepwise prompting and agentic strategies on these tasks (e.g., ToH, River Crossing), breaking them to step-by-step segments as reviewer suggested, but still finds similar collapse behavior (eg $\\sim$N=8 for ToH), supporting our conclusion that the collapse behavior lies in the model’s ability to generalize compositional reasoning with complexity—not just in handling long contexts.\n \n\n> In Figure 6 of [2], blocksworld performance is reported to be much higher than in this paper. More details on the experimental settings and possible reasons for this discrepancy would be helpful.\n\nThank you for raising this question. Performance discrepency is because of different designs in initial and target block configurations. [2] is only testing on the non-reasoning models (e.g. gpt-4o, gemini 1.5 pro, llama-3.1). Our design is 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). Details of our design for initial and target block configurations are already provided in the Appendix A.1.4 L963-971. We will make sure to clarify this further in the updated version.\n\n\n> Could you clarify how the algorithm is incorporated into the prompt? It seems that providing the algorithm does not lead to significant performance differences in your results. However, as mentioned in [2], supplying correct exemplars can substantially improve performance on tasks like BlockWorld. Providing the algorithm should have similar effects. Could you share more details about your approach?\n\nIn our experiments, we tested different algorithm incorporation methods: algorithm alone as scratchpad, and algorithm with execution examples on simple problems. Both settings showed very similar performance where algorithm provision does not change the observed collapse behavior. Details of these experiments are already provided in Appendix A.2 L1025.  \n\nOne may speculate that this observed performance for algorithm provision might be only true for ToH where algorithm is already more known for models; so in response, we also conducted additional experiments on Checker Jumping and our results show very similar behavior to what we observed on ToH where algrithm may lead to slight boost in the accuracy for some N but it generally does not change the collapse point. This behavior is also puzzling for us and we think it might be one of the key limitations of recent LRMs. Notably, [2] has only tested this with non-reasoning models, while our focus is on reasoning models. LRMs' failure in following algorithm steps might also partially relate to their weaker instruction-following capabilities (as shown by some recent works eg [3]). Exploring these puzzling behaviors and limitations in LRMs could be an important direction for future research.\n\n[3] Li et al., When Thinking Fails: The Pitfalls of Reasoning for Instruction-Following in LLMs, 2025\n\n\n> Could you provide the results for Qwen and QwQ on the puzzle problems? I noticed that Qwen appears only in Figure 6 and is not included in earlier figures. Is there a particular reason for this omission?\n\nFigure 6 includes R1-Distilled-Qwen specifically to compare with DeepSeek-R1 for examine of LRMs. Our main experiments which is the core for other figures focus on two reasoning/non-reasoning model pairs: DeepSeek-R1 vs V3, and Claude 3.7 Sonnet w. & w/o thinking.\nIn response to your suggestion, we also conducted additional experiments during rebuttal on QwQ-32B reasoning and its corresponding non-reasoning pair Qwen-2.5-32B. Results show very similar collapse behavior to other model pairs and will be included in the camera-ready version.\n\n---\nThank you once again for the thoughtful review. We noticed that several concerns raised in the reviews echo some misunderstandings about our methodology and findings. In our response, we have addressed each point with detailed evidence and clarification, while incorporating revisions where appropriate. We hope that our rebuttal address the reviewer's concerns, and if so, they would consider updating their score. We’d be more than happy to engage in further discussions."}, {"review_id": "D9vGtmpC0Q", "reviewer": "Reviewer_P5aZ", "summary": "The goal of this paper is to understand the true reasoning capabilities of Large Reasoning Models (LRMs), which are LLMs that generate \"thinking\" steps before outputting an answer. The paper argues that current evaluation on math/coding benchmarks is basically flawed due to possible data contamination (there is some evidence with AIME 24/25) and a lack of control over the complexity of the problem (which seems an important missing feature). To address these flaws, it proposes an evaluation framework using puzzles whose complexity can be “controlled” - in particular, four puzzles including Tower of Hanoi and Blocks World. Thus, it is able to systematically vary the puzzle complexity and study not only the final accuracy but also the accuracy/quality of the intermediate reasoning steps.\n\n\nThe paper is basically experimental.  By studying the four puzzles, it identifies three performance regimes wrt problem complexity: non-thinking LLMs are better in the low-complexity regime, LRMs are excellent in the medium-complexity regime, and both fail in the high-complexity regime.  In particular, all models experience a full performance collapse after a certain complexity limit. Even more surprisingly, the paper suggests that as problems approach this collapse limit, the models' reasoning effort decreases, suggesting a compute scaling limit.  The paper’s experiments also suggest inefficiencies including \"overthinking\" of LRMs on simple problems.", "questions": "- How would you answer the criticism in https://arxiv.org/html/2506.09250v1\n- How would you view your results with tool use?\n- How would you reconcile your finding (regarding supplying code) vs instruction-following abilities these models demonstrate on say many benchmarks?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n1. Good amount of novelty in using controllable puzzles to study LRMs\n2. Studying the reasoning trace is interesting and offers good insights\n3. The three regimes are a good empirical finding\n4. The paper is well written\n\n### Weaknesses\n1. Unclear if the paper’s experimental setup is completely accurate (see https://arxiv.org/html/2506.09250v1) - in particular, issues of model exceeding output  capacity (despite knowing the solution) and models faced with problems that are essentially infeasible\n2. Some lack of statistical significance analysis\n3. The finding of the three regimes is not too surprising - experience with thinking models has anecdotally suggested these regimes, but to its credit, this work seems to be one of the earliest to properly study and articulate it\n\n### Minor Typos \n- Line 59: \"put the emphasis\" -> \"putting the emphasis\"\n- Line 125: \"model thinks\"-> \"the model thinks\"\n- Line 127: \"corelation\" -> \"correlation\"\n- Line 173: \"in distibution\" ->\"in-distribution\"\n- Line 221: \"exists three\" -> \"exist three\"\n- Line 223: \"to obtain\" -> \"of obtaining\"", "was_revised": true, "final_justification": "The responses addressed some of my concerns.  I confirm my mild positive (revised) rating.", "rebuttal": "Thank you for dedicating your time and expertise to review our submission. Please find our responses below. \n\n> * Unclear if the paper’s experimental setup is completely accurate (see https://arxiv.org/html/2506.09250v1) - in particular, issues of model exceeding output capacity (despite knowing the solution) and models faced with problems that are essentially infeasible\n> * How would you answer the criticism in https://arxiv.org/html/2506.09250v1\n\nWe understand the reviewers' concern and have incorporated several modifications to address valid points while clarifying misunderstandings where appropriate:\n\n**Output Length Constraints on ToH.** Our empirical evidence demonstrates that collapse behavior observed in experiments occur within the output limits in all puzzles. For the Tower of Hanoi specifically, with its exponential growth raising questions of context-limit failures, reasoning models begin to collapse at N=7-8, corresponding to 127-255 moves (as shown in Figure 4 and Figure 10 in appendix) which is well within the context limits. More importantly, if we look deeper into the failure cases (like in Figure 8c and Figure 11 in appendix), we see that the first failure move actually happens much sooner than the final move. For example, for Tower of Hanoi with N=10 (requiring 1023 moves), failure typically occurs within the first $\\sim$100 moves (10% of solution length); for N=8, which requires 255 moves, failure occurs around $\\sim$40 moves (15% of solution length). This indicates that model failures and particularly collapse behavior happen much earlier and are not due to premature outputs because of generation limits. To account for context limit concerns for large values of N in ToH, we have excluded N>12 from experiments. We do plan to update the camera-ready accordingly. \nNotably, N>12 lies within the third region, post-collapse (N=8), so this modification does not affect our core findings for this puzzle.\n\n**Infeasibility on River Crossing.** Upon further experiments, we found that the puzzle dynamics shift considerably for N>5, where the optimal boat capacity is (k = 4) and fundamentally changes the problem structure. Indeed this has been an overlook from us and we have currently modified our environment to N <=5 to address this. We do plan to update the camera-ready accordingly. However, we would like to note that this modification also does not affect our core findings, as performance of models mostly collapse earlier from N=3.\n\n> How would you view your results with tool use?\n\nIt’s important to note that our objective is to assess models’ reasoning processes—their ability to understand problems, explore solution spaces, and execute logical steps—rather than merely achieving correct final answers. For the puzzles in our study, algorithmic solutions are very well-established as standard implementations. Allowing tool use would tell us nothing about their capacity for problem understanding, constraint reasoning, or multi-step logical execution. Tool usage becomes valuable when algorithmic codes for solving the problem are unknown and require compositional reasoning to be developed.\n\n> Some lack of statistical significance analysis\n\nWe would appreciate if the reviewer could further clarify on this. Figure 13 in the appendix already presents the full distribution of results across collected samples, different models, and complexity levels. Figures 7 and 12 in appendix also provide density distributions for more in-depth analyses of intermediate reasoning traces and failure moves, which together aim to support statistical significances of findings. \n\n> How would you reconcile your finding (regarding supplying code) vs instruction-following abilities these models demonstrate on say many benchmarks?\n\nThank you for the thoughtful question. It is true that LRMs' failure in following algorithm steps might also partially relate to their weaker instruction-following capabilities (as shown by some recent works eg [1]). To further investigate this, we conducted additional experiments during the rebuttal period with algorithm provision to non-reasoning models (eg DeepSeek-V3 and Claude 3.7 Sonnet w/o thinking). Results (to be included in the camera-ready) show that algorithm provision improves accuracy of non-reasoning models on some N, but—like LRMs—it still does not change the collapse point with increasing complexity, suggesting that failures and collapse behavior might be due to factors beyond instruction-following.\n\n[1] Li et al., When Thinking Fails: The Pitfalls of Reasoning for Instruction-Following in LLMs, 2025\n\n> The finding of the three regimes is not too surprising - experience with thinking models has anecdotally suggested these regimes, but to its credit, this work seems to be one of the earliest to properly study and articulate it\n\nThank you for the recognition of our contribution.\n\n---\n\n**Minor Typos.** Thank you for noting these. We will make sure to address them in the updated vesion. \n\n---\nThank you once again for the thoughtful review. We noticed that several concerns raised in the reviews echo some misunderstandings about our methodology and findings. In our response, we have addressed each point with detailed evidence and clarification, while incorporating revisions where appropriate. We hope that our rebuttal address the reviewer's concerns, and if so, they would consider updating their score. We’d be more than happy to engage in further discussions."}, {"review_id": "pSxIaoTv8d", "reviewer": "Reviewer_rPRW", "summary": "This work systematically investigates the reasoning capabilities of LLMs and Large Reasoning Models (LRMs) using controllable puzzle environments -- like Tower of Hanoi, Blocksworld, and River Crossing, amongst others -- that isolate problem complexity. The authors identify three performance regimes and show that beyond a certain complexity (third regime), LRMs exhibit a complete accuracy collapse and a surprising decline in reasoning effort. The authors raise important questions about the true nature of LRM reasoning and thinking abilities.", "questions": "* What is compositional depth (section 3.1)? How is it related to your definition of \"complexity\"?\n* What kind of sampling strategy and temperature were used? Did the authors try to see if reducing the temperature creates a big difference?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n* The paper addresses an important and timely question: evaluating the reasoning abilities of LLMs, and more importantly, LRMs.\n* The chosen evaluation problems are fundamental and carefully selected to mitigate data contamination, which is a pervasive issue in many standard benchmarks.\n* The experimental design includes comparisons between reasoning-enabled and non-reasoning counterparts of LLMs. This approach helps control for potential similarities in pretraining data and shared model behaviors, leading to better comparisons.\n\n\n**Weaknesses**.\nDespite a range of experiments, there seem to be serious flaws in the claims of the paper:\n\n* **Seemingly a lack of thorough analysis of reasoning traces.** The authors repeatedly claim to perform a detailed analysis of reasoning traces. However, the experimental results suggest that this analysis may not have been conducted as thoroughly as stated\n    - L282-287: Based on Figures 8a, 8b, the authors claim that the observed collapse happens around the same place in Tower of Hanoi despite providing the algorithm. The authors state that providing the algorithm should make it easier for the LLMs to output correct steps.  It is highly plausible — and even suggested by the authors themselves — that the ToH algorithm was included in the models’ pretraining data. In this case, the LLMs and LRMs might simply reproduce this known algorithm within their reasoning (CoT) traces. Consequently, the results presented in Figures 8a and 8b are unsurprising. Did the authors investigate the reasoning traces for any such behavior?\n    - Paper [1] shows that for n>=6, k>=4 is necessary to have a solution at all in River Crossing. However, it appears that the authors use k=3 for n>=4, so there are no solutions (L 195). \n    - Finally, in the third regime, have the authors analyzed whether LLMs and LRMs actually produce incorrect solutions, or if they instead *give up* beyond a certain point (which would explain their slight reduction in token usage in the hard regime)? It would be important to clarify whether such *lazy* solutions are counted as incorrect solutions in the reported metrics. Furthermore, have the authors considered whether it is even feasible to fit an explicit search process within the token limits of these models at larger problem sizes, despite LRMs having significantly higher token capacities?\n* **Flawed complexity analysis.**  The paper’s analysis heavily relies on measuring LLM performance against problem complexity measured primarily by the number of disks, people, or blocks. This approach could be flawed. Problem difficulty cannot be accurately assessed by instance size alone; it is also governed by factors such as action space size (i.e., branching) and requirement for backtracking (for dead ends). \n   - For e.g., River Crossing problems have a significantly larger action space than ToH. Even assuming a conservative branching factor ~ 10, a solution of length 3–4 already entails searching through $10^3 - 10^4$ possible action sequences, not accounting for backtracking necessitated by dead ends. This large search space differentiates these tasks from ToH (with either 1,2,3 actions), which has a narrow and structured move space despite a longer solution length. This discrepancy is further illustrated by Figure 6 (Accuracy and Thinking Tokens vs. Complexity). If plotted on a comparable scale along the x-axis, it becomes evident that the number of thinking tokens in River Crossing problems grows rapidly even at low “complexity” levels (e.g., with just 3 people), indicating substantial *hidden difficulty* not captured by simple size metrics.\n    - Additionally, recent works have emphasized analyzing LLM and LRM performance using computational complexity frameworks. Notably, [2] demonstrates that LLMs and LRMs struggle in \"hard\" regions of Satisfiability problems where no effective heuristics exist, even when instance sizes are modest. There, hardness is characterized by the ratio $\\alpha$ = #clauses / # variables, and it is shown that neither the number of clauses nor variables alone explains problem difficulty -- directly contradicting the assumptions made in this paper. While I acknowledge that computational complexity analyses can themselves be imperfect (e.g., due to dependencies on the model’s pretraining data), this does not justify disregarding such frameworks entirely and attributing the observations instead to *puzzling behavior* (section 4.4) \n\n[1] River Crossing Problems: Algebraic Approach, Efimova et al., 2018  \n[2] Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition; Hazra et al., 2025", "was_revised": true, "final_justification": "The authors have identified and corrected the shortcomings of their experimental settings and have promised to update the results in their final version. In general, most of the conclusions drawn from the initial version remain the same, and some of the results are interesting for the community to reflect on and improve upon. I believe the rebuttal process has been useful for both the authors and me since I have had time to reflect upon some of the results and perceive them from the authors' point of view. That also helped resolve some of my earlier doubts, especially about analysing from a computational complexity perspective -- which, as the authors have argued -- might not always be the right way of evaluating LLMs.", "rebuttal": "Thank you for dedicating your time and expertise to review our submission. Please find our responses below.\n\n> L282-287: Based on Figures 8a, 8b, the authors claim that the observed collapse happens around the same place in Tower of Hanoi despite providing the algorithm. The authors state that providing the algorithm should make it easier for the LLMs to output correct steps. It is highly plausible — and even suggested by the authors themselves — that the ToH algorithm was included in the models’ pretraining data. In this case, the LLMs and LRMs might simply reproduce this known algorithm within their reasoning (CoT) traces. Consequently, the results presented in Figures 8a and 8b are unsurprising. Did the authors investigate the reasoning traces for any such behavior?\n\nThe critic suggests that the findings of algorithm execution limitation in LRMs may be only an artifact of the ToH’s well-known recursive algorithm being already memorized by models, rather than indicating a general limitation in algorithm execution. To investigate this, we conducted additional experiments on Checker Jumping puzzle, with some different characteristics: it requires fewer moves than ToH, exhibits earlier collapse behavior, and appears to have less algorithmic familiarity. If the critic’s hypothesis were correct, we should observe clear benefits from algorithm provision in this problem. However, our results show very similar patterns for both puzzles (to be included in the camera ready). Even when given explicit algorithm steps—requiring only execution rather than problem-solving—models show no meaningful improvement on either puzzle, with collapse happening at similar points. These results further validate our findings regarding limitations in the execution of logical steps and suggest a more fundamental failure mode rather than one specific to the ToH. \n\n> Paper [1] shows that for n>=6, k>=4 is necessary to have a solution at all in River Crossing. However, it appears that the authors use k=3 for n>=4, so there are no solutions (L 195).\n\nThank you for pointing this out. Upon further experiments, we found that the puzzle dynamics shift considerably for N>5, where the optimal boat capacity is (k = 4) and fundamentally changes the problem structure. Indeed this has been an overlook from us and we have currently modified our environment to N <=5 to address this. We do plan to update the camera-ready accordingly. However, we would like to note that this modification does not affect our core findings, as performance of models mostly collapse earlier from N=3. \n\n> Finally, in the third regime, have the authors analyzed whether LLMs and LRMs actually produce incorrect solutions, or if they instead give up beyond a certain point (which would explain their slight reduction in token usage in the hard regime)? It would be important to clarify whether such lazy solutions are counted as incorrect solutions in the reported metrics. Furthermore, have the authors considered whether it is even feasible to fit an explicit search process within the token limits of these models at larger problem sizes, despite LRMs having significantly higher token capacities?\n\nThank you for the thoughtful question. \nRegarding the feasibility of solutions in token limits, our empirical evidence demonstrates that collapse behavior observed in experiments occur within the token limits in all puzzles. For the ToH specifically, with its exponential growth raising questions of context-limit failures, reasoning models begin to collapse at N=7-8, corresponding to 127-255 moves (as shown in Figure 4 and 10 in appendix) which is well within the generation limits. More importantly, if we look deeper into the failure cases (like in Figure 8c and 11 in appendix), we see that the first failure move actually happens much sooner than the final move. For example, for ToH with N=10 (requiring 1023 moves), failure typically occurs within the first $\\sim$100 moves (10% of solution length); for N=8, which requires 255 moves, failure occurs around $\\sim$40 moves (15% of solution length). This indicates that model failures and particularly collapse behavior happen much earlier and are not due to premature outputs because of token limits. To account for context limit concerns for large values of N in ToH, we have excluded N>12 from experiments. We do plan to update the camera-ready accordingly. \nNotably, N>12 lies within the third region, post-collapse (N=8), so this modification does not affect our core findings for this puzzle. For all other puzzles, solution lengths are short enough that search process easily fits within context limits and reach to final move. \n\nRegarding incorrect solutions versus giving up, can reviewer clarify what they mean? we confirm that models continue generating full solutions after the first failure move until reaching end /token limits. However, near collapse, they start to counterintuitively reduce reasoning effort with complexity (less thinking and reflecting) which is observed across all puzzles regardless of the solution length.\n\n\n> Flawed complexity analysis. The paper’s analysis heavily relies on measuring LLM performance against problem complexity measured primarily by the number of disks, people, or blocks. This approach could be flawed. Problem difficulty cannot be accurately assessed by instance size alone; it is also governed by factors such as action space size (i.e., branching) and requirement for backtracking (for dead ends).\nFor e.g., River Crossing problems have a significantly larger action space than ToH. Even assuming a conservative branching factor ~ 10, a solution of length 3–4 already entails searching through $10^3 - 10^4$ possible action sequences, not accounting for backtracking necessitated by dead ends. This large search space differentiates these tasks from ToH (with either 1,2,3 actions), which has a narrow and structured move space despite a longer solution length. This discrepancy is further illustrated by Figure 6 (Accuracy and Thinking Tokens vs. Complexity). If plotted on a comparable scale along the x-axis, it becomes evident that the number of thinking tokens in River Crossing problems grows rapidly even at low “complexity” levels (e.g., with just 3 people), indicating substantial hidden difficulty not captured by simple size metrics.\n\nWe respectfully disagree with the reviewers' assertion that our analysis is flawed. \nFirst of all, the statement pointed out by reviewer is not mathematically correct. While the branching factor in River Crossing is larger than in ToH, the search space for a valid 11-move solution (N=3) is vastly smaller than the search space for a 127-move (N=7) ToH solution. Specifically, in River Crossing with N=3, search space contains of $2^{2N+1}$=128 states and in ToH with N=7 search space contains of $3^N$=2187 states, yet models fail on the former and succeed on the latter. This indicates that how LLMs approach complexity does not necessarily corresponds to the actual computational complexity of the problem and more to the learned solution distributions. That’s why our focus on complexity is mostly to track model behavior within each puzzle setting rather than between the puzzles.\n\nSecond, reviewer states that we solely rely on the problem size (N) while neglecting the search space and compositional depth with N, however, we have already discussed about this compositional depth for all puzzles in Appendix A.3 (Figure 9) and show the performance with respect to it (Figure 10) which is what reviewer is suggesting as \"plot with comparable x-axis\". Still, we observe that even tasks with low depth can face collapse, indicating that learned solution distribution is most likely the dominant factor for model behavior.\n\n> What is compositional depth of (section 3.1)? How is it related to your definition of \"complexity\"?\n\nThe compositional depth of all puzzles across N is already discussed in Appendix A.3.\n\n> ..While I acknowledge that computational complexity analyses can themselves be imperfect (e.g., due to dependencies on the model’s pretraining data), this does not justify disregarding such frameworks entirely..\n\nComputational complexity has been already discussed in the Appendix A.3. As model behavior does not necessarily reflect the computational complexity (elaborated above with multiple evidence), we mostly rely on empirical observations within each task, which better capture model behavior given the unknowns in training data.\n\n\n> What kind of sampling strategy and temperature were used? Did the authors try to see if reducing the temperature creates a big difference?\n\nAs noted in our experimental setup and implenetation details (sec 4.1 and A.2 in appendix), currently temperature 1 is used for sampling. In response to the reviews, we conducted additional ablation experiments with temperature $\\tau=0$ on open-source DeepSeek-R1 (to ensure precise local control). Our results show that reducing temperature and eliminating sampling generally does not prevent collapse—in fact, sampling often slightly delays it. For example, Tower of Hanoi with $\\tau$=0 causes collapse at N=8, while sampling extends performance to N=9 (18.2% accuracy at N=8). In Blocks World also= $\\tau$=0 causes collapse at N=4 versus N=30 with sampling. \nWe will include this analysis in the camera-ready version.\n\n---\nThank you once again for the thoughtful review. We noticed that several concerns raised in the reviews echo some misunderstandings about our methodology and findings. In our response, we have addressed each point with detailed evidence and clarification, while incorporating revisions where appropriate. We hope that our rebuttal address the reviewer's concerns, and if so, they would consider updating their score. We’d be more than happy to engage in further discussions."}, {"review_id": "7KtsYShblx", "reviewer": "Reviewer_K8Ta", "summary": "This paper compares and contrasts reasoning models with \"classic\" large language models in a controlled environment, namely, solving puzzles. The puzzles have well-defined complexities to evaluate how well models perform in terms of different problem complexities. The study finds that the large reasoning models do not always show a performance gain across different complexities compared to traditional large language models: they perform comparably, or even underperform traditional models in low-complexity scenarios; outperform traditional models in medium-complexity scenarios; and collapse as traditional models do in high-complexity scenarios.", "questions": "Please see weaknesses above. Beyond the weaknesses, can the authors also clarify why the easy-medium-hard regimes in Figure 4 seem to vary by model and tasks?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well written and easy to follow (clarity). Figures present the results very well.\n\n2. The topic is important: whether reasoning models can really \"reason\" or is it a misnomer? It is also important to find why and when we need reasoning models (significance).\n\n3. The experiment is carefully designed with several tasks (quality).\n\n4. The testing of reasoning models on complexity-controlled tasks is novel (novelty).\n\nWeaknesses:\n\n1. The motivation to mitigate contamination is not very well supported by the experiment setting (quality). I understand that the authors want to set up an environment that is generated on the fly, but as the authors note on page 9, line 295, that LRMs might still memorize instances during training for known tasks with specific variables. This is also well documented in existing works such as [1].\n\n2. Can the authors estimate and clarify whether the hard problems are actually solvable within the context window of these models? The authors note that the models' output lengths for hard problems are even lower than simpler problems, but is it possible that the models know the problems are not solvable, so that they just use a lower output budget to reduce the cost and terminate the reasoning? If so, this is not a \"bad\" phenomenon from my point of view, as can also be seen in [2, 3] and other works to improve inference efficiency.\n\n3. Personally, I think it is not surprising that LRMs perform comparably or underperform LLMs in low-complexity settings, outperform them in medium-complexity settings, and collapse with them in high-complexity settings. If tasks are very easy, we do not need very advanced models (e.g., what is the answer to 1+1). When tasks are very hard, even very advanced models cannot solve the problem (e.g., prove the Riemann Hypothesis). The places where LRMs are useful are exactly in the problems that are neither extremely easy nor extremely hard.\n\n4. The significance of the tasks is questionable in my opinion. I wonder how often real-life users use reasoning models to solve logic puzzles like those examined in this paper. It is, of course, not difficult to come up with very difficult questions to make models fail, but what is important is to identify real-life critical tasks that the models still cannot do for users. This is also acknowledged in the limitations section of the paper.\n\n[1] Prabhakar, A., Griffiths, T. L., & McCoy, R. T. (2024). Deciphering the factors influencing the efficacy of chain-of-thought: Probability, memorization, and noisy reasoning. arXiv preprint arXiv:2407.01687.\n\n[2] Damani, M., Shenfeld, I., Peng, A., Bobu, A., & Andreas, J. (2024). Learning how hard to think: Input-adaptive allocation of lm computation. arXiv preprint arXiv:2410.04707.\n\n[3] Manvi, R., Singh, A., & Ermon, S. (2024). Adaptive inference-time compute: Llms can predict if they can do better, even mid-generation. arXiv preprint arXiv:2410.02725.", "was_revised": true, "final_justification": "My concerns have been resolved.", "rebuttal": "Thank you for dedicating your time and expertise to review our submission. Please find our responses below.\n\n\n> Can the authors estimate and clarify **whether the hard problems are actually solvable within the context window** of these models? The authors note that the models' output lengths for hard problems are even lower than simpler problems, but **is it possible that the models know the problems are not solvable, so that they just use a lower output budget** to reduce the cost and terminate the reasoning? If so, this is not a \"bad\" phenomenon from my point of view, as can also be seen in [2, 3] and other works to improve inference efficiency.\n\nThat's a great question and thank you for raising this interesting point for discussion. \nFirst of all, we do clarify that based on our empirical evidence, collapse behavior observed in experiments occur within the output limits in all puzzles. \nFor the Tower of Hanoi specifically, with its exponential growth which has raised questions of context-limit failures, reasoning models begin to collapse at N=7-8, corresponding to 127-255 moves (as shown in Figure 4 and Figure 10 in appendix) which is solvable well below the context window limits. To account for context limit concerns for large values of N in ToH, we have excluded N>12 from our experiments (to be updated in the camera-ready). For N<=12, the problems are solvable within the context window, yet models still lower their reasoning length (tokens) with complexity after the collapse ($\\sim$N=8). This indicates that lowering reasoning budget observed in our experiments is not happening because of the unsovability of problems in the context window limits. \n\nAlso, for other puzzles, the solutions are always solvable within the context window limits yet we still observe this counterintuitive lowering of reasoning budget after a complexity point. For River Crossing specifically, concerns about infeasibility for N>6 are not due to context limits but rather stem from the mathematical properties of the problem itself, which requires k>3 when N>5. Upon further experiments, we found that the puzzle dynamics shift considerably for N>5, where the optimal boat capacity is (k = 4) and fundamentally changes the problem structure. So, we have modified our environment on this puzzle to N <=5 (to be updated in the camera-ready). For problems with N<=5 where solutions are feasible and fit well within context limits, most models (except o3-mini-high) still show the counterintuitive drop in reasoning budget after collapse (N ≈ 3).\n\n> The motivation to mitigate contamination is not very well supported by the experiment setting (quality). I understand that the authors want to set up an environment that is generated on the fly, but as the authors note on page 9, line 295, that LRMs might still memorize instances during training for known tasks with specific variables. This is also well documented in existing works such as [1].\n\nThank you for the insightful comment. We agree with the reviewer that contamination cannot be entirely ruled out by complexity, without knowing about the model training data. However, by systematically manipulating complexity per problem, we empirically observe degradation in performance of models—even when solution lengths are short, e.g., Checker Jumping (24 moves, N=4) and River Crossing (11 moves, N=3). This trend indicates that complexity can in fact act as a useful lens to probe model behavior, beyond what is captured in common uncontrollable benchmarks.\n\n> The significance of the tasks is questionable in my opinion. I wonder how often real-life users use reasoning models to solve logic puzzles like those examined in this paper. It is, of course, not difficult to come up with very difficult questions to make models fail, but what is important is to identify real-life critical tasks that the models still cannot do for users. This is also acknowledged in the limitations section of the paper.\n\nYes. While logic puzzles may not reflect everyday user queries, they offer envrionments for controlled and step-by-step evaluation of core reasoning capabilities. We think that these tasks can serve as diagnostic tools and a good first step towards understanding the behavior of models under controllable settings: if models struggle with simple and step-by-step verifiable reasoning, it raises concerns about their reliability in more complex and open real-world scenarios.\n\n>  Beyond the weaknesses, can the authors also clarify why the easy-medium-hard regimes in Figure 4 seem to vary by model and tasks?\n\nThe easy–medium–hard regimes in Figure 4 are defined based on the performance comparison for each reasoning vs non-reasoning model pair with respect to N at each task. A regime is labeled easy where non-reasoning model perform comparably or better, hard where both model types collapse, and medium where reasoning model show clear advantage.\n\n\n---\nThank you once again for the thoughtful review. We noticed that several concerns raised in the reviews echo some misunderstandings about our methodology and findings. In our response, we have addressed each point with detailed evidence and clarification, while incorporating revisions where appropriate. We hope that our rebuttal address the reviewer's concerns, and if so, they would consider updating their score. We’d be more than happy to engage in further discussions."}]

Author rebuttal:

Meta-review: In ‘The illusion of thinking’ the authors consider the strengths and limits of reasoning models be testing them with four different problem classes where the model must find a sequence of legal moves to transform an initial state to a specified end state.  Problems in each class can be constructed to vary in what the authors call ‘complexity’, operationalized as a variable N that controls the minimum number of moves required to achieve a solution.  For example, in the tower of Hanoi problem, a stack of N discs must be moved from one peg to another under constrained rules.  As N increases, then number of moves required to solve the task increases.  The paper compares matched models with base and ‘thinking’ variants, and reports several fairly consistent patterns.  First, for low-complexity problems, the base and thinking variants perform well, but the thinking variants produce more tokens.  Second, for intermediate complexity problems, thinking models outperform base variants, but begin to fail while generating longer and longer chains of thought.  Third, there is a critical difficulty level (specific to each model and problem type) where the thinking models performance ‘collapses’, i.e. its accuracy falls to zero.  Beyond this point, rather than continuing to generate even longer trains of thought on even harder problems, the models actually end their responses after somewhat shorter sequences.  Another finding is that thinking models tend to generate correct answers within their thinking traces well before they stop ‘thinking’ – a phenomenon others have described (as the authors acknowledge) called ‘overthinking’.  The authors are able to assess whether particular solution steps are valid or not within thinking traces and find that for simpler problems, earlier solution steps can sometimes be more accurate, while for harder problems, earlier steps tend to be incorrect while later steps are more likely to be accurate.

The reviewers identified several strengths of the work, including the timeliness of understanding the performance of reasoning models, the use of problems that vary parametrically in the number of solution steps required, the value of comparing base and reasoning variants of the same model, and the complex three stage pattern that these comparisons contributed to delineating.  All of the reviewers cited weaknesses; some of these reflected misunderstanding or missed information on first reading, while others were resolved with clarifications after a productive back and forth exchange.  Still others were addressed with additional results.
All reviewers acknowledged the responsiveness of the authors to their concerns.  In the end, 3 of the 4 reviewers gave the paper a 4/borderline accept rating, with the fourth stuck with their initial 3/borderline reject rating.  

After reading the paper and the exchange with the reviewers, I find myself in agreement with the majority opinion that the paper falls in the borderline acceptable range.  The stated plans for revision make me guardedly optimistic that the final product will be much clearer and stronger than the original, leading me to recommend acceptance of the article a poster, space permitting.

Whether the article is finally accepted or not, I hope to authors will pursue the work to publication.  Producing a strong publication will require great care in ensuring that many points are clearly addressed within the body of the article to avoid the confusions some of the reviewers experienced.   For example, ‘complexity’ is used quite vaguely in the main text – the discussion in Appendix 3 gives it considerably more meaning and this should be more fully addressed in the text.  Furthermore, the authors appear to vacillate on the extent to which it is reasonable to assume the models have not been extensively contaminated by related problems in their training data.  I’d suggest considerable caution here, and not just in the case of the tower of Hanoi problem.  The final version of the paper should also reconsider the authors’ characterization of the tendency reasoning models sometimes show to produce shorter reasoning traces when given problems beyond the complexity threshold where accuracy drops to 0 (e.g., in Fig 1, bottom middle, when the number of disks in the tower of Hanoi problem is 15 or 20). The authors characterize this (line 72) in terms of ‘reducing reasoning effort’.  However, this may not be the right way to characterize the phenomenon. Like one of the reviewers, I felt it was very important to know that these were not cases where the model simply gives up – instead they were cases where the model produced its final (always false) solution more quickly as complexity increased.  The fact that the model reaches incorrect solutions more quickly as complexity increases is consistent with the idea that the model may lose sensitivity to whether a tentative solution is valid as complexity becomes to great.

More generally, I think a great deal of humility is required in offering interpretations of the patterns the authors have uncovered.  I hope they with read the paper over with a very critical eye with this point in mind as they finalize the paper for publication.
Decision: Accept (poster)