一句话：提出 AMaze 框架，自动优化 DSL 以加速语法引导程序合成，最高取得 4.35× 加速。
语法引导的程序合成依赖领域特定语言（DSL）约束搜索空间以提升效率，但人工设计最优 DSL 困难且常导致性能次优。本文提出 AMaze，一个自动优化 DSL 以加速合成的框架。AMaze 迭代地精化 DSL：它识别关键的“特征组件”（feature components），这些组件的枚举排名与合成时间相关；随后利用基于动态规划的算法计算特征组件的枚举排名，并基于这些排名训练机器学习模型来估计合成代价，从而避免直接调用合成器带来的高昂计算开销。作者在 DryadSynth、Duet、Polygen 与 EUsolver 等当前先进合成器上跨多个领域评估 AMaze。实验结果表明，AMaze 在保持表达力的同时最高实现 4.35× 加速，有效降低合成时间。
Syntax-guided program synthesis relies on domain-specific languages (DSLs) to constrain the search space and improve efficiency. However, manually designing optimal DSLs is challenging and often results in suboptimal performance. In this paper, we propose AMaze , a novel framework that automatically optimizes DSLs to accelerate synthesis. AMaze iteratively refines a DSL by identifying key program fragments, termed feature components, whose enumeration ranks correlate with synthesis time. Using a dynamic-programming-based algorithm to calculate enumeration ranks of feature components and a machine learning model based on them, AMaze estimates synthesis cost instead of directly invoking the synthesizer, which is impractical due to high computational cost. We evaluate AMaze on state-of-the-art synthesizers, including DryadSynth , Duet , Polygen , and EUsolver , across multiple domains. Empirical results demonstrate that AMaze achieves up to 4.35× speedup, effectively reducing synthesis time while maintaining expressiveness.
@article{YeJXZ26,
title = {Accelerating Syntax-Guided Program Synthesis by Optimizing Domain-Specific Languages},
author = {Zhentao Ye and Ruyi Ji and Yingfei Xiong and Xin Zhang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {POPL},
year = {2026},
doi = {10.1145/3776679}
}