Loading...
Strengths and Limitations of Reasoning Models via Problem Complexity
Parshin Shojaee, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, Mehrdad Farajtabar
Read the Paper on arXivThe Illusion of Thinking (Shojaee, Mirzadeh, Alizadeh, Horton, Bengio & Farajtabar — NeurIPS 2025, Apple) asks a deceptively simple question: do Large Reasoning Models actually reason, or do they perform a sophisticated kind of pattern-matching that happens to be wrapped in explanatory prose?
Standard math and coding benchmarks like MATH, AIME, HumanEval and MMLU are contaminated by pre-training data and only score the final answer — they can't tell you whether the model's long chain-of-thought was genuinely deriving the answer or hallucinating a plausible path to a memorized target. The authors replace these benchmarks with controllable puzzle environments — Tower of Hanoi, Checker Jumping, River Crossing and Blocks World — where the problem complexity is a tunable parameter , every instance is algorithmically generated (no contamination), and correctness can be mechanically verified step by step.
The three findings that reframe LRM evaluation:
Three performance regimes. At low complexity, standard (non-thinking) models actually beat Large Reasoning Models — extra chain-of-thought is wasted effort. At medium complexity, LRMs pull ahead. At high complexity, both collapse to near-zero accuracy — the thinking prefix buys nothing past a critical threshold .
The reasoning-token collapse. As increases toward , LRMs spend more thinking tokens — exactly as you'd expect. But past , the number of thinking tokens shrinks even though the generation budget is untouched. The model has the compute to keep reasoning; it just stops.
Algorithmic execution failure. Even when the correct step-by-step algorithm is given in the prompt, LRMs still fail at roughly the same . The bottleneck isn't 'doesn't know how to solve it' — the model cannot reliably execute a known procedure once the required step count crosses a threshold.
Why this matters. The paper doesn't claim LRMs are useless — it claims current benchmarks systematically hide their limits. If an LRM that nails MATH still collapses on an 8-disk Tower of Hanoi (a problem a competent undergraduate can simulate on paper), our evaluation pipeline is telling us the wrong thing about what these models can do. The controllable-puzzle methodology is portable: any future reasoning model can be plotted on the same complexity axis and compared directly, without new benchmarks to curate or contaminate.
Click any topic to jump in
Large Reasoning Models emit a thinking prefix before the answer — but current benchmarks only score the answer.
MATH, AIME and friends are scraped from the same internet LRMs train on — memorization masquerades as reasoning.
Four puzzle families (Hanoi, Checker Jumping, River Crossing, Blocks World) with a single integer complexity knob N.
Low-N: non-thinking wins. Medium-N: LRM wins. High-N: both collapse past a critical threshold N_c.
Thinking-token count rises with complexity — then falls past N_c despite the full generation budget being unused.
Giving the model the algorithm in the prompt does not shift N_c — the failure is execution, not knowledge.
Overthink on easy problems (correct answer abandoned) and underthink on hard ones (early commit, no search).
The paper's argument in one picture — from a thinking-model's inference path, through the four puzzle environments and their complexity dial, to the three-regime accuracy curve and the token-collapse finding that defines the paper's headline claim.
Large Reasoning Models (LRMs) emit a long thinking prefix before the final answer — o1-style, Claude extended thinking, DeepSeek-R1 style
Standard benchmarks score only the final answer — contamination + hidden failure modes
Controllable puzzles (Tower of Hanoi, Checker Jumping, River Crossing, Blocks World) give a complexity dial and mechanically-verified step-by-step correctness
Low complexity: non-thinking models match or beat LRMs — thinking is wasted
Medium complexity: LRMs genuinely help — the regime where chain-of-thought pays off
High complexity: both collapse — accuracy → 0 past a critical threshold
Reasoning-token collapse: thinking tokens grow then shrink past despite unused budget
Giving the model the algorithm does not move — the failure is in execution, not knowledge
Plot accuracy as a function of complexity: is high and flat for , declines steeply near , and is ~0 for . LRMs shift rightward on medium-hard problems but not on the hardest ones — the wall is real, and every current LRM has one.