Lightweight Implementations of Probabilistic Programming Languages Via Transformational Compilation

David Wingate, Andreas Stuhlmüller, Noah D. GoodmanAISTATS 2011

Introduction

Probabilistic Programming Languages (PPLs) provide a powerful framework for defining stochastic models using the expressive power of general-purpose programming. However, widespread adoption has been hindered by performance bottlenecks and the engineering overhead of building custom interpreters. This paper presents a "lightweight" approach to PPL implementation through transformational compilation, enabling efficient inference in existing languages with minimal modifications.

The Performance-Engineering Trade-off

Traditional PPLs often rely on heavy-duty, custom-built interpreters to manage the state of random variables during inference. This approach introduces significant execution overhead compared to native code and isolates the PPL from established software ecosystems, such as high-performance math libraries or GPU-accelerated functions. The authors propose a method to "wrap" standard languages, leveraging their native compilers to achieve near-native execution speeds while maintaining the flexibility of a PPL.

Core Methodology: Transformational Compilation

The central innovation is the use of a source-to-source compiler to rewrite standard programs into a form suitable for Markov Chain Monte Carlo (MCMC) inference. Instead of a new runtime, the system uses a lightweight transformation to instrument the code.

Structural Naming

For MCMC to be effective, the sampler must be able to identify and reuse random choices across different execution traces. A simple sequential naming scheme (e.g., 1, 2, 3...) fails when the control flow changes, such as when a loop iteration count varies. This "misalignment" leads to low acceptance rates in MCMC.

The authors introduce structural naming, where each random choice (Elementary Random Primitive, or ERP) is assigned a unique address based on its structural position in the execution trace—incorporating the function call stack, line numbers, and loop indices. This ensures that corresponding random choices retain the same identity across different traces, facilitating efficient value reuse.

Comparison of naive vs. structural naming schemes. Structural naming ensures that random choices remain aligned across different execution traces, even when the number of iterations changes.

The MCMC Engine

The inference engine maintains a database of these structurally named choices. During a proposal step, the system modifies a value in the database and re-executes the transformed program. Because the program is compiled to look up values by their structural address, it can efficiently compute the likelihood of the new trace by reusing the majority of the previous state.

Evaluation and Results

The approach was evaluated using Bher (a compiled version of the Scheme-based Church language) and Stochastic Matlab. The researchers tested these implementations on several models, including Hidden Markov Models (HMM) and Latent Dirichlet Allocation (LDA).

Key results include:

  • Performance Gains: In HMM inference, Bher significantly outperformed the interpreted MIT-Church, demonstrating the advantages of leveraging native compilation.
  • Scalability: On LDA tasks, Bher remained competitive with more complex systems. While specialized caching in MIT-Church provided benefits for very large document sets, Bher's lightweight implementation (approx. 1,600 lines of code) achieved high efficiency with far less engineering effort.
  • Extensibility: Stochastic Matlab successfully integrated a GPU-based geological modeling function, proving that this lightweight approach can easily incorporate high-performance external code.
Inference performance comparison for HMM and LDA models. Bher shows significant speedups over the interpreted MIT-Church, particularly as model complexity increases.

Conclusion and Future Work

By shifting the burden of PPL implementation from custom runtimes to source-to-source transformation and structural addressing, the authors demonstrate a path toward high-performance, extensible probabilistic programming. Future work includes exploring more advanced MCMC kernels and applying these techniques to imperative languages like Python to further broaden the accessibility of probabilistic modeling.

Summary updated

BibTeX
@article{wingate2011lightweight,
  author = {David Wingate and Andreas Stuhlmüller and Noah D. Goodman},
  title = {{Lightweight Implementations of Probabilistic Programming Languages Via Transformational Compilation}},
  journal = {AISTATS},
  year = {2011},
}
Figure