Optimising Density Computations in Probabilistic Programs via Automatic Loop Vectorisation

Sangho Lim, Hyoungjin Lim, Wonyeol Lee, Xavier Rival, Hongseok Yang · 2025

Read Optimising Density Computations in Probabilistic Programs via Automatic Loop Vectorisation by Sangho Lim, Hyoungjin Lim, Wonyeol Lee, Xavier Rival, Hongseok Yang (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-2511-11070.txt.

Introduction

Sangho Lim, Hyoungjin Lim, and their colleagues present a sound method that speeds up density work in probabilistic programs by vectorising loops on its own. Such programs model uncertainty for many fields, but inference over large data sets or long sample chains is costly. Hand vectorisation is error-prone, and older automatic tools handle only simple loop shapes with heavy user help.

Their method runs loop rounds in parallel on a speculative basis, then checks with a fixed-point test that the meaning stayed the same. It is stated as a translation into a lower-level language built for vector work. A built tool shows the method is both safe and effective in practice.

Catalog record

CREATORSangho Lim, Hyoungjin Lim, Wonyeol Lee, Xavier Rival, Hongseok Yang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-11070

Browse the full library · About the Tower of Babel

Full text

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

Optimising Density Computations in Probabilistic Programs via Automatic Loop Vectorisation Journal: PACMPL Volume: 10 POPL 0 1 Thanks: This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korean Government(MSIT) (No. RS-2023-00279680). CCS: Mathematics of computing Probabilistic inference problems CCS: Computing methodologies Parallel algorithms CCS: Computing methodologies Vector / streaming algorithms Sangho Lim, Hyoungjin Lim, Wonyeol Lee, Xavier Rival, Hongseok Yang Abstract . Probabilistic programming languages (PPLs) are a popular tool for high-level modelling across many fields. They provide a range of algorithms for probabilistic inference, which analyse models by learning their parameters from a dataset or estimating their posterior distributions. However, probabilistic inference is known to be very costly. One of the bottlenecks of probabilistic inference stems from the iteration over entries of a large dataset or a long series of random samples. Vectorisation can mitigate this cost, but manual vectorisation is error-prone, and existing automatic techniques are often ad-hoc and limited, unable to handle general repetition structures, such as nested loops and loops with data-dependent control flow, without significant user intervention. To address this bottleneck, we propose a sound and effective method for automatically vectorising loops in probabilistic programs. Our method achieves high throughput using speculative parallel execution of loop iterations, while preserving the semantics of the original loop through a fixed-point check. We formalise our method as a translation from an imperative PPL into a lower-level target language with primitives geared towards vectorisation. We implemented our method for the Pyro PPL and evaluated it on a range of probabilistic models. Our experiments show significant performance gains against an existing vectorisation baseline, achieving 1.1 1.1 – 6 × 6\times speedups and reducing GPU memory usage in many cases. Unlike the baseline, which is limited to a subset of models, our method effectively handled all the tested models. 1. Introduction Over the last two decades, probabilistic programming languages (PPLs) have emerged as important tools for expressing and reasoning about models in machine learning, statistics, and computational science ( Pyro ; NumPyro ; PyMC ; Anglican ; Edward2 ; Turing ; Stan ) . They are used to analyse datasets from epidemiology ( epidemiology:21 ; epidemiology:22 ) and ecology ( ecology:22 ; ecology:24 ) to phylogenetics ( phylogenetics:23 ) and robotics ( robotics:23 ; robotics:24 ) . PPLs enable users to model probabilistic phenomena naturally using primitives for probabilistic sampling and conditioning, as well as features from general-purpose programming languages, such as loops, branches, and more recently, trainable parameters (e.g., neural networks). These models are then analysed using generic inference engines of PPLs, which approximate posterior distributions or learn model parameters by performing algorithms from Bayesian statistics and deep learning, such as Hamiltonian Monte Carlo (HMC) ( HMCphy ; HMCcs ) , Stochastic Variational Inference (SVI) ( SVI ) , and Stochastic Gradient Descent (SGD) ( SGD:51 ; SGD:52 ) . This paper aims to reduce the high computational cost of PPL inference engines, a challenge that persists despite advances in statistical algorithms and compilation. Our work focuses on scenarios requiring repeated evaluation of probabilistic programs during parameter learning or posterior inference, particularly those involving intensive computations of model densities and their gradients arising from repetition structures, often implemented as for-loops. We develop a sound automatic method for optimising such loops through tensor-based vectorisation, thereby enabling the underlying inference engines to analyse these models more efficiently. Models with repetition structures are common in practice. Graphical models from statistics even employs a special notation, called plate , to compactly describe such structures. The simplest repetition structure is a loop over a dataset where each iteration is independent of the others in the sense that it does not have data dependency from the other iterations. Our optimisation allows the inference engines to process such loops in parallel using tensors, yielding significant benefits for medium-to-large datasets. More challenging examples come from sequence models and hierarchical models, such as Bayesian hierarchical models ( hierarchical:03 ; hierarchical:19 ) and hidden Markov models ( hmm:09 ) , where repetition structures are implemented as nested loops, or they lack independence and are coded as loops whose iterations are data-dependent on the previous ones. Even in these complex scenarios, our optimisation enables the inference engines to identify the available parallelism and exploit it through tensor-based vectorisation, achieving significant speedups in posterior inference and parameter learning. Speeding up PPL inference engines using tensor-based vectorisation is a known idea in the PPL community, supported by a range of existing primitives, such as vmap ( jax ) , vectorized_map ( vectorized-map ) , vectorized_markov ( funsor:2019 ) , and the MarkovChain distribution ( tensorflow-probability ) . However, these primitives fall short of fully automatic vectorisation of the general repetition structures that we target. Concretely, they require users to write repetition structures explicitly in vectorised form, or to provide vectorisation-related information, e.g., dependency information in the repetition structures. This task is both cumbersome and error-prone; for example, manually vectorising the loop in Figure 1 requires care due to inter-iteration data dependencies, as detailed in Section 2 . Moreover, these primitives are limited, and cannot handle nested repetition structures or dynamically varying dependencies arising from internal random choices; they often support only repetition without data dependencies. In contrast, our vectorisation is fully automatic, requires no user input, and correctly handles general repetition structures, including nested ones and those with complex, randomly-varying dependencies. When viewed as a code transformer, our optimisation can be understood as a non-standard loop vectoriser. Given a model with a repetition structure expressed as a for-loop over \{0,1,\ldots,n-1\} , our optimisation transforms the loop to parallelism-friendly tensor-based vectorised code. The vectorised code here is subtle, which goes beyond the simple standard idea of executing all the n iterations of the original loop in parallel. To handle the case that the iterations of the loop are data-dependent, the code implements two novel ideas: (i) speculative execution of the loop body, and (ii) the use of a fixed-point check for testing the validity of speculation. (i) The code runs all the n iterations of the original loop in parallel, but some iterations are speculative in the sense that their starting states may differ from those of the corresponding iterations in the original loop. This speculation lets the code avoid waiting until the starting states of all the iterations of the original loop are known. But the outcomes of these speculative computations may diverge from those of the corresponding iterations of the original loop. (ii) To address this divergence issue, the code repeats the parallel (and partly speculative) execution of all the n iterations of the loop multiple times, and terminates this repetition when it finds out that all the speculative executions in the current repetition are correct, i.e., they correspond to the n iterations of the original loop. The termination mechanism here employs a fixed-point check to detect the correctness of speculation, and it is guaranteed to stop the repetition within at most n iterations (due to a particular type of speculation we use). For instance, as we explain in Section 3 , our optimisation transforms the loop of Figure 1 into vectorised code with a fixed-point check, which ensures that the parallel execution of the original

Read the complete text