# End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 19 of its 25 references that are in the map.
- First posted on arXiv 11 Feb 2022.

## 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, 19 of 19)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [Highway Networks](https://mlsanity.com/paper/1505.00387/) (2015)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [PonderNet: Learning to Ponder](https://mlsanity.com/paper/2107.05407/) (2021)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks](https://mlsanity.com/paper/2106.04537/) (2021)
- [Recurrent Relational Networks](https://mlsanity.com/paper/1711.08028/) (2017)
- [Differentiable Adaptive Computation Time for Visual Reasoning](https://mlsanity.com/paper/2004.12770/) (2020)
- [Datasets for Studying Generalization from Easy to Hard Examples](https://mlsanity.com/paper/2108.06011/) (2021)
- [The Uncanny Similarity of Recurrence and Depth](https://mlsanity.com/paper/2102.11011/) (2021)
- [NAIS-Net: Stable Deep Networks from Non-Autonomous Differential Equations](https://mlsanity.com/paper/1804.07209/) (2018)
- [Improving the Neural GPU Architecture for Algorithm Learning](https://mlsanity.com/paper/1702.08727/) (2017)
- [Deep Algorithmic Question Answering: Towards a Compositionally Hybrid AI for Algorithmic Reasoning](https://mlsanity.com/paper/2109.08006/) (2021)

## Built on by (most cited first, 30 of 33)

- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [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)
- [Looped Transformers are Better at Learning Learning Algorithms](https://mlsanity.com/paper/2311.12424/) (2023)
- [Transformers Can Do Arithmetic with the Right Embeddings](https://mlsanity.com/paper/2405.17399/) (2024)
- [Relaxed Recursive Transformers: Effective Parameter Sharing with Layer-wise LoRA](https://mlsanity.com/paper/2410.20672/) (2024)
- [Length Generalization in Arithmetic Transformers](https://mlsanity.com/paper/2306.15400/) (2023)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [The Unreasonable Effectiveness of Easy Training Data for Hard Tasks](https://mlsanity.com/paper/2401.06751/) (2024)
- [Path Independent Equilibrium Models Can Better Exploit Test-Time Computation](https://mlsanity.com/paper/2211.09961/) (2022)
- [Neural Algorithmic Reasoning with Causal Regularisation](https://mlsanity.com/paper/2302.10258/) (2023)
- [Adaptive Computation with Elastic Input Sequence](https://mlsanity.com/paper/2301.13195/) (2023)
- [Banana: Banach Fixed-Point Network for Pointcloud Segmentation with Inter-Part Equivariance](https://mlsanity.com/paper/2305.16314/) (2023)
- [SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning](https://mlsanity.com/paper/2309.12253/) (2023)
- [Stability and Generalization in Looped Transformers](https://mlsanity.com/paper/2604.15259/) (2026)
- [Position: An Empirically Grounded Identifiability Theory Will Accelerate Self-Supervised Learning Research](https://mlsanity.com/paper/2504.13101/) (2025)
- [Grounded Image Text Matching with Mismatched Relation Reasoning](https://mlsanity.com/paper/2308.01236/) (2023)
- [Benchmarking ChatGPT on Algorithmic Reasoning](https://mlsanity.com/paper/2404.03441/) (2024)
- [Adaptive recurrent vision performs zero-shot computation scaling to unseen difficulty levels](https://mlsanity.com/paper/2311.06964/) (2023)
- [Unlocking Out-of-Distribution Generalization in Transformers via Recursive Latent Space Reasoning](https://mlsanity.com/paper/2510.14095/) (2025)
- [Learning to Stop Overthinking at Test Time](https://mlsanity.com/paper/2502.10954/) (2025)
- [Stabilizing Extrapolation in Looped Transformers via Learned Stochastic Stopping](https://mlsanity.com/paper/2606.29983/) (2026)
- [Logical Tasks for Measuring Extrapolation and Rule Comprehension](https://mlsanity.com/paper/2211.07727/) (2022)
- [What Survives When You Compress a Recursive Reasoner for the Edge?](https://mlsanity.com/paper/2606.26488/) (2026)
- [MazeNet: An Accurate, Fast, and Scalable Deep Learning Solution for Steiner Minimum Trees](https://mlsanity.com/paper/2410.18832/) (2024)
- [Playing Hex and Counter Wargames using Reinforcement Learning and Recurrent Neural Networks](https://mlsanity.com/paper/2502.13918/) (2025)
- [Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion](https://mlsanity.com/paper/2607.19635/) (2026)
- [DART: Distributional Adversarial Recurrent Training for Algorithm Learning](https://mlsanity.com/paper/2609.05988/) (2026)
- [Storing Is Not Remembering: LSTM-UT and Bounded Gated Memory for Looped Transformers](https://mlsanity.com/paper/2609.19521/) (2026)
- [Reasoning with Neural Cellular Automata](https://mlsanity.com/paper/2609.36126/) (2026)

## Abstract (arXiv)

Machine learning systems perform well on pattern matching tasks, but their ability to perform algorithmic or logical reasoning is not well understood. One important reasoning capability is algorithmic extrapolation, in which models trained only on small/simple reasoning problems can synthesize complex strategies for large/complex problems at test time. Algorithmic extrapolation can be achieved through recurrent systems, which can be iterated many times to solve difficult reasoning problems. We observe that this approach fails to scale to highly complex problems because behavior degenerates when many iterations are applied -- an issue we refer to as "overthinking." We propose a recall architecture that keeps an explicit copy of the problem instance in memory so that it cannot be forgotten. We also employ a progressive training routine that prevents the model from learning behaviors that are specific to iteration number and instead pushes it to learn behaviors that can be repeated indefinitely. These innovations prevent the overthinking problem, and enable recurrent systems to solve extremely hard extrapolation tasks.