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

Parshin Shojaee; Iman Mirzadeh; Keivan Alizadeh; Maxwell Horton; Samy Bengio; Mehrdad Farajtabar

Source-linked AI summary

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

Parshin Shojaee, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, Mehrdad Farajtabar

arXiv:2506.06941v3Jun 7, 2025cs.AIcs.CLcs.LG

TL;DR

The paper asks whether LRMs possess generalizable reasoning capabilities and how their performance and reasoning effort scale with problem complexity, beyond contaminated, final-answer-focused benchmarks. It uses controllable algorithmic puzzles to vary complexity and inspect both solutions and reasoning traces. LRMs outperform standard LLMs only at moderate complexity, then both collapse at high complexity while LRMs reduce reasoning effort near the threshold.

Problem
Existing evaluations emphasize final accuracy on math and coding benchmarks, but contamination and limited access to intermediate traces leave LRM reasoning and complexity scaling insufficiently understood.
Method
The paper evaluates matched reasoning and non-reasoning models in controllable algorithmic puzzles that vary complexity while preserving logical structure and expose reasoning traces.
Results
Standard LLMs outperform LRMs at low complexity, LRMs have an advantage at moderate complexity, and both approaches collapse at high complexity; LRM reasoning effort also decreases near collapse.
Takeaways & Limitations
LRMs provide a conditional advantage rather than generalizable problem-solving ability, with self-correction and inference-time reasoning showing clear complexity-dependent limits.
Takeaways & Limitations
The puzzle environments cover a narrow slice of reasoning tasks, and black-box access to closed LRMs limits mechanistic analysis of internal states and architecture.

Abstract

from arXiv · show

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

1 Introduction

The paper argues that existing evaluations leave LRM reasoning mechanisms and complexity scaling insufficiently understood, so it uses controllable puzzles to inspect answers and reasoning traces. It finds distinct complexity regimes, collapse beyond thresholds, declining reasoning effort near collapse, and limitations in self-correction and exact computation.

Existing math and coding evaluations often suffer from contamination and cannot systematically vary complexity or reveal intermediate reasoning traces.
The study uses algorithmic puzzle environments that vary complexity while preserving core logic and enable verification of both solutions and reasoning traces.
Standard LLMs outperform LRMs on low-complexity tasks, LRMs gain an advantage at moderate complexity, and both collapse at high complexity under equivalent inference compute.
Reasoning traces shift from early correct solutions and overthinking to extensive incorrect exploration, then fixation on early errors beyond a complexity threshold.
LRMs fail to develop generalizable problem-solving capabilities and show limited exact computation, including failure to benefit from explicit algorithms and inconsistent reasoning across scales.
LRM reasoning effort decreases after specific complexity points despite remaining below generation length limits, revealing an inference-time scaling limitation.

2 Related Works

Related work identifies unresolved questions about whether reasoning-model gains reflect data exposure, additional inference compute, or capabilities developed through reinforcement learning. It motivates controlled puzzle environments and trace-level analysis beyond final benchmark accuracy.

Prior work reports discrepancies between reasoning traces and final answers, alongside verbose redundant outputs known as overthinking.
Established mathematical benchmarks do not provide controlled manipulation of complexity, motivating environments that preserve logical processes while varying task difficulty.
The paper extends prior comparisons by pairing DeepSeek-R1/V3 and Claude 3.7 Sonnet thinking/non-thinking models and examining reasoning traces across complexity.

3 Math and Puzzle Environments

The paper replaces potentially contaminated math benchmarks with four controllable puzzles whose complexity can be varied while preserving explicit logical rules. It evaluates matched thinking and non-thinking models across task structures and complexity levels.

Math-benchmark comparisons motivate controlled puzzles because benchmark complexity cannot be manipulated precisely and contamination may affect frontier-model results.
The testbed evaluates reasoning across four puzzles spanning compositional depth, planning complexity, and distributional settings.
Tower of Hanoi: Tower of Hanoi scales difficulty with disk count, with n disks requiring a minimum of 2^n − 1 moves, while evaluation checks move correctness and reaching the target state.
Checkers Jumping: Checkers Jumping swaps red and blue checkers using slides or opposite-color jumps, with complexity controlled by the number of checkers.
River Crossing: River Crossing transports n actor-agent pairs under boat-capacity and protection constraints, with complexity controlled by the number of pairs.
Blocks World: Blocks World rearranges blocks into a goal configuration using only topmost-block moves, with complexity controlled by the number of blocks.

4 Experiments & Results

Across controllable puzzle environments, reasoning models show three complexity-dependent regimes and eventually collapse, while trace analyses reveal overthinking, delayed correctness, and failures to execute explicit algorithms.

Three Regimes of Complexity: At low complexity, non-thinking models match or outperform thinking models with more token-efficient inference.
Three Regimes of Complexity: At medium complexity, long chain-of-thought gives reasoning models an increasing performance advantage over matched standard models.
Three Regimes of Complexity: At high complexity, both reasoning and non-thinking models collapse to zero, although thinking models delay the collapse.
Collapse of Reasoning Models: Accuracy declines as complexity rises, while thinking-token usage initially increases and then decreases after a model-specific collapse threshold.
Reasoning Traces: For simple Tower of Hanoi problems (N=1-4), models often find correct solutions early but continue exploring incorrect alternatives.
Reasoning Traces: For moderate Tower of Hanoi problems (N=5-7), accuracy improves slightly with continued reasoning, whereas complex problems (N≥8) remain near zero.
Algorithm Execution: Providing explicit algorithms does not improve performance: Tower of Hanoi and Checker Jumping still collapse at roughly the same points.
Cross-Puzzle Behavior: Failure thresholds vary across puzzles: Claude 3.7 Sonnet solves Tower of Hanoi at N=5 nearly perfectly but fails River Crossing at N=3.

5 Conclusion

The paper finds that reasoning models have complexity-dependent strengths but fail to develop generalizable reasoning beyond certain thresholds, with reasoning effort eventually declining. Its conclusions are bounded by narrow puzzle coverage, black-box access, and assumptions about stepwise validation.

Reasoning models outperform standard LLMs only at moderate complexity; standard models lead at low complexity, and both collapse at high complexity.
Reasoning effort decreases as problems approach critical complexity, indicating an inference-time compute scaling limit.
Reasoning traces range from overthinking on simple problems to complete failure on complex ones.
The puzzle environments cover a narrow slice of reasoning tasks and may not represent real-world or knowledge-intensive reasoning.
Black-box API access limits mechanistic analysis of the closed frontier models’ internal states and architectural components.
Deterministic simulators assume perfect step-by-step validation, which may not transfer to less structured, open-ended reasoning.

A Appendix

The appendix supplies responses to criticisms, detailed environment and implementation specifications, computational-complexity analyses, and additional experiments across models and puzzle settings.

The appendix includes responses to alternative critics, experimental setup specifications, additional results, and extended analyses.
Puzzle-environment details cover four environments, including problem descriptions, prompt designs, and simulators.
Implementation details include experimental configurations, extraction pipelines, and prescribed-algorithm execution experiments.
Computational-complexity analyses address compositional depth and performance and inference as compositional depth changes.
Additional results analyze Qwen model pairs, sampling effects, reasoning-effort patterns, and failure behavior across models and environments.

A.1 Response to Main Criticisms

The authors respond to criticisms by clarifying concerns and incorporating modifications where they judge them valid, while addressing misunderstandings.

The section addresses criticisms and reports modifications intended to clarify valid concerns and misunderstandings.

Question: Are failures on Tower of Hanoi due to context limit issues rather than reasoning limitations?

The experiments reject context limits and sampling as primary explanations for puzzle failures, while revealing earlier reasoning breakdowns and a scope refinement for River Crossing.

Context limits: Tower of Hanoi failures begin within context limits: collapse starts at N=7–8, while first failures occur around 40–100 moves.For N≈10, failure typically occurs within the first ∼100 moves; for N=8, around ∼40 moves.
Sampling effects: Temperature-zero ablations leave collapse unchanged across puzzles, showing that long-sequence sampling is not the primary cause.Sampling can even delay collapse: Blocks World shifts from N=4 at temperature zero to N=30 with sampling.
Scope refinement: River Crossing cases with N≥6 change structure because optimal boat capacity becomes k=4, so the analysis focuses on N<6.This refinement does not alter the core finding because performance mostly collapses earlier, from N=3 requiring an 11-move solution.
Algorithm execution: Providing explicit algorithm steps produces no meaningful improvement on Tower of Hanoi or Checker Jumping, indicating a broader execution limitation.Both puzzles show similar collapse points despite requiring execution rather than solution discovery.

A.2.1 Tower of Hanoi

Tower of Hanoi evaluates sequential reasoning and planning through a recursively structured, exponentially scaling disk-transfer puzzle, with simulator-validated move correctness as the success criterion.

Puzzle definition: Tower of Hanoi transfers N disks among three pegs while preserving size ordering and obeying one-disk and top-disk movement constraints.The initial stack is on peg 0 and the goal is the same ordered stack on peg 2.
Complexity: The minimum solution length is 2^N − 1 moves, providing fine-grained difficulty control through the number of disks.The evaluation assesses correctness rather than optimality.
Reasoning demands: The puzzle tests recursive decomposition, simultaneous state tracking, constraint satisfaction, and sequential planning.These demands arise from tracking disk positions while planning valid operations toward the target state.
Prompt design: Prompts specify the puzzle rules, objective, examples, complete move-list format, and zero-indexed peg representation.Solutions use moves = [[disk id, from peg, to peg], ...].
Evaluation: A stateful simulator tracks configurations across three pegs and validates every proposed move against the puzzle constraints.The framework separates state management and move validation in a modular architecture.

A.2.2 Checker Jumping

Checker Jumping is a one-dimensional constraint-satisfaction puzzle that tests planning and rule adherence by requiring red and blue checkers to exchange sides through legal forward moves.

Puzzle definition: The puzzle starts with N red checkers, an empty middle position, and N blue checkers, aiming to swap the colors’ sides.The board contains 2N + 1 positions.
Movement rules: Legal moves are forward slides into an adjacent empty space or jumps over exactly one opposite-color checker.Checkers cannot move backward toward their starting side.
Reasoning demands: Checker Jumping tests spatial reasoning, constraint satisfaction, lookahead planning, and state-space exploration.Models must track checker positions and anticipate how current moves affect future options.
Prompt design: Prompts specify the initial and goal boards, movement rules, examples, and the move format [checker_color, position_from, position_to].Positions are 0-indexed and the final response must contain the complete move list.
Evaluation: The custom simulator tracks all checkers and the empty space while validating each move and the evolving state against the rules.It provides solution validation and failure analysis within the evaluation framework.

A.2.3 River Crossing

River Crossing evaluates multiagent coordination and constraint management as actors and their agents cross a river under boat-capacity and safety restrictions.

Puzzle definition: The puzzle contains N actors and N corresponding agents who must all travel from the left bank to the right bank.The boat has capacity k, typically 2 for N≤3 and 3 for larger puzzles.
Constraints: Every crossing must use a non-empty boat and preserve the safety rule that an actor cannot be with another agent without their own agent present.The safety constraint applies on both banks and in the boat.
Reasoning demands: The puzzle tests multiagent coordination, constraint satisfaction, and planning under capacity and safety constraints.The evaluation requires maintaining legality throughout the full crossing sequence.
Prompt design: Prompts define actor-agent notation, boat-move formatting, examples, and the requirement to provide the complete move list without comments.Moves list the people riding in each boat trip.
Evaluation: A custom simulator tracks all individuals and boat position while checking capacity, passenger location, and safety for each move.Each move undergoes multi-step validation.

A.2.4 Blocks World

Blocks World tests whether models can transform an initial stack configuration into an exact goal configuration under top-block movement constraints. The setup specifies standardized prompts, move formats, indexing, and simulator validation for controlled planning evaluation.

Puzzle definition: Blocks World rearranges uniquely identified blocks across stacks from an initial configuration to an exact goal configuration.Only the topmost block may move, and placement is allowed on an empty position or another block.
Puzzle definition: The puzzle’s difficulty can be varied by changing the number and arrangement of blocks while preserving its movement rules.Models must plan ordered state transformations because temporary placements may be needed to access buried blocks.
Prompt design: The system prompt states the movement constraints, defines the move representation, and provides an example solution structure.The example uses moves formatted as block, source stack, and destination stack.
Output format: Solutions must list complete moves using zero-indexed stack positions in the format moves = [[block, from stack, to stack], ...].The same complete move list is required during reasoning and in the final answer.
Validation: A custom simulator validates stack bounds, nonempty sources, and whether each specified block is the source stack’s top block.These checks enforce the puzzle’s operational constraints when extracted solutions are executed.

A.3 Implementation Details

The implementation evaluates reasoning and non-reasoning models on controlled puzzles, extracts and validates solutions and reasoning traces, and relates accuracy, compute, and failures to compositional depth. Results show collapse beyond puzzle-specific thresholds, non-monotonic effort allocation, and inconsistent failure behavior.

Configurations: Experiments compare Claude 3.7 Sonnet, DeepSeek-R1/V3, and selected o3-mini variants using up to 64,000 generated tokens and 25 samples per model and complexity level.Reasoning-trace analysis focuses on models exposing intermediate thinking tokens.
Algorithmic support: Providing explicit algorithms yields modest accuracy gains at some complexity levels but does not remove the collapse.The result points toward limitations in compositional representation, planning, and consistent logical verification rather than instruction following alone.
Compositional depth: Compositional depth measures the number of sequential moves required to solve a puzzle, with growth ranging from exponential to near-linear across environments.Tower of Hanoi scales as 2^N −1, Checker Jumping quadratically, while River Crossing and Blocks World are near-linear.
Accuracy patterns: Accuracy declines with increasing depth within each puzzle, but depth alone does not predict performance across different puzzle types.Models can struggle on lower-depth puzzles while succeeding on higher-depth ones.
Collapse thresholds: Collapse points occur around N = 7 for Tower of Hanoi, N = 2 for Checker Jumping, N = 10 for Blocks World, and N = 3 for River Crossing.Beyond these thresholds, accuracy becomes near-zero in the reported experiments.
Failure analysis: Models show non-monotonic failure positions across complexity, sometimes failing earlier on larger instances despite longer required solutions.Tower of Hanoi examples include failures below 50 moves at N = 12 but success beyond 100 moves at N = 10.
Failure analysis: Thinking models generally fail later in solution sequences than non-thinking models, as shown by higher mean first-failure positions across puzzles.The comparison uses density distributions aggregated across problem complexities within each puzzle environment.
Inference compute: Reasoning effort initially increases with complexity, then declines after model-specific thresholds despite remaining below generation limits.This counterintuitive reduction appears across multiple reasoning models, including QwQ-32B and o3-mini variants.