我们整理分享最新论文：Language Models as Compilers: Simulating Pseudocode Execution Improves Algorithmic Reasoning in Language Models，文末有论文连接。
内容概要
本文介绍了一种名为THINK-AND-EXECUTE的创新规划模式，旨在提高大型语言模型（LLMs）在算法推理任务上的性能。该框架将推理过程分为两个步骤：首先，在THINK阶段，模型发现并表达跨所有实例共享的任务级逻辑，并将其用伪代码形式表达出来；其次，在EXECUTE阶段，模型进一步定制生成的伪代码以适应每个实例，并模拟执行代码。通过在七个算法推理任务上的广泛实验，证明了THINK-AND-EXECUTE框架的有效性，相较于其他强基线方法，如Chain-of-Thought和Program-of-Thought，该方法能更好地提升LMs的推理能力。此外，研究还表明，与自然语言相比，伪代码能更好地引导LMs的推理过程。
文章标签：算法推理、语言模型、伪代码、编译器模拟、任务级逻辑
作者：张长旺, 旺知识
1. 研究背景
大型语言模型（LLMs）中的推理通常涉及分析问题背后的逻辑结构，并实现逻辑成为一系列推理步骤以得出最终答案（Zhou等人，2022a;b; Hao等人，2023）。特别是，算法推理长期以来一直是LLMs的一个巨大挑战，因为它需要仔细审查复杂的推理模式，并将其实现为一系列推理步骤（Suzgun等人，2022; Valmeekam等人，2022; Pan等人，2023）。
为了提高LLMs的推理能力，以前的工作主要追求了两个方向。第一个方向包括通过生成自然语言的合理解释（例如，思维链（Wei等人，2022; Kojima等人，2022））或一段代码（例如，思维程序（Chen等人，2023），程序辅助LMs（Gao等人，2023））来增强推理执行步骤。然而，这种方法在没有专门计划阶段的情况下进行逐步推理。这要求LLM在单个推理调用中分析逻辑并执行它，这限制了其表达能力。此外，以前的工作大多依赖于通过观察单个实例来生成计划，这阻碍了在单个任务中分析跨相似实例共享的核心推理模式（Zhou等人，2024）。
为了解决这些问题，我们引入了THINK-AND-EXECUTE，这是一个算法框架，发现了反映给定任务背后共享推理模式的逻辑，并通过定制逻辑到每个实例来进行推理。THINK-AND-EXECUTE由三个独特的步骤组成；我们首先要求一个LLM通过提供一些示例问题来思考任务的共同推理模式。然后，LLM将逻辑的自然语言描述翻译成伪代码格式。与Python等编程语言相比，伪代码格式在将逻辑应用于每个实例时提供了更多的灵活性。最后，在EXECUTE步骤中，LLM模拟执行任务级伪代码，遵循其中的逻辑并预测伪代码的输出结果。
通过在Big-Bench Hard（Suzgun等人，2022）中的7个算法推理任务上进行广泛的实验，我们展示了THINK-AND-EXECUTE在具有挑战性的基线上的有效性。THINK-AND-EXECUTE优于PoT的结果表明，发现给定任务的共同逻辑并将其应用于每个实例，比为每个实例编写特定代码更有帮助。值得注意的是，模拟伪代码的执行被证明比使用自然语言（NL）进行计划更能改善LMs的推理，即使它们被训练遵循NL指令。此外，我们通过实验表明，一个LLM发现的伪代码提示可以应用于小型LMs（SLMs），例如CodeLlama-7B，以提高它们的推理能力。这表明THINK-AND-EXECUTE比其他需要LLM每次生成特定实例代码的代码提示方法（例如，PoT）更有效。
文本技术创新点如下：
引入了将算法推理任务的逻辑用伪代码表达的方法，提高了模型对复杂逻辑的理解能力。
通过模拟伪代码的执行，使模型能够更好地跟踪和执行推理步骤。
证明了任务级逻辑的发现和应用对于提升模型在算法推理任务上的性能至关重要。
2. THINK-AND-EXECUTE技术实现方案
技术实现设计总结：
设计了一个两阶段的推理框架：THINK阶段用于发现和表达任务级逻辑，EXECUTE阶段用于定制和执行伪代码。
使用了伪代码而不是自然语言或具体的编程语言，提供了更大的灵活性和可读性。
-
通过模拟执行伪代码，模型能够生成中间输出结果，帮助跟踪变量状态的变化。
2.1 THINK：用伪代码格式描述任务的底层逻辑
在这个阶段，指导LM I的目标是发现解决给定任务t的底层逻辑，并生成描述该逻辑的提示，这将进一步应用于任务的所有实例（在EXECUTE中）。这个提示是用伪代码而不是自然语言构建的，自然语言在以前的工作中用于指导LM进行逐步推理（Kojima等人，2022; Wang等人，2023）。
步骤1：构建元提示。为了提示指导LM I为给定的目标任务t生成任务级伪代码，我们在元提示中提供了P个其他任务作为示范。实际上，我们使用T中随机抽取的3个任务（每个任务3个示例问题、分析和P）作为示范，以及目标任务t（没有答案的3个示例问题）。我们手动为T中的每个任务注释P。
步骤2：分析目标任务。给定元提示，I生成一个分析，包含解决目标任务所需的关键推理逻辑，无论实例（问题）如何。例如，在图2（顶部）中，生成的分析指出，需要构建一个真实性地图并通过处理声明来更新它，以解决任务，即谎言之网。这一步引导I专注于所有实例共享的推理过程，这在制作任务级提示时至关重要。
步骤3：根据分析生成伪代码提示。接下来，基于分析，I以伪代码的形式编写了一个提示P，它分解了解决目标任务所需的必要推理步骤。我们选择使用伪代码格式而不是自然语言计划的形式（Kojima等人，2022; Wang等人，2023），主要有两个原因：（1）它在描述任务背后的逻辑时的效率（例如，避免通过循环使用重复的指令），以及（2）通过print()语句中的参数和代码执行位置来指导何时生成理由。例如，在图2中，P包含语句print(f”{person1} says {person2} {action}. {person1} tells the truth: {truth dict[person1]}”），它指导推理LM在执行P的过程中生成一个理由，这有助于跟踪包含每个人真实性的真值图。
2.2 EXECUTE：为实例模拟伪代码提示的执行
然后，推理LM R使用生成的伪代码提示P进行推理，将P中的逻辑定制到给定实例。遵循Wei等人（2022）的方法，我们通过指示LM明确生成中间推理步骤（称为思维链（CoT）推理）来最大化LM的推理能力。R被指示不仅预测代码的最终输出结果，还预测中间执行输出作为理由。具体来说，R通过模拟P的执行过程来预测伪代码的输出列表O = {o1, o2, ..., ok}，其中oi表示来自print()语句的第i个系统输出，{o1}k−1 1是通往最终答案ok的CoT理由。我们假设跟踪中间执行结果将有助于R在代码执行过程中跟踪变量的状态变化。我们通过系统消息“生成代码的所有预期输出（来自所有print()函数）”来使R模仿编译器的行为。给定问题的最终答案以“print("Final answer:{answer}")”命令作为最后一个系统输出ok输出。
3. 实验评估
技术实验结果总结：
在七个算法推理任务上的实验结果显示，THINK-AND-EXECUTE框架在零样本设置下取得了优于多个强基线方法的性能。
研究表明，伪代码提示可以有效地转移到小型语言模型上，提升其推理能力。
与自然语言计划相比，伪代码在指导模型推理方面更为有效。
我们从Big-Bench Hard（Suzgun等人，2022）中筛选了七个算法推理任务。这些任务专门设计用来衡量大型语言模型（LLMs）的逐步推理能力。我们在零次设置下评估模型性能，即提示中不提供示范。
我们考虑以下基线：（1）直接提示：直接预测答案，不生成任何理由。（2）零次CoT（Kojima等人，2022）：在LLMs被唤起生成答案之前的“让我们一步步思考”的设置。（3）零次PoT（Chen等人，2023）：LLM生成特定于实例的Python代码，可以与Python解释器一起执行。然后，执行结果被用作最终答案。（4）NL规划：THINK-AND-EXECUTE的一个变体，其中任务级指令是用自然语言表达的，而不是伪代码。
对于推理LM R，我们采用了GPT-3.5-Turbo（OpenAI，2023），它在各种推理基准和代码生成任务中表现出强大的性能（Zellers等人，2019；Cobbe等人，2021；Muennighoff等人，2024），以及CodeLlama的7B和13B版本（Roziere等人，2023），它们是在代码和自然语言语料库上训练的，并进一步微调以遵循自然语言指令。至于指导LM I，我们选择GPT-3.5-Turbo。
3.1 THINK-AND-EXECUTE提高了算法推理能力
我们首先将我们的框架与直接提示和零次CoT Kojima等人（2022）进行比较（表1）。我们发现零次CoT比直接提示平均提高了11.1%，这表明零次CoT是一个强大的基线。然而，我们的THINK-AND-EXECUTE无论模型大小如何，都显著优于它们，这表明明确生成计划是提高LLM推理能力的有效方法，而不仅仅是鼓励LLM生成它们的中间推理步骤。
3.2 任务级伪代码提示比特定于实例的Python代码对更广泛的算法推理任务有益
在表1中，PoT在某些任务上比直接提示（例如，导航；追踪洗牌目标）显示出性能增益，这些增益是通过为每个实例生成特定Python代码并使用相应的解释器输出作为答案来实现的。然而，这种改进很难推广到所有任务，例如，在Dyck语言和时间序列中，GPT-3.5-Turbo的准确率仅为0.4%。相比之下，使用GPT-3.5-Turbo的THINK-AND-EXECUTE在所有任务中都优于PoT和直接提示。这表明使用伪代码制定任务级策略并将其应用于每个实例，可以比生成特定于实例的Python代码更广泛地提高LLM的算法推理能力。
3.3 由LLM发现的逻辑可以转移到SLMs
我们进一步探索由LLM（即作为指导者的GPT-3.5-Turbo）编写的伪代码提示是否可以应用于较小的LMs：CodeLlama系列。当应用由GPT-3.5-Turbo生成的伪代码提示时，CodeLlama-7B和-13B显著优于直接提示。此外，使用CodeLlama-13B的THINK-AND-EXECUTE显示出与使用PoT和直接提示的GPT-3.5-Turbo相当的性能。
3.4 伪代码比自然语言更好地描述了解决任务的逻辑
我们还将我们的方法与自然语言规划进行了比较，自然语言规划是我们的一种变体，使用自然语言而不是伪代码编写任务级指令。实际上，我们提供了人工编写的自然语言计划，其中包含与元提示中的P相似的信息量，并使用它为给定任务生成任务级自然语言计划。令人惊讶的是，尽管LMs被微调以遵循自然语言指令，但我们发现任务级伪代码提示可以比NL计划更提高它们的性能（表1）。
3.5 消融研究
伪代码提示的组成部分。我们对伪代码提示的每个组成部分进行了消融研究。为此，我们准备了四种类型的伪代码提示：（1）人工编写的伪代码；（2）没有注释和语义的人工编写提示，通过删除解释代码的注释并用无意义的字母（如X、Y和Z）替换变量名；（3）带有for循环的人工编写提示；（4）带有中间print()语句的人工编写提示。结果如图3所示。当应用没有注释和语义的提示时，模型性能显著下降，特别是在时间序列中。这意味着语义在指导LLMs应用发现的逻辑并相应地进行推理中起着重要作用。此外，我们发现使用print()打印中间执行步骤对于推理至关重要，这与Wei等人（2022）的发现一致。
在生成伪代码提示之前生成分析。表2显示了在没有进行分析的情况下生成伪代码提示时模型性能显著下降。这表明明确生成任务分析可以引出更好的伪代码提示，其中包含解决任务所需的必要逻辑。
3.6 与其他基线的比较
我们进一步将THINK-AND-EXECUTE与另外三个基线进行比较：（1）Plan-and-Solve（Wang等人，2023），其中一个LLM依次为给定实例生成自然语言计划，根据计划进行逐步推理，并得出最终答案；（2）Chain-of-Code（Li等人，2023），其中Python代码作为中间推理步骤的一部分为给定实例生成；（3）Self-Discover（Zhou等人，2024），一项并行工作，在推理实例之前设计了一个任务级推理结构的JSON格式。首先，如表3（左）所示，我们发现THINK-AND-EXECUTE在准确性方面大大优于Plan-and-Solve和Chain-of-Code。其次，虽然Self-Discover也采用了任务级指令，但在表3（右）中，我们发现使用GPT-4的THINK-AND-EXECUTE在伪代码提示方面表现更好（Achiam等人，2023）。这些发现表明，生成（1）任务级指令和（2）伪代码可以更好地表示解决任务所需的逻辑，并有益于LLM的算法能力。
4. 实验分析
我们通过实验来回答以下研究问题：
RQ1: 任务级的伪代码是否比特定于实例的伪代码更有帮助？
RQ2: 代码预训练是否提高了推理能力？
RQ3: THINK-AND-EXECUTE发现的逻辑与人类编写的逻辑相比如何？
4.1 在伪代码中实现底层逻辑比特定于实例的逻辑更有效（RQ1）
我们进行了分析，以检查THINK-AND-EXECUTE的改进是否归因于我们选择的任务级指令格式，即伪代码。我们将THINKAND-EXECUTE与一项并行工作Chain-of-Code（CoC）（Li等人，2023）进行了比较。在表3中，THINK-AND-EXECUTE优于CoC，平均得分提高了约2倍。THINK-AND-EXECUTE与CoC之间的主要区别在于，我们使用的伪代码是为了表达任务实例之间共享的逻辑，而CoC将伪代码作为解决给定实例的部分中间推理步骤。因此，结果表明，将伪代码用于生成任务级指令而不是仅将它们用作理由的一部分，具有优势。
4.2 THINK-AND-EXECUTE需要代码知识（RQ2）
为了了解SLMs是否在代码语料库的预训练中获得了理解任务级逻辑的能力，我们比较了使用THINK-AND-EXECUTE的CodeLlama-13B与Llama-13B的性能。在图4中，CodeLlama-13B在所有任务中都显示出比Llama-13B更好的推理能力。这些结果表明，使用THINK-AND-EXECUTE的改进可能取决于通过预训练代码语料库获得的代码知识。编写代码通常涉及理解给定问题背后的逻辑，并期望代码的执行结果，这类似于THINK-AND-EXECUTE的推理过程。
4.3 THINK-AND-EXECUTE可以生成与人类相当的逻辑（RQ3）
为了衡量LLMs在辨别任务底层逻辑的能力，我们将THINKAND-EXECUTE与人工编写的伪代码提示进行了比较。结果如表4所示。使用GPT-3.5-Turbo作为推理者的THINKAND-EXECUTE在准确性方面的得分为60.4%，优于人工编写的P（准确率为55.7%）。特别是在导航和追踪洗牌目标的任务中，由THINK-AND-EXECUTE生成的伪代码提示引出了更好的性能。当采用CodeLlama-7B和-13B作为推理者时，这也成立，进一步表明我们的THINK步骤比人类编写者更有效。
4.4 LLMs的能力对THINK-AND-EXECUTE的影响
在考察LLMs的能力在我们的框架内的影响时，我们研究了推理器和指导者组件对性能的影响，如表5所示。显著的是，当使用GPT-3.5-Turbo作为推理者时，观察到更高的准确率得分，相比之下，使用CodeLlama-13B和CodeLlama-34B时得分较低。此外，指导者的有效性也起着关键作用，GPT-3.5-Turbo在所有配置中展示了最高的准确率得分。这些结果强调了推理者和指导者组件在提高THINK-AND-EXECUTE性能中的重要性。
5. 结论
本文提出了THINK-AND-EXECUTE思维模式。研究表明，该框架通过将算法推理任务的逻辑用伪代码表达，并模拟执行这些伪代码，显著提高了大型语言模型在算法推理任务上的表现。与现有的推理方法相比，THINK-AND-EXECUTE能够更好地发现并应用任务级逻辑，从而提升了模型的推理能力。此外，研究还发现，伪代码在指导模型推理方面比自然语言更有效，即使模型是被训练来遵循自然语言指令的。最后，论文指出，该框架不仅可以提高大型语言模型的性能，还可以通过伪代码提示来增强小型语言模型的推理能力。这些发现为未来的研究提供了新的方向，即探索如何更有效地利用伪代码和其他编程结构来提升语言模型在更广泛任务上的性能。
论文信息：
论文：语言模型作为编译器：通过模拟伪代码执行来提高语言模型中的算法推理
Language Models as Compilers: Simulating Pseudocode Execution Improves Algorithmic Reasoning in Language Models作者：Hyungjoo Chae1, Yeonghyeon Kim1, Seungone Kim2, Kai Tzu-iunn Ong1, Beong-woo Kwak1, Moohyeon Kim1, Seonghwan Kim1, Taeyoon Kwon1, Jiwan Chung1, Youngjae Yu1, Jinyoung Yeo1
1延世大学 2韩国科学技术院 AI {mapoout, jinyeo}@yonsei.ac.kr
连接：https://arxiv.org/abs/2404.02575
