C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching
This addresses a performance bottleneck for researchers and practitioners using probabilistic programming languages, offering incremental improvements to existing lightweight MCMC approaches.
The paper tackles the inefficiency of lightweight MCMC methods in probabilistic programming, which require full program re-execution per proposal, by introducing C3, a technique using continuation passing style and callsite caching to enable incremental re-execution. The result is a 20-100x reduction in proposal runtime, with some cases shifting from linear to constant complexity in model size.
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.