{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:33:53Z","timestamp":1767929633883,"version":"3.49.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["1955457, 1911149, 1943623"],"award-info":[{"award-number":["1955457, 1911149, 1943623"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,11,13]]},"abstract":"<jats:p>A key challenge in program synthesis is the astronomical size of the search space the synthesizer has to explore. In response to this challenge, recent work proposed to guide synthesis using learned probabilistic models. Obtaining such a model, however, might be infeasible for a problem domain where no high-quality training data is available. In this work we introduce an alternative approach to guided program synthesis: instead of training a model ahead of time we show how to bootstrap one just in time, during synthesis, by learning from partial solutions encountered along the way. To make the best use of the model, we also propose a new program enumeration algorithm we dub guided bottom-up search, which extends the efficient bottom-up search with guidance from probabilistic models.<\/jats:p>\n          <jats:p>We implement this approach in a tool called Probe, which targets problems in the popular syntax-guided synthesis (SyGuS) format. We evaluate Probe on benchmarks from the literature and show that it achieves significant performance gains both over unguided bottom-up search and over a state-of-the-art probability-guided synthesizer, which had been trained on a corpus of existing solutions. Moreover, we show that these performance gains do not come at the cost of solution quality: programs generated by Probe are only slightly more verbose than the shortest solutions and perform no unnecessary case-splitting.<\/jats:p>","DOI":"10.1145\/3428295","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T23:40:14Z","timestamp":1606261214000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Just-in-time learning for bottom-up enumerative synthesis"],"prefix":"10.1145","volume":"4","author":[{"given":"Shraddha","family":"Barke","sequence":"first","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hila","family":"Peleg","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"Polikarpova","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2018. Euphony Benchmark Suite. https:\/\/github.com\/wslee\/euphony\/tree\/master\/benchmarks  2018. Euphony Benchmark Suite. https:\/\/github.com\/wslee\/euphony\/tree\/master\/benchmarks"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_67"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Miltiadis Allamanis Earl T Barr Premkumar Devanbu and Charles Sutton. 2018. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR) 51 4 ( 2018 ) 1-37.  Miltiadis Allamanis Earl T Barr Premkumar Devanbu and Charles Sutton. 2018. A survey of machine learning for big code and naturalness. ACM Computing Surveys (CSUR) 51 4 ( 2018 ) 1-37.","DOI":"10.1145\/3212695"},{"key":"e_1_2_2_4_1","volume-title":"Introduction to Machine Learning ( 3 ed.)","author":"Alpaydin Ethem"},{"key":"e_1_2_2_5_1","volume-title":"FMCAD 2013","author":"Alur Rajeev","year":"2013"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Rajeev Alur Dana Fisman Rishabh Singh and Armando Solar-Lezama. 2016. Sygus-comp 2016: results and analysis. arXiv preprint arXiv:1611.07627 ( 2016 ).  Rajeev Alur Dana Fisman Rishabh Singh and Armando Solar-Lezama. 2016. Sygus-comp 2016: results and analysis. arXiv preprint arXiv:1611.07627 ( 2016 ).","DOI":"10.4204\/EPTCS.229.13"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Rajeev Alur Dana Fisman Rishabh Singh and Armando Solar-Lezama. 2017a. Sygus-comp 2017 : Results and analysis. arXiv preprint arXiv:1711.11438 ( 2017 ).  Rajeev Alur Dana Fisman Rishabh Singh and Armando Solar-Lezama. 2017a. Sygus-comp 2017 : Results and analysis. arXiv preprint arXiv:1711.11438 ( 2017 ).","DOI":"10.4204\/EPTCS.260.9"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54577-5_18"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3208071"},{"key":"e_1_2_2_10_1","volume-title":"Deepcoder: Learning to write programs. arXiv preprint arXiv:1611. 01989 ( 2016 ).","author":"Balog Matej","year":"2016"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Shraddha Barke Hila Peleg and Nadia Polikarpova. 2020. Just-in-Time Learning for Bottom-up Enumerative Synthesis. ( 2020 ). https:\/\/shraddhabarke.github.io\/publication\/probe-oopsla  Shraddha Barke Hila Peleg and Nadia Polikarpova. 2020. Just-in-Time Learning for Bottom-up Enumerative Synthesis. ( 2020 ). https:\/\/shraddhabarke.github.io\/publication\/probe-oopsla","DOI":"10.1145\/3428295"},{"key":"e_1_2_2_12_1","volume-title":"International Conference on Machine Learning. 2933-2942","author":"Bielik Pavol","year":"2016"},{"key":"e_1_2_2_13_1","volume-title":"Program Synthesis Using Deduction-Guided Reinforcement Learning. In International Conference on Computer Aided Verification. Springer, 587-610","author":"Chen Yanju","year":"2020"},{"key":"e_1_2_2_14_1","volume-title":"Armando Solar-Lezama, and Joshua B Tenenbaum.","author":"Ellis Kevin","year":"2018"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062351"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Yu Feng Ruben Martins Yuepeng Wang Isil Dillig and Thomas W Reps. 2017b. Component-based synthesis for complex APIs. ACM SIGPLAN Notices 52 1 ( 2017 ) 599-612.  Yu Feng Ruben Martins Yuepeng Wang Isil Dillig and Thomas W Reps. 2017b. Component-based synthesis for complex APIs. ACM SIGPLAN Notices 52 1 ( 2017 ) 599-612.","DOI":"10.1145\/3093333.3009851"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737977"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837629"},{"key":"e_1_2_2_19_1","unstructured":"Jianhang Gao Qing Zhao Wei Ren Ananthram Swami Ram Ramanathan and Amotz Bar-Noy. 2012. Dynamic Shortest Path Algorithms for Hypergraphs. CoRR abs\/1202.0082 ( 2012 ). arXiv: 1202.0082 http:\/\/arxiv.org\/abs\/1202.0082  Jianhang Gao Qing Zhao Wei Ren Ananthram Swami Ram Ramanathan and Amotz Bar-Noy. 2012. Dynamic Shortest Path Algorithms for Hypergraphs. CoRR abs\/1202.0082 ( 2012 ). arXiv: 1202.0082 http:\/\/arxiv.org\/abs\/1202.0082"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_2_2_21_1","volume-title":"Verification and Synthesis of Correct and Secure Systems","author":"Gulwani Sumit"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Sumit Gulwani Susmit Jha Ashish Tiwari and Ramarathnam Venkatesan. 2011. Synthesis of loop-free programs. ACM SIGPLAN Notices 46 6 ( 2011 ) 62-73.  Sumit Gulwani Susmit Jha Ashish Tiwari and Ramarathnam Venkatesan. 2011. Synthesis of loop-free programs. ACM SIGPLAN Notices 46 6 ( 2011 ) 62-73.","DOI":"10.1145\/1993316.1993506"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462192"},{"key":"e_1_2_2_24_1"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806833"},{"key":"e_1_2_2_26_1","volume-title":"Neural-guided deductive search for real-time program synthesis from examples. arXiv preprint arXiv","author":"Kalyan Ashwin","year":"1804"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2544173.2509555"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.229.9"},{"key":"e_1_2_2_29_1","unstructured":"Manos Koukoutos Mukund Raghothaman Etienne Kneuss and Viktor Kuncak. 2017. On repair with probabilistic attribute grammars. arXiv preprint arXiv:1707.04148 ( 2017 ).  Manos Koukoutos Mukund Raghothaman Etienne Kneuss and Viktor Kuncak. 2017. On repair with probabilistic attribute grammars. arXiv preprint arXiv:1707.04148 ( 2017 )."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594333"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Woosuk Lee Kihong Heo Rajeev Alur and Mayur Naik. 2018. Accelerating search-based program synthesis using learned probabilistic models. ACM SIGPLAN Notices 53 4 ( 2018 ) 436-449.  Woosuk Lee Kihong Heo Rajeev Alur and Mayur Naik. 2018. Accelerating search-based program synthesis using learned probabilistic models. ACM SIGPLAN Notices 53 4 ( 2018 ) 436-449.","DOI":"10.1145\/3296979.3192410"},{"key":"e_1_2_2_32_1","volume-title":"International Conference on Machine Learning. 187-195","author":"Menon Aditya","year":"2013"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738007"},{"key":"e_1_2_2_34_1","volume-title":"34th European Conference on Object-Oriented Programming, ECOOP.","author":"Peleg Hila","year":"2020"},{"key":"e_1_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Daniel Perelman Sumit Gulwani Dan Grossman and Peter Provost. 2014. Test-driven synthesis. ACM Sigplan Notices 49 6 ( 2014 ) 408-418.  Daniel Perelman Sumit Gulwani Dan Grossman and Peter Provost. 2014. Test-driven synthesis. ACM Sigplan Notices 49 6 ( 2014 ) 408-418.","DOI":"10.1145\/2666356.2594297"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980024.2872387"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594321"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25543-5_5"},{"key":"e_1_2_2_39_1","unstructured":"Rohin Shah Sumith Kulal and Rastislav Bodik. 2018. Scalable Synthesis with Symbolic Syntax Graphs. ( 2018 ).  Rohin Shah Sumith Kulal and Rastislav Bodik. 2018. Scalable Synthesis with Symbolic Syntax Graphs. ( 2018 )."},{"key":"e_1_2_2_40_1"},{"key":"e_1_2_2_41_1","unstructured":"Xujie Si Yuan Yang Hanjun Dai Mayur Naik and Le Song. 2019. Learning a Meta-Solver for Syntax-Guided Program Synthesis. https:\/\/openreview.net\/forum?id=Syl8Sn0cK7  Xujie Si Yuan Yang Hanjun Dai Mayur Naik and Le Song. 2019. Learning a Meta-Solver for Syntax-Guided Program Synthesis. https:\/\/openreview.net\/forum?id=Syl8Sn0cK7"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-11245-5_2"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168917.1168907"},{"key":"e_1_2_2_44_1","volume-title":"Milo MK Martin, and Rajeev Alur","author":"Udupa Abhishek","year":"2013"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062365"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158151"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133886"},{"key":"e_1_2_2_48_1","unstructured":"Henry S Warren. 2013. Hacker's delight. Pearson Education.  Henry S Warren. 2013. Hacker's delight. Pearson Education."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428295","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428295","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428295","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:58Z","timestamp":1750197778000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428295"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":48,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428295"],"URL":"https:\/\/doi.org\/10.1145\/3428295","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"2020-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}