Breaking the Illusion of Thinking: LLM Performance Collapse and Deterministic Loops in the Towers of Hanoi Problem

Forum topic · ✨步子哥 · 2025-11-12

Summary

This post analyzes the 'illusion of thinking' phenomenon in large language models, based on Apple's widely discussed paper 'The Illusion of Thinking'. Using the Towers of Hanoi puzzle as a controlled testbed, it shows that models perform well at low complexity (3-4 disks) but suffer an abrupt collapse to near-zero success rates at 5-6 disks, where the minimum solution length is 2^n - 1 moves. Performance follows three phases: standard LLMs excel at low complexity, large reasoning models show advantages at medium complexity via chain-of-thought, and all models fail at high complexity. The core failure mode is a 'deterministic loop': instead of backtracking or trying new strategies, the model repeats an invalid but locally legal sequence of moves that is reproducible across runs. The analysis attributes this to advanced pattern matching rather than genuine logical deduction: Transformer multi-step reasoning reduces to linearized subgraph matching via attention, and solution paths for higher disk counts are sparse or absent in training data. Notably, models fail even when given an explicit correct recursive algorithm, indicating an architectural limit in maintaining recursion depth and state tracking. The post also describes an agentic framework that externalizes state management to a deterministic environment module to isolate pure reasoning ability.

Breaking the "Illusion of Thinking": LLM Performance Collapse and Deterministic Loop Analysis in Towers of Hanoi

*English adaptation of a zhichai.net forum post. Based on Apple's paper "The Illusion of Thinking" (arXiv:2507.01231).*

Key points

Large reasoning models (LRMs) do not degrade gracefully on logic puzzles; instead, past a complexity threshold, success rates collapse abruptly from ~90% to nearly 0%.
Towers of Hanoi serves as the testbed: deterministic rules, a well-defined state space, and a quantifiable complexity metric — the minimum number of moves is 2^n - 1 for n disks.
Three-phase performance model:

Low complexity (3–4 disks):

Medium complexity:

High complexity (5–6 disks):

Counterintuitive behavior

Near the capability limit, models consume the most tokens; beyond it, they dramatically shorten their output — suggesting a crude internal difficulty-assessment and an "early abandonment" strategy.
Even when given an explicit, correct recursive algorithm, models still fail at high complexity. The failure is not about finding the algorithm, but about sustaining recursion depth and state tracking — an architectural limitation.

Root cause: deterministic loops

When stuck, the model does not backtrack or try new strategies. It falls into a deterministic loop: a reproducible, invalid sequence of moves, each locally legal but globally forming an inescapable cycle ("knowingly repeating the mistake").
Loop characteristics: repeatable action sequences, locally valid but globally ineffective, no self-correction.

Why it fails: pattern matching, not logical deduction

Transformer multi-step reasoning operates by matching operations: attention layers match relevant fragments of a linearized reasoning sequence. This linearized subgraph matching fundamentally limits tasks requiring deep recursion and state-stack management.
Success depends on finding a similar "computation graph" in training data. Solutions for 3–4 disks are abundant; full paths for 5–6 disks (2^n − 1 steps) are extremely sparse or absent.
True reasoning would dynamically develop new strategies from basic rules; instead, models show total failure rather than adaptation — they cannot derive recursive solutions from scratch or learn new heuristics through trial and error.

Agentic framework

The proposed framework's design philosophy is "offloading": all memory and state-tracking tasks are stripped from the LLM and handled by an external, deterministic environment module.
The environment maintains the current Hanoi state; the LLM stores no history of past moves — isolating pure reasoning ability from memory burden.

Implications

The study challenges the notion that chain-of-thought constitutes genuine reasoning. The abrupt, threshold-like failure mode and deterministic loops suggest current LLMs execute sophisticated pattern matching over training distributions rather than performing symbolic, compositional logical deduction.