Abstract
We develop a new Low-level, First-order Probabilistic Programming Language (LF-PPL) suited for models containing a mix of continuous, discrete, and/or piecewise-continuous variables. The key success of this language and its compilation scheme is in its ability to automatically distinguish parameters the density function is discontinuous with respect to, while further providing runtime checks for boundary crossings. This enables the introduction of new inference engines that are able to exploit gradient information, while remaining efficient for models which are not everywhere differentiable. We demonstrate this ability by incorporating a discontinuous Hamiltonian Monte Carlo (DHMC) inference engine that is able to deliver automated and efficient inference for non-differentiable models. Our system is backed up by a mathematical formalism that ensures that any model expressed in this language has a density with measure zero discontinuities to maintain the validity of the inference engine.
1. Introduction
Modern Probabilistic Programming Systems (PPSs) such as Stan, PyMC3, and Pyro have revolutionized statistical modeling by providing access to efficient gradient-based inference algorithms like Hamiltonian Monte Carlo (HMC). However, these algorithms typically require the target probability density to be differentiable. When models incorporate discrete variables or control flow (e.g., if-else branching), they introduce discontinuities that can cause standard HMC integrators to fail, leading to rejected samples and poor scaling.
While specialized algorithms like Discontinuous Hamiltonian Monte Carlo (DHMC) can handle these scenarios, they traditionally require manual identification of discontinuous variables and boundary tracking. This paper introduces LF-PPL, a low-level probabilistic programming language and compilation scheme that automates this process, enabling gradient-based inference for non-differentiable models out-of-the-box.
2. Methodology
LF-PPL is designed to expose discontinuity information directly to the inference engine through a novel compilation pipeline.
2.1 Linearized Intermediate Representation (LIR)
The compiler translates programs into a graph-based LIR that tracks both probabilistic and control-flow dependencies. By recognizing that non-differentiability in probabilistic programs primarily arises from branching (if statements), the compiler performs static analysis to automatically classify variables. Any random variable that can alter a control-flow path is flagged as "discontinuous," while others are treated as "continuous."
2.2 Runtime Boundary Detection
To handle discontinuities during sampling, LF-PPL assigns a unique boolean variable to every if predicate. A state change in these booleans during the integration step serves as a computationally efficient signal that a discontinuity boundary has been crossed. This allows the DHMC engine to apply a coordinate-wise integrator for discontinuous variables and a standard leapfrog integrator for continuous ones.
2.3 Mathematical Foundations
The language restricts primitive operations to analytic functions, allowing the authors to formally prove that any program compiled in LF-PPL results in a density function where discontinuities form a measure-zero set. This guarantee is essential for maintaining the mathematical validity of the DHMC sampler.
3. Experimental Evaluation
3.1 Baseline Performance: Gaussian Mixture Model
The system was first evaluated on a classic Gaussian Mixture Model (GMM) containing mixed continuous and discrete variables. As shown in Figure 1, the automated DHMC implementation in LF-PPL achieved Mean Squared Error (MSE) performance comparable to PyMC3's highly optimized NUTS sampler using a Metropolis-within-Gibbs strategy.
3.2 High-Dimensional Scaling: Heavy Tail Piecewise Model
To test scalability, the authors used a synthetic Heavy Tail Piecewise Model with planes of discontinuities. In this high-dimensional setting, standard HMC performance degraded rapidly as dimensionality increased from 10 to 500 due to frequent boundary collisions. In contrast, DHMC in LF-PPL maintained low error rates across all dimensions, demonstrating its ability to circumvent the curse of dimensionality in discontinuous spaces (see Figure 2).
4. Discussion and Limitations
While LF-PPL significantly advances automated inference for non-differentiable models, some challenges remain. The system can potentially generate models with "zero-density gaps" that trap the sampler, a problem that is generally mathematically intractable to detect. Additionally, the current boolean tracking method may fail to detect "double crossings" if a single large integration step crosses and then re-crosses a boundary. Future work includes using LF-PPL as a compilation target for higher-level PPLs and extending the framework to support discontinuous Stochastic Variational Inference (SVI).
Summary updated