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

In plain words

Newer chat models can "think" before they answer: they write out a long chain of reasoning first. This paper asks how well that works as puzzles get harder. It uses simple, rule-based puzzles such as Tower of Hanoi, where the difficulty can be turned up one notch at a time and every move can be checked by a program.

The authors compare thinking models with their non-thinking versions, given roughly the same token budget. They find three phases. On easy puzzles the plain models do as well or better and need fewer tokens. On medium puzzles the thinking models pull ahead. On hard puzzles both kinds fail almost completely. Strangely, the thinking models also write less reasoning as the puzzles get hardest, even though they are nowhere near their length limit.

The paper also looks inside the reasoning text. Models often find a correct answer early, keep exploring wrong ones, and then fixate on an early mistake. Even when the solution algorithm is given in the prompt, the failure point barely moves. The authors read this as a limit in carrying out step-by-step logic, not only in finding a plan.

TL;DR

• Four rule-based puzzles with a dial for difficulty and a simulator that checks each move §3.1 app. A.2.
• Thinking models beat their non-thinking twins only at medium difficulty; both collapse at high difficulty §4.2 fig. 5.
• Thinking-token use rises with difficulty, then falls before the collapse point §4.2 fig. 6.
• Giving the solution algorithm in the prompt does not move the failure point much §4.4 fig. 8.

Problem

The authors argue that math and coding benchmarks measure final-answer accuracy, can be contaminated by training data, and say little about the reasoning trace §1. They want controlled tasks where difficulty can be scaled precisely while the rules stay the same, and where every intermediate step can be verified §1 §3.

They also doubt that the gains of reasoning models on math benchmarks are clearly due to reasoning rather than more tokens or data exposure §3. Their working assumption is that a model's correctness under a fixed token budget can be compared against its non-thinking twin on the same puzzle §4.1.

Method

The study has three parts. The first compares matched pairs of thinking and non-thinking models across puzzle sizes §4.2. The second studies the intermediate solutions found inside thinking traces §4.3. The third probes exact execution, using prompts that include the solution algorithm §4.4 app. A.3.

Puzzles (difficulty knob N; all four are defined in §3.1 and app. A.2):

• Tower of Hanoi. Three pegs and N disks. The minimum solution has 2^N - 1 moves. Only move validity and reaching the goal are graded, not optimality §3.1 app. A.2.1.
• Checker Jumping. A 1-D board with N red and N blue checkers and one empty cell. Checkers slide or jump, and cannot move backwards. The minimum solution has (N+1)^2 - 1 moves §3.1 app. A.2.2.
• River Crossing. N actor-agent pairs and a boat. Boat capacity is k = 2 for N ≤ 3 and k = 3 above that §3.1 app. A.2.3. An actor may not share a bank or the boat with another agent unless its own agent is present app. A.2.3. See Pitfalls for a conflict on k.
• Blocks World. Two initial stacks of N blocks, and a goal that interleaves them on one stack. Only top blocks may move app. A.2.4.

Models and sampling. Thinking/non-thinking pairs: Claude 3.7 Sonnet with and without extended thinking, and DeepSeek-R1 vs V3 §4.1 app. A.3. Also o3-mini (medium and high), R1-Distill-Qwen-32B, and QwQ-32B vs Qwen2.5-32B §4.2 app. A.6. Thinking traces are used only because these models expose them §4.1.

Protocol (for each model, puzzle and N):

# Evaluation loop  [§4.1] [app. A.3]
# Input:  puzzle, N, model, prompt template
# Output: pass/fail, first failure move, thinking-token count

def evaluate_instance(puzzle, size, model):
    # Build the system and user prompts for this instance  [app. A.2]
    prompt = render_prompt(puzzle, size)
    # Sample with the token cap in [app. A.3]
    response, thoughts = model.generate(prompt, max_tokens=64000)
    # Keep only answers in the requested format  [§4.1]
    if not has_moves_list(response):
        return discard
    # Replay each move through the simulator  [app. A.1] [app. A.2]
    moves = parse_moves(response)
    result = simulator.check(puzzle, size, moves)
    return result

Solution extraction app. A.3. Regular expressions pull candidate move lists from both the final answer and the thinking trace. Comments are stripped and duplicate move lists are dropped (the first occurrence is kept). Token positions are counted with the cl100k_base tokenizer and normalised by trace length.

Simulator app. A.2. Each puzzle has a stateful simulator that validates every move against the rules and then checks the goal state. For failures it records the first bad move and the failure type app. A.3.

Algorithm-provision experiment §4.4 app. A.3. The recursive Hanoi procedure, or a backtracking Checker Jumping procedure, is appended to the normal prompt as a scratchpad. The model must still produce the move list.

# Recursive Tower of Hanoi  [app. A.3]
# Input:  n disks, source, target, auxiliary peg
# Output: appends (disk, from, to) tuples to moves

def solve(n, source, target, auxiliary, moves):
    # Base case: move the single top disk  [app. A.3]
    if n == 1:
        moves.append((top_disk(source), source, target))
        return
    # Move the n-1 disks above out of the way  [app. A.3]
    solve(n - 1, source, auxiliary, target, moves)
    # Move the largest remaining disk  [app. A.3]
    moves.append((top_disk(source), source, target))
    # Move the n-1 disks back on top  [app. A.3]
    solve(n - 1, auxiliary, target, source, moves)

Trace analysis §4.3 fig. 7. Every unique intermediate solution is recorded with its relative position in the trace, whether it is correct, and its puzzle size. Position is normalised by trace length.

Hyperparameters

Results

Author-reported. No numeric results table appears in the paper. Accuracy curves are shown only as figures, so values below come from the text. Setup: four puzzles, thinking vs non-thinking pairs, 25 samples per point §4.1.

Paper vs code

No official code. The paper names no repository. A GitHub search for the title and for the Apple organisation found no repository owned by the authors or by Apple. Several third-party reimplementations exist, but the skill forbids using them, so none is cited or used here.

Pitfalls

• Boat capacity conflicts. §3.1 and app. A.2.3 give k = 2 for N ≤ 3 and k = 3 above. The rebuttal app. A.1 says k = 4 for N ≥ 6, and that the analysis was restricted to N < 6. Pick one and state it explicitly in any reimplementation.
• Inconsistent failure positions for Hanoi N = 8. app. A.1 says the first failure is around move 40. app. A.6 says around move 50. §4.4 says above 100 moves for N = 10. Treat the exact move numbers as approximate.
• "Minimum moves" vs grading. §3.1 says Blocks World asks for the minimum number of moves. The simulator grades only validity and the goal state, so optimal solutions are not required app. A.2.1 app. A.3. Neither the paper nor the text says whether any optimality check was made for Blocks World.
• Temperature and sampling. Main experiments use temperature 1.0 app. A.3. Collapse depends on sampling in the ablation. Reported gains in Blocks World at T = 1 are large (N = 4 to N = 30), so compare only at the same temperature.
• Context-limit critique. The authors argue failures are not caused by context limits app. A.1. They also removed Hanoi N > 12 app. A.1. The reported move counts are the ones they chose to keep.
• Trace positions depend on a tokenizer. Positions use cl100k_base for every model, including non-OpenAI models app. A.3. Trace position is therefore a proxy, not the model's own token count.
• Solution filtering. Only responses in the requested format are analysed §4.1 app. A.3. The filter can exclude failures that matter, and the paper does not report how many samples were dropped.
• Black-box APIs. Most runs use closed APIs, so internal states cannot be inspected [Limitations]. Model versions and checkpoints can change over time, which affects repeatability.
• Algorithm-provision claim. The statement that providing the algorithm does not help is shown for Hanoi and Checker Jumping only §4.4 fig. 8. River Crossing and Blocks World were not tested that way.
• Not all figures are numeric. Most findings rest on figures fig. 4 fig. 5 fig. 6 fig. 14 that carry no numbers in the text. Read them directly before quoting values.
• Conclusions beyond the puzzles. The authors note that puzzle difficulty does not correspond neatly to computational complexity, so comparisons should stay within one puzzle §4.2 app. A.4.2.

Lineage

• Builds on: Chain of Thought prompting (see the concept chain-of-thought-prompting) and its extensions to reinforcement-learned reasoning models, including DeepSeek-R1 §2.
• Compared against: Claude 3.7 Sonnet with and without thinking, DeepSeek-R1 vs V3, o3-mini, QwQ-32B vs Qwen2.5-32B §4.1 app. A.6.
• Related controlled-environment work: planning benchmarks on Blocks World §2 app. A.2.4.
• Superseded by: not stated.