提出常延迟最优优先搜索算法，加速程序合成效率。
EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis
- 采用常延迟机制，输出程序间计算开销恒定。
- 在两个经典领域中显著优于先前算法。
- 适合需要快速生成程序的自动化开发场景。
程序合成常需在庞大程序空间中进行组合搜索以找到满足规范的程序。为应对搜索空间爆炸问题，以往工作引入概率和神经方法，通过启发式代价函数引导搜索。最优优先搜索算法能严格按代价函数顺序搜索，大幅减少需探索的空间。本文提出新算法EcoSearch，是首个针对预生成代价函数的常延迟算法：输出两个程序之间的计算量恒定，且不随时间增长。这一关键特性带来显著加速效果，实验显示EcoSearch在两个经典任务上均超越先前方法。
原文摘要 · Abstract (English)
Many approaches to program synthesis perform a combinatorial search within a large space of programs to find one that satisfies a given specification. To tame the search space blowup, previous works introduced probabilistic and neural approaches to guide this combinatorial search by inducing heuristic cost functions. Best-first search algorithms ensure to search in the exact order induced by the cost function, significantly reducing the portion of the program space to be explored. We present a new best-first search algorithm called EcoSearch, which is the first constant-delay algorithm for pre-generation cost function: the amount of compute required between outputting two programs is constant, and in particular does not increase over time. This key property yields important speedups: we observe that EcoSearch outperforms its predecessors on two classic domains.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。