Compiling Probabilistic Programs for Variable Elimination with Information Flow

Explore a 19-minute video presentation from PLDI 2024 that delves into compiling probabilistic programs for variable elimination using information flow. Learn about a novel approach to variable elimination and marginal inference in probabilistic programming languages that support bounded recursion and discrete distributions. Discover how the presented compiler eliminates probabilistic side effects and uses an innovative information-flow type system to factorize computations. Understand how this method effectively decomposes complex marginal-inference problems into tractable subproblems for recursive programs with dynamically recurring substructure. Examine the proof of compilation correctness through denotational semantics preservation and the development of a denotational, logical-relations model of information-flow types in a measure-theoretic setting. Review experimental results demonstrating the compiler's ability to subsume PTIME algorithms for recursive models and its scalability with inference problem size.