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

Abstract

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.

Fix typo in author name

References in corpus (1)

• Context-Specific Independence in Bayesian Networks

Cited by in corpus (5)

• Swift: Compiled Inference for Probabilistic Programming Languages
• Simplifying Dependent Reductions in the Polyhedral Model
• Divide, Conquer, and Combine: a New Inference Strategy for Probabilistic Programs with Stochastic Support
• PClean: Bayesian Data Cleaning at Scale with Domain-Specific Probabilistic Programming
• Accelerating Metropolis-Hastings with Lightweight Inference Compilation