Guaranteed Bounds for Posterior Inference in Universal Probabilistic Programming

Raven Beutner, Luke Ong, Fabian Zaiser

TL;DR

This paper introduces a novel method for computing guaranteed, non-stochastic lower and upper bounds for posterior distributions in universal probabilistic programming languages. By combining interval-based trace semantics with a "weight-aware" type system, the authors provide a rigorous way to "sandwich" the true posterior, offering a much-needed ground truth to verify the results of popular but often unreliable stochastic inference algorithms like MCMC.

What Problem Does This Paper Address?

Probabilistic Programming Languages (PPLs) allow researchers to write complex statistical models as code. However, performing "inference"—calculating the posterior distribution of variables given observed data—is notoriously difficult.

Currently, practitioners rely on two main approaches, both with significant drawbacks:

  1. Stochastic Methods (e.g., MCMC, Importance Sampling): These are approximate and provide no guarantees for finite runtimes. As shown in the paper's "Pedestrian" example, different standard algorithms can yield wildly different, and sometimes flat-out wrong, results without the user knowing.
  2. Exact Symbolic Methods: These attempt to find closed-form mathematical solutions. While precise, they generally cannot handle "universal" features like recursion or unbounded loops, which are common in complex models.

This paper addresses the gap for a rigorous, automated method that can handle universal PPL features while providing provable bounds on the results.

Methods

The authors propose a framework implemented in a tool called GuBPI (Guaranteed Bounds for Posterior Inference). The key technical innovations include:

  • Interval-Based Trace Semantics: Instead of evaluating a program on single real-valued samples, the semantics operates on interval traces. This allows the system to approximate the behavior of the program over entire sets of possible sample outcomes simultaneously.
  • Weight-Aware Interval Type System: This is a static analysis tool that automatically infers interval bounds for both the return value of a program and its "weight" (the likelihood score assigned to a path via observe or score statements). This is critical because the posterior is defined by these weights.
  • Symbolic Execution: GuBPI uses symbolic execution to explore program paths. When it encounters recursion that exceeds a depth limit, it uses the interval type system to soundly over-approximate the remaining infinite paths, ensuring the final bounds remain valid.
  • Linear Splitting Optimization: For models with linear constraints and scores, the authors use efficient volume computations of convex polytopes to speed up the calculation of bounds.

The method is proven to be sound (the true posterior is always between the bounds) and complete (the bounds can be made arbitrarily tight given enough computation).

Datasets

The authors evaluated GuBPI on several benchmark suites:

  • Probability Estimation Benchmarks: 18 programs from prior literature [56] involving uniform samples and linear guards.
  • Exact Inference Benchmarks: 21 non-recursive models from the PSI solver repository [26].
  • Recursive Models: A new set of challenging benchmarks including geometric random walks and the "Pedestrian" example, which features unbounded recursion and continuous distributions.

Key Insights and Ideas

  • Catching MCMC Failures: One of the most striking "aha moments" is the demonstration that GuBPI can definitively prove when a popular inference engine (like Pyro's HMC) has failed to converge or is ill-suited for a model. Figure 1. GuBPI's bounds (green) show that HMC samples (red) are incorrect, while Importance Sampling (blue) remains plausible.

  • Sandwiching the Truth: By providing both a lower and an upper bound, the method creates a "safe zone." If an approximate result falls outside this zone, it is guaranteed to be wrong.

  • Handling the Unbounded: Unlike symbolic solvers that simply unroll loops to a fixed depth (which changes the model's actual meaning), GuBPI uses its type system to account for the "tail" of recursive calls, maintaining the integrity of the original universal program.
Figure 1. Histogram of samples from the posterior distri- bution of Example 1.1 and wrong samples produced by the probabilistic programming system Pyro.

Key Results

  • Correctness: GuBPI's results matched exact solutions from the PSI solver in all testable cases.
  • Precision: In many probability estimation benchmarks, GuBPI produced tighter bounds than previous state-of-the-art static analysis tools, even identifying cases where those previous tools had contradictory results.
  • Pedestrian Example: For the complex recursive model defined below, GuBPI successfully ruled out erroneous HMC results in about 1.5 hours—a task that purely statistical validation methods (like SBC) struggled to do even after 300 hours of computation.
The "Pedestrian" model code in SPCF.

Limitations and Future Work

  • Path Explosion: Like all symbolic execution methods, GuBPI struggles with programs that have a massive number of execution paths (the "path explosion" problem).
  • Dimensionality: The interval-based approach scales exponentially with the number of independent random variables in the model, making it less suitable for very high-dimensional models.
  • Coarse Bounds for Fixpoints: While the type system can handle recursion, the bounds it produces for complex recursive functions can sometimes be quite loose (e.g., $[-\infty, \infty]$).

Future work aims to combine this rigorous analysis with stochastic path sampling to handle larger models and to develop more sophisticated probabilistic summaries for recursive functions.

Summary updated

Abstract

We propose a new method to approximate the posterior distribution of probabilistic programs by means of computing guaranteed bounds. The starting point of our work is an interval-based trace semantics for a recursive, higher-order probabilistic programming language with continuous distributions. Taking the form of (super-/subadditive) measures, these lower/upper bounds are non-stochastic and provably correct: using the semantics, we prove that the actual posterior of a given program is sandwiched between the lower and upper bounds (soundness); moreover the bounds converge to the posterior (completeness). As a practical and sound approximation, we introduce a weight-aware interval type system, which automatically infers interval bounds on not just the return value but also weight of program executions, simultaneously. We have built a tool implementation, called GuBPI, which automatically computes these posterior lower/upper bounds. Our evaluation on examples from the literature shows that the bounds are useful, and can even be used to recognise wrong outputs from stochastic posterior inference procedures.
BibTeX
@inproceedings{beutner2022guaranteed,
  author = {Raven Beutner and Luke Ong and Fabian Zaiser},
  title = {{Guaranteed Bounds for Posterior Inference in Universal Probabilistic Programming}},
  booktitle = {PLDI},
  year = {2022},
  url = {https://openreview.net/forum?id=k-ht_K2HCI},
}
Figure