Mannem et al.: Some Puzzles Are Learnable, Some Are Not — Fukai Reads

TL;DR

Today I read a preprint that reshapes four classic logic puzzles — Tower of Hanoi, River Crossing, Block World and Checkers Jumping — into a single benchmark with exactly one difficulty knob, then trains small language models on it to ask which puzzles are learnable and which are not. The set contains 10,817 puzzles and 285,933 moves. Difficulty runs from N=1 to N=10; the models train on N=1 to 7, and N=8 to 10 is held out entirely, so problems harder than anything seen in training are graded separately.

The results differ enormously from puzzle to puzzle. On Block World a T5-style model reached 97.27% on validation and 81.00% on the held-out harder instances. Tower of Hanoi peaked at 11.11% validation and 0.00% out-of-distribution; Checkers Jumping at 1.11% and 0.10%; River Crossing scored 0.00% for every model under every condition (all from the paper's Table 2). That is a wide gap inside one category called 'logic puzzles'.

The authors attribute the gap not to model size but to puzzle structure and the shape of the input-output format. A 60M-parameter T5 beat a 124M-parameter GPT-2 on every puzzle. Read from a puzzle maker's chair, this gives us a way to look at difficulty along three axes rather than move count alone: how much of the board a single move rewrites, how many options there are, and how the solution length grows. This is an arXiv preprint (arXiv:2606.15686, June 2026); the text says code and data will be released upon acceptance, so it has not yet been peer-reviewed.

Introduction

The paper is titled 'Recurrent Reasoning on Symbolic Puzzles with Sequence Models'. The authors are Gowrav Mannem, Chowdhury Marzia Mahjabin, Jason Chen, Shivank Garg and Kevin Zhu, affiliated with Algoverse AI Research, with Jason Chen also listed at Cornell University. The arXiv ID is 2606.15686, submitted in June 2026.

A note on venue first. This is an arXiv preprint, not a peer-reviewed conference or journal paper. The text states that code and data will be open-sourced upon acceptance, which reads as 'currently under submission'. So in this article I quote the numbers exactly as the paper gives them, while staying cautious about generalising the conclusions.

I chose it today because it is the mirror image of the study I covered here yesterday — Pereira and Zuidema, on how a reasoning model builds an internal map of the Tower of Hanoi and then loses it while writing out the moves. That paper looked inside the model to find where things break; this one measures, from the outside, which puzzles do not break. Put side by side, they give a three-dimensional view of how puzzle difficulty bites on the machine side.

Background

Research on making language models solve puzzles has grown fast in recent years, but most of it grades on whether the final answer is right. The authors object to that. What reasoning should really ask is whether each intermediate move was legal, whether the model stayed consistent over a long trajectory, and whether it finished in close to the minimum number of moves. A correct answer reached through nonsense is hard to call reasoning.

This concern extends the point the authors cite most prominently, from Shojaee et al. (2025): models can look competent while leaning on brittle heuristics that collapse under a modest increase in difficulty. Relatedly, Valmeekam et al. (2022, 2023) showed on planning benchmarks that plain next-step prediction does not give stable multi-step reasoning, and Kambhampati (2024) argues from there that explicit symbolic machinery is needed.

What was not settled is whether that brittleness belongs to the model or to the puzzle. If the same model with the same amount of data succeeds on one puzzle and fails on another, then part of the difficulty lives in the structure of the puzzle itself. The RecurrReason benchmark is built to make that separation.

Approach

The authors first put the four puzzles under one shared difficulty knob N. Block World rearranges N labelled blocks across stacks, one move taking the top block of one stack onto another. Tower of Hanoi moves N disks among three pegs under the rule that a larger disk may not sit on a smaller one. Checkers Jumping has N red pieces, a gap and N blue pieces, which must swap sides by sliding one cell or jumping one opposing piece. River Crossing ferries N actor-agent pairs with a boat of capacity k, under the constraint that actor a may not be with another agent unless their own agent A is present.

Every instance comes with a shortest solution found by breadth-first search (BFS — the classical method of exploring outward level by level to find a minimum-length path). That lets the grader judge each move mechanically, including how far it strays from optimal. Table 1 gives the breakdown: Block World 849 puzzles and 5,827 moves; Checkers Jumping 5,700 and 242,494; Tower of Hanoi 60 and 12,216; River Crossing 4,208 and 25,396.

Two model families are used. T5-small (60M parameters) is an encoder-decoder: one part reads the whole input at once, another writes the answer token by token. Because the current board and the goal board both sit on the input side, the goal stays visible at every step of writing. GPT-2 (124M parameters) is decoder-only: current board, goal and next board are strung together and read left to right, so board tokens cannot look ahead to the goal placed after them. The authors call this a structural bottleneck created by the causal mask, the mechanism that lets each token see only what came before it.

Each family is run under three conditions: trained from scratch, pre-trained and evaluated with no puzzle training (zero-shot), and pre-trained then fine-tuned. Training uses AdamW at a learning rate of 0.0001, batch size 16, with early stopping after five rounds without improvement. Four metrics are used: whether the rollout reaches the goal within twice the optimal number of moves, the fraction of legal moves, the excess over the optimal length, and a breakdown of failures (illegal move, unparseable output, looping back to a visited board, and stopping early).

Findings

Block World first. Pre-trained T5, fine-tuned, reached 97.27% on validation and 81.00% on the held-out harder instances (Table 8). The same T5 trained from scratch scored 0.00%, and pre-trained without fine-tuning also 0.00%. GPT-2 under fine-tuning managed 24.55% validation and 0.00% out-of-distribution, and from scratch 21.82% and 0.00%. So this puzzle is solved along exactly one path: fine-tune a pre-trained encoder-decoder.

The other three are bleak. Tower of Hanoi: T5 fine-tuned gives 11.11% validation and 0.00% out-of-distribution (Table 6); GPT-2 gives 0.00% even fine-tuned. Checkers Jumping: both families at 1.11% and 0.10% (Table 5). River Crossing: every cell of Table 7 is 0.00%. On the harder N=8 to 10 split, effectively only Block World's 81.00% survives.

The shape of the failures matters too. When T5 fails on Block World, validation failures are 66.7% loops and 33.3% early stops, with almost no illegal moves; on the harder split it is 58.3% loops, 37.5% early stops and 4.2% illegal moves. GPT-2, by contrast, fails at 80.7% loops on validation but at 91.4% illegal moves out-of-distribution (Figure 2 and Table 9). The authors read this as a model that has memorised which moves are legal within the training range but cannot choose among them by proximity to the goal — and whose grasp of legality itself breaks once difficulty rises. On Tower of Hanoi, 100% of T5's validation failures are illegal moves; on Checkers Jumping, illegal moves account for roughly 86-87% for both families.

The headline conclusion is structure over scale. The 60M T5 beat the 124M GPT-2 on every puzzle. The paper names three properties that set the ceiling on learnability. First, how much of the board you must inspect to check one move (Block World needs only the top of a stack; River Crossing needs the whole arrangement). Second, how many moves are available at a position (River Crossing balloons with the combinations of who boards the boat). Third, how the shortest solution grows (Block World grows in proportion to N; Tower of Hanoi roughly doubles with each added disk, reaching 1,023 moves at N=10; Checkers Jumping grows quadratically, 120 moves at N=10). If the per-move error rate is constant, the authors argue, the chance of success is multiplied down once for every move in the trajectory.

How Puzzle Makers Can Use This

One. The three axes — how much of the board you must inspect to verify a move, how many moves are available, how the solution length grows — transfer directly as a difficulty-design ruler. If you are building a Sokoban-like, adding one crate mostly turns the second and third knobs; as long as legality is decided by what sits beyond the pushed crate, the first stays low. Add a rule that can only be checked against the whole board (keep the total colour count, preserve a symmetry) and perceived difficulty jumps independently of move count. When a designer feels 'the move count is the same but it suddenly got hard', usually the first axis moved.

Two. If you plan to ship an in-game hint system or auto-solver, this paper gives concrete advice about input format. Showing the goal state again at every step (the T5 condition) clearly beat writing it once and letting it scroll away (the GPT-2 condition) at comparable scale. In practice: re-supply 'current board' and 'goal' together on every hint request, and bolt a symbolic legality checker on the outside rather than trusting the model. Given that illegal moves dominate the failure breakdown, that gap is cheaper to close by checking than by training.

Three. There is a use in the other direction. If you want a puzzle that current models do not crack easily, River-Crossing-style global constraints — where legality cannot be judged without the whole board — still work: every model under every condition scored 0.00% here. But that holds for models of this size in this study, and it is not a wall you can lean on permanently.

Four. The failure taxonomy is borrowable for player analytics. The paper's four categories (illegal move, unparseable output, looping back to a visited state, stopping early) map neatly onto human play logs. A stage full of loops means the rules are understood but the direction to the goal is not; a stage full of illegal moves means the rules have not landed; a stage full of early stops means players are past their give-up threshold. Those three readings alone narrow down what to fix in a tutorial.

Limitations

Start with what the authors admit. First, the account of success probability being multiplied down once per move rests on assuming that per-move errors are independent and the error rate constant; the authors explicitly call these simplifying assumptions and note that errors may in practice be correlated. Second, only four puzzles are covered, and transfer to other domains is untested. Third, the pre-trained zero-shot condition produced nothing on any puzzle, which limits what can be said about transfer. Fourth, the models are small (60M to 124M parameters), so extrapolating to large language models is not warranted.

What I would add first is the imbalance in dataset sizes. Table 1 lists 5,700 puzzles for Checkers Jumping but only 60 for Tower of Hanoi. That is partly inherent — fix N and the Hanoi start and goal configurations are essentially determined — but the 11.11% obtained over those 60 instances works out, by the size of the denominator, to a swing of a few problems. When comparing scores across puzzles, keep that difference in denominators in mind.

The second thing I would flag is how to read 'unlearnable'. River Crossing's 0.00% is a result for these two model families, at this data volume, in this input-output format; it does not establish that the puzzle cannot be learned in principle, and the authors do not claim a general law. Taken back to design work, the safe reading is the hedged one: global constraints are hard for models of this kind today. This is also an unreviewed preprint with no accumulated citations yet.

Fukai's Reading

Here is my own reading. I would place this study among the attempts to re-measure puzzle difficulty from the side of machine learnability. The three axes the authors name — how much of the board a move must be checked against, how many options exist, how the solution length grows — read not only as machine properties but as indicators of how much board state a human player must hold in working memory. In the vocabulary of design criticism, this comes close to a proposal to break the vague phrase 'difficulty curve' into three independent knobs. That said, the authors make no claim about human cognition. Whether the gradient of 'hard' lines up between people and machines, or whether there are axes like River Crossing that bite only on the machine side, nobody has measured yet.

Closing

If you want to go deeper, read this alongside Shojaee et al. (2025) — the observation the authors lean on most, that models collapse under a modest rise in difficulty — plus Valmeekam et al. (2022, 2023) on planning benchmarks and Kambhampati (2024). For the classic treatment of compositional generalisation failures, Lake and Baroni (2018) on SCAN is also cited here.

I would also suggest pairing it with the Pereira and Zuidema paper covered on this site yesterday. That one says the board map exists inside the model but decays as the moves are written out; this one says some puzzles are far more prone to that decay than others. Overlay the two and the outline of what the puzzle format actually demands of a model starts to appear from both inside and out.

References

Papers and materials referenced in this article:

・Recurrent Reasoning on Symbolic Puzzles with Sequence Models (Gowrav Mannem, Chowdhury Marzia Mahjabin, Jason Chen, Shivank Garg, Kevin Zhu, 2026, arXiv preprint arXiv:2606.15686)

・Full HTML text of the paper (including Tables 1, 2, 5-9 and Figure 2)

・Key works cited in the paper's related-work section: Shojaee et al. (2025) / Valmeekam et al. (2022, 2023) / Kambhampati (2024) / Lake & Baroni (2018, SCAN) / Talmor et al. (2020) / Ding et al. (2024) / Mueller et al. (2022)

・Related article on this site: Pereira & Zuidema: Reasoning Models Build a Map of the Tower of Hanoi, Then Lose It — Fukai Reads

・Review status: an arXiv preprint with no DOI assigned; the text states that code and data will be released upon acceptance