A homotopy-type-theoretic generalization of neurosymbolic inference
Fernando Zhapa-Camacho, Robert Hoehndorf
cs.AI
Jun 16, 2026 · v2
cs.LO
TL;DR
The conservativity theorem, orbit-uniform posterior, and generating-function results are formalized in Lean 4 over Mathlib via orbit–stabilizer arithmetic, with no sorry.
Abstract
A wide range of neurosymbolic (NeSy) systems compute one functional: a belief-weighted sum of a logical quantity over a space of $σ$-structures, of which weighted model counting, fuzzy logic, and probabilistic logic are special cases. This account is built on sets, and a set deliberately forgets two things that are important for NeSy: when two $σ$-structures are the same up to a symmetry of the theory, and how many distinct proofs witness a query. Types, in the sense of homotopy type theory, preserve this information and turn the functional into a belief-weighted homotopy cardinality, a notion of size that counts each object in inverse proportion to its symmetries. We develop the framework from scratch for NeSy systems, prove a conservativity theorem that recovers the classical functional when symmetries are trivial, and show that the symmetry our framework exposes is exactly the one behind reasoning shortcuts. The payoff is concrete: the shortcut-aware concept posterior that recent methods reach by ensembling or expressive density estimation is the only symmetry-invariant point of the confusion-set simplex, computable in closed form by averaging a single model over the symmetry group. On MNIST reasoning-shortcut benchmarks this single-model wrapper is better calibrated than a diversity-trained ensemble, while leaving label accuracy and identifiable concepts untouched. Code is freely available at
https://github.com/bio-ontology-research-group/hott-nesy.
Problem
Many neurosymbolic inference systems compute a belief-weighted sum over a set of σ-structures. Sets forget two things: symmetries between structures and the multiplicity of proofs witnessing a query. The symmetry information is what underlies reasoning shortcuts.
Approach
Sets are replaced by homotopy types, so inference becomes a belief-weighted homotopy cardinality of a dependent sum of proof families, with semiring choice as the decategorification. A conservativity theorem recovers the classical functional when symmetries are trivial. The symmetry is identified with reasoning shortcuts, and the shortcut-aware posterior is derived as the unique symmetry-invariant point, computed by averaging a single model over the group. The finite, 1-truncated theorems are machine-checked in Lean 4 with Mathlib.
Results
The orbit-averaged single model matches the base model's label accuracy and lowers confusable-digit calibration error. It is better calibrated than RS-independence, NeSyDM and Bears ensembles on MNIST reasoning-shortcut tasks. The Lean development compiles with only standard axioms and no sorry.
| method | label | id-ECE | conf-ECE | conf-ent. |
|---|
| base | 0.996 | 0.002 | 0.588 | 0.05 |
| ours (orbit-avg.) | 0.996 | 0.004 | 0.013 | 0.94 |
| RS-independence | 0.995 | 0.004 | 0.054 | 0.94 |
| NeSyDM (40 ep.) | 0.997 | 0.002 | 0.021 | 0.93 |
| Bears (best fair) | 0.997 | 0.007 | 0.102 | 0.91 |
MNIST label-merging reasoning-shortcut task (selected rows)