A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetics
Authors: Lennert De Smet
Pedro Zuidberg Dos Martires
Venue: NeurIPS 2024 poster (2024)
Keywords: Probability theory
neurosymbolic AI
neuro-symbolic AI
neural-symbolic AI
integer arithmetic
linear integer arithmetic
integer programming
discrete random variables
Primary area: probabilistic_methods
TL;DR: We propose a differentiable tensorisation of linear arithmetics over integer-valued random variables that extends the horizon of exact probabilistic inference by exploiting the fast Fourier transform.

Abstract: As illustrated by the success of integer linear programming, linear integer arithmetics 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 arithmetics 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 integer linear arithmetics 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.

A Fast Convoluted Story: Scaling Probabilistic Inference for Integer Arithmetic
Lennert De Smet KU Leuven Belgium
Pedro Zuidberg Dos Martires Örebro University Sweden
Abstract
As illustrated by the success of integer linear programming. linear integer arith- metic is 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 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 meaningful gradients challenging. which is problematic for learning. In order to mitigate these issues, formulate linear arithmetic over vallger-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 be performed by adapting the fast Fourier transform 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 experi- mental validation we show that tensorising probabilistic linear integer arithmetic and leveraging the fast Fourier transform allows us push the state of the art by several orders of magnitude in terms of inference and learning times.
1 Introduction
Integer linear programming (ILP) [15, 32] uses linear arithmetic over integer variables to model intricate combinatorial problems probleems and has successfully been applied domains such scheduling [31], telecommunications [34] and energy grid optimisation [26]. If one replaces deterministic integers with integer-valued random variables, the resulting probabilistic arithmetic expressions be used to model probabilistic combinatorial problems. In particular, many problems studied in the field of neurosymbolic AI can be described using probabilistic linear integer arithmetic.
Unfortunately, exact probabilistic inference for integer arithmetic is a #P-hard problem in general. Consequently, even state-of-the-re probabilistic programming languages with dedicated inference algorithms for discrete random variables, such as ProbLog [8] and Dice [13], fail to scale. The reason being that they resort to exact enumeration algorithms, exemplified in Figure 1. Note that while approximate inference algorithms such as Monte Carlo methods and variational inference can be applied to probabilistic combinatorial problems, they come with their set of limitations, as discussed by Cao et al. [5]. For instance, conditional inference with low-probability evidence.
In order to mitigate the computational hardness of probabilistic inference over integer-valued random variables, we make the simple yet powerful observation that the probability mass function (PMF) of the sum of two random variables is equal to the convolution of the PMFs of the summands. The key advantage of this perspective is that the exact convolution for finite domains can be implemented efficiently using the fast Fourier transform (FFT) in O(N log N), which avoids the traditionally quadratic behaviour of computing the PMF of a sum of two random variables (Figure 1). Moreover,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Px, (xr)
088
0.5
(x) 64-
(x) 06-
(x)
04
014
67
0.2
0
px(4)
pxt px
Figure 1: On the left and in the middle we have two histograms representing the probability distri- butions of the random variables Xı and X2, respectively. The grid on the right represents the joint probability of the two distributions, with more intense colors indicating events with higher probability. The distribution of the random variable X X1 + X2 can be obtained by summing up the diagonals of the grid as indicated in the figure. While this method of obtaining the distribution for X is valid and used by state-of of-the-art neurosymbolic techniques [14, 21]. the explicit construction of the joint is unnecessary and hampers inference and learning times (cf. Section 5).
efficient implementations of the FFT are readily available in modern deep learning libraries such as TensorFlow [1] and PyTorch [28]. making our approach to probabilistic inference end-to-end differentiable by construction. In turn, differentiability allows us to apply our approach to prototypical problems in neurosymbolic AI.
Our main contributions are the following. 1) of bounded integer-valued random variables that allows for the computation of the distribution of sum of two such variables in O(N log N) instead of ((N2) by exploiting the fast Fourier transform (Section 2). 2) We formulate common operations in linear integer arithmetic, such as multiplication by constants and the modulo operation, operations give rise to PLIA,, a scalable and differentiable framework for Probabilistic Linear Integer Arithmetic.' PLIA, supports two exact probabilistic inference primitives; taking expected values and performing probabilistic branching (Section 4). 3) We provide experimental evidence that PLIA, outperforms the state of the art in exact probabilistic inference for integer arithmetic [5] in terms of inference time by multiple orders of magnitude (Section 5.1). Moreover, we deploy PLIA, in the context of challenging neurosymbolic combinatorial problems, where it is again orders of magnitude more efficient when compared to state-of torth--r- exact and approximate methods (Section 5.2).
We propose a tensor representation of the distributions
tensor manipulations (Section 3). These tensorised
2 Efficient Addition of Integer- Valued Random Variables
In what follows, denote random variables by uppercase letters, while specific realisation of random variable is written in lowercase. That is, the value x is an element the sample space ?(X) of X. We will also refer ((X) as the domain of the random variable X. Furthermore, 2(() is assumed to be integer-valued, i.e. is a finite subset of the integers Z with lower and upper bounds I(X) and ((X). respectively. In particular, We will call these integer-valued random variables probabilistic integers from here on.
have that the cardinality [[(X)] ((X)-I((X))
The distribution of probabilistic integer X is represented using its probability mass function (PMF) px ((X) + [0, 1] with the conventional restrictions
Vr E ((X): (x) 2 0
and
ExERLx)xX(E Px(x) =
2.1 Probabilistic Integers and the Convolution Theorem
At the core of PLIA, and linear arithmetic in general the addition of two probabilistic integers X, and Xº, Let us assume for now that X, and X, satisfy L(X,) = L(X₂) 0 and have upper bounds ((x) = N, and U(2)) = N2. Just as in Figure 1, we would now like to find the PMF of the random variable X such that X = Xi + X2. However, contrary to Figure 1, we wish to avoid the
'The subscript "t" in PLIA, stands for "tensorised" and is pronounced.

---

explicit quadratic construction of all possible outcomes. To this end, we exploit that the PMF of the sum of two random variables is equal the convolution of their respective PMFs [12]
px(x) (px, (x),
X X2.
(2)
Next, we apply the Fourier transform J both sides of the equation and use the convolution theorem (CT) [23] that states that the Fourier transform of two convoluted functions is equal to the product of their transforms
(()x)(x)= = F(xx, * (x) _h F(xx, (x:) F(Px,)(=) = Px, (x) (x),
(3) where we also introduce the hat notation F(px) = px for a Fourier transformed PMF px. As X = X1 + X2, we know that ((X) {O....,NY .1 + N22. Consequently, the PMF px is non- zero for just these M = N1 + N2 + domain elements and can be represented using a vector of probabilities
xx px(x), Vx NI + N2).
All vectors of probabilities will be written using boldface π and their elements accessed using square brackets. Looking at Equation 3, we would now like to express the Fourier transformed probability vector xx as the point-wise product of the transformed vectors
F = Xx, Xx
(5)
where FMr MMM is the M-point discrete Fourier transform (DFT) matrix and the symbol @ denotes the Hadamard product. In order for Equation to hold we need to have that
FM
and πx2- = X2
(6)
At first sight these equalities seem to cause a problem; each probabilistic integer X; has a domain of size N; + while its PMF should be represented with probability vector лx, RR for the multiplication with Far to make sense. Fortunately, this problem is easily resolved by observing that we can extend the domain (2.X.) of X, by simply assigning probability of zero newly added elements. In practice, we simply pad the probability vectors Xx, and лx, with N2 and N1 zeros the end to obtain vectors of dimension M. With this issue resolved, we can finally obtain the probability vector x that represents the PMF px by using Equation 5 via
FM 7x,
TX2 + FM = FMTXX, O FMTX,
x = Fid (FMIXX, 3 FMTXX..
(8)
2.2 The Fast Log-Conv-Exp Trick
The attentive reader might have noticed that, even though we avoid the explicit construction of the joint probability distribution Px,xa (#1, we have not gained much. The matrix-vector products in Equation still take ((M2) to compute. Fortunately, matrix-vector products where the matrix is the DFT matrix or its inverse can be computed in time O log M) by using the fast Fourier transform (FFT), with M being the size of the vector. As result,
express Equation 8 as
x IFFT [FF((Xx)) FFT(TX))).
Computing the values of the vector x can now be done in time O(M log M). First we apply the FFT on the vectors лx, and xx,- Then multiply the transformed vectors pointwise and apply the inverse FFT on the result of this Hadamard product. We note that Equation is a well known result from the signal processing literature, where convolutions are always computed in this fashion [23].
However, applying Equation naively to the problem of probabilistic inference quickly results in numerical stability issues. The problem is that multiplying together small probabilities eventually results in numerical underflow. well-know and widely used remedy to this problem is the log-sumi exp trick, which allows one to avoid underflow by performing computations in the log-domain instead of the linear domain. Inspired by the log-einsum-exp trick [29], we introduce the fast log-conv-exp trick, which allows us to perform the FFT on probabilities in the log-domain.
We first characterise a probability distribution px not by the vector of probabilities лx but by the vector of log- probabbbaallssies Ax = log π In terms of log bog-rrbbbbiliiies Equation 9 can be written as
exp Ax = IFFT (FFT(exp Ax,) FFT Axx)).
(10)
3

---

Now define μa; == (XX)))((X)) Ax, as the maximum value present in the vector Xx,, which lets us write Equation 10 as
expXx IFFT (FFT px, + +x,,) @ FFT(exp(Ax, 1xx, + pxx)))
(11)
IFFT IFFT (FFT(FF(()sp(Ax, -xx,) FFT(exp(2x, - (xx))) exp(ux,) exp(px.)-
Crucially, we were able to pull out the scalars exp(ux,) and exp(xx,) due to the linearity of the FFT transform and its inverse. Taking the logarithm of both sides results in the fast log-conv-exp trick
Ax = log IFFT FF - -xx)) O FFT(exp(Ax, - -xx))) + μxx, + PX2. (12)
which expresses the log- propoabbaiiiiies Ax in function of Xx, and Xx,- It can still be computed in time O(M log M) and avoids, at the same time, numerical stability issues by exponentiating Xx, P4 instead of Xx, directly.
While using the fast log-conv-exp trick is necessary to scale computations in a numerically stable manner, describing operations on probability mass functions in the log-domain is rather cumbersome. Hence, we will, for the sake of clarity, describe PLIA, using probability vectors π (cf.. Sections 2.3, 3 and 4). We refer the reader our implementation for the log-domain versions.
Another solution to the numerical instability of applying the FFT on probabilities was given in an application of the FFT to open-population [6] N -miitture models [27]. However, it has a major brawback when compared to the fast log-conv-exp trick: it relies on repeated applications of the traditional log-sum-ews trick within each of the N log N iterations of the FFT. This drawback prevents the use of optimised, off-the-shelf FFT algorithms and adds computational overhead. In contrast, we utilise the linearity of the FFT transform provide implementation--agossii solution that works with tensorised representations.
2.3 Translational Invariance
In the previous sections we assumed that the first non-zero probability event of all probabilistic
integers X was the event X 0, i.c. L(X) = O. However, we can remove this assumption by characterizing PMF px not only by vector of probabilities πT, but also by an integer 3x = L(X) encoding the non non-zero lower bound of the domain f(X).. Indeed, we can write any PMF px over an integer domain as the translation of PMF p& whose first non-zero probability event is X =
px (x) (Txx (x) = (x 3x))
(13)
Since the PMF p can be represented by probability vector л as the previous sections, follows that the PMF of any probabilistic integer can be characterised by such vector and an integer 3x that shifts the domain. The upper bound of the domain is not important for the characterisation of px as it can be obtained via U(X) Bx dim (x)) ) 1, where dim(Tx (Tx x) is the dimension of the probability vector π--
The inclusion of translations in our representation of PMFs is compatible with using convolutions to compute the PMF of the sum of two probabilistic integers because of the translational invariance of the convolution
(s * g) = (Tu] * = (ʃ * <T.));
(14)
where Tı denotes the translations by scalar k. In general, & can be real-valued, but for PLIA, limit i to integers. Using Equation 13, we can write the PMF of the sum of two probabilistic integers X, and X₂ with non-zero lower bounds Bx, and Bx,
px (px, px2) (Txx, && T8x, px,) (Tax, o TBx (PX, * PX,)
(15)
= =Txx]t0x, (px: * *PX,).
(16)
This final equality shows that can characterise the PMF px for X = = + X2 by the following lower bound and probability vector
3x = 3x, 8x2
and xx = Fri (FMITX, 3 P
(17)

---

Figure 2: (Left) Adding a constant to a probabilistic integer simply means that we have to shift the corresponding histogram, shown here for X' X 1. (Middle) For the negation X' = -X, the bins of the histogram reverse their order and the negation of the upper bound becomes the new lower bound, (Right) For multiplication, here show the X' = 3X by inserting probability bins.
2.4 Formalising PLIA
PLIA, concerned with computing the parametric form of the probability distribution of linear integer arithmetic expression. It does so by representing random variables and linear combinations thereof tensors whose entries are the log-proo pog-prbbabilities the individual events in the sample space of the random variable that is being represented. We define this formally as follows.
Definition 2.1 (Probabilistic linear arithmetic expression). Let {X1,..., Xx} } be a set of N indepen- dent probabilistic integers with bounded domains. probabilistic linear integer arithmetic expression X is itself a bounded probabilistic integer of the form
N
X f((x),
(18)
where each fi denotes an operation performed on the specified random variables that can be either one of the operations specified in Section 3 as well as compositions thereof.
Note that operations within PLIA; are closed. That is, performing either of the operations delin- eated in Section 3 will again result in bounded probabilistic integer representable as tensor of rog-probabilities and an off-set parameter indicating the value of the smallest possible event (cf. Section 2.3). Section PLIA, will also be provided with probabilistic inference primitives that allow it to compute certain expected values efficiently as well as to perform probabilistic branching.
Assuming all f(();) computable in polytime, tion 18) in polytime in N. However, when computing PLIA, expressions recursively, the domain size of the random variables might grow super-polynomially manifesting the #P-hard character of probabilistic inference.
also compute PLIA, expressions (Equa-
Arithmetic on Integer- Valued Random Variables
The previous section introduced how PLIA, deals with the addition of probabilistic integers. We discuss now five further operations: 1) addition of a constant, 2) negation, 3) multiplications by constant, 4) integer division by a constant and the modulo.
Constant Addition.
The addition of a probabilistic integer X and constant scalar integer & forms a new probabilistic integer X' X k. Adding scalar integer equivalent to translation of the distribution of X (Figure 2, left). In other words, the lower bound and probability vector of X' are given by
8x Bx + k and xx nx.
(19)
5

---

Figure 3: (Left) We show the histogram transformation for the integer division X' = X/33. The probability mass of three subsequent bins accumulated in the bins for which æ mod = and a/3 Q(X). (Right) For the modulo X' X mod 3, the only non-zero elements of S2(X') are elements of the set {0, 1, 2}. The bins corresponding to these values then accumulate the probability masses of all other bins indicated by the colors.
Negation. The negation X' -X of a probabilistic integer is equally straightforward to characterise. Taking negation mirrors the probability distribution of X around zero (Figure 2, middle). terms of lower bound and probability vector, we get 3x (3x + dim(TTx) - 1) and
x [x] = [x x (dim((Tx) - I 1], if S x<<<< dim(Txx:
(20)
10,
otherwise.
respectively. That is, the lower bound of X' is equal to the negated upper bound of X while the probability vector is flipped, taking into account that probability vectors have to start at O.
Constant Multiplication. For the multiplication X' X k of probabilistic integer X with scalar integer k, we assume, without loss of generality, that k: 2 0. Multiplication by a scalar is then characterised
8x Bx k and [x] x 0,
if mod and 0 S < dim(TTx); (21) otherwise.
Intuitively, only multiples of k get a non-zero probability equal the probability of that multiple in πx. The lower bound of X' is also immediately given by multiplying the lower bound of X by k. In other words, we obtain x by inserting k zeros between every two subsequent entries of π (Figure 2. right). The case l < 0 is obtained by first negating X.
Integer Division and Modulo. For the case of integer division X' = X/4= and the modulo operation X'= X mod k, the probability distribution of X' can be obtained by adequately accumulating probability mass from events in (2)).. We demonstrate these operations by example in Figure 3 and refer the reader to Appendix A for the formal description.
Probabilistic Inference Primitives
4.1 Computing Expected Values
PLIA, supports the exact computation of two different forms of expected values. The first is a straightforward expectation of probabilistic integer X, given by weighing each element of ((X) with its probability
E [ I x [x]
(22)
The second is computing the expectation of linear comparative expression of probabilistic integers. Such comparison can an equality, inequality or negated equality. We only consider the equality and strictly larger inequality as the other cases follow from them. The strict inequality can itself always be reduced to an inequality with respect zero and hence comprises sum over all domain elements below zero
E [xxoo] Ex x 8x]-
(23)
Similarly, the computation of the expected value of equality comparison always be reduced to a comparison to zero. Hence, the expected value is computable by simple indexing
E 1 x= xx(-8xl
(24)

---

True
gT
XT
C
X1
False
9.1
Figure 4: Control flow diagram for probabilistic branching. The branching condition is probabilis- tically true and induces binary random variable C. In each of the two branches we then have two conditionally independent random variables X- and X which the functions gT and g. applied in their respective branches, The probabilities of X' are then given by the weighted sums of the probabilities gT (XT) and g1 gi({1) (Equation 29).
As computing expected values is no harder than computing the sum of the elements of vector, can conclude that we can compute these expected values in O(dim π xx)): )) By using prefix sums [18] and harnessing parallel compute GPUs, the complexity further be reduced Ollog dim(xx))
4.2 Probabilistic Branching
Consider an if-then-else statement with condition c(x)= (f(x) De 0), where / a composition of the functions introduced in Section and Da domain ((X) of a probabilistic integer X. In the case of c(x) being true, a function gT is executed. If c(x) is false, another function g.1. is executed instead. We assume that both gr and gi again linear arithmetic functions expressible in PLIA, (Section 2.4).
Furthermore, æ belongs to the
The if-then-else statement defines
new probabilistic integer X' by combining both of its branches (Figure 4). These branches depend on X which itself influences binary random variable C' that represents the probabilistic condition of the if-then-else statement. To be precise, the PMF px is given by the decomposition
(x) Px (T) PT(()) + Px -c((),,
(25)
where Px is the conditional PMF of X' given C. The true branch gives rise probabilistic integer XT with probability distribution
px, (x) = Pxio(" T) (T x))x(=)
xx( - Ax] PC(T)
(26)
Pc(T)
If C = T, then X' is given by application of gT the instances x E ?(X) that satisfy c(x). Consequently, by applying gr, we find that
(x =
(27)
With the right-hand side of Equation 26, we now know how obtain the probability vector for XT- Using Equation 27 and the operations from Section 3, we can then compute the probability vector Tg (x+), well the lower bound [gr(X Also note that (C(T) is nothing but expected value as described by Equation 23 or Equation 24. Analogously, we obtain for the false branch that
(1 Le(x) ) 3x]
px_ (x)
and (x 11)= = (x))xx)(
(28)
PC(1)
By plugging the expressions for Px (x T) and px | 1] into Equation 25 we find that px: Por (X (x') (T( + Psi (x, (x') po((),
(29)
which are all quantities computable using either probabilistic linear arithmetic operations or expected values thereof.

---

Dice
PLIA (spu)
PLIA (gpu)
10
101
Time
10
10
10
10a2
1.0 35 (ROW dth
1.0 Bitwidth
150
300
Bitwidth
Identifier length
Figure 5: We plot the runtime of Dice [5] and PLIA, against the domain size of the problems. E +Xx++X,=o) and probabilistic Luhn. All four plots share the same y-axis on the very left, which in log-scale. Following the experimental protocol of Cao et al. [5], we report average runtimes for every integer on the x-axis, both bitwidths and identifier lengths. No significant deviations from the mean were found.
From left to right, we have E [X1 + X2). E
5 Experiments
We first compare PLIA, to the state of the art in probabilistic integer arithmetic [5] in terms of infer- ence speed (Section 5.1). These experiments were performed using an Intel Xeon Gold 6230R CPU @ 2.10GHz, 256GB RAM for CPU experiments and an Nvidia TITAN RTX (24GB) for GPU experi- ments. In Section 5.2, we then illustrate how PLIA, fares against the state the art neurosymbolic AI [14, 33). These experiments were performed using an Nvidia RTX 3080 Ti (12GB). We imple- mented PLIA, TensorFlow [1] using the Einops library [30]. This implementation is open-source and available at https: http//gtttttttt/e com ML-KMMLuee// /tt.-//uuueeeeeeprrbbaattti----- aittetitttttataattttiiiii thmetic
5.1 Exact Inference with Probabilistic Integers
The work of Cao al. [5] exploits the structural properties and symmetries of integer arithmetic by proposing general encoding strategies for an arithmetic expression of probabilistic integers as logical circuits. That is, binary decision diagrams [4] obtained via knowledge compilation [7]. This strategy allows them to avoid redundant calculations and repetition, leading to improved scalability over more naive encodings [8, 13].
We compare PLIA, and Cao et al. inference algorithm on four of their benchmark problems. In the first three benchmarks, expected values of the sum of two random variables need to be computed. Concretely, the expectations E [ + X2] (cf. Equation 22), E [1 [1x (cf. Equation 23) and [1 X (cf. Equation 24).
As fourth benchmark we use probabilistic version of the Luhn checksum algorithm [20], which necessitates summation of two probabilistic integers, negation, addition of constant, multiplication by a constant, the modulo operations, as well as probabilistic branching. We provide further details on the Luhn algorithm in general and the encoding of its probabilistic variant in PLIA, in Appendix C.
As the probabilistic Luhn algorithm takes as input an identifier consisting of a sequence of probabilistic integers with domain (O...., 9}. we can increase the problem size by increasing the length of this sequence. For the other three benchmarks we vary the problem size by varying the domain size the probabilistic integers in terms of their bitwidth. That is, bitwidth of E N indicates that we consider probabilistic integers ranging from 0 up until terms of i. In experimental evaluation (Figure 5), measure the time it took for PLIA, and Cao et al.' 's method to terminate for varying problem sizes. The measured time includes all computational overhead inherent to each method, such as the construction of computational graphs and compilation time. Each method is also profiled in terms of memory, which we discuss further in Appendix B. Note that Cao et al.' 's method is denoted by "Dice", the probabilistic programming language in which was implemented.
1, increasing the problem size exponentially in
For the first three benchmarks, we observe that PLIA, easily scales to probabilistic integers with domain size of 224 on both the CPU and GPU as the highest runtime reached less than 100 seconds on the CPU and approximately 1 second on the GPU. The similarity of the curves is due to the fact

---

0423
6
7 3 2 9
576 9 0
1
891
(245
+
o 8 5
4
(85097
30
1 126
7507
4 6 2 (
8 6
718030 4
Figure 6: (Left) Example of an MNIST addition data point, consisting of two numbers given as series of MNIST digits and an integer. The integer is the sum of the two numbers and constitutes the label of the data point. (Right) Data point from the visual sudoku data set, consisting of a 9 x grid filled with MNIST digits. Data points are labeled with Boolean value indicating whether the integers underlying the MNIST digits satisfy the constraints of sudoku.
that the time is dominated by computing the probability vector x and not much by computing the actual expected value.
In contrast, Dice, which only runs CPU, already reaches runtime of approximately 1000 seconds for integers with domain size 2 where PLIA, only takes around 10-1 and 10 seconds on the CPU and GPU, respectively. This is rather considerable improvement in the order of 10s Dice can outperform PLIA, on the GPU (Figure 5, bitwidth smaller strictly below 5) due to the computational the GPU. However, much of this overhead can be avoided by running PLIA,
overhead of rumning on the CPU for smaller domain sizes, where it performs on par or better than Dice (Figure 5, bitwidth smaller strictly below 5).
On the probabilistic Luhn benchmark (Figure 5, extreme right) we observe that both methods exhibit similar linear scaling behaviors. However, the use of tensors representations instead of logical circuits does result in a significant improvement in terms of run time in the order of 102 for the longest sequences of length 350.
5.2 Neurosymbolic Learning
For the comparison of PLIA, to neurosymbolic systems, we two standard benchmarks from the literature: MNIST addition [21] and visual sudoku [2]. The common idea for both is to train neural networks to classify MNIST digits while only having access to distant supervision (Figure 6).
As an MNIST classifier outputs distribution over the integers ,0,....99 9}. we can readily encode these predictions as probabilistic integers and enforce the constraints given by the two problems using the arithmetic operations developed in Section and Section 3. We refer the reader to Appendix D (MNIST addition) and Appendix E (visual sudoku) for details the encodings.
In the experimental evaluation we compare PLIA, which uses exact probabilistic inference, one other exact method, DecpProbLog (DPL) [21, 22], and two approximate methods, Scallop [14] and A-NeSI [33]. Similar Dice (Section 5.1), DPL also relies on expensive knowledge compilation in order to obtain the distribution of the sum of two probabilistic integers. Essentially, it performs explicit enumeration as illustrated in Figure 1. Scallop approximates this explicit enumeration by only considering the top-k most likely solutions of problem. The approximation of A-NeSI is based on optimising a neural surrogate model for the combinatorial problem. While this model sidesteps the computational complexity encountered by DPI. and Scallop to certain degree, training the surrogate model becomes prohibitively expensive for larger problems.
We compare the different methods along two dimensions, being prediction accuracy and training time. Specific details on training, c.g. neural architectures and hyperparameters, can be found Appendix We report the statistics in Table 1, where we use numbers consisting of N E {2, 4, 15, 50) digits for the MNIST addition benchmark and grid size G [4, 9) for the visual sudoku benchmark. We see that PLIA, significantly outperforms the other methods, both exact as well as approximate, in terms of training times. The difference is particularly apparent on the MNIST addition benchmark, where no other method was able to scale up to N 50 without timing out. The reported accuracies also show that this advantage of training time for PIIIA, with respect to the other methods does not come at the cost of predictive performance of the learned neural networks.

---

Table In the upper part part we report median test accuracies over 10 runs for the MNIST addition and the visual sudoku benchmarks for varying problem sizes and different neurosymbolic frameworks. Sub- and superscript indicate the 25 and percent quantiles, respectively. In the lower part we report the training times in minutes, again using medians with 25 and 75 percent quantiles. We set the time-out to 24 hours (1440 minutes).
Method
MNIST Addition
Visual Sudoku
N
N =4 4
N 15
N
50
G=4
G = 9
Accuracy
Accuracy
DPL
94.20+2.04
T/O
T/O
T/O
T/O
T/O
Scallop
95.40+0.40
90.88
T/O
T/O
74.5012.00
T/O
0.48
A-NeSI
95.40 +0.60
-0.24
92.40
74.71
+2.91
-1.27
T/O
85.5012.00
-0.00
61.50
PLIA
95.88 0.16
+0
91.60 0.16
0.772
79.09
+..21
43.00 3.00
85.00 4.50
+3.00
63.00
2.12
-1.00
Timings (minutes)
Timings (minutes)
DPL
88.21
+15.58
T/O
T/O
T/O
T/O
T/O
1.89
Scallop
22.62+0.e4
0.06
50.41+6.40
0.117
T/O
T/O
3.90+0.01
T/O
A-NeSI
41.02
-2.79
53.62
6.40
1.76
714.55127.66
T/O
30.67
-.117
134.86+31.01
PLIA,
1.97+0.02
2.44 0.04
+0.01
7.85+0.61
11.9 11.98+0.68
0.58+0.03
6.39+0.01
-0.01
-0.04
0.02
Conclusion and Future Work
We introduced PIJA,, efficient, differentiable and hyperparameter-ffee framework for linear arithmetic over integer-valued random variables. The efficiency of PLIA, is due to representing probabilistic integers as tensors and exploiting the FFT for computing the sum of two probabilistic integers. Compared to state-of-the-art methods for inference [5] and learning [33] the concepts underlying PLIA, are surprisingly simply: tensorised calculus and the fast Fourier transform. This simple yet elegant approach has led to improvements in inference and learning times in the order of 10y and 102, respectively. We attest this advantage PLIA''s formulation in terms of fundamental concepts shared across modern machine learning. As such, any algorithmic or hardware improvements will immediately improve PLIA,'S 's performance. For instance, incorporating recent advancements for computing FFTs on GPUs [11] would directly benefit PLIA,'s 's efficiency.
In future work envisage extend the probabilistic inference primitives of PIIA, to full- fledged neuroprobabilistic programming language, resulting in a user-friendly interface to an efficient neurosymbolic reasoning engine. In this regard, we deem ideas from the satisfiability modulo theory literature [3] as important. Specifically, probabilistic [17, 25] and neural [9] extensions thereof, as well as novel formula representations [10, 24].
Acknowledgements
This work was supported by the KU Leuven Research Fund (C14/18/062 and iBOF/21/075) and the Flemish Government under the Sonderzoeksprogramm.. Artificiële Intelligentie (AI) Vlaanderen" programme. It also received funding from the Research foundation Flanders project "Neural Proba- bilistic Logic Programming" (G097720N). PZD is supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded the Knut and Alice Wallenberg Foundation.
10

---

References
[1] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Good- fellow, Andrew Harp. Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Vié- gas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL https: wwww. www.:reenrrff.. low. org/ Software available from tensorflow.org.
[2] Eriq Augustine, Connor Pryor, Charles Dickens, Jay Pujara, William Wang, and Lise Getoor. Visual sudoku puzzle classification: suite of collective neuro-symbole tasks. International Workshop on Stural-Symoolic Learning and Reasoning (NeSy), 2022.
[3] Clark Barrett and Cesare Tinelli. Satisfiability modulo theories. In Handbook of model checking. Springer, 2018.
[4] Randal E Bryant. Graph-based algorithms for boolean function manipulation. Computers, IEEE Transactions on, 10068):677-691, 1986.
[5) William X Cao, Poorva Garg, Ryan Tjoa, Steven Holtzen, Todd Millstein, and Guy Van den Broeck. Scaling integer arithmetic in probabilistic programs. In Uncertainty in Artificial Intelligence, pages 260-270. PMLR, 2023.
[6] David Dail and Lisa Madsen. Models for estimating abundance from repeated counts of an open metapopulation. Biometrics, 67(2):577-587, 2011.
[7] Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research, 2002.
[8] Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. Problog: A probabilistic prolog and its application in link discovery. In IJCAI. Hyderabad, 2007.
[9] Lennert De Smet, Pedro Zuidberg Dos Martires, Robin Manhaeve, Giuseppe Marra, Angelika Kimmig, and Luc De Readt. Neural probabilistic logie programming discrete-continet domains. UAI, 2023.
[10] Vincent Derkinderen, Pedro Zuidberg Dos Martires, Samuel Kolb, and Paolo Morettin. Top- down knowledge compilation for counting modulo thcories. arXiv preprint arXiv:2306.04541, 2023.
[11] Daniel Y Fu, Hermann Kumbong, Eric Nguyen, and Christopher Ré. Flashfftconv: Efficient convolutions for long sequences with tensor cores. arXiv preprint arXiv:2311.05908, 2023.
[12] Paul G Hoel. Introduction mathematical statistics. Introduction to mathematical statistics., 1954.
[13] Steven Holtzen, Guy Van den Broeck, and Todd Millstein. Scaling exact inference for discrete probabilistic programs. Proceedings of the ACM Programming Languages, 4(0OPSLA): 1-31, 2020.
[14] Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. Scallop: From probabilistic deductive databases scalable differentiable reasoning. NeurlPS, 2021.
[15] Michael Jünger, Thomas M Liebling, Denis Naddef, George L Nemhauser, William R Pul- lcyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A Wolsey. 50 Years of integer programming 1958-2008 From the early years to the state-of-the-ar. Springer Science & Business Media, 2009.
[16] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2015.

---

[17] Samuel Kolb, Martin Mladenov, Scott Sanner, Vaishak Belle, and Kristian Kersting. Efficient symbolic integration for probabilistic inference. In 27th International Joint Conference on Artificial Intelligence: IJCAI 2018, pages 5031-5037. IJCAI Inc, 2018
[18] Richard E Ladner and Michael J Fischer. Parallel prefix computation. Journal of the ACM (JACM), 27(4):831-833, 1980.
[19] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-bant learning applied to document recognition. IEEE, 1998.
[20] H.P. Luhn. Computer for verifying numbers. U.S. Patent US2950048A, 1960.
[21] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. Advances in neural informa- tion processing systems, 31, 2018.
[22] Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Neural probabilistic logic programming in deepproblog. Artificial Intelligence, 2021.
[23] Clare D McGillem and George R Cooper. Probabilistic methods of signal and system analysis. Oxford University Press, Oxford, UK, 1986.
[24] Massimo Michelutti, Gabriele Masina, Giuseppe Spallitta, and Roberto Sebastiani. Canonical decision diagrams modulo theories. arXiv preprint arXiv:2404. 16455, 2024.
[25] Paolo Morettin, Pedro Zuidberg Dos Martires, Samuel Kolb, and Andrea Passerini. Hybrid probabilistic inference with logical and algebraic constraints: a survey. In IJCAI, 2021.
[26] Akomeno Omu, Ruchi Choudhary, and Adam Boies. Distributed energy resource system optimisation using mixed integer linear programming. Energy Policy, 61:249-266, 2013.
[27] Matthew RP Parker, Laura LE Cowen, Jiguo Cao, and Lloyd T Elliott. Computational efficiency and precision for replicated-coum and match-marked hidden population models. Journal of Agricultural, Biological and Environmental Statistics, 28(1):43-58, 2023.
[28] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style. high-performance deep learning library. NeurIPS, 2019.
[29] Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp. Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In International Conference Machine Learning, pages 7563-7574. PMLR, 2020.
[30] Alex Rogozhnikov. Einops: Clear and reliable tensor manipulations with einstein-like notation. In International Conference Learning Representations, 2022.
[31] David M Ryan and Brian A Foster. An integer programming approach scheduling. Computer scheduling of public transport urban passenger vehicle and crew scheduling, pages 269-280,, 1981.
[32] Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
[33] Emile van Krieken, Thiviyan Thanapalasingam. Jakub Tomczak, Frank Van Harmelen, and Annette Ten Teije. A-nesi: A scalable approximate method for probabilistic neurosymbolic inference. Advances in Neural Information Processing Systems, 36, 2023.
[34] Zhibo Yan, Guoyong Gu, Kanglian Zhao, Qi Wang, Gang Li, Xin Nie, Hong Yang. and Sidan Du. Integer linear programming based topology design for gnsss with inter-satellite links. IEEE Wireless Communications Letters, 10(2):286-29) 290, 2020.
12

---

Appendix
A Formal Description of Integer Division and Modulo
Integer Division. Performing a scalar integer division of the random variable X by l yields the random variable X' = X with lower bound Bx 2x and probability vector
Σ Da
bo xx|1].
20 dim
x [ar] =
(30)
otherwise,
where assume that L(X) mod a weak assumption as it can easily be obtained via zero-padding. The intuition is then that the probability vector x of an integer division of X by k accumulates probability mass of k sequential entries of x (Figure 3, left).
and U(X) + mod k: dim( mod A: 0. This
Modulo Operation. For the modulo of random variable by constant, i.e. X' = X mod k, we have the lower bound 8x = 0 and the probability vector is
x [x]
Ei
xx + k. i].
i S < k.
(31)
0,
otherwise.
where we again assumed that L(X) mod k and UXX) mod dim( mod k In other words, the probability vector x of the modulo of a random variable X accumulates the probability mass of x by multiples of i (Figure 3, right).
B Studying the Memory Consumption of PLIA
is well-known that the FFT has, apart from the N log N runtime complexity, also N log N theoretical space complexity, again in contrast to N2 space complexity of the naive approach. Moreover, we performed an additional empirical comparison between Dice [5] and PLIA, with respect to memory allocation (Figure 7). We found that Dice only more efficient for smaller problem sizes due to the memory overhead of TensorFlow on the GPU. However, from problem sizes of bitwidth higher than 13, Dice overtook PLIA, in memory usage and we confirmed the better scaling behaviour of PLIA, Hence, PLIA, not only outshines the current state of the art in terms of runtime but also terms of memory usage. Memory usage of PLIA, the CPU could be properly profiled due to Python's limited functionality, but there is no reason to suspect it would be significanlty different from the GPU memory usage.
Dice
PLIA Igpu)
101
Memory (MB)
107
10--
10-2
1.0
20
1.0 Bitwidth
160
300
Bitwi dth
Bitwidth
Idontrfier length
Figure The memory usage in MB plotted against the domain size of each the problems discussed in Section 5.1. From left to right, we have [X; + X²). E [1 +x E [ and probabilistic Luhn. All four plots share the same y-axis on the very left, which is in log-scale. Memory measurements were consistently identical across multiple different runs.
13

---

def "uun_ http_chhcckummmcmc (iaerusmmddddniiiireee check = 0
for i, digit in enumerate(fdenttffee))
if
len(identifier) % ite_digit = ifthenelse( digit,
lt=5,
tbranch=lamber x: 2 * X,
Obranch-lambda x: 2 x 9,
check = check ite_digit
else:
13
check check digit check check % 10
14
return check
Algorithm 1: Probabilistic Luhn algorithm written in Python using plia library.
C Luhn Program
The traditional Luhn algorithm [20] computes check digit from given sequence of integers. If the check digit is correct, then means that there are no single-entry mistakes the sequence. Such errors often arise, for example, when transcribing credit card information. Hence, Luhn is often used in this context to quickly identify mistyped numbers.
We provide an implementation of the probabilistic Luhn algorithm using PLIA, in Algorithm 1. During its execution, the algorithm sequentially constructs the check digit by iterating over the given sequence. At the start of every step. deterministic if-then-else statement checks whether the current sequence has the same binary polarity as the length of the total sequence be checked (Line 4). The first argument of the ifthensels test. The second argument gives the test. For Luhn we have digi digit<5. The two lambda functions then tell us which function to perform on the random variable in each of the two branches. The function outputs a probabilistic integer which we add to the check probabilistic integer.
function is the probabilistic integer which to perform the
D MNIST Encoding
Let n and ni be two probabilistic integers. The MNIST addition problem then usually encoded in one of two different ways. The first approach simply directly constructs the joint distribution over all possible integers. The second approach avoids this explicit constructions by computing conditional distributions for intermediate computations. In other words, the first approach constructs lookup table for the sum of two integers while the second encoding gives us probabilistic version of the sum of two integers via carry. Naturally, the second approach is able scale to larger numbers and we also use it in our experiment for all methods. We give the implementation for both encodings in Algorithmns 2 and Algorithm 3.
Visual Sudoku Probabilistic Binary Encoding
G sudoku puzzle filled with handwritten digits (Figure 6, right). The task itself is to predict whether such given sudoku puzzle valid, meaning the values of digits satisfy the various sudoku constraints. For 4, constraints to satisfy are that every row and every column must have different entries. In case G = 9. all nine inner 3 grids of the puzzle must also have different entries. Again, because the digits handwritten, neural network has classify the digits into probabilistic integers from 0 to 9.
For the problem of solving visual sudoku [2]. the input
14

---

def sum_numbers(
probs_1, probs_2,
digits_per_nunbee ):
number1
number2
for i in range (digitts_per__numbrr
number1 PInt(probs_1[1), 0) 10 1
number2 += PInt(probs_2TH) 0) * 10 ** i
result = numberl + number2
return result
Algorithm Computing the sum of two numbers by explicitly constructing the joint distributions of the resulting digit. PInt is the plia primitive to construct probabilistic integers.
def sum_numbers
probs_1, probs_2 2_, digits_per_nunts
3
):
5 carry 0
result = []
for i in rragg(ciiitts_perr_ubbrr
sum_digit PInt(probs__]gg 0)
PInt(probs_ 0)
carry sug_digit % 10)
carry sum_digit // 10
result. append (carry) return result
13
Algorithm 3: Computing the sum of two probabilistic digits by computing conditional probabilities of the next digit in the resulting sum given the current digits by means of a carry.
Consequently, this task requires both solving the now probabilistic combinatorial problem together with training the neural classifiers. Note that this problem is far from trivial, as there are 10G-G possible ways to fill in a G x G sudoku puzzle.
Checking whether sudoku puzzle is correct requires checking if the sudoku constraints satisfied. While there are many encodings these constraints, PLIA, needs an encoding in terms of linear arithmetic operations. The encoding used is as follows. Every grid cell is associated with 10 binary probabilistic integers, leading to the probability of the kd binary integer of grid cell being equal should be interpreted the probability that the grid cell contains the number k. We represent these binary integers as 3-tensor B.g,, where i indexes cell (i. With this representation, expressing that row should only contain different digits is equivalent obtaining value of I after summing out the index from Byyk- Concretely, that is
10 such integers for the whole puzzle. Intuitively,
of the grid, indexes a column and & is the b binary digit of grid
Bigk = 1, Wi (1, G} and Vk (1,...,10 10).
(32)
Indeed, for fixed value of i.e. a single row i, there are constraints to satisfy, where each one excludes double presences of one of the 10 possible digits. The constraint that each column only
15

---

contains different digits is completely analogous to Equation 32, but instead summing over the row index i.
In case = 9, there are the additional constraints that the inner 9 blocks of the puzzle also have no repeating entries. The intuition is similar the other two constraints; we sum over all grid cells of block for each of the binary integers and should obtain 1. If we index the 9 inner blocks as a 3 x 3 grid with coordinates (1, m), then the equations
3- 3-(-1)3((mt) ΣE 3=
Big= 1,
v,, E 1,, and bk E (I,..., 10),
(33)
true if and only if each of the inner blocks has different digits in all of its grid cells.
Bringing everything together, PLIA, approximates the probability of a sudoku puzzle being correct by computing the product of the probabilities of all the above linear constraints. Note that this approach computes each of the constraints as independent of one another, allowing for the probability of each constraint be computed in parallel. Because PLIA, is based tensor manipulations, implementation can and does exploit this parallelism. Additionally, note that PLIA, works with srg--obbabilites in practice, which avoids the problem of numerical underflow often arising when taking long products of probabilities.
Choice of Encoding for Comparisons. The other methods compare to do not necessarily need to use the same binary linear arithmetic encoding as they are not restricted to linear arithmetic. Instead, their provided implementations directly encode every grid cell as categorical random variable with 10 outcomes, one for every possible digit. Expressing that row, column or block of grid cells only contains different digits is then done by comparing all pairs of categorical variables in the row, column or block. Each of these pairs then has to be different for the constraint to hold. To again provide fair comparison, we tested both encodings for Scallop and A-NeSI and took the best performing one. In both cases, the categorical encoding gave better runtime results.
F Details on Training the Neurosymbolic Methods
Since both the MNIST and visual sudoku task involve the classification of MNIST images, we use the same traditional LeNet [19] in both cases. Next we discuss the hyperparameters involved in training.
The optimal parameters for PLIA, and Scallop were found by performing a grid search on held- out validation set. The main hyperparameters important for all methods used for neurosymbolic learning are the learning rate and the number of epochs to train. For our grid search, we considered values (0.001, 0.005, 0.0001) } for the learning rate and (5. 10, 15, 20, 50, 100, 200} for the number of epochs. Scallop and PLIA, both consistently performed best with a learning rate of 0.001 in all experiments. Both Scallop and PLIA, use Adam [16] as optimiser. The number of epochs varies per experiment. On the MNIST task, PLIA, needed 10, 15, 100 and 200 epochs for N = 2, 4, N = 15 and N = 50, respectively. For Scallop, N = 2 and N = 4 ran optimally when training for 5 and 10 epochs, respectively.
For Scallop, with its top-k-bbsed approximate inference, it is additionally important to choose good value for k. If A too small, then the approximation quality is poor. If l: is too large, then it becomes prohibitively expensive to compute the approximation. Inspired by the implementation of Scallop, the possible values for were (1, 3, 5, 6, 7). For the MNIST addition task, all cases that did not time out, h: = 3 was optimal as it gave state-of fftte-of-hheaand performance and the quickest runtimes. The visual sudoku problem benefitted from a higher value of having an optimal value of 6. No
value of k allowed Scallop to run 9 x sudoku.
In stark contrast PLIA, A-NeSI has multitude of hyperparameters be We used the set of parameters provided in the original paper [33] and its implementation that were already used there to perform the experiments on MNIST addition and visual sudoku.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Claim 1
Supported by Section 2. Theoretical evidence that the FFT allows for O(N log N) computation of sum distribution using our proposed tensor representations.
Claim 2 Supported by Sections 3 and 4. Theoretical construction of tensorised representations of the necessary integer operations and probabilistic inference primitives to construct PLIA, scalable, differentiable and hyperparameter- framework for probabilistic linear integer arithmetic.
Claim 3 Supported by Section 5. All our experimental results clearly show PLIA, able to indeed outperform the state of the art in terms of both inference and learning time by multiple orders of magnitude.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We explicitly mention the problem of probabilistic inference is #P-hard in general and that PLIA, because of its exact inference, can still suffer from this limitation.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
17

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: In our more theoretical sections (Sections 2, 3 and 4), our discussion always clearly states the assumptions made, and when and how these can be lifted. Our proposed tensorised representations and the use of the FFT are all theoretically sound.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Sections 2, 3 and 4 clearly describe the theory behind our implementation and all details necessary for reproduction. Moreover, our full implementation, following these descriptions, is provided as supplementary material. Finally, the implementation together with the details given in the appendix, such as architectures, encodings and hyperparameters, are sufficient to reproduce all experiments. Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
18

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide our full implementation, complete with instructions and scripts exactly how to load the data and run the experiments. All data is publicly available and automatically downloaded, and the submitted code is fully anonymous.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines chttps://nipss cc/ public/ guggdes///// Code sorisssion ssionPolicy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: 1/n //nips.oo cc publ lic/ he//gdiesss guwdee//ooeeuubmm Subm ss i onPolic licy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification; All training and testing details are provided in the appendix, with corresponding code present in the provided implementation.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
19

---

Justification: All numerical results are provided with the necessary statistics, Figure 5 reports mean runtime with standard errors aggregated over 10 runs, following the experimental protocol of Cao et al. [5]. Table reports median values with corresponding 25 and 75 quantiles for all results, again computed over runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our compute resources are detailed at the start of Section 5, Times of execution are shown in Figure and Table
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //ess//////ppp.... /tthsstrt/://eerrisss hccppbbiic//tnniicsuueeeeeee
Answer: [Yes]
Justification: We have read the NeurIPS Code of Ethics and confirm we comply in every aspect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
20

---

10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: We do not explicitly mention societal impact as we do not foresee any immedi- ate positive or negative impact. However, it our hope that this progression on the state of the art allows solving more challenging combinatorial problems under uncertainty with positive effect on society in the future. Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. den.lymelo of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses no immediate risk for misuse, as it claims foundational advances on exact inference. However, this exact probabilistic inference could be used as safeguard itself in the future.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
21

---

All utilised libraries and code are properly credited through the correct citations, taking into account their applicable licences.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswi thcode. com/ da ta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The newly introduced asset of this paper is an implementation of PLIA, which is provided in the supplementary material and properly documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our entire paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB)
22

---

approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Our entire paper does not involve crowdsourcing nor research with human subjects.
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "JeHED5Mndd", "reviewer": "Reviewer_JM4B", "summary": "This paper presents an approach to compute probability distributions over sums of random variables. To achieve this, the authors replace as slow quadratic computation with a Fourier transformation and a Hadamard product that can be computed in log-linear time.\nThe authors introduce the log-sum-exp trick to improve the stability of the computations. In this process, the authors note that their approach is differentiable, which allows them to connect with work on neurosymbolic AI.\nThe authors present metrics that can be computed, and finally the authors present an empirical evaluation which demonstrates the accuracy and speed improvements of their approach.", "questions": "Do you do a special treatment for the case where the pmf is zero i.e., where the log is -inf? or do you simply allow it and let the exponential handle that? A small paragraph on that would be interesting.", "limitations": "no issues", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The connection to neurosymbolic AI is very interesting and in my opinion the most important part of the paper. The performance of the method both in accuracy and speed are significant. The implementation using GPUs and DNN libraries are valuable for the community.", "weaknesses": "My only concern with this paper, is that their work shares many similarities with the work in [1]. The authors do not cite this paper, which includes the convolutions and Fourier transform motivation which is known, as well as the use of the log-sum-exp trick. Providing a citation and a more thorough differentiation would be extremely valuable and maybe even required.\n\n[1] Parker, M. R., Cowen, L. L., Cao, J., & Elliott, L. T. (2023). Computational efficiency and precision for replicated-count and batch-marked hidden population models. Journal of Agricultural, Biological and Environmental Statistics, 28(1), 43-58.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for bringing the work of [1] to our attention!\n\nFirstly, we would like to clarify that we do not introduce the log-sum-exp trick as this is indeed a well-known trick to avoid numerical instabilities when summing probabilities in log space. Instead, we introduce a similar trick, dubbed the fast log-conv-exp trick, that avoids numerical instabilities when applying the FFT on probabilities in log space. \n\nSecond, we would like to stress the differences between PLIA$_t$ and [1]. Both utilise the FFT to improve computational efficiency of probabilistic inference. \n\n1. PLIA$_t$ and the method of [1] use the FFT for probabilistic inference on different applications. PLIA focuses on scaling probabilistic inference in linear integer arithmetic, while [1] uses the FFT for N-mixture models and applies it to the open-population model of [2].\n\n2. While [1] does discuss numerical instability of computing convolutions in log space, their proposed solution differs from our proposed fast log-conv-exp trick in the following way. As can be seen from algorithm 2 in [1], their approach is to use the traditional log-sum-exp trick inside each iteration of the FFT and inverse FFT, which prevents using any off-the-shelf FFT algorithm and adds computational overhead (note that FFT algorithms are extremely tough to implement efficiently). In contrast, our trick exploits the linearity of the Fourier transform to show it is possible to simply rescale the in- and outgoing log probabilities by their maximum to prevent numerical instabilities. Just like the linearity of the summation does for the log-sum-exp trick. This means we go to and from linear space only once instead of at every iteration in the FFT. Our approach has the advantage of being implementation-agnostic, allowing for off-the-shelf and highly optimised FFT implementations to be used.\n\n\n3. The proposed tensorised representations and operations of PLIA$_t$ are crucial for the measured increase in performance. Additionally, they also lead to out-of-the-box differentiability. Both of these aspects are not discussed nor examined by [1]. Moreover, [1] only reports an improvement of 6x-30x in computation time for two specific population models, while we observed improvements in the order of 100 000x in our benchmarks compared to the state of the art.\n\n\n4. The work of [1] only proposes a solution for computing numerically stable convolutions (discussed in points 2 and 3 above). We do provide further operations that can be performed efficiently, e.g. multiplication by scalars and probabilistic branching. This is not discussed at all in [1].\n\nWe will add a reference to [1] to the paper and also include the above discussion.\n\nThird, to answer your question, our implementation does allow for -infinity in case the PMF is zero. We utilise the numpy implementation np.inf that adheres to the IEEE 754 [3] industry standard for representing infinity as a floating-point number. Moreover, this implementation is compatible with all operations of our deep learning backend, TensorFlow.\n\nWe hope to have clearly differentiated PLIA from the cited work and to have addressed all your concerns. If so, we hope you are open to the idea of raising your score. If not, we will gladly try to discuss any remaining concerns.\n\n[1]  Parker, M. R., Cowen, L. L., Cao, J., & Elliott, L. T. (2023). Computational efficiency and precision for replicated-count and batch-marked hidden population models. Journal of Agricultural, Biological and Environmental Statistics, 28(1), 43-58.\n\n[2] Dail, D., Madsen, L. (2011). Models for estimating abundance from repeated counts of an open metapopulation. Biometrics 67(2):577–587.\n\n[3] IEEE Standard for Binary Floating-Point Arithmetic. 1985.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1yisoSmBti", "reviewer": "Reviewer_Ltsw", "summary": "The paper addresses key challenges in applying neurosymbolic AI techniques, specifically in integer arithmetic. Leveraging the power of tensor operations and the fast Fourier transform (FFT), the authors propose a novel approach to perform probabilistic inference on integer-valued random variables. Central to their method is the tensor representation of the distributions of bounded integer-valued random variables, enabling efficient computation of distribution sums using FFT, thus significantly reducing computational complexity from quadratic to logarithmic time complexity. The study validates the effectiveness of this approach through experiments showing substantial improvements in inference and learning times, pushing the state of the art by several orders of magnitude. This contribution not only enhances computational efficiency but also facilitates gradient-based learning, which was previously challenging due to the discrete nature of integers.", "questions": "1.  Could the authors provide additional details about the computational environment, versions of libraries used, and precise parameter settings?\n2.  How do the authors address potential underflow or overflow problems during computations, and what impact might these issues have on the method's accuracy and stability?\n3. Are there plans or ongoing work to test the applicability of this approach in other fields that heavily rely on integer arithmetic, such as cryptographic algorithms or complex financial computations? Insights into such applications could significantly enhance the paper's impact.", "limitations": "One potential limitation is the paper's reliance on specific assumptions for the efficiency of FFT in the log-domain. While these assumptions are necessary for the mathematical framework, there is limited discussion on how sensitive the results are to deviations from these assumptions. Exploring the robustness of the proposed method under less ideal conditions or discussing potential modifications that could accommodate more general cases would strengthen the paper.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a creative approach to tackling the computational challenges in probabilistic inference for integer arithmetic. The innovative use of tensor operations and the fast Fourier transform (FFT) to represent and compute the distribution of integer-valued random variables is a notable advancement. This method is original in its application of FFT in the log-domain for probabilities, which is a sophisticated adaptation not extensively explored in previous studies within the neurosymbolic AI domain.\n\n2. The paper is exceptionally well-written, with a clear structure and logical flow that enhances readability. Technical concepts and methods are explained with precision, making the complex content accessible to readers who may not be intimately familiar with the technical details of probabilistic inference or FFT. Diagrams and examples further aid in understanding and illustrating key points effectively.\n\n3. The significance of this work is manifold. Firstly, it addresses a critical bottleneck in neurosymbolic AI, opening up new possibilities for applying these techniques to more complex, real-world problems. The ability to perform differentiable operations on discrete data structures could have profound implications for the field, potentially influencing future research directions and applications.", "weaknesses": "1.While the paper briefly mentions the inherent #P-hardness of probabilistic inference, there is scant elaboration on how this impacts the scalability or applicability of the proposed method in practical, large-scale scenarios. A more detailed discussion of the practical limitations, potential computational bottlenecks, or scenarios where the method might not perform as expected would be invaluable for readers and practitioners looking to apply these techniques.\n2. The clarity and depth provided in the theoretical formulation and experimental setup are excellent. However, the paper could be enhanced by including more detailed information on the implementation, such as the specifics of the software environment, libraries used, and parameter settings. This addition would aid in reproducibility and allow other researchers to more easily validate and build upon the work.\n3. The paper could further detail the algorithmic complexity of the proposed method beyond the FFT application. While it highlights the reduction in time complexity, there's minimal discussion about space complexity or the computational overhead introduced by tensor manipulations and log-domain calculations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review and appreciate the raised concerns. We will start below by answering the main questions:\n\n1. Our precise parameter settings are detailed in Appendix E for the neurosymbolic experiments (cf. Section 5.2), being learning rate, number of training epochs and neural architecture. As PLIA$_t$ itself is a hyperparameter-free framework, there are no other parameters to set when just performing inference in PLIA$_t$ (cf. Section 5.1).\nAll other implementation details are provided in the supplementary code material (submitted together with the paper), where the precise computational environment, including the exact versions of all necessary libraries, are given. Moreover, our complete implementation of PLIA$_t$, its experiments and the precise parameter settings can also be found in the supplementary code material for ease of reproducibility. Finally, we will publicly release PLIA$_t$ upon acceptance.\n\n\n2. The issue of numerical overflow or underflow is addressed in Section 2.2. There, we introduce a new variant of the well-known log-sum-exp trick for FFT computations in the log domain, called the fast log-conv-exp trick. Using the fast log-conv-exp trick PLIA$_t$ runs without any numerical stability issues.\n\n\n3. We are currently looking into many different application domains for PLIA$_t$ as the scalability results from our experiments, where we observe orders of magnitude better performance, seem to indicate it is an enabling technology. We did not yet consider applications in cryptography or finance, but these are indeed promising directions! We thank the reviewer for bringing these to our attention.\n\n\nAs for the weaknesses, we would like to address your raised concerns about limitations, complexity and computational overhead.\n\n**Limitations.** We acknowledge the discussion on the practical applicability of PLIA$_t$ could be extended. We propose to add the following discussion to the camera-ready version of the paper.\n\nThe inherent #P-hardness of probabilistic inference does remain the main bottleneck for PLIA$_t$ and can be observed in our experiments. During the comparison between PLIA$_t$ and the state-of-the-art approach of Cao et al. [1] in Figure 5, we can see that PLIA$_t$ also starts to take a significant amount of time when the domain of the probabilistic integers grows. Hence, if the explicit computation of probabilistic integers with a very large domain is required, then PLIA can still struggle. However, PLIA$_t$ does scale orders of magnitude further (5 to be precise) than what was possible so far and considerably pushes the envelope on the state of the art.\n\n**Space complexity.** It is well-known that the FFT has, apart from the $N \\log N$ runtime complexity, also $N \\log N$ theoretical space complexity, again in contrast to a $N^2$ space complexity of the naive approach. Moreover, we performed an additional empirical comparison between Dice [1] and PLIA$_t$ with respect to memory allocation (see attached PDF in global rebuttal), where we indeed confirmed the better scaling behaviour of PLIA$_t$. Hence, PLIA$_t$ not only outshines Dice (the current state of the art) in terms of runtime but also in terms of memory usage. We will add this comparison to the appendix and mention it in the main paper in Section 5.1.\n\n\n**Computational overhead.** Finally, the computational overhead, including construction of the computational graphs for PLIA$_t$, is already included in the time measurements of all our experiments. For smaller domains, it is indeed possible that PLIA$_t$ on CPU or even Dice can outperform PLIA$_t$ on the GPU (Figure 5, bitwidth strictly below 5). However, it is clear that this computational overhead has a diminishing effect, as PLIA$_t$ clearly scales better than Dice for larger, more practical domain sizes (Figure 5, bitwidth above 5). Moreover, much of this overhead can be avoided by running PLIA$_t$ on the CPU for smaller domain sizes, where it performs on par or better than Dice (Figure 5, bitwidth strictly below 5). We will also make this point clearer in our experimental discussion in Section 5.1.\n\n[1] Cao, W. X., Garg, P., Tjoa, R., Holtzen, S., Millstein, T., & Van den Broeck, G. (2023). Scaling integer arithmetic in probabilistic programs. In Uncertainty in Artificial Intelligence (pp. 260-270). PMLR.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YWxhVUmFi3", "reviewer": "Reviewer_GGzh", "summary": "The paper presents a framework, PLIA_t, to solve the generally intractable problem of probabilistic inference using the fast Fourier transform (FFT) for integer-valued random variables. The paper shows how to use the log-sum-exp trick to solve the numerical stability issue in the FFT setting and defines arithmetic operations on integer-valued random variables. It also defines how to compute expected values and how to handle probabilistic branching. Experiments show that the gains can be realised in an implementation for the given examples.", "questions": "- Can you please characterise / define PLIA_t formally as a framework in the rebuttal?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper tackles a central problem, probabilistic inference, from a new perspective to the best of my knowledge.\n- The results are promising.", "weaknesses": "- Even though the paper plans to introduce PLIA_t as a new framework, the framework itself remains rather opaque regarding its inputs, outputs, representations, algorithms, or whatever they consider part of PLIA_t. It almost reads as if a section is missing between Section 4 and 5. As such, I am also not so sure about the reproducibility of the experiments. (I have formulated a corresponding question. This is one of the main reasons for my overall score that I am willing to revise given a convincing rebuttal.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort, and for their suggestion of formalizing PLIA$_t$. For the camera-ready version we propose to add the following subsection at the end of the Section 2:\n\n### 2.4. Formalizing PLIA$_t$ \n\n**Definition** *(probabilistic linear arithmetic expression)\nLet  $\\{X_1, …X_N\\}$ be a set of $N$ independent integer-valued random variables with bounded domains. A probabilistic linear integer arithmetic expression X is a bounded integer-valued random variable of the form\n$$\nX = \\sum_{i=1}^{N} f_i (X_i).\n$$\nIn the equation above the functions $f_i$ denote operations performed on the specified random variables that can be either one of the operations specified in Section 3 as well as compositions thereof.*\n\nPLIA$_t$ is concerned with computing the parametric form of the probability distribution of a linear integer arithmetic expression. It does so by representing random variables and linear combinations thereof (cf. Definition of probabilistic linear arithmetic expressions) as tensors whose entries are the log-probabilites of the individual events in the sample space of a the random variable that is being represented. Note that operations within PLIA$_t$ are closed. That is, performing either of the operations delineated in Section 3 will again result in a bounded probabilistic integer representable as a tensor of log-probabilities and an off-set parameter indicating the value of the smallest possible event (cf. Section 2.3). In Section 4 we also equip PLIA$_t$ with probabilistic inference primitives that allow it to compute certain expected values efficiently as well as to perform probabilistic branching.\n\n\n<END OF SECTION 2.4>\n\n**Reproducibility concerns.** We would like to stress that the complete implementation of PLIA$_t$, including all operations discussed in Sections 3 and 4, are provided in the supplementary material of our submission. This code also contains our complete experimental setup and automatically installs all necessary dependencies in an easy-to-run script as documented in the provided README file. PLIA$_t$ is a hyperparameter-free framework for inference tasks (cf. Section 5.1). For the neurosymbolic learning tasks (cf. Section 5.2) we provide all our optimal parameters in Appendix E. Upon acceptance, we will also make this implementation publicly available. In this regard we believe we follow best practices concerning reproducibility.\n\nWe hope our answers have addressed your concerns and allow for an increase in score. Please let us know if there are any further concerns and we will gladly try to address them.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZNIpZVQ9OK", "reviewer": "Reviewer_DnxY", "summary": "The authors study the problem of probabilistic inference's scalability in the integer arithmetic setting. Their method is based on the representation of integer-valued random variables probability mass functions (PMFs) as vectors and the observation that PMFs of different operations applied on said random variables can be expressed as convolutions of the PMFs vectors by leveraging Fast Fourier Transforms.", "questions": "- More test to understand the limits of the approach in terms of scalability can be useful. How far can you push the size of MNIST addition by allowing, e.g. 1 hour computational time?", "limitations": "-", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The method and the mathematical background underlying the proposed approach for probabilistic inference over integer-valued random variables are well-detailed. \nThe Fast Log-Conv-Exp trick and related computational aspects are properly discussed.\nThe PLIA framework and its implementation seem fairly simple, allowing the authors to scale probabilistic inference over larger integer problems and neurosymbolic learning surpassing previous state-of-the-art approaches.", "weaknesses": "- The experimental part is a bit limited and could be extended to show more clearly potential and limitations of the method", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their supportive review. Please allow us to address your experimental concern below.\n\nOur experimental evaluation tackled two of the most prominent neurosymbolic benchmarks, where PLIA$_t$ outperformed both exact and approximate state-of-the-art methods for neurosymbolic learning. It demonstrates that the field of neurosymbolic AI is in need of more challenging benchmarks, as we have shown that it is now possible to solve both MNIST addition and visual sudoku quickly and accurately. The goal of our paper is to scale probabilistic inference on linear integer arithmetic, which we illustrate by outperforming the state-of-the-art in inference (exact method) by 100 000x and the state of the art in learning (approximate method) by 100x in terms of run time. Hence, we fully agree it is high time for more challenging benchmarks, yet proposing new benchmarks is not the aim of this paper.\n\nFurther scaling the MNIST addition task to more digits is limited by the size of the dataset, as there are only 60 000 images available for training and 10 000 for testing. Each of these images can only be used once in the construction of the various sums, meaning increasing the number of digits leads to an overall reduction of available sums for training and testing. For example, our case of $N = 50$ requires 100 images to construct a single sum data sample. Consequently, the test dataset only contains 100 samples, which was the lowest number of samples we were still comfortable with to compute test statistics over. We did run learning experiments with $N = 100$ and even $N = 1000$, but we do not deem their test statistics faithful enough to be reported.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their valuable comments and suggestions to improve the paper. Our rebuttal to the individual reviews can be found directly under each review. We also attached a plot (as pdf) used to address Reviewer Ltsw's concern regarding memory usage.We discuss this issue just below.

We hope the rebuttal clears up some of the concerns and allows the reviewers to reconsider their inital scores. Please let us know if there are remaining imprecisions/unclarities.


#### **Space Complexity**

We thank Reviewer Ltsw for raising the concern of space complexity and memory usage, and acknowledge this aspect was not properly covered. While it is well-known that the space complexity of the FFT is also $N \log N$, just as its runtime, an empirical comparison was still missing. To this end, we analysed the memory consumption of PLIA$_t$ for the inference tasks in Section 5.1 and compared it to the state of the art, Dice [1]. The result can be seen in the attached PDF showing that PLIA$_t$ indeed scales better and seems more efficient in terms of memory usage compared to the state of the art across all inference benchmarks. We will add the attached figure to the appendix and refer to it during our experimental discussion in Section 5.1.


[1] Cao, W. X., Garg, P., Tjoa, R., Holtzen, S., Millstein, T., & Van den Broeck, G. (2023). Scaling integer arithmetic in probabilistic programs. In Uncertainty in Artificial Intelligence (pp. 260-270). PMLR.

Meta-review: This paper describes a simple idea for probabilistic inference over linear, integer systems, based on the well-known property that the distribution of a linear combination of random variables can be performed using the Fourier representation. This allows the authors to frame their inference process using tensor operations, with a useful byproduct being that the entire computation becomes differentiable and usable in learning. Empirically, they show very high speedups and show the application of their ideas to neurosymbolic programming. 
The ideas in the paper are straightforward, with the result that some of the text feels obvious — the discussion of zero-padding to match vector lengths, for example, and even the authors’ log-sum-exp trick contribution. However, in their application they manage to improve over very recent work in significant ways.  One reviewer pointed out a closely related publication, which the authors’ response indicated they would incorporate.  Otherwise, reviewers were agreed on the potential impact of the work, with a few concerns that were generally well addressed by the author response.
Decision: Accept (poster)