{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:05:57Z","timestamp":1784199957061,"version":"3.55.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T00:00:00Z","timestamp":1749772800000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>\n                    We present new techniques for exact and approximate inference in discrete probabilistic programs, based on two new ways of exploiting lazy evaluation. First, we show how knowledge compilation, a state-of-the art technique for exact inference in discrete probabilistic programs, can be made lazy, enabling asymptotic speed-ups. Second, we show how a probabilistic program\u2019s lazy semantics naturally give rise to a division of its random choices into subproblems, which can be solved in sequence by sequential Monte Carlo with locallyoptimal proposals automatically computed via lazy knowledge compilation. We implement our approach in a new tool,\n                    <jats:sc>Pluck<\/jats:sc>\n                    , and evaluate its performance against state-of-the-art approaches to inference in discrete probabilistic languages. We !nd that on a suite of inference benchmarks, lazy knowledge compilation can be faster than state-of-the-art approaches, sometimes by orders of magnitude.\n                  <\/jats:p>","DOI":"10.1145\/3729325","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"1863-1887","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Stochastic Lazy Knowledge Compilation for Inference in Discrete Probabilistic Programs"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8450-7033","authenticated-orcid":false,"given":"Maddy","family":"Bowers","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9262-4392","authenticated-orcid":false,"given":"Alexander K.","family":"Lew","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"},{"name":"Yale University, New Haven, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1925-2035","authenticated-orcid":false,"given":"Joshua B.","family":"Tenenbaum","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7604-8252","authenticated-orcid":false,"given":"Armando","family":"Solar-Lezama","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2507-0833","authenticated-orcid":false,"given":"Vikash K.","family":"Mansinghka","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Eric Atkinson Cambridge Yang and Michael Carbin. 2018. Verifying handcoded probabilistic inference procedures. arXiv preprint arXiv:1805.01869 (2018)."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3563347"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3656463"},{"issue":"28","key":"e_1_3_2_5_2","first-page":"1","article-title":"Pyro: Deep universal probabilistic programming","volume":"20","author":"Bingham Eli","year":"2019","unstructured":"Eli Bingham, Jonathan P Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, and Noah D Goodman. 2019. Pyro: Deep universal probabilistic programming. Journal of machine learning research 20, 28 (2019), 1\u20136.","journal-title":"Journal of machine learning research"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","unstructured":"Maddy Bowers Alexander K Lew Joshua B Tenenbaum Armando Solar-Lezama and Vikash Mansinghka. 2025. Artifact for \"Stochastic Lazy Knowledge Compilation for Inference in Discrete Probabilistic Programs\". doi:10.5281\/zenodo.15051140","DOI":"10.5281\/zenodo.15051140"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"e_1_3_2_8_2","first-page":"266","volume-title":"Uncertainty in Artificial Intelligence","author":"Cao William X","year":"2023","unstructured":"William X Cao, Poorva Garg, Ryan Tjoa, Steven Holtzen, Todd Millstein, and Guy Van den Broeck. 2023. Scaling integer arithmetic in probabilistic programs. In Uncertainty in Artificial Intelligence. PMLR, 266\u2013270."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3586050"},{"key":"e_1_3_2_10_2","volume-title":"An introduction to sequential Monte Carlo Vol. 4","author":"Chopin Nicolas","year":"2020","unstructured":"Nicolas Chopin, Omiros Papaspiliopoulos, et al. 2020. An introduction to sequential Monte Carlo Vol. 4. Springer."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796815000143"},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","unstructured":"Guillaume Claret Sriram K Rajamani Aditya V Nori Andrew D Gordon and Johannes Borgstr\u00f6m. 2013. Bayesian inference using data flow analysis. In Proceedings of the 2013 9th joint meeting on foundations of software engineering 92\u2013102.","DOI":"10.1145\/2491411.2491423"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Marco F Cusumano-Towner Feras A Saad Alexander K Lew and Vikash K Mansinghka. 2019. Gen: a general-purpose probabilistic programming system with programmable inference. In Proceedings of the 40th acm sigplan conference on programming language design and implementation 221\u2013236.","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571239"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-015-5494-z"},{"key":"e_1_3_2_16_2","unstructured":"Luc De Raedt Angelika Kimmig and Hannu Toivonen. 2007. ProbLog: A probabilistic Prolog and its application in link discovery. In IJCAI 2007 Proceedings of the 20th international joint conference on artificial intelligence IJCAI-INT JOINT CONF ARTIF INTELL 2462\u20132467."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_31"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46669-8_16"},{"key":"e_1_3_2_19_2","unstructured":"Daan Fierens Guy Van den Broeck Ingo Thon Bernd Gutmann and Luc De Raedt. 2012. Inference in probabilistic logic programs using weighted CNFs. arXiv preprint arXiv:1202.3719 2012."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000076"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3656412"},{"key":"e_1_3_2_22_2","first-page":"1682","volume-title":"International conference on artificial intelligence and statistics","author":"Ge Hong","year":"2018","unstructured":"Hong Ge, Kai Xu, and Zoubin Ghahramani. 2018. Turing: a language for flexible probabilistic inference. In International conference on artificial intelligence and statistics. PMLR, 1682\u20131690."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386006"},{"key":"e_1_3_2_24_2","unstructured":"Noah D. Goodman and Andreas Stuhlm\u00fcller. 2014. The design and implementation of probabilistic programming languages."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1080\/03640210701802071"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490421"},{"key":"e_1_3_2_27_2","unstructured":"Shivam Handa. 2019. Composable inference metaprogramming using subproblems. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428208"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00023-X"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068410000566"},{"key":"e_1_3_2_31_2","unstructured":"Angelika Kimmig Bernd Gutmann Theofrastos Mantadelis Guy Van den Broeck Vitor Santos Costa Gerda Janssens and Luc De Raedt. 2011. ProbLog. ALP Newsletter (2011)."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03034-5_17"},{"key":"e_1_3_2_33_2","unstructured":"Daphne Koller David McAllester and Avi Pfeffer. 1997. Effective Bayesian inference for stochastic programs. In AAAI\/IAAI 740\u2013747."},{"key":"e_1_3_2_34_2","first-page":"1927","volume-title":"International conference on artificial intelligence and statistics","author":"Lew Alexander","year":"2021","unstructured":"Alexander Lew, Monica Agrawal, David Sontag, and Vikash Mansinghka. 2021. PClean: Bayesian data cleaning at scale with domain-specific probabilistic programming. In International conference on artificial intelligence and statistics. PMLR, 1927\u20131935."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371087"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591290"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571243"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3656448"},{"key":"e_1_3_2_39_2","unstructured":"Vikash Mansinghka Daniel Selsam and Yura Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. arXiv preprint arXiv:1404.0099 (2014)."},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","unstructured":"Vikash K Mansinghka Ulrich Schaechtle Shivam Handa Alexey Radul Yutian Chen and Martin Rinard. 2018. Probabilistic programming with programmable inference. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation 603\u2013616.","DOI":"10.1145\/3192366.3192409"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.arcontrol.2018.10.013"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737982"},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","unstructured":"Jingwen Pan and Amir Shaikhha. 2023. Compiling Discrete Probabilistic Programs for Vectorized Exact Inference. In Proceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction 13\u201324.","DOI":"10.1145\/3578360.3580258"},{"key":"e_1_3_2_45_2","unstructured":"Avi Pfeffer. 2001. IBAL: A probabilistic rational programming language. In IJCAI. Citeseer 733\u2013740."},{"key":"e_1_3_2_46_2","unstructured":"Avi Pfeffer. 2006. IBAL: An Expressive Functional Probabilistic Modeling Language. (2006)."},{"key":"e_1_3_2_47_2","unstructured":"Avi Pfeffer Brian Ruttenberg Amy Sliva Michael Howard and Glenn Takata. 2015. Lazy factored inference for functional probabilistic programming. arXiv preprint arXiv:1509.03564 (2015)."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3689748"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1543134.1411292"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3290350"},{"key":"e_1_3_2_51_2","doi-asserted-by":"crossref","unstructured":"Feras A Saad Martin C Rinard and Vikash K Mansinghka. 2021. SPPL: probabilistic programming with fast exact symbolic inference. In Proceedings of the 42nd acm sigplan international conference on programming language design and implementation 804\u2013819.","DOI":"10.1145\/3453483.3454078"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3236778"},{"key":"e_1_3_2_53_2","first-page":"1056","volume-title":"Uncertainty in Artificial Intelligence","author":"Stites Sam","year":"2021","unstructured":"Sam Stites, Heiko Zimmermann, Hao Wu, Eli Sennesh, and Jan-Willem van de Meent. 2021. Learning proposals for probabilistic programs with inference combinators. In Uncertainty in Artificial Intelligence. PMLR, 1056\u20131066."},{"key":"e_1_3_2_54_2","unstructured":"Andreas Stuhlm\u00fcller and Noah D Goodman. 2012. A dynamic programming algorithm for inference in recursive probabilistic programs. arXiv preprint arXiv:1206.3555 (2012)."},{"key":"e_1_3_2_55_2","doi-asserted-by":"crossref","unstructured":"David Tolpin Jan-Willem van de Meent Hongseok Yang and Frank Wood. 2016. Design and implementation of probabilistic programming language Anglican. In Proceedings of the 28th Symposium on the Implementation and Application of Functional Programming Languages 1\u201312.","DOI":"10.1145\/3064899.3064910"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3290349"},{"key":"e_1_3_2_57_2","first-page":"2178","volume-title":"Proceedings of the Twenty-Second International Joint conference on Artificial Intelligence","year":"2011","unstructured":"Guy Van den Broeck, Nima Taghipour, Wannes Meert, Jesse Davis, and Luc De Raedt. 2011. Lifted probabilistic inference by first-order knowledge compilation. In Proceedings of the Twenty-Second International Joint conference on Artificial Intelligence. AAAI Press\/International Joint Conferences on Artificial Intelligence; Menlo\u00a0\u2026, 2178\u20132185."},{"key":"e_1_3_2_58_2","doi-asserted-by":"crossref","unstructured":"Di Wang Jan Hoffmann and Thomas Reps. 2021. Sound probabilistic inference via guide types. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation 788\u2013803.","DOI":"10.1145\/3453483.3454077"},{"key":"e_1_3_2_59_2","first-page":"770","volume-title":"Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics","author":"Wingate David","year":"2011","unstructured":"David Wingate, Andreas Stuhlm\u00fcller, and Noah D Goodman. 2011. Lightweight implementations of probabilistic programming languages via transformational compilation. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 770\u2013778."},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2021865119"},{"key":"e_1_3_2_61_2","article-title":"Exact Bayesian inference on discrete models via probability-generating functions: a probabilistic programming approach","volume":"36","author":"Zaiser Fabian","year":"2024","unstructured":"Fabian Zaiser, Andrzej Murawski, and Chih-Hao Luke Ong. 2024. Exact Bayesian inference on discrete models via probability-generating functions: a probabilistic programming approach. Advances in Neural Information Processing Systems 36 (2024).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_62_2","first-page":"11534","volume-title":"International Conference on Machine Learning","author":"Zhou Yuan","year":"2020","unstructured":"Yuan Zhou, Hongseok Yang, Yee Whye Teh, and Tom Rainforth. 2020. Divide, conquer, and combine: a new inference strategy for probabilistic programs with stochastic support. In International Conference on Machine Learning. PMLR, 11534\u201311545."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729325","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:06:58Z","timestamp":1784196418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":61,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729325"],"URL":"https:\/\/doi.org\/10.1145\/3729325","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}