{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T21:07:15Z","timestamp":1760044035536,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DARPA PTG Program","award":["HR00112220005"],"award-info":[{"award-number":["HR00112220005"]}]},{"name":"DARPA ANSR program","award":["FA8750-23-2-0004"],"award-info":[{"award-number":["FA8750-23-2-0004"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["#IIS-1943641, #IIS-1956441, #CCF-1837129"],"award-info":[{"award-number":["#IIS-1943641, #IIS-1956441, #CCF-1837129"]}],"id":[{"id":"10.13039\/100000001","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":[[2024,6,20]]},"abstract":"<jats:p>\n            Probabilistic programming languages (PPLs) are an expressive means for creating and reasoning about probabilistic models. Unfortunately\n            <jats:italic toggle=\"yes\">hybrid<\/jats:italic>\n            probabilistic programs that involve both continuous and discrete structures are not well supported by today\u2019s PPLs. In this paper we develop a new approximate inference algorithm for hybrid probabilistic programs that first discretizes the continuous distributions and then performs discrete inference on the resulting program. The key novelty is a form of discretization that we call\n            <jats:italic toggle=\"yes\">bit blasting<\/jats:italic>\n            , which uses a binary representation of numbers such that a domain of\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                <mml:msup>\n                  <mml:mn>2<\/mml:mn>\n                  <mml:mi>b<\/mml:mi>\n                <\/mml:msup>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            discretized points can be succinctly represented as a discrete probabilistic program over\n            <jats:italic toggle=\"yes\">poly<\/jats:italic>\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                <mml:mfenced close=\")\" open=\"(\">\n                  <mml:mi>b<\/mml:mi>\n                <\/mml:mfenced>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            Boolean random variables. Surprisingly, we prove that many common continuous distributions can be bit blasted in a manner that incurs no loss of accuracy over an explicit discretization and supports efficient probabilistic inference. We have built a probabilistic programming system for hybrid programs called\n            <jats:monospace>HyBit<\/jats:monospace>\n            , which employs bit blasting followed by discrete probabilistic inference. We empirically demonstrate the benefits of our approach over existing sampling-based and symbolic inference approaches\n          <\/jats:p>","DOI":"10.1145\/3656412","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"865-888","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Bit Blasting Probabilistic Programs"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4753-3974","authenticated-orcid":false,"given":"Poorva","family":"Garg","sequence":"first","affiliation":[{"name":"University of California, Los Angeles, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8190-5412","authenticated-orcid":false,"given":"Steven","family":"Holtzen","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3434-2503","authenticated-orcid":false,"given":"Guy","family":"Van den Broeck","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2031-1514","authenticated-orcid":false,"given":"Todd","family":"Millstein","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_1_2_1","unstructured":"@10kdiver. [n.d.]. @10kdiver. https:\/\/twitter.com\/10kdiver\/status\/1503307755976765443?s=20&t=Ux1C55thW5qnCPVOHoxguQ. [Online; accessed 14-March-2022]."},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133904"},{"key":"e_1_3_1_4_1","volume-title":"Computational Complexity: A Modern Approach","author":"Arora S.","year":"2006","unstructured":"S. Arora and B. Barak. 2006. Computational Complexity: A Modern Approach. Cambridge University Press. https:\/\/theory.cs.princeton.edu\/complexity\/book.pdf"},{"key":"e_1_3_1_5_1","doi-asserted-by":"publisher","unstructured":"Raven Beutner Luke Ong and Fabian Zaiser. 2022. Guaranteed Bounds for Posterior Inference in Universal Probabilistic Programming. https:\/\/doi.org\/10.48550\/ARXIV.2204.02948 10.48550\/ARXIV.2204.02948","DOI":"10.48550\/ARXIV.2204.02948"},{"key":"e_1_3_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/141000671"},{"key":"e_1_3_1_7_1","unstructured":"Eli Bingham Jonathan P. Chen Martin Jankowiak Fritz Obermeyer Neeraj Pradhan Theofanis Karaletsos Rohit Singh Paul Szerlip Paul Horsfall and Noah D. Goodman. 2018. Pyro documentation. https:\/\/pyro.ai\/examples\/enumeration.html"},{"key":"e_1_3_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3322706.3322734"},{"key":"e_1_3_1_9_1","doi-asserted-by":"publisher","DOI":"10.1111\/rssb.12158"},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","unstructured":"Roberto Bruttomesso and Natasha Sharygina. 2009. A scalable decision procedure for fixed-width bit-vectors. In 2009 IEEE\/ACM International Conference on Computer-Aided Design - Digest of Technical Papers. 13\u201320. https:\/\/doi.org\/10.1145\/1687399.1687403 10.1145\/1687399.1687403","DOI":"10.1145\/1687399.1687403"},{"key":"e_1_3_1_11_1","unstructured":"canyon289. 2022. Spacex. (2022). https:\/\/gist.github.com\/canyon289\/73890bab211c5cbaea41ad6f32df01a5"},{"key":"e_1_3_1_12_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 Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence (Pittsburgh PA USA) (UAI \u201923). JMLR.org Article 25 11 pages."},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v076.i01"},{"key":"e_1_3_1_14_1","unstructured":"Arun Chaganty Aditya Nori and Sriram Rajamani. 2013. Efficiently sampling probabilistic programs via program analysis. In Artificial Intelligence and Statistics. 153\u2013160."},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.11.002"},{"issue":"1","key":"e_1_3_1_16_1","first-page":"4","article-title":"Compiling Relational Bayesian Networks for Exact Inference","volume":"42","author":"Chavira Mark","year":"2006","unstructured":"Mark Chavira, Adnan Darwiche, and Manfred Jaeger. 2006. Compiling Relational Bayesian Networks for Exact Inference. IJAR 42, 1-2 (May 2006), 4\u201320.","journal-title":"IJAR"},{"key":"e_1_3_1_17_1","unstructured":"Irene Y. Chen Shalmali Joshi Marzyeh Ghassemi and Rajesh Ranganath. 2020. Probabilistic Machine Learning for Healthcare. arXiv:2009.11087 [stat.ML]"},{"key":"e_1_3_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491411.2491423"},{"key":"e_1_3_1_19_1","doi-asserted-by":"crossref","unstructured":"Fredrik Dahlqvist Alexandra Silva and William Smith. 2023. Deterministic stream-sampling for probabilistic programming: semantics and verification. arXiv:2304.13504 [cs.PL]","DOI":"10.1109\/LICS56636.2023.10175773"},{"key":"e_1_3_1_20_1","unstructured":"Luc De Raedt Angelika Kimmig and Hannu Toivonen. 2007. ProbLog : A Probabilistic Prolog and Its Applications to Link. Proc. of IJCAI (2007) 2468\u20132473."},{"key":"e_1_3_1_21_1","unstructured":"Joshua V Dillon Ian Langmore Dustin Tran Eugene Brevdo Srinivas Vasudevan Dave Moore Brian Patton Alex Alemi Matt Hoffman and Rif A Saurous. 2017. TensorFlow Distributions. arXiv preprint arXiv:1711.10604 (2017)."},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068414000076"},{"key":"e_1_3_1_23_1","doi-asserted-by":"crossref","unstructured":"Poorva Garg Steven Holtzen Guy Van den Broeck and Todd Millstein. 2023. Bit Blasting Probabilistic Programs. arXiv:2312.05706 [cs.PL]","DOI":"10.1145\/3656412"},{"key":"e_1_3_1_24_1","doi-asserted-by":"publisher","unstructured":"Poorva Garg Steven Holtzen Guy Van den Broeck and Todd Millstein. 2024. Bit Blasting Probabilistic Programs. https:\/\/doi.org\/10.5281\/zenodo.10901544 10.5281\/zenodo.10901544","DOI":"10.5281\/zenodo.10901544"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_4"},{"key":"e_1_3_1_26_1","unstructured":"Noah D. Goodman Vikash K. Mansinghka Daniel M. Roy Keith Bonawitz and Joshua B. Tenenbaum. 2008. Church: a language for generative models. In Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence (UAI)."},{"key":"e_1_3_1_27_1","unstructured":"Noah D Goodman and Andreas Stuhlm\u00fcller. 2014. The Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org. Accessed: 2022-10-26."},{"key":"e_1_3_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490421"},{"key":"e_1_3_1_29_1","unstructured":"Maria I Gorinova Dave Moore and Matthew D Hoffman. 2020. Automatic Reparameterisation of Probabilistic Programs. International Conference on Machine Learning (ICML) (2020)."},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21295-6_12"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","unstructured":"Steven Holtzen Guy Van den Broeck and Todd Millstein. 2020. Scaling Exact Inference for Discrete Probabilistic Programs. Proc. ACM Program. Lang. (OOPSLA) (2020). https:\/\/doi.org\/10.1145\/3428208 10.1145\/3428208","DOI":"10.1145\/3428208"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-88885-5_16"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","unstructured":"Chung-kil Hur Aditya V. Nori Sriram K. Rajamani and Selva Sammuel. 2015. A Provably Correct Sampler for Probabilistic Programs. FSTTCS FSTTCS (2015) 1\u201314. https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2015.475 10.4230\/LIPIcs.FSTTCS.2015.475","DOI":"10.4230\/LIPIcs.FSTTCS.2015.475"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","unstructured":"Chung-Kil Hur Aditya V. Nori Sriram K. Rajamani and Selva Samuel. 2014. Slicing probabilistic programs. Proc. of PLDI (2014) 133\u2013144. https:\/\/doi.org\/10.1145\/2594291.2594303 10.1145\/2594291.2594303","DOI":"10.1145\/2594291.2594303"},{"key":"e_1_3_1_35_1","unstructured":"Michael I. Jordan. 2010. Stat260: Bayesian Modeling and Inference: The Conjugate Prior for the Normal Distribution. http:\/\/www.cs.berkeley.edu\/~jordan\/courses\/260-spring10\/lectures\/lecture5.pdf"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1795555"},{"key":"e_1_3_1_37_1","unstructured":"Alp Kucukelbir Rajesh Ranganath Andrew Gelman and David Blei. 2015. Automatic variational inference in Stan. In Advances in neural information processing systems. 568\u2013576."},{"key":"e_1_3_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-44914-8_14"},{"key":"e_1_3_1_39_1","unstructured":"Edward A. Lee and Sanjit A. Seshia. 2017. Introduction to Embedded Systems A Cyber-Physical Systems Approach."},{"key":"e_1_3_1_40_1","unstructured":"Vikash Mansinghka Tejas D Kulkarni Yura N Perov and Josh Tenenbaum. 2013. Approximate bayesian image interpretation using generative probabilistic graphics programs. In Advances in Neural Information Processing Systems. 1520\u20131528"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192409"},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177693058"},{"key":"e_1_3_1_43_1","first-page":"1352","volume-title":"In Proceedings of the 19th International Joint Conference on Artificial Intelligence (Edinburgh, Scotland) (IJCAI\u201905)","author":"Milch Brian","year":"2005","unstructured":"Brian Milch, Bhaskara Marthi, Stuart Russell, David Sontag, Daniel L. Ong, and Andrey Kolobov. 2005. BLOG: Probabilistic Models with Unknown Objects. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (Edinburgh, Scotland) (IJCAI\u201905). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1352\u20131359."},{"key":"e_1_3_1_44_1","unstructured":"T. Minka J.M. Winn J.P. Guiver S. Webster Y. Zaykov B. Yangel A. Spengler and J. Bronskill. 2014. Infer.NET 2.6. Microsoft Research Cambridge. http:\/\/research.microsoft.com\/infernet."},{"key":"e_1_3_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_3_1_46_1","doi-asserted-by":"publisher","unstructured":"Robert Nishihara Thomas Minka and Daniel Tarlow. 2013. Detecting Parameter Symmetries in Probabilistic Models. https:\/\/doi.org\/10.48550\/ARXIV.1312.5386 10.48550\/ARXIV.1312.5386","DOI":"10.48550\/ARXIV.1312.5386"},{"key":"e_1_3_1_47_1","unstructured":"Avi Pfeffer. 2007. A general importance sampling algorithm for probabilistic programs. (2007). http:\/\/nrs.harvard.edu\/urn-3:HUL.InstRepos:25235125"},{"key":"e_1_3_1_48_1","doi-asserted-by":"publisher","DOI":"10.1142\/6300"},{"key":"e_1_3_1_49_1","unstructured":"Feras Saad and Vikash Mansinghka. 2016. A Probabilistic Programming Approach To Probabilistic Data Analysis. In Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_3_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454078"},{"key":"e_1_3_1_51_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1365-2966.2007.11871.x"},{"key":"e_1_3_1_52_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2017.1415911"},{"key":"e_1_3_1_53_1","first-page":"2600","volume-title":"In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2 (Montreal, Canada) (NIPS\u201914)","author":"Tristan Jean-Baptiste","year":"2014","unstructured":"Jean-Baptiste Tristan, Daniel Huang, Joseph Tassarotti, Adam Pocock, Stephen J. Green, and Guy L. Steele. 2014. Augur: Data-Parallel Probabilistic Modeling. In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2 (Montreal, Canada) (NIPS\u201914). MIT Press, Cambridge, MA, USA, 2600\u20132608."},{"key":"e_1_3_1_54_1","unstructured":"Jan-Willem van de Meent Hongseok Yang Vikash Mansinghka and Frank Wood. 2015. Particle Gibbs with Ancestor Sampling for Probabilistic Programs. In AISTATS."},{"key":"e_1_3_1_55_1","unstructured":"David Wingate and Theophane Weber. 2013. Automated variational inference in probabilistic programming. arXiv preprint arXiv:1301.1299 (2013)."},{"key":"e_1_3_1_56_1","unstructured":"Frank Wood Jan Willem Meent and Vikash Mansinghka. 2014. A new approach to probabilistic programming inference. In Artificial Intelligence and Statistics. 1024\u20131032."},{"key":"e_1_3_1_57_1","doi-asserted-by":"publisher","unstructured":"Yi Wu Siddharth Srivastava Nicholas Hay Simon Du and Stuart Russell. 2018. Discrete-Continuous Mixtures in Probabilistic Programming: Generalized Semantics and Inference Algorithms. https:\/\/doi.org\/10.48550\/ARXIV.1806.02027 10.48550\/ARXIV.1806.02027","DOI":"10.48550\/ARXIV.1806.02027"},{"key":"e_1_3_1_58_1","unstructured":"Yuling Yao Aki Vehtari and Andrew Gelman. 2021. Stacking for Non-mixing Bayesian Computations: The Curse and Blessing of Multimodal Posteriors. arXiv:2006.12335 [stat.ME]"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656412","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656412","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:42:37Z","timestamp":1751661757000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656412"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":57,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656412"],"URL":"https:\/\/doi.org\/10.1145\/3656412","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}