Reactive Graphs for Efficient Markov Chain Monte Carlo Inference in Probabilistic Programming Languages DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8 CCS: Mathematics of computing Markov-chain Monte Carlo methods CCS: Software and its engineering Functional languages
Viktor Palmkvist, Fredrik Ronquist, David Broman · 2026
Read Reactive Graphs for Efficient Markov Chain Monte Carlo Inference in Probabilistic Programming Languages DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8 CCS: Mathematics of computing Markov-chain Monte Carlo methods CCS: Software and its engineering Functional languages by Viktor Palmkvist, Fredrik Ronquist, David Broman (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30137.txt.
Introduction
Viktor Palmkvist, Fredrik Ronquist, and David Broman speed up Bayesian inference inside probabilistic programming languages. Markov chain Monte Carlo explores a model's posterior by proposing small sample changes. Most proposals alter only a small part of the previous sample. A clever implementation should skip recomputing everything else. Their approach makes that skipping automatic and safe.
A program is translated into a dynamic reactive graph. The graph records in full which parts depend on which data. A proposal then recomputes only nodes that use redrawn variables. The graph interface mirrors familiar functional style tools. Models using only the applicative part match Bayesian networks. Models using monads reach the full power of universal such languages. Efficiency grows because unchanged work is never repeated needlessly. The design keeps the programmer's view simple throughout.
Catalog record
| CREATOR | Viktor Palmkvist, Fredrik Ronquist, David Broman |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30137
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reactive Graphs for Efficient Markov Chain Monte Carlo Inference in Probabilistic Programming Languages DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8 CCS: Mathematics of computing Markov-chain Monte Carlo methods CCS: Software and its engineering Functional languages 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. 1. Introduction Many scientific disciplines involve the analysis of phenomena that are either random in nature, or can favorably be modelled as random processes. Examples include phylogenetics Yang 2006 , economics Ray et al. 2008 , and epidemiology Duarte et al. 2023 . Some of these problems can be modelled and solved analytically, giving exact results, but many cannot; they require sophisticated inference methods to provide sufficiently accurate approximate results. Fortunately, much work has been done on such inference methods, e.g., sequential Monte Carlo (SMC) Smith 2013 , Markov chain Monte Carlo (MCMC) Gilks et al. 1995 , and variational inference (VI) Wainwright & Jordan 2008 . Each of these present different trade-offs, both theoretically and practically. For example, SMC and MCMC are precise at the limit (i.e., given infinite computation time) while VI can only choose the best fit amongst a user-supplied family of distributions, whether that is accurate or not, though it often runs faster than the other two. SMC and MCMC are thus often used when the target distribution is unknown, or too difficult to express in the distributional form required by VI. For Bayesian phylogenetic inference in particular, which motivates our work, SMC has never gained much traction Štrumbelj et al. 2024 . Instead, MCMC or one of its many variations Horowitz 1991 ; Homan & Gelman 2014 ; Syed et al. 2022 tends to be the inference method of choice. Efficient inference depends not only on the inference method used, but also on the means by which the probabilistic model is expressed, along with how the inference method is implemented. A probabilistic programming language (PPL) lets a user describe a probabilistic model in the form of a program Kozen 1979 . Such a program can a) sample from simpler distributions, including distributions depending on previously sampled values, b) condition values, for example on observed data, and c) export values to be inferred. PPLs inherit the expressiveness and flexibility of programming languages, but also the difficulty of analysis. This is especially true if the PPL is universal. We refer to a PPL as universal if it supports models with a statically unbounded number of random variables. This stands in contrast with classical Bayesian networks, whose models have statically fixed numbers of random variables. This paper focuses on efficiently supporting Markov chain Monte Carlo (MCMC) inference using the Metropolis-Hastings algorithm Metropolis et al. 1953 ; Hastings 1970 on models written in a universal PPL. In brief, inference produces one sample at a time by drawing a proposal and then randomly accepting or rejecting it based on its likelihood relative to the previous sample. If the proposal is accepted, then that is the next sample, otherwise we repeat the previous sample. In a PPL we typically produce the proposal by randomly redrawing a subset of the random variables present in the model. This has an important performance implication: we should only need to recompute the parts of the model that depend on the redrawn random variables; everything else can be reused as-is. Of course, this is not a new observation. For example, approaches using more restrictive modelling approaches, e.g., the graphical models of RevBayes Höhna et al. 2014 , tend to build graph-representations of their models that explicitly represent such data-dependencies, and Bayesian networks are graph-like by definition. In the space of PPLs, C3 Ritchie et al. 2016 uses continuation passing style and function caching to start execution at changed random variables and skip unchanged computations, respectively. Finally, Bali-Phy Redelings 2021 has a new release 1 1 1 https://github.com/bredelings/BAli-Phy/releases/tag/4.1 which appears to similarly build a graph for a more expressive PPL, though the details are not immediately obvious from the implementation. In this paper we solve this problem in a principled way by connecting the well-explored concept of functional reactive programming (FRP) Elliott & Hudak 1997 to PPLs. FRP centers around graphs of dependent values, where changes in dependencies are propagated to dependent values automatically, along with sources that can trigger changes and sinks that do not propagate changes. Broadly speaking, our approach can be summarized in three points: • Our graphs have random variables as the only kind of source available, propagating a concrete sample. At the same time, each random variable is a sink, consuming the distribution of the random variable (which affects the likelihood of the proposal) without necessarily updating the sample drawn from it. • Likelihood is updated by dedicated sink nodes, and tracked as hidden state inside the graph. • We add support for the rejection of a proposal by adding a transactional interface; changes caused by redrawing a set of random variables can be rolled back. A subtle but particularly important insight is that a graph represents a single run of a model, not the model itself. This means that even if the model contains recursion, the graph remains acyclic. Instead, certain nodes will contain “sub-graphs” representing the actual choices made in the sample, roughly equivalent with the execution trace of an ordinary program. However, each node contains enough information such that the graph can be modified to represent any possible sample from the model, e.g., by storing the recursive functions present in the original model, but the graph itself remains finite. Similar to FRP, the core of the graph-building interface forms a Monad , with two additional probabilistic constructs: assume for introducing new random variables and weight for conditioning. The standard Functor , Applicative , and Monad interfaces also have a nice connection to expressivity: models using Functor and Applicative are as expressive as Bayesian networks, while Monad brings universality. In this paper we make the following contributions: • An overarching approach for using a modified version of FRP for efficient MCMC inference (Section 2 ). • An interface for manually building graphs and using them to write model-specific inference (Section 3 ). • An implementation of the aforementioned interface using internal mutability (Section 4 ). • A sketch of an automatic translation from TreePPL Senderov et al. 2023 , a high-level universal probabilistic programming language, to a graph-building