{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:53:28Z","timestamp":1767920008990,"version":"3.49.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2022YFB4501902"],"award-info":[{"award-number":["2022YFB4501902"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62172017"],"award-info":[{"award-number":["62172017"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["W2411051"],"award-info":[{"award-number":["W2411051"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,1,8]]},"abstract":"<jats:p>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.35X speedup, effectively reducing synthesis time while maintaining expressiveness.<\/jats:p>","DOI":"10.1145\/3776679","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T18:59:43Z","timestamp":1767898783000},"page":"1066-1093","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Accelerating Syntax-Guided Program Synthesis by Optimizing Domain-Specific Languages"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-7164-1465","authenticated-orcid":false,"given":"Zhentao","family":"Ye","sequence":"first","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0150-8629","authenticated-orcid":false,"given":"Ruyi","family":"Ji","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8991-747X","authenticated-orcid":false,"given":"Yingfei","family":"Xiong","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1515-7145","authenticated-orcid":false,"given":"Xin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/fmcad.2013.6679385"},{"key":"e_1_2_1_2_1","unstructured":"Rajeev Alur Dana Fisman Saswat Padhi Rishabh Singh and Abhishek Udupa. 2019. Sygus-comp 2018: Results and analysis. arXiv preprint arXiv:1904.07146 arxiv:1904.07146"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54577-5_18"},{"key":"e_1_2_1_4_1","volume-title":"5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net. arxiv:1611","author":"Balog Matej","year":"2017","unstructured":"Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. 2017. DeepCoder: Learning to Write Programs. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net. arxiv:1611.01989"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_14"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571234"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571207"},{"key":"e_1_2_1_9_1","volume-title":"Seshia","author":"Chan Nicolas","year":"2020","unstructured":"Nicolas Chan, Elizabeth Polgreen, and Sanjit A. Seshia. 2020. Gradient Descent over Metagrammars for Syntax-Guided Synthesis. CoRR, abs\/2007.06677 (2020), arxiv:2007.06677. arxiv:2007.06677"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939785"},{"key":"e_1_2_1_11_1","volume-title":"IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence","author":"Dechter Eyal","year":"2013","unstructured":"Eyal Dechter, Jonathan Malmaud, Ryan P. Adams, and Joshua B. Tenenbaum. 2013. Bootstrap Learning via Modular Concept Discovery. In IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, Francesca Rossi (Ed.). IJCAI\/AAAI, 1302\u20131309."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632913"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454080"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062355"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5860\/choice.27-0936"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","unstructured":"Sumit Gulwani Oleksandr Polozov Rishabh Singh et al. 2017. Program synthesis. Foundations and Trends\u00ae in Programming Languages 4 1-2 (2017) 1\u2013119. https:\/\/doi.org\/10.1561\/2500000010 10.1561\/2500000010","DOI":"10.1561\/2500000010"},{"key":"e_1_2_1_17_1","volume-title":"Cumulative learning in the lambda calculus. Ph. D. Dissertation","author":"Henderson Robert John","unstructured":"Robert John Henderson. 2013. Cumulative learning in the lambda calculus. Ph. D. Dissertation. Imperial College London, UK."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3680410"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3322485"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806833"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428292"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485544"},{"key":"e_1_2_1_23_1","unstructured":"Ashwin Kalyan Abhishek Mohta Oleksandr Polozov Dhruv Batra Prateek Jain and Sumit Gulwani. 2018. Neural-guided deductive search for real-time program synthesis from examples. arXiv preprint arXiv:1804.01186 arxiv:1804.01186"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434335"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3296979.3192410"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.3233\/978-1-61499-419-0-525"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013 (JMLR Workshop and Conference Proceedings","volume":"195","author":"Menon Aditya Krishna","year":"2013","unstructured":"Aditya Krishna Menon, Omer Tamuz, Sumit Gulwani, Butler W. Lampson, and Adam Kalai. 2013. A Machine Learning Framework for Programming by Example. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013 (JMLR Workshop and Conference Proceedings, Vol. 28). JMLR.org, 187\u2013195. https:\/\/proceedings.mlr.press\/v28\/menon13.html"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5522"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/b978-0-934613-64-4.50040-2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-014-5471-y"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10710-008-9073-y"},{"key":"e_1_2_1_32_1","unstructured":"Saswat Padhi. 2019. SyGuS-Comp 2019. https:\/\/sygus.org\/comp\/2019\/ Accessed: 2021-07-09"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25540-4_17"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814310"},{"key":"e_1_2_1_35_1","volume-title":"Learning Differentiable Programs with Admissible Neural Heuristics. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Shah Ameesh","year":"2020","unstructured":"Ameesh Shah, Eric Zhan, Jennifer J. Sun, Abhinav Verma, Yisong Yue, and Swarat Chaudhuri. 2020. Learning Differentiable Programs with Admissible Neural Heuristics. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/342285bb2a8cadef22f667eeb6a63732-Abstract.html"},{"key":"e_1_2_1_36_1","volume-title":"Osbert Bastani, Yewen Pu, Armando Solar-Lezama, and Martin C. Rinard.","author":"Yang Yichen","year":"2021","unstructured":"Yichen Yang, Jeevana Priya Inala, Osbert Bastani, Yewen Pu, Armando Solar-Lezama, and Martin C. Rinard. 2021. Program Synthesis Guided Reinforcement Learning for Partially Observed Environments. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, Marc\u2019Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 29669\u201329683. https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/f7e2b2b75b04175610e5a00c1e221ebb-Abstract.html"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.18653\/V1\/2021.FINDINGS-EMNLP.146"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.17345861"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775058"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3776679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T19:04:22Z","timestamp":1767899062000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3776679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":39,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2026,1,8]]}},"alternative-id":["10.1145\/3776679"],"URL":"https:\/\/doi.org\/10.1145\/3776679","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-07-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}