Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 2 Think-and-Execute 2 Think-and-Execute 3 Experimental Setup 3 Experimental Setup 4 Results 4 Results 5 Analysis 5 Analysis 6 Related Work 6 Related Work 7 Limitations and Discussion 7 Limitations and Discussion 8 Conclusion and References 8 Conclusion and References A Experimental Details A Experimental Details B Details of Think-and-Execute B Details of Think-and-Execute C Prompts Used in Our Experiments C Prompts Used in Our Experiments D Human-written Pseudocode Prompts D Human-written Pseudocode Prompts E Generated Analyses E Generated Analyses F Generated Pseudocode Prompts F Generated Pseudocode Prompts G Qualitative Analysis G Qualitative Analysis 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. 1 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 (Zhou et al., 2022a;b; Hao et al., 2023). 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 (Suzgun et al., 2022; Valmeekam et al., 2022; Pan et al., 2023). 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 (Wei et al., 2022; Kojima et al., 2022)) or a piece of code (e.g., Program-of-Thought (Chen et al., 2023), Program-Aided LMs (Gao et al., 2023)). 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 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 (Zhou et al., 2022b), Plan-and-Solve (Wang et al., 2023)). Yet, as prior works have mentioned, during our preliminary experiments, we find that natural language might not be the optimal medium to describe the logic of the problem (Li et al., 2023). 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 within a single task (Zhou et al., 2024). 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 natural language 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 of the task-level pseudocode to follow the logic in it and predicts the output result of the pseudocode. Through extensive experiments on 7 algorithmic reasoning tasks from Big-Bench Hard (Suzgun et al., 2022), 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 natural language (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: • We introduce THINK-AND-EXECUTE, a framework that performs reasoning with a pseudocode that contains the common logical structure of a given task. • We show that THINK-AND-EXECUTE achieves notable improvements over strong baselines, including Chain-of-Thought and Program-of-Thought prompting, across various algorithmic tasks in Big-Bench Hard. • We demonstrate that the pseudocode written by an LLM can be transferred to SLMs, showing the efficiency of our approach. This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license. This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license. available on arxiv Authors:
(1) Hyungjoo Chae, Yonsei University;
(2) Yeonghyeon Kim, Yonsei University;
(3) Seungone Kim, KAIST AI;
(4) Kai Tzu-iunn Ong, Yonsei University;
(5) Beong-woo Kwak, Yonsei University;
(6) Moohyeon Kim, Yonsei University;
(7) Seonghwan Kim, Yonsei University;
(8) Taeyoon Kwon, Yonsei University;
(9) Jiwan Chung, Yonsei University;
(10) Youngjae Yu, Yonsei University;
(11) Jinyoung Yeo, Yonsei University. Authors: Authors: (1) Hyungjoo Chae, Yonsei University; (2) Yeonghyeon Kim, Yonsei University; (3) Seungone Kim, KAIST AI; (4) Kai Tzu-iunn Ong, Yonsei University; (5) Beong-woo Kwak, Yonsei University; (6) Moohyeon Kim, Yonsei University; (7) Seonghwan Kim, Yonsei University; (8) Taeyoon Kwon, Yonsei University; (9) Jiwan Chung, Yonsei University; (10) Youngjae Yu, Yonsei University; (11) Jinyoung Yeo, Yonsei University.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Language Models as Compilers: Simulating Pseudocode Execution Improves Algorithmic Reasoning

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Conducting a Qualitative Analysis by Comparing the Outputs of Our Think-and-Execute Framework

What Is Think-and-Execute?

How We Curated Seven Algorithmic Reasoning Tasks From Big-Bench Hard

Think-and-Execute Improves Algorithmic Reasoning: Here's How

Our Analysis on Think-and-Execute and Pseudocode

Conducting a Qualitative Analysis by Comparing the Outputs of Our Think-and-Execute Framework

What Is Think-and-Execute?

How We Curated Seven Algorithmic Reasoning Tasks From Big-Bench Hard

Think-and-Execute Improves Algorithmic Reasoning: Here's How

Our Analysis on Think-and-Execute and Pseudocode

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps