{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T14:29:31Z","timestamp":1754144971384,"version":"3.41.2"},"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>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 locally-optimal proposals automatically computed via lazy knowledge compilation. We implement our approach in a new tool, Pluck, and evaluate its performance against state-of-the-art approaches to inference in discrete probabilistic languages. We find that on a suite of inference benchmarks, lazy knowledge compilation can be faster than state-of-the-art approaches, sometimes by orders of magnitude.<\/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":0,"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"}]},{"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"}]},{"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"}]},{"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"}]},{"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"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Eric Atkinson Cambridge Yang and Michael Carbin. 2018. Verifying handcoded probabilistic inference procedures. arXiv preprint arXiv:1805.01863."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563347"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656463"},{"key":"e_1_2_2_4_1","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_2_2_5_1","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\". https:\/\/doi.org\/10.5281\/zenodo.15051140 10.5281\/zenodo.15051140","DOI":"10.5281\/zenodo.15051140"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"e_1_2_2_7_1","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. 260\u2013270."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586050"},{"volume-title":"An introduction to sequential Monte Carlo. 4","author":"Chopin Nicolas","key":"e_1_2_2_9_1","unstructured":"Nicolas Chopin and Omiros Papaspiliopoulos. 2020. An introduction to sequential Monte Carlo. 4, Springer."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796815000143"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491411.2491423"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571239"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-015-5494-z"},{"key":"e_1_2_2_15_1","volume-title":"IJCAI 2007, Proceedings of the 20th international joint conference on artificial intelligence. 2462\u20132467","author":"Raedt Luc De","year":"2007","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. 2462\u20132467."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_31"},{"key":"e_1_2_2_17_1","volume-title":"John Hughes, and Robert Bruce Findler.","author":"Fetscher Burke","year":"2015","unstructured":"Burke Fetscher, Koen Claessen, Micha\u0142 Pa\u0142 ka, John Hughes, and Robert Bruce Findler. 2015. Making random judgments: Automatically generating well-typed terms from the definition of a type-system. In Programming Languages and Systems: 24th European Symposium on Programming, ESOP 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015, Proceedings 24. 383\u2013405."},{"key":"e_1_2_2_18_1","volume-title":"Guy Van den Broeck","author":"Fierens Daan","year":"2012","unstructured":"Daan Fierens, Guy Van den Broeck, Ingo Thon, Bernd Gutmann, and Luc De Raedt. 2012. Inference in probabilistic logic programs using weighted CNF\u2019s. arXiv preprint arXiv:1202.3719."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000076"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656412"},{"key":"e_1_2_2_21_1","volume-title":"International conference on artificial intelligence and statistics. 1682\u20131690","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. 1682\u20131690."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386006"},{"key":"e_1_2_2_23_1","unstructured":"Noah D Goodman and Andreas Stuhlm\u00fcller. 2014. The design and implementation of probabilistic programming languages."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/03640210701802071"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490421"},{"volume-title":"Composable inference metaprogramming using subproblems. Ph. D. Dissertation","author":"Handa Shivam","key":"e_1_2_2_26_1","unstructured":"Shivam Handa. 2019. Composable inference metaprogramming using subproblems. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428208"},{"key":"e_1_2_2_28_1","volume-title":"Planning and acting in partially observable stochastic domains. Artificial intelligence, 101, 1-2","author":"Kaelbling Leslie Pack","year":"1998","unstructured":"Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. 1998. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101, 1-2 (1998), 99\u2013134."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068410000566"},{"key":"e_1_2_2_30_1","volume-title":"Vitor Santos Costa, Gerda Janssens, and Luc De Raedt.","author":"Kimmig Angelika","year":"2011","unstructured":"Angelika Kimmig, Bernd Gutmann, Theofrastos Mantadelis, Guy Van den Broeck, Vitor Santos Costa, Gerda Janssens, and Luc De Raedt. 2011. ProbLog. ALP Newsletter."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03034-5_17"},{"key":"e_1_2_2_32_1","unstructured":"Daphne Koller David McAllester and Avi Pfeffer. 1997. Effective Bayesian inference for stochastic programs. In AAAI\/IAAI. 740\u2013747."},{"key":"e_1_2_2_33_1","volume-title":"International conference on artificial intelligence and statistics. 1927\u20131935","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. 1927\u20131935."},{"key":"e_1_2_2_34_1","volume-title":"Proceedings of the ACM on Programming Languages, 4, POPL","author":"Lew Alexander K","year":"2019","unstructured":"Alexander K Lew, Marco F Cusumano-Towner, Benjamin Sherman, Michael Carbin, and Vikash K Mansinghka. 2019. Trace types and denotational semantics for sound programmable inference in probabilistic languages. Proceedings of the ACM on Programming Languages, 4, POPL (2019), 1\u201332."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591290"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571243"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656448"},{"key":"e_1_2_2_38_1","unstructured":"Vikash Mansinghka Daniel Selsam and Yura Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. arXiv preprint arXiv:1404.0099."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192409"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.arcontrol.2018.10.013"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737982"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3578360.3580258"},{"key":"e_1_2_2_44_1","volume-title":"IBAL: A probabilistic rational programming language. In IJCAI. 733\u2013740.","author":"Pfeffer Avi","year":"2001","unstructured":"Avi Pfeffer. 2001. IBAL: A probabilistic rational programming language. In IJCAI. 733\u2013740."},{"key":"e_1_2_2_45_1","volume-title":"IBAL: An Expressive, Functional Probabilistic Modeling Language.","author":"Pfeffer Avi","year":"2006","unstructured":"Avi Pfeffer. 2006. IBAL: An Expressive, Functional Probabilistic Modeling Language."},{"key":"e_1_2_2_46_1","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."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689748"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1543134.1411292"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290350"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454078"},{"key":"e_1_2_2_51_1","volume-title":"Proceedings of the ACM on Programming Languages, 2, ICFP","author":"\u015acibior Adam","year":"2018","unstructured":"Adam \u015acibior, Ohad Kammar, and Zoubin Ghahramani. 2018. Functional programming for modular Bayesian inference. Proceedings of the ACM on Programming Languages, 2, ICFP (2018), 1\u201329."},{"key":"e_1_2_2_52_1","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. 1056\u20131066."},{"key":"e_1_2_2_53_1","unstructured":"Andreas Stuhlm\u00fcller and Noah D Goodman. 2012. A dynamic programming algorithm for inference in recursive probabilistic programs. arXiv preprint arXiv:1206.3555."},{"volume-title":"Proceedings of the 28th Symposium on the Implementation and Application of Functional programming Languages. 1\u201312","author":"Tolpin David","key":"e_1_2_2_54_1","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."},{"key":"e_1_2_2_55_1","volume-title":"Proceedings of the ACM on Programming Languages, 3, POPL","author":"V\u00e1k\u00e1r Matthijs","year":"2019","unstructured":"Matthijs V\u00e1k\u00e1r, Ohad Kammar, and Sam Staton. 2019. A domain theory for statistical probabilistic programming. Proceedings of the ACM on Programming Languages, 3, POPL (2019), 1\u201329."},{"key":"e_1_2_2_56_1","volume-title":"Proceedings of the Twenty-Second international joint conference on Artificial Intelligence. 2178\u20132185","author":"den Broeck Guy Van","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. 2178\u20132185."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454077"},{"key":"e_1_2_2_58_1","volume-title":"Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. 770\u2013778","author":"Wingate David","year":"2011","unstructured":"David Wingate, Andreas Stuhlm\u00fcller, and Noah Goodman. 2011. Lightweight implementations of probabilistic programming languages via transformational compilation. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. 770\u2013778."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2021865119"},{"key":"e_1_2_2_60_1","volume-title":"Exact Bayesian inference on discrete models via probability generating functions: a probabilistic programming approach. Advances in Neural Information Processing Systems, 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)."},{"key":"e_1_2_2_61_1","volume-title":"International Conference on Machine Learning. 11534\u201311545","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. 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":[[2025,7,16]],"date-time":"2025-07-16T06:06:53Z","timestamp":1752646013000},"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":[{"type":"electronic","value":"2475-1421"}],"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"}}]}}