Search-Based LLMs for Code Optimization
作者: Shuzheng Gao, Cuiyun Gao, Wenchao Gu, Michael Lyu
分类: cs.SE, cs.AI, cs.CL
发布日期: 2024-08-22
备注: Accepted by 2025 IEEE/ACM 47th International Conference on Software Engineering (ICSE'25)
💡 一句话要点
提出基于搜索的LLM框架SBLLM，用于迭代优化代码并发现改进的优化方法。
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 代码优化 大型语言模型 搜索算法 进化算法 程序优化 自动化重构 性能提升
📋 核心要点
- 现有代码优化方法，如一步生成式LLM，难以捕获复杂优化，且知识注入不精确，导致优化不足。
- SBLLM框架从搜索角度建模代码优化，通过迭代改进和发现，提升优化效果。
- SBLLM集成了执行评估、优化模式检索和思维链提示，协同优化代码，提升优化性能。
📝 摘要（中文）
开发者编写的代码通常存在效率问题和性能缺陷。为了解决这些问题，代码自动重构优化方法的研究变得至关重要。早期的代码优化研究采用基于规则的方法，专注于特定的效率问题，但这种方法耗费人力且覆盖率低。最近的研究将此任务视为序列生成问题，并借助大型语言模型（LLM）等深度学习（DL）技术。这些方法通常提示LLM直接生成优化后的代码。然而，这种一步到位的生成模式难以获得最优解。首先，组合优化等复杂优化方法难以被LLM捕获。其次，一步生成模式难以将有效代码优化所需的知识精确地注入到LLM中，导致代码优化不足。为了解决这些问题，我们提出从搜索的角度对该任务进行建模，并提出了一个名为SBLLM的基于搜索的LLM框架，该框架能够迭代改进并发现改进的优化方法。SBLLM将LLM与进化搜索协同集成，包含三个关键组件：1）基于执行的代表性样本选择部分，用于评估每个现有优化代码的适应度，并优先考虑有希望的代码，以引导生成改进的代码；2）自适应优化模式检索部分，将有针对性的优化模式注入到模型中，以指导LLM纠正并逐步增强其优化方法；3）受遗传算子启发的思维链提示部分，帮助LLM组合不同的优化方法并生成改进的优化方法。
🔬 方法详解
问题定义：论文旨在解决现有基于LLM的代码优化方法难以达到最优解的问题。现有方法，特别是one-step generation的方法，无法有效处理复杂的组合优化，并且难以将代码优化所需的知识精确注入LLM中，导致优化效果不佳。
核心思路：论文的核心思路是将代码优化问题建模为一个搜索问题，通过迭代地改进和发现更优的优化方法来解决上述问题。这种思路借鉴了进化算法的思想，通过不断地评估和选择更优的解，逐步逼近全局最优解。
技术框架：SBLLM框架包含三个主要模块：1) 执行评估的代表性样本选择：该模块负责评估现有优化代码的适应度，并选择有潜力的代码作为种子，引导后续的优化过程。2) 自适应优化模式检索：该模块将有针对性的优化模式注入到LLM中，指导LLM纠正和增强其优化方法。3) 遗传算子启发的思维链提示：该模块借鉴遗传算法中的交叉和变异操作，帮助LLM组合不同的优化方法，并生成新的优化方法。整个框架通过迭代执行这三个模块，不断改进代码的优化效果。
关键创新：该论文的关键创新在于将搜索算法与LLM相结合，用于代码优化。与传统的one-step generation方法不同，SBLLM通过迭代搜索的方式，能够更好地处理复杂的优化问题，并且能够更有效地利用LLM的知识。此外，自适应优化模式检索和遗传算子启发的思维链提示也是该论文的创新点，它们能够帮助LLM更好地理解和应用代码优化的知识。
关键设计：执行评估部分使用基于执行的测试用例来评估代码的性能，例如运行时间和内存占用。自适应优化模式检索部分可能使用知识图谱或者代码模式库来存储和检索优化模式。遗传算子启发的思维链提示部分可能使用特定的prompt模板来引导LLM生成新的优化方法，例如“首先，分析代码的瓶颈；然后，应用X优化方法；最后，验证优化效果”。具体的参数设置和损失函数等细节在论文中可能没有详细描述，需要进一步查阅论文原文。
🖼️ 关键图片
📊 实验亮点
论文提出的SBLLM框架通过迭代搜索和优化，在代码优化任务上取得了显著的性能提升。具体的实验结果（例如，在特定数据集上的性能指标提升百分比）需要在论文中查找。与直接使用LLM进行一步生成相比，SBLLM能够更有效地优化代码，尤其是在处理复杂的优化问题时。
🎯 应用场景
该研究成果可应用于自动化代码优化、软件性能提升、编译器优化等领域。通过SBLLM框架，开发者可以更高效地优化代码，减少人工干预，提升软件的性能和可靠性。未来，该方法有望集成到IDE或CI/CD流程中，实现代码的持续优化。
📄 摘要（原文）
The code written by developers usually suffers from efficiency problems and contain various performance bugs. These inefficiencies necessitate the research of automated refactoring methods for code optimization. Early research in code optimization employs rule-based methods and focuses on specific inefficiency issues, which are labor-intensive and suffer from the low coverage issue. Recent work regards the task as a sequence generation problem, and resorts to deep learning (DL) techniques such as large language models (LLMs). These methods typically prompt LLMs to directly generate optimized code. Although these methods show state-of-the-art performance, such one-step generation paradigm is hard to achieve an optimal solution. First, complex optimization methods such as combinatorial ones are hard to be captured by LLMs. Second, the one-step generation paradigm poses challenge in precisely infusing the knowledge required for effective code optimization within LLMs, resulting in under-optimized code.To address these problems, we propose to model this task from the search perspective, and propose a search-based LLMs framework named SBLLM that enables iterative refinement and discovery of improved optimization methods. SBLLM synergistically integrate LLMs with evolutionary search and consists of three key components: 1) an execution-based representative sample selection part that evaluates the fitness of each existing optimized code and prioritizes promising ones to pilot the generation of improved code; 2) an adaptive optimization pattern retrieval part that infuses targeted optimization patterns into the model for guiding LLMs towards rectifying and progressively enhancing their optimization methods; and 3) a genetic operator-inspired chain-of-thought prompting part that aids LLMs in combining different optimization methods and generating improved optimization methods.