The Illusion of Thinking: Why LLMs Collapse on Towers of Hanoi and Fall into Deterministic Loops

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

Summary

This article analyzes the performance collapse of large language models (LLMs) and large reasoning models (LRMs) on the Towers of Hanoi puzzle, echoing Apple's controversial paper "The Illusion of Thinking." Using Hanoi as a controlled testbed — with a known minimum solution length of 2^n − 1 moves — the post shows that models solve low-complexity instances (3–4 disks) with high accuracy, but success rates plunge to nearly zero at 5–6 disks. The failure is not gradual but catastrophic, and follows a three-phase pattern: standard LLMs excel at low complexity, chain-of-thought reasoning models help at medium complexity, and all models fail at high complexity. The core failure mode is the "deterministic loop": when stuck, the model repeats a locally legal but globally ineffective sequence of moves, without backtracking or new strategies, reproducibly across runs. Even when given the correct recursive algorithm explicitly, models still fail, indicating an architectural inability to maintain recursion depth and state tracking. The post attributes this to advanced pattern matching — linearized subgraph matching via attention — rather than genuine logical deduction: solutions for 3–4 disks are abundant in training data, while 5–6 disk trajectories are sparse or absent. It also describes an agentic framework that externalizes state tracking to test pure reasoning, and notes counterintuitive behavior where models shorten outputs as difficulty exceeds their limits.

Introduction

A recent and widely debated study from Apple, "The Illusion of Thinking", revealed a striking phenomenon: large reasoning models (LRMs) do not degrade smoothly on logic puzzles of controllable complexity. Instead, once a specific complexity threshold is reached, their performance collapses abruptly.

Key Findings: Performance Collapse on Towers of Hanoi

The Towers of Hanoi puzzle serves as the core testbed: it has clear rules, a deterministic state space, and a quantifiable complexity metric tied directly to the number of disks.

Minimum moves: 2^n - 1, where n is the number of disks
Critical point: With 3–4 disks, models typically succeed; at 5–6 disks, success rates plunge from near-perfect to almost zero
The decline is not gradual and predictable but sudden and catastrophic

Three-Phase Performance Model

1. Low complexity — standard LLMs perform better, solving tasks directly and efficiently 2. Medium complexity — reasoning models (LRMs) leverage chain-of-thought to gain an advantage 3. High complexity — all models' success rates drop to zero

Counterintuitive Behavior: Reduced Reasoning Effort

When tasks are solvable but near the model's capability limit, models consume the most tokens; as complexity rises further, they dramatically shorten their outputs — suggesting a rough internal difficulty-assessment mechanism and an "early surrender" strategy
Even when given an explicit, correct recursive algorithm, models still fail on high-complexity instances. The failure is not about finding the right algorithm, but an architectural inability to maintain recursion depth and state tracking

Root Cause: Deterministic Loops

A deterministic loop occurs when, upon hitting an obstacle, the LLM does not try new strategies or backtrack. Instead, it falls into a pre-determined, ineffective sequence of moves:

The sequence is reproducible across runs for the same or similar states — hence "deterministic"
Every step is locally legal, but globally the moves form an inescapable closed loop — "knowingly repeating the mistake"
The model cannot self-correct and never converges to a valid solution despite producing no illegal moves

Pattern Matching, Not Logical Deduction

Transformer models perform multi-step reasoning primarily via "matching operations": treating the reasoning process as a sequence and matching relevant fragments through attention at each layer. This reduction of multi-step reasoning to linearized subgraph matching is fundamentally limited for problems requiring deep recursion and state-stack management
Training data dependence: Solutions for 3–4 disks are ubiquitous in training data. Full 5–6 disk trajectories (2^n − 1 steps) become extremely sparse or nonexistent — a pattern-sparsity problem
True logical reasoning would mean dynamically developing new strategies from first rules. LLMs instead exhibit complete failure, not adaptation: they cannot derive recursive solutions from scratch or learn new heuristics through trial and error

Agentic Framework Design

The post describes an agentic framework whose core philosophy is "offloading": all memory- and state-tracking tasks are stripped from the LLM and handed to an external, deterministic environment module.

The environment maintains the current Hanoi state
The LLM stores no history of past moves
This isolates pure reasoning capability from memory burden, enabling cleaner experiments

Internal Mechanisms

Attention's role: Reasoning proceeds by attention-based matching of information fragments across layers
Generation limits: The autoregressive generation process cannot sustain the depth of recursion and global state consistency needed for high-complexity instances

Conclusion

The apparent reasoning ability of LLMs at low complexity is largely an artifact of pattern matching against training data. When pushed beyond memorized complexity regimes, models do not adapt — they collapse into deterministic loops, exposing a structural limitation of current Transformer-based architectures for genuine compositional reasoning.