[论文] FrugalEvo: Towards Cost-Aware LLM-Guided Program Evolution

论文概要

研究领域: NLP 作者: Hui Chen, Xuan Qi, James Xu Zhao, Zhaopeng Feng, Shilong Liu, Kuang Xu, Pang Wei Koh, Bryan Hooi 发布时间: 2026-10-02 arXiv: 2610.03675

中文摘要

LLM 引导的进化方法（如 AlphaEvolve）已成为解决计算优化难题的有力工具。然而，先前工作通常在固定迭代次数内优化性能增益。我们认为实际优化应最大化单位成本的增益。为此，我们提出 FrugalEvo——一个成本感知的进化框架，其中更强但更贵的 LLM 探索解题策略，更便宜的 LLM 实现策略并迭代优化代码。我们还设计了缓存高效的进化过程，通过 harness 和提示词设计最大化不同进化步骤间的前缀共享，提高缓存复用。为在固定成本预算内衡量解的质量，我们引入预算感知曲线下面积（BA-AUC）——定义为最优评估分数曲线在累计 LLM 成本下的面积，直至预算上限。在 10 个数学和系统优化任务上，FrugalEvo 在最终解质量上匹配或超越最先进水平基线（包括 OpenEvolve、ShinkaEvolve、AdaEvolve 和 EvoX），在 9 个任务上取得更高 BA-AUC，在 ALE-Bench-Lite 的 10 个算法优化任务上也取得更高平均性能。值得注意的是，在圆形填充问题上，FrugalEvo 使用 GPT-5.6 Terra 和 Luna 仅花费 1.68 美元、使用 GLM-5.3 及其 Flash 变体仅花费 0.55 美元，就达到新的最先进水平，匹配或超越所有基线——包括 CORAL 和 SwarmResearch 等多智能体方法，后者平均花费约 50 美元。

原文摘要

LLM-guided evolutionary methods, such as AlphaEvolve, have emerged as powerful approaches for challenging computational optimization problems, such as circle packing. However, prior work typically optimizes performance gain over a fixed number of iterations. We argue that practical optimization should maximize gain per unit cost. To this end, we propose FrugalEvo, a cost-aware evolutionary framework where a stronger, higher-cost LLM explores solution strategies, and a cheaper LLM implements them and iteratively refines the resulting code. We also design a cache-efficient evolution process, where our harness and prompts maximize the sharing of prefixes across different evolution steps, to improve cache reuse. To measure solution quality throughout a fixed cost budget, we introduce Budget-Aw...

#论文 #arXiv #NLP #小凯