Neurosymbolic Diffusion Models
Authors: Emile van Krieken
Pasquale Minervini
Edoardo Ponti
Antonio Vergari
Venue: NeurIPS 2025 poster ()
Keywords: neurosymbolic AI
discrete diffusion models
probabilistic reasoning
uncertainty
reasoning shortcuts
Primary area: probabilistic_methods
TL;DR: We integrate discrete diffusion models with neurosymbolic predictors for scalable and calibrated learning and reasoning

Abstract: Neurosymbolic (NeSy) predictors combine neural perception with symbolic reasoning to solve tasks like visual reasoning. However, standard NeSy predictors assume conditional independence between the symbols they extract, thus limiting their ability to model interactions and uncertainty --- often leading to overconfident predictions and poor out-of-distribution generalisation. To overcome the limitations of the independence assumption, we introduce _neurosymbolic diffusion models_ (NeSyDMs), a new class of NeSy predictors that use discrete diffusion to model dependencies between symbols. Our approach reuses the independence assumption from NeSy predictors at each step of the diffusion process, enabling scalable learning while capturing symbol dependencies and uncertainty quantification. Across both synthetic and real-world benchmarks — including high-dimensional visual path planning and rule-based autonomous driving — NeSyDMs achieve state-of-the-art accuracy among NeSy predictors and demonstrate strong calibration.

Neurosymbolic Diffusion Models
Emile van Krieken'
Pasquale Minervini Edoardo Ponti 1
Antonio Vergari !+
"Shooo of Informatics, University of Edinburgh
Miniml.AI
eraann @ {p.minervini, eponti, avergari @ @ed.ac.uk
Abstract
Neurosymbolic (NeSy) predictors combine neural perception with symbolic reasoning to solve tasks like visual reasoning. However, standard NeSy predictors assume conditional independence between the symbols they extract, thus limiting their ability to model interactions and uncertainty often leading to overconfident predictions and poor out-of-distribution generalisation. To overcome the limitations of the independence assumption, we introduce newrosymbolic diffusion models (NESYDMs), new class of NeSy predictors that use discrete diffusion model dependencies between symbols. Our approach reuses the independence assumption from NeSy predictors each step of the diffusion process, enabling scalable learn- ing while capturing symbol dependencies and uncertainty quantification. Across both synthetic and real-world benchmarks - including high-dimensional visual path planning and rule-based autonomous driving NES achieve state-of- the-art accuracy among NeSy predictors and demonstrate strong calibration.
Introduction
Neurosymbolic (NeSy) methods aim to develop reliable and interpretable Al systems by augmenting neural networks with symbolic reasoning [25, 26, 77J. In particular, probabilistic neurosymbolic predictors [52, 54, 57, 80] learn neural networks that extract high-level symbols, also called concepts, from raw inputs. These concepts are latent variables used in interpretable symbolic programs to reason and predict output labels. However, recent work highlights that the reliability of NeSy predictors is not guaranteed, especially under certain common architectural choices.
More specifically, in many real-world settings, NeSy predictors fail silently: they can learn the wrong concepts while achieving high accuracy on output labels [22, 27]. This issue arises when the data and program together admit multiple concept assignments that are indistinguishable [54, 56). How do we design NeSy predictors that handle this ambiguity? Marconato et al. [55] argued that NeSy predictors should express uncertainty over the concepts that are consistent with the data. Then, uncertainty can guide user intervention, inform trust, or trigger data acquisition when the model is uncertain [55].
However, most existing NeSy predictors cannot properly model this uncertainty, as they rely on neural networks that assume (conditional) independence between concepts [10, 80, 86). While this assumption enables efficient probabilistic reasoning [6, 73, 80, 86], it also prevents these NeSy predictors from being aware of concept ambiguity and thus reliably generalising out-of-distribun [39, 79]. Therefore, designing expressive, scalable and reliable NeSy predictors an open problem.
To fill this gap, we design neurosymbolic diffusion models (NESyDMs). NESYDMs are the first class of diffusion models that operate over the concepts of NeSy predictor in conjunction with symbolic programs. In theory, discrete diffusion models [9, 68] are particularly suited for NeSy predictors, as each step of their denoising process involves predicting discrete distribution that fully factorises.
Shared supervision.
Code is available at
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Input
Predicted concepts è
Pa(Co) x,
Unmasking model
Program s<c")
80(c x, k,y")
a(c' ce))
(Dijkstra)
Variational posterior
Mask
Concepts c²
Masked concepts cf
Gradient estimation
(0
True path Yo
Costs:
grass
sand
rock
masked
Predicted path y
Figure I: NESYDMS integrate masked diffusion models (orange boxes) with symbolic programs (blue box) to learn to predict the minimum cost path in a visual path-planning task. A variational posterior (Section 3.3) first obtains a candidate concept c², that represents the costs of traversing each cell of the grid. Then, we partially mask c using the masking process q(c" c²) to obtain masked concepts e², We feed this to the discrete diffusion model's unmasking model pe c²) to predict the unmasked concepts σ We use the symbolic program yo, which we choose as Dijkstra's 's algorithm, to map the predicted concepts č to the predicted path y Finally, update the parameters of the unmasking model. Dotted arrows denote samples from a distribution.
gradient estimation to
We use this local independence assumption to profit from the insights and machinery of classical NeSy predictors, while modelling concepts dependent entities globally. In practice, designing diffusion process for NeSy predictors is highly non-trivial, as it requires dealing with a symbolic program and marginalising over all possible concepts, task that is intractable in general. We show how to solve both aspects effectively by devising a novel continuous time loss function for diffusion that incorporates symbolic programs, for which training scales gracefully.
Contributions. After discussing the background on NeSy predictors and (masked) diffusion models in Section 2, we (cl) introduce NESYDMS in Section 3, class of scalable NeSy predictors that model concept dependencies by formalising a masked diffusion process [68]. Then Section 3.2, we (c2)
derive principled loss function for NESYDMs and present an efficient gradient estimator for training To derive this loss, we prove that continuous-time losses of masked diffusion models extend to non-factorised distributions. Finally, in Section 4, we (c3) empirically show that NESSDMs (i) both calibrated and performant on tasks from the RSBench suite of visual reasoning problems [11] while (ii) scaling beyond the state-of-hhe-aee the complex visual path- maannplanning task [64].
2 Background
2.1 Neurosymbolic predictors
We aim to learn a parametrised predictive model Po xx that maps sigh-dimensional inputs x to Y d-dimensional discrete labels y [V,"", where each label can take value in [Vy] 21, 2...... V.. } typical (probabilistic) NeSy predictor implements (y x) by first (i) using a concept extractor, i.e., neural network (c x) that maps the input x C-dimensional vector of symbolic concepts c E [V]]c_ i.e., discrete variables encoding high-level information that can take V values. Then, (ii) the NeSy predictor maps concepts through program &p [V.]o [Vy]* obtain output predictions y. As usual in NeSy [10, 43, 52, 80], we only assume access to training data for input- output pairs (x, y) but labelled data for concepts c, i.e., concepts are latent variables. Formally, we define the predictor pe (y x) by marginalising over all concepts e E V. that are consistent with
For simplicity of presentation, we assume that the number of possible values V is the same for both concepts and labels, but this is necessary for the paper.

---

the output summing their probability masses:
poly x) Epo(e x)1[f(c) y).
(I)
The equation above is also known as computing conditional weighted model count (WMC), and it is central to several probabilistic neurosymbolic methods [6, 43, 52, 80, 86].
Example 2.1 ([65]). Consider the visual path- aath-laaniing task in Fig. where the task is to predict a minimum cost path from the top-left corner to the bottom-right corner of the visual map x. y is encoded as binary matrix, where cells traversed form path. neural network extracts concepts that represent discrete costs с for each cell on the grid, then search algorithm (ec), like Dijkstra, is used find the shortest path y according to costs c.
Reasoning shortcuts. Recent work proved NeSy predictors susceptible to reasoning short- cuts [RSs; 56], which is when a model ( x) learns to predict the output labels y correctly given the input but incorrectly maps inputs to concepts c. Since we cannot catch RSs on the training data, it can dramatically harm model performance on unseen data [53]. Mitigating RSs is challenging and potentially costly [54, 56]. However, models can be made aware of their RS by properly expressing uncertainty over all concepts that are consistent with the input-output mapping, improving reliability and generalisation [39, 54, 55]. Then can, for example, deploy NeSy predictors in an active learning setting where uncertain concepts are queried for extra labelling.
Example 2.2. Consider an input x containing two MNIST digits that are either 0 or The unseen concepts с are the digits, and (p()) returns 1 if the two digits are different, otherwise 0. A neural concept extractor po x) that maps MNIST digits of to and MNIST digits of 1s to Os will perfectly fit the input-output mapping.
The configuration in Example 2.2 maximises Eq. 1 without learning the ground-truth concepts. Given only input-output pairs, it is not possible to distinguish this RS from the correct input-concept mapping. Instead, given ground-trum trunh concepts c* = (0, 1), an RS-aware model would assign some belief to both options (0, 1) and (1, O).
Independence assumption and its limitations. Unfortunately, in practice, the vast majority of NeSy predictors make an architectural assumption that prevents RS awareness: the conditional independence of concepts с given inputs x [43, 80, 86). Formally, this assumption implies that (o x) in Eq. factorises as I 1=1 Po x). NeSy predictors use this assumption to perform efficient probabilistic reasoning via WMC solvers and knowledge compilation techniques [15, 18, 63], or by developing efficient approximation algorithms [73, 80].
Recent work proved that such models cannot simultaneously represent the relevant uncertainty over different concepts while maximising Eq. [39]. To see why, consider Example 2.2, with true concepts c = (0, 1). The only maximisers of Eq. for the independent model are to either deterninistically return (0, or (1,0) [39, 79]. However, there is no maximiser that can simultancously assign probability mass to both cases, meaning independent models cannot be RS-aware. To overcome this limitation, we should design a NeSy predictor that can express dependencies between concepts, which we address next.
2.2
Which expressive model class for NeSy?
Previous work on NeSy predictors without the independence assumption explored mixture models and their generalisation as probabilistic circuits [6, 16). An example is BEARS [55], which is specifically designed for RS- -s-awrressss. A related approach is to add extra variables and constraints to the WMC This can, for instance, be done using a probabilistic programming language [43, 51]. However, these methods require (i) compiling the program into a logic circuit via knowledge compilation and (ii) ensuring the probabilistic circuit is compatible with this logic circuit [83]. The first step can require exponential time in the worst case, and as such scaling to high high-dimensional spaces can be challenging [4, 80). Furthermore, these methods require the neural concept extractor to predict many more additional parameters for the different mixture components.
Alternatively, autoregressive models are common type of expressive model, but using these in NeSy predictors based on Eq. is computationally hard, as the marginalisation over concepts does not commute with autoregressive conditioning [3, 5]. While this limitation also holds for diffusion
3

---

models, they do use conditional independence assumption locally at every denoising step. This local assumption is sufficient to encode global dependencies. Furthermore, the locality allows us to design neural models that predict only C' parameters, just like NeSy predictors with the independence assumption. Thus, we use masked diffission models [68] that achieve expressiveness by iteratively unmasking a discrete sample. We discuss in Section 3 how to extend their local independence assumption to realise NeSy predictors.
Masked diffusion models. Diffusson models encode an expressive joint distribution over concepts c by defining a forward process that a neural network modelling reverse process will learn to invert. As our concepts are symbolic, we need a diffusion process for discrete data [9, 90]. We choose masked diffusion models (MDMs) [68, 72), type of discrete diffusion model with promising results on language modelling [61, 89] and reasoning [88]. MDMs allow us to derive principled loss using the program yp (Section 3.2) and develop scalable approximations (Section 3.4). We first review MDMs in their vanilla form, i.e., to model an unconditional distribution over concepts, po (c()..
MDMs consider continuous time diffusion process [9, 14], where the forward process gradually masks dimensions of a data point ca into a partially masked data point c² E [V. + +1 at time steps t [0, 1]. We extend the vocabulary size include placeholder
Ve+ + 1 for masked dimensions. The data point becomes fully masked as c' m .m] at time step 1. More formally, for 0 S 8
<
1 < 1, the forward process y masks a partially masked concept c* into cf with
C
g(c² c*) = II 1=1
1
c3] +
ar a, 1[c uld m]:
(2)
where a [0 - [0, 1] is a strictly decreasing noising schedule with og = 1 and 01 = 0. q(c' | c*) masks each dimension with probability 1- 01, leaving unchanged otherwise. Importantly, once masked, a dimension remains masked. MDMs learn to invert the forward process q(c" | c*) using trained reverse process po(c" c²). The reverse process starts at fully masked input c = at time step 1, and gradually unmasks dimensions by assigning values in {1,..., Va).
a,
The reverse process (o c²) is usually parameterised with conditionally independent unmasking models pe ct) = 11 (e | c²) that predict completely unmasked data e0 given (partially) masked versions c Then, MDMs remask some dimensions using the so-called reverse posterior q(c* c', E²) (see more details Eq. 10 in Section A):
po(c" c²) = Σ (o c') g(c" |c,cc= =c)) 20
(3)
The standard loss function masks c" partially to obtain c². and then uses the conditionally independent unmasking model (e c²) to attempt to reconstruct c". This loss function requires that pe (c" ct) implements the carry-over unmasking assumption, meaning should assign a probability of I to the values of previously unmasked dimensions. We provide additional background on MDMs in Section Next, we discuss how to design novel MDMs tailored for NeSy prediction.
3 Neurosymbolic Diffusion Models
To overcome the limitations of the independence assumption haunting NeSy predictors, our neu- rosymbolic diffusion models (NESyDMs) use MDMs to learn an expressive distribution over concepts and labels while retaining this assumption locally, enabling scaling. To develop NESYDMs,
extend
MDMs by (i) conditioning on the input x, (ii) acting on both concepts e and outputs y, treating concepts as latent variables and (iii) providing differentiable feedback through the program p. We first define this model in Section 3.1 and then derive a principled loss in Section 3.2. We discuss how to optimise this loss in Sections 3.3 and 3.4 3.4, and finish by discussing inference in Section 3.5, Finally, Fig. provides an overview of the loss computation of NESYDMS.
3.1 Model setup
We define NESYDMs using a conditionally independent unmasking model po(E" c' x) and program y that maps concepts to outputs. We use forward processes for both the concepts q(c) c*) and the outputs g(y" y²), each defined as in Eq. 2. The concept reverse process pe cc,x) is

---

parameterised as in Eq. with conditional concepr unmasking model po(č") | c²,x), and the outpu reverse process po (y" c², ".y', xx) parameterised by reusing the concept unmasking model:
pa(y" c c",y",
Σ po(C" c", x))(("" ly' ppy (é")). 80
(4)
po(y" yy, x) takes the concept unmasking model and marginalises over all concepts e" that consistent with the partially masked output y". To implement the carry-over unmasking assumption, we use Pyr to refer to variation of the program yp that always returns yf if dimension in y". We refer to Section D.I for details. The neural network for the concept unmasking model Po(c") c',x) can be readily adapted from NeSy predictors as defined in Eq. by additionally conditioning the neural network (e x) on the currently unmasked concepts c².
unmasked
Since do not have direct access ground-truth concepts c², will use variational setup and derive a lower-bound for the intractable data log-likelihood po (y x) (fully defined in Eq. 45). In particular, we use a variational distribution qo (c yy, x) that shares parameters O with the MDM to approximate the posterior (c yy, x). ) To implement this, we repurpose our concept unmasking model (o(c* c² x) with the controlled generation method from [29], which describe in Section 3.3. We provide more details and full derivation of the log- ligelioel in Section D.I.
3.2 Loss function
We next derive a NELBO for NESYDMs. Intuitively, we define the NESYDM reverse process over T discrete steps, and then consider the data log- log-likelihood as T goes to infinity, giving NELBO for continuous-timg process. This NELBO will be the base for the loss function used to train NESYDMS.
Theorem 3.1. Let po | | x) be concept unmasking model, program, (e y x) a variational distribution, and ar noising schedule. Then, we have that the D
[Va]e + [Vy] given
data log- -ikelikhokod as T - is bounded as lim logP8 NESYDMM (y" x) S LNESYDM, where
a
LNESYDM 10, (0.1) (e((ee
Σ
logpo |',x)
att
Lei concept unmasking loss
(5)
+ 0
log
Σ po |c, xx,x))l+(("); = vll
- (( |y,,
1=1
20
Cuta] variational entropy
By: output unmasking loss
We provide derivation of this NELBO in Section D.2. This NELBO has three components:
The concept unmasking loss Le is like the unmasking loss used in MDMs (Eq. 14). Since we do not have access to the ground-truth concept c", sample e from the variational distribution qo (c y", x) and ask the model to reconstruct c" from partially masked version cf ~ q(ce c²).
The output unmasking loss Ly is sum of weighted model counts (WMC) like in Eq. one for each dimension i of the output y". Unlike Eq. Cy weights concepts using the concept unmasking model po c². x) that is conditioned conditionally independent concept unmasking models, meaning we can use standard techniques in the NeSy literature to compute this loss efficiently. Section B provides additional analysis.
partially masked concepts c'. Importantly, we
The variational entropy Lujg is maximised to encourage the variational distribution to cover all concepts c that are consistent with the input x and output y
To derive the NELBO, we had to prove a new theorem that extends the standard MDM NELBO to non-factorised unmasking models po (e c²) (Section C), which can be an interesting result for future MDM architectures even outside NeSy predictors. We need this result because, unlike the concept reverse process, the output reverse process Po (y c* y y², x) in Eq. 47 does not factorise. and we cannot naively apply the standard MDM NELBO given in Eq. 14.
5

---

3.3 Variational posterior
To compute the NESYDM NELBO, we require variational distribution go y x) to sample likely concepts c' that are consistent with the ground -trtt output yO. We achieve this by adapting the sampling algorithm described Section 3.5 using a concept unmasking model pe pe(c") |c', xx)x) that
depends on the output y" and the program yp:
go (c c',y", x) = pa c', -x) - y
2(c',x,y²)
where 2(c", x²) is a normalising constant. This redefines the standard unmasking process from Eq. 3 by only considering valid e Unfortunately, sampling from (e c',x, y²) is NP-hard [33, 491. However, we have a tractable representation of the program y. e.g., a polysize circuit as the output of knowledge compilation step [63], then
represent qa(c") c', y x) compactly and exactly sample from it [6]. Without access to such a circuit, we can instead use relaxation of the constraint similar to [29]. Let (e | y²) exp(-8 Ex= (pp(,") & v()), where 3 >> 0 and / + oo approaches the hard constraint. At each step in the reverse process, we resample to approximately obtain samples from ug (c)) y") x po(c" | c', (') y") [29]. This procedure may sample concepts 2 that are inconsistent with y", but prefers samples that reconstruct more dimensions of y". We find that reasonably large B >> 10 works in our experiments. In practice, this effectively samples K times from pa | c x) and chooses the sample that violates the fewest constraints. See Section F.I for details.
3.4
Loss optimisation and scalability
Next, describe how we optimise the NESYDM NELBO LNESYDM using gradient descent. We design a gradient estimation algorithm that scales to large reasoning problems by approximating intractable computation. Note that, given samples c c¹ v' (o x, y") q(c² | cD), the empirical concept unmasking loss Le is tractable, so we only discuss how to backpropagate through the output unmasking loss Ly and the variational entropy Liggg-
Computing the output unmasking loss Ly involves computing multiple WMCs, which are #P-hard. One option is to compute each WMC exactly using circuits obtained via knowledge compilation [37, 52, 86]. However, to ensure scalability, we develop a sampling- based approach that approximates the WMC gradients [73]. In particular,
REINFORCE-basee gradient estimator [59]. the REINFORCE Leave-One-on Out (RLOO) estimator [1. 38). RLOO is similar to the popular GRPO algorithm [71] while being unbiased. Furthermore, RLOO allows for flexible tradeoffs between variance and computation constraints by choosing the number of samples.
However, methods like RLOO can fail for problems where the probability of getting sample T consistent with y is very low: when we only sample inconsistent concepts čo, RLOO does not provide any gradient signal. However, the output unmasking loss is subtly different, as Ly gives a signal for each of the dimensions of yo independently. This helps structure the search for consistent concepts T by decomposing the problem into Y independent subproblems [8, 80). More precisely, given time step E [0, 1), samples ca, ct go(c", e' y", x) and samples a0 cb po(60 c², x), we use:
Voly R oe
Σ (1(x())) = = - p4) V Lo (c) c d))x) 1=1
(7)
(S - 1)
where 14 = ΣE ((p())) = y. We provide further details in Section E.
Maximising the variational entropy LHtg is challenging: the variational distribution in Section 3.3 samples from a conditioned version of the unmasking model where computing likelihoods, and by extension, maximising the entropy of qo. highly untractable. We therefore experimented with two biased approximations of this loss which sufficed for our experiments, and leave more sophisticated approximations for future work:
conditional 1-step entropy: we have access to a tractable constraint circuit of yp, we can use to compute the entropy of an independent distribution over e conditioned on y and [7, 83). Then, we maximise the entropy over the variational distribution when performing time discretisation with a single step (T 1): ((" ccl =m,y", x)] using the distribution defined in Eq. 6.

---

unconditional 1-step entropy: Without access to a tractable constraint circuit, we instead maximise the unconditional 1-step entropy (( cc'
m.,)) x)].
Furthermore, as is common in variational setups [30], we add hyperparameters that weight the contribution of each loss component Le. Ly, and Ltgg] We found these hyperparameters critical to model (see Section H.2 for an ablation study). Finally, unbiased optimisation of Le and Ly also requires calculating the gradient through sampling c from the variational distribution [59, 70]. Like with the variational entropy, we found that sidestepping this part of the gradient, which would be intractable and have high variance otherwise, simplifies optimisation and yields good performance in practice. See pseudocode for the learning algorithm in Algorithm and additional discussion and definitions of the gradient estimation algorithm in Section E.
performance
Algorithm Algorithm for estimating the gradients of the NELBO for training NESYDM
I: Given datapoints (x. y") and unmasking model (T x, ct) with current parameters 0
2: c ~ (c
x.y²)
b Sample from variational distribution (Section 3.3).
3: ~ U(0,1)
Sample random time step.
4: ct ~ q(c' cO)
>> Mask the concept ea to c' (Eq. 9).
5: of Ci..... CS (c c²)
Sample S samples from unmasking model. b Estimate gradient of Ly using Eq. 60.
6: By < (cp (.))
7: ge I-a; LiEM,t
Vo Pologro(it = x, ct)
Compute gradient of Le D Compute gradient of Lu- Return the weighted of the gradients.
8: gu t VoLn1
9: return ge + 7
th gh
3.5 Sampling and Inference
Next, we describe how we sample from trained NESYDMS to make predictions of given x. Exactly computing the mode argmax,, P'g NESYDM x) is intractable even for representations supporting tractable marginals [2, 84], therefore we need to approximate it. We use majority voting strategy, where we sample L concepts of from the trained MDM, compute the output with the program p. and take the most frequent output:
y = argmax, Σ ((p(())) =y. cf....,ch pp(c x, x = =m). 1=1
(8)
the concept dimension is not too large, we use the first-hitting sampler from [94] to sample from (c c² m) exactly in C' steps. Otherwise, we use a T'step time-discretisation of the reverse process [68], for pseudocode see Algorithm 2. For implementation details, we refer to Section F. Additionally, experimented with different majority voting strategies, which discuss in Section H.I. These mainly study whether to do majority voting before or after running the program.
Algorithm 2 Standard time-discretised output prediction for NESYDM
1: Given datapoint x and unmasking model (e x, cf) with parameters for -- to L do
2:
3:
c² m
4:
for + T to do j ~ (C
5:
x, c²) c"~qle c Ed)
Sample from unmasking model (Section 3.3).
6:
Sample from remasking process (Eq. 10). b Store the sampled concept Compute program output for this sample
7:
of c
8:
y p(c])
9: + argmaxx El. 1 y]
> Majority vote Return the most frequent output
Return
4 Experiments
We aim to answer the following research questions: (RQ1:) "Can NESYDMs scale to high- dimensional reasoning problems?" and (RQ2:) "Does the expressiveness of NESYDMs improve
7

---

Table 1: Accuracy of predicting the correct sum on MNIST Addition with N and N 15 digits. Methods above the horizontal line are exact, and below are approximate. We bold the best-scoring methods in the exact and approxi- mate categories separately.
Table 2: NESYDM significantly scales beyond current NeSy predictors. Accuracy of predict- ing a shortest path on visual path planning with different grid sizes. Above the horizontal line are methods predicting continuous costs, while below are approximate NeSy methods that pre- dict discrete, binned costs.
MЕTHOD
N N= 1
N = 15
DEEPSOFTLOG [48]
93.5 0.6
77.1
+ 1.6
MЕTHOD
12
30 30
PLIA [21]
91.84=10
79.00 0.73
I-MLE [62]
97.2 = 0.5
93.7 + 0.6
SCALLOP [21, 43]
90.88= 0.48
T/O
EXAL [85]
94.19 1.74
80.85 3.83
EXAL [85]
91.65= 0.57
73.27 2.05
A-NESI [80]
9..57=2.27
17.13#
16.32
A-NESI [80]
92.56= 0.79
76.84 2.82
A-NESI+RL, [80]
98.96+ 1.33
67.57= 36.76
NESYDM (ours)
92.49= 0.98
77.29 1.40
NESYDM (ours)
99.41 0.06
97.40 1.23
reasoning shortcut awareness compared to independent models?" Since there are currently no scalable RS-aware NeSy methods, the baselines we use are separated for the two research questions. We match experimental setups of the basclines, using the same datasets and neural network architectures for fair comparison. To approximate the variational entropy (Section 3.4), we use the unconditional entropy for the experiments, as the conditional entropy is intractable. For the RSBench experiments, we tried both. We use the linear noising schedule a; = t for all experiments.
For all experiments, we repeat runs with 10 different random seeds. In all tables, we find the best-performing methods with bold font. In particular, bold all methods that are not statistically different from the highest-scoring method according to an unpaired one-sided Mann-Whitney U test significance level of 0.05. We provide additional experimental details in Section G. Code is available at https: //github com Hwweeeeeeeeeereeeneoeeeee http:///uurrrmombmooooodiiiiiiii diffusion.
4.1 RQ1: Scalability of NESYDM
To evaluate the scalability of NESYDM, we consider two NeSy benchmark tasks with high combi- natorial complexity: multidigit MNIST Addition and visual path planning. We compare to current approximate NeSy methods that use the independence assumption and are not RS-aware, namely A-NeSI [81], Scallop [43], and EXAL [85].
Multidigit MNIST Addition. The input x is a sequence of 2 numbers of N digits, and the output is the sum of the two numbers, split up into N digits. The goal is to train neural network that recogmises the individual digits с E {0, I,... 922N in the input from input-output examples. There are no dependencies between the digits and the problem is not affected by reasoning shortcuts, so we do not expect NESYDM to improve significantly over NeSy methods that use the independence assumption. Still, we find Table that NESYDM, which uses a much more expressive model than the baselines, performs similar to the state-of-the-art art approximate method A-NeSI, and is competitive with exact methods [19, 48]. Therefore, the expressivity does not come at a cost of performance and scalability in traditional NeSy benchmarks.
Visual path planning. We study the problem described in Example 2.1. Specifically, we train neural network to predict the correct cost Ci.j at each of the N x N grid cells. Then, we use Dijkstra's algorithm to find the shortest path y E (0, [0,1) NNN, where Vi.j = 1 if the shortest path passes through cell i.j and 0 otherwise. Like other NeSy methods, we predict costs with 5-dimensional categorical variable E (1,...,5] 5] xN We also compare to I-MLE, the state-of-the-arl method that predicts costs as single continuous variable [62]. We find in Table that NESYDM significantly outperforms all baselines on the challenging 30 x 30 problem, including I-MLE. This problem has a combinatorial space of 5000 and is considered very challenging for NeSy and neural models [65]. On the 12 12 problem, we cannot reject the null hypothesis that NESYDM outperforms A A-NeSI + RLOO, but it does have much lower variance, highlighting the reliability of our method.
4.2 RQ2: RS-awareness of NESYDM
To evaluate the RS awareness of NESYDM, we use the RSBench dataset [56] of reasoning problems that cannot be disambiguated from data alone. We consider two synthetic problems and a real-
8

---

Table 3: NESYDM is performant and RS-aware NeSy predictor as shown on several tasks from the RSBench dataset. We report relevant performance metrics for each task, and concept calibration using ECE to evaluate RS-awareness (see Section G.4.2 for motivation for this metric). We underline the accond-best-ccoinng method if there is only single statistically significant best-scoring method. The first two methods use the independence assumption. Note that SL does not support BDD-OIA.
METHOD
PNP
SL-
BEARS [55]
NESYDM (ours)
PNP
SL
UNCOND
COND H
BDD MNISTE-0 MNIST HALF
ACCy f
98. 28.244+000 0.12
99.62.t
0.12
99.19t 0.12
99.76:
0.00
99.1224
0.10
99. 0.10
ACCe f
42.76: 0.14
42.88 0.09
43.26
0.75
0.00 42.86.:
79.41 6.58
71. 1.77
ACCy,Ood
f
5.81 0.07
0.28+
6.31+ 1.10
0.11
10.9 0.05
28.44: 0.90
ACCe,ood f
38.97:t 0.08
3.192+0.11
1.07 39.49+
38.88+
0.03
57.22+
62.76:t 0.89
ECFF,.ID +
69.40+ 0.35
70.61+0.18
37.61+ 1.22 36.81+0.17
5.01 39.52++
4.18+ 2.56
ECEe,oOD 4
86.67:
0.19
2.18
35.99.1 2.88
35.07-4 2.67
11.74:: 1.18
ACCy t
70.77:
92.02+ 0.33
98.67 0.27
97.52:
98.27:1 0.44
ACCe I
0,40 0.04
0.33
0.48+ 0.10
0.19 0.08
0.36 0.27
20.33+ 1.33
ACCy,ood t
7.29 0.49
0.05
1.60 2.04
0.00 0.00
0.00 0.00
0.02 0.04
ACCe,oon f
7.50 0.32
0.09
9.36 2.13
6.25 1.46
4.65+ 0.49
14.25 0.76
ECE,, |
81,04 1.15
82.18 1.57
28.824 2.19
34.51 1.65
20.93+1 0.49
2.70 1.21
ECE,,OOD
85,44 0.72
86.96 1.15
26.83 1,56
32.61 3.32
19, 19.133 0.50
5.77 0.98
MFly f
63.71+ 1.50
60.80+ 0.11
61.67+ 0.32
62.63+ 0.53
MFL,
10.41 1.90
19.25# 0.16
18. 0.21
13.77 0.51
ECE,
38.89# 1.34
16.00:t 0.20
18.86 1.75
21.72 1.83
world task. MNIST Half and MNIST Even-Odd (MNIST E-O) are variations of MNIST Addition constructed to ensure disambiguation of concepts is impossible. They have OOD test-sets to diagnose overcontident classifiers. BDD-OIA (BDD) is self-driving task [87] where a model predicts what actions
take given dashcam image. NeSy predictors extract high-level concepts from the image and use rules to predict the allowed actions. We compare to NeSy predictors using the independence assumption, namely Semantic Loss (SL"), [86] and a standard probabilistic NeSy predictor "). We also compare to BEARS, an RS-aware ensemble of NeSy predictors with the independence assumption [55].
In Table 3, we find that NESYDM strikes good balance between accuracy and RS-awareness through- out the datasets. On the MNIST tasks, it attains significantly better concept accuracy than competitors, both and out-of-distribution. Furthermore, NESYDM, especially using the conditional entropy, has much better concept calibration than both baselines using the independence assumption and RS-aware baselines. We report additional results on these datasets in Section H.1 and find that different majority voting strategies may improve OOD performance. On BDD-OIA, we find that NESyDM has better predictive performance on outputs than BEARS while significantly improving calibration and concept performance compared to PNP using the independence assumption. Furthermore, we note that, unlike the baselines, NESYDM is much more scalable highlighted in Section 4.1.
5 Further related work
NeSy predictors. The field of NeSy predictors is primarily divided into methods using fuzzy logies [10, 17, 28, 78] and those using probabilistic logics [6, 43, 52, 80, 86]. Fuzzy methods implicitly assume a form of independence between concepts, while probabilistic methods can model dependencies. Previous methods that went beyond the independence assumption mixed multiple independent distributions, like in SPL [6] and BEARS [55] which is specifically designed for RS-awareness. Neurosymbolic probabilistic logic programming frameworks like DeepProbLog and Scallop [43, 52] allow modifying the program to increase expressivity compared to the naive independence over concepts. However, these methods are built on exact or top-k inference, which is difficult to scale to high- sigh-dimensional reasoning problems like visual path planning when the number of dependencies grows. Relatedly, DeepGraphLog [34] extends DeepProbLog by using graph neural networks to model dependencies between concepts, also relying on exact inference. Conversely, all current methods focussed on approximate inference to scale neurosymbolic predictors assume independence between concepts [73, 80, 85], hence lacking RS- RS-awareness.

---

NeSy generative models. A closely related topic is generating from expressive models like large language models (LLMs) and diffusion models while involving programs and constraints. For LLMs. this was studied with NeSy loss functions encoding the constraints [2, 3, 13] and with constrained decoding, for example using sequential Monte Carlo methods [42, 46, 93] and by combining the LLM with approximations using probabilistic circuits [5, 91, 92]. However, these methods adopt heuristics to steer the LLM towards a constraint, for instance, by using a pseudo-likelihod formulation [2, 3] or training HMM surrogate that approximates the LLM [91, 92]. Instead, for NESYDM formulate a principled NELBO, and we do so by exploiting the local structure that diffusion models offer. Furthermore, some methods tackle constrained generation from GANs [24, 75, 76], VAEs [58], deep HMMs [74], and continuous diffusion models [31, 69]. We leave extensions of NESYDM to this generative setting to future work.
6 Conclusion
In this paper, we introduced NESYDMs, the first method to integrate masked diffusion models as the neural network extractor in neurosymbolic predictors. We show how to scale NESYDMS by using efficient probabilistic reasoning techniques on local unmasking distributions while minimising a global NELBO that lower-bounds the data log-likelihood. Empirically, we show that NESYDMS position themselves as one of the best NeSy predictors available that can scale to high-dimensional reasoning problems while being RS-aware This is crucial property for NeSy predictors deployed in real-world safety-critical applications, as they need to be well calibrated and generalise robustly.
Limitations and future work. The NESYDM NELBO can be extended to incorporate additional exact inference routines if we can obtain an efficient circuit, e.g., as the tractable representation for a symbolic program [63]. Otherwise, as argued in Section 3.4, our sampling- bbaed approach relies on the ability to decompose the output y into separate dimensions to ensure the search RLOO decomposed into independent subproblems. Together, this limits the scalability of NESYDM to tasks with either efficient circuit representations or decomposable output spaces. Understanding how to combine these two aspects, or how to automatically (and approximately) reduce different setting into one of them, is an interesting and challenging future venue. Two other areas of improvement are our approach to maximising the variational entropy and the influence of the indirect gradient coming from sampling from the variational distribution. Finally, we believe studying how NESYDMs extend to other discrete diffusion models than masked diffusion [9] models is an interesting direction. NESYDM could even be extended to hybrid diffusion models that involve both symbolic, discrete concepts and continuous latent variables by using recent work on generating under continuous constraints [20, 40, 76).
Acknowledgements
Emile van Krieken was funded by ELIAI (The Edinburgh Laboratory for Integrated Artificial Intelligence), EPSRC (grant no. EP/W002876/1). Pasquale Minervini was partially funded by ELIAI, EPSRC (grant no. EP/W002876/1) )), industry grant from Cisco. and a donation from Accenture LLP. Edoardo M. Ponti is supported by the ERC Starting Grant AToM-FM (101222956). Antonio Vergari supported by the "UNREAL: Unified Reasoning Layer for Trustworthy ML" project (EP/Y023838/1) selected by the ERC and funded by UKRI EPSRC. We would like to express our gratitude to Samuele Bortolotti, Emanuele Marconato, Lennert de Smet, Adrián Javaloy, and Jaron Maene for fruitful discussions during the writing of this paper.
References
[1] Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzieh Fadace, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, and Sara Hooker. Back to basics: Revisiting reinforce style optimization for learning from human feedback in lls. CoRR, abs/2402. 14740, 2024.
[2] Kareem Ahmed, Catarina G Belem, Padhraic Smyth, and Sameer Singh. Semantic probabilistic control of language models. arXiv preprint arXiv:2505.0195. 2025.
[3] Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. A pseudo-semantic loss for autore- gressive models with logical constraints. In Thirty-Sevente Conference on Neural Information Processing Systems, 2023.
10

---

[4] Kareem Ahmed, Kai- Wei Chang, and Guy Van den Broeck. Semantic strengthening of neuro- symbolic learning. In International Conference on Artificial Intelligence and Statisties, pages 10252-10261. PMLR, 2023.
[5] Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. Controllable generation via locally constrained resampling. In Neurips Safe Generative Al Workshop 2024, 2024.
[6] Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning. 35:29944-29955 2022.
[7] Kareem Ahmed, Eric Wang, Kai-Wei Chang, and Guy van den Broeck. Neuro-Symbole Entropy Regularization. 2022.
[8] Yaniv Aspis, Krysia Broda, Jorge Lobo, and Alessandra Russo. EmbedZsym--scalable neuro- symbolic reasoning via clustered embeddings. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 19, pages 421-431, 2022.
[9] Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured Denoising Diffusion Models in Discrete State-Spaces, 2023.
[10] Samy Badreddine, Artur d' Avila Garcez, Luciano Serafini, and Michael Spranger. Logic Tensor Networks. Artificial Intelligence, 303: February 2022.
[1I] Samuele Bortolotti, Emanuele Marconato, Tommaso Carraro, Paolo Morettin, Emile van Kricken, Antonio Vergari, Stefano Teso, and Andrea Passerini. A neuro-symbolic benchmark suite for concept quality and reasoning shortcuts. In The Tiihty- Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024.
[12] Nicola Branchini and Víctor Elvira. Generalizing self-normalized importance sampling with couplings, 2024.
[13] Diego Calanzone, Stefano Teso, and Antonio Vergari. Logically consistent language models via neuro-symbolic integration. In The Thirteenth International Conference Learning Representations, 2025.
[14] Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. Advances in Neural Information Processing Systems, 35:28266-28279 2022.
[15] Weixin Chen, Simon Yu, Huajie Shao, Lui Sha, and Han Zhao. Neural probabilistic circuits: Enabling compositional and interpretable predictions through logical reasoning. arXiv preprint arXiv:2501.0002 2025.
[16] Y Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. UCLA. URL: htlp://starai. cs. ucla edulpupers/ProbCir220. pdf, page 6, 2020.
[17] Alessandro Daniele, Emile van Krieken, Luciano Serafini, and Frank van Harmelen. Refining neural network predictions using background knowledge. Machine Learning, 112(9)33933-3311 2023.
[18] Adnan Darwiche and Pierre Marquis. Knowledge compilation: Preface. Annals of Mathematics and Artificial Intelligence, 1205)11007-1 2024.
[19] Lennert De Smet and Pedro Zuidberg Dos Martires. A fast convoluted story: Scaling proba- bilistic inference for integer arithmetics. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[20] Lennert De Smet, Pedro Zuidberg Dos Martires, Robin Manhaeve, Giuseppe Marra, Angelika Kimmig, and Lue De Readt. Neural probabilistic logic programming in cisstrtte-omtiiuuuss domains. In Uncertainty in Artificial Intelligence, pages 529-538. PMLR, 2023.
[21] Lennert De Smet and Pedro Zuidberg Dos Martires. A fast convoluted story: Scaling proba- bilistic inference for integer arithmetics. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 102456-102478. Curran Associates, Inc., 2024.
[22] Lauren Nicole DeLong, Yojana Gadiya, Paola Galdi, Jacques D Fleuriot, and Daniel Domingo- Fernández. Mars: neurosymbolic approach for interpretable drug discovery. arXiv preprint arXiv:2410.05289, 2024.

---

[23] Jacob Devlin, Ming- wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguisties: human language technologies, volume (long and short papers), pages 4171-4186, 2019.
[24] Luca Di Liello, Pierfrancesco Ardino, Jacopo Gobbi, Paolo Morettin, Stefano Teso, and Andrea Passerini. Efficient Generation of Structured Objects with Constrained Adversarial Networks, 2020.
[25] Jonathan Feldstein, Paulius Dilkas, Vaishak Belle, and Efthymia Tsamoura. Mapping the neuro- symbolic ai landscape by architectures: A handbook on augmenting deep learning through symbolic reasoning. arXiv preprint (rXiv:2410.22077. 2024.
[26] Artur d' Avila Garcez and Luis C Lamb. Neurosymbolic ai: The 3 rd wave. Artificial Intelligence Review, 56(1 13:17737-1 2023.
[27] Elconora Giunchiglia, Mihaela Cätälina Stoian, Salman Khan, Fabio Cuzzolin, and Thomas Lukasiewicz. Road-r: the autonomous driving dataset with logical requirements. Machine Learning, 112(9))3261-329) 2023.
[28] Eleonora Giunchiglia, Alex Tatomir, Mihaela Cătälina Stoian, and Thomas Lukasiewicz. Cen+:
A neuro-symbolic framework for deep learning with requirements. International Journal of 124, 2024.
Approximate Reasoning,
[29] Wei Guo, Yuchen Zhu, Molei Tao, and Yongxin Chen. Plug-an and--add-ppa play controllable generation for discrete masked models, 2024.
[30] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. In International conference on learning representations, 2017.
[31] Yujia Huang, Adishree Ghatare, Yuanzhe Liu, Ziniu Hu, Qinsheng Zhang, Chandramouli S Sastry, Siddharth Gururani, Sageev Oore, and Yisong Yue. Symbolic music generation with non-differentiable rule guided diffusion. In Proceedings of the 41st International Conference on Machine Learning, pages 19772-19797, 2024.
[32] Adrian Javaloy, Maryam Meghdadi, and Isabel Valera. Mitigating modality collapse in multi- modal VAES via impartial optimization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 9938-9964. PMLR, 17-23 Jul 2022.
[33] Richard M Karp. Michael Luby, and Neal Madras. Monte-carlo approximation algorithms for enumeration problems. Journal of algorithmss, 10(3):429 448, 1989.
[34] Adem Kikaj. Giuseppe Marra, Floris Geerts, Robin Manhaeve, and Luc De Raedt. Deepgraphlog for layered neurosymbolic ai. arXiv preprint arXiv:2509.0766 2025.
[35] Diederik P. Kingma and Jimmy Ba.
Adam: Method for Stochastic Optimization.
arXiv: 14126690 [cs], January 2017.
[36] Diederik P. Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational Diffusion Models. 2021.
[37] Doga Kisa, Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. Probabilistic sentential decision diagrams. In KR, 2014.
[38] Wouter Kool, Herke van Hoof, and Max Welling. Buy 4 REINFORCE samples, get a baseline for free!, 2019.
[39] Emile van Krieken, Pasquale Minervini, Edoardo Ponti, and Antonio Vergari. Neurosym- bolic reasoning shortcuts under the independence assumption. In Leilani H. Gilpin, Eleonora Giunchiglia, Pascal Hitzler, and Emile van Krieken, editors, Proceedings of The 19th Interna- tional Conference on Neurosymbolic Learning and Reasoning, volume 284 of Proceedings of Machine Learning Research, pages 285-302. PMLR, 08-10 Sep 2025.
[40] Leander Kurscheidt, Paolo Morettin, Roberto Sebastiani, Andrea Passerini, and Antonio Vergari. probabilistic neuro-symbolic layer for algebraic constraint satisfaction. arXiv preprint arXiv:2503.19466 2025.
12

---

[41] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227-2333 1998.
[42] Alexander K Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash Mansinghka. Sequential monte carlo steering of large language models using probabilistic programs. In ICML 2023 Workshop: Sampling and Optimization in Discrete Space, 2023.
[43] Ziyang Li, Jiani Huang, and Mayur Naik. Scallop: A language for neurosymbolic programming. Proceedings of the ACM on Programming Languages, 7(PIDD): 1463-1487, 2023.
[44] Anji Liu, Oliver Broadrick, Mathias Niepert, and Guy Van den Broeck. Discrete copula diffusion. arXiv preprint arXiv:2410.01990 2024.
[45] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. International Conference Learning Representations, 2020.
[46] João Loula, Benjamin LeBrun, Li Du, Ben Lipkin, Clemente Pasti, Gabriel Grand, Tianyu Liu, Yahya Emara, Marjorie Freedman, Jason Eisner, Ryan Cotterell, Vikash Mansinghka, Alexander K. Lew, Tim Vieira, and Timothy J. O' O'Donnell. Syntactic and semantic control of large language models via sequential monte carlo. In The Thirteenth International Conference on Learning Representations, 2025.
[47] Calvin Luo. Understanding diffusion models: A unified perspective. arXiv preprint arXiv:2208. I 1970, 2022.
[48] Jaron Maene and Lue De Raedt. Soft-unification in deep probabilistic logic. Advances in Neural Information Processing Systems, 36:60804-60520, 2023.
[49] Jaron Maene, Vincent Derkinderen, and Luc De Raedt. On the hardness of probabilistic neurosymbolic learning. In Forty-first International Conference on Machine Learning, 2024.
[50] Jaron Maene, Vincent Derkinderen, and Pedro Zuidberg Dos Martires. Klay: Accelerating arithmetic circuits for neurosymbolic ai. In The Thirteenth International Conference on Learning Representations, 2025.
[51] Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. DeepProbLog: Neural probabilistic logic programminng In Samy Bengio, Hanna M Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, edi- tors, Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, 2018.
[52] Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Neural probabilistic logic programming in DeepProbLog. Artificial Intelligence, 298:103504, 2021.
[53] Emanuele Marconato, Gianpaolo Bontempo, Elisa Ficarra, Simone Calderara, Andrea Passerini, and Stefano Teso Neuro-symbolit continual learning: Knowledge, reasoning shortcuts and concept rehearsal. arXiv preprint arXiv:2302.0124/ 2023.
[54] Emanuele Marconato, Samuele Bortolotti, Emile van Krieken, Paolo Morettin, Elena Umili, Antonio Vergari. Efthymia Tsamoura, Andrea Passerini, and Stefano Teso. Symbol grounding in neuro-symbolic ai: A gentle introduction to reasoning shortcuts, 2025.
[55] Emanuele Marconato, Samuele Bortolotti, Emile van Krieken, Antonio Vergari, Andrea Passerini, and Stefano Teso. BEARS Make Neuro-Symbolic Models Aware of their Reasoning Shortcuts. In Uncertainty Artificial Intelligenc, February 2024.
[56] Emanuele Marconato, Stefano Teso, Antonio Vergari, and Andrea Passerini. Not All Neuro- Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts. In Thirty-Seventh Conference on Neural Information P Processing Systems, May 2023.
[57] Giuseppe Marra, Sebastijan Dumančić, Robin Manhaeve, and Luc De Raedt. From statistical relational to neurosymbolic artificial intelligence: A survey. Artificial Intelligence, 328: 104062, 2024.
[58] Eleonora Misino, Giuseppe Marra, and Emanuele Sansone. Vael: Bridging variational au- toencoders and probabilistic logic programming. Advances in Neural Information Processing Systems, 35:4667-4677, 2022.
13

---

[59] Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient estimation in machine learning. Journal of Machine Learning Research, 21:132: 2020.
[60] Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated probabilities using bayesian binning. In Proceedings of the AAAI conference on artificial intelligence, volume 29, 2015.
[61] Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, JUN ZHOU, Yankai Lin, Ji-Rong Wen, and Chongxuan Li. Large language diffusion models. In ICLR 2025 Workshop on Deep Generative Model in Machine Learning: Theory, Principle and Efficacy, 2025.
[62] Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit mle: backpropagating through discrete exponential family distributions. Advances in Neural Information Processing Systems, 34:14567-14559, 2021.
[63] Umut Oztok and Adnan Darwiche. A top-down compiler for sentential decision diagrams. In IJCAI, volume 15, pages 3141-3148, 2015.
[64] Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.
[65] Marin Vlastelica Pogančié, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2020.
[66] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. Advances in neural information processing systems, 28, 2015.
[67] Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learning, 62:107- 136, 2006.
[68] Subham Sekhar Sahoo, NYC Cornell Tech, Mariaann Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin T Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. 2024.
[69] Davide Scassola, Sebastiano Saccani, Ginevra Carbone, and Luca Bortolussi. Conditioning score-based generative models by neuro-symbolic constraints. arXiv e-prints, pages arXiv-2308, 2023.
[70] John Schulman, Nicolas Heess, Theophane Weber, and Pieter Abbeel. Gradient estimation using stochastic computation graphs. Advances in neural information processing systems, 28, 2015.
[71] Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint 3030:22402.03300. 2024.
[72] Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis Titsias Simplified and generalized masked diffusion for discrete data. arXiv preprint arXiv:2406.044:: 2024.
[73] Lennert De Smet, Emanuele Sansone, and Pedro Zuidberg Dos Martires. Differentiable sampling of categorical distributions using the catlog-derive derivative trick. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[74] Lennert De Smet, Gabriele Venturato, Luc De Raedt, and Giuseppe Marra. Relational neurosym- bolic markov models. In Toby Walsh, Julie Shah, and Zico Kolter, editors, AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 -Mrchh 2025, Philadelphia, PA, USA, pages 16181-16189, AAAI Press, 2025.
[75] Mihaela C Stoian, Salijona Dyrmishi, Maxime Cordy, Thomas Lukasiewicz, and Eleonora Giunchiglia. How realistic is your synthetic data? constraining deep generative models for tabular data. In The Twelfth International Conference on Learning Representations, 2024.
[76] Mihaela C Stoian and Eleonora Giunchiglia. Beyond the convexity assumption: Realistic tabular data generation under quantifier-free real linear constraints. The Thirteenth International Conference Learning Representations, 2025.
14

---

[77] Frank Van Harmelen and Annette Ten Teije. A boxology of design patterns for hybrid learning and reasoning systems. Journal of Web Engineering. 18(1-3):97-123, 2019.
[78] Emile van Krieken, Erman Acar, and Frank van Harmelen. Analyzing differentiable fuzzy logic operators. Artificial Intelligence, 102:003 2022.
[79] Emile van Krieken, Pasquale Minervini, Edoardo M Ponti, and Antonio Vergari. On the independence assumption in neurosymbolic learning. In Proceedings of the 41st International Conference on Machine Learning, pages 49078-49097, 2024.
[80] 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:24586-24609, 2023.
[81] Emile van Krieken, Thiviyan Thanapalasingam, Jakub Tomezak, Frank Harmelen, and Annette Ten Teije. A-NeSI: A scalable approximate method for probabilistic neurosymbolic inference. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 24586-24609. Curran Associates, Inc., 2023.
[82] Emile van Krieken, Jakub Tomezak, and Annette Ten Teije. Storchastic: A framework for general stochastic automatic differentiation. Advances in Neural Information Processing Systems, 34:7574-7587, 2021.
[83] Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A com- positional atlas of tractable circuit operations for probabilistic inference. Advances in Neural 2021.
Information Processing Systems,
[84] Antonio Vergari, Nicola Di Mauro, and Guy Van den Broeck. Tractable probabilistic models: Representations, algorithms, learning. and applications, 2019. In Tutorial at the 35th Conference on Uncertainty in Artificial Intelligence (UAl 2019).
[85] Victor Verreet, Lennert De Smet, Luc De Raedt, and Emanuele Sansone. Explain, agree, learn: Scaling learning for neural probabilistic logic. arXiv e-prints, pages arXiv-2408, 2024.
[86] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy den Broeck. A semantic loss function for deep learning with symbolic knowledge. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 5502-5511, 1, Stockholmsmässan, Stockholm Sweden, 2018. PMLR.
[87] Yiran Xu, Xiaoyin Yang. Lihang Gong, Hsuan-Chu Lin, Tz-Ying Wu, Yunsheng Li, and Nuno Vasconcelos. Explainable object-induced action decision for autonomous vehicles. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9023,,532,420 2020.
[88] Jiacheng Ye, Jiahui Gao, Shansan Gong, Lin Zheng, Xin Jiang, Zhenguo Li, and Lingpeng Kong. Beyond autoregression: Discrete diffusion for complex reasoning and planning. The Thirteenth International Conference on Learning Representations, 2025.
[89] Jiacheng Ye, Zhihui Xie, Lin Zheng, Jiahui Gao, Zirui Wu, Xin Jiang, Zhenguo Li, and I Lingpeng Kong. Dream 7b, 2025,
[90] Runpeng Yu, Qi Li, and Xinchao Wang. Discrete diffusion in large language and multimodal models: A survey, 2025.
[91] Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for autoregressive language generation. In International Conference on Machine Learning, pages 40932-40945 PMLR, 2023.
[92] Honghua Zhang, Po-Nien Kung, Masahiro Yoshida, Guy Van den Broeck, and Nanyun Peng. Adaptable logical control for large language models. Advances in Neural Information Processing Systems, 37:1 15563-1 15587, 2024.
[93] Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Baker Grosse. Probabilistic inference in language models via twisted sequential monte carlo. In International Conference on Machine Learning, pages
PMLR, 2024.
[94] Kaiwen Zheng, Yongxin Chen, Hanzi Mao, Ming-Yu Yu Liu, Jun Zhu, and Qinsheng Zhang Masked diffusion models are secretly time-agnostic masked models and exploit inaccurate categorical sampling. arXiv preprint arXiv:2409.02900 2024.
15

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine 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 have a limitations section in the conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect 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 be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 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, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best 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 set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification:
All theoretical results are marked, and assumptions stated alongside them.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs 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 the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix 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: We provide all experimental details in Section G, and additionally provide code in the supplementary materials. We also give pseudocode for all implemented algorithms.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, 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 to 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 to either make possible for others to 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 are 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) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be 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 deseribe 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., registered users), but it should be possible for other researchers to have some path to reproducing or 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?
17

---

Answer:
[Yes]
Justification:
All data used is open access. We provide links to the code in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (attps://nips.cm cc/ public/guides htte///ooeumiissonnniioo.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
//niss.. wwtpcc/ppplcccccccccccc wwtpc///ggge/eeeeeeeeeeeeeeeeeee Caaeae//dodSSubbmeice wwssssssossliiioeoo cnoonolicy)) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
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/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All these details are provided in the supplementary material (Section G).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report standard deviations, and used Mann- WhinnWy U-tests to compute vavuuues for comparing whether the top- uo-performing methods are statistically different from other methods.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by eπror bars, confi- dence intervals, or statistical significance tests, at 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).
18

---

It 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 range (e.g. negative еπхо 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 the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We discuss compute used in Section G.
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, 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 it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: :ttp:://nneuee http///eeurruuu.ceee htt.:/pp....p.bcccc/ccccccceeedd
Answer: [Yes]
Justification:
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 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).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper tackles general improvements of NeSy predictors and improving their reliability. This could be downstream societal impact, in particular more reliable models. However, there are no direct impacts downstream from our research.
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 societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied to particular 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 to 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses 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 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. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.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]
Justification: We cite all datasets used, and add licenses to datasets wherever applicable.
Guidelines:
The answer NA means that the paper does not 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.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: There are no assets related to this paper. However, we include code the supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to 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
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 details about compensation (if any)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in 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 NeurlPS 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) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be 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, not include any information that would break anonymity (if applicable), such the institution conducting the review.
21

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLMs were used in this research except for writing, editing, and formatting.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: btttps://neuuee for what should or should not be described.
22

---

A Additional background on masked diffusion models
Here, we will discuss additional background and formalisation of masked diffusion models (MDMs). This background is used derive the NELBO of the masked diffusion model in Section D.2 and the loss with arbitrary joints in Section C.
Forward process details. We first define the continuous-time forward process g(c" c.), which masks the data up to timestep t E [0, 1] using the forward process defined in Eq.
C
ac cc))
= II ar 14
cf] +
an) (1--x)) = m]
i=1
Secondly, we need the reverse posterior q(c² , which the distribution of the initial state cº given the state at timestep and the final state. Here we assume of is either equal to the mask value m or to the value of cg, as otherwise the probability is not well-defined. The form for each case (see [68], 1.2.I)
C
q(c cc) = II
q( c9,c))
(10)
i=1
d( c = d. d) = 1 = cd
(11)
q(c) c = m, 4 =
as il 1c = m| + 0, at 10 =
(12)
at
04
We note that g(c) c = cf.c c?) refers to the probability of of conditioned on some value for the variable of and where the value of variable of equals this value. e indeed is equal to the value of e, the distribution deterministically returns that value. If it is masked instead, it either stays masked or turns into the value of cf with a probability depending on az.
Additional notation. We let Mc. = {i ci = m} refer to the dimensions that are masked in cf. Similarly, Uet {i of A m} is the set of unmasked dimensions of c². Furthermore, we will use c* 2 c' to denote that c² is a (partial) extension of c'. This means c* agrees on all unmasked dimensions of c¹ with c', that is, w 3 for all i Up.. We will also use c" yc e' to denote that c" is a complete extension that does not have any masked dimensions. Finally, we use notation such as ef,, to index e* using the set of indices Uet, the unmasked dimensions of c².
Reverse process definition. Using (c c') (Eq. 3), we can express the intractable generative model pg MDM (c")), for time discretisation T,
T II (k(c c((()))
(C Po
MDM
Σ C1203
(13)
where the sum over (())) iterates over all trajectories c!..... T from fully masked c¹ = mm to unmasked c², and skk) k- 7 and t(a)) f index the timesteps.
Several recent papers [68, 72] proved that this model has simple negative variational lower bound (NELBO) under a continuous-time process, that is, when T + co. Given a dataset of samples co, this NELBO resembles weighted cross-entropy loss:
- -log
MDM MCDM) <
MDM co=
log = ol @100)
(14)
iEM,
Here af = Bog g(c co) is computed with Eq. 9, and the cross-entropy term computes the loss on at
the factors of the unmasking model (2@ cf). When using the common linear noising schedule,
af then ar - L, T-at -1. This bound holds when the unmasking model po cf) assigns probability to the mask value (zero masking probabilities), and assigns probability of to unmasked dimensions (carry-over unmasking). i.c., for all i Met, pe (c) = of c+) 1 [68].
23

---

B Analysis of the output unmasking loss
Here, will discuss the output unmasking loss Ly in more detail, and relate it other common loss functions in the NeSy literature. In our problem setup, assume program ip [V]c - [V] that maps concepts c to outputs y". Then, we defined the WMC in Eq. as the probability that some maps to y This constraint can be understood
1kp(c)) - (())))
(15)
That is, we can see this setup actually having Y different programs, and we want each program to return the right output. Now, disregarding the weighting and sampling, Ly is
Cy
=
log Σ 6
po(e") c' xx)x))(p((e)): = =
(16)
log pe (1/ Vi 0 c' x))
(17)
This loss is a sum of Y different WMC terms, one for each of the Y different programs. Ly assumes, in vacuum, that these programs independent, meaning we can sum the losses for each program independently. How could that be possible?
This is actually common property of continuous-time losses of discrete diffusion models. For instance, one can observe the same in the NELBO of MDMs in Eq. 14. There, the goal to reconstruct the (masked) dimensions of c independently. In fact, to perfectly fit an MDM, the goal is merely to perfectly fit each of the C' different conditional data marginals p(č)) c²) perfectly, without regard for any dependencies between dimensions [44]. The dependencies for the full MDM handled by the iterative unmasking process, which changes the condition at each step. The same property holds for Ly: the dependencies between the different programs are (ideally) handled by different conditions c" each step.
We highlight that this loss is related to existing loss functions in the NeSy literature. In particular, for programs that implement conjunctive normal forms (CNFs), this loss is equivalent to the logarithm of the product t-norm, which a common loss function in the NeSy literature [10, 78]. More precisely, if 10 models the C' variables of the CNF and y E 10, the Y clauses consisting of disjunctions of literals 4 V ... 4.K., then p(c), = V 4g computes the truth value of the ith clause of the CNF. Under the independence assumption, the probability that disjunction holds (that is, whether c(c), = 1) is
R
(o = 1 x) = I Po(li |x))
(18)
which is equal to the product t-conorm of the probabilities of the literals. Finally, the logarithm product t-norm takes the logarithm over the product of these probabilities, implicitly assuming these clauses are independent:
LLog-product. = Σ
log 1x).
(19)
Note that, outside the reweighting with af, this is precisely what by would compute for this problem (Eq. 17).
This equality between Ly and CLog product holds only for CNFs: for general programs, the product t-norm is not equal the probability on the output of program, unlike the disjunction case. For example, the different subprograms used in our experiments are not expressed as CNFs. Furthermore, our setup gives more flexibility even in the CNF case by allowing us to redefine what the dimensions of y represent. For instance, we can remove the independence assumption between set of clauses by defining y as the conjunction of these clauses. In that sense, it is highly related to Semantic Strengthening [4], which starts from CLog-product and then dynamically joins clauses by building probabilistic circuit to relax the independence assumption. This idea can be directly applied to our setup, which we leave as future work.
24

---

C Masked Diffusion with Arbitrary Joint Distributions
In this section, we will prove Theorem C.I which states that the NELBO in Eq. 14 also holds for non-factorised unmasking models po(c" c²). We use the notation introduced in Section A and Section 2.2. During this proof, we will derive both discrete- and continuous-time versions of the NELBO. In this appendix, we will use Cso to refer c/ ..... c' & and Any. This result is related to the tractability result of [14], namely that in continuous-time process, the probability that two dimensions are unmasked at exactly the same time step in (0, 1] 0.
Theorem C.1. Let (e c²) be any conditional joint distribution over 2 with conditional marginals Po c²) that satisfy the following assumptions for all {I....,C}.
1. Zero masking probabilities: pe(č; = m c²)
2. Carry-over unmasking: Given some c' E (Ve + 1) pola = l (d)== =
3. Proper prior: po(c') = 1 = m).
Let pe(c* c²) be the reverse process defined in Eq. using pe (τ ct) instead of a fully factorised model. Then as 'I' + oc,
log Togpe(c) = = ot) ct)
0l
- -log
MDM (co) - MDM [o.
MDM((C)
Σ
(20)
1 at
ieM
Proof. We start with a standard variational diffusion models derivation that closely follows those presented in [36, 47].
[log po (C) (C,o o co)
log Po (C log
Σ po (C S
C
Now we reduce the nominator with Bayes theorem and by conditioning on ca, which is conditionally independent given cx:
T
(C c²) = q(c
|c)
II q(c' c²) = q(c 1 |c9
II
q('
g(ch ce
A=
k=2
(21)
T
g(c c', c',c')))oe c9)g(( cc))
=T(ct/T
II
q(c ce))
a[ c',c9),
g(c0 (c))
co)
k=
where in the last step we use that the q(c' c and g(c" cc) cancel out in the product over leaving only q(c² | co). Filling in Eq. 3,
log Po(c") p(("))
II Po(c" ct)
(22)
q(c! c0))
Ih q(c* c co)
p(c")
log I Po (c ct)
colo))))
log po |!!/T) + log
(23)
g(c! c0)
I a(** ct co)
log c2/T)
) KL|g(c* o (poo( co)]+G +G
(24)
Laun, unmasking loss at timestep
To reconstruction loss
where G = (g((o (o log (e0 is constant and equal to 0 if p(c!) = 1[c² m).
p(ct)
Lemma C.2. Using the assumptions of Theorem C.I, I, for any integer 1,
L.e.T Extol/T log lo c² 1
(25)
25

---

Proof. First note that, using Eq. 12.
q( 1 q
1/T = m, 2
1 --00 000
1 = m|
ag 01/T
1 12 = -
1 1 1-T
21/T
1-1 0 11/TTT
1 01/7 1c G.] = c =
-
01/T
1 01/T
since no elements of λ are masked and og = by definition, and so combined with Eq. 11, we get 1/T
q(c G ( _ c. Therefore,
1e log (c | (((e
log Σ cc
Epo(E
II
1/r 29)
do
i=1
log Epo(t |c 1/T II
I = = +1
Go
1=1
E Bg(et/T(e")
log (c = c cc
Where we use that the only nonzero term the sum when e c..
Next, we focus on T'm & in Eq. 24. The standard derivation of the MDM NELBO in [68] computes the dimension-wisg KL-divergence between the forward and reverse process, and then sums. This is not possible in our setting because we assume arbitrary joints for the unmasking model, and so the KL-divergence does not decompose trivially.
Lemma C.3. Using the assumptions of Theorem C.I, any integer T and & (2...., T).
funm, = ( (L ct, clroo")) |c)]
(26)
= (eg(e",00000) - log po Vor
po = 0 Coo c')
Proof. We first consider what terms the KL-divergence in Lumm, are nonzero. First, note that et needs extend c (i.e., c c²) otherwise qcc c² c²) 0 by Eq. 11. Next, the unmasked dimensions in c need to be consistent with c" by Eq. 12, in other words, c > ca. Then, the Me
dimensions that stay unmasked get factor of 1-a, while the |Mae MM dimensions that become unmasked get factor of du-01,
T-o,-
Assuming e - c¹. we have
I-a,
1-a,
|Mall
(a,-a)) 1-ar
|Mrrl-MMa
if > c c
q(c² c', cc,co)- =
1-ar
(27)
otherwise.
Filling this into the KL of Lunm.T.No.
Eygcotley KL[g(c" c', (etco))lo c() q(c" c c²) g(c" c², c²) log Ee (o c')q((c ct 20)
-Eg(
Σ
(28)
eizezcc'
Now because of the carry-over unmasking assumption, we know that the only 2hts getting positive probabilities are those that extend c². Focusing just the log-ratio above and using Eq. 27 and Eq. 12 we have
|Mai|
|M |MMe
1-a,
a. aa 1-ax
1-07
log
Mai
[M MMgel-lMer Maa
Σ Exrror po(60 cf)
1-a, I-ax
ILEV 1[2 c!)
1-ar
= log
Σ Po c²)
II
--log Σ
(e c()),
oo
ieUe Vaa
600
26

---

since the ratio's 's involving de and are independent of e and can be moved out of the sum, dividing away. Then note that Te We 1 cg also requires that enl extends c².
Giving the denoising loss:
Cunm, T,k (0(
Σ
q(c" I',,''''' log Σ po(c") (')
(29)
60
Ee(ces,ttoc - log
Pa(c") c') = Byleer log log (Ct = ct.. |dt)
(30)
60
=Byles,
log po (C0.-
of Corr = -Woo 1c')
(31)
Eoler log po (CU. cba. cc)po((Cte = VerVWae |c')
(32)
,e1(e)) - log po (.. CU Vea = V. lc"),
(33)
where we use the carry-over unmasking assumption twice. In Eq. 33, we use that pe ( = c²) because p ci c')
U
for all i E Ue', and so the joint over the variables C must also be deterministic and return c Similarly, in Eq. 32, we use that oi is conditionally independent of c M given c' since the support of c) has only one element.
Combining Eq. 24 and Lemmas C.2 and C.3, we get the discrete-ting time loss:
C CMDM
al (oo) l- pop = c |
(34)
(c) Byler log log pa \ige = -u. |c)]
po(c) = co \ug c²) the marginal probability of the newly unmasked dimensions in c*: Ue \. Ue.. Therefore, computing the discrete-time loss requires being able to be compute conditional marginal distributions over multiple variables. Of course, this tractable for fully factorised distributions, in which case it's just product of individual marginals [68]. This loss can be estimated by sampling pairs c and c², and can be further simplified depending on the form of pa-
Next, we consider Lr as T + co. We will show that this allows us to marginalise out c*, reducing the variance. We will do this by considering the two loss terms individually, and letting T -> 30.
Lemma C.4. Using the assumptions of Theorem C.I,
lim T-000
LiST = 0
(35)
Proof. Recall that in discrete time this is equal to (see Lemma C.2)
LreeT = E
gic fictleet loo) log = c. |
(36)
Note that q(c.//T = m ( = 01/T. Then, limr 01/T lim 1 by continuity and monotonicity of ac, giving limy +0o q(c 1/T = m cf) = 0. Therefore, asymptotically, for all c c//T * c², we are left with a term that tends to 0 and a constant term independent of T, meaning the only relevant element of the sum c//T = co:
lim
Σ
|c0) 2/2
Σ CC C/T)- = lim
log Σ po ce))
(37)
T-000
T-000 60
e//T
= = log Σ C cCo) = log 1 0
(38)
20
where we the carry-over unmasking assumption to get the last equality.
n
Lemma C.5. Using the assumptions of Theorem C.I,
of
Lum. = Ex-(0_11g(ette))
Σ
log (e =
| c()]
(39)
iEM
27

---

Proof. Instead of having sum over T timesteps, each computing KL, we will now sample some & ~ {...... 1), redefining s 7. Then, we will weight the result by T Using Lemma C.3,
lim Lunm,T T-+xc
= lim ( Bo(et) - 1)KL[g(c" (e,'o) c')] 7-+00
(40)
Σ
lim (T- - 1)g(c") co) logro wa = V War |c)]]
T-000
(41)
|
Assuming that c ž c* 2 c', recall a(c" c',c")- = 1-ax
and assume
T-
least one dimension becomes unmasked: |Ma' M we get
O. Then, using that limy-+co 1-ac
Meel
MM Marl-1Mer
lim (T - -1)((c cc) T-200
lim T
1 - ag
[a -
(42)
T-x
1 0ct
1 Ot.
T(a. - -0t) = lim T
(xs Oz
|M
Morl-1
(43)
1 a₁
1
Next, using that 0; is differentiable, consider the first-order Taylor expansion of a around to evaluate
Qg: ag 7 + ( Then 7 (a, -a;) = T(a 7 + ( - a.) = -a (
And so lim T(a; a4) = -44-
Now if [M - 2 2, then the following term appears: T(a, -(-
o T( of T +(())))) - + (++)). And so limm- T(a, ox,) lim -xx 7
+ 0 ( = 0.
Therefore, the only e in the sum with non-zero contribution are where MM Me < that is. when e" unmasks at most one dimension c'. When no dimensions are unmasked, g(c* and if e* unmasks one dimension, we have q(c c', c²)- -a/-
ct cc) = 1.
e does not unmask any dimensions, then there are no variables in 20 Vigt to compute the
probability over in log lo po(Cio. of Cua I ct), giving probability 1 and a term equal to 0. Next, if e unmasks only dimension i E Met such that of ci, then po Ve. = ce W., d²) = (e = cf c*).
Therefore,
d Σ
lim
Lunm.T.k = MDM = =B, (0
log ( = c()]
(44)
T
Summing Lemmas C.4 and C.5 completes the proof of Theorem C.I.
D Neurosymbolic diffusion models: formal definition and NELBO derivation
In this section, we will formally define derive the NELBO for neurosymbolic diffusion model. Throughout this section, assume the same notation in Section A. We refer to the graphical model Fig. 2 to set up the model and the notation.
D.1 Formal model definition
First, we will define the discrete-time data log-likelihood. We let C be the trajectory of partially T-1 masked concepts over timesteps c", c 2 ...... c.,, and similarly Yoς is the trajectory
28

---

X
c
y
y
1
x conditioning
forward
reverse pe
Figure 2: Probabilistic graphical model for neurosymbolic diffusion model. The forward process q. indicated by striped arrows, masks both concepts and outputs y. Since only y" is observed, variational distribution qe has to predict c from y" and x. The reverse process, with regular arrows, unmasks both concepts and outputs y, transforming concepts into outputs at every time step.
y², y ..... yy' Marginalising out all latent variables according to the graphical model in the NeSWDM (y. x) of outputs given inputs x as: bottom of Fig. 2, we define the data log- ligleikl pe
NESYDM (yo) x=)== = Σ Σ q(c' y") Pg
II (c ((((), xy=o c>(k), ((()) xx) (45)
Y(
Here, pe(c" c² x) and poly" c², yf, x) are defined in Section 3.1.
First, we define the conditional program Poy as the program yp that maps concepts to outputs, but always returns y if dimension i is unmasked in y". To be precise,
(E = ((")) if yf
(46)
of
We need this definition in Eq. 4 to ensure the output unmasking model satisfies the carry-over unmasking assumption from Theorem C.I.
Next, define
po (50 ce,y' y','',x xx) Σ Po | (ex 20
(e9) 50)
(47)
as the output unmasking model such that the MDM defined as Ezo Po(50) c x)g("" 1yt,9) is
equal to po(y" c² c',y', x) defined in Eq. 4:
Σ Eo c x)g(x* 1v'55% = ΣΣ (e ct, (E)) = 501a("" 10 (48)
80
Po x))x)) I (y: = po c',y', Σ
(49)
Note that po c",, y², x) does not decompose into product of marginals, requiring the new results in Section C rather than the standard MDM NELBO derivation.
To be able to Theorem C.I and the other lemmas in Section C. need to ensure that the output unmasking model satisfics the assumptions Theorem C.I. Since Py: maps completely unmasked concepts completely unmasked outputs, it satisfies
masking probabilities. Further, the carry-over unmasking assumption is satisfied, since for any unmasked dimension E Uy and
any concept čo, Py (E"); = y by Eq. 46 and hence Po = y/ c² c.,y", x) = 1. Importantly, the carry-over unmasking assumption would not hold if we used (e))) instead of pp (eº) in Eq. 47, and would not have been able to use the results in Section C.
29

---

D.2 NELBO derivation
Theorem D.1. Let po(c") c' x) be a concept unmasking model with zero masking probabilities and earry-over unmasking as defined in Theorem C.I, x0 [Ve] - [Vyl be given program, qo(c²) y" x) be variational distribution, and 0g be noising schedule. Then we have that the data log-likelihood as T is bounded as lim logre NNNSVDM
p (y x) S DNSSYDM. where
o
LNSSYDM [E (x,9)
log (c) - c',x)
a4
NE M,
Gei Concept unmasking loss
(50)
+ 0
log (e | x))l((()))) v/
H[ge(c |y |ydxx]
Cutel: Variational entropy
Ey: Output unmasking loss
Proof.
- log Po
NESYDM (y")
|x)
log
Po
Po(C Y
x
(51)
log
- (
Ir (C, Y yO x)
Y
C
Next, we again the trick from Eq. 21, both for C and Y, and we expand the model pe following the graphical model in Fig. 2:
log (c . c y x)p(cc,
Ihe po(c", y c', x²,
(C,
qo(c), co x.y")((y! y0)
IT=2 ct, c0) y0)
log po(c c ct,xx) x)
oly (yo) [- loggpo c yt,, x
E (x
E gie eny
go x, y")
Cus.y.::
recomsiruttion
Luaee reconstruction
Be KL[g(C" | .e,,'))ll ('locc |c, cl,x)]++
Lum,e, as uummssking
Egter y' yo) KLLgg(y") y", yd) llvoly" Iy, o², xx,x)]
+ +
Cunar unmasking
pic' y²)
where = Eyyee Sy (y"
log go y x is a constant and equal to if p(c', .y) = 1[c²
m y 1 m]. which is true by assumption.
Discrete-tie time NELBO. Next, we use Lemma C.2 to rewrite Lee.y T and L, Then, the first two terms are the reconstruction losses for yd and e respectively, and the third term is the entropy of the variational distribution.
E ocr 2 1y0) [- loggoo "5==poo0""" y ,o,y,, x)] +
L.C + Lree,e.T = =Boo(e"
(52)
-log = ct x)) x)) log (c 1 x0,x0)
E vitt (eo)
Similarly, using Lemma C.3, we have the concept unmasking loss as
T
Lumm, ..P
Be of
log po (C W.. -ia Wa lc,,x)
(53)
k=2
30

---

For the output unmasking loss Lumm.y again using Lemma C.3, we have
Σ
Cumm.y &
Σ y" log pe (V you |c,xxx)] k=
(54)
km
Summing Eqs. 52 to 54, we get the discrete-time NELBO.
Continuous-time NELBO. Using Lemma C.4 twice and adding the entropy of the variational
distribution in Eq. 52, and then using Lemma C.5 twice, we get the continuous-time NELBO:
at 1 - a-a
NESYDM (0.
Σ k M
log ( ci c',x)
Cei Concept denoising loss
(55)
]]
Bg(y
log po ( = y c c',y',xx) xx)
H (c)) |y |y²xx)]
iEMy
Gmtg] Variational entropy
Output denoising loss
Next, we will further simplify the output unmasking loss Ly with a Rao- Rao-Blackwellisattoon to get the form given in Theorem 3.1. Using Eq. 47,
a
by = 1o (olo)))loorttexxxx
Σ iEMy
log Po = ve c ,',
1 04
= _e..oo.11.0000..com (xx,x)
log Σ Σ
Co (c)xx)((gg(((") =5
iEMy,
yo ve 20
d
-E,,oo (0) (x,0)
log Σ
Po d',x)
Σ
1 (10))("0) = 530
att
iEM y
2al
8
0/2 1
log Σ Po c. x' (E"); = =vol
a4
My
20
where in the last step that only a single ÿo satisfies B (τ") y0 and appears in the sum only if exactly that 50 has ग vf. and the conditional independence in Fig. 2 of y' and et given y Next, define the following inductive hypothesis based on the value of Y:
Cy -Enn
a
Σ log Σ (e" | x))x)()(())
=
(56)
Base case = The only elements in the support of g(y² y are vi vp and sf = m. If v (probability ax)), the set of unmasked values is empty, and so the loss is zero. If it is (probability 1 a4), the only masked dimension i 1. Furthermore, there are no unmasked dimensions in y hence 'py = xp and so the loss is
Ly = Ee-(0,11 x)
af log Σ (c xe.x) vil 80
Inductive step Y> 1: Assume the result holds for Y - 1. Like in the base case, g0v² v& y²) = ar and q = m y") = at Then, let ÿd denote all variables yd except y and we assume the inductive hypothesis holds for We again consider the two cases: Either y = v with
31

---

probability a, or v = In with probability 1 - ag.
a Σ
cy 10.1 y1(x,00))
log Σ
pa(è I (x)) - v
I at
iEM,
20
=R1~(0.1) ( (x))
Σ Ealss 1x9)
log Σ po | (pgo (E0); = 3/1
ait
y
iEM
60
(1 - oz)ak
log
M po(ee | ((xx))((s(((e)) = 4!'
1
Note now that the second term contains the same sum over the i E My as in the first term, but in addition it contains the dimension Y. We next move the other terms into the first term, leaving with weight of og for the first term:
I-ac
(fo
d d
Cy (0.1
Eg(3"
1r9
Σ
log
Σ
po ['xxx)((pg((())) v
sEM
+ al log Σ poleo (pg))) v 60
Next, we apply the inductive hypothesis to the first term. After, note that the second term is independent the value of ye as the result of spy. (τ") does not depend on yr.
Y-1 log Σ (e
Ly (00
| (x)x)) = =
Σ q(3s ira log
D ce xxxx))(p = =881
+
69
1E (x)
0
log Σ
po x)(p(((((()) = =
1=1 20
completing the inductive proof.
Finally, replacing Eq. 56 for Ly in Eq. 55 completes the proof.
E Gradient estimation details
In this section, we provide additional details and formalisation on our gradient estimation procedure, extending the discussion in Section 3.4.
32

---

Given some onput pair (x.y") ~ D, the gradient of the loss is given by [70, 82]
VoL NESYDM
V VoHlqgo (c xxy")
+
Gradient variational entropy Vo CH(v]
[e [l oo xxyx))
Vo log = = x))
1 04
ie M
Gradicnt of concept unmasking Ve
log
V Ve | xxx, -
Gradient of oulput ummasking loss Voly
ΣS Σو= [Kb())); =y
log = = c 0
log
V log (c xx,
1 Ot
S
aEMM
Indirect gradient sampling from distribation (ignored)
Monte carlo approximation. We will monte carlo approximation estimate this gradient. We first sample a single c. (c X, yy), ~ [0. 1]. and then a single ~ q(c' c²) using Eq. 9. Finally, sample S samples 20 ci:-.-. Cg Po (e ct, x) to approximate the gradient of the output unmasking loss Ly with the RLOO estimator [38]. Alternatively, one could use probabilistic circuits compute this gradient exactly [50, 86].
Indirect gradient. The indirect gradient arises from the expectation over the variational distribution which depends on the parameter 0. This term has high variance in monte-carlo estimator. Firstly, the vanilla score function estimator is known to have high variance, especially without additional variance reduction techniques [59]. However, the reward, which is given between the large braces, is doubly-stochastic: it depends on sampling L, c', and čD ..,... es making it an inherently noisy process. Furthermore, when using the variational distribution defined in Section 3.3, the score term l log (c x, y²) itself a NESYDM for which computing log- bog-likelhooos is intractable, and thus we would require additional approximations to estimate Because of the variance, intractability, and to keep the algorithm simple, we ignore the term altogether.
Therefore, our gradient estimate is given by
Ja
Σ
Vo Volog po = xc)
TH VoHlgglee x +
g
C 1 Ct REM
Choose estimate of V Cutjel
Unblased estimate VoLc
(57)
s
(I(p(e)), = 101 - us) Vo logpe c², cx,x),
SS 1)p4 j=1
Consistent estimate of Vo
where = [x(())) y is the empirical mean of the constraints, and Te: and Ty are weighting coefficients. We keep 7 = 1, and tune the other two. Additionally, inspired by the local step approach of [32], average tuning among different problems. This is especially useful in experiments with variable dimension size such as MNISTAdd and Warcraft Path Planning. We discuss how estimate the gradient of the entropy of the variational distribution in Section 3.4.
dimensions rather than summing to stabilise hyperparameter
Estimate of VeLy Next, derive the consistent gradient estimator for Voly using the RLOO estimator [38]. Assuming we have some , and c', and using the score-function estimator, the
33

---

gradient of the loss is given by
Vo a
Ve log Σ pe(ć") | xxxx))(o(ē"); v.l
Vovo(C")
c' (x))))(((e)) 396
G0 Po
c¹ xxx)) v.7l
v (o c², xxx)) - v/ Vo po c',x)
P x) [1 (c()) vlll
Vo Pooce el x) [1(((e)) v Vo lo (c x)]
(58)
pe" (c))) = y/ll
Both the numerator and denominator are expectations under Pe c² x) of the constraints, A consistent (but not unbiased) estimator given by sampling S samples c ci...., ... po c², x) and taking averages at each of these 2Y expectations separately. Then, we will use RLOO as baseline reduce the variance of the numerators. A baseline 0, and so by linearity of expectation,
constant where we use
that for any distribution pa(a)) Ppo(z)]bV log po()) [pf(=)(((())) b) Ve log Pe()) = pp)(() [f Ve log pe (z)]. Since we are using S samples, we choose for each sample é) and dimension i the baseline biy to be the empirical mean over the other samples, leaving one sample out: big - Eins [p((e));
vº]- Then, (1[x(c)))
v bij) Vo le (C) | c', x) is an unbiased estimator of the numerator. Finally, we average over the S different estimators obtained this way to derive the RLOO gradient estimator
E (e ct x) [1(p vll V log (o c',x)]
(1(p(c)) v by)) poc c',x)
j=1
(S 1)1 (p(()) = v E1zs 1(p(E)); = vi' ) Vo logrre c'
S(S - 1)
[L(p(())) = v - -5-
-1=1 1(p(t)); = v99
Vo Vologpo(e x),x)
S(S -
j=1
S Σ
= (S -
(1(x(E)); = vill - p4) V Co Vologpo(e (',,x
(59)
j=1
Combining Eqs. 58 and 59 gives the gradient estimator:
Voly Rs (y og)==
P Σ 1=1
(1(x(c)) = =v.1 - -m4) Vo Vologro(c)) |
(60)
Full gradient estimation algorithm. In Algorithm 1, we provide the full algorithm for estimating gradients to train NESYDM, The algorithm proceeds by sampling e from the variational distribution, and then sampling a partially masked value c'. We then compute the gradients of the three individual losses using Eq. 57. This requires sampling S samples from the unmasking model, which is done in line 5. Finally, we weight the gradients appropriately and sum them up.
F Sampling details
We use the first-hitting sampler [94] if the configured number of discretisation steps T is larger or equal to the dimension the concept space C. Otherwise, we use a T-step sime-discretisation the reverse process [68].
34

---

The first-hitting sampler in Algorithm 3 randomly samples the next timestep to unmask at. There, randomly selects an index unmask using the concept unmasking model. Note that a is the inverse of the noising schedule. Since we do not provide the temperature to our neural networks, this sampler is, practice, a suncept-by-coneepe decoding process similar to masked models like BERT [23, 94].
Algorithm 3 First- First-hitting sampler for pe (e x)
1: Input: x, unmasking model pa c*)
2: 1<1
3: c² = m
4: for k <- C to do
5:
$ f (1- Vu(1 az)), where a ~ 1))
Select next timestep to unmask at Select random dimension unmask
6:
Uniform(Mer
7:
c* c
8:
of (e x, c')
Sample the unmasked dimension
9: t
Return ca
Instead, the time-discretised sampler in Algorithm samples a completely unmasked sample e from the unmasking model at each timestep, then samples e from the reverse process in Eq. 10 obtain the next timestep. When sampling from the reverse process, the algorithm remasks some of the newly unmasked dimensions in 2", while keeping the unmasked dimensions in cx fixed.
Algorithm 4 Time discretised sampler for p(c) x)
1: Input: x, unmasking model po (e X, c²), number of discretisation steps T
2: c² = m
3: for k < T to do
4: E"
~ Pe c²) c²~ c c² T0)
Sample from unmasking model >> Sample from reverse process in Eq. 10
5:
6: Return e
F1 Sampling from the variational distribution
We adapted the two samplers above to sample from our model conditioned on the output y". We use simple resampling approach as described in Section 3.3, which we elaborate here. First, recall the relaxed constraint for 3 > 0 as
ce y -exp(-3
Σ 1 +
(61)
1=1
Then, we define the distribution to sample from as
go (c x, c' ,',y") x po x, e' )ra(( 1
(62)
Since we cannot tractably sample from this distribution, we self-normalised importance sampling [12]. In other words, we sample K samples from the unmasking model, compute the relaxed constraint for each sample, and then normalise these values. Finally, we sample from the renormalised distribution. We provide the full algorithm in Algorithm
We note that the distribution pe" x, c²) does not appear in the importance weights. This holds because we are sampling from thus divides away in the computation of the importance weights.
We implement this algorithm in the two samplers as follows. For the discrrtiet sampler, we replace Algorithm 4 of Algorithm with Algorithm 5. Together, this is the algorithm used in [29]. For the first-hitting sampler, we replace Algorithm of Algorithm by first calling Algorithm 5 to obtain some é and then returning the i-th dimension 20.
Relation to Markov Logic Networks. The distribution in Eq. 62 is similar Markov Logic Network (MLN) [67]. Particularly, the formulas of the MLN are (I): the different constraints
35

---

Algorithm 5 Self-normalised importance sampling for go(c²) x, xx,c,, ,²,
1: Input: x, y', unmasking model pa x, c²), number of samples K
2: c..... 2o pa(co) x, c')
Sample K samples from unmasking model I> Compute importance weights
3: wi =ra(e yy for all i [K]
4: Z Di= wi
K
Normalisation constant D Sample from renormalised distribution
5: i ~ Categorical 2
6: Return c
I[p(E"); A v.), each weighted by -B" and (2); the unmasking model (e c'), defined with formulas 1 1 c and weight log po (c) = di x, c'). In particular, this means that c that violate constraints still have positive energy. However, the energy exponentially shrinks by factor of for each violated constraint. Since we use rather high values B > 10, the resampling step in exp(0)
Algorithm is extremely likely to pick the sample that violates the least number of constraints.
Numerically stable implementation. In practice, computing Eq. 61 in Algorithm 5 is numerically highly unstable if multiple constraints are violated. Then, the reward is equal to exp(18) where 7 is the number of violated constraints. PyTorch floats are roughly between xxp(-104) and exp(88), meaning that for 3 > 10, the reward underflows at / 8. First, we note that when sampling from the reweighted distribution in Algorithm 5, probabilities are computed as the relative proportion of the rewards. Therefore, we can simply rescale all rewards by a constant factor to ensure they do not underflow overflow. Particularly, redefine the reward
( 1 exp (- max
(Kp(")) # v I., U
Here, L >> O acts as scaling on the reward as ra.L,u not active. U acts as floor on the reward such that samples that violate many constraints still have non-zero probability, even if it is extraordinarily unlikely. We fix U = 100 to remain in the floating point range. Note that this is ever so slightly biased as will over-estimate the probability of the samples that violate the least number of constraints. However, this bias is very small as the probability of choosing these samples is extraordinarily low.
yd) exp(L) if the max is
We want to choose L to maximise the range of the reward among the samples without overflowing.
Within this range, the differences between the samples that violate the least number of constraints most important: these are the samples we are most likely to choose. Our intuition is as follows: we set L to the average number of violated constraints among the samples in Algorithm 5. However, if this would overflow the best sample, we instead set L such that the best sample has reward of (X)) where M- 70 prevent overflow. Therefore, we choose
L = min
(o(())) + 4 M + min 3r Σ 1 k=1
(p(C2); + wi1l
(63)
G Experimental details
NESYDM is implemented in PyTorch. We used RAdam [45] for all experiments except for MNIST Addition, where we used Adam [35]. We did not compare these optimisers in detail, but we do not expect this choice to significantly affect the results. Furthermore, we used default momentum parameters for both optimisers. For all neural networks used to implement the unmasking model po(e" x, ).), we did not pass the current time step / the network, as previous work found minimal impact on performance for doing so (Appendix E.5 of [68]).
For all experiments, used GPU computing nodes, each with single lower-end GPU. In particular, we used NVIDIA GeForce GTX 1080 Ti and GTX 2080 Ti GPUs. All our experiments were run with 12 CPU cores, although this not the bottleneck in most experiments. On the GTX 1080 Ti, our experiments took between I and 17 hours, depending on the complexity of the task and number
Unlike MLNs, we sum unsatisfied constraints rather than satisfied ones to ensure re(e 1
[0. 1].
36

---

of epochs. The project required extra compute when testing different variations of the model, and by performing hyperparameter tuning. For repeating our runs and hyperparameter tuning, we further expect around 600 total GPU hours are needed.
G.1 Hyperparameter tuning
We list all hyperparameters in Table 4. We perform random search over the hyperparameters on the validation set of the benchmark tasks. For the random search, we used fixed ranges for each parameter, from which we sample log-uniformly. For the parameter 33 sampled uniformly instead. We used a budget of 30 random samples for each problem, although for some problems we needed more when we found the ranges chosen were poor.
Several hyperparameters, namely the minibatch size, S, K, T' and L, are compute dependent, and keep these fixed when tuning depending the compute budget and the problem size. The hyperparameters we do tune are the learning rate, Ye. "is, and B. We found that low values of % were usually fine, and that for large enough / above 10, its value did not matter much. Therefore, the most important hyperparameters to tune are "/H and the learning rate, for which the optimal values varied between problems significantly. For an ablation study on the influence of the value of the loss weighting hyperparameters, see Section H.2.
Table All hyperparameters used in the experiments, and rough recommendations for some of their values. We recommend at least tuning learning rate, and "H and % to some extent (leaving Vy at 1). Some hyperparameters are compute dependent, and higher is always better for reducing gradient estimation variance (S, K, T) and majority voting quality (L,7).
Variable Recommendation
Description
Range
Definition
(0.0001, 0.0005)
0.0005)
Overall learning rate
R>0
Minibatch size
Epochs
N
7y
Weight of concept unmasking loss
R20
Eq. 57
ee
10-5
Weight of output unmasking loss
R 20
Eq. 57
HH
(0.002,
2)
Weight of variational entropy
R
Eq. 57
10
Penalty in soft constraint
00
Section 3.3
S
2
4
Number of RLOO samples
N
Eq. 7
K
2
2
Number of SNIS samples for go
Section F.1
T
VC
MDM discretisation steps
Section 3.5
L
28
Number of majority voting samples
N
Section 3.5
G.2 MNIST Addition
We use the LeNet architecture [41] for the neural network architecture is standard in the NeSy literature [52]. As there are no dependencies between the digits in the data generation process, making the neural network conditional partially unmasked outputs is not useful: merely predicting marginals is sufficient. Therefore, we ignore the conditioning on c when computing pe (c c', in Eq. 47.
Since there no standard dataset for multidigit MNIST addition, we use a generator defined as follows: for some dataset of MNIST images, we permute it randomly, then split it into 2N parts and stack them to obtain the different datapoints. This ensures we use each datapoint the dataset training datapoints.
exactly once, ending up in 60000
2N
We tuned hyperparameters in accordance with Section G.I. Since MNIST has no separate validation dataset, we split the training dataset in training dataset of 50.000 samples and validation dataset 10.000 samples before creating the addition dataset. We tune with this split, then again train 10 times with the optimised parameters on the full training dataset of 60.000 samples for the reported test accuracy. We tune on
15, and reuse the same hyperparameters for N and N 4. For number of epochs, we use 100 for N and N = 4 as an epoch is more expensive for smaller N and because N 15 requires moving beyond cold-start phase. We found all 10 runs moved past this phase within 100 epochs, but needed more time to converge after.
37

---

Table 5: Hyperparameters for MNIST Addition and Warcraft Path Planning.
Variable
MNIST Addition
Path Planning
learning rate
0.0003
0.0005
minibatch size
16
50
epochs
N = 4: 100, N = 15: 1000
40
Ye
10
10 10-6
0.01
0.002
Ty
B
20
12
S
1024
12 x 12: 16, 30 x 30: 4
K
1024
12 12:
4, 30:
2
T
20
L
8
Baselines. For all methods, we take the numbers reported in the papers where possible. We obtained numbers for Scallop from the PLIA paper. For A-NeSI, we pick the best-scoring variant as reported, which is Predict for N = 4 and Explain for N = 15. For DeepSoftLog, A-NeSI and PLIA, we obtained performance on 10 individual runs from the authors to compute the Hhan-WWitney U test.
G.3 Visual Path Planning
Following [80], we categorical costs for the Visual Path Planning task. We use V. 5, which corresponds to possible cost values in the data, costs = [0.8, 1.3, 7.7,, 9.2). Then, d corresponds to an index of the cost of each grid cell. That is, CNi+s E {1,..., 5.. corresponds to the cost value costs [ch at grid cell i,j.
We adapted the ResNet18 b-based architecture from [62] for the unmasking model p(č") x, c²) over grid costs. This architecture consists of a single convolutional layer to start encoding the image, with batch normalisation and adaptive max-poot max-pooling to grid of size x N. After this, we have 64-dimensional embeddings for each grid cell. To condition on the currently unmasked values, we add embeddings of c E {1...., 5, m) m).² for each cell: use six 64-dimensional embeddings for the different costs plus the mask value. Then we add these embeddings to the image embeddings cell-wise. That is, if e/ is the image embedding at cell i, then the
ef...., .e e
follows. Finally, "x+,'" After this, a ResNet layer containing two more convolutional layers over the possible costs.
embedding is el.5 + eC
output layer that takes the grid cell embeddings and predicts distribution
We performed hyperparameter tuning the validation set of the 12 x 12 grid size problem, then reused same hyperparameters for the x 30 grid size problem. We only reduced number of RLOO samples S and the number of samples for the SNIS algorithm in Section 1 for the 30 x 30 grid size problem to reduce the overhead many calls to Dijkstra's 's algorithm. This algorithm quickly becomes the main compute bottleneck on large grids.
For 12 12, we evaluated test accuracy accuracy every 5 epochs within the 40 epoch timeframe, choosing the best performing model for the test accuracy. We found that on 30 30 the model was sometimes unstable, suddenly dropping in accuracy and recovering after while. As is common in this task and our baselines, we consider path prediction correct if the predicted path has the same cost as the gold-truth shortest path given. This is because shortest paths may not be unique.
epochs, and for 30 30 we evaluated validation
Baselines. We take the numbers for EXAL as reported in the paper [85]. For A-NeSI, I-MLE and A-NeSI + RLOO, we obtained performance on 10 individual runs from the authors compute the Mann- Whitney U test.
38

---

G.4 RSBench
For all experiments, we adapt the implementation of the benchmark in the RSBench repository [11]. We use the conditional 1-step entropy discussed in Section 3.4. For the MNIST experiments, we brute-force the conditional entropy computation, while for BDD-OIA, we adapt the inference procedure in [1] I] to obtain the conditional entropy.
G.4.1 Metrics
For all tasks, compute the Expected Calibration Error (ECE) over marginal concept probabilities [60] as a metric for calibration. Since NESYDM is not tractable, we have to estimate these marginals. Therefore, use simple maximum- likellihoi estimation obtain approximate marginal probabili- ties for Pa (w; x) by sampling L samples from the model and taking the empirical mean. We used L= 1000 throughout improve the accuracy of the ECE estimate.
For the MNIST tasks, we report both the output accuracy Accy and concept accuracy Acce- In particular, for output accuracy, compute exact match accuracy over the output predictions. For concept accuracy, we use micro-averaged accuracy over the concept predictions (that is, the two digits). This requires NESYDM to output predictions for the digits separately. We tried two different majority voting strategies using the L samples. 1) Take the dimension wise mode among the samples, or 2) take the most common complete concept vector and use the individual dimensions of as the predictions. We used the second strategy in Table to ensure the predictions can capture dependencies between digits, and compare the two methods in Section H.1 and Table 8.
For BDD-OIA, we report macro-averaged Fl scores for both the output and concept prediction. For example, for the concept F1 score, we compute the F1 score for each concept separately, then take the unweighted mean these Fl scores. Similarly, we computed computed marginal probabilities for concept and output
averrged ECE scores
for concept prediction. For NESYDM, predictions, that is, per dimension. Furthermore, we recomputed all metrics for the baselines reported in Table 3, we found bugs in the code for both metrics in the RSBench and BEARS codebases.
Note that PNP !I was called DPL in the BEARS paper. We changed the name as 1) the baseline code did not actually use the DeepProbLog language, and 2) there are many different NeSy predictors that could be implemented in DecpProbLog, so it is not clear which one compare to.
G.4.2 Why Expected Calibration Error for reasoning shortcut awareness?
In this section, we motivate the use of concept calibration, in particular using the Expected Calibration Error (ECE), to empirically measure reasoning shorteut (RS) awareness. BEARS [55] introduced RS-awareness as attaining high accuracy concepts unaffected by RSs, while being calibrated on concepts affected by RSs. In the latter case, perfect concept accuracy is unattainable, and we should aim for high calibration. A model that predicts concepts in such a way by mixing over RSs that cannot be disambiguated from data alone maximises data likelihood [39].
For example, consider the XOR problem from Example 2.2, which has RS that maps MNIST digits of Is to Os and MNIST digits of Os to 1s. This RS cannot be distinguished from the ground-truth mapping. The ideal model under this ambiguity would assign 50% confidence to the ground-truth mapping and 50% to the RS. We can achieve this with a neural network that given two distinct MNIST digits outputs a uniform distribution over (0, 1) and (1, O), and given two equivalent MNIST digits, outputs a uniform distribution over (0, 0) and (1, 1). In the first case, the XOR function will return 1 with probability 1, and in the second case, it will return 0 with probability 1.
This attains maximum data likelihood as the model returns the correct output label. Furthermore, it always assigns 0.5 probability to I and O. Its concept accuracy will also be around 0.5 in our synthetic setup. Therefore, the ECE will also be around O, highlighting its calibration, and in practical experiments low ECE values are attainable [39]. Instead, a non RS-aware method finding the RS will attain an ECE of around I: it always predicts exactly the opposite of the correct concept. Since the non RS-aware method randomly finds the RS or the correct solution, the ECE will be around 0.5 on average [39]. For concepts that are not affected by RSs, the accuracy will be and maximum likelihood will also attain high confidence, resulting also in a low ECE value.
39

---

That said, ECE is a proxy for measuring concept calibration, but is not necessarily the only or perfect metric for uncertainty quantification. A further theoretical study evaluating how to best measure RS-awareness could be of significant value.
G.4.3 Hyperparameters
Table 6: Hyperparameters for RSBench.
Variable
MNIST Half Even-Odd
BDD-OIA
learning rate minibatch size
0.00009
0.0001
16
256
epochs
500
30
Ve IH
1.5 10
5 10-6
1.6
2.0
Ty
B
10
10
S
1024
1024
K
1024
1024
8
22
L
1000
1000
For the datasets in RSBench, we tuned on the validation set for all parameters using the conditional entropy. Then, ran additional hyperparameter search on just the entropy weight to find the right trade-off between calibration and accuracy. We found the entropy weight can be sensitive, where high values significantly slow down training, while low values may result in uncalibrated models. See Table 10 and Section H.2 for an ablation study on the effect of the entropy weight. For L, we use much higher number of 1000 samples. This is ensure the Expected Calibration Error is properly estimated (see Section G.4.1 for details). For the runs with the unconditional entropy, we used the same hyperparameters and no additional hyperparameter search.
G.4.4 Experimental details and architectures
MNIST Half and MNIST Even-Odd. We adapted the original architecture from our baselines in [55]. For both experiments, we encode the two individual digits in with convolutional neural network (ReLU activations) of 3 layers, with 32, 64 and 128 channels respectively. Then, we flatten the output, obtaining two embeddings e₁ and e2. For predicting the unmasking distribution p(c x, c²) for the first digit, we concatenate one-hot encodings of é₁ og and e1, while for predicting the distribution of the second digit p(22 x, c²), we concatenate one-hot encodings of clz cf and 62. Note the order here: This is to ensure permutation equivariance, as the sum is a commutative operation. Therefore, like baselines,
have disentangled architecture that uses the same neural network to classify the two digits, while still incorporating the currently unmasked values. Finally, using the concatenated vector, use a linear output layer and softmax obtain the distribution over the possible digits.
BDD-OIA. We used early stopping by running for epochs, testing on the validation set every epoch and picking the model with the highest validation accuracy. As in [55], we used preprocessed embeddings of the dashcam images from a Master-RCNi [66]. This Faster-RCNN was pre-trained on MS-COCO and fine-tuned on 100k. These are provided in the RSBench dataset, and were also used for BEARS. For the unmasking model p(E x, c¹), we adapted the MLP from [55], using single hidden layer with dimensionality of 512, by simply concatenating one-hot encoding of c' E {0, 1, m to the input embedding of x. Note that, since the concepts are binary, this one-hot encoding is 3-dimensional vector, it can be 0. 1, or the mask value
Baselines. We obtained results of the 5 individual runs used for each method [55] and re-evaluated them to obtain 4 digits of precision for all reported results, as [55] only reported 2 digits of precision. Furthermore, we used these results to compute statistical significance tests. We have different results than reported in [55] for BDD-OIA as we found bugs in the code for the metrics.
40

---

H Further ablation experiments
H.1
Other majority voting strategies
As stated in the main text, computing the exact mode argmax,o P4 WNSYDDM(y (y x) is intractable in general, also for representations supporting tractable marginals [2, 84). Throughout this paper, we used the majority voting strategy described in Section 3.5. However, when observing the results on MNIST-Even-Odee one might be puzzled by the relatively high performance on concept accuracy while the output accuracy is low. We hypothesised that this was due to our chosen majority voting strategy, and repeated the evaluation of the models using different strategies, which we describe here. All assume access to set of samples cf. cf......c ct, po(c" x, m).
(PTM): The strategy described in Eq. 8, and the main one used in this paper. We emphasise that this is the "correct" strategy according to the generative process of NeSy predictors.
Program-then-true-mee
Program- taanm-tte--marina monee (PMM): Similar to above, we feed all sampled concepts into the program, but rather than taking the most likely output, choose the most likely output dimension-wise:
i. argmax
E(p(())) vi
(64)
True-mode-then-proaee program (TMP): Find the mode of the sampled concepts, then feed that into the program:
y = = aargmax,
Σ Iic - 1=1
(65)
Marginal- soseeaal-moeeefee moode-tee--prone thoogram (MMP): Compute the dimension-wis. mode of the concepts é, combine them into a single concept è, and feed that into the program:
é argmaax
Σ L.gh cıl.
S ((c)
(66)
Table 7: Output accuracy, both in- and out-of but-of--istribuue -idtitriibu,o,, for different majority voting strategies on the MNIST-Half and MÑIST-Even-Odd datasets.
Strategy
Half, ID
Half, OOD
Even-Odd, ID
Even-Odd, OOD
NESYDM, Conditional entropy
PTM
99.12 0.18
28,45 0.90
98.65 0.31
0.02= 0.04
PMM
99.12.1 0.18
28.44 0.91
98.65.1 0.31
0.02 0.04
TMP
98.871
28.461 0.91
97.94.1 0.49
0.18 0.14
MMP
60.161 4.77
33.15 1.40
25.1411 2.81
5.39 0.45
NESYDM, Unconditional entropy
PTM
99.12+
10.95 0.05
97.52+ 0.44
0.00= 0.00
PMM
99.12+
10.95+ 0.05
97.52+ 0.44
0.00= 0.00
TMP
99.26 0.26
15.71 0.49
98.10- 0.37
0.02 0.02
MMP
79.42+
44.11 4.87
87.644 0.37
5.27 0.52
We evaluated these strategies on the validation set of all benchmarks, and found that they all performed similar, at most marginally worse than the PTM strategy used in this paper. However, we found exceptions in MNIST-Half and MNIST-Even-OUL -Oddd where MMP significantly outperforms the other strategies in the OOD setting, while significantly underperforming in the ID setting, highlighted in Table 7. This result holds for both NESYDM with the conditional entropy and the unconditional entropy.
ID performance MMP takes rather significant hit because there are strong statistical dependencies between the concepts in the construction of the ID datasets. Especially the Even-Odd OOD dataset
41

---

is rather adversarially constructed, as highlighted by the extremely low OOD performance of all methods. However, because NESYDM has relatively high concept accuracy OOD, using MMP still results in some correct outputs.
We performed similar analysis for the two strategies for predicting concepts in Table 8. Here find that, overall, the true mode strategy usually performs better, except that we find a significant difference between TM and MM on the OOD dataset of MNIST-Half.
Table 8: Concept accuracy, both in- and out-of-distribution for different majority voting strategies the MNIST-Half and MNIST-Even-OOd datasets.
Strategy
Half, ID
Half, OOD
Even-Odd, ID
Even-Odd, OOD
NESYDM, Conditional entropy
TM
71.161 1.77
61.841 0.89 62. 02.761 0.77
20.331 1.33
15.60 0.99 14.56= 0.86
MM
66.781 2.84
19.65 2.37
NESy DM, Unconditional entropy
TM
79.41 6.58
57.22 0.49
0.36 0.39
4.65 0.49
MM
80.56 5.12
70.40 2.71
0.394 0.44
1.16 0.44
H.2 Effect of loss weighting hyperparameters
In this appendix, we investigate the effect of the loss weighting hyperparameters %e. 7H and on the performance of NESYDM. We experimented with the conditional entropy version of NESYDM on the MNIST-Half dataset with three repeated runs. Here, we kept the output unmasking weight Ty 1 and tuned the other two hyperparameters.
For the concept unmasking weight Ye in Table 9, we find that all tested values achieve high label accuracy. However, its value significantly influences the concept accuracy both in and out of distribution, and the OOD label accuracy. We observe values below are effective. We suspect the concept unmasking loss provide the model information that it useful, but it should not dominate the loss, as this results in significantly lower concept accuracy and OOD performance. Furthermore, results poor calibration, suggesting that the model converged onto single reasoning shortcut.
We observe a significant influence of the entropy weight "H in Table 10. All values below 1.3 seem to converge single reasoning shortcut, exhibiting poor calibration and worse concept accuracy. These runs do not balance the maximisation of entropy as the weight is too low, resulting in models with low entropy. By increasing the entropy weight beyond the value used (1.6), find that the entropy loss can also impact the performance when above 2.0, resulting in reduced label and concept accuracy and calibration. As the optimal range of values is quite tight, we recommend tuning the entropy weight when using NESYDM.
Table 9: Effect of concept unmasking weight on label and concept accuracies (in- and out-of- distribution) and calibration (ECE) performance on MNIST-Half. Bold values indicate best results per column. We used le-06 in the experiments.
Te
Accy
Acca f
Accy,ood f
AcCo,OOD f
ECEa,1D +
ECE&,ooD +
le-08
99.381
0.27
70.45 2.32
33,921 5.10
65.131 2.72
8.54 4.46
12.23 1.18
le-07
99.61 0.13
71.41 0.72
37.16 1.22
67.74+ 0.56
7.77 1.09
10.67 0.98
1e-06
99.54+ 0.80
72.88+ 0.85
33.21 7.06
64.86+
5.31+ 1.19
11.00= 0.87
1.5e-06
99.12+ 0.10
71.16+ 1.77
28.44+ 0.90
62.76+ 0.89
4.18 2.56
11.74 1.18
le-05
99,00 0.53
69.79 3.09
29.72+3.00
63.10=
6.83=
11.39= 1.76
0.0001
99.23+ 0.13
72.07+
36.46 6.60
66.8444.00
4.90=
10.22 1.96
0.001
99.61 0.13
72.03 0.84
32.75+
64.60
4.98=3.15
10.46 2.86
0.01
99.1511 0.48
71.60.1 0.35
31.991 7.80
5.4571
3.80 1.52
10.81 1.07
0.1
99,46.1 0.35
71.881 0.81
36.76.1 8.27
66.851
6.96-
12.35 4.01
1.0
98.841 0.61
41.55 0.12
5,70 0.24
38.651
56.87 0.25
61.09 0.11
10.0
99.381 0.13
41.591 0.13
5.64 0.19
38.591
57.00 0.23
60.97 0.08
42

---

Table 10: Effect of entropy weight on label and concept accuracies (in- and out-of-distribution)) and calibration (ECE) performance MNIST- Half. Bold values indicate best results per column. We used 1.6 in the experiments.
7H
Accy
Acc. t
AcDy,OoD t
Acce,OOD f
ECE,,
ECE,,0OD +
0.001
99.15 0.13
41.63. 0.07
5.611 0.16
38.631
57.051 0.12
61.081 0.16
0.01
99.00= 0.35
41.74+ 0.18
5.79 0.18
38.66+ 0.03
56.80+ 0.21
60.91 0.11
0.1
98.77=0.48
41.67+
5.61+
38.60+ 0.23
56.98+ 0.26
60.97 0.09
0.5
99.31=0.23
41.63+ 0.07
5.58+
38.59+ 0.15
56.94+ 0.09
61.09+
1.0
9.13
41.63:#
38.73 0.15
56.90 0.25
61.06
1.3
99.77= 0.23
67.05 1.99
35.51
65.79 1.79
9.33+ 1.74
12.26 1.31
1.6
99.1
71.16 1.77
28.44 0.90
62.76: 0.89
4.18+ 2.56
11.74 1.18
2.0
0.13
72.26 0.41
29.35 1.73
62.191 1.03
3.791 0.48
11.42.1 0.61
3.0
5.88
46.531 2.50
17.031 8.97
51,231 7.03
12.70 5.87
14.56 2.71
5,0
95.73-1.99
39.74.1 1.33
11.241 0.14
44.041 1.39
12.56. 1.33
24.22.1 2.12
10.0
85.73 0.35
34.22.1 1.27
10.8110.11
41.251 1.03
15,401 2.25
24.01 1.56
43


Reviews:
[{"review_id": "HGHhVU3Lxo", "reviewer": "Reviewer_N1ag", "summary": "Disclaimer: I am no expert in neurosymbolic models or diffusion models. I am unsure why I was assigned this paper and flagged this to the AC.\n\nThe paper proposes to use discrete diffusion models to overcome the conditional independence assumption commonly made for context variables in neurosymbolic models. \nThe paper proposes to do this by having a diffusion model to have global dependencies between concepts.\nThe work then derives the update rules and loss functions, before empirically evaluating e.g. on MNIST classification.", "questions": "See weaknesses", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The work seems well motivated\n- The paper is clearly written, technically sound, and can be followed\n- The work shows clear empirical improvements over prior work\n- Code is attached\n\nWeaknesses:\n- The experimental validation is limited to few tasks\n- The largest problem studied is MNIST classification. To me, these experiments do not show the \"scalability\" of the approach, as minst classification is a rather small-scale problem.", "was_revised": true, "final_justification": "nothing to be added", "rebuttal": "We thank the reviewer for their comments and feedback, and appreciate they believe our work is well-motivated and clear, and technically sound.\n\n>The largest problem studied is MNIST classification. \n> To me, these experiments do not show the \"scalability\" of the approach, as minst classification is a rather small-scale problem.\n\n**The scalability described here is regarding reasoning.** Our method also significantly surpasses baseline methods on large reasoning problems like visual path planning that are challenging for current NeSy methods [1-3]. Furthermore, we also study real-world images with the BDD-OIA dataset [4].  \n\n> The experimental validation is limited to few tasks\n\nWe are very happy to add additional tasks if the reviewer has a concrete list in mind.\n\n1. van Krieken, E., Thanapalasingam, T., Tomczak, J., Van Harmelen, F., & Ten Teije, A. (2023). A-nesi: A scalable approximate method for probabilistic neurosymbolic inference. Advances in Neural Information Processing Systems, 36, 24586-24609.\n2. Verreet, V., De Smet, L., De Raedt, L., & Sansone, E. (2024). EXPLAIN, AGREE, LEARN: Scaling Learning for Neural Probabilistic Logic. AAAI 2025.\n3. Maene, J., Derkinderen, V., & Martires, P. Z. D. (2024). Klay: Accelerating arithmetic circuits for neurosymbolic ai. ICLR 2025.\n4. Xu, Y., Yang, X., Gong, L., Lin, H. C., Wu, T. Y., Li, Y., & Vasconcelos, N. (2020). Explainable object-induced action decision for autonomous vehicles. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 9523-9532)."}, {"review_id": "2TYtpXYapi", "reviewer": "Reviewer_MBEg", "summary": "Briefly summarize the paper and its contributions. This is not the place to critique the paper; the authors should generally agree with a well-written summary. This is also not the place to paste the abstract—please provide the summary in your own understanding after reading.\n\nThe authors propose neurosymbolic diffusion models (NeSyDMs), which are a masked-diffusion-based class of neurosymbolic (NeSy) predictors operating both in concept space and in output space.\n\nHere, a neurosymbolic (NeSy) predictor is (informally) a model that extracts a concept $c$ from its input $x$ (normally with $c$ having conditionally independent coordinates; i.e. a “disentangled embedding” in some sense), and then feeds $c$ as input to a program $\\phi$, obtaining a final output $y = \\phi(c)$. The paper works with NeSy predictors in a probabilistic framework, so that concept extraction is seen as sampling from $p(c | x)$, and the posterior output distribution is $p(y|x) = \\int 1_{\\phi(c)=y} p_\\theta(dc|x)$. This distribution is known as a weighted model count (WMC).\n\nIn practice, the conditional independence assumption on concepts $c$ can be limiting, as many realistic tasks can indeed have interactions between ground truth concepts, and are potentially solvable even if the learned input-to-concept mapping is spurious (“Reasoning Shortcuts”, RS). Prior work has tried to get around Reasoning Shortcuts by building NeSy predictors that express uncertainty across concepts consistent with the input-output mapping. However, correctly expressing this uncertainty can be at odds with maximizing $p(y|x)$ for conditionally independent concept extractors.\n\nThe authors address this limitation by proposing a NeSy architecture allowing for expressive inter-dependencies between the coordinates of $c$. A natural expressive model class for this is that of masked diffusion models. Their model has the following main components:\n\n- A concept unmasking model $p_\\theta(\\tilde{c}^0 | c^s, x)$, which is essentially a masked diffusion model.  \n- A variational approximation $q_\\theta(c^0 | y^0, x)$ of the distribution of concepts compatible with an input-output pair. This shares parameters with the concept unmasking model, except that sampling is done through controlled generation, conditioned on $y^0$.  \n- An output reverse process (Eq. 4), which marginalizes over (masked) concepts according to the concept unmasking model.\n\nThe authors derive a NELBO for their model, which consists of a concept unmasking loss term (essentially the MDM loss for $p_\\theta(\\tilde{c}^0 \\mid c^s, x)$), an output unmasking loss (which requires computing weighted model counts), and a variational entropy term for $q_\\theta(c^0 \\mid y^0, x)$.\n\nThe output unmasking loss is non-trivial to compute, and requires using a REINFORCE Leave-One-Out estimator, which essentially involves sampling multiple concepts $\\tilde{c}^0_1, \\dots, \\tilde{c}^0_S$ from the reverse diffusion model, computing a per-dimension binary reward $\\mathbf{1}[\\varphi(\\tilde{c}^0_j)_i = y^0_i]$ for each sample, subtracting the mean reward over the other $S-1$ samples as a leave-one-out baseline, and weighting each sample’s reward by the score-function gradient $\\nabla_\\theta \\log p_\\theta(\\tilde{c}^0_j \\mid c^t, x)$ to obtain an unbiased, variance-reduced gradient estimate.\n\nComputing the variational entropy term is also challenging, since $q_\\theta$ is defined by performing controlled sampling on the concept unmasking model, with conditioning on $y^0$, which makes computing exact likelihoods intractable. The authors address this by working with 1-step entropies, i.e. using $T=1$ discretization steps in the diffusion process.\n\nSampling on a given input $x$ is done by simply denoising several concepts $c_i$ and taking a majority vote over the resulting outputs $y_i := \\phi(c_i)$.\n\nExperiments aim to answer (RQ1) whether NESYDM scales to high-dimensional reasoning and (RQ2) whether its expressiveness reduces reasoning shortcuts. For RQ1, NESYDM is compared to A-NeSI, Scallop, EXAL and I-MLE on multidigit MNIST addition and visual path planning (12×12 and 30×30 grids); it matches baseline accuracy on MNIST addition (92.49±0.98 for N=4, 77.29±1.40 for N=15) and exceeds others on 30×30 planning (97.40±1.23 vs ≤67.57±36.76). For RQ2, on the RSBench tasks (MNIST Half, MNIST Even-Odd, BDD-OIA) NESYDM is evaluated against DPL, Semantic Loss, DeepProbLog and BEARS, reporting concept and output accuracy plus ECE; it achieves comparable or higher accuracy with lower calibration error than these baselines. Overall, the results indicate that joint modeling via diffusion can scale without assuming conditional independence and produces more calibrated predictions under ambiguity.", "questions": "- I don’t have any major questions for the authors, and believe the exposition in the paper is already very thorough. Please feel free to point out e.g. any misunderstandings on my part in the summary.  \n- Out of curiosity, what was the authors’ process for constructing the presented formulation of NeSyDM’s? In particular:  \n  - Is it somehow unavoidable to denoise outputs in addition to concepts? If not unavoidable, did you try at any point in your exploration process to only use diffusion for the concepts? What were the limitations?  \n  - How did you arrive at the RLOO estimator as a solution to computing $\\mathcal{L}_y$? As in, what was the reasoning process for trying this approach specifically?", "limitations": "The authors extensively discuss limitations and future work in the conclusion.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**  \n- The method is well-motivated by a very concrete research goal: removing the need for conditional independence in NeSy predictors to enable reasoning-shortcut-awareness and better uncertainty quantification.  \n- Extensive exposition of related background: as someone with a background in diffusion models but not neurosymbolic prediction, I found the authors did a good job of introducing both relevant lines of research and how they interact in their formulation of NeSyDMs.  \n- Significant technical novelty: in order to get NeSyDM training to actually be tractable, the authors architect a training process including non-obvious algorithmic tricks (e.g. RLOO estimator for the output unmasking loss). This is a significant value add to the body of research in the area, as re-discovering this kind of trick can be very hard and time-consuming, so that knowing the tricks in advance can significantly save time from research efforts which might have struggled with these tractability issues.  \n- Overall very high quality of presentation, exposition, formatting, and so on.\n\n**Weaknesses:**  \n- The method is fairly complex and requires a lot of e.g. gradient approximation tricks in order to work. These tricks are explained separately in the main paper, but I believe it would facilitate understanding if the authors included a “linear” summary of what training and sampling look like at the end of the day when all components are put together.", "was_revised": true, "final_justification": "My recommendation of acceptance follows from the points listed in **Strengths**. Also, the authors agreed to include a more \"linear\" summary of their method, addressing what I considered to me the main missing element for this paper.", "rebuttal": "We thank the reviewer for their encouraging comments, and would like to confirm their summary is pretty spot-on! Furthermore, we are happy they thought our paper is **well-motivated**, discussing the related work properly while providing **extensive significant technical novelty**, and appreciate they believe **the exposition is thorough**. \n\nWe will extend our paper to give a linear overview of the loss computation and sampling, and provide extra discussion on our RLOO gradient estimator, as suggested by the reviewer.\n\n> I believe it would facilitate understanding if the authors included a “linear” summary of what training and sampling look like at the end of the day when all components are put together.\n\nThat is a great suggestion, thank you. **We will add this to our paper**.\n\n> Is it somehow unavoidable to denoise outputs in addition to concepts? If not unavoidable, did you try at any point in your exploration process to only use diffusion for the concepts? What were the limitations?\n\n**It is not unavoidable, but it makes the resulting algorithms more tricky.** If outputs are not denoised, they’d from a generative perspective only come in for completely clean data. This requires full simulation of the diffusion model during training, which is more akin to standard RL training in LLMs and diffusion. While this is theoretically possible, it is highly compute-intensive and has much a more challenging credit assignment problem: Ie, which of the many denoising steps were relevant to producing a good result? \n\n> How did you arrive at the RLOO estimator as a solution to computing ? As in, what was the reasoning process for trying this approach specifically?\n\n**RLOO is the simplest RL-based estimator to implement, really.** It scales well with number of samples, and is unbiased [1]. Recent work in RLHF also shows it is a great, simple alternative to, e.g., PPO [2] and it is closely related to (but simpler than) the currently very popular GRPO algorithm [3]. For more expensive symbolic programs, one could also consider LOOP [4], a combination of PPO and RLOO. We will add this discussion to our paper. \n\n1. Kool, Wouter, Herke van Hoof, and Max Welling. \"Buy 4 reinforce samples, get a baseline for free!.\" (2019).\n2. Schulman, J., Wolski, F., Dhariwal, P., Radford, A., & Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347.\n3. Shao, Z., Wang, P., Zhu, Q., Xu, R., Song, J., Bi, X., ... & Guo, D. (2024). Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300.\n4. Gupta, S., Ahuja, C., Lin, T. Y., Roy, S. D., Oosterhuis, H., de Rijke, M., & Shukla, S. N. (2025). A simple and effective reinforcement learning method for text-to-image diffusion fine-tuning. arXiv preprint arXiv:2503.00897."}, {"review_id": "SwwgOOaHN4", "reviewer": "Reviewer_cdKS", "summary": "The paper introduces Neurosymbolic Diffusion Models (NeSy-DMs), which combine discrete diffusion processes with symbolic reasoning to model dependencies between symbolic concepts more effectively. Unlike traditional NeSy models that assume conditional independence among concepts, NESYDMs leverage a denoising diffusion framework to sample structured symbolic predictions iteratively. This allows them to handle uncertainty better and generalize more robustly to ambiguous or out-of-distribution data. The authors provide a principled derivation of the training objective, along with a thorough theoretical analysis of its NELBO formulation. Experiments on visual reasoning and path-planning tasks demonstrate significant improvements in both accuracy and calibration.", "questions": "Given the weaknesses above, I would ask:\n\n- How would NESYDMs behave on tasks whose outputs are not easily factorised and whose programs lack a compilable circuit? A deeper discussion on this matter would clarify better the scope and the limitations of the approach.\n\n- How do the authors envision applying NESYDMs to reasoning-heavy tasks like visual question answering, where the symbolic structure is more complex and less explicit?\n\n- Since L_y , L_c , and L_H are critical to performance (L234), what is the effect of varying these weights? Can the authors provide ablation studies or sensitivity analysis?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The paper tackles the independence assumption flaw that limits existing NeSy predictors and presents a principled and theoretically grounded solution.\n\n- The paper proposes a theoretically grounded explanation of how the local independence assumption within diffusion steps balances scalability and expressiveness. A continuous-time NELBO is proved (Thm 3.1) and linked to masked diffusion losses, providing a solid learning objective\n\n- The paper is clear and well organized.\n\nWeaknesses:\n\n- The training objective (Eq. 5) requires either (i) a decomposable output space or (ii) a compiled circuit to evaluate weighted model counts. What would happen in tasks where neither is available? How do NESYDMs address such problems? \n\n- The experiments focus mostly on visual planning and rule-based driving. It would be beneficial for the paper if the authors discussed how NESYDMs could be used for further tasks that require reasoning, such as visual-question answering.\n\n- The loss-component weights are \"critical to the performance\" as reported by the authors in L234. The paper would benefit from ablation studies for the terms and the hyper-parameter sensitivity analysis of the components of the loss term.", "was_revised": true, "final_justification": "The authors provided a thorough explanation and conducted additional experiments that addressed my initial concerns. Their rebuttal was clear and responsive, and I recommend incorporating the new material into the manuscript. Based on this, I have increased my score.", "rebuttal": "We thank the reviewer for their helpful comments and feedback, and are glad they found our paper **clear and well-organized**. They believe NeSyDM is a **theoretically grounded solution** with a solid learning objective, while providing **significant experimental improvements**. \n\nThe reviewer had several important questions on the fit of NeSyDMs to other tasks and applications, which we discuss in our response below. They also gave the valuable suggestion to **include an ablation study for the weighting of our loss components**, which we ran and also provide below. We will add these clarifications and new results to our manuscript. \n\n> How would NESYDMs behave on tasks whose outputs are not easily factorised and whose programs lack a compilable circuit? A deeper discussion on this matter would clarify better the scope and the limitations of the approach.\n\n**Yes, this also is a challenge for _all_ our NeSy competitors. However, the strength of NeSyDM lies in its compatibility with approximate inference methods for WMC [1, 2].** So, if one has a problem for which a good WMC approximation is available, this can be directly applied in NeSyDM by updating the gradient estimation procedure. \n\nIn particular, we believe a significant scalability boost can be obtained by using pretrained models. For instance, Reinforcement Learning with Verifiable Rewards (RLVR) methods use pretrained LLMs that already have a large probability of obtaining a positive reward. Similarly, we can use pretrained diffusion models, such as LLADA or MMADA [3, 4], to bootstrap the learning process.\n\nWe will include this discussion in the camera-ready version. \n\n\n> How do the authors envision applying NESYDMs to reasoning-heavy tasks like visual question answering, where the symbolic structure is more complex and less explicit?\n\nIndeed, when the symbolic structure is not explicit, we have the additional challenge of predicting a suitable symbolic structure. **Luckily, this can be neatly integrated with NeSyDMs.** For instance, we can use a pretrained model (again, like LLADA or MMADA [3, 4]) that can already generate programs ($\\approx$symbolic structures). Then, we can evaluate the resulting program to predict the answer. If this aligns with the ground-truth answer, we can reinforce the probability of this program. This is similar to popular approaches like ViperGPT, VISPROG, Faithful CoT and Logic-LM [5-8], which can improve the quality of the generated program. We will include a discussion of this extension in our camera-ready.  \n\n> Since L_y , L_c , and L_H are critical to performance (L234), what is the effect of varying these weights? Can the authors provide ablation studies or sensitivity analysis?\n\n**Yes we can provide those, see below!** We ran the conditioned model NeSyDM_Cond with 3 repeated runs on MNISTHalf with various values of the entropy weight and concept unmasking weight to understand their effect on the various metrics. We will include these results and our analysis in our appendix. \n\nL234 is somewhat imprecise, we only experimented with the concept unmasking weight and the variational entropy weight, keeping the output unmasking weight to 1 (affected only by learning rate). We will update L234 and refer to the new appendix.\n\n| Concept unmasking weight | Label accuracy ↑  | Concept accuracy ↑| Label accuracy OOD ↑| concept accuracy OOD ↑ | ECE ID ↓ | ECE OOD ↓ |\n|------------------|------------|-----------|-------------|------------|----------|-----------|\n| 1e-08 | 99.38±0.27 | 70.45±2.32 | 33.92±5.10 | 65.13±2.72 | 8.54±4.46 | 12.23±1.18 |\n| 1e-07 | **99.61±0.13** | 71.41±0.72 | **37.16±1.22** | **67.74±0.56** | 7.77±1.09 | 10.67±0.98 |\n| 1e-06 | 99.54±0.80 | **72.88±0.85** | 33.21±7.06 | 64.86±3.92 | 5.31±1.19 | 11.00±0.87 |\n| 1.5e-06 (used) | 99.12±0.10 | 71.16±1.77 | 28.44±0.90 | 62.76±0.89 | 4.18±2.56                                      | 11.74±1.18 |\n| 1e-05 | 99.00±0.53 | 69.79±3.09 | 29.72±3.00 | 63.10±2.11 | 6.33±3.87 | 11.39±1.76 |\n| 0.0001 | 99.23±0.13 | 72.07±0.77 | 36.46±6.60 | 66.84±4.04 | 4.90±0.69 | **10.22±1.96** |\n| 0.001 | **99.61±0.13** | 72.03±0.84 | 32.75±6.51 | 64.60±4.44 | 4.98±3.15 | 10.46±2.86 |\n| 0.01 | 99.15±0.48 | 71.60±0.35 | 31.99±7.80 | 63.57±5.41 | **3.80±1.52** | 10.81±1.07 |\n| 0.1 | 99.46±0.35 | 71.88±0.81 | 36.76±8.27 | 66.85±5.05 | 6.96±2.35 | 12.35±4.01 |\n| 1.0 | 98.84±0.61 | 41.55±0.12 | 5.70±0.24 | 38.65±0.14 | 56.87±0.25 | 61.09±0.11 |\n| 10.0 | 99.38±0.13 | 41.59±0.13 | 5.64±0.19 | 38.59±0.19 | 57.00±0.23 | 60.97±0.08 |\n\n\nFor the output unmasking weight  $\\gamma_{\\mathbf{c}}$, we find that all test values achieve high label accuracy. However, its value significantly influences the concept accuracy both in-distribution and OOD, and the OOD label accuracy. We observe lower values (<1.0) are effective, which is in line with our observation on L947. We suspect the output unmasking loss can provide the model information that it is useful, but it should not dominate the loss, as this results in significantly lower concept accuracy and OOD performance, and very poor calibration. This suggests the model converged onto a single reasoning shortcut. \n\n| Entropy weight | Label accuracy ↑  | Concept accuracy ↑| Label accuracy OOD ↑| concept accuracy OOD ↑ | ECE ID ↓ | ECE OOD ↓ |\n|------------------|------------|-----------|-------------|------------|----------|-----------|\n| 0.001 | 99.15±0.13 | 41.63±0.07 | 5.61±0.16 | 38.63±0.03 | 57.05±0.12 | 61.08±0.16 |\n| 0.01 | 99.00±0.35 | 41.74±0.18 | 5.79±0.18 | 38.66±0.03 | 56.80±0.21 | 60.91±0.11 |\n| 0.1 | 98.77±0.48 | 41.67±0.12 | 5.61±0.32 | 38.60±0.23 | 56.98±0.26 | 60.97±0.09 |\n| 0.5 | 99.31±0.23 | 41.63±0.07 | 5.58±0.14 | 38.59±0.15 | 56.94±0.09 | 61.09±0.01 |\n| 1.0 | 99.23±0.13 | 41.63±0.13 | 5.85±0.14 | 38.73±0.12 | 56.90±0.25 | 61.06±0.09 |\n| 1.3 | **99.77±0.23** | 67.05±1.99 | **35.51±2.78** | **65.79±1.79** | 9.33±1.74 | 12.26±1.31 |\n| 1.6 (used)             | 99.12±0.10                        | 71.16±1.77                        | 28.44±0.90                                   | 62.76±0.89                                   | 4.18±2.56                                      | 11.74±1.18                                     |\n| 2.0 | 99.61±0.13 | **72.26±0.41** | 29.35±1.73 | 62.19±1.03 | **3.79±0.48** | **11.42±0.61** |\n| 3.0 | 89.81±5.84 | 46.53±2.50 | 17.03±8.97 | 51.23±7.03 | 12.70±5.87 | 14.56±2.71 |\n| 5.0 | 85.73±1.94 | 39.74±1.33 | 11.24±0.14 | 44.04±1.39 | 12.56±1.33 | 24.22±2.12 |\n| 10.0 | 85.73±0.35 | 34.22±1.27 | 10.81±0.19 | 41.25±1.03 | 15.40±2.25 | 24.01±1.56 |\n\nWe also observe a significant influence of the entropy weight $\\gamma_{\\text{H}}$. All values <1.3 seem to converge on a single reasoning shortcut, exhibiting very poor calibration and worse concept accuracy. These runs do not balance the maximisation of entropy as the weight is too low, resulting in models with low entropy. Increasing the entropy weight beyond the value we used (1.6), we find that this can also impact the performance (>2.0), resulting in reduced label and concept accuracy and calibration. As the optimal range of values is quite tight, we recommend tuning $\\gamma_{\\text{H}}$ (as mentioned in L949). \n\n**Citations**\n1. van Krieken, E., Thanapalasingam, T., Tomczak, J., Van Harmelen, F., & Ten Teije, A. (2023). A-nesi: A scalable approximate method for probabilistic neurosymbolic inference. Advances in Neural Information Processing Systems, 36, 24586-24609.\n2. De Smet, L., Sansone, E., & Zuidberg Dos Martires, P. (2023). Differentiable sampling of categorical distributions using the catlog-derivative trick. Advances in Neural Information Processing Systems, 36, 30416-30428.\n3. Nie, S., Zhu, F., You, Z., Zhang, X., Ou, J., Hu, J., ... & Li, C. (2025). Large language diffusion models. arXiv preprint arXiv:2502.09992.\n4. Yang, L., Tian, Y., Li, B., Zhang, X., Shen, K., Tong, Y., & Wang, M. (2025). Mmada: Multimodal large diffusion language models. arXiv preprint arXiv:2505.15809.\n5. Surís, D., Menon, S., & Vondrick, C. (2023). Vipergpt: Visual inference via python execution for reasoning. In Proceedings of the IEEE/CVF international conference on computer vision (pp. 11888-11898).\n6. Gupta, T., & Kembhavi, A. (2023). Visual programming: Compositional visual reasoning without training. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (pp. 14953-14962).\n7. Lyu, Q., Havaldar, S., Stein, A., Zhang, L., Rao, D., Wong, E., ... & Callison-Burch, C. (2023, November). Faithful chain-of-thought reasoning. In The 13th International Joint Conference on Natural Language Processing and the 3rd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics (IJCNLP-AACL 2023).\n8. Pan, L., Albalak, A., Wang, X., & Wang, W. Y. (2023). Logic-lm: Empowering large language models with symbolic solvers for faithful logical reasoning. arXiv preprint arXiv:2305.12295."}, {"review_id": "JvRjMNaMGe", "reviewer": "Reviewer_QdAB", "summary": "The paper introduces neurosymbolic diffusion models that are a novel class of neurosymbolic models based on diffusion process. The key contributions of these models is that they overcome the \"independence assumption\" and reuse the \"independence assumption\" from NeSy predictors at each step of deffusion process for scalable learning. The method shows close to SOTA performance on multiple synthetic datasets.", "questions": "I have mentioned my concerns and two main questions in the weakness section.", "limitations": "I think the limitations  are fairly addressed wrt the methodology proposed by the authors", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 1, "originality": 2, "strengths_and_weaknesses": "***Strengths:***\n\nNovel use of diffusion models in a NeSy setting\n\n***Weakness:***\n\n**Independence Assumption**\n\nMy main problem with the paper is statements like  *\"independence assumption haunting NeSy predictors....\"* can be misleading in my current understanding of the literature: Weighted Model Counting is fully expressive wrt any discrete distribution, given that one adds additional parameters and this is already addressed in the original paper on WMC [1], this is also true for Problog [2, Section 2.6].  Hence, I find the statement that NeSy predictors can not express something because of the \"independence assumption\" quite misleading, and infact \"independence assumption\" should more appropriately be called \"multiplicative parameterization\". The claim that, *\"The only maximisers of Eq. 1 for the independent model are to either deterministically return (0, 1) or (1, 0). However, there is no maximiser that can simultaneously assign probability mass to both cases, meaning independent models cannot be RS-aware\"*,  seems wrong to me. I demonstrate it in the following:\n\nIf you define $P_{\\theta}(c = (c_1,c_2))$ as a WMC distribution, by defining $w(c_i) = p_i$ if $c_i =1$ and $w(c_i) = 1-p_i$ if $c_i =0$, and \n\n$$P_{\\theta}(c = (c_1,c_2)) = \\frac{w_{1}(c_1)w_{2}(c_2)}{\\sum_{c' \\models y} w_{1}(c'_1)w_2(c'_2)}$$\n\n\nwhere $w(c_i) \\in [0,1]$, then for $ w_i = 0.5$ you get uniform distribution on (0,1) and (1,0) and this parameterization maximizes equation 1, infact equation 1 achieves the maximum value of 1, always with this equation. The only NeSy model in which Equation 1 actually reduces to only multiplicative weights with no partition function is semantic loss, and again semantic loss is essentially a regularizer which is trained with other loss terms. So it is not meaningful to analyze its expressivity in isolation.  If required, I can also provide a WCM reduction that is, it can express any possible distribution. \n\nInfact, theoretically WMC is already much more powerful than diffusion, if analyzed wrt Theorem C.1. As Theorem C.1 only guarentees full expressivity as $T \\rightarrow \\infty$ which in my understanding requires infinitely many parameters to be modeled. Whereas with WMC you can model any distribution on n discrete boolean random variables with $2^{n}-1$ parameters.  \n\nQuestion: Given that WMC and Problog are already fully expressive, with better bounds on the number of required parameters than what is proposed in the paper, then why should one use diffusion?\n\n**RS-Awareness**\n\nThis critique could be because of my general misunderstanding of the literature. However, it is not obvious to me that RS-awareness as measured by ECE is indeed a correct metric. Note that parameters in NeSy models are supposed to weight predictions in a way such that they agree with constraints and (as usual) maximize data likelihood. Whereas ECE, in literature, and in the paper is supposed to measure if the model's accuracy on a given concept is indeed same as the predicted confidence. \n\nQuestion: Can the authors show that these two notions,  RS-Awareness while maximizing data likelihood and constraint satisfaction, and ECE are mutually compatible or even consistent with each other?\n\n**Experiments**\n\nAs mentioned earlier, I am not sure of ECE is a meaningful metric in this setting. Now removing ECE, the experimental results for accuracy look quite mixed on the rather toy datasets (common in NeSy literature).\n\n\n[1] On probabilistic inference by weighted model counting 2008. Mark Chavira and Adnan Darwiche. \n\n[2] Foundations of Probabilistic Logic Programming. Fabrizio Riguzzi [Section 2.6]", "was_revised": true, "final_justification": "- The authors clarified my doubts about **independence assumption**.\n- **About the metric ECE,** I think the authors did give a reasonable justification for it on a toy example. However, it still does not stand as a clear proof for me. However, given that RS-awareness is only one of the multiple contributions of NesyDM, I lean towards acceptance. \n- My confidence remains 2, as although I am reasonably aware of NeSy literature, I am not so well-versed with Diffusion models, and some important aspects of the proposed model may have been missed by me.", "rebuttal": "We thank the reviewer for their valuable comments, and are glad they found our approach novel. \n\nThe reviewer wonders about the benefit of Neurosymbolic Diffusion Models (NeSyDMs) compared to increasing the number of parameters in weighted model counting (WMC). We highlight how NeSyDMs use neural networks that predict the same number of parameters as baseline SotA NeSy methods that independence over concepts. Instead, increasing the number of WMC parameters also requires larger neural networks. This allows it to **scale to more challenging reasoning problems**. The reviewer also asked for a motivation for the ECE measure in studying Reasoning Shortcut Awareness. We motivate this measure in this context and provide an example. **We will add both clarifications to our manuscript**, and provide detailed answers below.\n\n> Question: Given that WMC and Problog are already fully expressive, with better bounds on the number of required parameters than what is proposed in the paper, then why should one use diffusion?\n\n**The number of parameters is precisely our motivation**. We assume a fixed number of concepts, say $n$ binary variables. Over these, we assume conditional independence, predict parameters with a neural diffusion model from an input $\\mathbf{x}$, and estimate $n$ WMC parameters, as is standard in our baselines. One could alternatively increase the expressivity by introducing additional variables and changing the program. Then one can indeed achieve full expressivity at $2^{n}-1$ parameters. However, in NeSy one needs to predict these additional parameters with the neural network, significantly increasing the neural network size and training requirements. For full expressivity on our largest path planning task, our diffusion method requires a neural network that predicts only $5*900$ rather than $5^{900}-1$ parameters. We explain how to think of these numbers below.\n\n> Question: Can the authors show that these two notions, RS-Awareness while maximizing data likelihood and constraint satisfaction, and ECE are mutually compatible or even consistent with each other?\n\nCertainly! We understand RS-awareness as in BEARS [1]: we aim for high accuracy on concepts unaffected by reasoning shortcuts, while being calibrated on concepts that are affected; therefore, perfect concept accuracy is unattainable. A model which predicts concepts like this while mixing over reasoning shortcuts also maximises data likelihood. To measure calibration over ambiguous concepts, we use ECE. We provide a detailed example below. \n\n# Detailed response\n\n## Independence assumption\nThank you for the useful comments. We will clarify our understanding of this problem and highlight the benefit of using diffusion for NeSy. \n\n> Weighted Model Counting is fully expressive wrt any discrete distribution, given that one adds additional parameters\n\n**The reviewer is correct that WMC can be more expressive only by adding variables apart from those used to characterise concepts and changing the constraint.**\n- We understand independence in our paper as follows: given a fixed program and a fixed number of concepts, we define a factorised distribution over them (conditioned on the input $\\mathbf{x}$). In the graphical modelling literature, one would therefore say these concepts are conditionally independent.\n- By increasing the number of variables beyond those characterising concepts, we can indeed represent more flexible distributions over concepts than conditionally independent ones. This is an alternative to diffusion for increasing the expressivity beyond independence, which is done in eg SPL [1] (mentioned in paper). SPL cannot be directly applied to our setting where concepts are latent, and all NeSy baselines we compare against do not introduce these additional variables to make WMC more expressive. **As a matter of fact, all baselines we consider (except BEARS) assume concepts to be independent and hence are limited in expressiveness and uncertainty quantification**. \n- We agree that this possibility is not clearly highlighted in the paper; we will clarify this point in the camera-ready version.\n\nSecondly, the reviewer shows a parameterisation that attains the uniform distribution. Note that this parameterisation requires access to the label $y$ to compute the partition function. But in our NeSy setting, the model does not know what the label $y$ is at test time, as that is what the model needs to predict. Therefore, this particular parameterisation is not applicable here.\n\nIt is possible to have an unconditioned uniform WMC distribution when using three parameters; however, this would go beyond what we understand in our paper as the independence assumption.\n\nNow, since theoretically WMC can be fully expressive, why use diffusion? As the reviewer mentions, to attain increased expressivity via WMC, we need to increase the number of WMC parameters. However, consider our NeSy setting: these WMC parameters are predicted from the high-dimensional input $\\mathbf{x}$ using our neural network. So we would need to train a (potentially very large) neural network that predicts $2^n-1$ WMC parameters, which is certainly infeasible for the problems we study. For the largest path planning task in our experiments, this requires predicting $5^{900}-1$ WMC parameters for full expressivity. \n\nInstead, by having our neural network predict an independent distribution / multiplicative parameterisation, the network only needs to predict $5*900$ WMC parameters, creating a practically viable expressive parameterisation. \n\n> As Theorem C.1 only guarentees full expressivity as  $T\\rightarrow \\infty$ which in my understanding requires infinitely many parameters to be modeled\n\nIncreasing $T$ does **not** increase any requirements of parameter counts. $T\\rightarrow \\infty$, mentioned in Theorem C.1 refers to the number of diffusion timesteps, not number of parameters. We assume $T\\rightarrow \\infty$ (continuous-time diffusion) throughout our paper. \n\n## ECE validity\n> Question: Can the authors show that these two notions, RS-Awareness while maximizing data likelihood and constraint satisfaction, and ECE are mutually compatible or even consistent with each other?\n\n**We give an example of consistency.** Consider again the XOR problem, which has 1 reasoning shortcut (RS) that maps MNIST digits of 1s to 0s and MNIST digits of 0s to 1s. This RS cannot be distinguished from the ground-truth mapping. The ideal model under this ambiguity would assign 50% confidence to the ground-truth mapping and 50% to the RS. \n\nHow would one achieve this? Using a neural network that, 1) given two distinct MNIST digits outputs a uniform distribution over (0, 1) and (1, 0), and 2) given two equivalent MNIST digits, outputs a uniform distribution over (0, 0) and (1, 1). Then for case 1), running the XOR function returns 1 with probability 1, and for case 0), it will return 0 with probability 1. \n\nThis attains maximum data likelihood: The model will always return the correct output label. Furthermore, it always assigns 0.5 probability to 1 and 0. Its concept accuracy will also be ~0.5 in our synthetic setup. Therefore, the ECE will also be ~0, highlighting its calibration. \nInstead, a non RS-aware method finding the RS will attain an ECE of ~1: it always predicts exactly the opposite of the correct concept.\n\nFor concepts that are not affected by RSs, the accuracy will be 1 and maximum likelihood will also attain high confidence, resulting also in a low ECE value.\n\nNow, ECE is a proxy for measuring RS-awareness and also not the only / perfect metric for uncertainty quantification. A future study in the limitations of ECE for measuring RS-awareness could be of significant value, even if it is useful for the problems studied in this paper. We would be happy to add alternative metrics the reviewer suggests. \n\nWe will add a paragraph motivating the ECE measure in the appendix with this example included.\n\n1. Ahmed, K., Teso, S., Chang, K. W., Van den Broeck, G., & Vergari, A. (2022). Semantic probabilistic layers for neuro-symbolic learning. Advances in Neural Information Processing Systems, 35, 29944-29959."}]

Author rebuttal:

Meta-review: (a) This paper introduces Neuro-symbolic Diffusion Models (NESYDMs), a new class of NeSy predictors that drop the restrictive independence assumption while staying scalable. The key idea is to use discrete masked diffusion to model dependencies over symbolic concepts, while integrating the symbolic program directly into both the reverse process and the loss. The authors derive a continuous-time NELBO that incorporates a program-aware weighted model count term, and they prove a new result extending diffusion NELBOs to non-factorized unmasking distributions. Empirical results are demonstrated on hard reasoning problems including path planning and RSBench. 

(b) The derivation of a program-aware diffusion NELBO and the new theoretical extension to non-factorized joints is a clear and makes sense. The integration of symbolic programs directly inside the reverse process, variational posterior via constrained resampling, and gradient estimation via decomposed RLOO go beyond MDM + some penalty. The method outperforms baselines in high-dimensional reasoning (30×30 path planning) and improves calibration/RS-awareness on various datasets. 

(c) Personally I think the experimental results are okay but needs to demonstrate on more realistic and challenging reasoning problems, where it is difficult to solve the problem otherwise. Empirical validation is limited to RSBench and path-planning - broader real-world tasks are needed for wider impact. 

(d) The paper does address a fundamental independence assumption limitation of NeSy. So for everyone interested in this problem domain, the assumptions and experimental results should be interesting. 

(e) 
- One reviewer raised whether NeSyDMs truly add value beyond just scaling up weighted model counting with more parameters. The authors clarified that NeSyDMs predict the same number of parameters as standard NeSy baselines, but can scale to larger reasoning problems without requiring exponentially larger neural networks

- A second concern was about using ECE as the measure for reasoning-shortcut awareness. The authors gave a concrete example showing how calibration reflects whether probability mass is spread correctly over ambiguous concepts.

- There were also two side issues: one reviewer flagged potential AI-assistance in a review (handled separately, no impact on this paper), and another noted they weren’t an expert in this area, which limited their feedback but didn’t affect the consensus.
Decision: Accept (poster)