# flip-hoisting: Exploiting Repeated Parameters in Discrete Probabilistic Programs

arXiv: https://arxiv.org/abs/2110.10284 · HTML: https://mlsanity.com/paper/2110.10284/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 45 references that are in the map.
- First posted on arXiv 19 Oct 2021.

## Builds on (most cited first, 10 of 10)

- [Context-Specific Independence in Bayesian Networks](https://mlsanity.com/paper/1302.3562/) (2013)
- [Deep Amortized Inference for Probabilistic Programs](https://mlsanity.com/paper/1610.05735/) (2016)
- [Automatic Reparameterisation of Probabilistic Programs](https://mlsanity.com/paper/1906.03028/) (2019)
- [SPPL: Probabilistic Programming with Fast Exact Symbolic Inference](https://mlsanity.com/paper/2010.03485/) (2020)
- [ADDMC: Weighted Model Counting with Algebraic Decision Diagrams](https://mlsanity.com/paper/1907.05000/) (2019)
- [Divide, Conquer, and Combine: a New Inference Strategy for Probabilistic Programs with Stochastic Support](https://mlsanity.com/paper/1910.13324/) (2019)
- [Delayed Sampling and Automatic Rao-Blackwellization of Probabilistic Programs](https://mlsanity.com/paper/1708.07787/) (2017)
- [AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models](https://mlsanity.com/paper/1401.3448/) (2014)
- [Autoconj: Recognizing and Exploiting Conjugacy Without a Domain-Specific Language](https://mlsanity.com/paper/1811.11926/) (2018)
- [Model Checking Finite-Horizon Markov Chains with Probabilistic Inference](https://mlsanity.com/paper/2105.12326/) (2021)

## Built on by (most cited first, 1 of 1)

- [Inference Plans for Hybrid Particle Filtering](https://mlsanity.com/paper/2408.11283/) (2024)

## Abstract (arXiv)

Many of today's probabilistic programming languages (PPLs) have brittle inference performance: the performance of the underlying inference algorithm is very sensitive to the precise way in which the probabilistic program is written. A standard way of addressing this challenge in traditional programming languages is via program optimizations, which seek to unburden the programmer from writing low-level performant code, freeing them to work at a higher-level of abstraction. The arsenal of applicable program optimizations for PPLs to choose from is scarce in comparison to traditional programs; few of today's PPLs offer significant forms of automated program optimization. In this work we develop a new family of program optimizations specific to discrete-valued knowledge compilation based PPLs. We identify a particular form of program structure unique to these PPLs that tangibly affects exact inference performance in these programs: redundant random variables -- variables with repeated parameters and inconsistent path conditions. We develop a new program analysis and associated optimization called flip-hoisting that identifies these redundancies and optimizes them into a single random variable. We show that flip-hoisting yields inference speedups of up to 60% on applications of probabilistic programs such as Bayesian networks and probabilistic verification.