🤖 AI

A homotopy-type-theoretic generalization of neurosymbolic inference

This paper proposes a homotopy type theory framework for neurosymbolic inference that generalizes traditional set-based approaches to account for structural symmetries and proof multiplicities, thereby resolving reasoning shortcuts and improving calibration through a symmetry-invariant, closed-form averaging method.

Original authors: Fernando Zhapa-Camacho, Robert Hoehndorf

Published 2026-06-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Fernando Zhapa-Camacho, Robert Hoehndorf

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a computer to understand a logical puzzle, like a detective solving a mystery. The computer has two parts: a "neural" part that guesses probabilities (like "I think the butler did it with 70% confidence") and a "symbolic" part that knows the rules of logic (like "The butler can only be the killer if he was in the library").

Usually, when these two parts work together, the computer makes a mistake called a "reasoning shortcut."

The Problem: The "Mirror" Trap

Think of a room with two identical twins, Alice and Bob. The computer is asked: "Is someone in the room?"

Scenario A: Alice is there, Bob is not.
Scenario B: Bob is there, Alice is not.

To the computer's logic, these are two different answers. But to the rules of the game, they are the exact same situation because Alice and Bob are interchangeable. The computer doesn't know they are interchangeable, so it treats them as two separate, distinct possibilities. It might get confused, thinking, "Oh, there are two ways this could happen, so I should be very confident," or it might pick one twin arbitrarily and ignore the other.

This is the "shortcut": the computer learns to guess the right answer for the wrong reason, by latching onto a specific detail (like "Alice") that isn't actually important, just because it happened to see that detail during training.

The Solution: A New Way to Count

The authors of this paper propose a mathematical upgrade. Instead of treating the computer's world as a simple list of items (a "set"), they treat it as a map of connections (a "type" from Homotopy Type Theory).

Here is the analogy:

The Old Way (Sets): Imagine you are counting people in a room. You see Alice and Bob. You count "1, 2." You don't care that they look alike or that swapping them changes nothing about the room's vibe. You just count heads.
The New Way (Types/Homotopy): Imagine you are counting people, but you also have a "symmetry meter." If Alice and Bob are identical twins, the meter realizes that swapping them doesn't create a new situation; it's the same situation seen from a different angle.
- In this new math, a situation with a lot of symmetry (like the twins) counts as less than a situation with no symmetry. It's like saying, "Because there are two ways to arrange these twins, this specific arrangement only counts as half a person."

This new method is called Belief-Weighted Homotopy Cardinality. It's a fancy way of saying: "Count the possibilities, but give a discount to any possibility that is just a mirror image of another one."

The Magic Trick: Orbit-Averaging

The paper shows that by using this new math, you can fix the "reasoning shortcut" problem without needing to train a whole army of different computers (ensembles) or complex density models.

They introduce a technique called Orbit-Averaging.

The Analogy: Imagine you have a blurry photo of a face. Instead of trying to guess which specific person it is, you take the photo, spin it around in every possible way that looks the same (rotating the twins), and take the average of all those views.
The Result: The computer stops guessing "It's Alice!" or "It's Bob!" and instead says, "It's one of the twins, and I'm equally unsure which one." It becomes calibrated. It knows when it is guessing and when it is certain.

What They Found

The authors tested this on a task where the computer had to recognize digits (0–9) but was told to group them (e.g., 1 and 2 are the same category).

The Old Computer: Got the group right but was overconfident about which specific digit (1 or 2) it saw, even though it couldn't tell them apart.
The New Computer (Orbit-Averaging): Got the group right, kept the same accuracy, but correctly admitted, "I can't tell 1 from 2, so I'm 50/50."

Why This Matters

It's a Single Model: You don't need to train five different versions of the AI and combine them (which is slow and expensive). You can take one model and apply this mathematical "filter" to fix its confidence.
It's Exact: The math proves that this method is the only way to be perfectly fair when things are symmetrical.
It's General: This works for any logic system where things can be swapped without changing the outcome, not just for the specific digit examples they tested.

In short, the paper says: "Stop counting possibilities like a simple list. Start counting them like a symmetrical dance, where swapping partners doesn't change the dance. If you do this, your AI will stop lying to you about how sure it is."

Technical Summary: A Homotopy-Type-Theoretic Generalization of Neurosymbolic Inference

Problem Statement
Current neurosymbolic (NeSy) systems largely rely on a unified functional defined as a belief-weighted sum of a logical quantity over a space of $\sigma$ -structures (assignments of values to logical symbols). This functional, often instantiated as weighted model counting (WMC), probabilistic logic, or fuzzy logic, operates on sets. The authors argue that sets are "deliberately forgetful" objects that discard two critical pieces of information essential for structured NeSy:

Symmetry: They fail to distinguish between $\sigma$ -structures that are identical up to a symmetry of the theory (e.g., swapping interchangeable individuals). Consequently, the standard functional overcounts symmetric structures.
Proof Multiplicity: They collapse multiple distinct derivations witnessing a query into a single number, ignoring the "how many ways" a fact is proven.

This decategorification leads to a specific failure mode known as reasoning shortcuts. When a model is trained only on logical outputs, it may converge to a perception that assigns the wrong meaning to latent concepts (a "shortcut") while preserving the output. Standard methods struggle to identify the correct "shortcut-aware" posterior (a uniform distribution over the confusion set of equivalent concepts) without resorting to complex ensembling or expressive density estimation.

Methodology
The paper proposes replacing the underlying sets of NeSy inference with types from Homotopy Type Theory (HoTT). In this framework, a type remembers not just its elements, but the ways in which elements can be identified (isomorphisms).

The authors "lift" the four ingredients of the standard NeSy functional (Eqn. 1) one level up:

Structure Space ( $\Omega$ ): Replaced by a type where identity types record symmetries (renamings of individuals). The classical set of structures is the 0-truncated case.
Logic Function ( $\ell$ ): Replaced by a proof family $P: \Omega \to \mathcal{U}$ . The truncation level of $P$ is a design parameter: a proposition (level -1) checks satisfaction; a set (level 0) counts derivations; a groupoid (level 1) identifies symmetric derivations.
Inference: Replaced by belief-weighted homotopy cardinality. Instead of a simple sum, the inference value is computed as:
$N(P, b) = \left\| \sum_{\omega:\Omega} P(\omega) \right\|_{V,b}$
This counts each element weighted by the reciprocal of its symmetry group size ($1/|Aut(x)|$), ensuring that symmetric structures contribute less than asymmetric ones.
Valuation: The choice of commutative semiring (e.g., $(+, \times)$ for probability, $(\max, +)$ for tropical) determines which numerical invariant is read from the homotopy cardinality.

Key Contributions

Theoretical Framework: The authors formalize NeSy inference as a belief-weighted homotopy cardinality. This framework introduces two explicit parameters absent in classical formulations: a symmetry parameter (defining the group of allowed renamings) and a truncation level (defining the granularity of proof tracking).
Conservativity Theorem: A machine-checked theorem (verified in Lean 4) proves that when symmetries are trivial (the group is identity) or the semiring is idempotent, the homotopy cardinality collapses exactly to the classical set-based functional. This ensures the new framework is a faithful generalization.
Reasoning Shortcuts as Orbits: The paper identifies the "confusion set" (the set of concept assignments yielding the same output) as an orbit under the symmetry group of the theory.
- The "shortcut-aware" concept posterior is identified as the unique symmetry-invariant point: the uniform distribution over the orbit.
- This leads to Orbit-Averaging, a closed-form method to compute this posterior:
  $\bar{p}(c | x) = \frac{1}{|G|} \sum_{g \in G} p_\theta(g^{-1} \cdot c | x)$
  This method symmetrizes a single base model over the output-preserving group $G$ without requiring an ensemble or density estimation.
Generating Functions: For exchangeable models, the framework naturally yields exponential generating functions (via homotopy cardinality) rather than ordinary generating functions, aligning with the theory of combinatorial species.

Experimental Results
The authors evaluated the orbit-averaging method on MNIST reasoning-shortcut benchmarks (specifically tasks with known symmetry groups and ground truth for concept identifiability).

Setup: A single neural network was trained to predict merged labels. The task involved distinguishing between identifiable digits (orbit size 1) and confusable digits (orbit size > 1).
Comparison: The single-model orbit-averaged wrapper was compared against a base model and a diversity-trained 5-model ensemble (Bears).
Findings:
- The base model was overconfident on confusable digits (high Expected Calibration Error, ECE).
- Orbit-averaging reduced the ECE on confusable digits from 0.614 to 0.010 while preserving label accuracy and the calibration of identifiable concepts.
- The diversity-trained ensemble achieved similar calibration improvements only by sacrificing label accuracy or miscalibrating identifiable concepts, highlighting a trade-off that the single-model orbit-averaging avoids.

Significance and Claims
The paper claims that reading NeSy inference through the lens of HoTT provides a "concrete payoff" by exposing the symmetry structure responsible for reasoning shortcuts.

Theoretical Unification: It unifies various NeSy approaches (probabilistic, fuzzy, provenance) under a single decategorified view of a richer, structured object.
Practical Efficiency: It demonstrates that the "shortcut-aware" posterior, previously thought to require expensive ensembling, can be computed in closed form by averaging a single model over the symmetry group.
Calibration: The method improves calibration on unidentifiable concepts without degrading performance on identifiable ones, solving a specific failure mode of NeSy learning.
Limitations: The authors note that the current framework relies on finite types ( $\pi$ -finiteness). Extending homotopy cardinality to continuous domains via "cohesion" remains an open problem.

The work is presented as a foundational shift from set-based to type-based reasoning, where the "forgetfulness" of sets is replaced by the structural memory of types, directly addressing the root causes of reasoning shortcuts.