# Scaling up Hybrid Probabilistic Inference with Logical and Arithmetic Constraints via Message Passing

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

## Key facts

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

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

- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [A Probabilistic Neuro-symbolic Layer for Algebraic Constraint Satisfaction](https://mlsanity.com/paper/2503.19466/) (2025)
- [A Unified Approach to Count-Based Weakly-Supervised Learning](https://mlsanity.com/paper/2311.13718/) (2023)
- [A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries](https://mlsanity.com/paper/2102.06137/) (2021)
- [Collapsed Inference for Bayesian Deep Learning](https://mlsanity.com/paper/2306.09686/) (2023)
- [Enhancing SMT-based Weighted Model Integration by Structure Awareness](https://mlsanity.com/paper/2302.06188/) (2023)
- [SMT-based Weighted Model Integration with Structure Awareness](https://mlsanity.com/paper/2206.13856/) (2022)
- [Measure Theoretic Weighted Model Integration](https://mlsanity.com/paper/2103.13901/) (2021)
- [The Theory and Practice of MAP Inference over Non-Convex Constraints](https://mlsanity.com/paper/2602.08681/) (2026)
- [Probabilistic ML Verification via Weighted Model Integration](https://mlsanity.com/paper/2402.04892/) (2024)

## Abstract (arXiv)

Weighted model integration (WMI) is a very appealing framework for probabilistic inference: it allows to express the complex dependencies of real-world problems where variables are both continuous and discrete, via the language of Satisfiability Modulo Theories (SMT), as well as to compute probabilistic queries with complex logical and arithmetic constraints. Yet, existing WMI solvers are not ready to scale to these problems. They either ignore the intrinsic dependency structure of the problem at all, or they are limited to too restrictive structures. To narrow this gap, we derive a factorized formalism of WMI enabling us to devise a scalable WMI solver based on message passing, MP-WMI. Namely, MP-WMI is the first WMI solver which allows to: 1) perform exact inference on the full class of tree-structured WMI problems; 2) compute all marginal densities in linear time; 3) amortize inference inter query. Experimental results show that our solver dramatically outperforms the existing WMI solvers on a large set of benchmarks.