Guaranteed bounds for posterior inference in universal probabilistic programming
summary
Provides guaranteed numeric bounds on posterior probabilities by partitioning trace space into interval traces and using interval arithmetic to bound likelihoods, then summing volumes. Implements the method in tool guppy and proves soundness and completeness. Handles continuous distributions and unbounded loops via an interval type system; uses symbolic execution and linear programming as optimizations. On examples (pedestrian model with observed distance 1.1, Nil’s funnel, mixture models) the bounds expose HMC failures and validate importance sampling; performance falls as branching or dimension grows.
AI-written summary · about