@inproceedings{chae-etal-2024-language,
    title = "Language Models as Compilers: Simulating Pseudocode Execution Improves Algorithmic Reasoning in Language Models",
    author = "Chae, Hyungjoo  and
      Kim, Yeonghyeon  and
      Kim, Seungone  and
      Ong, Kai Tzu-iunn  and
      Kwak, Beong-woo  and
      Kim, Moohyeon  and
      Kim, Sunghwan  and
      Kwon, Taeyoon  and
      Chung, Jiwan  and
      Yu, Youngjae  and
      Yeo, Jinyoung",
    editor = "Al-Onaizan, Yaser  and
      Bansal, Mohit  and
      Chen, Yun-Nung",
    booktitle = "Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing",
    month = nov,
    year = "2024",
    address = "Miami, Florida, USA",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/jlcl-multiple-ingestion/2024.emnlp-main.1253/",
    doi = "10.18653/v1/2024.emnlp-main.1253",
    pages = "22471--22502",
    abstract = "Algorithmic reasoning tasks that involve complex logical patterns, such as completing Dyck language, pose challenges for large language models (LLMs), despite their recent success. Prior work has used LLMs to generate programming language and applied external compilers for such tasks. Yet, when on the fly, it is hard to generate an executable code with the correct logic for the solution. Even so, code for one instance cannot be reused for others, although they might require the same logic to solve. We present Think-and-Execute, a novel framework that improves LLMs' algorithmic reasoning: (1) In Think, we discover task-level logic shared across all instances, and express such logic with pseudocode; (2) In Execute, we tailor the task-level pseudocode to each instance and simulate the execution of it. Think-and-Execute outperforms several strong baselines (including CoT and PoT) in diverse algorithmic reasoning tasks. We manifest the advantage of using task-level pseudocode over generating instance-specific solutions one by one. Also, we show that pseudocode can better improve LMs' reasoning than natural language (NL) guidance, even though they are trained with NL instructions."
}