# Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks

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

## Key facts

- Cited by 117 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 43 references that are in the map.
- First posted on arXiv 8 Jun 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [Perceiver: General Perception with Iterative Attention](https://mlsanity.com/paper/2103.03206/) (2021)
- [Deep Networks with Stochastic Depth](https://mlsanity.com/paper/1603.09382/) (2016)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Recurrent Residual Convolutional Neural Network based on U-Net (R2U-Net) for Medical Image Segmentation](https://mlsanity.com/paper/1802.06955/) (2018)
- [Value Iteration Networks](https://mlsanity.com/paper/1602.02867/) (2016)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Aligning Superhuman AI with Human Behavior: Chess as a Model System](https://mlsanity.com/paper/2006.01855/) (2020)
- [Trellis Networks for Sequence Modeling](https://mlsanity.com/paper/1810.06682/) (2018)
- [Bridging the Gaps Between Residual Learning, Recurrent Neural Networks and Visual Cortex](https://mlsanity.com/paper/1604.03640/) (2016)
- [Differentiable Adaptive Computation Time for Visual Reasoning](https://mlsanity.com/paper/2004.12770/) (2020)

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

- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Large Language Models Are Zero-Shot Time Series Forecasters](https://mlsanity.com/paper/2310.07820/) (2023)
- [Weak-to-Strong Generalization: Eliciting Strong Capabilities With Weak Supervision](https://mlsanity.com/paper/2312.09390/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Reasoning with Latent Thoughts: On the Power of Looped Transformers](https://mlsanity.com/paper/2502.17416/) (2025)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning and Coding with LLMs](https://mlsanity.com/paper/2305.11860/) (2023)
- [Easy-to-Hard Generalization: Scalable Alignment Beyond Human Supervision](https://mlsanity.com/paper/2403.09472/) (2024)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)
- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [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)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [Parcae: Scaling Laws For Stable Looped Language Models](https://mlsanity.com/paper/2604.12946/) (2026)
- [Adaptive Length Image Tokenization via Recurrent Allocation](https://mlsanity.com/paper/2411.02393/) (2024)
- [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)
- [Learning Iterative Reasoning through Energy Diffusion](https://mlsanity.com/paper/2406.11179/) (2024)
- [End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking](https://mlsanity.com/paper/2202.05826/) (2022)
- [Skills-in-Context Prompting: Unlocking Compositionality in Large Language Models](https://mlsanity.com/paper/2308.00304/) (2023)
- [Learning Iterative Reasoning through Energy Minimization](https://mlsanity.com/paper/2206.15448/) (2022)
- [A Configurable Library for Generating and Manipulating Maze Datasets](https://mlsanity.com/paper/2309.10498/) (2023)
- [Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challenges](https://mlsanity.com/paper/2502.01612/) (2025)
- [Universal Length Generalization with Turing Programs](https://mlsanity.com/paper/2407.03310/) (2024)
- [Easy2Hard-Bench: Standardized Difficulty Labels for Profiling LLM Performance and Generalization](https://mlsanity.com/paper/2409.18433/) (2024)
- [Encode, Think, Decode: Scaling test-time reasoning with recursive latent thoughts](https://mlsanity.com/paper/2510.07358/) (2025)

## Abstract (arXiv)

Deep neural networks are powerful machines for visual pattern recognition, but reasoning tasks that are easy for humans may still be difficult for neural models. Humans possess the ability to extrapolate reasoning strategies learned on simple problems to solve harder examples, often by thinking for longer. For example, a person who has learned to solve small mazes can easily extend the very same search techniques to solve much larger mazes by spending more time. In computers, this behavior is often achieved through the use of algorithms, which scale to arbitrarily hard problem instances at the cost of more computation. In contrast, the sequential computing budget of feed-forward neural networks is limited by their depth, and networks trained on simple problems have no way of extending their reasoning to accommodate harder problems. In this work, we show that recurrent networks trained to solve simple problems with few recurrent steps can indeed solve much more complex problems simply by performing additional recurrences during inference. We demonstrate this algorithmic behavior of recurrent networks on prefix sum computation, mazes, and chess. In all three domains, networks trained on simple problem instances are able to extend their reasoning abilities at test time simply by "thinking for longer."