Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Differentiable Reasoning

Soft logic, neural theorem provers and their limits.

Make every truth value a number between 0 and 1 and logic becomes differentiable: a knowledge base turns into a loss, a proof into a computation graph, and backpropagation can learn rules, symbol embeddings and perception together. The price shows up as gradients that point the wrong way, proof searches that explode, and networks that satisfy the rules for the wrong reasons.

What you’ll learn

  • Define t-norms and residuated implications, state the Mostert–Shields classification, and derive the gradients of the standard quantifier aggregators.
  • Explain soft unification in neural theorem provers and differentiable forward chaining in ∂ILP, with their costs.
  • Express probabilistic logic programs and the semantic loss as weighted model counts, and show why exact inference is #P-hard.
  • Define reasoning shortcuts, construct one, and prove that digit addition admits none.

Real-valued logic, precisely

A universally quantified rule ∀x φ(x)\forall x\,\varphi(x) is grounded on every constant, giving truth values t1,…,tnt_1,\dots,t_n, and then aggregated. The aggregator decides which groundings learn.

DerivationGradients of the three aggregators
  1. A=∏iti,∂A∂tj=∏i≠jti,∂log⁡A∂tj=1tjA=\prod_it_i,\qquad \frac{\partial A}{\partial t_j}=\prod_{i\ne j}t_i,\qquad \frac{\partial\log A}{\partial t_j}=\frac1{t_j}

    Product. Each grounding's gradient is the product of all the others, which vanishes for large nn: with n=100n=100 and every ti=0.9t_i=0.9 it is 0.999≈3×10−50.9^{99}\approx3\times10^{-5}. Implementations therefore often maximize the logarithm, whose gradient is 1/tj1/t_j.

  2. A=min⁡iti,∂A∂tj=1[j=arg min⁡iti]A=\min_it_i,\qquad \frac{\partial A}{\partial t_j}=\mathbb 1\Big[j=\argmin_it_i\Big]

    Gödel. Only the worst grounding receives any gradient, so each step teaches one example.

  3. A=max⁡(0, ∑iti−(n−1)),∂A∂tj=1[∑iti>n−1]A=\max\Big(0,\ \sum_it_i-(n-1)\Big),\qquad \frac{\partial A}{\partial t_j}=\mathbb 1\Big[\textstyle\sum_it_i>n-1\Big]

    Łukasiewicz. All groundings learn, but only once the average truth exceeds 1−1/n1-1/n; below that the aggregate is stuck at 00 with zero gradient.

  4. Ap(t1,…,tn)=1−(1n∑i=1n(1−ti)p)1/pA_p(t_1,\dots,t_n)=1-\Big(\frac1n\sum_{i=1}^n(1-t_i)^p\Big)^{1/p}

    Logic Tensor Networks (Badreddine et al., 2022) use a generalized mean of the errors instead, which interpolates between the arithmetic mean (p=1p=1) and the minimum (p→∞p\to\infty):

In Logic Tensor Networks, constants are embedding vectors, predicates are neural networks with outputs in [0,1][0,1], connectives are fuzzy operators and quantifiers are such means; training maximizes the aggregated truth of the whole knowledge base. The implication's gradient imbalance from the Hidden Layer applies here in full: when most groundings have a false antecedent and a false consequent, most of the signal flows into denying antecedents.

Differentiable proving: NTPs and ∂ILP

Neural theorem provers (Rocktäschel & Riedel, 2017) run Prolog-style backward chaining, but unification of two symbols succeeds softly, with a score k(θa,θb)∈(0,1]k(\boldsymbol\theta_a,\boldsymbol\theta_b)\in(0,1] given by a radial basis function kernel on their embeddings. So grandpaOf\mathit{grandpaOf} can unify with grandfatherOf\mathit{grandfatherOf}. A proof scores the minimum of its unification scores, and a query the maximum over its proofs. Rule templates such as p(X,Y)⇐q(X,Z)∧r(Z,Y)p(X,Y)\Leftarrow q(X,Z)\land r(Z,Y) with trainable predicate embeddings learn rules that can be read off by nearest neighbors.

The catch is that soft unification never fails outright, so every subgoal branches over every fact and rule head, and the number of proofs grows exponentially with depth. NTPs were limited to small knowledge bases; greedy variants keep only the kk nearest facts per subgoal (Minervini et al., 2020), which makes larger knowledge bases tractable at the price of exactness.

∂ILP (Evans & Grefenstette, 2018) learns definite programs from positive and negative examples. It generates every clause allowed by a program template, gives each predicate it must define a softmax distribution over its candidate definitions (pairs of clauses), and runs TT steps of differentiable forward chaining on a valuation vector that holds a truth value for every ground atom. The loss is the cross-entropy between the final values of the example atoms and their labels.

DerivationOne soft forward-chaining step
  1. at+1(x,y)=at(x,y) ⊕ w max⁡z[par(x,z)⋅at(z,y)]a_{t+1}(x,y)=a_t(x,y)\ \oplus\ w\,\max_z\big[\mathit{par}(x,z)\cdot a_t(z,y)\big]

    Take the candidate clause anc(X,Y)⇐par(X,Z)∧anc(Z,Y)\mathit{anc}(X,Y)\Leftarrow\mathit{par}(X,Z)\land\mathit{anc}(Z,Y) with weight ww. Conjunction is a product, the existential variable ZZ is a maximum, and new conclusions merge with old ones by the probabilistic sum u⊕v=u+v−uvu\oplus v=u+v-uv:

  2. u,v∈{0,1}⟹u⊕v=u∨vu,v\in\{0,1\}\quad\Longrightarrow\quad u\oplus v=u\lor v

    With w=1w=1 and every value in {0,1}\{0,1\}, this is exactly one round of crisp forward chaining, so TT steps derive every atom with a derivation of depth at most TT. Between 0 and 1 the step is differentiable (almost everywhere, because of the maximum) in ww and in the input values.

  3. time per step=O(∣C∣ n3),memory=O(∣C∣ n2)\text{time per step}=\order{|\mathcal C|\,n^3},\qquad \text{memory}=\order{|\mathcal C|\,n^2}

    The cost is the grounding. A binary predicate over nn constants has n2n^2 ground atoms, and each step takes a maximum over nn values per atom and per clause in the candidate set C\mathcal C:

∂ILP learned recursive programs and, unlike classical ILP, tolerated mislabeled examples, but its memory restricted it to small domains, tens of constants rather than thousands. Both systems show the general trade: making a symbolic procedure differentiable means running all of its branches at once, with weights.

Probabilistic logic as weighted model counting

Systems avoid enumerating worlds by knowledge compilation: they compile λq\lambda_q into a d-DNNF or SDD circuit, on which the weighted count and its gradient take time linear in the circuit's size (Darwiche & Marquis, 2002). The exponential cost moves into compilation, and appears only on hard instances. DeepProbLog lets neural networks supply the pip_i, for example a digit classifier's softmax for the fact digit(img,d)\mathit{digit}(\mathit{img},d), and backpropagates through the circuit. The semantic loss −log⁡WMC(α;p)-\log\mathrm{WMC}(\alpha;\mathbf p) uses the same machinery for a constraint α\alpha on a network's outputs.

DerivationWhere the semantic loss pushes
  1. W(p)=p1(1−p2)(1−p3)+(1−p1)p2(1−p3)+(1−p1)(1−p2)p3W(\mathbf p)=p_1(1-p_2)(1-p_3)+(1-p_1)p_2(1-p_3)+(1-p_1)(1-p_2)p_3

    For "exactly one of three", the weighted model count is a polynomial in the output probabilities:

  2. ∂W∂p1=(1−p2)(1−p3)−p2(1−p3)−(1−p2)p3\frac{\partial W}{\partial p_1}=(1-p_2)(1-p_3)-p_2(1-p_3)-(1-p_2)p_3

    Differentiate, say, in p1p_1; the other two partials are symmetric:

  3. ∇p(−log⁡W)=−∇WW≈(−0.15, 0.56, 0.56)\nabla_{\mathbf p}\big(-\log W\big)=-\frac{\nabla W}{W}\approx(-0.15,\ 0.56,\ 0.56)

    At p=(0.6,0.3,0.3)\mathbf p=(0.6,0.3,0.3), W=0.462W=0.462 and ∇W=(0.07,−0.26,−0.26)\nabla W=(0.07,-0.26,-0.26). Descending −log⁡W-\log W raises the leading class and lowers the others: the loss pushes toward a confident, constraint-satisfying prediction without any label, which is why it helps semi-supervised learning.

Reasoning shortcuts, and the frontier

A pipeline y=K(fθ(x))y=K\big(f_\theta(x)\big) maps inputs to concepts with a network fθf_\theta and concepts to labels with fixed knowledge KK, and is trained on (x,y)(x,y) pairs only. A reasoning shortcut is a concept map that attains optimal label likelihood while assigning unintended concepts (Marconato et al., 2023). It exists whenever KK has a non-trivial symmetry on the training support, as in the smallest example below.

Check your understanding

Which change does not help against the XOR shortcut above?

  1. Labeling the concepts of a few training images
  2. Adding a second task whose knowledge depends on AA alone
  3. Training longer on the same (x,y)(x,y) pairs
  4. Adding a reconstruction objective that ties concepts to input features
Show the answer

C. Training longer on the same (x,y)(x,y) pairs

The inverted concept map already achieves optimal label likelihood, so more optimization on the same supervision cannot prefer the intended one. A few concept labels, knowledge that breaks the symmetry, or objectives that tie concepts to the input do change which maps are optimal.

Key takeaways

  • T-norms extend the Boolean connectives, and every continuous one is an ordinal sum built from Łukasiewicz, product and minimum (Mostert–Shields). Their aggregators differ sharply: products vanish, minima are sparse, Łukasiewicz sums saturate.
  • Neural theorem provers make backward chaining differentiable through soft unification, at the price of exponentially many proofs; ∂ILP makes forward chaining differentiable at a cost of order ∣C∣ n3|\mathcal C|\,n^3 per step.
  • ProbLog, DeepProbLog and the semantic loss compute weighted model counts: exact, differentiable through compiled circuits, and #P-hard in general.
  • Reasoning shortcuts arise from symmetries of the knowledge: XOR is invariant under joint negation, so labels cannot identify its concepts, while digit addition identifies every digit.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A rule is grounded on 1,000 constants and aggregated with the Gödel minimum. With no ties, how many groundings receive gradient in one step?

  1. All 1,000
  2. One
  3. None, until the average truth exceeds 0.9990.999
  4. About half
Show the answer

B. One

∂min⁡iti/∂tj\partial\min_it_i/\partial t_j is 1 for the minimizing grounding and 0 for every other, so each step improves only the currently worst example.

Question 2

Why can exact inference in ProbLog or DeepProbLog take exponential time in the worst case?

  1. Because neural networks are slow to evaluate
  2. Because definite clauses are undecidable
  3. Because gradients cannot be computed through logic programs
  4. Because query probabilities are weighted model counts, which are #P-hard, so compiling them into circuits can blow up
Show the answer

D. Because query probabilities are weighted model counts, which are #P-hard, so compiling them into circuits can blow up

P(q)=WMC(λq)P(q)=\mathrm{WMC}(\lambda_q), and even probabilistic reachability (network reliability) is #P-complete. Compiled circuits make counting linear in their size, but the circuits can be exponentially large.

Question 3

A network maps each image to concepts (A,B)(A,B) and is trained only on labels Y=A⊕BY=A\oplus B. Which concept map also reaches zero training loss?

  1. (¬A,¬B)(\neg A,\neg B)
  2. (¬A,B)(\neg A,B)
  3. (A,A)(A,A)
  4. None: the labels identify the concepts
Show the answer

A. (¬A,¬B)(\neg A,\neg B)

¬A⊕¬B=A⊕B\neg A\oplus\neg B=A\oplus B for all inputs, so inverting both concepts preserves every label. This is a reasoning shortcut.

Question 4

Why do neural theorem provers scale poorly with the depth of proofs?

  1. Their kernels are not differentiable
  2. Soft unification never fails, so every subgoal branches over all facts and rule heads, and proofs multiply exponentially with depth
  3. They require the knowledge base to be in CNF
  4. They can only represent propositional rules
Show the answer

B. Soft unification never fails, so every subgoal branches over all facts and rule heads, and proofs multiply exponentially with depth

Hard unification prunes most branches at once; soft unification gives every branch a small positive score, so the prover must keep them all. Greedy variants restore pruning by keeping only the nearest facts.

Further reading

  • R. Evans & E. Grefenstette, "Learning explanatory rules from noisy data," Journal of Artificial Intelligence Research 61, 1–64 (2018).
  • T. Rocktäschel & S. Riedel, "End-to-end differentiable proving," NeurIPS (2017).
  • S. Badreddine, A. d'Avila Garcez, L. Serafini & M. Spranger, "Logic Tensor Networks," Artificial Intelligence 303, 103649 (2022).
  • J. Xu, Z. Zhang, T. Friedman, Y. Liang & G. Van den Broeck, "A semantic loss function for deep learning with symbolic knowledge," ICML (2018).
  • E. Marconato, S. Teso, A. Vergari & A. Passerini, "Not all neuro-symbolic concepts are created equal: Analysis and mitigation of reasoning shortcuts," NeurIPS (2023).