# SPPL: Probabilistic Programming with Fast Exact Symbolic Inference

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

## Key facts

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

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

- [Building Machines that Learn and Think with People](https://mlsanity.com/paper/2408.03943/) (2024)
- [Neuro-Symbolic AI in 2024: A Systematic Review](https://mlsanity.com/paper/2501.05435/) (2025)
- [A Compositional Atlas for Algebraic Circuits](https://mlsanity.com/paper/2412.05481/) (2024)
- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [Scaling Integer Arithmetic in Probabilistic Programs](https://mlsanity.com/paper/2307.13837/) (2023)
- [Declarative Probabilistic Logic Programming in Discrete-Continuous Domains](https://mlsanity.com/paper/2302.10674/) (2023)
- [Total Variation Distance Meets Probabilistic Inference](https://mlsanity.com/paper/2309.09134/) (2023)
- [Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approach](https://mlsanity.com/paper/2305.17058/) (2023)
- [Estimators of Entropy and Information via Inference in Probabilistic Models](https://mlsanity.com/paper/2202.12363/) (2022)
- [Hierarchical Infinite Relational Model](https://mlsanity.com/paper/2108.07208/) (2021)
- [The Limits of Tractable Marginalization](https://mlsanity.com/paper/2506.12020/) (2025)
- [Likelihood Hacking in Probabilistic Program Synthesis](https://mlsanity.com/paper/2603.24126/) (2026)
- [flip-hoisting: Exploiting Repeated Parameters in Discrete Probabilistic Programs](https://mlsanity.com/paper/2110.10284/) (2021)
- [Guaranteed Bounds for Posterior Inference in Universal Probabilistic Programming](https://mlsanity.com/paper/2204.02948/) (2022)
- [Approximate Bayesian Inference via Bitstring Representations](https://mlsanity.com/paper/2508.13598/) (2025)
- [Top-Down Bayesian Posterior Sampling for Sum-Product Networks](https://mlsanity.com/paper/2406.12353/) (2024)
- [Prediction of Hospital Associated Infections During Continuous Hospital Stays](https://mlsanity.com/paper/2508.13561/) (2025)
- [GradInf: Gradient Estimation as Probabilistic Inference](https://mlsanity.com/paper/2607.07840/) (2026)

## Abstract (arXiv)

We present the Sum-Product Probabilistic Language (SPPL), a new probabilistic programming language that automatically delivers exact solutions to a broad range of probabilistic inference queries. SPPL translates probabilistic programs into sum-product expressions, a new symbolic representation and associated semantic domain that extends standard sum-product networks to support mixed-type distributions, numeric transformations, logical formulas, and pointwise and set-valued constraints. We formalize SPPL via a novel translation strategy from probabilistic programs to sum-product expressions and give sound exact algorithms for conditioning on and computing probabilities of events. SPPL imposes a collection of restrictions on probabilistic programs to ensure they can be translated into sum-product expressions, which allow the system to leverage new techniques for improving the scalability of translation and inference by automatically exploiting probabilistic structure. We implement a prototype of SPPL with a modular architecture and evaluate it on benchmarks the system targets, showing that it obtains up to 3500x speedups over state-of-the-art symbolic systems on tasks such as verifying the fairness of decision tree classifiers, smoothing hidden Markov models, conditioning transformed random variables, and computing rare event probabilities.