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.
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.
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