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

This paper evaluates reasoning models on puzzles whose size can be varied while their rules remain stable. Instead of scoring only a final answer, the authors extract candidate plans and execute them in simulators. That reveals illegal transitions, incomplete plans and the point at which an apparently plausible solution stops working.

The tested models show different behavior at different difficulty levels. Extra thinking can help in an intermediate range, while harder instances eventually produce severe accuracy declines. Longer reasoning traces do not reliably prevent those failures, and the authors observe reduced thinking-token use beyond some difficulty thresholds.

The result is evidence about particular models, prompts and puzzle tasks. It is not a proof that all language models lack reasoning, that tool-using agents cannot solve these problems, or that future models must fail at the same threshold. Those are broader claims than this experiment can establish.

This page uses the November 2025 camera-ready revision. Its appendix responds to critiques of the original June paper and narrows some experimental ranges. Reading that revision matters because repeating the initial controversy without the later controls gives an incomplete account of the evidence.

An enterprise agent can explain a sensible procedure and still violate a constraint halfway through execution. A migration plan might name the right steps but perform them in the wrong order. A reconciliation workflow might preserve totals initially and then lose track of one exception.

The paper suggests a useful evaluation habit: inspect state transitions and first failures, not only the final narrative. It also shows why spending more inference tokens is an intervention to test rather than a general reliability guarantee.

Connect agent trajectory evaluation with benchmark limitations. A production test should separate planning, tool execution, output formatting and recovery. The customer needs a correct completed workflow; understanding which component fails is what lets an FDE improve that outcome.