# A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 36 references that are in the map.
- First posted on arXiv 16 Oct 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference](https://mlsanity.com/paper/2212.12393/) (2022)
- [FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores](https://mlsanity.com/paper/2311.05908/) (2023)
- [Neural Probabilistic Logic Programming in Discrete-Continuous Domains](https://mlsanity.com/paper/2303.04660/) (2023)
- [Scaling Integer Arithmetic in Probabilistic Programs](https://mlsanity.com/paper/2307.13837/) (2023)
- [Top-Down Knowledge Compilation for Counting Modulo Theories](https://mlsanity.com/paper/2306.04541/) (2023)
- [Canonical Decision Diagrams Modulo Theories](https://mlsanity.com/paper/2404.16455/) (2024)

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

- [Neurosymbolic Diffusion Models](https://mlsanity.com/paper/2505.13138/) (2025)
- [A Probabilistic Neuro-symbolic Layer for Algebraic Constraint Satisfaction](https://mlsanity.com/paper/2503.19466/) (2025)
- [CTSketch: Compositional Tensor Sketching for Scalable Neurosymbolic Learning](https://mlsanity.com/paper/2503.24123/) (2025)

## Abstract (arXiv)

As illustrated by the success of integer linear programming, linear integer arithmetic is a powerful tool for modelling combinatorial problems. Furthermore, the probabilistic extension of linear programming has been used to formulate problems in neurosymbolic AI. However, two key problems persist that prevent the adoption of neurosymbolic techniques beyond toy problems. First, probabilistic inference is inherently hard, #P-hard to be precise. Second, the discrete nature of integers renders the construction of meaningful gradients challenging, which is problematic for learning. In order to mitigate these issues, we formulate linear arithmetic over integer-valued random variables as tensor manipulations that can be implemented in a straightforward fashion using modern deep learning libraries. At the core of our formulation lies the observation that the addition of two integer-valued random variables can be performed by adapting the fast Fourier transform to probabilities in the log-domain. By relying on tensor operations we obtain a differentiable data structure, which unlocks, virtually for free, gradient-based learning. In our experimental validation we show that tensorising probabilistic linear integer arithmetic and leveraging the fast Fourier transform allows us to push the state of the art by several orders of magnitude in terms of inference and learning times.