A New Approach to Probabilistic Programming Inference

Frank Wood, Jan Willem van de Meent, Vikash Mansinghka

TL;DR

This paper introduces a powerful new inference framework for Turing-complete probabilistic programming languages (PPLs) using Particle Markov Chain Monte Carlo (PMCMC). By leveraging Sequential Monte Carlo to propose multi-variable updates simultaneously, this approach significantly outperforms traditional single-site Metropolis-Hastings methods in complex models with dense conditional dependencies.

What Problem Does This Paper Address?

Probabilistic programming languages (PPLs) allow developers to define complex statistical models as computer programs. However, performing inference—computing the conditional distribution of latent variables given observed data—is incredibly challenging, especially for Turing-complete languages that feature stochastic recursion and dynamic control flow.

Traditional PPL inference engines rely heavily on single-site Metropolis-Hastings (MH) algorithms, often referred to as "Random Database" (RDB) samplers. These samplers propose changes to only one random variable at a time. While simple, this single-site approach is highly inefficient for expressive models with dense conditional dependencies, where variables are tightly coupled. Exploring the execution space this way becomes a massive computational bottleneck.

Methods

The authors propose using Particle Markov Chain Monte Carlo (PMCMC)—specifically a variant called Particle-Gibbs (PG)—to drive inference in PPLs.

Instead of updating a single variable at a time, PMCMC runs an internal Sequential Monte Carlo (SMC) sweep to generate proposals. In each sweep, a "retained" execution trace from the previous step is mixed into the particle pool. This ensures that the algorithm remains a valid MH transition operator that always accepts. As a result, the sampler can update multiple variables at once across entire execution traces.

The authors implemented this method within Anglican, an expressive PPL. The paper highlights an evolution from an older interpreted version of Anglican to a newer compiled version that uses a continuation-passing style (CPS) transformation to compile programs directly into Java Virtual Machine (JVM) bytecode via Clojure, yielding a 10x to 100x speedup.

Datasets

Rather than using standard external machine learning datasets, the authors evaluate their approach using four distinct synthetic benchmark programs designed as "conditional measure tests":

  1. HMM: A Hidden Markov Model with continuous observations to test state estimation.
  2. DP Mixture: An uncollapsed Dirichlet Process mixture of Gaussians to evaluate Bayesian nonparametric primitives.
  3. Branching: A multimodal deterministic recursion program with no fixed graphical model structure, testing dynamic execution paths.
  4. Marsaglia: A recursive rejection-sampling algorithm used to infer the mean of a univariate normal distribution.

Key Insights and Ideas

  • Multi-Variable Updates: The core "aha" moment is that by treating entire execution traces as particles, PMCMC can make sweeping changes to many variables simultaneously, bypassing the slow exploration bottlenecks of single-site MH.
  • Code Ordering Matters: Unlike traditional graphical models where structure is purely declarative, PPL execution order matters. Pushing observe statements earlier in the code allows PMCMC to re-weight particles sooner, drastically improving efficiency. Interestingly, single-site MH (RDB) is entirely invariant to this line permutation.
  • The Cost of Rejection: For recursive rejection samplers (like Marsaglia), PMCMC can actually be slower than RDB. PMCMC spends computational effort exploring long, rejected execution paths, whereas RDB's implicit geometric prior naturally avoids paying excess computational costs on unnecessarily long traces.

Key Results

The authors compared PMCMC (using 100 particles) against the RDB sampler across their four benchmark programs:

Figure 1: Comparative conditional measure test performance: PMCMC with 100 particles vs. RDB.
  • Expressive Models: In models with rich conditional dependencies (HMM and DP Mixture), PMCMC converged significantly faster than RDB relative to the number of simulations, wall-clock time, and function application counts (as shown in Figure 1a and 1b).
  • Robustness to Bad Coding: For the DP Mixture, PMCMC outperformed RDB on all program reorderings, even when the code was structured in an adversarial, non-optimal ordering.
  • Simple Models: For the Branching program (Figure 1c), which features only one observation and a single named random variable, PMCMC and RDB achieved virtually indistinguishable performance, proving that PMCMC does not introduce a massive statistical penalty for simpler tasks.

Limitations and Future Work

  • Latency in Single-Threading: Single-threaded implementations of PMCMC suffer from latency because they must complete a full batch of simulations (equal to the number of particles) before emitting any predict outputs.
  • Parallelization Bottlenecks: Although PMCMC is conceptually easy to parallelize, the Anglican implementation at the time faced memory organization sub-optimalities that led to excessive locking overhead in multi-threaded environments.
  • Soft Constraints Only: The language syntactically forces observe statements to be noisy (soft constraints). Hard constraints require a Dirac likelihood, which the authors intentionally omit to prevent users from writing non-computable, NP-hard trace-finding problems.
  • Future Directions: The authors suggest exploring automatic code optimization to automatically push observe statements forward, as well as hybrid samplers that combine conditional SMC with RDB MH by partitioning program variables.

Summary updated

Abstract

We introduce and demonstrate a new approach to inference in expressive probabilistic programming languages based on particle Markov chain Monte Carlo. Our approach is simple to implement and easy to parallelize. It applies to Turing-complete probabilistic programming languages and supports accurate inference in models that make use of complex control flow, including stochastic recursion. It also includes primitives from Bayesian nonparametric statistics. Our experiments show that this approach can be more efficient than previously introduced single-site Metropolis-Hastings methods.
BibTeX
@inproceedings{wood2014new,
  author = {Frank Wood and Jan Willem van de Meent and Vikash Mansinghka},
  title = {{A New Approach to Probabilistic Programming Inference}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2014},
  url = {https://openreview.net/forum?id=xUVbMHxuOXs},
}
Figure