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.
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.
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