{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T09:32:38Z","timestamp":1770283958435,"version":"3.49.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T00:00:00Z","timestamp":1667174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-17-1-2699"],"award-info":[{"award-number":["N00014-17-1-2699"]}],"id":[{"id":"10.13039\/100000006","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":[[2022,10,31]]},"abstract":"<jats:p>A streaming probabilistic program receives a stream of observations and produces a stream of distributions that are conditioned on these observations. Efficient inference is often possible in a streaming context using Rao-Blackwellized particle filters (RBPFs), which exactly solve inference problems when possible and fall back on sampling approximations when necessary. While RBPFs can be implemented by hand to provide efficient inference, the goal of streaming probabilistic programming is to automatically generate such efficient inference implementations given input probabilistic programs.<\/jats:p>\n          <jats:p>In this work, we propose semi-symbolic inference, a technique for executing probabilistic programs using a runtime inference system that automatically implements Rao-Blackwellized particle filtering. To perform exact and approximate inference together, the semi-symbolic inference system manipulates symbolic distributions to perform exact inference when possible and falls back on approximate sampling when necessary. This approach enables the system to implement the same RBPF a developer would write by hand. To ensure this, we identify closed families of distributions \u2013 such as linear-Gaussian and finite discrete models \u2013 on which the inference system guarantees exact inference. We have implemented the runtime inference system in the ProbZelus streaming probabilistic programming language. Despite an average 1.6\u00d7 slowdown compared to the state of the art on existing benchmarks, our evaluation shows that speedups of 3\u00d7-87\u00d7 are obtainable on a new set of challenging benchmarks we have designed to exploit closed families.<\/jats:p>","DOI":"10.1145\/3563347","type":"journal-article","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T20:23:35Z","timestamp":1667247815000},"page":"1668-1696","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Semi-symbolic inference for efficient streaming probabilistic programming"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8396-1258","authenticated-orcid":false,"given":"Eric","family":"Atkinson","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4918-4467","authenticated-orcid":false,"given":"Charles","family":"Yuan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2230-1616","authenticated-orcid":false,"given":"Guillaume","family":"Baudart","sequence":"additional","affiliation":[{"name":"ENS \u2014 PSL University \u2014 CNRS \u2014 Inria, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5291-6067","authenticated-orcid":false,"given":"Louis","family":"Mandel","sequence":"additional","affiliation":[{"name":"IBM Research, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6928-0456","authenticated-orcid":false,"given":"Michael","family":"Carbin","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7082520"},{"key":"e_1_2_1_2_1","unstructured":"Eric Atkinson Charles Yuan Guillaume Baudart Louis Mandel and Michael Carbin. 2022. Semi-Symbolic Inference for Efficient Streaming Probabilistic Programming. arxiv:2209.07490 \t\t\t\t  Eric Atkinson Charles Yuan Guillaume Baudart Louis Mandel and Michael Carbin. 2022. Semi-Symbolic Inference for Efficient Streaming Probabilistic Programming. arxiv:2209.07490"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386009"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1155\/2008\/246309"},{"key":"e_1_2_1_5_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 A. Szerlip , Paul Horsfall , and Noah D. Goodman . 2019 . Pyro: Deep Universal Probabilistic Programming . J. Mach. Learn. Res. , 20 (2019), 28:1\u201328:6. http:\/\/jmlr.org\/papers\/v20\/18-403.html Eli Bingham, Jonathan P. Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul A. Szerlip, Paul Horsfall, and Noah D. Goodman. 2019. Pyro: Deep Universal Probabilistic Programming. J. Mach. Learn. Res., 20 (2019), 28:1\u201328:6. http:\/\/jmlr.org\/papers\/v20\/18-403.html","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3437-9_24"},{"key":"e_1_2_1_7_1","unstructured":"Daniel Fink. 1997. A Compendium of Conjugate Priors. \t\t\t\t  Daniel Fink. 1997. A Compendium of Conjugate Priors."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1984.4767596"},{"key":"e_1_2_1_10_1","volume-title":"Goodman and Andreas Stuhlm\u00fcller","author":"Noah","year":"2014","unstructured":"Noah D. Goodman and Andreas Stuhlm\u00fcller . 2014 . The Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org Accessed October 2022 Noah D. Goodman and Andreas Stuhlm\u00fcller. 2014. The Design and Implementation of Probabilistic Programming Languages. http:\/\/dippl.org Accessed October 2022"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1049\/ip-f-2.1993.0015"},{"key":"e_1_2_1_12_1","volume-title":"Autoconj: Recognizing and Exploiting Conjugacy Without a Domain-specific Language. In NeurIPS. https:\/\/proceedings.neurips.cc\/paper\/2018\/file\/9b89bedda1fc8a2d88c448e361194f02-Paper.pdf","author":"Hoffman Matthew D","year":"2018","unstructured":"Matthew D Hoffman , Matthew J Johnson , and Dustin Tran . 2018 . Autoconj: Recognizing and Exploiting Conjugacy Without a Domain-specific Language. In NeurIPS. https:\/\/proceedings.neurips.cc\/paper\/2018\/file\/9b89bedda1fc8a2d88c448e361194f02-Paper.pdf Matthew D Hoffman, Matthew J Johnson, and Dustin Tran. 2018. Autoconj: Recognizing and Exploiting Conjugacy Without a Domain-specific Language. In NeurIPS. https:\/\/proceedings.neurips.cc\/paper\/2018\/file\/9b89bedda1fc8a2d88c448e361194f02-Paper.pdf"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428208"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCA.1999.801027"},{"key":"e_1_2_1_15_1","volume-title":"Delayed sampling in the probabilistic programming language Anglican. Master\u2019s thesis","author":"Lund\u00e9n Daniel","unstructured":"Daniel Lund\u00e9n . 2017. Delayed sampling in the probabilistic programming language Anglican. Master\u2019s thesis . KTH Royal Institute of Technology . http:\/\/urn.kb.se\/resolve?urn=urn:nbn:se:kth:diva-210756 Daniel Lund\u00e9n. 2017. Delayed sampling in the probabilistic programming language Anglican. Master\u2019s thesis. KTH Royal Institute of Technology. http:\/\/urn.kb.se\/resolve?urn=urn:nbn:se:kth:diva-210756"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192409"},{"key":"e_1_2_1_17_1","unstructured":"T. Minka J.M. Winn J.P. Guiver Y. Zaykov D. Fabian and J. Bronskill. 2018. Infer.NET 0.3. http:\/\/dotnet.github.io\/infer Microsoft Research Cambridge. \t\t\t\t  T. Minka J.M. Winn J.P. Guiver Y. Zaykov D. Fabian and J. Bronskill. 2018. Infer.NET 0.3. http:\/\/dotnet.github.io\/infer Microsoft Research Cambridge."},{"key":"e_1_2_1_18_1","unstructured":"Thomas P. Minka. 2001. Expectation Propagation for approximate Bayesian inference. In UAI. Morgan Kaufmann 362\u2013369. isbn:1558608001 \t\t\t\t  Thomas P. Minka. 2001. Expectation Propagation for approximate Bayesian inference. In UAI. Morgan Kaufmann 362\u2013369. isbn:1558608001"},{"key":"e_1_2_1_19_1","volume-title":"Sch\u00f6n","author":"Murray Lawrence M.","year":"2018","unstructured":"Lawrence M. Murray , Daniel Lund\u00e9n , Jan Kudlicka , David Broman , and Thomas B . Sch\u00f6n . 2018 . Delayed Sampling and Automatic Rao-Blackwellization of Probabilistic Programs . In AISTATS (Proceedings of Machine Learning Research, Vol. 84). PMLR, 1037\u2013 1046 . https:\/\/proceedings.mlr.press\/v84\/murray18a.html Lawrence M. Murray, Daniel Lund\u00e9n, Jan Kudlicka, David Broman, and Thomas B. Sch\u00f6n. 2018. Delayed Sampling and Automatic Rao-Blackwellization of Probabilistic Programs. In AISTATS (Proceedings of Machine Learning Research, Vol. 84). PMLR, 1037\u20131046. https:\/\/proceedings.mlr.press\/v84\/murray18a.html"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.arcontrol.2018.10.013"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_2_1_22_1","volume-title":"Functional Tensors for Probabilistic Programming. In Program Transformations for ML Workshop at NeurIPS.","author":"Obermeyer Fritz","year":"2019","unstructured":"Fritz Obermeyer , Eli Bingham , Martin Jankowiak , Du Phan , and Jonathan Chen . 2019 . Functional Tensors for Probabilistic Programming. In Program Transformations for ML Workshop at NeurIPS. Fritz Obermeyer, Eli Bingham, Martin Jankowiak, Du Phan, and Jonathan Chen. 2019. Functional Tensors for Probabilistic Programming. In Program Transformations for ML Workshop at NeurIPS."},{"key":"e_1_2_1_23_1","unstructured":"Fritz Obermeyer Elias Bingham Martin Jankowiak Neeraj Pradhan Justin Chiu Alexander Rush and Noah Goodman. 2019. Tensor Variable Elimination for Plated Factor Graphs. In ICML. https:\/\/proceedings.mlr.press\/v97\/obermeyer19a.html \t\t\t\t  Fritz Obermeyer Elias Bingham Martin Jankowiak Neeraj Pradhan Justin Chiu Alexander Rush and Noah Goodman. 2019. Tensor Variable Elimination for Plated Factor Graphs. In ICML. https:\/\/proceedings.mlr.press\/v97\/obermeyer19a.html"},{"key":"e_1_2_1_24_1","unstructured":"Judea Pearl. 1982. Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach. In AAAI. \t\t\t\t  Judea Pearl. 1982. Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach. In AAAI."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454078"},{"key":"e_1_2_1_26_1","first-page":"303","article-title":"Latency Determination and Compensation in Real-Time Gnss\/ins Integrated Navigation Systems","volume":"3822","author":"Solomon P. D.","year":"2012","unstructured":"P. D. Solomon , Jinling Wang , and Chris Rizos . 2012 . Latency Determination and Compensation in Real-Time Gnss\/ins Integrated Navigation Systems . ISPRS , 3822 (2012), 303 \u2013 307 . P. D. Solomon, Jinling Wang, and Chris Rizos. 2012. Latency Determination and Compensation in Real-Time Gnss\/ins Integrated Navigation Systems. ISPRS, 3822 (2012), 303\u2013307.","journal-title":"ISPRS"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0577-7"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064899.3064910"},{"key":"e_1_2_1_29_1","volume-title":"Blei","author":"Tran Dustin","year":"2017","unstructured":"Dustin Tran , Matthew D. Hoffman , Rif A. Saurous , Eugene Brevdo , Kevin Murphy , and David M . Blei . 2017 . Deep Probabilistic Programming. In ICLR (Poster). OpenReview .net. https:\/\/openreview.net\/forum?id=Hy6b4Pqee Dustin Tran, Matthew D. Hoffman, Rif A. Saurous, Eugene Brevdo, Kevin Murphy, and David M. Blei. 2017. Deep Probabilistic Programming. In ICLR (Poster). OpenReview.net. https:\/\/openreview.net\/forum?id=Hy6b4Pqee"},{"key":"e_1_2_1_30_1","article-title":"Variational Message Passing","volume":"6","author":"Winn John","year":"2005","unstructured":"John Winn and Christopher M. Bishop . 2005 . Variational Message Passing . Journal of Machine Learning Research , 6 , 4 (2005), https:\/\/www.jmlr.org\/papers\/v6\/winn05a.html John Winn and Christopher M. Bishop. 2005. Variational Message Passing. Journal of Machine Learning Research, 6, 4 (2005), https:\/\/www.jmlr.org\/papers\/v6\/winn05a.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_31_1","volume-title":"Canadian Conference on Artificial Intelligence.","author":"Zhang N.L.","unstructured":"N.L. Zhang and D. Poole . 1994. A Simple Approach to Bayesian Network Computations . In Canadian Conference on Artificial Intelligence. N.L. Zhang and D. Poole. 1994. A Simple Approach to Bayesian Network Computations. In Canadian Conference on Artificial Intelligence."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563347","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563347","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563347","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:38:11Z","timestamp":1750178291000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563347"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,31]]},"references-count":31,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3563347"],"URL":"https:\/\/doi.org\/10.1145\/3563347","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,31]]},"assertion":[{"value":"2022-10-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}