C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching

By Daniel Ritchie, Andreas Stuhlmüller, Noah D. Goodman. 2015

33 citations recorded by the source corpus.

Lightweight, source-to-source transformation approaches to implementing MCMC for probabilistic programming languages are popular for their simplicity, support of existing deterministic code, and ability to execute on existing fast runtimes. However, they are also slow, requiring a complete re-execution of the program on every Metropolis Hastings proposal. We present a new extension to the lightweight approach, C3, which enables efficient, incrementalized re-execution of MH proposals. C3 is based on two core ideas: transforming probabilistic programs into continuation passing style (CPS), and caching the results of function calls. We show that on several common models, C3 reduces proposal runtime by 20-100x, in some cases reducing runtime complexity from linear in model size to constant. We also demonstrate nearly an order of magnitude speedup on a complex inverse procedural modeling application.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Hardware and Architecture, Probabilistic & Bayesian Methods, Program Analysis & Verification

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Vikash K. Mansinghka

In Probabilistic & Bayesian Methods

In Program Analysis & Verification

Citations in the corpus

Gen: a general-purpose probabilistic programming system with programmable inference (2019, methodology): “However, existing systems either lack Gen’s modeling flexibility [29], are restricted to single-variable updates [51, 69], and/or have very high runtime overhead [40].”
Bean Machine: A Declarative Probabilistic Programming Language For Efficient Programmable Inference (2020, background): “C3 (Ritchie et al., 2016) proposes another solution that requires that models be written in a speciﬁc style that allows the DAG to be inferred.”