Language Models as Compilers: Simulating Pseudocode Execution Improves
  Algorithmic Reasoning in Language Models
Authors: name: Hyungjoo Chae; name: Yeonghyeon Kim; name: Seungone Kim; name: Kai Tzu-iunn Ong; name: Beong-woo Kwak; name: Moohyeon Kim; name: Seonghwan Kim; name: Taeyoon Kwon; name: Jiwan Chung; name: Youngjae Yu; name: Jinyoung Yeo
Published: 2024-04-03 08:49:11

Abstract: Algorithmic reasoning refers to the ability to understand the complex
patterns behind the problem and decompose them into a sequence of reasoning
steps towards the solution. Such nature of algorithmic reasoning makes it a
challenge for large language models (LLMs), even though they have demonstrated
promising performance in other reasoning tasks. Within this context, some
recent studies use programming languages (e.g., Python) to express the
necessary logic for solving a given instance/question (e.g.,
Program-of-Thought) as inspired by their strict and precise syntaxes. However,
it is non-trivial to write an executable code that expresses the correct logic
on the fly within a single inference call. Also, the code generated
specifically for an instance cannot be reused for others, even if they are from
the same task and might require identical logic to solve. This paper presents
Think-and-Execute, a novel framework that decomposes the reasoning process of
language models into two steps. (1) In Think, we discover a task-level logic
that is shared across all instances for solving a given task and then express
the logic with pseudocode; (2) In Execute, we further tailor the generated
pseudocode to each instance and simulate the execution of the code. With
extensive experiments on seven algorithmic reasoning tasks, we demonstrate the
effectiveness of Think-and-Execute. Our approach better improves LMs' reasoning
compared to several strong baselines performing instance-specific reasoning
(e.g., CoT and PoT), suggesting the helpfulness of discovering task-level
logic. Also, we show that compared to natural language, pseudocode can better
guide the reasoning of LMs, even though they are trained to follow natural
language instructions.