Command Palette
Search for a command to run...
自动化发现不存在普遍最优的搜索框架
自动化发现不存在普遍最优的搜索框架
Akshat Gupta Jermaine Lei Alexander Lu Gopala Anumanchipalli Leshem Choshen
摘要
OpenEvolve 和 TTT-Discover 等自主发现系统常被用作通用搜索框架。然而，在实践中，这些系统是将关于存档、父代选择、探索策略和预算分配的多种设计选择组合成单一方案的复合系统。由于发现运行成本高昂且本质上具有随机性，现有框架的比较往往基于过少的独立试验，难以将关键的方法改进与运行间的方差区分开来。我们系统地将 OpenEvolve 风格的进化搜索和 TTT-Discover 搜索框架分解为其构成组件，并在 12 个模型–问题对上，利用超过 310 万次大语言模型（LLM）运行和重复试验统计分析，系统评估了 30 种预算匹配的框架。结果表明，发现框架存在泛化问题：在所评估的模型–问题对中，没有一种固定框架能可靠地表现出优越性，且 OpenEvolve 的变体通常不如更简单的替代方案。因此，框架选择更应被视为一种超参数，而非通用配方，并应针对具体问题和底层模型进行定制。我们还发现，早期的发现进展能预测最终性能，并利用这一特性设计了一个预算匹配的自适应分配实验：该实验启动多个框架，剪枝表现不佳的部分运行，并将计算资源重新分配给更强的存活者，其性能优于承诺使用随机采样的固定框架和非自适应的框架集成。这些结果共同表明，应从固定框架选择转向由早期性能引导的在线自适应。我们公开了所有运行池，包括每个模型–问题对的基线零分布，作为可复用的统计基础设施，供未来框架提案进行对比。
一句话总结
在系统性地分解并评估了12个模型–问题对上的30个发现框架，且发现没有一种普遍优越的框架后，来自加州大学伯克利分校、麻省理工学院和MIT-IBM Watson AI Lab的研究人员提出了一种自适应分配方法，利用早期进展剪枝弱运行并重新分配计算资源，其性能优于固定框架和集成方法。
核心贡献
- 本文系统地分解了OpenEvolve和TTT-Discover发现框架的组成组件，并在12个模型–问题对上评估了30个预算匹配的框架变体，使用了超过310万次LLM展开和重复试验统计分析。
- 研究表明，没有一种固定的发现框架能在不同模型和问题上可靠地泛化；框架选择更适合被视为一个依赖模型和问题的超参数，更简单的替代方案往往优于OpenEvolve风格的配置。
- 该工作提出了一种自适应框架集成，利用早期运行进展剪枝表现不佳的框架，并将计算资源重新分配给更强的幸存者，在平均最终性能上相较于单一固定框架和非自适应集成均取得了提升。
引言
作者研究了LLM引导的自主发现系统，这类系统迭代地生成、评估并改进候选解决方案。在这些系统中，一个框架控制存档构建、父代选择、探索和预算分配，但先前的工作仅通过少量试验评估复合框架，无法将有意义的设计选择与运行间方差区分开。作者在310万次展开和12个模型–问题对上进行了大规模、统计控制的评估，评估了30个预算匹配的框架，发现没有一种单一的固定框架能可靠地跨设置迁移。他们随后表明，将框架选择视为一个在线的、依赖问题的超参数——利用部分运行反馈进行剪枝和重新分配计算——能够提升最终性能，优于预先承诺单一框架的做法。
方法
作者开发了一个统一的程序发现框架，将两种流行的搜索框架统一起来，并通过在线预算分配策略进行扩展。该方法从贪婪的顺序最佳N基线开始，每次迭代从历史记录Ht中选择得分最高的单一程序作为父代：
pt=argx∈HtmaxS(x).这种确定性的top-1选择，pt∼Et1，生成N个候选子代，经评估后追加到历史记录中。总展开预算固定为B=NT，跨越所有迭代。
从这一基线转向OpenEvolve框架涉及四个递进的松弛：将top-1存档替换为top-K存档EtK；引入epsilon-贪婪探索，偶尔从完整历史Ht中采样；通过减少N并增加T将预算从广度转向深度；最后加入灵感采样、MAP-Elites多样性维护以及带交叉的多岛进化。为了推导TTT-Discover框架，评分函数被转换为以程序为根的子树的估计值，基于访问次数添加了上置信界（UCT）探索奖励，并将该奖励修改为带有先验估计的PUCT规则。TTT-Discover还在每个时间步采样多个父代，而非单一父代。
由于最优固定框架因模型–问题对而异，作者引入了一种在线分配策略，利用中间反馈动态选择框架。自适应框架集成启动多个框架配置，推进到一个或多个检查点（例如，完整运行的25%、50%、75%），根据迄今为止观察到的最佳评估分数对部分运行进行排序，剪枝较弱的运行，并将剩余计算资源用于幸存者。总预算固定为Be=5个完整运行等价，与标准的五选一评估相匹配。单阶段策略满足预算约束
mq+s(1−q)≤Be,其中m个部分运行被推进到检查点q，s个幸存者完成运行。多阶段剪枝使用多个检查点0=q0<q1<⋯<qL=1，在阶段ℓ有mℓ个活跃配置，从而得到
ℓ=1∑Lmℓ(qℓ−qℓ−1)≤Be.最强的策略在早期检查点从广泛的组合开始，并随着更丰富的反馈可用而逐步集中预算。例如，一个三阶段12→5→2→1调度在完整运行的25%、50%和75%处进行剪枝，在相同计算预算下优于固定框架承诺和未剪枝的框架集成。
实验
评估在固定展开预算下，比较了四个LLM和三个数学发现任务上的搜索框架。配对间和跨配对的显著性检验表明，没有一种单一的固定框架能始终优于简单的顺序BoN基线，观察到的最强框架因模型–问题对而异。早期运行性能被证明可预测最终结果，而启动多个框架并根据中间反馈进行剪枝的自适应在线分配策略，产生了高于单一框架承诺和未剪枝框架组合的平均性能。
在五个完整运行等价的固定计算预算下，启动多个配置、评估部分进展并剪枝较弱运行的自适应在线框架分配策略始终优于固定策略。最强的自适应调度——一种三阶段剪枝方法——通过从广泛的组合开始并逐步将资源集中到最有希望的候选者上，将平均最终得分从84.35%提高到85.75%。这表明早期部分运行反馈能有效引导计算资源流向更好的解决方案。在平均最终得分上，每种自适应剪枝调度都超过了单一框架基线、未剪枝的框架组合和顺序BoN参考。表现最佳的策略（在完整运行的25%、50%和75%处剪枝）取得了最高的平均分85.75%，并在12个模型–问题对中的11个上优于未剪枝的组合。
在五个完整运行等价的固定计算预算下，启动多个配置、评估部分进展并剪枝较弱运行的自适应在线分配策略始终优于静态策略。一种三阶段剪枝调度从广泛的组合开始，并逐步将资源集中到最有希望的候选者上，提高了平均最终得分，表明早期部分运行反馈能有效引导计算资源流向更好的解决方案。所有自适应剪枝调度均超过了单一框架基线、未剪枝的框架组合和顺序BoN参考，其中最佳策略（在完整运行的25%、50%和75%处剪枝）在12个模型–问题对中的11个上优于未剪枝的组合。