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 is grounded on every constant, giving truth values , and then aggregated. The aggregator decides which groundings learn.
Product. Each grounding's gradient is the product of all the others, which vanishes for large : with and every it is . Implementations therefore often maximize the logarithm, whose gradient is .
Gödel. Only the worst grounding receives any gradient, so each step teaches one example.
Łukasiewicz. All groundings learn, but only once the average truth exceeds ; below that the aggregate is stuck at with zero gradient.
Logic Tensor Networks (Badreddine et al., 2022) use a generalized mean of the errors instead, which interpolates between the arithmetic mean () and the minimum ():
In Logic Tensor Networks, constants are embedding vectors, predicates are neural networks with outputs in , 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 given by a radial basis function kernel on their embeddings. So can unify with . A proof scores the minimum of its unification scores, and a query the maximum over its proofs. Rule templates such as 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 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 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.
Take the candidate clause with weight . Conjunction is a product, the existential variable is a maximum, and new conclusions merge with old ones by the probabilistic sum :
With and every value in , this is exactly one round of crisp forward chaining, so steps derive every atom with a derivation of depth at most . Between 0 and 1 the step is differentiable (almost everywhere, because of the maximum) in and in the input values.
The cost is the grounding. A binary predicate over constants has ground atoms, and each step takes a maximum over values per atom and per clause in the candidate set :
∂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 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 , for example a digit classifier's softmax for the fact , and backpropagates through the circuit. The semantic loss uses the same machinery for a constraint on a network's outputs.
For "exactly one of three", the weighted model count is a polynomial in the output probabilities:
Differentiate, say, in ; the other two partials are symmetric:
At , and . Descending 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 maps inputs to concepts with a network and concepts to labels with fixed knowledge , and is trained on 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 has a non-trivial symmetry on the training support, as in the smallest example below.
Which change does not help against the XOR shortcut above?
- Labeling the concepts of a few training images
- Adding a second task whose knowledge depends on alone
- Training longer on the same pairs
- Adding a reconstruction objective that ties concepts to input features
Show the answer
C. Training longer on the same 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 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.
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?
- All 1,000
- One
- None, until the average truth exceeds
- About half
Show the answer
B. One
is 1 for the minimizing grounding and 0 for every other, so each step improves only the currently worst example.
Why can exact inference in ProbLog or DeepProbLog take exponential time in the worst case?
- Because neural networks are slow to evaluate
- Because definite clauses are undecidable
- Because gradients cannot be computed through logic programs
- 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
, and even probabilistic reachability (network reliability) is #P-complete. Compiled circuits make counting linear in their size, but the circuits can be exponentially large.
A network maps each image to concepts and is trained only on labels . Which concept map also reaches zero training loss?
- None: the labels identify the concepts
Show the answer
A.
for all inputs, so inverting both concepts preserves every label. This is a reasoning shortcut.
Why do neural theorem provers scale poorly with the depth of proofs?
- Their kernels are not differentiable
- Soft unification never fails, so every subgoal branches over all facts and rule heads, and proofs multiply exponentially with depth
- They require the knowledge base to be in CNF
- 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).