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
NeurIPS 2025
cs.AI, cs.CL, cs.LG
2025-06-08
Apple tests frontier LRMs on controllable puzzles: past a complexity threshold accuracy collapses, thinking tokens shrink despite spare budget, and given algorithms don't help.
This NeurIPS 2025 paper from Apple attacks two blind spots in how reasoning models are evaluated. Standard math and coding benchmarks score final answers only, so test items may already sit in training data, and nothing in the score says whether the model reasoned or pattern-matched. An open comparison also hangs over the field: with inference compute held equal, how much do thinking models actually beat their non-thinking siblings? The team first rechecked this on math: given the same token budget, Claude 3.7 Sonnet thinking and non-thinking reach essentially the same pass@k (the chance of at least one correct answer within k samples, an upper-bound measure) on MATH-500. The gap widens a little on AIME24 and more on AIME25. Humans scored higher on AIME25 than on AIME24, so harder problems cannot explain it, and contamination stays on the table. Math benchmarks offer no dial for complexity, so the work moves to puzzle environments where difficulty can be tuned precisely.
Four puzzles, each with a simulator that validates every move: Tower of Hanoi (minimum 2^N-1 moves, exponential), Checker Jumping ((N+1)^2-1 moves, quadratic), River Crossing (constraint-satisfaction planning), and Blocks World (stack rearrangement). The simulators pull double duty: they grade final answers, and they also verify the intermediate solutions a model writes inside its thinking trace, recording where each appears and whether it is correct. Comparisons use matched pairs sharing a backbone, Claude 3.7 Sonnet with and without thinking plus DeepSeek-R1 versus V3, with o3-mini and R1-Distill-Qwen-32B joining accuracy-only runs. Each complexity level gets 25 samples under a 64k generation budget, far more than needed, so collapse is not a length artifact. One extra condition drops the full solving pseudocode into the prompt, reducing the task to step-by-step execution.
Accuracy splits into three regimes: at low complexity non-thinking models match or beat their thinking counterparts while using fewer tokens; in the middle band thinking models pull ahead; past a threshold, both collapse to zero.
| Setting | Result |
| Hanoi N=5 (31 moves) | Claude 3.7 Thinking near-perfect |
| Hanoi N=7-8 (100-200 moves) | reasoning models start collapsing |
| Hanoi N=12 | Claude 3.7 Thinking first error within 100 moves |
| River Crossing N=3 (11-move solution) | collapse; valid sequence ends around move 4 |
| Full algorithm given in prompt | collapse points barely move on both puzzles |
| Blocks World, temperature 0 | R1 collapses at N=4; sampling delays it to N=30 |
Two behaviors stand out. Near the collapse point, thinking tokens shrink as complexity rises even with budget to spare, most visibly in o3-mini and least in Claude 3.7 Thinking. Trace analysis also splits three ways: on easy problems the correct solution shows up early and the model keeps exploring wrong branches (overthinking); at moderate complexity it wades through wrong solutions before landing the right one; past the threshold it locks onto an early wrong answer and burns the remaining tokens there. The temperature-0 ablation rules out sampling luck, and the algorithm condition shows the failure sits in execution itself, not in solution search.
The advantage of thinking models has a measured band, not a blank check. Inside the band there are real gains; outside it, long chains of exact moves and multi-constraint planning fail for both model types. Watching a model fail while following pseudocode it was handed is a direct warning for agent builders, since reliable tool calls rest on the same stepwise execution these puzzles probe. The evaluation recipe, a controllable-complexity environment plus a simulator that grades intermediate traces, transfers well to internal evals and exposes failure modes a final-answer score hides. The AIME25 comparison is also a handy contamination check for benchmark maintainers.
The authors list three: puzzles cover a narrow slice of reasoning and say little about knowledge-intensive or open-ended tasks; most experiments run through black-box APIs, so no mechanistic analysis of internals is possible; and deterministic step-by-step validation does not transfer to domains without a clean simulator. Two more caveats survive a careful read. Collapse thresholds are entangled with training-data familiarity, and the authors concede that River Crossing instances at larger N may simply be rare in training, so thresholds track distribution more than intrinsic difficulty. River Crossing also changes structure at N≥6, when optimal boat capacity shifts, which is why the analysis keeps N<6. Default-temperature API runs and response-format filtering could bias the sample set further.