Accelerating Syntax-Guided Program Synthesis by Optimizing Domain-Specific Languages
summary
AMaze automatically refines DSLs to cut synthesis time by estimating enumeration cost instead of running the solver, computing a feature component rank for solution fragments and using a dynamic‑programming algorithm to get ranks in polynomial time. Evaluated on DryadSynth, Duet, Polygen and EUsolver across benchmarks, AMaze yields up to 4.35X speedup, often shrinking a fragment rank from 3,158 to 58 and enabling hundreds more solved tasks.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:07DSL design challenges
- 2:36DSL refinement impact example
- 4:26Cost of direct DSL evaluation
- 5:10Feature rank as synthesis proxy
- 7:24Validating feature rank
- 9:35Generalizing beyond EOS server
- 10:39AMAze framework phases
- 12:47Efficient rank computation
- 13:31Evaluation setup
- 14:16AMAze accelerates synthesizers
- 15:25Comparison with DSL methods
- 15:46Ablation study
- 16:08Summary
related talks
38mDSLs, Code Generation, and New Domains for Ruby
15mLanguage-Parametric Reference Synthesis
07mNew Ideas: Automated Engineering of Metamorphic Testing Environments for Domain-Specific Languages
48mBenefits of Abstract Modelling using Conjure
28mScooPy: Enhancing Program Synthesis with Nested Example Specifications
13mProgramming with a Read-Eval-Synth Loop
20mEquivalence by Canonicalization for Synthesis-Backed Refactoring
15mProgram Sketching with Live Bidirectional Evaluation