title: Language Models as Compilers: Simulating Pseudocode Execution Improves
    Algorithmic Reasoning in Language Models
summary: 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.
paper_authors._id: 660e2ce3e23148df7c927a69
paper_authors.name: Hyungjoo Chae
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-04-04T07:56:48.638Z
paper_authors._id: 64c8f4cec547ed5243ebd0a8
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/64c8f4cec547ed5243ebd0a8/MiOH5YbMg8Gh9KYlQsLmX.jpeg
paper_authors.fullname: Hyungjoo Chae
paper_authors.type: user
paper_authors.user: hyungjoochae
paper_authors._id: 660e2ce3e23148df7c927a6a
paper_authors.name: Yeonghyeon Kim
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-04-15T06:45:53.955Z
paper_authors._id: 65951e629b53611f666c7973
paper_authors.avatarUrl: /avatars/a395a480ef35c84bd2df204f10a6e873.svg
paper_authors.fullname: Yeong-Hyeon Kim
paper_authors.type: user
paper_authors.user: younghkim1
paper_authors._id: 660e2ce3e23148df7c927a6b
paper_authors.name: Seungone Kim
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-04-05T10:06:14.039Z
paper_authors._id: 6469949654873f0043b09c22
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/6469949654873f0043b09c22/Lk7IJAR16Wa_sGJ2g81AQ.jpeg
paper_authors.fullname: Seungone Kim
paper_authors.type: user
paper_authors.user: seungone
paper_authors._id: 660e2ce3e23148df7c927a6c
paper_authors.name: Kai Tzu-iunn Ong
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-04-05T10:05:55.404Z
paper_authors._id: 640ec2fd2f9c7b364d182735
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/640ec2fd2f9c7b364d182735/G5WxQXYEOaVL39rAoOI3Y.jpeg
paper_authors.fullname: kai tzu-iunn ong
paper_authors.type: user
paper_authors.user: ktio
paper_authors._id: 660e2ce3e23148df7c927a6d
paper_authors.name: Beong-woo Kwak
paper_authors._id: 660e2ce3e23148df7c927a6e
paper_authors.name: Moohyeon Kim
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-05-07T10:24:12.229Z
paper_authors._id: 659513f0f7291078f9ae8c34
paper_authors.avatarUrl: /avatars/2c58fc0630c391a0ae86851fef77898b.svg
paper_authors.fullname: Moohyeon Kim
paper_authors.type: user
paper_authors.user: moojuice8
paper_authors._id: 660e2ce3e23148df7c927a6f
paper_authors.name: Seonghwan Kim
paper_authors._id: 660e2ce3e23148df7c927a70
paper_authors.name: Taeyoon Kwon
paper_authors._id: 660e2ce3e23148df7c927a71
paper_authors.name: Jiwan Chung
paper_authors._id: 660e2ce3e23148df7c927a72
paper_authors.name: Youngjae Yu
paper_authors._id: 660e2ce3e23148df7c927a73
paper_authors.name: Jinyoung Yeo
paper_title: Language Models as Compilers: Simulating Pseudocode Execution Improves
    Algorithmic Reasoning in Language Models
paper_summary: 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.
paper_ai_keywords: large language models (LLMs) algorithmic reasoning Program-of-Thought Think-and-Execute pseudocode task-level logic reasoning process instance-specific reasoning CoT PoT algorithmic reasoning tasks BLEU