🤖 machine learning

Concise and Logically Consistent Conformal Sets for Neuro-Symbolic Concept-Based Models

This paper introduces COCOCO, a post-hoc conformal prediction framework that jointly generates concise, logically consistent, and coverage-guaranteed sets for Neuro-Symbolic Concept-Based Models by reconciling concept and label predictions through a single deduction-abduction revision step.

Original authors: Samuele Bortolotti, Emanuele Marconato, Andrea Pugnana, Andrea Passerini, Stefano Teso

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Samuele Bortolotti, Emanuele Marconato, Andrea Pugnana, Andrea Passerini, Stefano Teso

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 have a very smart, two-part robot assistant designed to solve complex puzzles. This robot is a Neuro-Symbolic Concept-Based Model (NeSy-CBM).

Here is how it works:

The "Eye" (Neural Network): First, the robot looks at a messy picture (like a photo of a street or a medical scan) and tries to identify the high-level objects in it. It says, "I see a car, a dog, and a tree." These are its concepts.
The "Brain" (Symbolic Logic): Then, the robot uses a set of strict rules (like "a car has wheels" or "if you add 7 and 6, you get 13") to figure out the final answer. It says, "Based on what I see, the answer must be 13."

The Problem: The Overconfident Robot
The problem is that this robot is often overconfident. Even when it is wrong, it speaks with 100% certainty.

Example: Imagine the robot looks at a picture of a dog and a horse. Because of a glitch in its training, it confidently decides the dog is actually a "cat" and the horse is a "cow." It then uses its logic rules to conclude the answer is "Farm Animal." It gets the final answer right by accident, but its reasoning is completely broken.
In high-stakes situations (like medical diagnosis or self-driving cars), we need to know when the robot is unsure so we can double-check its work. But right now, the robot doesn't know it's guessing; it just thinks it's right.

The Solution: COCOCO
The authors introduce a new method called COCOCO (which stands for Conformality, Consistency, Conciseness). Think of COCOCO as a safety net and a logic-checker that you put over the robot's head.

Instead of giving you a single answer, COCOCO gives you a list of possible answers (a "prediction set"). It promises: "I guarantee that the true answer is in this list with 90% certainty."

But COCOCO does something special that other safety nets don't do. It ensures two things:

Consistency (The Logic Check): It makes sure the list of objects the robot "saw" matches the list of answers it gave.
- Analogy: If the robot's list of answers includes "13," but the list of objects it saw (7 and 5) can only make "12," COCOCO says, "Wait, that doesn't add up!" It removes "13" from the list and fixes the object list to match the math. It forces the robot's "Eye" and "Brain" to agree with each other.
Conciseness (The Size Limit): A safety net that says "The answer could be anything from 0 to 100" is useless. COCOCO tries to keep the list as short as possible while still being safe. It cuts out the impossible options so the list is short enough for a human to actually read.

How It Works (The "Revision" Step)
COCOCO uses a clever trick called a Revision Step.

It starts with a list of possible answers from the robot's "Brain."
It starts with a list of possible objects from the robot's "Eye."
It asks: "Which objects can actually make the answers in the first list?" and "Which answers can actually be made by the objects in the second list?"
It cross-references them and throws out anything that doesn't fit. It does this just once, and it's mathematically proven to be the perfect, most efficient way to clean up the lists.

Why This Matters
The paper tested this on 8 different datasets (including medical X-rays, restaurant reviews, and math problems with digits).

The Result: COCOCO successfully kept the robot's predictions honest. It ensured that the robot's "Eye" and "Brain" always agreed (Consistency), kept the list of possibilities small enough to be useful (Conciseness), and still guaranteed that the true answer was inside the list (Coverage).
The Comparison: Other methods tried to fix just the "Brain" or just the "Eye," but they failed. They either gave lists that were too long to read, or lists where the objects and answers didn't match up. COCOCO was the only one that fixed both problems at the same time.

In a Nutshell
COCOCO is a tool that takes a smart but overconfident AI, wraps it in a safety net, and forces it to double-check its own work. It ensures that if the AI says "The answer is X," it also admits "I saw Y and Z that make X possible," and it keeps the list of possibilities short enough for a human to trust and use.

Technical Summary: Concise and Logically Consistent Conformal Sets for Neuro-Symbolic Concept-Based Models

Problem Statement

Neuro-Symbolic Concept-based Models (NeSy-CBMs) integrate neural networks for concept extraction with symbolic reasoning for task inference, aiming to produce reliable AI systems for high-stakes applications. However, these models often suffer from overconfidence and miscalibration, making it difficult for stakeholders to assess the reliability of their predictions. Furthermore, even when uncertainty is quantified, the resulting probabilities can be unintuitive for end-users.

Existing approaches to uncertainty quantification in NeSy-CBMs often fail to satisfy three critical desiderata simultaneously:

Consistency: Predicted concepts and labels must be logically consistent with the user-specified prior knowledge ( $K$ ).
Coverage: Prediction sets must provide distribution-free, finite-sample marginal coverage guarantees for both concepts and labels.
Conciseness: Prediction sets must be as small as possible to remain interpretable and operationally useful.

Current "one-sided" conformal prediction (CP) strategies (e.g., applying CP only to labels or only to concepts) or asymmetric revision methods fail to meet all three criteria, often resulting in sets that are either inconsistent, lack coverage guarantees on one side, or are prohibitively large.

Methodology: COCOCO

The authors introduce COCOCO (COnformality, COnsistency, COnciseness), a post-hoc framework designed to transform any trained NeSy-CBM into a conformal predictor satisfying all three desiderata.

Core Mechanism

COCOCO operates in two stages:

Joint Conformalization: It independently constructs a conformal prediction set for labels ( $\Upsilon_\alpha(x)$ ) and a conformal prediction set for concepts ( $\Gamma_\beta(x)$ ) using standard CP techniques. For concepts, it leverages the conditional independence of concept extractors to construct a product set, or utilizes e-values to avoid Bonferroni corrections and control set size.
Deduction-Abduction Revision: The framework applies a single, joint revision step to reconcile the two sets. This step involves:
- Deduction: Filtering the label set to retain only labels entailed by the concept set ( $\Upsilon_{rev} = \Upsilon_\alpha \cap g^\dagger(\Gamma_\beta)$ ).
- Abduction: Filtering the concept set to retain only concepts that entail at least one label in the label set ( $\Gamma_{rev} = \Gamma_\beta \cap g^{-\dagger}(\Upsilon_\alpha)$ ).

Theoretical Guarantees

One-Step Fixed Point: The authors prove that a single application of this joint revision operator is sufficient to reach a fixed point. Iterating the process is unnecessary, ensuring computational efficiency.
Optimality: The resulting pair $(\Gamma_{rev}, \Upsilon_{rev})$ is the largest possible subset of the original sets that maintains mutual logical consistency.
Coverage under Imperfect Knowledge: The framework retains distribution-free coverage guarantees. In cases where the inference layer is imperfect (e.g., due to incomplete knowledge or reasoning shortcuts), the coverage lower bound degrades linearly based on the soundness of the inference layer ( $\delta_{ab}$ and $\delta_{de}$ ).
User-Specified Size Budgets: By integrating conformal e-predictions (using e-values instead of quantiles), COCOCO allows users to specify maximum set sizes (budgets) while adaptively selecting miscoverage levels ( $\tilde{\alpha}, \tilde{\beta}$ ) to maintain coverage guarantees in expectation. This approach avoids the degradation of guarantees as the number of concepts increases.

Key Contributions

Formalization of Desiderata: The paper defines and formalizes consistency, coverage, and conciseness as the necessary conditions for conformal NeSy methods.
COCOCO Framework: A novel post-hoc framework that jointly conformalizes concepts and labels and reconciles them via a single deduction-abduction step.
Theoretical Proofs:
- Proof that COCOCO satisfies all three desiderata by construction.
- Proof that the revision step reaches a fixed point in one iteration.
- Derivation of coverage bounds that account for imperfect knowledge and joint failure probabilities.
Size Control: Demonstration of how e-values enable user-specified size budgets without compromising coverage guarantees.
Extensive Empirical Evaluation: Evaluation on 8 datasets (including medical imaging, text, and image classification) using two state-of-the-art NeSy architectures (DeepProbLog and Logic Tensor Networks).

Experimental Results

Experiments on 8 datasets (CHX, CEB, RIV10, MN-Add variants, CIF10) demonstrate that COCOCO outperforms natural baselines and the strongest competitor (RPB):

Consistency: COCOCO achieves 1.00 concept and label consistency across all datasets. In contrast, competitors like RPB often exhibit significant inconsistency on the concept side (e.g., dropping to 0.12 on the MN-EO dataset).
Conciseness: COCOCO significantly reduces prediction set sizes compared to baselines. For instance, on the CEB dataset, it reduced the concept set size from 75.06 (RPB) to 53.49, and on MN-EO, it reduced the size from 100.00 (RPB) to 12.13, while maintaining full consistency.
Coverage: While COCOCO trades a small amount of coverage (typically 7–10 percentage points lower than RPB on the concept side) to guarantee consistency and conciseness, it maintains high label coverage (often $\ge 0.87$ ) and concept coverage ( $\ge 0.83$ ) at the nominal 0.9 target.
Robustness: The method performs robustly even under incomplete knowledge (RIV10) and reasoning shortcuts (MN-EO), where the theoretical bounds correctly predict the degradation in coverage.
Runtime: The computational overhead of COCOCO is modest (approximately 1.2x to 1.6x the baseline runtime), as the revision step requires only a single pass of abductive and deductive image computation.

Significance and Claims

The paper claims that COCOCO is the first method to simultaneously exploit symbolic knowledge to shrink conformal prediction sets and enforce label-concept consistency while retaining distribution-free coverage.

The authors position COCOCO as a critical step toward making NeSy-CBMs suitable for decision-support systems in high-stakes domains (e.g., medical diagnosis), where stakeholders require not just a prediction, but a set of plausible, logically consistent alternatives with rigorous statistical guarantees. The framework addresses the "black box" nature of uncertainty in NeSy models by providing interpretable sets that respect domain constraints, thereby enhancing trust and reliability without requiring retraining of the underlying neural-symbolic model.