# Recurrent Reasoning on Symbolic Puzzles with Sequence Models

arXiv: https://arxiv.org/abs/2606.15686 · HTML: https://mlsanity.com/paper/2606.15686/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 28 of its 33 references that are in the map.
- First posted on arXiv 19 Apr 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 28 of 28)

- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Right for the Wrong Reasons: Diagnosing Syntactic Heuristics in Natural Language Inference](https://mlsanity.com/paper/1902.01007/) (2019)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [oLMpics -- On what Language Model Pre-training Captures](https://mlsanity.com/paper/1912.13283/) (2019)
- [What Language Model Architecture and Pretraining Objective Work Best for Zero-Shot Generalization?](https://mlsanity.com/paper/2204.05832/) (2022)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [Learning to Execute](https://mlsanity.com/paper/1410.4615/) (2014)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Neural Programmer-Interpreters](https://mlsanity.com/paper/1511.06279/) (2015)
- [Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architectures](https://mlsanity.com/paper/2007.08970/) (2020)
- [Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping](https://mlsanity.com/paper/2402.14083/) (2024)
- [Can Large Language Models Reason and Plan?](https://mlsanity.com/paper/2403.04121/) (2024)
- [Transcending Scaling Laws with 0.1% Extra Compute](https://mlsanity.com/paper/2210.11399/) (2022)
- [Coloring the Blank Slate: Pre-training Imparts a Hierarchical Inductive Bias to Sequence-to-sequence Models](https://mlsanity.com/paper/2203.09397/) (2022)
- [Examining Scaling and Transfer of Language Model Architectures for Machine Translation](https://mlsanity.com/paper/2202.00528/) (2022)
- [CausalLM is not optimal for in-context learning](https://mlsanity.com/paper/2308.06912/) (2023)

## Abstract (arXiv)

Large language models often appear strong on symbolic and algorithmic tasks, yet this apparent strength can hide brittle behaviour when problems become longer, harder, or slightly out of distribution. A major limitation of current reasoning benchmarks is that many primarily test whether a model can produce a valid answer, while paying less attention to whether the solution is minimal, robust, and stable under controlled difficulty scaling. We introduce RecurrReason, a difficulty-controlled benchmark of four recurrent logic puzzles (Tower of Hanoi, River Crossing, Block World, and Checkers Jumping) with BFS-optimal trajectories and a single interpretable difficulty parameter N ∈ 1,dots,10, totalling 10,817 unique puzzles and 285,933 moves. We benchmark two Transformer families, an encoder-decoder model (T5-style) and a decoder-only model (GPT-2-style), under consistent data splits and evaluation criteria, training on N=1 to 7 and evaluating on both held-out in-distribution instances and harder out-of-distribution instances at N=8 to 10. Fine-tuned pre-trained T5 achieves 97.27% validation and 81.00% OOD accuracy on Block World; all models score 0.00% on River Crossing under all conditions. Failure mode analysis reveals that architecture is a stronger determinant of success than scale. Pre-training transfers only to puzzles with locally structured transition functions. Our code and dataset will be open-sourced upon acceptance.