A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic

Lennert De Smet, Pedro Zuidberg Dos MartiresarXiv 2024 · DOI · arXiv

Introduction

In Neurosymbolic AI, researchers aim to bridge the gap between neural perception and symbolic reasoning. A classic example is recognizing handwritten digits and then performing arithmetic on them, such as ensuring the sum of a sequence of images matches a specific target. However, exact probabilistic inference for integer arithmetic is #P-hard. Existing tools often struggle to scale as the range of possible integers increases, primarily due to the computational overhead of exact enumeration or complex logical circuit compilation. Furthermore, the discrete nature of integers creates a "gradient gap," making it difficult to train these systems using standard backpropagation.

PLIAₜ: Inference as Convolution

The core innovation of this work is the PLIAₜ (tensorised Probabilistic Linear Integer Arithmetic) framework. It leverages a fundamental principle from probability theory: the probability mass function (PMF) of the sum of two independent random variables is the convolution of their individual PMFs.

The PMF of the sum of two independent random variables $X_1$ and $X_2$ is represented as a convolution, visualized here as summing along the diagonals of their joint distribution grid.

By treating probabilistic addition as a signal processing problem, the authors can utilize the Fast Fourier Transform (FFT) to reduce the complexity of convolution from $O(N^2)$ to $O(N \log N)$. To ensure numerical stability and differentiability, PLIAₜ represents distributions as tensors of log-probabilities and employs a "log-conv-exp" trick, analogous to the log-sum-exp trick used in deep learning.

Scaling Arithmetic Operations

Beyond simple addition, PLIAₜ provides a library of tensor operations for negation, multiplication by constants, integer division, and modulo. A key feature is translational invariance. By tracking a lower-bound parameter ($\beta$) alongside the probability vector, the system can efficiently handle integers that do not start at zero without needing to pad tensors with zeros.

PLIAₜ supports various arithmetic transformations, such as negation and shifting, by manipulating the underlying tensor representation and tracking distribution bounds.

Experimental Results

The authors evaluated PLIAₜ against state-of-the-art probabilistic programming languages and neurosymbolic methods:

  • Inference Speed: PLIAₜ achieved up to a $10^5 \times$ speedup over Dice for large domain sizes.
  • MNIST Addition: While previous exact methods like DeepProbLog failed beyond 4 digits, PLIAₜ successfully trained on sequences of up to 50 digits.
  • Visual Sudoku: On a $9 \times 9$ grid, PLIAₜ was 20x faster than the approximate method A-NeSI and provided higher accuracy through exact reasoning.

Conclusion and Future Work

PLIAₜ demonstrates that treating logic as a tensor-based signal processing problem can unlock massive scalability for neurosymbolic AI. While currently limited to linear integer arithmetic and independent variables, future work aims to extend these primitives to handle dependencies and non-linear operations, potentially integrating them into a full neuro-probabilistic programming language.

Summary updated

Abstract

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.
BibTeX
@misc{smet2024fast,
  author = {Lennert De Smet and Pedro Zuidberg Dos Martires},
  title = {{A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic}},
  year = {2024},
  eprint = {2410.12389},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.12389},
}
Figure