# Exact Bayesian Inference on Discrete Models via Probability Generating Functions: A Probabilistic Programming Approach

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 32 references that are in the map.
- First posted on arXiv 26 May 2023.

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

- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [An Introduction to Probabilistic Programming](https://mlsanity.com/paper/1809.10756/) (2018)
- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [SPPL: Probabilistic Programming with Fast Exact Symbolic Inference](https://mlsanity.com/paper/2010.03485/) (2020)
- [Generating Functions for Probabilistic Programs](https://mlsanity.com/paper/2007.06327/) (2020)
- [Does a Program Yield the Right Distribution? Verifying Probabilistic Programs via Generating Functions](https://mlsanity.com/paper/2205.01449/) (2022)

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

- [Polynomial Semantics of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2402.09085/) (2024)
- [Total Variation Distance Meets Probabilistic Inference](https://mlsanity.com/paper/2309.09134/) (2023)
- [AdaptFuse: Training-Free Sequential Preference Inference via Externalized Bayesian Computation](https://mlsanity.com/paper/2604.03925/) (2026)
- [JojoSCL: Shrinkage Contrastive Learning for single-cell RNA sequence Clustering](https://mlsanity.com/paper/2506.00410/) (2025)

## Abstract (arXiv)

We present an exact Bayesian inference method for discrete statistical models, which can find exact solutions to a large class of discrete inference problems, even with infinite support and continuous priors. To express such models, we introduce a probabilistic programming language that supports discrete and continuous sampling, discrete observations, affine functions, (stochastic) branching, and conditioning on discrete events. Our key tool is probability generating functions: they provide a compact closed-form representation of distributions that are definable by programs, thus enabling the exact computation of posterior probabilities, expectation, variance, and higher moments. Our inference method is provably correct and fully automated in a tool called Genfer, which uses automatic differentiation (specifically, Taylor polynomials), but does not require computer algebra. Our experiments show that Genfer is often faster than the existing exact inference tools PSI, Dice, and Prodigy. On a range of real-world inference problems that none of these exact tools can solve, Genfer's performance is competitive with approximate Monte Carlo methods, while avoiding approximation errors.