{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T11:07:38Z","timestamp":1790075258198,"version":"4.0.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:00:00Z","timestamp":1780876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,6,8]]},"abstract":"<jats:p>\n                    Inference in probabilistic programs generally requires evaluating many possible program executions to find those of high posterior density. To scale inference to large datasets, it is crucial that expensive intermediate results are shared across these many evaluations, rather than recomputed from scratch. This paper presents a new approach to realizing this sharing, based on\n                    <jats:italic toggle=\"yes\">incremental computation<\/jats:italic>\n                    , a technique for efficiently recomputing (deterministic) program outputs when program inputs change. First, we show how expressive probabilistic programs can be compiled to deterministic ones that compute their density functions. Then, building on the incremental\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                        <mml:mi>\u03bb<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -calculus, we develop a general technique for compositionally incrementalizing expressive functional programs, and apply it to these densities. The resulting incremental densities can be used to accelerate a broad range of Monte Carlo inference algorithms, including for nonparametric models not well supported by existing systems. Furthermore, our decomposition of incremental density computation into separate density and incrementalization steps allows for modular reasoning about correctness\u2014a key pain point in existing systems, where ad-hoc incrementalization features are a known source of soundness bugs. We develop denotational logical relations arguments for the correctness of each step independently, and implement the approach in a Julia prototype, finding that it leads to asymptotic runtime improvements in the size of the dataset on a range of models and inference algorithms.\n                  <\/jats:p>","DOI":"10.1145\/3808316","type":"journal-article","created":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T18:04:09Z","timestamp":1780941849000},"page":"1739-1763","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Incremental Computation for Efficient Programmable Inference in Probabilistic Programs"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5158-2002","authenticated-orcid":false,"given":"Fabian","family":"Zaiser","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3242-6969","authenticated-orcid":false,"given":"Jack","family":"Czenszak","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8095-8523","authenticated-orcid":false,"given":"Martin C.","family":"Rinard","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9262-4392","authenticated-orcid":false,"given":"Alexander K.","family":"Lew","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/1087939"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1480945.1480946"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOS574"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2011-05107-X"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3776729"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/944919.944937"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2508.20922"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/55.1.119"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594304"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17184-1_12"},{"key":"e_1_3_2_12_2","volume-title":"Gen: a high-level programming platform for probabilistic inference. Ph. D. Dissertation","author":"Cusumano-Towner Marco F.","year":"2020","unstructured":"Marco F. Cusumano-Towner. 2020. Gen: a high-level programming platform for probabilistic inference. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192399"},{"key":"e_1_3_2_14_2","unstructured":"Marco F. Cusumano-Towner Alexander K. Lew and Vikash K. Mansinghka. 2020. Automating Involutive MCMC using Probabilistic and Differentiable Programming. arXiv:2007.09871 [stat.CO] https:\/\/arxiv.org\/abs\/2007.09871"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571239"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1994.tb01985.x"},{"key":"e_1_3_2_18_2","first-page":"1682","volume-title":"Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics (AISTATS) (Proceedings of Machine Learning Research, Vol. 84)","author":"Ge Hong","year":"2018","unstructured":"Hong Ge, Kai Xu, and Zoubin Ghahramani. 2018. Turing: A Language for Flexible Probabilistic Inference. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics (AISTATS) (Proceedings of Machine Learning Research, Vol. 84). PMLR, 1682\u20131690."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17184-1_20"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814305"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594324"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005137"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371084"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371087"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571243"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3776663"},{"key":"e_1_3_2_27_2","volume-title":"Categories for the Working Mathematician","author":"Mac Lane Saunders","year":"1998","unstructured":"Saunders Mac Lane. 1998. Categories for the Working Mathematician (2nd ed.). Graduate Texts in Mathematics, Vol. 5. Springer.","edition":"2"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0927-0"},{"key":"e_1_3_2_29_2","unstructured":"Vikash Mansinghka Daniel Selsam and Yura N. Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. CoRR abs\/1404.0099 (2014). arXiv:1404.0099 http:\/\/arxiv.org\/abs\/1404.0099"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192409"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3531130.3533370"},{"key":"e_1_3_2_32_2","unstructured":"George Matheos Alexander K. Lew Matin Ghavamizadeh Stuart Russell Marco F. Cusumano-Towner and Vikash Mansinghka. 2021. Transforming Worlds: Automated Involutive MCMC for Open-Universe Probabilistic Models. In Third Symposium on Advances in Approximate Bayesian Inference. https:\/\/openreview.net\/forum?id=8Itm8dQnJRc"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3607830"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/3020419.3020462"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2016.1255636"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1989.39155"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90052-4"},{"key":"e_1_3_2_38_2","unstructured":"Akimasa Morihata. 2020. Short Cut to Incremental Typed Functional Programs (Extended Abstract). In WPTE 2020: 7th International Workshop on Rewriting Techniques for Program Transformations and Evaluation. http:\/\/maude.ucm.es\/wpte20\/papers\/WPTE_2020_morihata.pdf Informal proceedings."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2000.10474879"},{"key":"e_1_3_2_40_2","unstructured":"Daniel Ritchie Andreas Stuhlm\u00fcller and Noah D. Goodman. 2016. C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics AISTATS 2016 Cadiz Spain May 9-11 2016 (JMLR Workshop and Conference Proceedings Vol. 51) Arthur Gretton and Christian C. Robert (Eds.). JMLR.org 28\u201337. http:\/\/proceedings.mlr.press\/v51\/ritchie16.html"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434292"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158148"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1198\/016214502753479464"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_32"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591245"},{"key":"e_1_3_2_46_2","unstructured":"Nazanin Khosravani Tehrani Nimar S. Arora Yucen Lily Li Kinjal Divesh Shah David Noursi Michael Tingley Narjes Torabi Sepehr Masouleh Eric Lippert and Erik Meijer. 2020. Bean Machine: A Declarative Probabilistic Programming Language For Efficient Programmable Inference. In International Conference on Probabilistic Graphical Models PGM 2020 23-25 September 2020 Aalborg Hotel Comwell Rebild Bakker Sk\u00f8rping Denmark (Proceedings of Machine Learning Research Vol. 138) Manfred Jaeger and Thomas Dyhre Nielsen (Eds.). PMLR 485\u2013496. http:\/\/proceedings.mlr.press\/v138\/tehrani20a.html"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3290349"},{"key":"e_1_3_2_48_2","unstructured":"Matthijs V\u00e1k\u00e1r and Luke Ong. 2018. On s-finite measures and kernels. arXiv:1810.01837 https:\/\/arxiv.org\/abs\/1810.01837"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454077"},{"key":"e_1_3_2_50_2","unstructured":"Lingfeng Yang Pat Hanrahan and Noah D. Goodman. 2014. Generating Efficient MCMC Kernels from Probabilistic Programs. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics AISTATS 2014 Reykjavik Iceland April 22-25 2014 (JMLR Workshop and Conference Proceedings). JMLR.org 1068\u20131076. http:\/\/proceedings.mlr.press\/v33\/yang14d.html"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.19080766"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T10:49:45Z","timestamp":1790074185000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3808316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,8]]},"references-count":50,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2026,6,8]]}},"alternative-id":["10.1145\/3808316"],"URL":"https:\/\/doi.org\/10.1145\/3808316","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,8]]},"assertion":[{"value":"2025-11-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}