Elamur Research⌕
☰
home / papers / 2023 / Can Transformers Learn to Solve Problems Recursively?

Can Transformers Learn to Solve Problems Recursively?

Paper · 2023 · Shizhuo Dylan Zhang, Curt Tigges, Stella Biderman et al.

Summary

This study asks whether small transformer models can learn to imitate structurally recursive functions purely from input-output examples. Structural recursion underlies programming and theorem-proving tasks where symbolic tools still outperform neural ones. The authors define datatypes inductively, in Coq-style notation, so that a model cannot rely on prior associations with numbers. They then train transformers from scratch on two tasks. The first is the binary successor function, which has one recursive case. The second is binary tree traversal (preorder and inorder), which has two recursive cases. For analysis, they pair their experiments with a theoretical lens built on abstract-state machines (ASMs). They also apply mechanistic interpretability methods, including patching, circuit tracing and ablation, to reconstruct the algorithms the models actually learn. They find that the models do not learn true recursion. Instead, they acquire shortcut heuristics, such as tricks tied to particular tree depths. Reconstructing these shortcuts makes it possible to predict where the models will fail. The work offers a basis for explaining why neural models fall short on the very tasks they were trained for.

Key points

  • The authors are Shizhuo Dylan Zhang, Curt Tigges, Stella Biderman, Maxim Raginsky and Talia Ringer, from UIUC, EleutherAI and Booz Allen Hamilton.
  • For one of the approximated functions, the reconstructed shortcut algorithms correctly predict 91% of the model's failure cases.
  • The binary successor task uses three symbols (XO, X1, 01). Separate models are trained on the "natural" and the "reverse" bit orderings.
  • On tree traversal, a model trained on an atomic one-step reduction subtask (UNROLL) performs well, while the same setup fails on the full end-to-end traversal.
  • Attention heads that track brackets and parentheses, a rough proxy for recursion depth, are among the most important for performance. Deeper reductions require extra reliance on decoder self-attention, which shallow reductions do not.

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 Illinois Urbana-ChampaignUrbana · United States228 works · 74,590 citations🏢Booz Allen HamiltonTysons Corner · United States4 works · 1,881 citations

 Fields, topics and concepts

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

Cite

Cite as Shizhuo Dylan Zhang, Curt Tigges, Stella Biderman, Maxim Raginsky and Talia Ringer. 2023. Can Transformers Learn to Solve Problems Recursively?. arXiv:2305.14699.

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

@misc{zhang2023can,
  title = {{Can Transformers Learn to Solve Problems Recursively?}},
  author = {Shizhuo Dylan Zhang, Curt Tigges, Stella Biderman, Maxim Raginsky and Talia Ringer},
  year = {2023},
  doi = {10.48550/arxiv.2305.14699},
  eprint = {2305.14699},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2305.14699}
}

References

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

  1. Arpan Agrawal et al. “Proofster: Automated Formal Verification”. In: ICSE Demo. May 2023. find
  2. Loubna Ben Allal et al. SantaCoder: don’t reach for the stars! 2023. arXiv: 2301.03988 [cs.SE].
  3. Swarat Chaudhuri et al. “Neurosymbolic programming”. In: Foundations and Trends® in Programming Languages 7.3 (2021), pp. 158–243. find
  4. Mark Chen et al. “Evaluating Large Language Models Trained on Code”. In: CoRR abs/2107.03374 (2021). arXiv: 2107.03374. URL : https://arxiv.org/abs/2107.03374. ↗
  5. Aakanksha Chowdhery et al. “PaLM: Scaling Language Modeling with Pathways”. In: CoRR abs/2204.02311 (2022). DOI : 10.48550/arXiv.2204.02311. arXiv: 2204.02311. URL : https://doi.org/10.48550/arXiv.2204.02311. ↗
  6. Bilal Chughtai, Lawrence Chan, and Neel Nanda. A Toy Model of Universality: Reverse Engineering How Networks Learn Group Operations. 2023. DOI : 10.48550/ARXIV.2302.03025. URL : https://arxiv.org/abs/2302.03025. — [doi:10.48550/arxiv.2302.03025](https://doi.org/10.48550/arxiv.2302.03025) ↗
  7. Arthur Conmy et al. Towards Automated Circuit Discovery for Mechanistic Interpretability. 2023. arXiv: 2304.14997 [cs.LG]. find
  8. Andrew Cropper et al. “Inductive logic programming at 30”. In: CoRR abs/2102.10556 (2021). arXiv: 2102.10556. URL : https://arxiv.org/abs/2102.10556. — [arXiv:2102.10556](https://arxiv.org/abs/2102.10556) ↗
  9. Mostafa Dehghani et al. Universal Transformers. 2019. arXiv: 1807.03819 [cs.CL]. find
  10. Grégoire Delétang et al. Neural Networks and the Chomsky Hierarchy. 2022. DOI : 10.48550/ ARXIV.2207.02098. URL : https://arxiv.org/abs/2207.02098. ↗
  11. N Elhage et al. “A mathematical framework for transformer circuits”. In: Transformer Circuits Thread (2021). find
  12. Emily First and Yuriy Brun. “Diversity-Driven Automated Formal Verification”. In: ICSE (ICSE). May 2022, pp. 749–761. DOI : 10.1145/3510003.3510138. — [doi:10.1145/3510003.3510138](https://doi.org/10.1145/3510003.3510138) find
  13. Emily First et al. Baldur: Whole-Proof Generation and Repair with Large Language Models. 2023. arXiv: 2303.04910 [cs.LG].
  14. Mor Geva et al. Transformer Feed-Forward Layers Are Key-Value Memories. 2020. DOI : 10.48550/ ARXIV.2012.14913. URL : https://arxiv.org/abs/2012.14913. ↗
  15. Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. “Program Synthesis”. In: Foundations and Trends® in Programming Languages 4.1-2 (2017), pp. 1–119. ISSN : 2325-1107. DOI : 10.1561/ 2500000010. URL : http://dx.doi.org/10.1561/2500000010. ↗
  16. Rahul Gupta et al. “DeepFix: Fixing Common C Language Errors by Deep Learning”. In: AAAI. 2017. find
  17. Yuri Gurevich. “Evolving Algebras 1993: Lipari Guide”. In: Specification and Validation Methods. Specification and Validation Methods. Oxford University Press, Jan. 1995, pp. 9–36. URL : https://www.microsoft.com/en-us/research/publication/103-evolving-algebras-1993-lipari-guide/. ↗
  18. Michael Hahn. “Theoretical Limitations of Self-Attention in Neural Sequence Models”. In: Transactions of the Association for Computational Linguistics 8 (Dec. 2020), pp. 156–171. DOI : 10.1162/ tacl_a_00306. URL : https://doi.org/10.1162%2Ftacl_a_00306. find
  19. Woosuk Lee and Hangyeol Cho. “Inductive Synthesis of Structurally Recursive Functional Programs from Non-Recursive Expressions”. In: Proc. ACM Program. Lang. 7.POPL (Jan. 2023). DOI : 10.1145/3571263. URL : https://doi.org/10.1145/3571263. — [doi:10.1145/3571263](https://doi.org/10.1145/3571263) ↗
  20. Raymond Li et al. StarCoder: may the source be with you! 2023. arXiv: 2305.06161 [cs.CL]. find
  21. Yujia Li et al. “Competition-Level Code Generation with AlphaCode”. In: DeepMind (2022).
  22. Bingbin Liu et al. Transformers Learn Shortcuts to Automata. 2022. DOI : 10.48550/ARXIV.2210. 10749. URL : https://arxiv.org/abs/2210.10749. ↗
  23. Nicolas Magaud and Yves Bertot. “Changing Data Structures in Type Theory:A Study of Natural Numbers”. In: vol. 2277. Dec. 2000, pp. 181–196. ISBN : 978-3-540-43287-6. DOI : 10.1007/3-540-45842-5_12. — [doi:10.1007/3-540-45842-5_12](https://doi.org/10.1007/3-540-45842-5_12) find
  24. Kevin Meng et al. Locating and Editing Factual Associations in GPT. 2023. arXiv: 2202.05262 [cs.CL]. find
  25. William Merrill and Ashish Sabharwal. Transformers Can Be Expressed In First-Order Logic with Majority. 2022. DOI : 10.48550/ARXIV.2210.02671. URL : https://arxiv.org/abs/2210. 02671. ↗
  26. Anders Miltner et al. “Synthesizing Symmetric Lenses”. In: Proc. ACM Program. Lang. 3.ICFP (July 2019). DOI : 10.1145/3341699. URL : https://doi.org/10.1145/3341699. — [doi:10.1145/3341699](https://doi.org/10.1145/3341699) ↗
  27. Neel Nanda et al. Progress measures for grokking via mechanistic interpretability. 2023. DOI : 10.48550/ARXIV.2301.05217. URL : https://arxiv.org/abs/2301.05217. ↗
  28. Maxwell Nye et al. “Show your work: Scratchpads for intermediate computation with language models”. In: arXiv preprint arXiv:2112.00114 (2021).
  29. Peter-Michael Osera and Steve Zdancewic. “Type-and-Example-Directed Program Synthesis”. In: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI ’15. Portland, OR, USA: Association for Computing Machinery, 2015, pp. 619–630. ISBN : 9781450334686. DOI…
  30. Jorge Pérez, Pablo Barceló, and Javier Marinkovic. “Attention is Turing-Complete”. In: Journal of Machine Learning Research 22.75 (2021), pp. 1–35. URL : http://jmlr.org/papers/v22/20-302.html. ↗
  31. Jorge Pérez, Javier Marinković, and Pablo Barceló. On the Turing Completeness of Modern Neural Network Architectures. 2019. arXiv: 1901.03429 [cs.LG]. find
  32. Mary Phuong and Marcus Hutter. Formal Algorithms for Transformers. 2022. arXiv: 2207.09238 [cs.LG]. — [arXiv:2207.09238](https://arxiv.org/abs/2207.09238) find
  33. Talia Ringer. “Proof Repair”. PhD thesis. 2021. find
  34. Talia Ringer et al. “Proof Repair across Type Equivalences”. In: Proceedings of the 42nd ACM SIG-PLAN International Conference on Programming Language Design and Implementation. PLDI 2021. Virtual, Canada: Association for Computing Machinery, 2021, pp. 112–127. ISBN : 9781450383912. DOI : 10.1145/34… — [doi:10.1145/3453483.3454033](https://doi.org/10.1145/3453483.3454033) find
  35. Ripon K. Saha et al. “ELIXIR: Effective object oriented program repair”. In: ASE. 2017, pp. 648– 659. find
  36. Alex Sanchez-Stern et al. “Generating Correctness Proofs with Neural Networks”. In: Proceedings of the 4th ACM SIGPLAN International Workshop on Machine Learning and Programming Languages. MAPL 2020. London, UK: Association for Computing Machinery, 2020, pp. 1–10. ISBN : 9781450379960. DOI : 10.1145…
  37. Alex Sanchez-Stern et al. “Passport: Improving Automated Formal Verification Using Identifiers”. In: ACM TOPLAS (2023).
  38. Ashish Vaswani et al. “Attention is All you Need”. In: Advances in Neural Information Processing Systems. Ed. by I. Guyon et al. Vol. 30. Curran Associates, Inc., 2017. URL : https://proceedings.neurips . cc / paper _ files / paper / 2017 / file / 3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf. ↗
  39. Kevin Wang et al. “Interpretability in the Wild: a Circuit for Indirect Object Identification in GPT-2 small”. In: arXiv preprint arXiv:2211.00593 (2022). find
  40. Jason Wei et al. “Chain of thought prompting elicits reasoning in large language models”. In: arXiv preprint arXiv:2201.11903 (2022).
  41. Chunqiu Steven Xia, Yuxiang Wei, and Lingming Zhang. “Automated program repair in the era of large pre-trained language models”. In: Proceedings of the 45th International Conference on Software Engineering (ICSE 2023). Association for Computing Machinery. 2023. find
  42. Kaiyu Yang and Jia Deng. “Learning to prove theorems via interacting with proof assistants”. In: International Conference on Machine Learning. PMLR. 2019, pp. 6984–6994.
  43. Shunyu Yao et al. “Self-Attention Networks Can Process Bounded Hierarchical Languages”. In: Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). Online: Association…
  44. Chiyuan Zhang et al. Pointer Value Retrieval: A new benchmark for understanding the limits of neural network generalization. 2022. arXiv: 2107.12580 [cs.LG]. find
  45. Yi Zhang et al. Unveiling Transformers with LEGO: a synthetic reasoning task. 2022. DOI : 10. 48550/ARXIV.2206.04301. URL : https://arxiv.org/abs/2206.04301. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2023-transformers-learn-solve-problems-recursively/