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

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.

## introduction reasoning in large language models (llms) typically entails analyzing the logical structure underlying a problem and realizing the logic into a sequence of reasoning steps to derive the final answer @xcite . in particular, algorithmic reasoning has long been a formidable challenge for llms, as it requires to scrutinize a complicated reasoning pattern and to translate it into a long sequence of reasoning steps @xcite @xcite . to improve the reasoning capabilities of llms, prior works have primarily pursued two directions. the first direction includes enhancing the reasoning execution step by generating a rationale in natural language (e.g., chain-of-thought @xcite ) or a piece of code (e.g., program-of-thought @xcite , program-aided lms @xcite ). however, such approaches perform step-by-step reasoning on-the-fly, without a dedicated phase for planning. this necessitates that the llm analyze the logic and execute it within a single inference call, which constrains its expressiveness. moreover, when encountering a similar problem, the llm should solve it without being able to reuse the logic previously understood. the second direction involves explicitly generating a plan described in natural language (nl) with llms. the plan describes the logic of the task and the llm would subsequently concretize it into a sequence of reasoning steps (e.g., least-to-most @xcite , plan-and-solve @xcite ). yet, as prior works have mentioned, in our preliminary experiments, we find that nl might not be the optimal medium to describe the logic of the problem @xcite . in addition, prior works mostly rely on generating a plan by observing a single instance, which hinders analyzing the core reasoning pattern shared across similar instances in a single task @xcite . to address these issues, we introduce think-and-execute, an algorithmic framework that discovers a logic that reflects the shared reasoning pattern behind a given task, and conducts reasoning by tailoring the logic into each instance. think-and-execute consists of three distinctive steps; we first ask an llm to think about common reasoning patterns of a task by providing it with a few example questions. then, the llm translates the nl description of the logic in a pseudocode format. the pseudocode format allows more flexibility in applying the logic to each instance compared to programming language such as python. finally, in execute step, the llm simulates the execution @xcite and program-of-thoughts @xcite . through extensive experiments on 7 algorithmic reasoning tasks from big-bench hard @xcite , we show the effectiveness of think-and-execute over the challenging baselines. the superior performance of think-and-execute over pot suggests that discovering the common logic for a given task and applying it to each instance would be more helpful than writing instance-specific code for every instance. noteworthily, simulating the execution of pseudocode is shown to improve lms' reasoning more than planning with nl, even though they are trained to follow nl instructions. furthermore, we empirically show that the pseudocode prompt discovered by an llm can be applied to small lms (slms), such as codellama-7b, to boost their reasoning ability. this indicates the efficiency of think-and-execute over other code prompting methods that require the llm to generate instance-specific code every time (e.g., pot). to summarize, our contributions are as follows: ## think-and-execute in this section, we introduce think-and-execute and provide a detailed explanation of how llms perform reasoning with it. we incorporate an instructor lm i and a reasoner lm r, for think and execute, respectively. figure 2 shows the overview of our framework. ## analysis we conduct experiments to address the following research questions: ## conclusion in this paper, we present think-and-execute, an algorithmic reasoning framework that generates a logic for solving the given task into a pseudocode and performs reasoning by simulating the execution of the pseudocode with language models. through extensive experiments, we show the effectiveness of think-and-execute, over the strong baselines. these results underscore not only the usefulness of pseudocode in eliciting language models' reasoning capabilities but also the efficiency of our framework in discovering the high-quality logic behind a given task.