mlsanityData to 7 Oct 2026

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

arXiv 2106.04537 ↗First posted 8 Jun 2021cs.LG cs.AIcited by 108

Not on the map. Why?

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."

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

Builds on

17 of 43 references.

References · 17

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2019ALBERT: A Lite BERT for Self-supervised Learning of Language Representationscited by 2,772
  3. 2019Invariant Risk Minimizationcited by 1,832
  4. 2021Perceiver: General Perception with Iterative Attentioncited by 1,089
  5. 2016Deep Networks with Stochastic Depthcited by 973
  6. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 723
  7. 2014Neural Turing Machinescited by 630
  8. 2019Deep Equilibrium Modelscited by 603
  9. 2016Adaptive Computation Time for Recurrent Neural Networkscited by 479
  10. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  11. 2018Recurrent Residual Convolutional Neural Network based on U-Net (R2U-Net) for Medical Image Segmentationcited by 180
  12. 2016Value Iteration Networkscited by 158
5 more
  1. 2015Neural GPUs Learn Algorithmscited by 118
  2. 2020Aligning Superhuman AI with Human Behavior: Chess as a Model Systemcited by 78
  3. 2018Trellis Networks for Sequence Modelingcited by 50
  4. 2016Bridging the Gaps Between Residual Learning, Recurrent Neural Networks and Visual Cortexcited by 42
  5. 2020Differentiable Adaptive Computation Time for Visual Reasoningcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 17; 2023: 17; 2024: 22; 2025: 15; 2026: 37.

108 papers.

Sort:

By area:

  1. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,397
  2. 2022Measuring and Narrowing the Compositionality Gap in Language Modelscited by 1,054
  3. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  4. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  5. 2023Large Language Models Are Zero-Shot Time Series Forecasterscited by 491
  6. 2023Weak-to-Strong Generalization: Eliciting Strong Capabilities With Weak Supervisioncited by 445
  7. 2022Transformers Learn Shortcuts to Automatacited by 260
  8. 2025Reasoning with Latent Thoughts: On the Power of Looped Transformerscited by 223
  9. 2022Exploring Length Generalization in Large Language Modelscited by 204
  10. 2023Let's Sample Step by Step: Adaptive-Consistency for Efficient Reasoning and Coding with LLMscited by 111
  11. 2024Easy-to-Hard Generalization: Scalable Alignment Beyond Human Supervisioncited by 95
  12. 2022Tutorial on amortized optimizationcited by 83
38 more
  1. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 82
  2. 2024Transformers Can Do Arithmetic with the Right Embeddingscited by 77
  3. 2024Relaxed Recursive Transformers: Effective Parameter Sharing with Layer-wise LoRAcited by 72
  4. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  5. 2023The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learningcited by 63
  6. 2026Parcae: Scaling Laws For Stable Looped Language Modelscited by 45
  7. 2024The Unreasonable Effectiveness of Easy Training Data for Hard Taskscited by 40
  8. 2024Adaptive Length Image Tokenization via Recurrent Allocationcited by 40
  9. 2024Learning Iterative Reasoning through Energy Diffusioncited by 36
  10. 2022End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinkingcited by 33
  11. 2022Path Independent Equilibrium Models Can Better Exploit Test-Time Computationcited by 33
  12. 2023Skills-in-Context Prompting: Unlocking Compositionality in Large Language Modelscited by 33
  13. 2022Learning Iterative Reasoning through Energy Minimizationcited by 32
  14. 2023A Configurable Library for Generating and Manipulating Maze Datasetscited by 31
  15. 2025Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challengescited by 30
  16. 2024Universal Length Generalization with Turing Programscited by 25
  17. 2024Easy2Hard-Bench: Standardized Difficulty Labels for Profiling LLM Performance and Generalizationcited by 24
  18. 2025Encode, Think, Decode: Scaling test-time reasoning with recursive latent thoughtscited by 23
  19. 2023Adaptive Computation with Elastic Input Sequencecited by 22
  20. 2025Continuous Thought Machinescited by 21
  21. 2023Banana: Banach Fixed-Point Network for Pointcloud Segmentation with Inter-Part Equivariancecited by 19
  22. 2024Planning in a recurrent neural network that plays Sokobancited by 17
  23. 2024Provable Weak-to-Strong Generalization via Benign Overfittingcited by 16
  24. 2026Probabilistic Tiny Recursive Modelcited by 16
  25. 2023Iterative Forward Tuning Boosts In-Context Learning in Language Modelscited by 15
  26. 2026LoopViT: Scaling Visual ARC with Looped Transformerscited by 14
  27. 2024MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofscited by 12
  28. 2026Equilibrium Reasoners: Learning Attractors Enables Scalable Reasoningcited by 12
  29. 2026Training-Free Looped Transformerscited by 12
  30. 2023SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoningcited by 11
  31. 2022A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithmscited by 8
  32. 2023Grounded Image Text Matching with Mismatched Relation Reasoningcited by 8
  33. 2024Benchmarking ChatGPT on Algorithmic Reasoningcited by 8
  34. 2024Rethinking Deep Thinking: Stable Learning of Algorithms using Lipschitz Constraintscited by 8
  35. 2024On Logical Extrapolation for Mazes with Recurrent and Implicit Networkscited by 7
  36. 2025Random Scaling of Emergent Capabilitiescited by 7
  37. 2025Efficient Parallel Samplers for Recurrent-Depth Models and Their Connection to Diffusion Language Modelscited by 7
  38. 2023Adaptive recurrent vision performs zero-shot computation scaling to unseen difficulty levelscited by 6

50 most cited of 108 All 108 (JSON)