Elamur Research⌕
☰
home / papers / 2024 / Language Models as Compilers: Simulating Pseudocode Execution Improves Algorithmic Reasoning in Language Models

Language Models as Compilers: Simulating Pseudocode Execution Improves Algorithmic Reasoning in Language Models

Paper · 2024 · Hyungjoo Chae, Yeonghyeon Kim, Seungone Kim et al.

Summary

Large language models still struggle with algorithmic reasoning, such as completing Dyck sequences or tracking who lies in a chain of statements. Existing remedies fall short in different ways. Chain-of-Thought and Program-of-Thought reason one instance at a time with no separate planning stage. Natural-language plans tend to describe logic imprecisely. The authors propose THINK-AND-EXECUTE, which separates planning from solving.

In the THINK phase, an Instructor LM receives a meta prompt containing hand-annotated pseudocode for three other tasks, plus three sample questions from the target task. It analyses the reasoning the task requires and writes a single task-level pseudocode prompt. Its print() calls specify which intermediate rationales to produce.

In the EXECUTE phase, a Reasoner LM applies that pseudocode to each instance. It simulates the program's execution, generating the intermediate outputs before the final answer.

On seven Big-Bench Hard tasks, the method beats direct prompting, zero-shot CoT, PoT, NL planning, Chain-of-Code and Plan-and-Solve. This suggests that reusable pseudocode guides models better than natural-language instructions or code written separately for each instance.

Key points

  • With GPT-3.5-Turbo, the average zero-shot accuracy is 60.4, compared with 48.0 for zero-shot CoT, 50.3 for Plan-and-Solve, 32.4 for PoT and 28.1 for Chain-of-Code.
  • Pseudocode generated by a large model transfers to smaller models. CodeLlama-7B improves from 18.4 (CoT) to 30.8 on average, and CodeLlama-13B from 28.2 to 36.3.
  • Gains are strongest on Navigate (96.8 with GPT-3.5-Turbo) and Web of Lies (72.8 vs. 59.2 for CoT). Dyck Languages remains very hard for all methods (at most 8.0).
  • The method consumes more tokens than CoT or PoT, but its accuracy-to-cost trade-off lies on the Pareto front.
  • A demonstrative experiment on SayCan robot planning yields more accurate plans than the baselines. The main limitation is the reliance on human-annotated meta prompts.

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

🎓Carnegie Mellon UniversityPittsburgh · United States633 works · 195,218 citations🎓Yonsei UniversitySeoul · South Korea20 works · 515 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 worksInformation Systems · 1,888 works

🧭 Topics 2Research subjects and languages the work is about.Language models & pretraining · 4,145 worksReasoning · 1,948 works

Cite

Cite as Hyungjoo Chae, Yeonghyeon Kim, Seungone Kim, Kai Tzu-iunn Ong, Beong-woo Kwak, Moohyeon Kim, Sunghwan Kim, Taeyoon Kwon, Jiwan Chung, Youngjae Yu and Jinyoung Yeo. 2024. Language Models as Compilers: Simulating Pseudocode Execution Improves Algorithmic Reasoning in Language Models. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2024.emnlp-main.1253 · arXiv 2404.02575

@inproceedings{chae2024language,
  title = {{Language Models as Compilers: Simulating Pseudocode Execution Improves Algorithmic Reasoning in Language Models}},
  author = {Hyungjoo Chae, Yeonghyeon Kim, Seungone Kim, Kai Tzu-iunn Ong, Beong-woo Kwak, Moohyeon Kim, Sunghwan Kim, Taeyoon Kwon, Jiwan Chung, Youngjae Yu and Jinyoung Yeo},
  booktitle = {Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  doi = {10.18653/v1/2024.emnlp-main.1253},
  eprint = {2404.02575},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/2024.emnlp-main.1253}
}

References

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

  1. Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774.
  2. OpenAI. 2023. Chatgpt. https://openai.com/ blog/chatgpt. ↗
  3. Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang. 2023. Logic-lm: Empowering large language models with symbolic solvers for faithful logical reasoning. ArXiv, abs/2305.12295.
  4. Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. 2023. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. Transactions on Machine Learning Research. find
  5. Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al. 2023. Code llama: Open foundation models for code. arXiv preprint arXiv:2308.12950.
  6. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. 2021. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168.
  7. Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, et al. 2022. Challenging big-bench tasks and whether chain-of-thought can solve them. arXiv preprint arXiv:2210.09261.
  8. Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023. Pal: Program-aided language models. In International Conference on Machine Learning, pages 10764–10799. PMLR. find
  9. Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. 2023. Reasoning with language model is planning with world model. ArXiv, abs/2305.14992. find
  10. Haozhe Ji, Pei Ke, Shaohan Huang, Furu Wei, Xiaoyan Zhu, and Minlie Huang. 2020. Language generation with multi-hop reasoning on commonsense knowledge graph. In Conference on Empirical Methods in Natural Language Processing. find
  11. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199– 22213.
  12. Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. 2022. Large language models still can’t plan (a benchmark for LLMs on planning and reasoning about change). In NeurIPS 2022 Foundation Models for Decision Making Workshop. find
  13. Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wei Lee, and Ee-Peng Lim. 2023. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Lon… find
  14. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171.
  15. Chengshu Li, Jacky Liang, Fei Xia, Andy Zeng, Sergey Levine, Dorsa Sadigh, Karol Hausman, Xinyun Chen, Li Fei-Fei, and brian ichter. 2023. Chain of code: Reasoning with a language model-augmented code interpreter. In NeurIPS 2023 Foundation Models for Decision Making Workshop. find
  16. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. 2022. Chain of thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems.
  17. Aman Madaan and Amir Yazdanbakhsh. 2022. Text and patterns: For effective chain of thought, it takes two to tango. arXiv preprint arXiv:2209.07686.
  18. Nathaniel Weir, Muhammad Khalifa, Linlu Qiu, Orion Weller, and Peter Clark. 2024. Learning to reason via program generation, emulation, and search. find
  19. Mayank Mishra, Prince Kumar, Riyaz Bhat, Rudra Murthy V, Danish Contractor, and Srikanth Tamilsel-vam. 2023. Prompting with pseudo-code instructions. arXiv preprint arXiv:2305.11790. find
  20. Dingjun Wu, Jing Zhang, and Xinmei Huang. 2023. Chain of thought prompting elicits knowledge augmentation. In Findings of the Association for Computational Linguistics: ACL 2023, pages 6519–6534, Toronto, Canada. Association for Computational Linguistics. find
  21. Niklas Muennighoff, Qian Liu, Armel Randy Zebaze, Qinkai Zheng, Binyuan Hui, Terry Yue Zhuo, Swayam Singh, Xiangru Tang, Leandro Von Werra, and Shayne Longpre. 2024. Octopack: Instruction tuning code large language models. In The Twelfth International Conference on Learning Representations. find
  22. Eric Zelikman, Qian Huang, Gabriel Poesia, Noah Goodman, and Nick Haber. 2023. Parsel: Algorithmic reasoning with language models by composing decompositions. Advances in Neural Information Processing Systems, 36:31466–31523.
  23. Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. 2019. HellaSwag: Can a machine really finish your sentence? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4791–4800, Florence, Italy. Association for Computational Linguistics. find
  24. Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. 2022a. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625.
  25. Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanie Sedghi. 2022b. Teaching algorithmic reasoning via in-context learning. arXiv preprint arXiv:2211.09066.
  26. Pei Zhou, Jay Pujara, Xiang Ren, Xinyun Chen, Heng-Tze Cheng, Quoc V Le, Ed H Chi, Denny Zhou, Swaroop Mishra, and Huaixiu Steven Zheng. 2024. Self-discover: Large language models self-compose reasoning structures. arXiv preprint arXiv:2402.03620. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/chae-2024-language-models-as-compilers-simulating/