Elamur Research⌕
☰
home / papers / 2022 / Teaching Algorithmic Reasoning via In-context Learning

Teaching Algorithmic Reasoning via In-context Learning

Paper · 2022 · Hattie Zhou, Azade Nova, Hugo Larochelle et al.

Summary

Large language models can generalize to new tasks from prompt examples, yet they still fail at algorithmic problems such as parity or multi-digit arithmetic, especially on inputs longer than those in the prompt. Zhou et al. argue that existing rationale-based prompts (scratchpad, chain-of-thought) leave the underlying rules ambiguous. A model may infer the wrong pattern, for instance about when a carry occurs. They propose algorithmic prompting: in-context examples that walk through every step of an algorithm with explicit natural-language explanations, so that only one interpretation is possible. The model is not fine-tuned. The work examines four stages:

  • learning a single algorithm as a skill
  • accumulating several skills in one prompt
  • composing simpler skills into harder ones
  • calling skills as tools inside math word problems

Evaluation separates in-distribution from out-of-distribution performance by answer length. Algorithmic prompts sharply cut errors on long arithmetic and parity compared with few-shot and chain-of-thought baselines. The study also shows that mixing informal reasoning with rigid algorithmic output in one context causes interference. For research on LLM reasoning, this suggests that longer, more precise demonstrations can translate context length into reliable systematic generalization.

Key points

  • Against the strongest baselines, error drops by roughly 10x on long parity, 9x on addition, 5x on multiplication and 2x on subtraction.
  • In ablations, ambiguity-free explanations matter, and mistakes inside algorithmic examples hurt performance noticeably, unlike with other prompting styles.
  • Combining natural-language reasoning with algorithmic steps in one prompt produces an interference effect. Adding a solution plan or prompt flags reduces it only partially.
  • On GSM8k-Hard, a dialogue-style setup routes addition sub-questions via special tokens to a second model holding the addition prompt.
    • Overall accuracy roughly doubles, from 27.4% to 55.8%.
    • Addition accuracy rises from 61.9% to 98.4%.
    • Logical accuracy falls from 70.6% to 57.7%.
  • The tool-use approach also sidesteps context-length limits. Learned algorithms can be invoked as subroutines inside more complex ones.

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

🏢GoogleMountain View · United States492 works · 440,462 citations🎓Université de MontréalMontreal · Canada87 works · 91,597 citations🔬Mila - Quebec Artificial Intelligence InstituteMontreal · Canada65 works · 14,425 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 3,894 worksReasoning · 1,685 works

Cite

Cite as Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur and Hanie Sedghi. 2022. Teaching Algorithmic Reasoning via In-context Learning. arXiv:2211.09066.

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

@misc{zhou2022teaching,
  title = {{Teaching Algorithmic Reasoning via In-context Learning}},
  author = {Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur and Hanie Sedghi},
  year = {2022},
  doi = {10.48550/arxiv.2211.09066},
  eprint = {2211.09066},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2211.09066}
}

References

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

  1. Anil, C., Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., and Neyshabur, B. (2022). Exploring length generalization in large language models. arXiv preprint arXiv:2207.04901.
  2. Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901.
  3. Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. d. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. (2021). Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374.
  4. Chen, X., Liang, C., Yu, A. W., Song, D., and Zhou, D. (2020). Compositional generalization via neural-symbolic stack machines. Advances in Neural Information Processing Systems, 33:1690–1701. find
  5. Chiang, T.-R. and Chen, Y.-N. (2018). Semantically-aligned equation generation for solving and reasoning math word problems. arXiv preprint arXiv:1811.00720. find
  6. Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. (2022). Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311.
  7. Cobbe, K., Kosaraju, V., Bavarian, M., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. (2021). Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168.
  8. Creswell, A. and Shanahan, M. https://arxiv.org/abs/2208.14271. (2022). — Faithful Reasoning Using Large Language Models ↗
  9. Csordás, R., Irie, K., and Schmidhuber, J. (2021). The devil is in the detail: Simple tricks improve systematic generalization of transformers. In ACL. find
  10. Faldu, K., Sheth, A., Kikani, P., Gaur, M., and Avasthi, A. (2021). Towards tractable mathematical reasoning: Challenges, strategies, and opportunities for solving math word problems. arXiv preprint arXiv:2111.05364. find
  11. Gordon, J., Lopez-Paz, D., Baroni, M., and Bouchacourt, D. (2019). Permutation equivariant models for compositional generalization in language. In International Conference on Learning Representations. find
  12. Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. (2021). Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03874.
  13. Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E., Casas, D. d. L., Hendricks, L. A., Welbl, J., Clark, A., et al. (2022). Training compute-optimal large language models. arXiv preprint arXiv:2203.15556.
  14. Jiang, A. Q., Li, W., Tworkowski, S., Czechowski, K., Odrzygóźdź, T., Miłoś, P., Wu, Y., and Jamnik, M. (2022). Thor: Wielding hammers to integrate language models and automated theorem provers. arXiv preprint arXiv:2205.10893.
  15. Jones, E. and Steinhardt, J. (2022). Capturing failures of large language models via human cognitive biases. arXiv preprint arXiv:2202.12299. find
  16. Jung, J., Qin, L., Welleck, S., Brahman, F., Bhagavatula, C., Bras, R. L., and Choi, Y. (2022). Maieutic prompting: Logically consistent reasoning with recursive explanations.
  17. Kaiser, Ł. and Sutskever, I. (2015). Neural gpus learn algorithms. arXiv preprint arXiv:1511.08228. find
  18. Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. (2020). Scaling laws for neural language models. arXiv preprint arXiv:2001.08361.
  19. Faithful reasoning using large language models.
  20. Kim, J., Hong, G., Kim, K.-m., Kang, J., and Myaeng, S.-H. (2021). Have you seen that number? investigating extrapolation in question answering models. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 7031–7037. find
  21. Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. (2022). Large language models are zero-shot reasoners.
  22. Lewkowycz, A., Andreassen, A., Dohan, D., Dyer, E., Michalewski, H., Ramasesh, V., Slone, A., Anil, C., Schlag, I., Gutman-Solo, T., et al. (2022a). Solving quantitative reasoning problems with language models. arXiv preprint arXiv:2206.14858.
  23. Lewkowycz, A., Andreassen, A., Dohan, D. M., Dyer, E. S., Michalewski, H., Ramasesh, V., Slone, A., Anil, C., Schlag, I., Gutman-Solo, T., Wu, Y., Neyshabur, B., Gur-Ari, G., and Misra, V. (2022b). Solving quantitative reasoning problems with language models.
  24. Li, W., Yu, L., Wu, Y., and Paulson, L. C. (2020). Isarstep: a benchmark for high-level mathematical reasoning. arXiv preprint arXiv:2006.09265. find
  25. Ling, W., Yogatama, D., Dyer, C., and Blunsom, P. (2017). Program induction by rationale generation: Learning to solve and explain algebraic word problems. In ACL. find
  26. Madaan, A. and Yazdanbakhsh, A. (2022). Text and patterns: For effective chain of thought, it takes two to tango. arXiv preprint arXiv:2209.07686.
  27. Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L. (2022). Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202.12837.
  28. Nogueira, R., Jiang, Z., and Lin, J. (2021). Investigating the limitations of transformers with simple arithmetic tasks. arXiv preprint arXiv:2102.13019.
  29. Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D., Dohan, D., Lewkowycz, A., Bosma, M., Luan, D., et al. (2021). Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114.
  30. Parisi, A., Zhao, Y., and Fiedel, N. (2022). Talm: Tool augmented language models. arXiv preprint arXiv:2205.12255.
  31. Polu, S. and Sutskever, I. (2020). Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.03393.
  32. Rabe, M. N., Lee, D., Bansal, K., and Szegedy, C. (2020). Mathematical reasoning via self-supervised skip-tree training. arXiv preprint arXiv:2006.04757. find
  33. Razeghi, Y., Logan IV, R. L., Gardner, M., and Singh, S. (2022). Impact of pretraining term frequencies on few-shot reasoning. arXiv preprint arXiv:2202.07206. — [arXiv:2202.07206](https://arxiv.org/abs/2202.07206) find
  34. Saxton, D., Grefenstette, E., Hill, F., and Kohli, P. (2019). Analysing mathematical reasoning abilities of neural models. arXiv preprint arXiv:1904.01557.
  35. Thawani, A., Pujara, J., Szekely, P. A., and Ilievski, F. (2021). Representing numbers in nlp: a survey and a vision. arXiv preprint arXiv:2103.13136.
  36. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. (2017). Attention is all you need. Advances in neural information processing systems, 30.
  37. Veličković, P. and Blundell, C. (2021). Neural algorithmic reasoning. Patterns, 2(7):100273. find
  38. Wang, H., Yu, M., Guo, X., Das, R., Xiong, W., and Gao, T. (2019). Do multi-hop readers dream of reasoning chains? arXiv preprint arXiv:1910.14520. find
  39. Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., and Zhou, D. (2022a). Rationale-augmented ensembles in language models. arXiv preprint arXiv:2207.00747.
  40. Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., and Zhou, D. (2022b). Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171.
  41. Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., et al. (2022a). Emergent abilities of large language models. arXiv preprint arXiv:2206.07682.
  42. Wei, J., Wang, X., Schuurmans, D., Bosma, M., Chi, E., Le, Q., and Zhou, D. (2022b). Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903.
  43. Welleck, S., Liu, J., Bras, R. L., Hajishirzi, H., Choi, Y., and Cho, K. (2021). Naturalproofs: Mathematical theorem proving in natural language. arXiv preprint arXiv:2104.01112.
  44. Wu, Y., Jiang, A. Q., Li, W., Rabe, M. N., Staats, C., Jamnik, M., and Szegedy, C. (2022). Autoformalization with large language models. arXiv preprint arXiv:2205.12615.
  45. Xhonneux, L.-P., Deac, A.-I., Veličković, P., and Tang, J. (2021). How to transfer algorithmic reasoning knowledge to learn new algorithms? Advances in Neural Information Processing Systems, 34:19500–19512. find
  46. Xu, K., Li, J., Zhang, M., Du, S. S., Kawarabayashi, K.-i., and Jegelka, S. (2019). What can neural networks reason about? arXiv preprint arXiv:1905.13211. find
  47. Yan, Y., Swersky, K., Koutra, D., Ranganathan, P., and Hashemi, M. (2020). Neural execution engines: Learning to execute subroutines. Advances in Neural Information Processing Systems, 33:17298–17308. find
  48. Zelikman, E., Wu, Y., and Goodman, N. D. (2022). Star: Bootstrapping reasoning with reasoning. arXiv preprint arXiv:2203.14465.
  49. Zhou, D., Schärli, N., Hou, L., Wei, J., Scales, N., Wang, X., Schuurmans, D., Bousquet, O., Le, Q., and Chi, E. (2022). Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhou-2022-teaching-algorithmic-reasoning-context-learning/