# Scaling Integer Arithmetic in Probabilistic Programs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 50 references that are in the map.
- First posted on arXiv 25 Jul 2023.

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

- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [An Introduction to Probabilistic Programming](https://mlsanity.com/paper/1809.10756/) (2018)
- [SPPL: Probabilistic Programming with Fast Exact Symbolic Inference](https://mlsanity.com/paper/2010.03485/) (2020)
- [The Beta-Bernoulli process and algebraic effects](https://mlsanity.com/paper/1802.09598/) (2018)
- [The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete Probability Distributions](https://mlsanity.com/paper/2003.03830/) (2020)
- [Exact Probabilistic Inference Using Generating Functions](https://mlsanity.com/paper/2302.00513/) (2023)
- [Swift: Compiled Inference for Probabilistic Programming Languages](https://mlsanity.com/paper/1606.09242/) (2016)

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

- [Polynomial Semantics of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2402.09085/) (2024)
- [A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic](https://mlsanity.com/paper/2410.12389/) (2024)
- [The Limits of Tractable Marginalization](https://mlsanity.com/paper/2506.12020/) (2025)
- [Probabilistic Circuits for Cumulative Distribution Functions](https://mlsanity.com/paper/2408.04229/) (2024)
- [Probabilistic Programs of Thought](https://mlsanity.com/paper/2604.17290/) (2026)
- [Pruning Boolean d-DNNF Circuits Through Tseitin-Awareness](https://mlsanity.com/paper/2407.17951/) (2024)

## Abstract (arXiv)

Distributions on integers are ubiquitous in probabilistic modeling but remain challenging for many of today's probabilistic programming languages (PPLs). The core challenge comes from discrete structure: many of today's PPL inference strategies rely on enumeration, sampling, or differentiation in order to scale, which fail for high-dimensional complex discrete distributions involving integers. Our insight is that there is structure in arithmetic that these approaches are not using. We present a binary encoding strategy for discrete distributions that exploits the rich logical structure of integer operations like summation and comparison. We leverage this structured encoding with knowledge compilation to perform exact probabilistic inference, and show that this approach scales to much larger integer distributions with arithmetic.