# Divide, Conquer, and Combine: a New Inference Strategy for Probabilistic Programs with Stochastic Support

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2019.

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

- [Tensor Program Optimization with Probabilistic Programs](https://mlsanity.com/paper/2205.13603/) (2022)
- [Smoothness Analysis for Probabilistic Programs with Application to Optimised Variational Inference](https://mlsanity.com/paper/2208.10530/) (2022)
- [Nonparametric Hamiltonian Monte Carlo](https://mlsanity.com/paper/2106.10238/) (2021)
- [Rethinking Variational Inference for Probabilistic Programs with Stochastic Support](https://mlsanity.com/paper/2311.00594/) (2023)
- [flip-hoisting: Exploiting Repeated Parameters in Discrete Probabilistic Programs](https://mlsanity.com/paper/2110.10284/) (2021)
- [Nonparametric Involutive Markov Chain Monte Carlo](https://mlsanity.com/paper/2211.01100/) (2022)
- [Divide, Conquer, Combine Bayesian Decision Tree Sampling](https://mlsanity.com/paper/2403.18147/) (2024)
- [Control-Data Separation and Logical Condition Propagation for Efficient Inference on Probabilistic Programs](https://mlsanity.com/paper/2101.01502/) (2021)
- [Beyond Bayesian Model Averaging over Paths in Probabilistic Programs with Stochastic Support](https://mlsanity.com/paper/2310.14888/) (2023)
- [Inference Plans for Hybrid Particle Filtering](https://mlsanity.com/paper/2408.11283/) (2024)
- [LazyHMC: Hamiltonian Monte Carlo Simulation for Lazy, Infinite Dimensional Probabilistic Programs](https://mlsanity.com/paper/2608.08588/) (2026)

## Abstract (arXiv)

Universal probabilistic programming systems (PPSs) provide a powerful framework for specifying rich probabilistic models. They further attempt to automate the process of drawing inferences from these models, but doing this successfully is severely hampered by the wide range of non--standard models they can express. As a result, although one can specify complex models in a universal PPS, the provided inference engines often fall far short of what is required. In particular, we show that they produce surprisingly unsatisfactory performance for models where the support varies between executions, often doing no better than importance sampling from the prior. To address this, we introduce a new inference framework: Divide, Conquer, and Combine, which remains efficient for such models, and show how it can be implemented as an automated and generic PPS inference engine. We empirically demonstrate substantial performance improvements over existing approaches on three examples.