Why LLMs really collapse on the Tower of Hanoi

▣ Simulation▣ Generative AI◆ Generative AI◆ Algorithms◆ Interactive

Updated：2026-09-23Published

Apple’s paper “The Illusion of Thinking” showed that accuracy collapses as you add disks, and concluded that the models are not reasoning. The rebuttal said they merely ran into the output token limit.

Which is right? Ask the same puzzle two different ways and watch.

The “Illusion of Thinking” debateCan it not reason, or can it just not write it all out?

Why LLMs really “collapse” on the Tower of Hanoi

The same puzzle, asked two ways. Left: “list every move.” Right: “write a function that generates the moves.”

Minimum moves (2ⁿ−1)

1,023

If written out

33k chars

Chance of zero mistakes

35.9%

Which wall comes first

Error accumulation

Output token limit:

Number of disks n10 disks (1,023 moves)

▲ error wall 10▲ token wall 13

Error rate per move e0.10%

Listing every move hits two walls

Output is 10,230 tokens (16% of the 64K limit). And even at 0.100% error per move, running 1,023 moves drops the chance of a perfect answer to 35.9%.

Writing a function removes both walls

Output stays at about 300 tokens regardless of n. A machine expands the moves, so per-move errors never accumulate. This is exactly the rebuttal paper’s point.

What is happening

The move count is 2ⁿ−1: 1,023 moves at 10 disks, 1.04 million at 20

Each extra disk doubles the number of moves. That is not a matter of reasoning difficulty — it is the length of the answer.

Raise n with the slider and the token meter pins immediately. Shifting the per-move token estimate by a factor of two or three moves the limiting n by only one or two. Against 2ⁿ, the precision of the estimate simply does not matter.

Even with tokens to spare, accumulated error breaks it

Set the error rate to 0.10% — a mistake once every thousand moves, which is generous.

Even then, the chance of a perfect answer at n=10 (1,023 moves) is 36%. At n=13 (8,191 moves) it is 0.03%. With a 64K limit and 0.1% error, the error wall (n=10) arrives before the token wall (n=13).

So “it was just the token limit” on its own does not explain the collapse. That is where the rebuttal overreaches.

Change the output format and the same model succeeds

Instead of “list every move,” ask it to write a function that generates the moves. Output size becomes roughly constant in n, and the token wall disappears.

Same puzzle, same model. The only difference is how the answer is expressed.

Conclusion: both papers see only half of it

Apple’s “collapse = evidence of no reasoning” does not separate out the fact that the answer length grows as 2ⁿ
The rebuttal’s “it just hit the token limit” leaves out error accumulation

What this simulation shows is that two distinct walls exist, and which one arrives first depends on the settings. And changing the format of the answer removes one of them entirely. An experiment intended to measure whether a model can reason may in fact have been measuring whether it can write a very long answer without slipping.

Facts and sources

The two papers

Apple, “The Illusion of Thinking” Apple Machine Learning Research (primary)
Rebuttal, “The Illusion of the Illusion of Thinking” arXiv:2506.09250, by Alex Lawsen of Open Philanthropy with Claude Opus 4
Overviews of the debate: Simon Willison, “Seven replies to the viral Apple reasoning paper” / VentureBeat / Sean Goedecke

Assumptions this model makes (not facts)

Tokens for one move written in prose: 10
Output size for “write a function that generates the moves”: 300 tokens
The chance of a perfect answer is (1−e)^(2ⁿ−1) for a per-move error rate e

These are estimates, not measurements from any specific model. As noted above, shifting them by a factor of two or three barely moves the limiting n.