Efficiently Vectorized MCMC on Modern Accelerators

Hugh Dance, Pierre Glaser, Peter Orbanz, Ryan Adams · 2025

Read Efficiently Vectorized MCMC on Modern Accelerators by Hugh Dance, Pierre Glaser, Peter Orbanz, Ryan Adams (2025) 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-2503-17405.txt.

Introduction

Hugh Dance, Pierre Glaser, Peter Orbanz, and Ryan Adams speed up a class of sampling methods used to explore probability landscapes. These methods, called MCMC, often run many chains side by side on modern chips. A snag is that all chains must wait for the slowest one at each step, which wastes the chip's power.

The team recasts single-chain methods as small state machines, a design that removes the waiting when chains are run in parallel by auto-vector tools. A simple model gives an exact form for the speed gain and guides design choices. Three popular samplers were rebuilt this way, with gains of up to ten times in tests.

Catalog record

CREATORHugh Dance, Pierre Glaser, Peter Orbanz, Ryan Adams
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-17405

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficiently Vectorized MCMC on Modern Accelerators Hugh Dance, Pierre Glaser, Peter Orbanz, Ryan Adams Abstract With the advent of automatic vectorization tools (e.g., JAX’s vmap ), writing multi-chain MCMC algorithms is often now as simple as invoking those tools on single-chain code. Whilst convenient, for various MCMC algorithms this results in a synchronization problem—loosely speaking, at each iteration all chains running in parallel must wait until the last chain has finished drawing its sample. In this work, we show how to design single-chain MCMC algorithms in a way that avoids synchronization overheads when vectorizing with tools like vmap , by using the framework of finite state machines (FSMs). Using a simplified model, we derive an exact theoretical form of the obtainable speed-ups using our approach, and use it to make principled recommendations for optimal algorithm design. We implement several popular MCMC algorithms as FSMs, including Elliptical Slice Sampling, HMC-NUTS, and Delayed Rejection, demonstrating speed-ups of up to an order of magnitude in experiments. 1 Introduction Automatic vectorization is the act of transforming a function to handle batches of inputs without user intervention. Implementations of automatic vectorization algorithms are now available in many mainstream scientific computing libraries, and have dramatically simplified the task of running multiple instances of a single algorithm concurrently. They are routinely used to train neural networks ( Flax,, 2023 ) and in other scientific applications, e.g., Schoenholz and Cubuk, (2021) ; Oktay et al., (2023) ; Pfau et al., (2020) . This paper focuses on the use of automatic vectorization for Markov chain Monte Carlo (MCMC) algorithms. Tools like JAX’s vmap provide a convenient way to run multiple MCMC chains in parallel: one can simply write single-chain MCMC code, and call vmap to turn it into vectorized, multi-chain code that can run in parallel on the same processor. Many state-of-the-art MCMC libraries have consequently adopted machine learning frameworks with automatic vectorization tools as their backend. One limitation with automatic vectorization tools is how they handle control flow. Since all instructions must be executed in lock-step, if the algorithm has a while loop, all chains must wait until the last chain has finished its iterations. This can lead to large inefficiencies for MCMC algorithms that generate each sample using variable-length while loops. Roughly speaking, if vectorization executes, say, 100 chains in parallel, all but one finish after at most 10 steps, and the remaining chain runs for 1000 steps, then about 99% of the GPU capacity assigned to vmap is wasted (and our simulations show the effect can indeed be this drastic). For the No-U-Turn Sampler (HMC-NUTS) ( Hoffman et al.,, 2014 ) , this problem is well-documented ( BlackJax,, 2019 ; Sountsov et al.,, 2024 ; Radul et al.,, 2020 ) . It also affects various other algorithms, such as variants of slice sampling ( Neal,, 2003 ; Murray et al.,, 2010 ; Cabezas and Nemeth,, 2023 ) , delayed rejection methods ( Mira et al.,, 2001 ; Modi et al.,, 2024 ) and unbiased Gibbs sampling ( Qiu et al.,, 2019 ) . In this work, we show how to transform MCMC algorithms into equivalent samplers that avoid these synchronization barriers when using vmap -style vectorization. In particular, 1. We develop a novel approach to transform MCMC algorithms into finite state machines (FSMs), that can avoid synchronization barriers with vmap . 2. We analyze the time complexity of our FSMs against standard MCMC implementations and derive a theoretical bound on the speed-up under a simplified model. 3. We use our analysis to develop principled recommendations for optimal FSM design, which enable us to nearly obtain the theoretical bound in speed-ups for certain MCMC algorithms. 4. We implement popular MCMC algorithms as FSMs, including Elliptical Slice Sampling, HMC-NUTS, and Delayed-Rejection MH - demonstrating speed-ups of up to an order of magnitude in experiments. 2 Background and Problem Setup In this section, we briefly review how MCMC algorithms are vectorized, explain the synchronization problems that can arise, and formalize the problem mathematically. 2.1 MCMC Algorithms and Vectorization MCMC methods aim to draw samples from a target distribution \pi (typically on a subset of \mathbb{R}^{d} ) which is challenging to sample from directly. To do so, they generate samples \{\bm{x}_{1},...,\bm{x}_{n}\}\in\mathbb{R}^{d\times n} from a Markov chain with transition kernel P and invariant distribution \pi , by starting from an initial state \bm{x}_{0}\in\mathbb{R}^{d} and iteratively sampling \bm{x}_{i+1}\sim P(\cdot|\bm{x}_{i}) . For aperiodic and irreducible Markov chains, as n\to\infty the samples will converge in distribution to \pi ( Brooks et al.,, 2011 ) . In practice, P is implemented by a deterministic function sample , which takes in the current state \bm{x}_{i} and a pseudo-random state r_{i}\in\mathbb{N} , and returns new states \bm{x}_{i+1} and r_{i+1} . This procedure is given in Algorithm 1 . Algorithm 1 MCMC algorithm with sample function 1: Inputs : sample \bm{x}_{0} , seed r_{0} 2: for i\in\{1,...,n\} do 3: generate {\bm{x}}_{i},r_{i}\leftarrow\verb|sample(|{\bm{x}}_{i-1},r_{i-1}\verb|)| 4: end for 5: return {\bm{x}}_{1},\ldots,{\bm{x}}_{n} Practitioners commonly run Algorithm 1 on m different initializations, producing m chains of samples. Given an implementation of sample :\mathbb{R}^{d}\times\mathbb{N}\to\mathbb{R}^{d}\times\mathbb{N} , one way to do this is to use an automatic vectorization tool like JAX’s vmap 1 1 1 We use JAX and its vectorization map vmap throughout, since this framework is widely adopted. Similar constructs exist in TensorFlow ( vectorized_map ) and PyTorch ( vmap ). . vmap takes sample as an input and returns a new program, vmap(sample) :\mathbb{R}^{d\times m}\times\mathbb{N}^{m}\to\mathbb{R}^{d\times m}\times\mathbb{N}^{m} , which operates on a batch of inputs collected into tensors \displaystyle\tilde{{\bm{x}}}_{i-1}\; \displaystyle:=\;({\bm{x}}_{i-1,1},\ldots,{\bm{x}}_{i-1,m})\;\in\;\mathbb{R}^{d\times m} \displaystyle\tilde{r}_{i-1}\; \displaystyle:=\;(r_{i-1,1},\ldots,r_{i-1,m})\;\in\;\mathbb{N}^{m}\; and returns the corresponding outputs from sample . One can therefore turn Algorithm 1 into a multi-chain algorithm by simply replacing sample with vmap(sample) and replacing (\bm{x}_{0},r_{0}) by (\tilde{\bm{x}}_{0},\tilde{r}_{0}) (see Algorithm 6 in Appendix B ). Under the hood, vmap transforms every instruction in sample (e.g., a dot product) into a corresponding instruction operating on a batch of inputs (e.g., matrix-vector multiplication); that is, it ‘vectorizes’ sample . These instructions are executed in lock-step across all chains. Using vmap usually yields code that performs as well as manually-batched code. For this reason, as well as its simplicity and composability with other transformations like grad (for automatic differentiation) and jit (for Just-In-Time compilation), vmap has been adopted by major MCMC libraries such as NumPyro and BlackJAX. 2.2 Synchronization Problems with While Loops Control flow (i.e., if/else , while , for , etc.) poses a challenge for vectorization, because different batch members may require a different sequence of instructions. vmap solves this by executing all instructions for all batch members, and masking out irrelevant computations. As a consequence, if sample contains a while loop, then vmap(sample) will execute the body of this loop for all chains until all termination conditions are met. Until then, no further instruction can be executed. As a result, if there is high variation in the number of loop iterations across chains, running Algorithm 1 with vmap(sample) introduces a synchronization barrier across all chains: at every iteration, each chain has to wait for the slowest sample call . This issue arises in practice, because a number of important MCMC algorithms have while loops in their sample implementations: such as variants of slice sampling ( Neal,, 2003 ; Murray et al.,,

Read the complete text