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

TL;DR

Apple researchers evaluate frontier Large Reasoning Models (LRMs — Claude 3.7 Sonnet Thinking, DeepSeek-R1, o1/o3) on four controllable puzzle environments (Tower of Hanoi, Checker Jumping, River Crossing, Blocks World) where compositional complexity can be tuned by a single integer parameter. They find three regimes: at low complexity, non-thinking LLMs match or beat LRMs at lower token cost; at medium complexity, LRMs win; at high complexity, both collapse to near-zero accuracy. The headline counter-intuitive finding: as problems approach the collapse boundary, LRMs’ reasoning effort decreases — fewer tokens spent on thinking — despite having ample budget. They also show that handing the model the explicit algorithm as a prompt does not prevent collapse. The paper is a critique of how the field measures progress on reasoning, and reframes “thinking” as pattern-matching that breaks predictably with compositional depth.

Key claims

Three complexity regimes separate LRMs from their non-thinking base models: at low complexity, base LLMs match or beat LRMs in both accuracy and token efficiency; at medium complexity, LRMs win; at high complexity, both collapse to ~0% accuracy [Fig. 1 bottom, §4].
Frontier LRMs exhibit a complete accuracy collapse beyond a critical problem complexity, not graceful degradation [Abstract, §4].
LRMs show a counter-intuitive reasoning-effort scaling limit: thinking tokens spent rise with complexity up to a point, then decline despite the model having token budget remaining and accuracy still dropping [Abstract, §4].
LRMs fail to use explicit algorithms: even when given the exact step-by-step solution procedure (e.g. the recursive Tower-of-Hanoi algorithm) as part of the prompt, performance does not improve and collapse still occurs at roughly the same complexity threshold [§4 / experiments on algorithm-in-prompt].
LRMs reason inconsistently across puzzle types: collapse thresholds differ markedly across Tower of Hanoi vs. River Crossing vs. Blocks World, suggesting models are matching to surface puzzle templates rather than executing a shared planning capability [§4].
On easy problems, LRMs exhibit overthinking: traces frequently find the correct answer early but continue exploring and sometimes converge on incorrect alternatives [§4.x reasoning-trace analysis].
Standard reasoning-benchmark evaluations (math / coding final-answer accuracy) are insufficient because of data contamination and because they do not probe the structure of the reasoning trace itself [Abstract, §1].
Controllable puzzle environments allow precise manipulation of compositional complexity while keeping logical structure fixed, enabling apples-to-apples comparison of LRM vs. base-LLM at matched inference compute [§3].

Method

The authors design four puzzle environments — Tower of Hanoi, Checker Jumping, River Crossing, Blocks World — each parameterized by a single integer that controls compositional complexity (number of disks, number of checkers, number of agents to cross, number of blocks). For each puzzle they generate problem instances across the complexity range and evaluate two model classes head-to-head: an LRM (Claude 3.7 Sonnet Thinking, DeepSeek-R1, OpenAI o-series) and its non-thinking counterpart at matched inference budget. Critically, they verify not just the final answer but also the intermediate reasoning trace by parsing it into puzzle moves and checking validity at each step. This lets them measure (a) accuracy as a function of complexity, (b) tokens spent on the “thinking” segment as a function of complexity, and (c) where in the trace the model first encounters the correct solution vs. where it commits. A separate experiment hands the model the explicit solution algorithm in the prompt and re-measures accuracy at increasing complexity.

Results

Three-regime performance pattern is replicated across all four puzzles and across LRM families [Fig. 1 bottom-left, bottom-middle].
Token spend on reasoning rises with complexity, peaks below the collapse threshold, then declines monotonically as the problem becomes harder — even though the model is still allowed to spend tokens [Fig. 1 bottom-right, Abstract].
Providing the exact recursive Tower-of-Hanoi algorithm in the prompt does not raise the collapse threshold [described in §4 algorithm-in-prompt experiment].
Collapse complexity varies by puzzle type for the same model — e.g. models that handle larger Tower-of-Hanoi instances may collapse much earlier on River Crossing — indicating that the “reasoning capability” is not a single transferable property [§4 cross-puzzle comparison].
Reasoning-trace analysis: on easy puzzles LRMs often hit the answer in the first portion of the trace but keep exploring and may finalize on an incorrect alternative; on hard puzzles correct intermediate states either never appear or appear and are not committed to [§4 trace patterns].

Why it’s interesting

The paper is the most-cited recent critique of how the Luma-adjacent field measures progress on “reasoning” — and it lands directly on the Reasoning RL recipe stack (GRPO + structured rewards on top of LRMs) and on the Inference-Time Scaling thesis. The declining-thinking-effort-as-complexity-rises finding is the load-bearing one: it contradicts the cleanest version of the “spend more tokens, get more reasoning” story that motivates sequence-budget scaling (Inference-Time Hyper-Scaling with KV Cache Compression) and learned parallel orchestration (Kimi K2.5: Visual Agentic Intelligence). The paper triggered an unusually large rebuttal literature (Comment on Illusion of Thinking (2506.09250) from Lawsen et al. arguing token limits, not reasoning limits, drive collapse; “Rethinking the Illusion of Thinking” arxiv:2507.01231 replicating with refinements) — meaning the headline conclusion is genuinely contested and the team should treat it as a “live debate” datapoint, not a settled finding. For Luma specifically: the experimental protocol (controllable-complexity puzzles + reasoning-trace verification) is a transferable evaluation idea for any internal reasoning-style model, including multimodal ones.