Embeddings as Probabilistic Equivalence in Logic Programs

We sincerely thank the reviewer for taking the time to review our paper and providing useful feedback.

There are no experiments to compare the training efficiency of the different approaches.

Our experiments indeed focus on accuracy improvements, rather than runtime performance. However, the runtimes of our experiments are generally faster than those of baselines, such as DeepSoftLog. For example, for the Countries S3 runs, the runtime was on average two hours per experiment, while for DeepSoftLog, this was five hours. Moreover, DeepSoftLog cannot handle e.g. the Nations experiment, due to scalability issues.

How does this new learning algorithm compare to DeepSoftLog on some of its scalability benchmarks, especially since this work is directly building on it? I would have liked to see a comparison for MNIST-Addition and Visual Sudoku.

The MNIST-addition and Visual Sudoku experiments are less interesting in our setting as they are ground problems over linear arithmetic. Furthermore, the MNIST-addition encoding of DeepSoftLog does not fully use soft unification. So performing this experiment using our approach would give functionally identical results to DeepSoftLog.

We have included experiments beyond the scalability limits of DeepSoftLog, namely on the Nations knowledge graph. Below, we furthermore repeated this last experiment on two other knowledge graphs (UMLS and Kinship), which are further out of reach for DeepSoftLog.

Define “symbol” upfront. I have seen some neurosymbolic literature that uses “symbol” to mean the likely discrete neural network prediction. But this paper is using it to mean the name of a rule.

In our context, a symbol is a constant in a Datalog program (i.e. an element of the Herbrand universe, see the second paragraph of Section 2). The outputs of a neural network can indeed be used as a distribution over symbols for a neurosymbolic model . In our work, however, symbols are embedded into a vector space.

Other than isIn/locatedIn, what are other examples of equivalences that were exploited in the evaluated benchmarks, resulting in performance improvements?

Another example is in the differentiable finite state machine experiment, where symbols represent states in an automaton. Now, consider the following transitions between states: $a\rightarrow b$, $c\rightarrow d$, and $e\rightarrow f$. Assuming we have that $b=c$ and $c=e$, it should be possible to transition $a\rightarrow b (=c) \rightarrow d$ and $a\rightarrow b (=e) \rightarrow f$. However, the latter derivation cannot be found without transitivity. Table 3 demonstrates that the more faithful modelling of automata behaviour has major performance implications. More generally, this problem is encountered in any task where true equivalence is present (in this example, automata states).

What do the authors see as the real-world application of this work? How does this work fit in with foundation models, which could likely eliminate the need for training the neural network?

Although our contribution is on the more fundamental side, we hope that it will enable future applications where symbolic and neural structures are jointly optimized, leading to models with interpretable reasoning traces that are critical in highly regulated domains (e.g., finance). Moreover, neurosymbolic models can provide formal guarantees about their behaviour, as previously demonstrated on applications with safety requirements (e.g., self-driving [1] or language model toxicity [2]).

Foundation models have indeed altered the conventional machine learning paradigm, but still face limitations in these aspects. Furthermore, there are still questions about how far out-of-distribution foundation models can perform compositional reasoning (as a symbolic model can). For example, Yue et al. [3] argue that the currently popular RL-trained reasoning models do not fundamentally expand their capabilities beyond the pre-training distribution, and Hazra et al. [4] argue that foundation models still struggle with computationally hard inferences.

[1] Giunchiglia, Eleonora, et al. "ROAD-R: the autonomous driving dataset with logical requirements." Machine Learning (2023).
[2] Ahmed, Kareem, Kai-Wei Chang, and Guy Van den Broeck. "A pseudo-semantic loss for autoregressive models with logical constraints." NeurIPS (2023).
[3] Yue, Yang, et al. "Does reinforcement learning really incentivize reasoning capacity in LLMs beyond the base model?." ICML AI4Math workshop (2025).
[4] Hazra, Rishi, et al. "Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition. COLM (2025).

We sincerely thank the reviewer for their feedback and taking the time to review our paper.

In particular, the crux of argument about the deficiencies of the embeddings-based in approach in lines 150-155 was lost on me. I’d like to see the notion of “global optimum” to be better explained there. [...] Can you elaborate “even though in the global optimum we have P_f (y \sim z)=0.” in line 155?

We have reworked Section 3.1 to improve clarity and accessibility to a broader audience. The overall goal of Section 3.1 is to show that using soft unification with embeddings is problematic, motivating the need for our new semantics. From the optimization perspective, it is well-known that marginals of probabilistic logic (or indeed any distribution over discrete variables) are multilinear polynomials (see e.g. [1] or [2]). This implies all optima are global, making it relatively easy to optimize neurosymbolic models based on probabilistic logic. However, by using soft unification, the model is no longer multilinear in the parameters (e.g., the embeddings), and local optima may appear. This problem was already noticed by [3]. Example 7 was an indication of this, where following the gradient moves you away from the global optimum. We have replaced the old Example 7 with the following to demonstrate these ideas more explicitly, without needing a program with rules.

Example 7. Consider a soft unification program where embeddings are compared using a radial basis function, as done by the Neural Theorem Prover [4]. In other words, $P_f(a\approx b) =\phi(d(a,b))$, where $d(a,b)$ is the distance between the constants $a$ and $b$ in the embedding space and $\phi$ is a monotone function, typically a Gaussian. Suppose now that we have a query whose probability is given by $(1 - P_f(a \approx b)) (1 - P_f(a \approx c))(1 - P_f(b \approx c)) + P_f(a \approx b) P_f(a \approx c)(1 - P_f(b \approx c)) + P_f(a \approx b)) P_f(b \approx c)(1 - P_f(a \approx c))$. Under the probabilistic semantics, the probabilities $P_f(\dots)$ are free parameters and hence this multilinear polynomial only has global optima. However, when soft unification is parameterized by embeddings, the probability of the query is computed by $(1-\phi(d(a,b))) (1-\phi(d(a,c)))(1-\phi(d(b, c)))+\phi(d(a, b)) \phi(d(a, c))(1-\phi(d(b , c)) + \phi(d(a, b))) \phi(d(b,c))(1-\phi(d(a, c)))$. This has a local maximum (e.g., using $\phi(x) = e^{-10x^2}$), because the vector space constrains the distances: $\vert d(a, b) - d(b, c)\rvert \leq d(a, c) \leq d(a, b) + d(b, c)$.

[1] Darwiche, Adnan. "A differential approach to inference in Bayesian networks." JACM (2003).
[2] Roth, Dan, and Rajhans Samdani. "Learning multi-linear representations of distributions for efficient inference." Machine Learning (2009).

In the proposed approach every constant also has an embedding. Can you elaborate the difference in how embeddings are used in your work and in the prior similarity-based approaches?

Both our work and previous research associate embeddings with symbols. However, we differ in the logic semantics associated with these embeddings. For example, what does it mean for the symbol $\mathtt{stop}$ of a logic formula $\mathtt{redlight} \rightarrow \mathtt{stop}$ to have an embedding $[0.130, 0.341, 0.023, …]$? Prior work, in particular, soft unification, compared symbols in the embedding space to assess how likely it is for two symbols to be "equivalent". On the other hand, we see embeddings as a latent random variable in a distribution over programs (see also Figure 1).

I'd like to see more discussion on whether inference/learning becomes harder with the proposed approach compared to prior work.

We have added some more discussion on these questions in Section 5. (On inference) Firstly, from a basic complexity view, nothing changes: inference is still #P-hard. Furthermore, elementary ground queries (such as whether two atoms are equal) remain tractable through our choice of factorization (c.f. Section 4.1). In practice, the most substantial difference of enforcing transitivity for exact inference is that the size of the ground program may increase. We partially mitigate this by using singularization and magic program transforms (c.f. Section 5). (On Learning) As optimization in our approach is multilinear and does not contain local optima, learning is easier compared to prior methods (c.f. the previous discussion about Sec. 3.1). For example, the NTP baseline uses 100 epochs for the experiments of Table 2, while we only need 1 epoch to converge.

We sincerely thank the reviewer for taking the time to review our paper and providing useful feedback.

While the proposed work is more general, the experiments enforce a single rule of transitivity. [...] Is there a reason why only transitivity was chosen within the experiments. Of course, it is true that transitivity occurs more naturally in real-world cases, but perhaps it would have helped to demonstrate enforcing other constraints.

The experiments use logic programs that may include dozens of rules, not just a transitive constraint (see Appendix B). Our work focuses on transitive equivalence because its importance has not yet been established in the context of differentiable proving and rule learning. Imposing such transitivity in an efficient fashion is nontrivial and required rethinking the prevailing probabilistic semantics of logic programming.

In more general cases, is the proposed learning method scalable? It seems like the singularization to be performed for exact weighted model counting will be computationally expensive.

Singularization itself is a very efficient program transformation step that can be done in linear time in the number of rules. On the other hand, the weighted model counting step is #P-hard, and hence faces scalability limitations. Notice that the latter is a challenge faced by every sufficiently expressive probabilistic programming language, and we have an approximation technique (c.f. lines 240-250) to keep the experiments reasonably fast.

Regarding the comparison as such, it seemed to me like the proposed “exact” inference/learning method is being compared to approximate soft unification methods. In that sense, the approximate inference methods seem to be doing reasonably well it looked like in the graph benchmark at least.

We are not sure we understand this point. Both our experiments as well as all the baselines use approximate inference (c.f. lines 240-250 for our approximation strategy). Indeed, exact inference is #P-hard in the size of the ground program (which can grow very quickly due to the use of templates in the experiments) and hence usually not feasible.

For the factorization, in the experiments, it is mentioned that the embedding dimension is as large as the vocabulary. This would seem like a limiting factor for many practical cases as such. What happens with a smaller embedding, I assume the distribution will not be expressive enough. But maybe this trade-off is important to address through some empirical results.

Setting the embedding dimensionality to the vocabulary size can indeed become problematic for large programs. However, in these cases one can just take a smaller embedding dimension. If expressivity is a concern, the parameter count can be increased independently of vocabulary size with hierarchical mixtures without affecting tractability. In our experiments, the embedding dimensionality never was an issue, which is why we did not explore it further.

If the embeddings are approximate (i.e. does not have dimensionality of the full vocabulary), does the proposed method reduce to other existing approximate approaches of soft unification using similarity?

No, it does not. The embeddings are only approximate in the sense that they limit the potential distributions over equivalence relations (in favour of tractability for certain queries). Further restricting expressivity by reducing the embedding dimensionality has no impact on the semantics. More specifically, transitivity is always guaranteed, and hence there cannot be a reduction to soft unification (which violates transitivity).

We sincerely thank the reviewer for their feedback and taking the time to review our paper. We have split our answer into the two main points of concern.

Concerning Section 3.1. (Equivalence vs Soft Unification)

Section 3.1 was somewhat difficult for me to follow. [...] Ensuring that this section is extremely clear to audiences with ranging understandings (i.e., not just experts) of neuro-symbolic methods, probabilistic logic programming, etc. would be a massive improvement.

To address this concern, we reworked Section 3.1 to provide more discussion and make it more accessible. As we cannot upload a new pdf, we summarize the main points below before moving to the specific questions.

The overall goal of Section 3.1 is to show that using soft unification with embeddings is problematic, motivating the need for our new semantics. First, there is the optimization perspective. It is well-known that marginals of probabilistic logic (or indeed any distribution over discrete variables) are multilinear polynomials (see e.g. [1] or [2]). This implies all optima are global, making it relatively easy to optimize neurosymbolic models based on probabilistic logic. However, by using soft unification, the model is no longer multilinear in the parameters (e.g., the embeddings), and local optima may appear. This problem was already noticed by [3]. Example 7 was an indication of this, where following the gradient moves you away from the global optimum. We have replaced the old Example 7 with the following to demonstrate these ideas more explicitly, without needing a program with rules.

Example 7. Consider a soft unification program where embeddings are compared using a radial basis function, as done by the Neural Theorem Prover [4]. In other words, $P_f(a\approx b) =\phi(d(a,b))$, where $d(a,b)$ is the distance between the constants $a$ and $b$ in the embedding space and $\phi$ is a monotone function, typically a Gaussian. Suppose now that we have a query whose probability is given by $(1 - P_f(a \approx b)) (1 - P_f(a \approx c))(1 - P_f(b \approx c)) + P_f(a \approx b) P_f(a \approx c)(1 - P_f(b \approx c)) + P_f(a \approx b)) P_f(b \approx c)(1 - P_f(a \approx c))$. Under the probabilistic semantics, the probabilities $P_f(\dots)$ are free parameters and hence this multilinear polynomial only has global optima. However, when soft unification is parameterized by embeddings, the probability of the query is computed by $(1-\phi(d(a,b))) (1-\phi(d(a,c)))(1-\phi(d(b, c)))+\phi(d(a, b)) \phi(d(a, c))(1-\phi(d(b , c)) + \phi(d(a, b))) \phi(d(b,c))(1-\phi(d(a, c)))$. This has a local maximum (e.g., using $\phi(x) = e^{-10x^2}$), because the vector space constrains the distances: $\vert d(a, b) - d(b, c)\rvert \leq d(a, c) \leq d(a, b) + d(b, c)$.

A second perspective is the Bayesian one. Consider three symbols $a$, $b$, and $c$. There exists no embedding of those symbols that satisfies the following nontransitive probabilities: $P(\mathsf{a} \approx \mathsf{b}) = 1$, $P(\mathsf{b} \approx \mathsf{c}) = 1$, and $P(\mathsf{a} \approx \mathsf{c}) = 0$. Indeed, to satisfy the previous probabilities, the symbols $a$, $b$, and $c$ need to map to the same elements in the embedding space, implying an inherent transitivity (c.f. Theorem 2). Since, this nontransitive property cannot be represented by embeddings, by assigning mass to these probabilities, i.e., by setting $P(\mathsf{a}\approx\mathsf{b})=1$, $P(\mathsf{b} \approx \mathsf{c})=1$, and $P(\mathsf{a} \approx \mathsf{c})=0$, we leak probability mass, adversely impacting uncertainty quantification.

[1] Darwiche, Adnan. "A differential approach to inference in Bayesian networks." JACM (2003).
[2] Roth, Dan, and Rajhans Samdani. "Learning multi-linear representations of distributions for efficient inference." Machine Learning (2009).
[3] de Jong, Michiel, and Fei Sha. "Neural theorem provers do not learn rules without exploration." (2019).
[4] Rocktäschel, Tim, and Sebastian Riedel. "End-to-end differentiable proving." NeurIPS (2017).

I don't really see how theorem 2 supports the paper's main contribution of showing that soft unification does not adhere to the laws of equivalence.

The fact that soft unification does not adhere to transitivity (one of the laws of equivalence) is known and follows from its Definition (see lines 140-148). In contrast, Theorem 2 relates to why it is problematic not to adhere to transitivity (see the previous discussion on the Bayesian perspective).

What exactly is bad about requiring embeddings to be equal?

Requiring embeddings to be equal is definitely not a problem on its own. However, doing so on the probabilistic level without enforcing the same structure in the logic semantics is what leads to issues (see the previous discussion about Section 3.1).

I am unclear what exactly you are referring to by "nontransitive possible worlds" on line 156 and 161. Are they the "possible worlds not in an equivalence relation" mentioned on line 148? This makes Theorem 2 very unclear to me.

With nontransitive possible world, we mean a possible world $w$ of the soft unification program $\mathcal{P}_{soft}$ where transitivity does not hold. For example, a possible world with $a \approx b$ and $b \approx c$ but not $a \approx c$.

I assume a negative fact is a falsehood, e.g., $a \neq b$? This should be defined.

Yes, we will define this in the text.

The notation $e$ and $e’$ to denote equivalence relations in the Herbrand Universe and Base, respectively, was somewhat difficult for me to keep track of.

We will modify this notation to $e_\mathsf{U}$ and $e_\mathsf{B}$, respectively.

Concerning Experiments on Transitivity

I don't feel that the description of the experiments clearly address the research question "does transitivity matter". [...] While the improvements of your method over the baselines in the experiments are an indicator that enforcing transitivity is helpful, I feel that additional experimentation or analysis would be helpful to support your claim. That is, just reporting higher AUCs is insufficient. Can you describe the extent to which each of these tasks depends on transitivity?

The DeepSoftLog baseline is essentially an ablation of our method where transitivity is not enforced. So the (considerable) performance improvements over this baseline can be attributed to the addition of transitivity.

Can you provide example failures of the other models that are caused by a lack of transitivity?

An example is in the differentiable finite state machine experiment, where the symbols represent states in an automaton. Consider the following transitions between states: $a\rightarrow b$, $c\rightarrow d$, and $e\rightarrow f$. Assuming we have that $b=c$ and $c=e$, it should be possible to transition $a\rightarrow b (=c) \rightarrow d$ and $a\rightarrow b (=e)\rightarrow f$. However, the latter derivation cannot be found without transitivity. This is the reason why DeepSoftLog often fails to optimize and has a large variance between experiments (c.f. Table 3).

Better yet, is it possible to, for example, quantify the number of links in experiment 1 that require rule learning in order to be predicted correctly?

In the Countries (Table 1) and differentiable automata (Table 3) experiments, rules are necessary in each query. In other words, without rule learning, the performance would be near random. In the Nations knowledge graph (Table 2), this is less drastic – hence also the more modest performance improvements.

Paper Formatting Concerns

Typos have been fixed. Regarding line 150, $x$ is an element of the Herbrand universe, while $X$ is a variable.