Reactive Graphs for Efficient Markov Chain Monte Carlo Inference in Probabilistic Programming Languages
2026-06-29 • Programming Languages
Programming Languages
AI summaryⓘ
The authors propose a method to make probabilistic programs run faster by reusing parts of previous calculations when only small changes happen. They achieve this by automatically turning these programs into a dynamic graph that tracks which parts depend on which variables, so only the necessary parts get recalculated during inference. Their approach builds on ideas from functional programming, linking different programming patterns to types of probabilistic models like Bayesian networks and universal probabilistic languages.
probabilistic programmingMarkov chain Monte Carlodynamic graphfunctional reactive programmingdata dependenciesapplicative functormonadsBayesian networksuniversal probabilistic programming
Authors
Viktor Palmkvist, Fredrik Ronquist, David Broman
Abstract
An important aspect of making inference based on a probabilistic program practical is efficiency; faster evaluation enables more work per unit of time, which can be translated into more precision. Inference via Markov chain Monte Carlo has a property that can be favorably exploited for efficiency: most proposed samples are computed as minor variations of previous samples, i.e., a clever implementation can skip computations pertaining to what is unchanged. This paper provides an approach for automatically translating a probabilistic program to a dynamic graph, reminiscent of functional reactive programming, that explicitly represents data dependencies, enabling proposals to only recompute the parts of the graph that depend on redrawn random variables. The graph-building interface follows familiar functional programming interfaces, which also connect to their expressiveness in terms of probabilistic programming: models using the applicative functor portion express Bayesian networks, while those using monads represent universal probabilistic programming languages.