Research map / Large language models / Reasoning and chain of thought

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

NeurIPS 2025 · Large language models › Reasoning and chain of thought · approach: Efficient and adaptive thinking · 29 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Uses controllable puzzle environments (Tower of Hanoi, Checker Jumping, River Crossing, Blocks World) to show frontier large reasoning models collapse beyond a complexity threshold, reduce reasoning effort near collapse, and fail to benefit from given algorithms.

Problem

Whether large reasoning models (LRMs) with long chain-of-thought truly reason generally, and how their accuracy, thinking effort, and reasoning traces scale with problem compositional complexity, is poorly understood because math and coding benchmarks suffer from contamination and give no trace-leve

Approach

Replace contaminated math benchmarks with simulator-verifiable puzzles whose complexity is controlled by a single size parameter, compare thinking vs. non-thinking model pairs at equal token budgets, and analyze intermediate solutions inside reasoning traces using puzzle simulators.

Key results

• Thinking models (Claude 3.7 Sonnet thinking, DeepSeek-R1) collapse to near-zero accuracy beyond a model-specific complexity threshold on puzzles, and the thinking-token count declines near that point despite budgets up to 64k.
• Three regimes observed: non-thinking models match or beat thinking models at low complexity, thinking models lead at medium complexity, and both collapse at high complexity.
• Providing the explicit Tower of Hanoi and Checker Jumping algorithm in the prompt does not delay the observed collapse point.

Measured effects reported in the paper

Surprising findings

• Reasoning models reduce thinking tokens as complexity approaches the collapse point, despite ample token budget.
• Supplying the solution algorithm does not improve execution performance, suggesting failures in logical step execution rather than search.

Limitations

• Puzzles are a narrow slice of reasoning tasks and may not transfer to real-world or knowledge-intensive reasoning.
• Most experiments use black-box API access to closed models, preventing mechanistic analysis.
• Deterministic simulators do not extend to less structured, open-ended domains.

Experimental setup

Datasets: MATH500 AIME24 AIME25

Benchmarks: Tower of Hanoi Checker Jumping River Crossing Blocks World MATH500 AIME24 AIME25

Metrics: accuracy pass@k thinking token usage first failure move position

Baselines: o3-mini DeepSeek-R1 Claude-3.7-Sonnet (non-thinking) DeepSeek-V3 DeepSeek-R1-Distill-Qwen-32B QwQ-32B Qwen2.5-32B

Builds on: chain-of-thought DeepSeek-R1 overthinking phenomenon

Closest papers by meaning

• Demystifying Reasoning Dynamics with Mutual Information: Thinking Tokens are Information Peaks in LLM Reasoning (NeurIPS 2025 · similarity 0.92)
• An Enigma of Artificial Reason: Investigating the Production-Evaluation Gap in Large Reasoning Models (NeurIPS 2026 · similarity 0.92)
• Measuring the Faithfulness of Thinking Drafts in Large Reasoning Models (NeurIPS 2025 · similarity 0.92)
• Trade-offs in Large Reasoning Models: An Empirical Analysis of Deliberative and Adaptive Reasoning over Foundational Capabilities (AAAI 2026 · similarity 0.91)
• Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems (ICLR 2026 · similarity 0.91)
• Think or Not? Exploring Thinking Efficiency in Large Reasoning Models via an Information-Theoretic Lens (NeurIPS 2025 · similarity 0.91)