Elamur Research⌕
☰
home / papers / 2022 / End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking

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

Paper · 2022 · Arpit Bansal, Avi Schwarzschild, Eitan Borgnia et al.

Summary

The authors investigate whether a neural network trained on small, simple problems can by itself infer an algorithm for much larger and harder problems. They call this ability logical extrapolation. The basis is recurrent Deep Thinking (DT) networks: a single residual block with shared weights is repeated many times, and the number of repetitions can be increased at test time. Previously, such models broke down when the number of iterations became much larger than during training. The authors named this phenomenon "overthinking". They propose two solutions. The first is the recall architecture: the input problem is fed to the features again at every step, so the model cannot "forget" it. The second is progressive training, which prevents the network from tying itself to the iteration number and forces it to improve the solution incrementally. The method was tested on three tasks: prefix sums, mazes, and chess puzzles. A model trained on 9×9 mazes solves 201×201 mazes and larger without retraining. The network state converges to a fixed point, so no stopping rule is needed. This matters for real-world data, where harder cases than those in the training set occur during deployment.

Key points

  • Previously, DT models trained on 9×9 mazes extrapolated only to 13×13. DT-Recall with progressive training reliably solves 59×59 and 201×201 mazes.
  • For the largest mazes, the models perform over 2,000 iterations, which corresponds to over 10,000 convolutional layers.
  • Model components: an input projection (convolution + ReLU), a recurrent block with a four-layer residual block, and an output head of three convolutional layers. During training the number of iterations is fixed, and gradients are computed through the unrolled network.
  • Robustness check. After 50 iterations, the models recover if a single bit is flipped in the input to the prefix-sum task. If the features are swapped for those of a different maze, the model with recall still returns to the solution of its own maze.
  • The change in features between iterations (ℓ2 norm) tends to zero in the new models. In DT without recall, by contrast, it explodes. The work was published at NeurIPS 2022.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of Maryland, College ParkCollege Park · United States151 works · 29,733 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 works

Cite

Cite as Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang, Micah Goldblum and Tom Goldstein. 2022. End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking. arXiv:2202.05826.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2202.05826 · arXiv 2202.05826

@misc{bansal2022end,
  title = {{End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking}},
  author = {Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang, Micah Goldblum and Tom Goldstein},
  year = {2022},
  doi = {10.48550/arxiv.2202.05826},
  eprint = {2202.05826},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2202.05826}
}

References

25 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Andrea Banino, Jan Balaguer, and Charles Blundell. Pondernet: Learning to ponder. arXiv preprint arXiv:2107.05407, 2021.
  2. Marco Ciccone, Marco Gallieri, Jonathan Masci, Christian Osendorfer, and Faustino Gomez. Nais-net: Stable deep networks from non-autonomous differential equations. arXiv preprint arXiv:1804.07209, 2018. — [arXiv:1804.07209](https://arxiv.org/abs/1804.07209) find
  3. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Łukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819, 2018. find
  4. Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. IEEE, 2009. find
  5. Cristobal Eyzaguirre and Alvaro Soto. Differentiable adaptive computation time for visual reasoning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12817– 12825, 2020. find
  6. Karlis Freivalds and Renars Liepins. Improving the neural gpu architecture for algorithm learning. arXiv preprint arXiv:1702.08727, 2017. find
  7. Felix A Gers and E Schmidhuber. Lstm recurrent networks learn simple context-free and context-sensitive languages. IEEE Transactions on Neural Networks, 12(6):1333–1340, 2001. find
  8. Alex Graves. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv:1603.08983, 2016. find
  9. Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines, 2014. find
  10. K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, 2016.
  11. Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700–4708, 2017. find
  12. Herbert Jaeger. Tutorial on training recurrent neural networks, covering BPPT, RTRL, EKF and the" echo state network" approach, volume 5.01. GMD-Forschungszentrum Informationstechnik Bonn, 2002. find
  13. Łukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. arXiv preprint arXiv:1511.08228, 2015. find
  14. Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
  15. Richard E Ladner and Michael J Fischer. Parallel prefix computation. Journal of the ACM (JACM), 27(4): 831–838, 1980. find
  16. Kwwabena Nuamah. Deep algorithmic question answering: Towards a compositionally hybrid AI for algorithmic reasoning. arXiv preprint arXiv:2109.08006, 2021. — [arXiv:2109.08006](https://arxiv.org/abs/2109.08006) find
  17. Rasmus Berg Palm, Ulrich Paquet, and Ole Winther. Recurrent relational networks. In 32nd Conference on Neural Information Processing Systems, pages 3368–2278. Neural Information Processing Systems Foundation, 2018. find
  18. Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint arXiv:2108.12409, 2021. find
  19. Jürgen Schmidhuber. Self-delimiting neural networks. arXiv preprint arXiv:1210.0118, 2012. — [arXiv:1210.0118](https://arxiv.org/abs/1210.0118) find
  20. Jürgen Schmidhuber, Daan Wierstra, Matteo Gagliolo, and Faustino Gomez. Training recurrent networks by evolino. Neural computation, 19(3):757–779, 2007. find
  21. Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Arpit Bansal, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. Datasets for studying generalization from easy to hard examples, 2021. find
  22. Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks, 2021. find
  23. Avi Schwarzschild, Arjun Gupta, Amin Ghiasi, Micah Goldblum, and Tom Goldstein. The uncanny similarity of recurrence and depth, 2021. find
  24. Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning a sat solver from single-bit supervision. arXiv preprint arXiv:1802.03685, 2018.
  25. Rupesh Kumar Srivastava, Klaus Greff, and Jürgen Schmidhuber. Highway networks. arXiv preprint arXiv:1505.00387, 2015.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bansal-2022-end-end-algorithm-synthesis-recurrent/