Planning In Natural Language Improves LLM Search For Code Generation

📄 arXiv: 2409.03733v2 📥 PDF

作者: Evan Wang, Federico Cassano, Catherine Wu, Yunfeng Bai, Will Song, Vaskar Nath, Ziwen Han, Sean Hendryx, Summer Yue, Hugh Zhang

分类: cs.LG, cs.AI, cs.CL

发布日期: 2024-09-05 (更新: 2024-10-18)

🔗 代码/项目: GITHUB

💡 一句话要点

PlanSearch：通过自然语言规划提升LLM代码生成搜索效率

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 代码生成 大型语言模型 自然语言规划 搜索算法 多样性 LiveCodeBench

📋 核心要点

  1. 现有LLM代码生成搜索方法缺乏输出多样性，导致搜索效率低，模型易重复生成相似错误结果。
  2. PlanSearch通过生成自然语言的问题解决方案规划，并在规划空间中搜索，增加潜在解决方案的多样性。
  3. 实验表明，PlanSearch在多个代码生成基准上显著提升性能，尤其是在LiveCodeBench上取得了SOTA结果。

📝 摘要（中文）

本文提出PlanSearch，一种新颖的搜索算法，旨在通过搜索自然语言形式的问题解决方案规划来提高大型语言模型（LLM）的代码生成能力。研究发现，LLM输出的多样性不足会导致搜索效率低下，因为模型会重复采样相似但错误的生成结果。PlanSearch通过生成关于问题的多样化观察，并利用这些观察构建解决方案规划来缓解这个问题。在HumanEval+、MBPP+和LiveCodeBench（一个无污染的竞争性编程基准）上的实验结果表明，PlanSearch表现出色。在Claude 3.5 Sonnet上使用PlanSearch，在LiveCodeBench上实现了77.0%的pass@200，超过了不使用搜索的最佳成绩（pass@1 = 41.4%）和使用标准重复采样的成绩（pass@200 = 60.6%）。此外，研究表明，在所有模型、搜索算法和基准测试中，搜索带来的性能提升可以直接预测为生成想法的多样性的函数。

🔬 方法详解

问题定义：现有的大型语言模型在代码生成任务中，即使通过增加推理计算资源进行搜索，也难以获得显著的性能提升。一个关键的痛点在于，模型生成的代码方案往往高度相似，缺乏多样性，导致搜索过程效率低下，容易陷入局部最优解。模型倾向于重复生成相似但错误的解决方案，无法充分探索潜在的解空间。

核心思路：PlanSearch的核心思路是将代码生成问题分解为自然语言的规划过程。与其直接搜索代码解决方案，不如先让LLM生成关于问题的各种观察和理解，然后基于这些观察构建解决问题的自然语言规划。通过在规划空间中搜索，可以探索更多样化的解决方案，从而提高搜索效率和最终的代码生成质量。

技术框架：PlanSearch的整体流程如下：1) 问题观察生成：LLM首先生成关于问题的多个观察，这些观察可以包括对问题描述的理解、对输入输出示例的分析、以及对潜在解决方案的初步想法。2) 规划构建：基于生成的观察，LLM构建解决问题的自然语言规划。每个规划代表一种可能的解决方案路径。3) 代码生成：对于每个规划，LLM生成相应的代码实现。4) 搜索与评估：对生成的代码进行评估，例如通过运行测试用例。根据评估结果，调整搜索策略，选择更有希望的规划进行进一步探索。

关键创新：PlanSearch最重要的创新在于将搜索空间从代码空间转移到自然语言规划空间。这种转变使得搜索过程能够探索更多样化的解决方案，避免陷入局部最优解。与直接在代码空间中搜索相比，自然语言规划更易于理解和修改，从而提高了搜索的效率和灵活性。

关键设计：PlanSearch的关键设计包括：1) 观察生成策略：如何引导LLM生成多样化的观察？可以使用不同的prompting技巧，例如鼓励模型从不同的角度思考问题，或者提供不同的约束条件。2) 规划构建方法：如何将观察转化为有效的规划？可以使用不同的规划策略，例如基于规则的规划、基于模板的规划、或者基于LLM的规划。3) 搜索算法：如何有效地搜索规划空间？可以使用不同的搜索算法，例如贪心搜索、束搜索、或者蒙特卡洛树搜索。4) 评估函数：如何评估生成的代码的质量？可以使用不同的评估指标，例如测试用例通过率、代码复杂度、或者代码可读性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

PlanSearch在LiveCodeBench上取得了显著的性能提升，在Claude 3.5 Sonnet模型上实现了77.0%的pass@200，超过了不使用搜索的最佳成绩（41.4%）和使用标准重复采样的成绩（60.6%）。该结果表明，通过搜索自然语言规划，可以显著提高LLM的代码生成能力。此外，研究还发现，搜索带来的性能提升与生成想法的多样性直接相关，这为进一步优化搜索算法提供了理论依据。

🎯 应用场景

PlanSearch具有广泛的应用前景，可应用于自动化代码生成、软件开发辅助、智能编程教育等领域。通过提高代码生成的多样性和准确性，PlanSearch可以帮助开发者更高效地完成编程任务，降低开发成本，并促进软件创新。此外，该方法还可以应用于其他需要生成复杂结构化输出的任务，例如自然语言生成、机器人控制等。

📄 摘要（原文）

While scaling training compute has led to remarkable improvements in large language models (LLMs), scaling inference compute has not yet yielded analogous gains. We hypothesize that a core missing component is a lack of diverse LLM outputs, leading to inefficient search due to models repeatedly sampling highly similar, yet incorrect generations. We empirically demonstrate that this lack of diversity can be mitigated by searching over candidate plans for solving a problem in natural language. Based on this insight, we propose PlanSearch, a novel search algorithm which shows strong results across HumanEval+, MBPP+, and LiveCodeBench (a contamination-free benchmark for competitive coding). PlanSearch generates a diverse set of observations about the problem and then uses these observations to construct plans for solving the problem. By searching over plans in natural language rather than directly over code solutions, PlanSearch explores a significantly more diverse range of potential solutions compared to baseline search methods. Using PlanSearch on top of Claude 3.5 Sonnet achieves a state-of-the-art pass@200 of 77.0% on LiveCodeBench, outperforming both the best score achieved without search (pass@1 = 41.4%) and using standard repeated sampling (pass@200 = 60.6%). Finally, we show that, across all models, search algorithms, and benchmarks analyzed, we can accurately predict performance gains due to search as a direct function of the diversity over generated ideas. Code can be found at https://github.com/scaleapi/plansearch.