Lune

POPL2026Top-tier venue

Accelerating Syntax-Guided Program Synthesis by Optimizing Domain-Specific Languages

Zhentao Ye, Ruyi Ji, Yingfei Xiong, Xin Zhang

Abstract

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • babble: Learning Better Abstractions with E-Graphs and Anti-unification cites DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning
  • babble: Learning Better Abstractions with E-Graphs and Anti-unification cites Top-Down Synthesis for Library Learning
  • Top-Down Synthesis for Library Learning cites babble: Learning Better Abstractions with E-Graphs and Anti-unification
  • Top-Down Synthesis for Library Learning cites Learning Differentiable Programs with Admissible Neural Heuristics
  • Top-Down Synthesis for Library Learning cites DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on11

  1. DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learningKevin Ellis, Catherine Wong, Maxwell I. Nye, Mathias Sablé-Meyer et al.PLDI 2021 · 97 citations
  2. Learning Differentiable Programs with Admissible Neural HeuristicsAmeesh Shah, Eric Zhan, Jennifer J. Sun, Abhinav Verma et al.NeurIPS 2020 · 56 citations
  3. babble: Learning Better Abstractions with E-Graphs and Anti-unificationDavid Cao, Rose Kunkel, Chandrakana Nandi, Max Willsey et al.POPL 2023 · 38 citations
  4. Combining the top-down propagation and bottom-up enumeration for inductive program synthesisWoosuk LeePOPL 2021 · 34 citations
  5. Top-Down Synthesis for Library LearningMatthew Bowers, Theo X. Olausson, Lionel Wong, Gabriel Grand et al.POPL 2023 · 32 citations

Related papers

  1. Guided Tensor LiftingYixuan Li, José Wesley de Souza Magalhães, Alexander Brauckmann, Michael F. P. O'Boyle et al.PLDI 2025 · 4 citations
  2. Just-in-time learning for bottom-up enumerative synthesisShraddha Barke, Hila Peleg, Nadia PolikarpovaOOPSLA 2020 · 33 citations
  3. Presynthesis: Towards Scaling Up Program Synthesis with Finer-Grained Abstract SemanticsRui Dong, Qingyue Wu, Danny Ding, Zheng Guo et al.PLDI 2026
  4. Optimal Program Synthesis via Abstract InterpretationStephen Mell, Steve Zdancewic, Osbert BastaniPOPL 2024 · 6 citations
  5. Automating Pruning in Top-Down Enumeration for Program Synthesis Problems with Monotonic SemanticsKeith J. C. Johnson, Rahul Krishnan, Thomas W. Reps, Loris D'AntoniOOPSLA 2024 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines