Shortcuts and Identifiability in Concept-based Models from a Neuro-Symbolic Lens
Authors: Samuele Bortolotti
Emanuele Marconato
Paolo Morettin
Andrea Passerini
Stefano Teso
Venue: NeurIPS 2025 poster ()
Keywords: Concept-based models
Neuro-Symbolic AI
Identifiability
Shortcuts
Primary area: other
TL;DR: We analyze formally and empirically shortcuts arising in concept-based models

Abstract: Concept-based Models are neural networks that learn a concept extractor to map inputs to high-level concepts and an inference layer to translate these into predictions. Ensuring these modules produce interpretable concepts and behave reliably in out-of-distribution is crucial, yet the conditions for achieving this remain unclear. We study this problem by establishing a novel connection between Concept-based Models and reasoning shortcuts (RSs), a common issue where models achieve high accuracy by learning low-quality concepts, even when the inference layer is fixed and provided upfront. Specifically, we extend RSs to the more complex setting of Concept-based Models and derive theoretical conditions for identifying both the concepts and the inference layer. Our empirical results highlight the impact of RSs and show that existing methods, even combined with multiple natural mitigation strategies, often fail to meet these conditions in practice.

Shortcuts and Identifiability in Concept-based Models from a Neuro-Symbolic Lens
Samuele Bortolotti'
Emanuele Marconato" DISI, University of Trento Italy emanuele marconnttoouitnn.it
DISI, University of Trento Italy samuele. bortolotti@unita.
Paolo Morettin
Andrea Passerini DISI, University of Trento Italy andrea passeriniQunte it
DISI, University of Trento Italy
paolo. morettinnunitaa
Stefano Teso
CIMeC and DISI, University of Trento Italy
stefano. teso@unitn.it
Abstract
Concept-based Models are neural networks that learn a concept extractor to map inputs to high-level concepts and an inference layer to translate these into predic- tions. Ensuring these modules produce interpretable concepts and behave reliably in out-of-distribution is crucial, yet the conditions for achieving this remain unclear. We study this problem by establishing a novel connection between Concept-basse Models and reasoning shortcuts (RSs), common issue where models achieve high accuracy by learning low-quality concepts, even when the inference layer is fixed and provided upfront. Specifically, extend RSs the more complex setting Concept-base based Models and derive theoretical conditions for identifying both the concepts and the inference layer. Our empirical results highlight the impact of RSs and show that existing methods, even combined with multiple natural mitigation strategies, often fail meet these conditions in practice.
1 Introduction
Concept-based Models (CBMs) are broad class of self-explainable classifiers [1, 2, 4, 6, 7] designed for high performance and ante-hoc interpretability. Learning a CBM involves solving two conjoint problems: acquiring high-level concepts describing the input (e.g., image) and an inference layer that predicts a label from them. In many applications, is essential that these two elements are "high quality", in the sense that: i) the concepts should be interpretable, doing so compromises understanding [8, 9] and steerability [10, 11], both key selling points CBMs; and ii) the concepts and inference layer should behave well also out distribution (OOD), e.g., they should not pick up spurious correlations between the input, the concepts and the output [12, 13, 14].
failure in
This raises the question of when CBMs acquire "high-quality" concepts and inference layers. While existing studies focus on concept quality [15, 16, 17], they neglect the role of the inference
Equal contribution. Correspondence samuele. bortolotti@uiiitt
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

7
7 2
7 Z
7 2
1
NN'
B
odd
NN
B
odd
NN
B
odd
2
y (G + (2) mod? 2
y = (q +
(2) mod 2
y (c c2)
Figure 1: Joint reasoning shortcuts. The goal is to predict whether the sum of two MNIST digits is odd (as in Example 2.1) from training set of all possible unique (even, even), (odd, odd), and (odd, even) pairs of MNIST digits. Green elements are fixed, purple ones are learned. Left: ground-truth concepts and inference layer. Middle: NeSy-CBMs with given knowledge can learn reasoning shortcuts, i.e., concepts with unintended semantics. Right: CBMs can learn joint reasoning shortcuts, i... both concepts and inference layer have unintended semantics.
layer altogether. contrast, we cast the question in terms of whether it possible to identify from data concepts and inference layers with the intended semantics, defined formally in Section 3.1. We proceed to answer this question by building a novel connection with reasoning shortcuts (RSs), well-known issue in Veuro-Symboli (NeSy) AI whereby models achieve high accuracy by learning low-quality concepts even if the inference layer is fixed [18, 19, 20, 21J. For instance, a NeSy model for autonomous driving whose inference layer encodes the traffic laws might confuse pedestrians with red lights, as both entail the same prediction (the car has to stop) [22]. We generalize RSs to CBMs in which the inference layer is learned, and concept supervision may be absent. Our analysis shows that shortcuts can be exponentially many, even more than RSs, (we count them explicitly in Appendix B.5) and that maximum likelihood training is insufficient for attaining intended semantics. This hinders both interpretability and OOD behavior. On the positive side, we also specify conditions under which (under suitable assumptions) CBMs cannot be fooled by RSs, proving that the ground-truth concepts and inference layer can be identified (see Theorem 3.9).
Our evaluation on several learning tasks suggest that CBMs can be severely impacted by reasoning shortcuts in practice, as expected, and also that the benefits of popular mitigation strategies do not carry over to this more challenging problem. These results cast doubts the ability of these models to identify concepts and inference layers with the intended semantics unless appropriately nudged.
In summary, we: (i) generalize reasoning shortcuts to the challenging case of CBMs whose inference layer is learned (Section 3.1), (ii) study conditions under which maximum likelihood training can identify good concepts and inference layers (Section 3.2), and (iii) present empirical evidence that well-tested mitigations fail in this challenging setting (Section 5).
Contributions:
2 Preliminaries
Concept-based Models (CBMs) first map the input x R" into k discrete categorical concepts = (CI...., .k) C via a neural backbone, and then infer labels white-box layer, e.g., linear layer. This setup makes easy to figure out what concepts are most responsible for any prediction, yielding form of ante-hoc concept-based interpretability. Several architectures follow this recipe, including approaches for converting black-box neural networks into CBMs [23, 24, 25, 26].
) from this using
key issue is how to ensure the concepts are interpretable. Some CBMs rely on concept annotations [3, 27, 4, 5, 28, 29]. These are however expensive to obtain, prompting researchers to replace them with (potentially unreliable [30, 31)) annotations obtained from foundation models [32, 33, 34. 35] or unsupervised concept discovery [1, 2, 6, 36].
Neuro-Symbolic CBMs (NeSy-CBMs) specialize CBMs to tasks in which the prediction y y ought to comply with known safety or structural constraints. These are supplied as a formal specification - logic formula K, aka knowledge tying together the prediction y and the concepts c. In NeSy-CBMs, the inference step is a symbolic reasoning layer that steers [37, 38, 39] or guarantees [40, 41, 42, 43, 44] the labels and concepts to be logically consistent according K. Throughout, we will consider this example task:
Given two MNIST digits [45], wish to predict whether their sum is even or odd. The numerical values of the two digits can be modelled as concepts C E {O....,9) 2 and the inference layer is entirely determined by the prior knowledge: K = ((y
Example 2.1

---

1) + (C1+CC) ) is odd). This specifies that the label E {0,1} ought to be consistent with the predicted concepts C. See Fig. 1 for an illustration.
Like CBMs, NeSy-CBMs are usually trained via maximum likelihood and gradient descent, but without concept supervision. The reasoning layer is typically imbued with fuzzy [46] probabilistic [47] logie semantics to ensure differentiability. Many NeSy-CBMs require to be provided upfront, as in Example 2.1, hence their inference layer has no learnable parameters. Starting with Section 3, we will instead consider NeSy-CBMs that just like regular CBMs learn the inference layer
[48, 49, 50, 51, 52].
2.1 Reasoning Shortcuts
Before discussing reasoning shorteuts, we need to establish a clear relationship between concepts.
inputs, and labels. The RS literature does so by assuming the following data generation process
[19, [9]] 53]: each input E IR" is the result of sampling ground-truth concepts g = (9), ..... 9t. E
G (e.g., in MNIST-SumParity two numerical digits) from an unobserved distribution p (G) and
then x itself (e.g.. two corresponding MNIST images) from the conditional distribution p" (X g).
Labels y E y are sampled from the conditional distribution of g given by p" g: K) consistently with K (e.g., y = 1 if and only 91 + 92 is odd). The ground-trun truth distribution is thus:
px(X Y) (G)(" (X| g)r" (Y g; K)]
Intuitively, a reasoning shortcut (RS) occurs when NeSy-CBM with fixed knowledge K attains high or even perfect label accuracy by learning concepts C that differ from the ground-trui ones G.
Example 2.2. In Sumaarty, a NeSy model can achieve perfect accuracy by mapping each pair of MNIST images x (x1xX) X2) to the corresponding ground- truth digits, that is, c = -91.92). However, would achieve the same accuracy if were map it to с = (g1 mod 2, 92 mod 2). as doing so leaves the parity of the sum unchanged, see Fig. 1. Hence, NeSy model cannot distinguish between the two based on label likelihood alone during training.
RSs by definition yield good labels in-distribution, yet they compromise out-of oittt---distiiutiion (OOD) performance. For instance, in autonomous driving tasks, NeSy-CBMs of "pedestrian" and "red light", leading to poor decisions for OOD decisions where the distinction matters [22]. The meaning of concepts affected by RSs is unclear, affecting understanding [8], intervenability [54, 55, 56). debugging [57, 14] and down-stream applications that hinge on concepts being high-quality, like NeSy formal verification [58, 59, 60]. Unfortunately, existing works on RSs do not apply to CBMs and NeSy-CBMs where the inference layer is learned.
confuse the concepts
As commonly done, we work in the setting with equal discrete predicted C and ground-truth G concept sets, i.e., 9 = C [19, 21J. Notice that, we make no assumption on how the set 9 is made; multiple concept vocabularies at different levels of abstraction may be valid for given task. At this stage, different choices of G are allowed but may lead to distinct results for RSs, depending on the number of ground- concepts and how they related to the labels. Both these two aspects will be made clear in light of the data generation process as per Assumptions 3.1 and 3.2.
3 Reasoning Shortcuts in CBMs
Given a finite set S, we indicate with As C [0, 1||s| the simplex of probability distributions P(Q) over items in S. Any random variable Q E S defines point in the simplex via its distribution P(Q). Notice that the set of the simplex vertices Vert(As) contains all point mass distributions 11QQ - 4
for all g E S. All relevant notation we will use is reported in Table 6.
CBMs as pairs of functions. CBMs and NeSy-CBMs differ in how they implement the inference layer, hence to bridge them we employ the following unified formalism. Any CBM can be viewed as a pair of learnable functions implementing the concept extractor and the inference layer, respectively, cf. Fig. 2. Formally, the former is a function P(C x) over the concepts, however it can be better understood as a function a G - Ae taking ground-truth concepts as input instead, and defined as:
f R² -> Ae mapping inputs x to conditional distribution
a(g) == E
Ex-p'' (X 8) [(x)
(2)
"This distribution subsumes stylistic factors, e.g., calligraphy.
3

---

i
B
B
G
JRS
B JRS
/
/
0 1
2
0 1
2
0
10012
0,0
0.0
0.0
0.1
0.1
0.1
0.2
0.2
0.2
1.0
1.0
1.0
1.1
1.2
2.0
2.0
2,0
2.1
2,2
2,2
2,2
Figure 2: Examples of semantics in MMIST-SumParity restricted to g, {0, 1, for readability. Left: ideally, a should be the identity (i.e., C recovers the ground concepts G) and the inference layer should learn B Middle: (ars (is) * (id, (3") has intended semantics (Definition 3.3), ie., the ground ground-truth truth concepts and inference layer can be recovered and generalize OOD. Right: (ains, Jns)) affected by the Joint Reasoning Shorteuts in Fig. Elements (predicted concepts C
and entries in (3) in red are never predicted nor used, highlighting simplicity bias. Maps are visualized matrices.
In contrast, the inference layer is function Ac -> Ay mapping the concept distribution output by the concept extractor into a label distribution p f(x)). For clarity, we also define (3 Ay: which is identical to the former except works with concept values rather than distributions, that is:
B(c) w[[C = ct)
(3)
Hence, CBM entails both pair w) E F x Ω and pair (), E EAx B. Later on, we will x make use of the fact that and are simplices [61, 62), i.e., each a A (resp. B B) can be written convex combination of vertices Vert(AA) (resp. Vert(B)).
As mentioned in Section 2, supplying prior knowledge K a NeSy-CBM is equivalent to fixing the inference layer to corresponding function w" (and 3²)) Note that whereas w" changes based on how reasoning implemented e.g., fuzzy vs. probabilistic logic - 3 does not, as both kinds of reasoning layers behave identically when input any moint-mass concept distribution 1[C c}.
Standard assumptions. The maps and induced respectively by the concept extractor and inference layer, are especially useful for analysis provided the following two standard assumptions about how data distributed [19, 21, 53]:
Assumption 3.1 (Extrapolabillity- The ground-truth distribution (G X is induced by a function
f* x g. ie., p" (G X) 1(G (X)).
This means that the ground- -tuuh concepts g can always be recovered for all inputs by a sufficiently expressive concept extractor; the it induces is the identity id(g) = 1|( g) E Vert(A).
Assumption 3.2 (Deterministic knowledge). The ground-truit truth distribution p" (Y G: K) induced by the knowledge via a map 3 E Vert(B)), such that p" (Y G;K) = (g).
This ensures that the labels y be predicted without any ambiguity from the ground-truth concepts g. Notice that, not choices of G guarantee that these assumptions are met. Small concept spaces may not give deterministic knowledge, i.e., labels can be confused for one another with only few concepts, or too-arbie arbitrabtryy choices the constituents may not guarantee their extrapolation from the input, i.e., ground-truth concepts of the input are ambiguous. Nonetheless, both assumptions hold in several NeSy tasks [22] and underlie many works in RSs [19, 63, 20), but formulating theory that relaxes them is not straightfoward and is technically challenging. In fact, Marconato et al. [19] showed that upon relaxing Assumption 3.2 it might not be possible to deal with RSs.
The maximum log- likelihood objective is then written
max (f.w)eX'X2
(xxx)))x'(xx) log(wy o (x)
Here, Wy is the conditional probability of the ground-truti labels y. Notice that under the above assumptions CBMs attaining maximum likelihood perfectly model the ground-truth data distribution (X, Y), see Lemma C.I.
'We work in the non- non-parane parametric setting, hence F and Ω contain all learnable concept extractors f and inference layers w. and similarly A and B contain all learnable maps and B.

---

3.1 Intended Semantics and Joint Reasoning Shortcuts
We posit that a CBM (a, E A B has "high-quality" concepts and inference layer if satisfies two desiderata: (i) disentanglement: each learned concept C; should correspond to single ground-truth concept G up to an invertible transformation; (ii) generalization: the combination of a and , must always yield correct predictions.
In our setting, without concept supervision and prior knowledge, the learned concepts are anonymous and users have to figure out which is which in a post-hoc fashion, e.g., by aligning them to dense annotations [3, 4, 50, 51]. Doing so is also prerequisite for understanding the learned inference layer [52, 50, 4, 55J. When disentanglement holds the mapping between G and C can be recovered exactly using Hungarian matching [64]; otherwise it is arbitrarily difficult to recover, hindering interpretability. This links CBMs with many works that treat model representations' identifiability in Independent Component Analysis and Causal Representation Learning [65, 66, 67, 68, 69], where disentanglement plays central role. Generalization is equally important, as it entails that CBMs generalize beyond the support of training data and yields sensible OOD behavior, i.e., output the same predictions that would be obtained by using the ground-truth pair. Therefore, the pairs (ax, (3) which satisfy both desiderata will be equivalent to the ground-truth pair (id, ,3)) and equally valid solutions for the NeSy task. Since we want a to be disentangled, this implies, in turn, specific form for the map B, as shown by the next definition, which formalizes these desiderata:
Definition 3.3 (Intended Semantics). A CBM (f, w) E F x Ω entailing a pair (ox, E AAx x B possesses the intended semantics if there exists a permutation : [k] + [kt] and k element-wise invertible functions 11,,.., 2/ such that:
(5) Here, Px: : : C is the permutation matrix induced by т and <b(c)= == (c1), Uu (cx)). In this case, we say that (ax, 3) is equivalent to (id, ), ie., (a,,3) ~ (id, 3*)
agg) = (1b o Pa o (g)
B(c) = =(3" P o (cC)
Intended semantics holds if the learned concepts C match the ground-truth concepts G modulo simple invertible transformations like reordering and negation (Eq. (5), left) and the inference layer undoes these transformations before applying the "right" inference layer 3 (Eq. (5), right). In particular, Eq. (5) (left) guarantees disentanglement of the concepts, ensuring that each learned concept corresponds to a distinct ground- trrtt concept up to an invertible transformation, matching the notion of [68]. A similar equivalence relation was analyzed for continuous representations in energy-based models, including supervised classifiers, by Khemakhem et al. [65]. CBMs satisfying these conditions are equivalent specifically by the equivalence relation ~ see Appendix C.1 to the ground-truth pair (id,3'): see Fig. 2 (middle) for an illustration. In Lemma C.4, we prove that models with the intended semanties yield the same predictions of the ground-truth pair for all g E G.
Training a (NeSy) CBM via maximum likelihood does not guarantee it will embody intended semantics. We denote these failure cases as joint reasoning shortcuts (JRSs):
Definition 3.4 (Joint Reasoning Shortcut). Take a CBM (f, w) E F x Q that attains optimal log- likelihood (Eq. (4)). The pair (3) entailed by it (Eqs. (2) and (3)) is a JRSs if it does not possess the intended semantics (Definition 3.3), i.e., (a, () + ).).
JRSs can take different forms. First, even if the learned inference layer (3 matches (modulo P., and xb) the ground-truth one 3 a might not match (also modulo P,, and ap) the identity. This is analogous to regular RSs in NeSy CBMs (Section 2), in that the learned concepts do not reflect the ground- ground-truth ones: while this is sufficient for high in-distribution performance (the training likelihood is in fact optimal), it may yield poor OOD behavior. Second, even if a matches the identity, the inference layer B might not match the ground-truth one 3 In our experiments Section 5, we observe that this often stems from simplicity bias [70], i.e., the CBM's inference layer tends to acquire specialized functions ,3 that are much simpler than , leading to erroneous predictions OOD. Finally, neither the inference layer /3 nor the map a might match the ground-trute opening the door to additional failure modes. Consider the following example:
Example 3.5. Consider a MWIST-SuuParity problem where the training set consists of all possible unique (even, even), (odd, odd). and (odd, even) pairs of MNIST digits, as in Fig. 1. A CBM trained on this data would achieve perfect accuracy by learning a JRS that extracts the parity of each input digit, yielding two binury concepts in {0,1), and computes the difference between these two concepts. This JRS involves much simpler concepts and knowledge compared to the ground-trutt truth ones. also mispredicts all OOD pairs where the even digits come before odd digits.
5

---

While the presence of JRSs undermines both interpretability and OOD generalization, their absence alone does not guarantee OOD robustness. However, if JRSs are present, the likelihood of OOD failure increases substantially. For example, consider Example 3.5, where a CBM achieves perfect training accuracy by learning a shorteut that captures only the parity of each digit rather than the full ground-truth concepts. This shorteut fails on OOD pairs; for example, given an (even, odd) pair not present in the training set, the model wrongly oulputs -1 as the final label.
3.2 Theoretical Analysis
We now count the deterministic JRSs admitted by a task, i.e., those that lie on the vertices of A and B: (a,, () E Vert(A) x Vert(B). We then show Theorem 3.9 that this number determines whether general (non-deterministic) JRSs exist. Theorem 3.6 (Informal). Under Assumptions 3.1 and 3.2, the number of deterministic JRSs is:
Σ1 RESupP(G)
(Boa)(g) = 3 -
(a.8)
where the sum runs over Vert(A) Vert(B), and C(G] counts the pairs with intended semantics.
All proofs and the definition of C[C] can be found in Appendix C. Intuitively, the first count includes all deterministic pairs (a,3) that achieve maximum likelihood on the training set (i.e., the predicted labels (g o (g) matches the ground-truth one 3 (g) for all ground-truth concepts g appearing in the data), while the second term subtracts those (ox, (33 that possess the intended semantics as per Definition 3.3. A positive count implies that a CBM trained via maximum likelihood can learn a deterministic JRS. Notice that the count of JRSs also depends on the choice of the concept space G: large number of fine-gre ame-ggrined ground truth concept may increase the number of JRSs, while coarser-graine concepts that are lower in number may reduce them.
As sanity check, we show that if prior knowledge K is provided fixing the inference layer to 3 the number of deterministic JRSs in fact matches that of RSs, as expected:
Corollary 3.7. Consider fixed 3 E Vert(B). Under Assumptions 3.1 and 3.2, the number of deterministic JRSs (ar, 3²¹) E Verr(A)) x Vert(B) is:
EneVen(A)) 1lA R(AResupp(C)) (3" a (g)(g)) = (g)) -1 This matches the count for deterministic RSs in [/9].
Corollary 3.7 implies that when \Ver(B)) > 1, the number of deterministic JRSs in Eq. (6) can be much larger than the number of deterministic RSs (Eq. (7)). For example, in WWIST-SunParity with digits restricted to the range [0, 4] there exist 64 RSs but about 100 thousand JRSs, and the gap increases
extend the range [0, MV. An in-depth analysis appears in Appendix B.5.
Next, we show that whenever the number of deterministic JRSs in Eq. (6) is zero, there exist no JRSs at all, including non non-deterministic ones. This however only applies to CBMs that satisfy the following natural assumption: Assumption 3.8 (Extremality).
The inference layer w E Q satisfies extremality for all X E (0. 1) and all # c' e C. such that argmaxyey w [1[C = c})y # argmaxy w( 1[C c'D)y, , it holds:
max o (Al = (1- = = yEy
max
max w (1[C c)ly, max w w =c)ly yEy
yEy
Intuitively, CBM satisfies this assumption if its inference layer is "peaked": for any two concept vectors e and e' yielding distinct predictions, the label probability output by w for any mixture distribution thereof is larger than the label probability that it associates That is, distributing probability mass across concepts does not increase label likelihood. While this assumption does not hold for general CBMs, show in Appendix E that it holds for popular architectures, including most of those that we experiment with. Under Assumption 3.8, we have: Theorem 3.9 (Identifiability). Under Assumptions 3. and 3.2, if the number of deterministic JRSs (Eq. (6) is zero then every CBM (f, w) F x Ω satisfying Assumption 3.8 that attains maximum log- likelihood (Eq. (4)) possesses the intended semantics (Definition 3.3). That is, the pair (a, (3) E AxB B entailed by each such CBM is equivalent to the ground-truth pair (id, B"), i.e., (a. 3) ~ (id, 33).
and c².
Clearly, a similar conclusion does not hold for models that do not satisfy Assumption 3.8: even when deterministic JRSs are absent, CBM can still be affected by non-deterministic JRSs.

---

4 Practical Solutions
By Theorem 3.9, getting rid of deterministic JRSs from a task prevents CBMs trained via maximum log- ge-likeelihodd to learn JRS altogether. The key question is how to make the JRSs count be zero As previously explored in RSs, pairing the maximum likelihood objective with other well-known penalties in the literature can limit optimal a's for the joint training objective. Several mitigation strategies for RSs have shown to decrease the count of the a's, in some cases leading to zeroing deterministic RSs [19, 21J. We report the count reduction of different mitigations in Appendix D.
Supervised strategies. The most direct strategies for controlling the semanties of learned CBMs rely on supervision. Concept supervision is the go-to solution for improving concept quality in CBMs [3. 71, 4, 5] and NeSy-CBMs [22, 21J. Full concept supervision prevents learning a + id. However, this does not translate into guarantees on the inference layer B3, at least in tasks affected by confounding factors such as spurious correlations among concepts [14]. E.g., if the i-th and j-th ground-trude truth concepts are strongly correlated, the inference layer 3 can interchangeably use either, regardless of what 3 does.
Another option is employing knowledge distillation [72], that is, supplying supervision of the form (g: y) to encourage the learned knowledge be close 3 for the supervised g's. This supervision is available for free provided concept supervision is available, but can also be obtained separately, e.g., by interactively collecting user interventions [54, 55, 56]. This strategy cannot avoid all JRSs because even if B = B", the CBM may suffer from regular RSs (i.e., a does not match the identity function id).
Another option is to fit a CBM on multiple tasks [73] sharing concepts. It is known that a NeSy-CBM attaining optimal likelihood multiple NeSy tasks with different prior knowledges is also optimal for the single NeSy task obtained by conjoining those knowledges [19]: this more constrained knowledge better steers the semantics of the learned concepts, ruling out potential JRSs. Naturally, collecting sufficiently large number of diverse tasks using the same concepts can be highly non-trivial, depending on the application.
Unsupervised strategies. Many popular strategies for improving concept quality in (NeSy) CBMs unsupervised. A cheap but effective one when dealing with multiple inputs is to process inputs individually, preventing mixing between their concepts. E.g., In MUIST-SumParity one can apply the same digit extractor to each digit separately, while for images with multiple objects one first segment them (e.g., with YoloV11 [74]) and then process the resulting bounding boxes individually. This is extremely helpful for reducing, and possibly overcoming, RSs [19] and frequently used in practice [41, 75, 50, 51J. We apply it in all our experiments.
Both supervised [5] and unsupervised [1, 76] CBMs may employ reconstruction penalty [77, 78] to encourage learning informative concepts. Reconstruction can help prevent collapsing distinct ground-truth concepts into single learned concepts, c.g., in MNIST-SumParity the odd digits cannot be collapsed together without impairing reconstruction. Alternatively, one can employ entropy maximization [79] to spread concept activations evenly across the bottleneck. This can be viewed as a less targeted but more efficient alternative to reconstruction, which becomes impractical for higher dimensional inputs. Another option is contrastive learning [80], in that augmentations render learned concepts more robust to style variations [81], e.g., for MNIST-base tasks it helps to cluster distinct digits [82]. Unsupervised strategies all implicitly counteract simplicity bias whereby ends up collapsing.
5
Case Studies
We tackle the following key research questions: Q1. Are CBMs affected by JRSs in practice? Q2. Do JRSs affect interpretability and OOD behavior? Q3. Can existing mitigation strategies prevent JRSs? Appendix A reports additional details about the tasks, architectures, and model selection.
Models. We evaluate several (also NeSy) CBMs. DeepProbLog (DPL) [41, 79] is the only method supplied with the ground-truth knowledge K, and uses probabilistic-loicc reasoning to ensure pre- dictions are consistent with it. CBNM is a Concept-Bottlenee Model [3] with no supervision on
'This is provably the case context-style separation i..., assuming concepts are independent of stylistic features like calligraphy [19, Proposition 6).
7

---

Table 1: Results for MNIST-Add.
Table 2: Results for MNIST-SumParity.
Microon
P1
0.58
0.01
0.90 + 0.01
0.01 = 0.01
DPC
0.99 + 0.01
0.43 + 0.08
0.96 0:1.66
CBRM
0.98 4: 0.01
0.90 a 0.01
0.01
# 0.01
1.00 0.00
CERN
0.50 + 0.18
0.00 = 0.03
0.66 0.00
0.54 0.04
0.57
0.01
0.50 = 0.07
0.01
0.01
0.76 = 0.06
2013
0.59 0.01
0.49 = 0.06
0.01 0.01
0.53 = 0.06
DEL
0.96
0.00
0.98
0.01
0.01
0.01
1.00 0.01
0.94 0.03
0.07 2.001
1.800:0000
0.522:0..0
0.93
0.92 0.08
0.01
0.01
0.50 0.08
DPC
0.50 2 0.01
0.07
2 0.01
0.80 2.000
0.50 2.05
bearx"
0.76
0:15
0.87 0:13
0.01
0.01
0.67
2:14
0.09 0.001
0.30 = 0.00
0.22 0.004
0.30 =
Table 4: CBNM on biased MNIST-SumPari tty
Table 3: Results for Clevr.
Mirwan
Pi(0) it)
P1
1D
000
C-S0
R-80
(1)
P400y (T)
Pu(/)) (1:
0.01
0.25 0.06
0.57 0.02
0%
0.59 + 0.00
0.35 + 0.05
0.01 +.0.1
0.47 + 0.07
CTRM
0.99 0.01
0:19 a 0.06
0.35 0.00
0:01 0.00
0.99
0.30
0.01 +:0.0
0.58 0.08
0.99 0.01
0.22 0.04
0.57 0.08
0.01 0.01
100%
100%
0.87 0.00
0.95 1:00
0.97 1.002
0.88 1..27
Table 5: Results for BDD-OIA.
METHOO
(t)
(t)
(L)
(1)
DPL
0.69 + 0.03
0.44 # 0.01
0.88 = 0.01
CONN
0.62 1: 0.03
0.43 4 0.02
0.06 1 0.02
0.42 1 0.03
the concepts. Deep Symbolic Learning (DSL) [50] is a SOTA NeSy-CBM that learns concepts and symbolic knowledge jointly; it implements the latter as a truth table and reasoning using fuzzy logic. We also consider two variants: DPL replaces fuzzy with probabilistic logic, while bears" wraps DPL* within BEARS [63], an ensemble approach for handling regular RSs. In short, bears" consists of a learned inference layer and multiple concept extractors. The former is learned only once, the latter are learned sequentially. We also evaluate Self-explainable Neural Networks (SENN) [1], unsupervised CBMs that include reconstruction penalty. Since they do not satisfy our assumptions, they are useful to empirically assess the generality of our remarks. In our experiments, we train all CBM variants in a joint manner [3] using only label supervision and do not rely on foundation models for gathering annotations [32, 33, 34]. For additional details, see Appendix A.
Data sets. To assess both learned concepts and inference layer, we use three representative NeSy tasks with explicit concept annotations and prior knowledge. AdIST-Add [41] involves predicting the sum of two MNIST digits, and serves as a sanity check as it provably contains no RSs. similar except we have to predict the parity of the sum, as in Fig. I, and admits many JRSs. We also include a variant of Clevr [83] in which images belong to 3 classes as determined by a logic formula and only contain 2 to objects, for scalability. Finally, we carry out basic checks also on BDD-OIA [84], a real-world autonomous driving task where images are annotated with actions (move forward, stop, turn_ left, turn_ sarn_right) and 21 binary concepts.
Metrics. For each CBM, we evaluate predicted labels and concepts with the Fi score (resp. Fi (Y) and (C)) on the test split. Computing Fi (C) requires to first align the predicted concepts to ground- truth annotations. We do so by using the Hungarian algorithm [64] to find a permutation ा that maximizes the Pearson correlation across concepts. this way, we directly evaluate disentanglement of the concepts as per Eq. (5) (left). Concept collapse Cls(C) quantifies to what extent the concept extractor blends different ground-truit concepts together: high collapse indicates that it predicts fewer concepts than expected. We measure the quality of the learned inference layer B3 follows: for each input x, (1) we reorder the corresponding concept annotations g using म, (2) feed the result to ,3, and (3) compute the Fi-score (F, (B)) of its predictions. Step (1) permutes and applies element-wiss invertible transformations on the ground-trum -ound-truth concepts using the inverse of the map returned by Hungarian matching. This evaluates whether the learned inference layer can correctly handle (an invertible transformation of) the ground-trum truth concept annotations, measuring the generalization as per Eq. (5) (right). This procedure is precisely detailed in Appendix A.6.
Mitigation strategies. We evaluate all strategies discussed in Section well as a combination of all unsupervised mitigations, denoted H+R+C (entropy, reconstruction, contrastive). Implementations are taken verbatim from [22]. For contrastive learning, we apply an InfoNCE loss to the predicted concept distribution with the augmentations suggested by Chen et al. [80]. For knowledge distillation, the inference layer is fed ground-truth concepts and trained to optimize the logllikeli of the corresponding labels.
8

---

1.00
k-sup
F1(C)
FalB
CIs(C)
20% k.sup
0.75
k-sup
60% k:sup
0.50
80%
100% kssup
Entropy
0.00
Reconstruction
20
40
60
80
100
0
20
40
60
80
100
0
20
40
60
80
100
Contrastive
C-SUP (16)
C-SUP (%)
C-SUP
(%)
I++C+
Figure 3: Traditional mitigations have limited effect CBNM for MNIST-SumParta The only
outlier is contrastive learning (orange and purple), which consistently ameliorates concept collapse.
Q1: All tested CBMs suffer from JRSs and simplicity bias. We analyze three learning tasks of increasing complexity. MNIST-Add provably contains no JRSs and thus satisfies the preconditions of Theorem 3.9. Compatibly, all CBMs attain high label performance (Fi (Yi(Y) > 90%) and high-quality semantics, as shown by the values of Fi (C) (2 90%) and (3) 2 75%) seen in Table 1. The only exception is bears", which by design trades off performance for calibration. However, in SUSTT-SuPaartty and Clevr," which are more complex, all models lack intended semantics. This is clear from Tables 2 and 3: despite attaining high F1 (Y) (2 90%), the learned concepts and inference layer are low quality: FCC is always low - never crosses the 50% mark and Fi ((3) is best around chance level. Our results BDD-OIA in Table 5 show the very same trend.
The behavior of concept collapse strongly hints simplicity bias. While no collapse takes place in MNIST-Add (CIs(C) < 0.01, i.e., digits are not compacted together), in Clevr collapse is omnipresent (CIs(C)= 2 0.22), suggesting that CBMs are prone to simplicity bias, expected. SENN is outlier, likely due to the higher capacity of its inference layer (rather than reconstruction, which is entirely ineffective in Q3). Even having access to the ground-truth knowledge is ineffective, as shown by the high degree of collapse displayed by DPL.
ty and
Q2: JRSs compromise OOD behavior and supervision only partially helps. We evaluate the impact of JRSs and supervision on OOD behavior by training a CBNM on the biased version of PuIS--SumPrrty in Fig. 1. The in-distribution (ID) data comprise all (odd, odd), (even, even), and (odd, even) pairs of MNIST digits, while the OOD split contains all (even, odd) pairs. Table 4 reports performance under varying levels of concept and knowledge supervision. While all models produce high-quality predictions in-distribution (Fi (Y) 2 0.97), only the CBNM receiving complete supervision attains acceptable OOD predictions: for the others, Fi (Y) & 0.40. Even this case, though, the inference layer still does not have intended semantics, as shown by Fi (B) < 70%.
Q3: Popular CBM and RS mitigations fall short. Finally, we test mitigation strategies on CBNM and Clevr, ablating the amount of supervision. The results for
trained on WWIST-SuPPare WIIST-SumPariyy in Fig. 3 show while concept supervision (æ-axis) helps all metrics, adding reconstruction, entropy maximization, and contrastive learning to the mix brings no benefits for concept and knowledge (Fi (C), (3)) quality, not even when combined (orange curve). Knowledge supervision is also ineffective (blue lines), likely because RSs even when the model is supplied prior knowledge. Contrastive learning improves concept collapse (CIs(C)): the orange and purple curves in Fig. 3 (right) show it can prevent CBMs from mixing concepts together. The results for Clevr in Appendix show similar trends.
and Clevr suffer from
6 Related Work
Shorteuts in machine learning. Shortcuts occur when machine learning models solve prediction task by using features that correlate with but do not cause the desired output, leading to poor OOD behavior [12, 10, 85, 86]. Existing work focuses black-box models rather than CBMs. Existing studies on the semantics of CBM concepts [87, 15, 88, 89] focus on individual failures but lack formal notion of intended semantics. One exception [17] which, however, ignores the role of the inference layer. We build on known results on reasoning shortcuts [90, 19, 20, 53] which are restricted to NeSy-CBMs in which the prior knowledge is given and fixed. Our analysis upgrades these results to general CBMs. Furthermore, our simulations indicate that strategies that are effective
For Clevr, we focus representative CBMs with high fit the training data.

---

for CBMs and RSs no longer work for JRSs. At the same time, while NeSy approaches that learn prior knowledge and concepts jointly are increasingly popular [48, 91, 49, 50, 51, 52], existing work neglects the issue of shortcuts in this setting. Our work partially fills this gap. Shortcuts and JRSs are related but distinet. While shorteuts can induce JRSs, the converse not true: a model can be affected by JRS even if it does not rely on confounders, shown in Fig. 2. This distinction also implies that mitigation strategies designed for vanilla shortcuts do not necessarily transfer to JRSs.
Relation to identifiability. Works in Independent Component Analysis and Causal Representation Learning focus on the identifiability of representations up to an equivalence relation, typically up to permutations and rescaling [92. 93, 69] or more general transformations [94, 95]. The equivalence relation introduced along with intended semantics (Definition 3.3) establishes a specific connection between the maps and B. This aligns with existing works that aim to identify representations and linear inference layers using supervised labels [68, 96, 97, 98, 99]. Moreover, while prior works primarily focus on identifying real-valued representations, we examine the identifiability of discrete concepts and of the inference layer. [100] explores the identifiability of (potentially discrete) concepts linearly encoded in model representations but focuses on multi-environment settings, Our results differ in that we show how concepts can be identified in CBMs by circumventing reasoning shortcuts. A concurrent work by Goyal et al. [101] identifies latent concepts through label supervision and sparsity regularization, showing that a variant of CBNMs can provably recover concepts with the intended semantics and thus avoiding JRSs altogether, see [101, Theorem 2].
7 Conclusion
We study the issue of learning CBMs and NeSy-CBMs with high-quality concepts and inference layers. We formalize intended semantics and joint reasoning shortcuts (JRSs), showing how, under suitable assumptions, zeroing the number of deterministic JRSs provably prevents all JRSs, yielding identifiability. Numerical simulations indicate that JRSs are very frequent and impactful, and that the only (partially) beneficial mitigation stratgy is contrastive learning. Our work paves the way to the design of effective solutions and therefore more robust and interpretable CBMs. In future work, we plan to extend our theory to general neural nets and large language models, and we will take a closer look at more complex mitigations such as smartly constraining the inference layer [49, 52], debiasing [13], and human interaction [10]. Another asset is considering concept-level supervision gathered from foundation models like CLIP, however recent results [35] call for caution in using them to supervise the bottleneck. Wrong concept-level supervision may transfer biases of foundation models and induce JRSs, thus resulting ineffective as a mitigation strategy.
Broader impact. With this work, we aim to highlight the issue of joint reasoning shortcuts in concept- based models and their subtle but impactful consequences on the trustworthiness and interpretability of these models, as well as on their reliability in out-of-distribution scenarios. It also highlights the limited effect of unsupervised mitigation strategies, thus pointing out significant gap in our toolbox for addressing joint reasoning shortcuts effectively and cheaply. Our work also provides a solid theoretical foundation upon which further studies can build.
Limitations. Our theoretical analysis of JRSs builds on two common assumptions for the data generation process, which limit its scope. Relaxing them, while not straightforward, will allow treating models and NeSy tasks with intrinsic uncertainty on label and concepts. Our experiments span both yynthetiaall-ggneeaai the impact of JRSs in other real-world settings and beyond the vision domain.
and real-world vision datasets; further analysis should highlight
Acknowledgements
The authors are grateful to Antonio Vergari, Emile van Krieken, Marco Pacini, and Luigi Gresele for useful discussions. Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Health and Digital Executive Agency (HaDEA). Neither the European Union nor the granting authority can be held responsible for them. Grant Agreement no. 101 TANGO. The work of AP was partially supported by the MUR PNRR project FAIR- Future AI Research (PE00000013) funded by the NexIGenerationEU. PM was supported by the MSCA project Probabilistic Formal Verification for Provably Trustworthy AI - PPV-4-PTAI under GA no. 1011 109100
10

---

References
David Alvarez-Melis and Tommi S Jaakkola. Towards robust interpretability with self- explaining neural networks. In NeurlPS, 2018.
[2] Chaofan Chen, Oscar Li, Daniel Tao, Alina Barnett, Cynthia Rudin, and Jonathan K Su. This looks like that: Deep learning for interpretable image recognition. NeurIPS, 2019.
[3] Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In International conference on machine learning, pages
PMLR, 2020.
[4] Mateo Espinosa Zarlenga, Pictro Barbiero, Gabriele Ciravegna, Giuseppe Marra, Francesco Gi- annini, Michelangelo Diligenti, Frederie Precioso, Stefano Melacci, Adrian Weller, Pictro Lio, et al. Concept embedding models. In NeurlPS 2022-36th Conference on Neural Information Processing Systems, 2022.
[5] Emanuele Marconato, Andrea Passerini, and Stefano Teso. Glancenets: Interpretable, leak- proof concept-basse based models. Advances in Neural Information Processing Systems, 35: 2 21212-21227, 2022.
[6] Armeen Taeb, Nicolo Ruggeri, Carina Schnuck, and Fanny Yang. Provable concept learning for interpretable predictions using variational autoencoders, 2022.
[7] Andrea Pugnana, Riccardo Massidda, Francesco Giannini, Pietro Barbiero, Mateo Espinosa Zarlenga, Roberto Pellungrini, Gabriele Dominici, Fosca Giannotti, and Davide Bacciu. Deferring concept bottleneck models: Learning to defer interventions to inaccurate experts, 2025. URI. https: htttap:://axxxv.rreeg. wttp://rr/a///.....//// 16199. 16199.
[8] Gesina Schwalbe, Concept embedding analysis: A review. arXiv preprint arXiv:2203. 13999.
2022.
[9] Elconora Poeta, Gabriele Ciravegna, Eliana Pastor, Tania Cerquitelli, and Elena Baralis. Concept-based explainable artificial intelligence: survey. arXiv preprint 2xXx:23312112993 2023.
[10] Stefano Teso, Öznur Alkan, Wolfang Stammer, and Elizabeth Daly. Leveraging explanations interactive machine learning: An overview. Frontiers in AI, 2023.
[11] Avani Gupta and PJ Narayanan. A survey on concept-based approaches for model improvement. arXiv preprint 1456 2024.
[12] Robert Geirhos, Jörn-Henrik Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. Shortcut learning in deep neural networks. Nature Machine Intelligence, 2(11):665-673, 2020.
[13] Mohammad Taha Bahadori and David Heckerman. Debiasing concept- explanations with causal analysis. In ICLR, 2021.
[14] Wolfgang Stammer, Patrick Schramowski, and Kristian Kersting. Right for the Right Concept: Revising Neuro-Symbolic Concepts by Interacting with their Explanations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3619-3629, 2021.
[15] Anita Mahinpei, Justin Clark, Isaac Lage, Finale Doshi-Velez, and Weiwei Pan. Promises and pitfalls of black-box concept learning models. In International Conference on Machine Learning: Workshop on Theoretic Foundation, Criticism, and Application Trend of Explainable AI, volume 1, pages 1-13, 2021.
[16] Mateo Espinosa Zarlenga, Pietro Barbiero, Zohreh Shams, Dmitry Kazhdan, Umang Bhatt, Adrian Weller, and Mateja Jamnik, Towards robust metrics for concept representation evalua- tion. In AAAI, 2023.
11

---

[17] Emanuele Marconato, Andrea Passerini, and Stefano Teso. Interpretability is in the mind of the beholder: A causal framework for human- interpp-terreet representation learning. Entropy. 2023.
[18] Oscar Chang, Lampros Flokas, Hod Lipson, and Michael Spranger. Assessing satnet's ability to solve the symbol grounding problem. NeurlPS, 2020.
[19] Emanuele Marconato, Stefano Teso, Antonio Vergari, and Andrea Passerini. Not all neuro- symbolic concepts are created equal: Analysis and mitigation of reasoning shortcuts. In NewrPPS, 2023.
[20] Kaifu Wang, Ef Tsamoura, and Dan Roth. On learning latent models with multi-instance weak supervision. In NeurlPS, 2023.
[21] Xiao-Wen Yang. Wen-Da Wei, Jie-Jing Shao, Yu-Feng Li, and Zhi-Hua Zhou. Analysis for abductive learning and neural-symbolic reasoning shortcuts. In ICMI., 2024.
[22] Samuele Bortolotti et benchmark suite for systematically evaluating reasoning shortcuts. In NeurlPS Datasets & Benchmarks Track, 2024.
[23] Mert Yuksekgonul, Maggie Wang, and James Zou. Post-hoc concept bottleneck models. arXiv preprint arXiv:2205. 15480, 2022.
[24] Zhenzhen Wang, Aleksander Popel. and Jeremias Sulam. Cbm-zero: Concept bottleneck model with zero performance loss. 2024.
[25] Gabriele Dominici, Pietro Barbiero, Francesco Giannini, Martin Gjoreski, and Marc Langhenirich. Anycbms: How to turn any black box into concept bottleneck model. arXiv preprint arXiv:2405. 16508, 2024.
[26] Ričards Marcinkeviës, Sonia Laguna, and Moritz Vandenhirtz. Beyond concept bottleneck models: How make black boxes intervenable? In NeurIPS, 2024.
[27] Yoshihide Sawada and Keigo Nakamura. Concept bottleneck model with additional unsuper- vised concepts. IEEE Access, 0144158-417666 2022.
[28] Eunji Kim, Dahuin Jung, Sangha Park, Siwon Kim, and Sungroh Yoon. Probabilistic concept bottleneck models. In International Conference on Machine Learning, pages 16521-16540. PMLR, 2023.
[29] David Debot, Pietro Barbiero, Francesco Giannini, Gabriele Ciravegna, Michelangelo Diligenti, and Giuseppe Marra. Interpretable concept-based memory reasoning. In NeurIPS, 2024.
[30] Lei Huang, Weijiang Yu, Weitao Ma, Weihong Zhong, Zhangyin Feng, Haotian Wang. Qiang- long Chen, Weihua Peng, Xiaocheng Feng, Bing Qin, et al. A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions. ACM Transactions Information Systems, 2024.
[31] Zechen Sun, Yisheng Xiao, Juntao Li, Yixin Ji, Wenliang Chen, and Min Zhang. Exploring and mitigating shortcut learning for generative large language models. L.RECCCLLING, 2024.
[32] Tuomas Oikarinen, Subhro Das, Lam M Nguyen, and Tsui-Wei Weng. Label-free concept bottleneck models. In ICLR, 2022.
[33] Yue Yang, Artemis Panagopoulou, Shenghao Zhou, Daniel Jin, Chris Callison-Burde and Mark Yatskar. Language in a bottle: Language model guided concept bottlenecks for interpretable image classification. In CVPR, 2023.
[34] Divyansh Srivastava, Ge Yan, and Tsui-Wei Weng. VI.G-BM: Training concept bottleneck models with vision-language guidance. In NeurIPS, 2024.
[35] Nicola Debole, Pietro Barbiero, Francesco Giannini, Andrea Passerini, Stefano Teso, and Emanuele Marconato. If concept bottlenecks are the question, are foundation models the answer?, 2025. URL https: h//s:://arraa //arxiv.vvv////////////e///aaxa org/ 2204 19774.
12

---

[36] Simon Schrodi, Julian Schur, Max Argus, and Thomas Brox. Concept bottleneck models without predefined concepts. arXiv preprint arXiv:2407.03921, 2024.
[37] Michelangelo Diligenti, Marco Gori, Marco Maggini, and Leonardo Rigutini. Bridging logic and kernel machines. Machine learning, 86( (6(1):57-88, 2012.
[38] Ivan Donadello, Luciano Serafini, and Artur D'Avila Garcez. Logic tensor networks for semantic image interpretation. In IJCAI, 2017.
[39] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck. A semantic loss function for deep learning with symbolic knowledge. In ICMI., 2018.
[40] Marco Lippi and Paolo Frasconi. Prediction of protein 3-residue contacts by markov logic networks with grounding-speciffi weights. Bioinformatics, 2009,
[41] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. DeepProbLogg: Neural Probabilistic Logic Programming. NeurIPS, 2018.
[42] Elconora Giunchiglia and Thomas Lukasiewicz. Coherent hierarchical multi-label classifica- tion networks. NeurIPS, 2020.
[43] Nick Hoemll,, Rafacl Michael Karampatsis, Vaishak Belle, and Kobi Gal. Multiplexnet: Towards fully satisfied logical constraints in neural networks. In AAAI, 2022.
[44] Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic Probabilistic Layers for Neuro-Symbolie Learning. In NeurlPS, 2022.
[45] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/,
1998.
[46] Lotf Asker Zadeh. Fuzzy logic. Computer, 1988.
[47] Luc De Raedt and Angelika Kimmig. Probabilistic (logic) programming concepts. Machine Learning, 100:5-47, 2015.
[48] Po-Wei Wang. Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In International Conference on Machine Learning, pages 6545-6554. PMLR, 2019.
[49] Anji Liu, Hongming Xu, Guy Van den Broeck, and Yitao Liang. Out-of-distribution general- ization by neural-symbolic joint training. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 12252-12259, 2023.
[50] Alessandro Daniele, Tommaso Campari, Sagar Malhotra, and Luciano Serafini. Deep symbolic learning: discovering symbols and rules from perceptions. IJCAI, 2023.
[51] Hao Tang and Kevin Ellis. From perception programs: regularize, overparameterize, and amortize. In ICMI., 2023.
[52] Antonia Wüst, Wolfgang Stammer, Quentin Delfosse, Devendra Singh Dhami, and Kristian Kersting. Pix2code: Learning to compose neural visual concepts as programs. arXiv preprint DXXv:2442.088288 2024.
[53] Elena Umili, Francesco Argenziano, and Roberto Capobianco. Neural reward machines. In ECAI 2024, pages 3055-3062. los Press, 2024.
[54] Sungbin Shin, Yohan Jo, Sungsoo Ahn, and Namhoon Lee, A closer look at the intervention procedure of concept bottleneck models. In ICML, 2023.
[55] Mateo Espinosa Zarlenga, Katie Collins, Krishnamurthy Dvijotham, Adrian Weller, Zohreh Shams, and Mateja Jamnik. Learning to receive help: Intervention- concept embedding models. NeurlPS, 2024.
[56] David Steinmann, Wolfgang Stammer, Felix Friedrich, and Kristian Kersting. Learning to intervene concept bottlenecks. In ICML, 2024.
13

---

[57] Piyawat Lertvitayakuujoon, Lucia Specia, and Francesca Toni. Find: human in- thop debugging deep text classifiers. In Conference on Empirical Methods in Natural Language Processing, pages 332-348, 2020.
[58] Xuan Xie, Kristian Kersting, and Daniel Neider. Neuro-symbolic verification of deep neural networks. In IJCAI, 2022.
[59] Faried Abu Zaid, Dennis Diekmann, and Daniel Neider. Distribution-aware neuro-symbolli verification. AISoLA, pages 145-447, 2023.
[60] Paolo Morettin, Andrea Passerini, and Roberto Sebastiani. A unified framework for probabilis- tic verification of ai systems via weighted model integration. arXiv preprint arXiv:2402.04899 2024.
[61] Jason Morton. Relations among conditional probabilities. Journal of Symbolic Computation, 011478-492.. 2013.
[62] Guido Montúfar, Johannes Rauh, and Nihat Ay. On the fisher metric of conditional probability polytopes. Entropy, 2014.
[63] Emanuele Marconato, Samuele Bortolotti, Emile Krieken, Antonio Vergari, Andrea Passerini, and Stefano Teso BEARS Make Neuro-Symbolic Models Aware of their Reasoning Shortcuts. Uncertainty AI, 2024.
[64] Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 1955.
[65] Ilyes Khemakhem, Ricardo Monti, Diederik Kingma, and Aapo Hyvarinen. Ice-beem: Iden- tifiable conditional energy-based deep models based on nonlinear ica. Advances in Neural Information Processing Systems, 33:12766 13112768-22778 2020.
[66] Luigi Gresele, Julius Von Kügelgen, Vincent Stimper, Bernhard Schölkopf, and Michel Besserve. Independent mechanism analysis, new concept? Advances in neural information processing systems, 34:28233-28248, 2021.
[67] Phillip Lippe, Sara Magliacane, Sindy Löwe, Yuki M Asano, Taco Cohen, and Efstratios Gavves, Biscuit: Causal representation learning from binary interactions. In Uncertainty in Artificial Intelligence, pages 1263-1273, PMLR, 2023.
[68] Sebastien Lachapelle, Tristan Deleu, Divyat Mahajan, Ioannis Mitliagkas, Yoshua Bengio, Simon L.acostee-ulien and Quentin Bertrand. Synergies between disentanglement and sparsity: Generalization and identifiability in multi-task learning. In ICML, 2023.
[69] Julius von Kügelgen, Michel Besserve, Liang Wendong, Luigi Gresele, Armin Kekić, Elias Bareinboim, David Blei, and Bemhard Schölkopf. Nonparametric identifiability of causal representations from unknown interventions. Advances in Neural Information Processing Systems, 36, 2024.
[70] Yu Yang, Eric Gan, Gintare Karolina Dziugaite, and Baharan Mirzasoleiman. Identifying spurious biases carly in training through the lens of simplicity bias. In AISTATS, 2024.
[71] Zhi Chen, Yijie Bei, and Cynthia Rudin. Concept whitening for interpretable image recognition. Nature Machine Intelligence, 2020.
[72] Cristian Bucilu, Rich Caruana, and Alexandru Niculescu-Mizil Model compression. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery 1150464.
and Data Mining, 2006. URL https:t//tt....... .oroii.org/1101 10.
[73] Rich Caruana. Multitask learning. Machine learning, 1997.
[74] Glenn Jocher, Jing Qiu, and Ayush Chaurasia. attps://githrr cww http:///w/w..aaaaa///////aaaaaaa
Ultralytics YOLO, January 2023. URL
14

---

[75] Emile van Krieken, Thiviyan Thanapalasingam, Jakub M Tomczak, Frank van Harmelen, and Annette ten Teije. A-nesi: scalable approximate method for probabilistic neurosymbolic inference. arXiv preprint arXiv:2212. 12393, 2022.
[76] Oscar Li, Hao Liu, Chaofan Chen, and Cynthia Rudin. Deep learning for case-based reasoning through prototypes: A neural network that explains its predictions. In AAAI, 2018.
[77] Pierre Baldi. Autoencoders, unsupervised learning, and deep architectures. ICML Workshop Unsupervised and Transfer Learning. 2012.
[78] Diederik P Kingma. Auto-encoding variational bayes. arXiv preprint arXiv: 2013.
[79] Robin Manhaeve, Sebastijan Dumančié, Angelika Kimmig, Thomas Demeester. and Luc De Raedt. Neural probabilistic logic programming in deepproblog. Artificial Intelligence, 298: 103504, 2021.
[80] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Everest Hinton. A simple framework for contrastive learning of visual representations. 2020.
[81] Julius Von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmentations provably isolates content from style. Advances in neural information processing systems, 34: 16451-16467, 2021.
[82] Emanuele Sansone and Robin Manhaeve. Learning Symbolic Representations Through Joint GEnerative and DIscriminative Training. In IJCAI 2023 Workshop on Knowledge-Bacd Compositional Generalization, 2023.
[83] Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Fei-Fei, Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. In CVPR, 2017.
[84] Yiran Xu, Xiaoyin Yang, Lihang Gong, Hsuan-Chu Lin, Tz- Ying Wu, Yunsheng Li, and Nuno Vasconcelos. Explainable object-induced action decision for autonomous vehicles. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
[85] Wenqian Ye, Guangtao Zheng, Xu Cao, Yunsheng Ma, and Aidong Zhang. Spurious correla- tions in machine learning: A survey. arXiv preprint arXhv: 12715, 2024.
[86] David Steimmann, Felix Divo, Maurice Kraus, Antonia Wüst, Lukas Struppek, Felix Friedrich, and Kristian Kersting. Navigating shortcuts, spurious correlations, and confounders: From origins via detection to mitigation. arXiv preprint arXiv:2412.05112, 2024.
[87] Andrei Margeloiu, Matthew Ashman, Umang Bhatt, Yanzhi Chen, Mateja Jamnik, and Adrian Weller. Do concept bottleneck models learn as intended? arXiv preprint 1rxiv:2105.04280 2021.
[88] Marton Havasi, Sonali Parbhoo, and Finale Doshi-Velez Addressing leakage in concept bottleneck models. 2022.
[89] Naveen Raman, Mateo Espinosa Zarlenga, Juyeon Hco, and Mateja Jamnik. Do concept bottleneck models obey locality? In XAI in Action: Past, Present, and Future Applications, 2023.
[90] Zenan Li, Zehua Liu, Yuan Yao, Jingwei Xu, Taolue Chen, Xiaoxing Ma. L Jian, et Learning with logical constraints but without shortcut satisfaction. In ICLR, 2023.
[91] Zhun Yang, Adam Ishay, and Joohyung Lee. Neurasp: Embracing neural networks into answer set programming. In IJCAI 2020, 2020.
[92] Ilyes Khemakhem, Diederik Kingma, Ricardo Monti, and Aapo Hyvarinen. Variational autoencoders and nonlinear ica: A unifying framework. In AISTATS, 2020.
15

---

[93] Luigi Gresele, Paul K Rubenstein, Arash Mehrjou, Francesco Locatello, and Bernhard Schölkopf. The incomplete rosetta stone problem: Identifiability results for multi-view nonlinear ica. In Uncertainty in Artificial Intelligence, pages 217-227. PMLR, 2020.
[94] Geoffrey Roeder, Luke Metz, and Durk Kingma. On linear identifiability of learned repre- sentations. In International Conference on Machine Learning, pages 9030- 9039. PMLR, 2021.
[95] Simon Buchholz, Michel Besserve, and Bernhard Schölkopf. Function classes for identifiable nonlinear independent component analysis. Advances in Neural Information Processing Systems, 35:16946-1696, 2022.
[96] Marco Fumero, Florian Wenzel, Luca Zancato, Alessandro Achille, Emanuele Rodolà, Ste- fano Soatto, Bernhard Schölkopf, and Francesco Locatello. Leveraging sparse and shared feature activations for disentangled representation learning. Advances in Neural Information Processing Systems, 36:27682-27606 2023.
[97] Simon Bing, Jonas Wahl, Urmi Ninad, and Jakob Runge. Invariance & causal representation learning: Prospects and limitations. Causal Representation Learning Workshop at NeurIPS 2023, 2023.
[98] Beatrix Miranda Ginn Nielsen, Luigi Gresele, and Andrea Dittadi. Challenges in explaining representational similarity through identifiability. In UniReps: 2nd Edition of the Workshop on Unifying Representations in Neural Models, 2024.
[99] Beatrix MG Nielsen, Emanuele Marconato, Andrea Dittadi, and Luigi Gresele. When does closeness in distribution imply representational similarity? an identifiability perspective. arXiv preprint arXiv:2506.0378 03784, 2025.
[100] Goutham Rajendran, Simon Buchholz, Bryon Aragam, Bernhard Schölkopf, and Pradeep Ku- mar Ravikumar. From causal to concept-based representation learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[101] Navita Goyal, Hal Daumé III. Alexandre Drouin, and Dhanya Sridhar. Causal differen- tiating concepts: Interpreting LM behavior via causal representation learning. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL
https://openreviiee
[102] Hikaru Shindo, Viktor Pfanschilling, Devendra Singh Dhami, and Kristian Kersting, (alpha)ilp: thinking visual scenes as differentiable logic programs. Machine Learning, 112(5):1465-149) 2023.
[103] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real- time object detection with region proposal networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL https: http:::///ccceceeeeeeeeeeeeee/ee neuriiiiiinnnnnnnneeeeeeeeeeeeep cc/ paper /twess/pper/2215//// /ttp:///e..e/eeeaaaa222222244440
.df.
[104] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017
[105] Diederik P Kingma. Adam: A method for stochastic optimization. arXiv:1412.6980. 2014.
arXiv preprint
[106] Aaron Defazio and Samy Jelassi, Adaptivity without compromise: momentumized, adaptive, dual averaged gradient method for stochastic optimization, 2021. URL https://://aax org/ abs/ 2211..11...01. 11075.
[107] Supratik Chakraborty, Kuldeep S. Meel, and Moshe Y. Vardi. Algorithmic improvements in approximate counting for probabilistic inference: From lincar to logarithmic sat calls. In IJCAI, 2016.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the main claims made in the abstract and introduction accurately reflect the papers contributions and scope.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The theory relies on assumptions Assumption 3.1 and Assumption 3.2, which are well established in the context of Reasoning Shortcuts. It also introduces novel assumption, Assumption 3.8, whose limitations are discussed in Section 3 and which generally hold for the architectures considered in the experiments as shown in Appendix E. Experimentally, the limitations of each supervision strategy are analyzed Section 4.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The proofs of all our theoretical results are included in Appendix C
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The experimental details are discussed in Section 5. The implementation details are also described Appendix A.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will release an open-source implementation of our code upon paper acceptance. Reviewers can inspect the code in the supplementary materials.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The training and test details are described in Appendix A.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For each experiment Section 5, we report error bars, standard deviations or confidence intervals, depending on the table/plot. The same applies to Appendix B.
8. Experiments compute resources
17

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: All the information related the computational resources is reported in Ap-
pendix B.
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the htcppp/lic/tthcccccleeeee......l
NeurlPS Code of Ethics https:
Answer: [Yes]
Justification: The research conducted in the paper conforms with the NeurIPS Code of Ethics.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We briefly discuss broader impact in Section 7.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The authors of the datasets and pre-trained models used in this paper are properly cited in the main text, and all asset licenses have been respected.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not introduce new assets.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowd-sourcing experiments nor research involving human subjects.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
18

---

Justification: The paper does not involve crowdsoureing nor research with human subjects.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, non-standard components.
19

---

A Implementation Details
Here, provide additional details about metrics, datasets, and models, for reproducibility. All the experiments were implemented using Python 3.9 and Pytorch 1.13 and run on one A100 GPU. The implementations of DPL, and the code for RSs mitigation strategies while the code for DSL was taken from [50]. DPL* and bears" were implement on top of DSL code- base. The complete codebase is publicly available https: /tte::///tttttt wtt..///ememeeebboooootttto..... joint-reasoning shortcuts.
taken verbatim from [19],
A.1 Notation
We summarize the notation used in this paper.
Table 6: Glossary of common symbols.
Symbol
Meaning
T, y
Scalar constants
X, Y, Z
Scalar variables
x, X
Vector constant and vector variable
X
Space of input
V. Ag,Ag
Sets of labels, ground- truth, and learned concepts Simplices of probability distributions on sets elements
f:X - AC
Concept extractor
w: By F20
Inference layer
Space of concept extractors and inference layers
a:g + Ac
Map from ground-truth concepts to distribution of model concepts Map the inference layer on concept vectors Spaces of a''s and f3's
B:C + Ay
A,B
p'
distribution over inputs, label, and ground truth concepts Prior knowledge Logical entailment
F
A.2
Datasets
All data sets were generated using the rsbench library [22].
A.2.1
MNIST-Add
Add [41] consists of pairs of MNIST digits [45]. ranging from O 9, and the goal is to predict their sum. The prior knowledge used for generating the labels is simply the rule of addition: K= (Y = Ci C2). This task does admit RSs JRSs when digits are processed separately. The training and test examples take the following form:
(8) All splits cover all possible pairs of concepts, from (0, to (9.9), i.e. there is sampling bias. Overall, MNIST- Add has 42, 000 training examples, 12, 000 validation examples, and 6, 000 test examples.
(( 1), 5 13),
12),
5)}
A.3 MNIST-Sumie MNIST-SumParity
Similarly, in MMIST-SumParity the goal is to predict the parity of the sum, i.c., the prior knowledge is the rule: K = (Y = (C1 + C2) mod 2). This task is more challenging for our purposes, as it is affected by both RSs and JRSs, cf. Fig. 1. Below we report four examples:
1), 6 6 0),
1)}
(9)
20

---

We consider two variants: like MNIST-Add, in MNIST- proper the training and test splits contain all possible combinations of digits, while biased WWIISTSumPPaity the training set contains (even, even), (odd, odd) and (odd, even) pairs, while the test set contains (even, odd) pairs only. This fools CBMs into learning an incorrect inference layer implementing subtraction instead of addition-and-pee ann-iaritt, as illustrated in Fig. 1. Both variants have the same number of training, validation, and test examples as MNIST-Add.
A.4 Clevr
Clevr [83] consists of 3D scenes of simple objects rendered with Blender, see Fig. 4. Images are 3 x 128 x 128 and contain a variable number of objects. We consider only images with 2 to 4 objects each, primarily due to scalability issues with DPL. The ground-truth labels were computed by applying the rules (prior knowledge) proposed by [14], reported in Table 8. Objects determined by four concepts, namely shape, color, material, and size. We list all possible values in Table 7. Overall, Clevr has 6000 training examples, 1200 validation examples, and 1800 test examples.
entirely
Property
Class
Condition
Shapes
Cube, Sphere, Cylinder
Class
3e, (Cubefary) Large(rs))
Colors
Gray
Aär. (Cylinder(xs)) Large[rs))
Class
Rr (Cuho(ay) A Small(ar) Metal(ay))
Purple, Cyan, Yollow
Aär (Spheno(pa)) Small(aa))
Materials
Rubber, Metal
3r, (Sphere(zt) ) A Largefa)) Blue(z,))
Sizes
Large,
ABre (Sphere(As) A Small((as) A Yellow (rs))
Table 7: Clevr properties.
Table 8: Clevr classes
Figure 4: Example of Clevr data.
Preprocessing. All CBMs process objects separately, as follows. Following [102], we fine-tune pretrained YoloV11 model [74] (for 10 epochs, random seed 13) on a subset of the training set's bounding boxes, and it to predict bounding boxes for all images. For each training and test image, we concatenate the regions in the bounding boxes, obtaining list 2 to 4 images which plays the role of input for our CBMs.
Each object has x x x 96 possible configurations of concept values, and we handle between 2 and 4 objects, hence the inference layer has model 962 + 96 + 96* distinct possibilities. Due to the astronomical number of possibilities (which would entail huge truth table/inference layer for DSL and related CBMs), we split the inference layer in two: first predict individual concepts, and then we aggregate them (into, e.g., large-cube and mmall-yellow-shheee prediction. Despite this simplification, Clevr still induces JRSs in learned CBMs.
and use these for
A.5 BDD-OIA
BDD-OIA is autonomous driving dataset, composed of images extracted from driving scene videos [84]. Each image is annotated with four binary labels: move move_ forwfforward stop, turn left. and turn riiht, Each image comes with 21 binary concepts that constitute the explanations for the corresponding actions. The training set contains almost 16k fully labeled frames, while the validation and test sets include almost 2k and 4.5k annotated samples, respectively. We adopt the same prior knowledge used in [22], which we briefly summarize here for the sake of completeness.
For the move _ forward and stop actions, the rules are as follows:
red. light + -ggren_leegaeee
obstacle = car V person V rider V other ochercobstacle road clear + oossaacle
(10)
green green_light V follow clear = move move_forveer forward
red_ bed_light/ stop_stt sign V obstacle + stop
stop + move move_forward
The rules for the turn, left
turn_left and the turn turn_right action, instead, are:
21

---

can turn = left _ane V _eet_grree__aat Lane Leff_follox
cannot_ turn no _o__eeft___t lane
V left_solid line
(11)
can_turn A -cannot_ turn = Surn_leftt
An overview of the classes of BDD-OIA can be found [84].
Preprocessing. BDD-OIA images are preprocessed following the approach described in [27]. We first used a Faster R-CNN [103] model pre-trained on MS-COCO and fine-tuned on BDD-100K, then we extract 2048-dimensions features using pre-trained convolutional layer from [27].
A.6 Metries
For all models, report the metrics averaged over five random seeds.
Label quality. We measure the macro average Fi- Fi-sc and Accuracy, to account for imbalance.
Concept quality. We compute concept quality via Accuracy and Fi-sc.e.. However, the order of ground-truth and predicted concepts might might differ, e.g., in Clevr G1 might represent whether "color = red", while C₁ whether "color = blue". Therefore, in order to compute these metrics have first align them using the Hungarian matching algorithm using concept-wise Pearson correlation on the test data [64]. The algorithm computes the correlation matrix R between and i..., Ry corr(G,, Cу) where corr the correlation coefficient, and then infers a permutation between concept values (e.g., mapping ground-truth color "red" to predicted value "blue") that maximizes the above objective. The metries are computed by comparing the reordered ground-truth annotations with the predicted concepts.
Concept Collapse. To compute the Concept Collapse metric Cls(C) [22], follow the procedure described Bortolotti et al. [22], which we briefly describe here. Specifically, we extract confusion matrix in the multilabel setting by encoding each binary concept vector (e.g.. 1,,1,1 3) into categorical label. Let C C 10, be the set of ground-truth concept vectors in the test set, and C be the set of predicted concept vectors. After converting both sets to categorical values, denoted F(C*) and F(C) respectively, construct the confusion matrix C E [0, 1| where m = (F(C) F(C))) From this matrix, we compute the number of predicted categories p as:
p
133. Cig > 0) = [F(C)
(12)
j=1
Then, the Cls(C) metric is given by:
Cls(C) = =1 p
(13)
Where m = 2*.
Inference layer quality. The same permutation is also used to assess knowledge quality. Specifically, we apply it to reorder the ground-truth concepts and then feed these to the learned inference layer, evaluating the accuracy and Fj score of the resulting predictions.
For ANIST-Add and MWIST-SumParity ty, we conducted an exhaustive evaluation since the number of possible combinations to supervise is 100. The results in Table 1 and Table 2 evaluate the knowledge exhaustively, whereas in Table 4, we separately assess the knowledge of in-distribution and out-of-distribution combinations.
In Clevr, as discussed in Appendix A.4, there are too many combinations of concept values to possibly evaluate them all. Therefore, both supervision and evaluation are performed by randomly sampling 100 combinations of ground-truth concepts. We follow the same procedure for BDD- OIA, except that we sample more combinations (2000) due to the larger space of possible concept configurations.
A.7 Architectures
For M0IST-SumParity and MNIST-Add, We employed the architectures from [22], while for DSL, DPL and bears", we followed the architecture described in [50]. For Clevr instead, we adopted
22

---

the decoder presented in Table 9 and the encoder presented in Table 10. All models process different objects (e.g., digits) separately using the same backbone. For BDD-OIA, we adopt the architectures defined in [22].
Table 9: Encoder architecture for Clevr.
LAYER TYPE
PARAMETER
(128. 126, 3)
Convolution
depth=32, kernel=3, stride=1, pod=1
ReLU
(128, 128,32) 32)
MaxPool2d
kemell2,, stridew?
(64, 64, 32)
Convolution
depth=64, kernel11, stride=1, pad=1
ReLU
64,
MaxPool2d
kemel=2, stride=2 kemel=3, stride11, pad=1 out=(1,1)
(61, 32, 32)
Convolution
depth=128.
ReLU
(128, 82)
AdaptiveAvghool2d
(128, 1,
Flatton
(128)
Linear
dim=40, bias True
(128)
Linear
dim=640, bias True dim=640, bias True
(126)
Lineur
Table 10: Decoder architecture for Clevr
INPUT
LAYER TYPE
PARAMETER
ACTIVATION
(255)
Lincar
dim=32768, bias Trie
(8. 8,512)
Com Transposedd
d5pth=266, kemele4, stridew2, padel
(16. 256)
BatchNorm22
ReLU
(16. 16, 256)
Com Transpose2d
depth 128, kemell44, stridew2, pade
(32, 128)
BatchNorm2d
ReLU
(32, 32, 128)
Conv' Con' Transpose2d
depth=64, kernelm4, stride=2, pad=1
[61] 641. 61)
BatehNorm22
ReLU
[64, 64, 64)
Conv' Transpose2d
depth=3, kernet=4, stride=2, pad=1
Tanh
Details of CBNM. For Clevr, we used standard linear layer. Since this is not expressive enough for MNIST-AGe Add and SRIIST-SumPartee we replaced it with an interpretable acondddeggre polynomial layer, i.e., it associates weights to combinations of two predicted digits rather than individual digits. We also include a small entropy term, which empirically facilitates data when little or no concept supervision is available.
Details of SENN. SENN [1] are unsupervised concept- based models consisting of neural network that produces distribution over concepts, neural network that assigns score to those concepts, and decoder. The final prediction made by computing the dot product between the predicted concepts and their predicted scores. SENN by default includes a reconstruction penalty, robustness loss, and sparsity term.
In our implementation, we focus only on the reconstruction penalty. The robustness loss, which aims make the relevance scores Lipschitz continuous, requires computing Jacobians, making the training of those models infeasible in terms of computational time and resources. Additionally, we did not implement the sparsity term, conflicts with the quality of concepts aim to study.
Details of bears". bears" combines DSL [50] and BEARS [63]. BEARS is a NeSy architectures based on deep ensembles [104], designed to improve the calibration of NeSy models in the presence
of RSs and provide uncertainty estimation for concepts that may be affected by such RSs and assumes to be given prior knowledge.
Since in our setup the inference layer learned, we built an ensemble with one learnable inference layer as in DSL and multiple concept extractors. The first element of the ensemble learns both the concepts and the inference layer. Then, we freeze it and train the other concept extractors using the frozen inference layer for prediction. In this sense, bears" provides awareness of the reasoning shortcuts present in the knowledge learned by the first model.
A.8 Mitigation Strategies
Concept supervision. When evaluating mitigation strategies, concept supervision for MNIST- SumParity was incrementally supplied for two more concepts each step, following this order: 4, 1, 0, 2, 8, 9, 5, 6, 7. For Clevr, supervision was specifically provided for sizes, shapes, materials, and colors, in this order.
Knowledge distillation. This was implemented using a cross-entropy on the inference layer. For DSL and DPL, ground-truth concepts were fed into the learned truth table, expecting the correct label.
23

---

Similarly, for CBNMs, which use a linear layer, the same approach was applied. In evaluating the mitigation strategies. we supervised all possible combinations for MNIST-Add, whereas for Clevr. we supervised a maximum of 500 randomly sampled combinations.
Entropy maximization. The entropy regularization term follows the implementation in [19]. The loss is defined as f Σ Hm. (c,] where po PC(C") represents the marginal distribution over the concepts, and Hm, is the normalized Shannon entropy over my possible values of the distribution.
Reconstruction. The reconstruction penalty is the same in [19]. In this case, the concept extractor outputs both concepts and style variables z, i.c. it implements a distribution pe(c, 2 x)) = pe(e)
x) po z). The reconstruction penalty is defined as: -B(c.)))pu(e.=)l) [L c, 2)] where (2 C, represents the decoder network.
Contrastive loss. We implemented contrastive learning using the InfoNCE loss, comparing the predicted concept distribution of the current batch with that of its respective augmentations. Following the recommendations of Chen et al. [80], we applied the following augmentations to each batch: random cropping (20 pixels for MNIST and 125 pixels for Clevr), followed by resizing, color jittering, and Gaussian blur.
A.9 Model Selection
Optimization. For DPL", bears", CBNM and SENN we used the Adam optimizer [105], while for DSL and DPL we achieved better results using the Madgrad optimizer [106].
Hyperparameter search. We performed an extensive grid search on the validation set over the following hyperparameters: (i) Learning rate (7) [1c-4, 1e-3, 1c-2]: (ii) Weight decay (w) in {0, lc-4, 1c-3, 1c-2, 1c-1]; (iii) Reconstruction, contrastive loss, entropy loss, concept supervision loss and knowledge supervision loss weights (w,, Wep Wh. Wesup and wg. respectively) 101; (iv) Batch size (v) in (32, 64, 128, 256, 512). DSL and DPL* have additional hyperparameters for the truth table: Exgm and Eyul for DSL, and A,, the truth table learning rate, for DPL".
(0.1, 1, 2, 5,
All experiments were run for approximately 50 epochs for MNIST variants, 30 for BDD-OIA and 100 epochs for Clevr using early stopping based on validation set FY) performance. The exponential decay rate 3 was set to 0.99 for all experiments, as we empirically found it to provide the best performance across tasks. In all experiments, we selected 7 1e 3.
To answer the first research question in Section 5 on MNIST-Add, for DPL we used: v = 32 and 0.0001; for DSL: / 128, 0.1077119516324466, for CBNM: v = 256 and w = 0.0001: for DPL P = 32, w = 0.01, and X, = 0.0001; for SENN:
0.001, Eeym 0. 0.2807344052335566 and Erul
set the diversifica- and its biased version, for DPL 512 and 0.0001: for DSL: // 128, = 0.0001, Exgm 0. 0.2807344552333566.
64, 0.001, and w, 0.1: while for bears"
tion loss term to 0 and the entropy term to 0.1. On MNIST-SumPar:e
we used:
and Erai = 0.10771 9516324266 for CBNM: y = 256 and ~ = 0.0001; for DPL v = 32, w = 0.01, 64, w 0.001, and w, 0.1; while for bears" we set the diver- sification loss term to 0.1 and the entropy term to 0.2. On Clevr, for DPL, CBNM, and DPL* we used 32 and
and 7, 0.01; for SENN:
0.001; for DPL", X 0.001. On BDD-OIA, for DPL used 128 and w = 10-4 while for CBNM we used = 64 and w = O.
For the second research question, we performed a grid search for each mitigation strategy individually. Additionally, since our analysis focuses on optimal models, we trained multiple models and retained only those achieving optimal (Y) performance
the validation set. For MNIST- SumParits ity, set v/ = 128, w = 0.001, and Wesup = 1 across all experiments. For specific mitigation strategies, used W/ = 1 for entropy regularization, w, 0.01 for reconstruction, w, 0.1 for contrastive learning, and wA = 1 for knowledge supervision. For Clevr, we applied the same settings: v = 128, = 0.001, and tesup 1 for all experiments. The specific mitigation strategy weights were set as follows: w = for entropy regularization, w, = 1 for reconstruction, W. = 0.1 for contrastive learning, and wa 1 for knowledge supervision. When concept supervision is applied, we follow sequential training approach as in [3]. During the initial epochs, the model learns only the concepts, and later, it jointly optimizes both the concepts and the label, as they are challenging learn simultaneously.
24

---

B Additional results
B.1 Additional Results for Q1
Tables 11 to 13 report additional results for Q1 including two additional models and metrics. The additional models are: "CBNM noent", which is identical to CBNM except it does not include any entropy term; and CENM 20 which is regular CBNM for which 20% of the concept combinations (c.g.. pairs of digits MNIST-based tasks) receive full supervision. The metrics include label aceuracy Accy, concept accuracy Acce, inference layer accuracy (c)( and negative log-likelihood, all evaluated on the test set.
Table 11: Complete results for MNIST-Add.
METHOD
Aony
FL(Y)
Aoee
(C)
(l)
(L
Ace(
NLL
DPL
+
0.98 +
0.99
0.99 0.01
0.01 0.01
CENM
+: 0.01
0.98 + 0.01
0.99
0.01
0.99
0.01
0.01 0.01
1.00
1.00 +
0.11
0.01
CBNM nocat
0.98 + 0.01
0.98 + 0.01
0.80
0.10
0.74 0.13
0.08 + 6.04
0.37 - 0.09
0.42 + 0.06
0.26 = 0.01
CENM
+ 0.01
0.98 + 0.01
0.99
0.01
0.99
1 0.01
0.01 0.01
0.02
+ 0.02
0.70
0.02
CBMM 20 noent
0.92 1 0.02
0.94 1: 0.01
0.60
1 0.09
0.48 0.10
0.22 0.12
0.02 1 0.01
0.12 1: 0.02
1.09
0.01
DSL
0.96 + 0.02
0.96 1: 0.02
0,98
0.01
0.98 0.01
0.01 0.01
1.00 2 0.01
1.00 + 0.01
0.38
0.14
DPL
0.90 = 0.09
0.91 + 0.09
0.93
0.07
0.92 0.08
0.01 0.00
1.90
0.90 = 0.09
0.02
0.01
bears"
0.81 + 0.12
0.76 0.15
0.87
0.12
0.873
0.01 0.01
0.67 0.14
0.63
0.10
0.34
0.22
1: 0.01
0.97 0.01
0.84 +
0.80 0.07
0.01
0.08
d: 0.08
0.01
Table 12: Complete results for MNIST-SumParity
METHOD
Accy
Fi(Y)
Acce
Fi(C)
Cls(C)) (4)
(G)
Acc(
NLL
DPL
0.99 a: 0.01
0.99 1: 0.01
0.47
0.04
0.43 1. 0.08
0.36 à. 0.15
0.33 &. 0.01
CBNM
0.90 + 0.18
0.90 0.18
0.21 = 0.06
0.09 1 0.03
0.66 :: 0.09
0.54 2: 0.04
0.21 0.06
0.52 =: 1.04
nocuE
0.01
0.01
0.72
DSL
0.94 + 0.03
0.94 0.03
0.20 0:01
0.07 + 0.01
0.80 0.00
0.52 2 0.01
0.51 0.02
0.29 + 0.16
bears"
0.99 4 0.01
0.99 0.00
0.28 = 0.05
0.30 + 0.03
0.22 0.00
0.36 = 0.09
0.37 0.09
0.04 = 0.01
SEW!
0.99 4: 0.01
+
0.53
0.49
0.01
0.53 0.06
0.53
0.01
Table 13: Complete Results for MMIST-SumParity biased.
METHOD
Accy
Fi(Y)
Accc
FC(C)
Cls(C)
(()
Acc(8)
NLL
DPL
0.99 + 0.01
0.99 + 0.01
0.65
0.05
0.59 0.06
0.08 0.07
0.06 = 0.01
CBNH noeas
0.99 + 0.01
0.99 1: 0.01
0.22 : 0.01
0.08 +: 0.02
0.76 0.06
0.52 4: 0.04
0.32 4: 0.04
0.05 = 0.01
CBNM
0.99 + 0.01
0.99 + 0.01
0.21
= 0.01
0.07
0.80 0.01
0.51
0.01
0.32
0.01
0.07 = 0.04
CBNM 20 noent
0.99 + 0.01
0.99 0.01
= 0.22
0.22
0.07
0.01
0.80
0.49
0.48 = 0.04
0.04
0.01
DSL
0.94 1 0.03
0.94
1 0.03
0.20
2 0.01
0.07
0.01
0.80 0.01
0.02 4 0.01
0.00
4 0.02
0.29 = 0.16
0.01
0.20
0.04
0.04
0.04
B.2 Additional Results for Q1: The BDD-OIA Task
Experimental setup. BDD-OIA is challenging real-world learning task with 21 binary concepts and, unlike in Clevr, these cannot be decomposed into unary predicates. Moreover, each concept cannot be separately assigned to individual actions as done for DPL [22], as this would introduce a negative bias in the learned solutions, effectively forcing the model to use fixed concept budget per action without interference. Due to scalability constraints, we compared only DPL and CBNM, as implementing DSL DPL would require allocating at least four tensors of size 221 which exceeds our available computational resources.
Results. The results for DPL and CBNM are reported in Table 14. Both competitors perform sub- optimally on BDD-OIA, as expected given the challenging nature of this task: DPL scores around 70% Fi (Y) while CBNM only 62%. Perhaps surprising, CBNM does not collapse concepts together and tends to use most of the concept bottleneck across the test set (Cls(C) 0.06). Despite the lack of collapse, both architectures are far from attaining the intended semantics, with F (C) scores of 44% for DPL and 43% for CBNM. Additionally, CBNM deviates from the ground-truth knowledge achieving low Fi (B) of around 42%. The low collapse for CBNM may be due to the trained model
25

---

being far from optimal. We hypothesize that adding sparsity penalty to the linear layer of CBNM would substantially increase concept collapse, but we leave a detailed examination future work.
Table 14: Results for BDD-OIA.
METROD
Fi(Y) (t)
Fx(C) (f)
(l)
(1)
DPL
0.69 = 0.03
0.44 4: 0.01
0.88 è 0.01
B.3
Additional Results for Q3
Here we show the effect of traditional mitigation strategies on MNIST-SumParity and Clevr as concept and knowledge supervision increase. As discussed in Section 5, traditional strategies have limited impact, with the exception of concept supervision.
0% K-sup
F1(C)
(((
Cis(C)
20% k-sup
0.75
k-sup
60% k-sup
80% k-sup
0.25
100% k-sup
Entropy
Reconstruction
20
40
80
100
0
20
40
80
100
0
20
40
60
80
100
Contrastive
C-SUP (%)
C-SUP (%)
C-SUP (%)
H+C+R
Figure 5: Fig. 3 with standard deviation over 5 seeds
1.00
C2(C)
Fi(
Cls(C)
0.75
0% k-sup
0.50
50% k-sup
0.25
100% k-sup
Contrastive
0.00
0
50
100
0
50
100
0
50
100
C-SUP (%)
C-SUP (%)
C-SUP (%)
Figure 6: Effect of standard mitigation strategies evaluated for CBNM on Clevr, with standard deviation over 5 seeds. We evaluated only the contrastive strategy as it performed best. Since supervising all knowledge infeasible, we observe that for sampled configurations (leading to
out-of-distribution settings), the leamee knowledge does not generalize.
B.4 Concept Confusion Matrices and Learned Inference Layers
Here, we present the concept and knowledge confusion matrices for different datasets and models to show examples of joint reasoning shorteut solutions that they learn.
Figure 7: Concept confusion matrices for CBNM on MWIST-Add and the corresponding learned inference layer. Left two matrices: concepts and knowledge before alignment. Right matrices: same but after alignment. The learned inference layer is visualized as a colored matrix where the numbers in the cells indicate the model's predictions.
26

---

Figure 8: Concepts and inference layer learned by CBNM on Sunaart before (two left) and after (two right) the post-hoe alignment step. For concepts, report the confusion matrix. For the inference layer, we visualize the learned operation as truth table: numbers within cells indicate the label predicted for each combination of predicted digits.
CBNM
DPL
DPL
MNI STT Add
MNIST Sammaammttt
Figure 9: Concept confusion matrices for WWIST-SumParite All models tend favor a's that collapse concepts together, hinting at simplicity bias.
B,5 Number of Reasoning Shortcuts and Joint Reasoning Shortcuts
Here, report the approximate number of deterministic reasoning shortcuts and joint reasoning shortcuts for MNIST-Add and count-rss software included in rsbench [22] to the enumeration of JRSs, compatibly with Eq. (7) and Eq. (6).
We obtained these numbers by extending the
We considered downsized versions of both MKIST-Add and MMIST-SumPare restricted the range (O,..., NV. and resorted to the approximate model counter approxMC [107] for obtaining approximate counts in the hardest cases. All counts assume object independence is in place (i.c., that the two input digits are processed separately), for simplicity. The situation similar when this is not the case, except that the all counts grow proportionally.
with input digits
The number of RSs and JRSs for increasing N reported in Table 15. Specifically, the #RSs column indicates the number of regular RSs obtained by fixing the prior knowledge (that is, assuming = (3') and matches the count [19] for the same tasks. The #JRSs columns refer to the CBM case, where the inference layer is learned from data (i.e., 33 might not match (²*). We report two distinct counts JRSs: one assumes that Hts that match on all concepts actively output by a should be considered identical despite possible differences on "inactive" concepts that a predicts as constant (#JSSs con-redundant) or not (# JRSs).
As can be seen from the results, JRSs quickly outnumber regular RSs as N grows, as anticipated in Section 3.1. This suggests that, as expected, learning CBMs with intended semantics by optimizing label likelihood is more challenging when prior knowledge is not given a priori.
27

---

MWIST-Add
RMIST-SumParls
Concapts
88
SENN
Figure 10: Concept confusion matrices for SENN on MNIST-Ade Add and SELSTTSumParity. SENN provide local explanations for individual predictions, as their inference layer depends the input and does not yield a global, interpretable rule set. No simplicity bias is evident in these two confusion matrices; hypothesize that this stems from the models flexibility in modeling local rules and from the reconstruction penalty applied to the concepts during training.
Table 15: Number of RSs vs. JRSs in MMIST-SumParity
(non-redundant)
(1.10 = 0.00) x 10'
(3.84 x 10a
(1.20 - 0.00) 10'
(6.30 1 0.00) x 10
(1.11 x
(1.27 0.06) x 102
(3.70 - 0.15) x 10a
(1.16 x 10
(1.40
10a
(2.98 0.10)
10a
(4.15 10
(1.74 0.13)
10a
(2.56 + 0.26)
X 10a
(8303
10th
(2.61 0.14)
10
8
(2.62 + 0.15) x 10
(5.39 + 0.225)
x 10
(4.21 + 0.10)
10"
C Theoretical Material
In this section, start by summarizing the prerequisite material. We begin by recalling central Lemma proven in [19] that allows us to write the condition for likelihood-optimal models in terms of a. For case of comparison, Iet p(C X) f(X) and p(Y X) (w o f)( denote the
conditional distributions defined by the CBM (f, w) E Ω and:
p(Y G) (x)))( ( x)]
(14)
Also, we consider the following joint distributions:
(X, Y) (Y X)p' (X), p(X. Y) P Xx)
(15)
Lemma C.1 ([19)). It holds that: (i) The true risk of p can be upper bounded as follows:
E (x.) log x)] KL (X: Y) p(X, Y)j H(p" (X, Y)Il
(16)
<Eg-M() KL (Y g: P g)l H(p'(Y
g: K)])
(17)
where KL is the Kellbackk-eiible divergence and H is the Shannon entropy. Moreover, under Assumptions 3.1 and 3.2, p(Y X; K) an optimum of the LHS of Eq. (17) if and only p(Y G) is an optimum of the RHS. (ii) There exists bijection between the deterministie concept distributions P(C X) that, for each g E supp(G) G), are constant over the support of p" [X g) apurt for zero-measure subspaces X C supp(p"((X (X) and the deterministic distributions of the form C(C |G).
1g)
Point (i) connects the optima of the likelihood p(Y X) and the optima of y G). This implies that, under Assumptions 3.1 and 3.2, knowing the optima of ( G) informs us about optimal CBMs p(Y X). Notice that single (GG) p(C G) might correspond to multiple
28

---

choices of f E F. However, by (ii), if we restrict ourselves to deterministic distributions p(C G). the correspondence with distributions p( X) that are almost constant in the support becomes one-to-one.
Next, we descrihe which distributions p Y G) are both deterministic and thus comply with (ii) and optimal.
Lemma C.2 (Deterministic optima of the likelihood), Under Assumptions 3.1 and 3.2, for all CBMs
(f.w) E F x Q where, for all g E G. f x + с is constant over the support of p' (X g) apart for a zero-measure subspace X C supp(p" (X g)), it holds that the optima of the likelihood for p(Y G) are obtained when:
Vg E supp(p" (3 (g) = = Here, agg) = Ex (Xig) [f(x] E Vert(A) and B(c) w[[C c}) E Vert(B).
(18)
Proof. Notice that by Lemma C.I. it holds that a E (A) is deterministic conditional distribu- tion. Since f: x - с constant over all x ~ p*(X (X g) for a fixed g G. it holds that f(x) ag)
apart for some x in measure-zero subspace X C supp(p" (X g)). Therefore we get:
E Ex~p' (Xig)
= w(a(g)) = (3 o (g)
(19)
In the last line, we substitute w with /3 since a is deterministic. For p(Y | G), the necessary and sufficient condition for maximum log- logelikel is:
(G)), Vg E supp(y" (G)), p(Y g) = (g)
(20)
and substituting Eq. (19) we get:
Vg E supp(p" (G)), (8 (g) (g)
(21)
This proves the claim.
C.1 Equivalence relation given by Definition 3.3
We start by proving that Definition 3.3 defines an equivalence relation.
Proposition C.3. Definition 3.3 defines equivalence relation ~ between pairs (a. B), (a', E A x B. as follows: (ax, B) (a', (²) iff there exist a permutation π [k] - [K] and l element-wise invertible functions 11, ...... 1/k such that:
Vg E G, a(g) op o a')
(22)
Vc E C, B(c) (3' o 2/ 1 P (c)
(23)
where P,, C C the permutation matrix induced by æ and vb(c) == ...,
Proof. It useful to analyze how Pa and ub are related. Let for any c E C:
(P= o (c) = (c)), ...: (he(cr)) (W=())(<()))..... (C(R)(((()))
(24)
(25)
Using the shorthand (c) = (1) ()(()) (c+)). we have that:
(P, (b) (v,, (c)
(26)
From this expression, notice that for all c E C it holds that:
(Px o (c) = (P, o v P-1 (c)(c)
(27)
(vb (c) ((P x th o poP p p)))ppP)))) (c)
(28)
so that we can equivalently write v, := P, o 2b P Reflexivity. This follows by choosing P id and similarly v/ id for all i [R].
Symmetry. We have to prove that (a, B) (a' = (a' ~ (a, Since (a, (8)
(a', ("), we can write a in terms of a' as follows:
ag (P, st 2 (g)
(29)
= ( o P, o (g)
(30)
29

---

where in the last step we used Eq. (26). By first inverting 1i and then Px, we obtain that:
a'g)) = (P-' কे ag)
(31)
The inverses exist by construction/ddefiittoon Showing the symmetry of a. With similar steps, we can show that similar relation also holds for B", that is for all E C:
3((c) = (3 v o Px)(())
(32)
Transitivity. We have to prove that if (a. 33 (a', 3") and (a', B¹) (B) then also (a, (3) ~ G²). We start from expression of and a', where we have that Vg E
(gg = (Px o 2 (g)
(33)
a' (g) (P w a (g)
(34)
We proceed by substituting the expression of a' in to obtain:
(g = (P, o o o P o rp' ao (g)
(35)
= (P, o P 3 o
P
o o a (g)
(Composing P., with the identity P.. o P
(P, o x Ua
(g)
(Using that uh 1 P vb P pr)))
= -Par ab o (g)
(36)
where we defined Pat = PT o px and tbt = 1/ -1 o up. With similar steps, we obtain that , can be related to Bi as:
B(c) ( vb (c)
(37)
for all c E C. This shows the equivalence relation of Definition 3.3.
We now prove how solutions with intended semanties (Definition 3.3) relate the optima of the logllikelihood:
Lemma C.4 (Intended semantics entails optimal models). Ifa pair (a, () E A x B possesses the intended semantics (Definition 3.3), it holds that:
Vg 9, (Boa) (r)
(38)
Proof. By Definition 3.3, we can write:
a(g) = (Pr o vp id)
(39)
B(c) (g + P P
(40)
Combining Eqs. (39) and (40), we get, for all g G. that:
()) = (8* P tb o 2b Pz)(g)
(41)
(B" P Pg))
(42)
3
(43)
yielding the claim.
C.2
Proof of Theorem 3.6 and Corollary 3.7
Theorem C.S. Let = UZ } be the set of cardinalities of each concept G C G and msG denote the multi-set msg := (( m(Gg.)), E [k]}, where m()) denotes the multiplicity of each element of sG. Under Assumptions 3.1 and 3.2, the number of deterministic JRSs (ax, B) Vert(A) x Vert(B) amounts to:
Σ
11
(B00)(g)= = -(g)
(44)
(A.)) gEsupp(G)
where C(G) is the total number of pairs with the intended semantics, given by C(G] := Iseeg mff!x
I !
30

---

Proof. Since we are considering pairs (a. E Vert(AA) x Vert(B), a defines (deterministic) function G - C and that, similarly. 3 defines (deterministic) function | C. V. In this case, G o G - )' is a map from ground-truth concepts to labels. We start by Definition 3.3 and consider the pairs that attain maximum likelihood by Lemma C.2:
Vg E supp(>" (G)); (g (g) (g)
(45)
Since E Vert(A) is deterministic, we can replace w with B. Since both Vert(AA) and Vert(B) are countable, we can count number of pairs that attain maximum likelihood as follows:
Σ
1 A
(Boa) 3 (g))
(46)
(a..))Veer(A)VVen(B)) gésupp(r"(G))
where, for each pair (a, E Vert(A) x Vert(B) the sum increases by one if the condition of Eq. (45) is satisfied.
Among these optimal pairs, some possess the intended semantics and therefore do not count as JRSs. By Lemma C.4, these correspond to all possible permutations of the concepts combined with all possible element-wise invertible transformations of the concept values.
We begin by evaluating the number of possible element-wise invertible transformations. The i-th concept can attain [Ge] values. The overall number of possible invertible transformations then given by the number of possible permutations, resulting in total of [Gil! maps. Hence, the number of element-wise invertible transformations is:
II |9
(47)
Next, consider what permutation of the concepts possible. To this end, consider the set and the multi-set comprising all different G3 cardinalities given by:
Gg = U (1 1=1
msg = [((1s) m()))) i [K]]
(48)
where m))) counts how many repetitions are present. When different G, and Gj have the same cardinality, we can permute G, and G, without compromising optimality, as there always exists a 3 that inverts the permutation and thus provides the same output. Thankfully, this shows in the multiplicity m(.) and we can account for this. Therefore, for each element { E ag we have that the total number of permutations of concepts amount to:
(e = II m(E)!
(49)
EEAG
Putting everything together, we obtain that the number of optimal pairs possessing the intended
semantics is pG) I [iil, meaning that the total number of deterministic JRSs is:
k
11
A
(Boa)(g) = =3² perm x II
(50)
(a x gEsupp(p-(GG)
yielding the claim.
Corollary 3.7. Consider fixed 8 E Vert(B). Under Assumptions 3.1 and 3.2, the number of deterministic JRSs (a, 3") E Vert(A) x Vert(B) is:
EaevertiA) ((AgGsupp(c) (3" e ax)gg) (g) -
This matches the count for deterministic RSs in [19].
Proof. The proof follows immediately by replacing Vert(B) with {8*}, allowing only for the ground- truth inference function. this context, by following similar steps of Theorem 3.6, we arrive at similar count to Eq. (46), that is:
Σ
I A
(Boo)(g)= = (r
(51)
(cc, (e. gEsupp(p"(G)
In the context of regular RSs, the only pair possessing the intended semantics (id, which has to subtracted from Eq. (51). This proves the claim.
D
31

---

C.3 Proof of Theorem 3,9
Theorem 3,9 (Identifiability). Under Assumptions 3.1 and 3.2, the number of deterministic JRSs (Eq. (6) is zero then every CBM w) E F x Ω satisfying Assumptiio 3.8 that attains maximum log- likelihood (Eq. (4) possesses the intended semantics (Definition 3.3). That is, the pair (a. (3) E Ax
entailed by each such CBM is equivalent to the ground-truth pair (id, B²), i.e. (a.
3").
Proof. Consider a pair (a. (3) probability distributions.
B, where both a and 33 can be -on-determiiistic condittoo conditional
Step (i). We begin by first recalling Lemma C.I. Under Assumptions 3.1 and 3.2, a CBM w)) FF x Q is optimal, i.e., it attains maximum likelihood, if it holds that:
Vg E supp(p" (G)), (Xlg) fx)] = (g)
(52)
Notice that, according Assumptions 3.1 and 3.2, it also holds that the labels must be predicted with probability one to attain maximum likelihood, that is:
Vg E G, max 3* (g) =
(53)
Now consider pair (a,3) E AAx B. By Lemma C.1 (i), it holds that to obtain maximum likelihood, the learned knowledge 3: C Ay must be deterministic:
max =
(54)
which implies that, necessarily, for 3 to be optimal the space B restricts to the set Vert(B), so any learned knowledge /3 must belong to Vert(B). This shows that optimal pairs (a,, belong to A x Vert(B).
Step (ii). Next, we make use of Assumption 3.8 and consider only inference functions w that satisfy it. We start by considering pair (a', b') Vert(A) x Vert(B) that attain maximum likelihood, that is, according to Theorem 3.6:
Vg E supp(y"(G)), (b' o o') = 3r)
(55)
Now, given b' E Vert(B), we have to prove that non-deterministic maximum likelihood for any of the w' E Ω that correspond to b', that is, such that w' (I{C = c}} = b'(c) for all c C. Since A is simplex, we can always construct non-deterministic conditional probability distribution a E A from convex combination of the vertices a, E Vert(A), i.e., for all g G it holds:
A \ Vert(.A) can attain
α (g)
Σ
(ga
(56)
()EVe))(A)
Consider another a" A a' Vert(A) and consider an arbitrary convex combination that defines a non-deterministic A:
Vg E G, agg) == Aa' + (1- (1--)aa A))"(()
(57)
where E (0, 1). When the deterministic JRSs count (Eq. (6)) equals to zero, we know that by Theorem 3.6 only (a', b') attains maximum likelihood, whereas (a", b') is not optimal. Therefore, there exists at least one g E supp(p" (G)) such that
(B' a²) (g) + (G' ag)
(58)
We now have to look at the form of f that induce such non-deterministic a Aa' + (1 \)a" Recalling, the definition of a (Eq. (2)) we have that:
ax (g) Ex-p (xlg)((()))
(59)
>a) + +1 A)a
(60)
For this a, there are two possible kinds of E F that can express it.
(1) one case, we can have f R²n - Vert(Ac) - mapping inputs to "hard" distributions over concepts. Since a is not "hard" distribution (provided X E (0, 1)), f(x) must be equal to a' (g)
for a fraction of the examples x E supp(p" (X g)) and to a((g) for fraction of In that
case, it holds that there exist a subspace of nanissnig measure X" C supp(p" [X] ğ)) such that
32

---

f(x) = a" (g). Therefore, for all X E X" we have that (b' o (x) = (wo aa) # (g). and such an is suboptimal.
(2) The remaining option that f: RR + Ac | Vert(Ac). In light of this, we rewrite as follows:
Vx E supp(p" (x g)). f(x) =
Σplc x)4[C=0 = =c}
(61)
cEC
where p(c x) := c( Let é' := (g) and é" (g). But a is a convex combination of a' and a". hence the function f must attribute non-zero probability mass only to the concept vectors è' and c". Hence, we rewrite it as:
E S supp(y" (x g)), f(x) = p(e' b + p(c" |x)[CC = =²")
(62)
where X has measure one. Notice that in this case it holds argmax b'(é's +
argmaxyel b'(é")y. y-- By Assumption 3.8 we have that, for any choice of X E (0,1) it holds that for all x E X:
maxw(p(c' x)][C= = c'} + +pc" |x) = c"})) < max(argmax b' (C(')) argmax b' (c")y)
yey (Using the condition from Assumption 3.8)
yey
=1
(63)
where the last step in Eq. (63) follows from the fact that b' E Vert(B)) so giving point-mass conditional probability distributions.
(1) and (2) together show that any E A Vert(A) constructed and an a" A a' cannot attain maximum likelihood. Hence, the optimal pairs restrict to (a, 3) e Vert(A)) (A) x Vert(B) and since the count of JRSs (Eq. (6)) is zero, all (a, A x B that are optimal also possess the intended semantics. This concludes the proof.
convex combination of a'
D Impact of mitigation strategies on the deterministic JRSs count
We focus on how the count can updated for some mitigation strategies that we accounted for in Section 4. We consider those strategies that gives constraint for the Eq. (6), namely: multi-task learning, concept supervision, knowledge distillation, and reconstruction.
D.1 Multi-task learning
In the following, we to indicate additional learning task with corresponding. Suppose that for a subset GT S supp(p" (G)), imput examples are complemented with additional labels y", obtained by applying an inference layer 3K- (g). Here, KT is the conjunction of the prior knowledges for the original and additional task, and yields a set yr of additional labels when applied to the examples in g". To understand how multi-task learning impacts the count of JRSs, we have to consider those G: y' x yr, where a component By maps to the original task labels Y and the other component By- maps the augmented labels Y Let B = B B the space where such functions defined. As obtained in [19], the constraint for pair (ax, E Vert(AA) x Vert(B*) can be written as:
1 1(Ageg- (By- o a) (ggg = AK- (g)}
(64)
This term can be readily combined with the one appearing in Theorem 3.6. Doing so, reduces the
number of possible maps a E Vert(AA) that successfully allow function 3 B to predict both (y.y") consistently. Notice that, in the limit where the augmented knowledge comprehends enough additional labels and the support covers the whole, the only admitted solutions consist of:
(Byr o id) = (By- o
(g)
(65)
for all g E G. where Φ G - C is an invertible function. This shows that a can be only bijection from G C. Provided all the concept vectors g E G, the number of such possible o's amounts the number of possible permutation of the | elements, that is !
33

---

D.2 Concept supervision
The intuition is the same as in [19]. Assume that we supply concept supervision for a subset of
concepts Gr S G, with I S [k] and pair the regular likeliooddo objective over the labels with a log- loglliilihood over the concepts, i.e., Dier log po (C, = 9i x). Let g - supp(p" (G)) be the
subset of values that receive supervision. The only deterministic a's 's that attain maximum likelihood on the concepts are those that match said supervision, i.e., that satisfy the constraint:
MAgese Asez (5) 9i)
(66)
This can be immediately used to obtain an updated (and smaller) JRS count. Note that if [K] and G G. then the only suitable map is a = id. Naturally, this requires dense annotations for all possible inputs, which may be prohibitive.
D.3 Knowledge distillation
We consider the case where samples (g.33" (g)) are used to distill the ground-truth knowledge. Since by Assumption 3.2 the ground-truti inference layer deterministic, we consider the following objective for distillation. Letting GK C supp(p" (G)) be the subset of supervised values, we augment the original likeliiid objective with the following log- likeliiei term:
Egegi log (I[C (g))
(67)
which penalizes the target CBM, for each g E g based on the (g) component of w, i.e. the predicted probability of the ground-truth label. This can be rewritten as a constraint on B as follows:
LLAREGK B(g) (g))
(68)
When gx = G it necessarily holds that 3 = 3"
D.4
Reconstruction penalty
When focusing on reconstructing the input from the bottleneck, the probability distributions p(C X) may not carry enough information to completely determine the input X. In fact, if X depends also on stylistic variables S E RR, it becomes impossible to determine the input solely from G. This means that training decoder only passing e p(C X) would not convey enough information and would reduce the benefits of the reconstruction term. Marconato et al. [19] have studied this setting and proposed to also include additional variables E IR9 in the bottleneck to overcome this problem. The encoder/decoder architecture works follows: first the input x is encoded into p( C, Z x) by the model and after sampling (c, 2) ~ p(C, Z x) the decoder d reconstruct the an input image x d(c, z). Following, under the assumption of content-style separation, i.c., both the encoder and the decoder process independently the concept and the stylistic variables, it holds that the constraint fr maps E Vert(A) given by the reconstruction penalty result in:
(69) The proof for this can be found in [19, Proposition 6). Notice that, with full support over G, the only such maps a must not confuse one concept vector for another, i.e., at most there are at most ! different valid a's o's that are essentially bijection from G to C.
L(Ag. (e.x''suup())) (g) # a(g'))
E
Models that satisfy Assumption 3.8
E.1
Theoretical analysis
Probabilistic Logic Models. For models like DeepProbL.og [41], the Semantic Loss [39], Semantic- Probabilistic Layers [44], w is defined as:
w(p(C)) = E -c)
(70)
EEC
Now, take c, c' E such that: B(c) * 3(')). Then, for any X E (0. holds that:
w(Al(C = - C) c')) A3(c) + (1 x)B(c')
(71)
- m (1- c')) =ax max (AB(cly (1- -))(((())))))))
(72)
yey
34

---

Notice that for all y E E, by the convexity of the max operator it holds that:
max (A3(cly + (1 a)3(c')x) -
(73)
yey
Amax
yey Blccy may B(c))s (y) (1- max yey Blc)y, max B(c')y)
(74)
-max (max(((c)) max ((c))x) yEy
(75)
Equality holds if and only if argmaxye) B(c)y = argmaxye> yey B(c')y and maxyey (ccy = maxyey ((c')y- This proves that probabilistic logic methods satisfy Assumption 3.8.
Deep Symbolic Learning [50]. At inference time, DSL predicts concept vector C from conditional probability concept distribution, that is, implements function D : R" + where:
(DSL()) argmax p(c x)
(76)
cEC
and pCC X) is a learned conditional distribution on concepts. (Note that f DSL (X) # P(C X).)
Hence, A can be defined as:
(g = Ex~ (Xig) [1 = f (x))())))
(77)
Notice that the learned 3: 9 + Ay consists look up table from concepts vectors c C, thereby giving the conditional distribution:
PDSL. ( g == Exxp (8() (s(
(78)
By considering the measure defined by px((x g) and the transformation fDSL (D))(x), we can pass to the new measure p(c g) = agg) obtaining:
PDSL
g) Σ
B(c)p(c
(79)
eEc
=Σ B(c)a(()
(80)
= (w (g)
(81)
where we used:
wDsL(p(C)) = Σ 3(c)p(C=cc
(82)
CEC
This form matches that of probabilistic logic methods Eq. (70), hence Assumption 3.8 similarly applies.
Concept Bottleneck Models. We consider CBNMs implementing a linear layer as w Ae y. as customary [3]. The linear layer consists of matrix W E Raxb with := [g] rows and : [}] columns. In this setting, probability distribution p( C) E Ac corresponds to the input vector passed to the inference layer w, implemented by the linear layer W and softmax operator. Notice that we can equivalently consider the tensor associated with the linear layer, w.., where lower-indices (c),-.. (k) are the possible values of concepts and higher-indices y (U1...., -Be) are the possible values of the labels. The scalar index e (resp. y) runs over concept vectors c E (resp. y), e.g., for two dimensional binary concepts, = corresponds to (0, 1) E (0, (W 1, = w and c 2 to (1 (W2.- w In the following, we make use of the tensor notation for simplicity exposition.
Given a concept probability vector E Ac, with components Pe = p(C = c), the conditional distribution over labels is given by the softmax operator:
exp Eeec We,PP.)
exp EoEc w.Y
p(y c) w())y Ey'ey exp EEse Wey'P.) Eyeyy exp EcEc w Pe)
(83)
CBMM may not satisfy Assumption 3.8 for arbitrary choices of weights W. Notice also that, since includes softmax operator, the B E Vert(B) expressed by CBNMs cannot be deterministic. 6 This is a
'I fact, attributing near 1 probability to label Y is only possible if the weights are extremely high in magnitude.
35

---

limitation for all CBNM. Specifically, in the context of Assumption 3.2, it means that they cannot reach an optimum of maximum likelihood and therefore learn deterministic maps 3 E Vert(B) (Eq. (8))
To proceed, we focus on a special case: a near-optimal CBNM that can express an "almost deterministic" conditional distribution ,3 E B, where subset of weights w is very high very low. For this to happen, we need [ to be peaked on concept vectors с E C. This can happen only when the magnitude of one w is much higher than other w Hence, we formulate the following condition for CBNM:
Definition E.I. Consider a CBNM w) E F Zt with weights W { J and let M > 1 1/. We say that it is log(M (M) -deterministic if. for all c E C, there exists a y E y such that:
Vy' * y, w. w 2 llog M
(84)
Vy' # y, Vy " 7 y, |w w S log M
(85)
This is helpful, as any log( ( determiiisic CBNM can flexibly approximate deterministic B²s, as we show next: Proposition E.2. Consider log( M) deterministic CBNM (f, w) E F x S. We have:
1
Vc E C, max yey
(c)y 2 + (()) 1)/M
(86)
Also:
EC lim max wccly = 1 M-+000 YE
(87)
Proof. For c E C, let = argmaxy w = We consider the expression:
exp w
[1[[==)) Eyecc exp w
(88)
(89)
1+ EyEy expl -wo + w
We now make use of the fact that the CBNM is log(M detterministi and use Eq. (84) to obtain:
(90)
1+ Ey - ww'')
1 Ey' exp(- log M)
(91)
Ex'ty I M
1 1 +
(92)
Putting everything together yields:
1
max ((yy 2 yEy
(93)
1 (1D) 1)/M
Now, consider the limit for large M E R:
1
lim max M yEy
w(cy 2 lim
M + 1 ((V) - 1)/M =1
(94)
This concludes the proof.
The last point of Proposition E.2 shows a viable way to get peaked label distributions from a log(M).
deterministic CBNM. Specifically, the limit guarantees that these CBMMs can approach an optimal likelihood. Now, we prove that a log (M))MMddterrminist
CBNM respects Assumption 3.8. Proposition F.3. CBNM (f,w) E F Ω that is log( (M) deterrminisic (Definition E. satisfies Assumption 3.8, Le., for all X E (0, 1) and for all e & e' such that argmax w w(1 (1(C== =c] #
argmaxyeyi w (1 c' it holds:
max max (A yey
= ca))y < max (maxw(1[C-- = yey
(0((C=c)))] cilly; max w c2) yey
(95)
36

---

Proof. Let Y1 == argmaxyeD w1fC = c1 fl and Y2 == argmaxye) w(ffC = c2 and A1 := x and X2 := 1 - X with À E (0, and yı # Y2. The proof consists of two steps.
First, we check that the values taken by w(AI(C c1 + X)IKCC cz))y, for E (1,2), lower than those taken at the extremes. The explicit expression for w(-),, is given by:
e exiwot +22w2y
w = ci} + Aa = c2))y, = Eyey ed: we tdgwoz
(96)
We differentiating over X, leveraging the fact that 0 and 022/01 1. Let Z(A)
Eyey exp(>i w + >2wwz,). We first evaluate the derivative of this expression:
02(1)
2
=
Σ
A wa t2am2
(97)
0A
yEy
Σ
e
AIwa +22w2, ( + +
(98)
yEy
Σ
ALWEy +dow's (w:)
-w
(99)
yEy
A.WA +.2
= ((1))
Σ
(w.) c1
ww
(100)
Z(A)
yEy
= ((A) yEy
Σ (w2.
c2)ly
(101)
This is legitimate as (AA > 0 by definition. Using this result we get:
① ediwel
+haw23 E1w thawo's Z(A) - exiwei + 0 Z(A)
(102)
0x
Z(A)
Z(A)2
exttwot thawoo
(wor)
w (1))
2(2)²
@diwe]]
+haw?? 7(A)
Exer (wY, - - =c]] + +21(CC = =c2lly
(103)
Z(A)2
(W2) +hgwo 1mmtyo
wir))
Z(A)
+haw (wr
Eyer(w (wv .wy Ae
(104)
Z(1)
+ (ww
((we) - w Eyey (w - [[C
+ co)ly))
Z(A)
(105)
Next, we analyze the sign of the derivative. Notice that we can focus only the following term since the others are always positive:
(w cj
w.y
Σ (w>y - WW, = c. + A21(CC = c2lly
(106)
yEy
From this expression, we can make use of the fact that in general, for a scalar function f(x), we have Ex] I maxx (x) and consider the following:
(WY)
wX!) Σ (wy,
- c1} 22 =ca))y
yEy
2 (WY) w --amaaaww w - -Wx) yEy
(107)
(wY) wV:) (W wX!))
(108)
(109)
37

---

where in the second line we used that the maximum is given by Y1. Therefore, the derivative is always increasing in the [0, 1] interval, meaning that:
AY E 1], w(A = c1} + X21{C = cally, Sw(4C= = cilly,
(110)
where the equality holds if an only if À = 1. Similarly, the derivative for w(-)y; gives:
(w1 c1 + A21((C = c23)y²
0X Aiwey +hwe++haw' ((wor w Eyee((w W = + - c2]ly)
Z(2)
(111)
By using the fact that Ex[ 2 minx fxx) for scalar function f(x), we obtain:
(w
w
w
w c1} + Aa1fC co)ly
yEy
S (w 01
w minn(w - w yE)
(112)
(w
w
(w w
(113)
(114)
where in the second line used that the minimum is given by y2. Hence, the derivative is always
decreasing for E [0, 1] and it holds:
AA 1], wA = c1) + = cally, S [w([C== = =22)ly2
(115)
where the equality holds if and only if X = O.
(2) Now, we check the same holds when choosing another element y' * Y1. To this end,
consider the following expressions:
ply 111[C c1) + 1=1[C== =2))), ply A1 =1 + c2))
(116)
p(y, c1)
ply² C2)
where p(y p) == w (p)y. Consider the first expression. We can rewrite it as follows:
ply 1 = c + [a([=cc]] =
(117)
ply, C1)
ply A = c1} + A²1(CC = c2)) ply, M = c1} + +221/CC c2))
(118)
ply, A, c1) xx1[C c2))
ply, c1)
p(y A1[[C= = c1 xx
< ply, A1 c A2 =
(119)
=ca)) c2))
where in the last line we made use of the fact that the second fraction in the right-hame side of the first line is always < 1. Similarly we have that:
ply A MMC C = ci A2 = c2))
ply [ +.
(120)
ply, C2)
ply2 c.][C=c))+++]([C
We proceed to substituting explicitly the expression for ply M11[C c1 A21ICC c1) into the upper bound of Eq. (119):
ply A C[C c1} + 121 = c2))
Aawa Haw 7(A)
(121)
ply1 11 = c1) Aa1(C c2))
elwwl +haw Z(2)
=xx (A1 Aww wXy) + >e(wW wWy))
(122)
< expp ( A1 log(M) + >y(wY -wY:) ))
(Substituting the bound from Eq. (84))
< <exp ( A₁ log(M)) ())++ A log(M))
(Substituting the bound from Eq. (85)
M A
(123)
38

---

With similar steps and substitutions we get that:
ply X 1[C = c1) + x2 = c2))
I <Mar
(124)
ply21 A 11 = c,) + +2
Taking the product of Eq. (123) and Eq. (124) we obtain:
p(y 2, = c1 + x,1[C=== = ca)) ply A 1 01 +g c2))
ply1 1 A1 = c + A21[C C c2)) A
ply2 x = c1 x21lC = c2))
S M -a- ~1
(125)
=1
(126)
Notice also that:
+21[C +
ply t | = c1 +
ply [1][
ply + +x][(c==3] p(y;
ply, [1
+ +1([C x1[[C== -2
min
p(y1 1] -10 + - ply |1([C=
p(y2 x1[[[= -
c] +2,(([ = c2))²
o2))2
(127)
c²))²²
which in turn means that:
ply 11[[C = )1) + A21(C c2))²² ply | e1) + A21(C c2))²
min
ply, A-1(C=c]] + +x11(C = c2])² ply2 b (i + 2₂1(c = c2))²
1
(128)
p(y ply, |+ + 121[C== c2)) ply, x1 - c + A2
+ 1 = c2)) ply A1|C = .1) + 1,11CC = c2
= min
c2))
(129)
This last expression is in line with the condition of Assumption 3.8, showing that, for all y E y, either
w[[C = ci Ji or w( [[C c2] by, are greater or equal to (Ai((C +1 A) I[C ca))y
Combining step (1) and (2), we obtain that Assumption 3.8 holds and that:
max w (AI(C )1) + (1-A)(CC- = 02))y I max ( (max w e1 e1)yy, max w (1(C = c2))y) yEy
yEy
yey
(130)
where equality holds if and only if X E 1).
E,2 Numerical evaluation of Assumption 3.8
Finally, we investigate experimentally whether the models used in our experiments satisfy Assump- tion 3.8. We have already shown in Appendix E. that the DSL inference layer reduces to Probabilistic Logic methods and, therefore, we only consider DPL and DPL as representatives, and our empirical results support this claim. We evaluate CBNMs separately. In this evaluation, train models on MNIST- Add, where there are two concepts total of 100 x 19 weights for the inference layer w, which are fixed (by the prior knowledge) for DPL and learned from data for DPL and CBNM.
(2),02)
02) E [10]² and 19 total labels y [19]. This yields
We begin from DPL, where the prior knowledge K defines the inference layer w". In this case, we find that - as expected- Assumption 3.8 is satisfied by all possible pairs (c1, E [10]² x [10]2 that predict distinct labels (as requested by the assumption), see Fig. 11.
We now turn to DPL Due to the linearity of the inference layer, in order to study the learned inference layer w it suffices consider random weights for w, cf. Eq. (71). Also in this case, we find that for all possible pairs (c1,c2) [10]2 x [10]2 that predict distinct labels, Assumption 3.8 is satisfied. See Fig. 12.
Finally, we evaluate whether a CBNM trained on MNIST-Add and that is close to achieving optimal likelihood satisfies, at least approximately, Assumption 3.8. To this end, we train the CBNM for 150 epochs, reaching a mean negative log- likelihoodd of 0.0884 on the test set. We find that Assumption 3.8 is satisfied for the 95% of possible pairs (ci, c2) E [10]2 x [10]2 giving different labels. For the remaining 5% the assumption is marginally violated with a maximum discrepancy:
max w (ALCC = c. + (1- A)I(C = c;})y max ( mmax w (((c)) Dly max w (1(2))l)
c1.
y
(131)
< 1.38 10-3
(132)
39

---

0.00
0.05
0.50
0.75
1,00
0:00
0.45
030
0.75
1,00
0.00
0.2
0.5
0.7
1.00
0.00
0.23
0.50
0.15
1.00
15
26
Figure 11: The logic inference layer of DPL in MNIST-Add. (Top) The behavior of f(A) maxy (A1f(C = c +
C = cy for four pairs i, sampled randomly from the 100 possible worlds. The x-axis represents and the y-axis f f()). (Bottom) The linear layer weights for DPL.
0.10
0.21
0.110
0.005
0.59
0.100
0.95
0.99
8073
0.28
3.00
325
230
2.5
120
000
025
050
0.7
1.00
0.00
025
0.50
0.13
1.00
0.00
0.25
0.30
9.75
100
1:5
-201
Figure 12: A random inference layer for DPL in MNIST-Ad Add. (Top) The behavior of f(A) == maxy w (A1(C C c (1 A)I{C c,1), for four pairs i,j sampled randomly from the 100 possible worlds. (Bottom) The linear layer weights for DPL
0.8
08
0.7
0.7
04
AA1162
0.00
0.25
0.50
0.75
1.50
0.50
0.25
0.50
0.75
1.00
0.00
0.25
0'50
0.75
1.00
0.03
0.20
0.50
0.35
1.00
Figure 13: Optimal CBMM in ANIST-Add. We visualize the learned weights by a CBMM achieving maximum log-likelihood in MNIST-Add. (Top) The behavior of f()) maxy w (X1(C = c,) (1- A)I{C = - for four pairs i,j sampled randomly the 100 possible worlds. The sampled pairs align with Assumption 3.8. (Bottom) The linear layer weights for the trained CBNM.
The results are illustrated in Fig. 13.
40


Reviews:
[{"review_id": "kqMHf90PGG", "reviewer": "Reviewer_d94G", "summary": "The paper attempts to connect reasoning shortcuts from neurosymbolic AI  with concept-based models, where models can achieve high performance without learning the right semantics. It shows that maximum likelihood training alone is insufficient to ensure intended semantics and formalize the conditions for when a CBM can acquire high-quality concepts and inference layer. It also explores and empirically tests potential mitigation strategies. The results show promise on benchmark datasets.", "questions": "* The paper seems to give a concept-based lens to a neurosymbolic models, rather than the other way around. It claims that a CBM is a NeSyCBM with a learnable inference layer. Is my understanding correct? If so, I don’t fully agree with this, as CBMs and NeSy models are fundamentally meant for different tasks (classification and reasoning respectively). Could you please exactly state what sort of CBM is being referred to throughout?\n* Is there a difference between NeSy models as NeSyCBMs? If so, could you please give an example of a NeSy model that isn’t a NeSyCBM? \n* Could you explain the reasoning behind the choice of baselines? There are only two CBM-based baselines [3, 4]. All the others are NeSy ones. Also, if the CBNMs [3] have no concept supervision (L267), how are the concepts learned?\n* The paper brings up desiderata for high-quality concepts and inference layer earlier in the paper. Yet these aren’t evaluated in any way or even used much in the derivations, for that matter. Could you explain why they were introduced?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n+ Studying concept and inference layer quality in CBMs from a reasoning shortcuts point of view is novel, to the best of my knowledge. \n+ The presented theory and bounds seemed fairly complete (although I do have some concerns about them in the weaknesses) and the provided examples made things more intuitive.\n\nWeaknesses: \n- The formalization of reasoning shortcuts for CBMs is interesting, however, considering the fact that a lot of the results build on existing works like [1, 2] (which the paper also mentions in the related work), makes the degree of novelty of the work questionable. Additionally, most of the practical solutions (Sec 4), have also already been proposed in [1].\n- I found the paper slightly lacking in clarity. In particular, in Sec 3, where CBMs are modeled as a pair of functions, the concept extractor is defined as mapping onto a simplex, yet in words it is said that it maps to a conditional distribution. Putting this mismatch aside, in standard CBMs [3], the concepts are predicted independently. There is no distribution over them. So it is not clear how vanilla CBM (as widely used) fits into this approach. \n- I also found it difficult to differentiate between NeSyCBMs and general NeSy models - although NeSyCBMs were defined, they weren’t formalized mathematically. Several of the references and baselines were standard NeSy models, like DeepProbLog. \n\nReferences:\n[1] Marconato, Emanuele, et al. \"Not all neuro-symbolic concepts are created equal: Analysis and mitigation of reasoning shortcuts.\" Advances in Neural Information Processing Systems 36. 2023.\n[2] Yang, Xiao-Wen, et al. \"Analysis for abductive learning and neural-symbolic reasoning shortcuts.\" Forty-first International Conference on Machine Learning. 2024.\n[3] Koh, Pang Wei, et al. \"Concept bottleneck models.\" International conference on machine learning. PMLR, 2020.\n[4] Alvarez Melis, David, and Tommi Jaakkola. \"Towards robust interpretability with self-explaining neural networks.\" Advances in neural information processing systems 31 (2018).", "was_revised": true, "final_justification": "I thank the authors for the responses; the rebuttal was helpful in clarifying most of my questions. I'd suggest that the authors also revise the manuscript with these responses to make it clearer (lack of clarity in the current manuscript on some of these fronts was an earlier concern for me).\n\nI stay positive on the paper for the contributions; however, I still believe the empirical analysis is limited, and stay with my BA rating.", "rebuttal": "We thank the reviewer for appreciating the novelty of our work and the thoroughness of the analysis.\n\n\n> **Novelty of the work**\n\nWe acknowledge that the work of Marconato et al. (2023) inspires ours, but we go beyond it by proposing a common framework to analyze NeSy-CBMs and CBNMs. We differ in that:\n\n- **Scope** Marconato et al. study NeSy-CBMs where the inference layer is **fixed**. Lifting this constraint is technically challenging but it allows us to substantially generalize the notions of reasoning shortcuts and concept identifiability to CBNMs, a class of models that were never analyzed under this lens.\n- **Analysis** How to properly learn concepts without concept supervision is an open question. Our results answer when to expect concepts to be learned correctly by avoiding joint reasoning shortcuts.\n- **Mitigation** We test existing mitigation strategies for NeSy-CBMs with a fixed inference layer and consider two novel strategies: knowledge distillation and contrastive learning. Our results suggest that preventing JRSs is still an open question.\n\n> **Clarity**\n\nWe use the functional notation for ease of manipulation (see 100-104). This formalism also captures regular CBNMs. We consider CBNMs where concepts are modelled by applying a sigmoid (or a softmax) activation on input embeddings in the bottleneck, meaning they are conditionally independent given the input, as usual. In this setting, the CBNMs’ concept extractor is precisely a function that maps inputs to a simplex with one dimension per concept: the $j$-th coordinate is the conditional probability that the $j$-th concept appears in the input. The same setup can also express NeSy-CBMs like DPL and LTN, which consider the same activations on the bottleneck.\n\n\n> **Question: NeSy is meant for reasoning, CBMs for classification**\n\nNeSy encompasses a wide family of approaches that integrate learning and reasoning, but reasoning shortcuts have so far only been studied in “NeSy predictors”, which happen to share much of the structure of CBNMs: both include a concept extractor mapping inputs to concepts and an inference layer, and both are trained via gradient descent. The main difference is the inference layer: in NeSy predictors, this is typically fixed and encodes known rules for deriving the label from the concepts (e.g., the rule of addition in MNIST-Addition); in CBNMs, it is typically a learned linear layer. This structural similarity is what enables us to extend RSs from NeSy predictors to CBNMs. At any rate, in NeSy, reasoning is always a means of computing predictions, as done in MNIST-Addition [4].\n\n> **Question: NeSy-CBMs vs general NeSy models**\n\nWe distinguish between NeSy-CBMs, which combine a concept extractor and an inference layer through a bottleneck of concept activations, and general NeSy models, which can have very different architectures and, in particular, may not model a bottleneck of latent concepts. Examples include grounding-specific Markov logic networks [1], SATNet [2], and the neural theorem prover [3].\n\n\n> **Question: Why these baselines? There are only two CBMs, all others are NeSy**\n\nFor both CBMs and NeSy-CBMs, we evaluated the most representative architectures:\n\n* CBNMs are the most well-studied architecture, and they also serve as a recipe for other concept-based models [see references in lines 53, 54, and 55];\n* SENNs are also well-known but leverage a slightly different architecture designed to learn concepts in an unsupervised manner.\n* DSL learns both knowledge and concepts, and implements the inference step as a lookup table.\n* a modified version of DeepProbLog that is similar to DSL but, like regular DeepProbLog, uses probabilistic logic for inference.\n\n\n> **Question: If the CBNMs have no concept supervision, how are the concepts learned?**\n\nWe train CBNMs using a regular cross-entropy loss on the labels, just like regular feed-forward neural networks. The concepts are treated as latent variables: the model will learn “concepts” that allow it to achieve low training loss. CBNMs also include a cross-entropy loss on the concept bottleneck, which we don't use unless otherwise specified.\n\n\n> **Question: Why introducing the desiderata if you don’t evaluate them?**\n\nThank you for raising this point. We want to clarify that **the metrics we use to evaluate the accuracy of learned concepts (F1(C)) and of the learned inference layer (F1(beta)) take both desiderata into account**.\n\n- **Disentanglement**:  F1(C) evaluates how close the map $\\alpha$ (encoding the concept extractor) is to the identity, up to permutation and element-wise invertible transformations. To account for these symmetries, we apply the Hungarian matching algorithm to map learned to ground-truth concepts. This indirectly measures whether the learned concepts are disentangled.\n- **Generalization**: We use the permutation and element-wise transformation obtained via Hungarian matching to evaluate whether the learned inference layer $\\omega$ predicts the same labels as the ground-truth knowledge $\\omega^*$.  In summary, F1(\\alpha) and F1(\\beta) together tell us whether the two desiderata are respected. \n\nWe will clarify in the text how the experimental verification accounts for the two desiderata.\n\n----\n\n**References**\n\n[1] Lippi and Frasconi. \"Prediction of protein β-residue contacts by Markov logic networks with grounding-specific weights.\" Bioinformatics, 2009.\n\n[2] Wang, Donti, Wilder, and Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. ICML 2019.\n\n[3] Rocktäschel and Riedel. End-to-end differentiable proving. NeurIPS, 2017\n\n[4] Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T., & De Raedt, L.. Deepproblog: Neural probabilistic logic programming. NeurIPS 2018"}, {"review_id": "BeGYr2EqV6", "reviewer": "Reviewer_mrPP", "summary": "This paper investigates the issue of Joint Reasoning Shortcuts (JRSs) in CBMs and NeSy-CBMs. Through theoretical analysis and empirical validation, the authors reveal how JRSs lead models to learn low-quality concepts and inference layers, thereby compromising interpretability and OOD performance. The paper introduces the notion of \"Intended Semantics\" and derives theoretical conditions under which JRSs can be avoided. Experiments demonstrate the limitations of existing mitigation strategies, particularly in unsupervised settings.", "questions": "Regarding the issue of the number of deterministic JRSs raised in the weaknesses, I suggest further analyzing how different mitigation strategies might affect this quantity.\n\nConcerning the necessity of studying CBM shortcuts, I have several reservations:\n- Intermediate layers in standard vision neural networks typically lack interpretable semantic features, and there is already extensive research on neural network shortcuts [1]. What distinguishes this work?\n- Enforcing intermediate layers to output interpretable concepts may be redundant (though it does enhance interpretability). In practical applications, constructing meaningful intermediate concepts is highly challenging. However, within the NeSy framework, the presence of intermediate concepts is justified due to the support of a knowledge base. So why not use current sota vision models?\n\n[1] Shortcut Learning in Deep Neural Networks. Geirhos, R., Jacobsen, J.-H., Michaelis, C., Zemel, R., Brendel, W., Bethge, M., & Wichmann, F. A.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This paper is the first to establish a theoretical framework for JRSs, which extends RS, and proposes sufficient conditions to avoid JRSs (e.g., Theorem 3.9).\n2. The theoretical analysis and experimental evaluations in this paper are both highly comprehensive.\n\nWeaknesses:\nThere are some questions regarding the content of Theorem 3.9. If I understand correctly, the theorem states that when the number of deterministic JRSs is zero, the system possesses the intended semantics. While this result aligns with intuition, I believe it is more important to provide a theoretical explanation of the conditions/assumptions under which the number of deterministic JRSs can be reduced.\n\nAdditionally, most of the experiments in this paper are based on variants of MNIST, which is somewhat limited. Furthermore, it would be valuable to compare with other NeSy algorithms (I noticed that only DPL was mentioned in the paper), such as LTN, among others.", "was_revised": true, "final_justification": "The author's response has solved my problem, and I will keep my score unchanged.", "rebuttal": "We thank the reviewer for finding our theoretical framework novel and appreciating the depth of the analysis. \nBelow, we address the points raised in their review.\n\n> **Conditions under which the count of deterministic JRSs can be reduced.**\n> **Question: How do different strategies affect this quantity?**\n\nThank you for raising this important point. We agree that reducing the number of deterministic JRSs should be the primary goal and the starting point for designing new mitigation strategies. We stress that some of the existing strategies already allow for reducing the count in Thm 3.6; we analyze the impact of multi-task learning, concept supervision, knowledge distillation, and reconstruction explicitly in Appendix D. For example, introducing a reconstruction term avoids all those JRSs in which multiple concepts are collapsed together, leading to a smaller count.\nWe will make sure to clarify this before the forward pointer to Appendix D in Section 4.\n\n> **Most experiments are based on variants of MNIST**\n\nIn order to assess the impact of joint reasoning shortcuts, we need concept-level annotations and prior knowledge (e.g., the rules of traffic in BDD-OIA), which are not commonly available. Our experiments rely on the most extensive existing benchmark for reasoning shortcuts [1], and, besides variants of MNIST-Addition, they also evaluate CLEVR and BDD-OIA. The former two are easy to control and evaluate, the latter is a challenging autonomous driving task with real-world images, four binary labels, and 21 binary concepts.\n\n> **Comparison with other NeSy algorithms**\n\nWe consider **two** NeSy baselines: DPL and DSL.\n\nLTN is not designed for learning the knowledge from data.  [Marconato et al. 2023] have already shown that NeSy predictors with fixed prior knowledge, including regular DPL, LTN, and the Semantic Loss [2], suffer from regular Reasoning Shortcuts.\n\nOur goal is to go beyond the “fixed prior knowledge” setting and understand what happens in  CBMs and NeSy predictors that learn the knowledge (or, more generally, the inference layer) from data. This is why our choice of competitors covers mainstream baselines like CBNMs, SENNs, and DSL, which all learn the inference layer. We also include a hybrid of DPL and DSL that does the same.\n\nIt is not straightforward to adapt LTN to learn the knowledge, as it would require handling the fuzzy logic in the inference layer, and designing appropriate data structures and losses for doing so is non-trivial. Doing so would be a standalone contribution.\n\n> **Question: Distinction between vanilla shortcuts and joint reasoning shortcuts.**\n\nRegular shortcuts [Geirhos et al. 2020] can be understood as unintended input-to-label assignments that achieve high performance. E.g., the model might rely on confounding features (like watermarks) to output good predictions. They compromise generalization to domains where the confounders are not present.\n\nJoint reasoning shortcuts are failure modes where either or both the concepts and the inference layer are not equivalent (in the sense we specify in Def. 3.4) to the ground-truth concepts and inference layer, and they can compromise interpretability and generalization.\n\nThe two issues are related but **different**. While shortcuts can induce JRSs, the converse is not true: a model can be affected by a JRS (i.e., it might have learned “bad” concepts or a “bad” inference layer) even if it does not rely on confounders. An example is reported in Fig 2. This also means that remedies to regular shortcuts do not necessarily resolve JRSs.\n\nWe will clarify this distinction in the Related Work.\n\n> **Question: Why not using SotA vision models to extract concepts?**\n\nGood point. Our work focuses on “regular” CBMs and NeSy-CBMs that do not leverage VLM concepts, but it is true that recent CBM/NeSy architectures do use them [3,4]. However, although VLMs keep improving, recent works [5,6] show that the concepts they produce are not necessarily high quality even for widely used datasets (like CUB), meaning that VLMs may be affected by JRSs or similar issues too. We plan to extend our theory to this case in future work. We will include this note in the revised manuscript.\n\n-----\n\n**References**\n\n[1] Bortolotti, Marconato, Carraro, Morettin, van Krieken, Vergari, Teso, and Passerini. A neuro-symbolic benchmark suite for concept quality and reasoning shortcuts. NeurIPS 2024.\n\n[2] Xu, Zhang, Friedman, Liang, van den Broeck. A semantic loss function for deep learning with symbolic knowledge. ICML 2018.\n\n[3] Cunnington, D., Law, M., Lobo, J., & Russo, A. The role of foundation models in neuro-symbolic learning and reasoning. In International Conference on Neural-Symbolic Learning and Reasoning 2024.\n\n[4] Oikarinen, T., Das, S., Nguyen, L., & Weng, L. Label-free Concept Bottleneck Models. ICLR 2023.\n\n[5] Srivastava, Yan, Weng.  VLG-CBM: Training Concept Bottleneck Models with Vision-Language Guidance. NeurIPS 2024.\n\n[6] Debole, Barbiero, Giannini, Passerini, Teso, Marconato. If Concept Bottlenecks are the Question, are Foundation Models the Answer? arXiv 2025."}, {"review_id": "WICU7YCNTt", "reviewer": "Reviewer_D2Sw", "summary": "The paper analyzes CBMs with respect to reasoning shortcuts: a CBM that learns a classifier of high accuracy without uncovering the true concepts or classifier function over the concepts. For this, the paper establishes a theory inspired by NeSy-CBMs. Using this theory the paper presents results for identifying both the true concepts and the true inference layer. In an empirical analysis, the paper demonstrated the impact of reasoning shortcuts on different datasets ans shows the impact of different mitigation strategies.", "questions": "1. L7: What are low-quality concepts? Isn't the definition of a concept quality always human-centric and, hence, notoriously difficult to describe mathematically?\n2. The paper references causality papers. One know paper in this field is \"Towards Causal Representation Learning\" by Schölkopf et al. A major statement in this paper is the fact that statistical ML can only generalize in the iid and not in the ood regime. To generalize in the ood regime, it is required to identify causal connections between variables as each ood shift from the iid training data can be viewed as an intervention (in the causal sense). In this light, how conflicting are statements that CBMs can deal with ood (L20) even if they are identifying correlations (statistical machines)?\n3. L46: What exactly is meant by discrete concepts?\n4. How is Eq. (1) related to the usual factorization of CBMs $P(X,C,Y) = P(X)P(Y|C)P(C|X)$\n5. L81: IMHO this assume that $\\mathcal{G}$ is unique. How realistic is this assumption considering that in reality a set of different objects can be uniquely described by different sets of concepts (e.g., assume different level of abstractions)?\n6. Table 2 results: All the methods in the table are deemed to be interpretable. Consequently, it should be possible to analyze the hypothesized simplicity bias. What rule has the SENN learned to solve the problem and how does this result relate to the established theory?\n7. L341: \"Our work partailly fills this gap\" Why partially? Again, the **limitations** should be clearly stated.\n8. L357: Why is contrastive learning helpful? Once more, using the interpretability of the methods should provide an answer.\n\n\n**Some general notes not related to my assessment:**\n\n- L24: What question? There is no question in the sentences before.\n- Colored links and references are unusual and not really needed IMHO\n- L32: shortcuts [...], more than reasoning shortcuts; it sounds like \"more shortcuts than shortcuts\"\n- L44: a **proven** fact cannot fail **empirically**\n- L99: A set is compared with an element. This doesn't make sense.\n- L264: reporhhts\n- L319: The \"ood\" generalization works because we induce expert knowledge pushing the assumed ood data into iid (see my comment above).\n- Maybe it would be good to have one running example instead of MNIST and autonomous driving.", "limitations": "The discussions of limitations must be improved: How realistic are the assumptions and what are the consequences? See further details in my comments before.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Note:** I have not checked the correctness of the proofs in detail due to the overall length of the paper+appendix.\n\n### Strengths:\n\n- **Originality:** The idea to analyze the learning abilities of CBMs from a mathematical perspective wrt whether the true generative process can be recovered is great. The results provide new insights about how difficult it is in theory to identify this said process. Moreover, the paper clearly motivates the existing work with respect to state of the art, and shows the limitations in learning CBMs even if respective penalties are applied.\n\n- **Significance:** The presented theory and results are of interested for the community that works on the design of interpretable models, especially CBM researchers. Additionally, the paper addresses a difficult task, IMHO.\n\n### Weaknesses:\n\n- **Clarity:** As already said, the paper addresses a difficult task and, in such a situation, it is to some extent okay if the paper is not easy to understand and follow. However, the understandability of the paper should be improved. First of all, a lot of information relevant to key claims (e.g., the transferability of the results to a real task is in Appendix B) are in the appendix making the paper not self-contained. Second, the mathematical part is not easy to understand because of too short descriptions and because of using mathematical notations as isolated descriptors instead of accompanying symbols for clarity of a description (see examples below). My impression is that the paper clarity and also **quality** suffered from the page limit of the venue. I think the paper would be better suited in a journal where the page limit is not so strict. In this case, I think that the paper could become a really strong submission by having the paper better organized and content less scattered across main part and appendix. Regarding the usage of mathematical notations, ideally, mathematical notation should support the written text to add clarity but it shouldn't be a replacement for text. For instance:\n   - L117: \"the maps $\\alpha$ and $\\beta$\" better \"the ground-truth distribution $\\alpha$ that generates the data ...\"; I'm not claiming that this is a good description but I hope it makes my statement clearer.\n   - L83: \"$\\mathcal{G} = \\mathcal{C}$\" better \"where we assume equal discrete $\\mathcal{C}$ and ground-truth concept sets $\\mathcal{G}$, i.e., $\\mathcal{G} = \\mathcal{C}$\" [...just realizing that it is not easy for me to find clear descriptive phrases for the mathematical entities, which is not a good indicator for the paper's clarity].\n\n   The reason why I'm stressing this point is because it complicates clarity as one has to memorize all the notations in order to understand the paragraphs. Moreover, in some cases it leaves room for different interpretations if a mathematical notation is not clear (e.g., L116, $\\mathbb{1}${$\\mathbf{C} = \\mathbf{c}$}, isn't $\\mathbf{C}$ a set and $\\mathbf{c}$ an element of $\\mathbf{C}$? How does comparison work?). Moreover, sometimes mathematical notations are not even clear at all (e.g., cf. L46 and L63: $\\mathbf{C}$ vs $\\mathbf{c}$). Additionally, Figure 1 is not self-explanatory. Even after reading the related text in the corresponding section, it requires some time to understand the illustration.\n\n- **Quality:** The paper nicely presents the assumptions related to the theory. However, when it comes to Definition 3.3 that is the backbone of all the theory, it is not rigorous in explaining the importance and the connection to the disentanglement assumption. It should be clearly stated that the definition only makes sense under this assumption. Then it should be discussed how realistic this assumption is in reality (element-wise, invertible functions and bijection from ground-truth to learned concepts); relating to the **limitations** of the paper. This discussion is crucial as it explains whether the paper analyzes an aspect of practical relevance. Hence, this should be stated clearly. The same is true for Definition 3.4. It should be discussed how realistic this definition is and what happens if it doesn't hold.", "was_revised": true, "final_justification": "The authors addressed my comments in the rebuttal and promised to fix the mentioned issues (my mentioned points highly overlap with comments from other reviewers). Since the corrections and improvements span huge parts of the paper, I only raise my score by one point (from 3 to 4) since I cannot foresee if all the promised changes will turn the current submission in a strong one that would justify a rating of 5.\n\nThanks again to the authors for the good rebuttal!", "rebuttal": "We thank the reviewer for the positive assessment of our contribution and for pointing out elements that need improvement. We will use the **extra page** allowed for the camera-ready to move the experiments on BDD-OIA in the main text, and to clarify the mathematical notation. \n\n> **Notation is difficult**\n\nWe amend this by adding a table of notation in Appendix A and complementing the text with additional explanations of the quantities in use, wherever necessary (**See detailed comments below**). We hope this improves the readability and are eager to iterate further based on the reviewer’s feedback.\n\n> **L117 and L83**\n\nThank you, we will improve the text based on your suggestions.\n\n> **The importance of disentanglement for intended semantics**\n\nWe agree with the reviewer that disentanglement is a central notion, and our definitions of intended semantics and joint reasoning shortcuts are based on it.  We will complement the text around Def 3.3 specifying that Eq. (5, left) guarantees disentanglement of the learned concepts.\n\n> **Mismatch between theory and practice**\n\nDefinitions 3.3 and 3.4 in our theory are intentionally strict.\n\n_Our key insight is that the existence of JRSs implies that the learned concepts and inference layers can drastically differ from the ground-truth ones, while still yielding accurate (in fact, perfect) label predictions_. This is precisely the issue we highlight in our experiments (Table 2 and Table 3), where models achieve high label accuracy despite significantly low F1(C) and F1(β) scores. These observations reflect a substantial mismatch between the learned and intended semantics, providing evidence that models are prone to learning JRSs.\n\nIn theory, when CBM concepts are even slightly entangled or do not perfectly match the ground-truth concepts, they do not satisfy Definition 3.3. Similarly, models that achieve nearly optimal label predictions but lack the intended semantics do not qualify as JRSs under Definition 3.4. However, we emphasize that our practical conclusion does not hinge on these definitions being satisfied exactly. Rather, the theory helps explain and anticipate the failure modes we observe: high task performance can mask severe representational mismatches.\nConversely, when deterministic JRSs are mitigated (as shown in Table 1), models exhibit much closer alignment with the intended semantics, both in terms of concept quality and reasoning, which validates our theoretical framing and its practical relevance.\nQuestions:\n\n> **Question: L7: What are low-quality concepts?**\n\nWe completely agree that concept quality is difficult to define and human-centric in general. As we mention in the introduction, at the bare minimum, “high quality” concepts ought to be interpretable and not compromise OOD generalization. This is precisely what our definitions of intended semantics and joint RSs are meant to capture.\n\n> **Question: How conflicting are statements that CBMs can deal with ood (L20) even if they are identifying correlations (statistical machines)?**\n\nGood point! CBNMs are learned from observational data, just like other neural networks. Fitting such data is insufficient to **guarantee** any sort of OOD generalization _when the target domain is different enough_ from the source domain. This applies equally well to the label predictions and to the concept predictions. If a CBM is affected by JRSs, however, we can construct target domains in which we know it won’t generalize. For instance, imagine it has learned concepts that do not identify the ground-truth ones (e.g., in MNIST-Addition, it conflates “0” and “2”). Then we can always design a ground-truth data-generating process whose concept distribution is the same as the source domain, but the inference layer is different (say, MNIST-Multiplication) such that the learned concepts will yield poor label predictions (all products involving “2” will yield “0” as output).\n\nIn short, while the absence of JRSs gives no guarantees that a CBM will generalize OOD, the presence of JRSs substantially increases the chances that it will not.\n\nWe will clarify what we mean by OOD in Section 3.\n\n> **Question: L46: What exactly is meant by discrete concepts?**\n\nWe mean categorical concepts, that is, random variables that can take only discrete values, as opposed to continuous concepts like angles or distances. We will be more precise in the text.\n\n> **Question: How is Eq. (1) related to the usual factorization of CBMs?**\n\nIt is identical, except we marginalize over the ground-truth concepts $g$.  This enables us to reason in terms of ground-truth concepts in the derivations and it is justified by our choice of data generating process.  The usual factorization of CBMs [1] can be reobtained considering that $ p^* ( \\mathbf G \\mid  \\mathbf X ) p^* (\\mathbf X )  =  p^* ( \\mathbf X \\mid  \\mathbf G ) p^* (\\mathbf G ) $. In which case, we have:\n\n$$\np^{\\ast}(\\mathbf{X}, \\mathbf{Y}) = \\mathbb{E}_{\\mathbf{g} \\sim p^{\\ast}(\\mathbf{G} \\mid \\mathbf{X})} \\left[ p^{\\ast}(\\mathbf{X}) \\, p^{\\ast}(\\mathbf{Y} \\mid \\mathbf{g}; \\mathrm{K}) \\right]\n$$\n\n> **Question: L81: Ground-truth concept vocabulary is assumed to be unique**\n\nGreat point. We agree that there might be different choices of concept vocabulary (or domain $\\mathcal G$) that all work fine for any given task, e.g., at different levels of abstraction. We do not make any assumptions about how this vocabulary is chosen.\n\nTo see this, fix any such vocabulary. This, in turn, it determines the ground-truth concept extractor $\\mathbf{f}^\\ast$ and inference function $\\mathbf{\\omega}^*$.  Compatibly, our Theorem 3.9 explains when the NeSy-CBM will learn concept extractor $\\mathbf f$ and an inference layer $\\mathbf \\omega$ equivalent to these.\n\n**Our analysis holds for any proper choice of ground-truth vocabulary** (i.e., as long as it allows to predict the ground-truth label perfectly, and assumptions 4.1 and 4.2 hold). In practice, we expect that, with more fine-grained concepts joint reasoning shortcuts can increase, whereas they can decrease with coarser concepts. \n\nWe will discuss this interesting point in the paper.\n\n\n> **Question: All the methods in Table 2 are deemed interpretable. Consequently, it should be possible to analyze the hypothesized simplicity bias. What rule has the SENN learned to solve the problem, and how does this result relate to the established theory?**\n\nSENNs provide local explanations for a given prediction, i.e., they do not provide an interpretable set of rules holding in the whole domain (i.e., the inference layer $\\beta$ depends on the input). In contrast, NeSy-CBMs like DSL and DPL provide global explanations that we report in our experimental evaluation (see Appendix B).\n\nWe computed the concept confusion matrices for SENNs. We will report them in Appendix B, together with a comparison with the other approaches. In short, we didn’t observe any simplicity bias in SENNs. We hypothesize that this depends on both the flexibility in modelling local rules and on the reconstruction penalty applied to concepts during learning.\n\nWe will clarify this in the text.\n\n> **Question: L341: \"Our work partially fills this gap.\" Why partially? Again, the limitations should be clearly stated.**\n\nWe *partially* fill the gap because we focus on NeSy-CBMs. While our results are likely to transfer to other NeSy models, doing so properly warrants further work.\n\n> **Question: L357: Why is contrastive learning helpful? Once more, using the interpretability of the methods should provide an answer.**\n\nIn our experiments (see Fig 3 for MNIST-SumParity and Fig 6 in the Appendix for CLEVR), contrastive learning reduces concept collapse but does not improve the other metrics. We remarked this point in the Conclusion (L327).\n\nThis is likely because contrastive losses encourage the concept extractor to assign similar (resp. dissimilar) concepts to similar (resp. dissimilar) inputs, i.e., the concept extractor can not collapse concepts together without increasing the contrastive loss.  In practice, we would expect the same to happen also when a reconstruction term is in place, but this does not work as well (Fig 3) as it is more challenging to optimize.  There are also theoretical reasons to believe contrastive learning should help with identifiability [2].\n\n> **Some general notes not related to my assessment**\n\nWe thank the reviewer for the detailed comments. We plan to include all the aforementioned changes in the final version of the manuscript.\n\n----\n\n**References**:\n\n[1] Koh, P. W., Nguyen, T., Tang, Y. S., Mussmann, S., Pierson, E., Kim, B., & Liang, P. Concept bottleneck models. In ICML 2020.\n\n[2] Zimmermann, R. S., Sharma, Y., Schneider, S., Bethge, M., & Brendel, W.  Contrastive learning inverts the data generating process. In ICML 2021."}, {"review_id": "K4FJlMrnJ0", "reviewer": "Reviewer_7RjS", "summary": "This paper investigates joint reasoning shortcuts (JRS) in the context of concept-based models. JRS describes shortcuts emerging from the two-level architecture of CBMs, where the concept extractor, the inference layer or both together can be subject to shortcut learning. The paper analyses these JRS from a theoretical perspective, formally describing situations under which these shortcuts can or cannot occur. Further, the paper illustrates that common mitigation strategies are limited in effect when mitigating JRS, highlighting the importance of the topic.", "questions": "Recommendations to improve the clarity of the beginning of the paper:\n- For the introduction and section 2, the current setting is often unclear (for example what type of supervision is considered or what parts of the model are learned). I would suggest to make this more clear in the beginning, especially for the examples up to 2.2.\n- Further, I would suggest to stick to one running example (and not mixing mnist with the pedestrians)\n\nI am confused by the intended semantics:\n- To my understanding, this allows $\\alpha$ and $\\beta$ to permute the concepts with respect to the ground-truth concepts as long as this inversion is corrected.\n- I understand this in the context of a learned $\\beta$ and no ground-truth concepts available. But it does not make sense to me in the context of a fixed inference layer, as this does not have the possibility to permute the concepts anymore. Is it then implied that in this case there is no permutation learned by $\\alpha$?\n\nCan the authors discuss the practicability of assumptions 3.1 and 3.2 in practice? In particular the assumption that the label can be predicted via without ambiguity from the ground-truth concepts seems unrealistic, as it assumes a perfect and complete ground-truth concept set. (Or, if stated differently: when the existence of such a concept set is assumed, it seems unlikely that assumption 3.1 holds and these concepts are always recoverable).\n\nFurther, can the authors provide a brief intuition how the problem of JRS is affected if the CBM is trained independently or if the concept extractor is pretrained in a general setup, as often done in recent CBMNs [1, 2]?\n\nQuestions about the experimental setup and evaluation:\n- How is the CBNM trained if there is no concept supervision? \n- Could the authors explain the evaluation of the learned inference layer? It seems confusing to use $\\pi$ on the concepts if the inference layer is learned, assuming that the inference layer itself is not permutation invariant, as then it gets a different input permutation than usual during its training.\n\n\nMinor:\n- Caption of figure 2: introduce the abbreviation (JRS) before using it\n- Typo in line 264 (reporhhts)\n\n[1] Oikarinen, Tuomas, et al. \"Label-free concept bottleneck models.\" _arXiv preprint arXiv:2304.06129_ (2023).\n\n[2] Yang, Yue, et al. \"Language in a bottle: Language model guided concept bottlenecks for interpretable image classification.\" _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 2023.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strenghts:\n- The paper covers an important problem of concept-based models: joint reasoning shortcuts, which are even more difficult to handle than regular (reasoning) shortcuts.\n- It introduces a theoretical framework that allows for analysis of these JRS and to describe situations where they occur or can be avoided.\n\nWeaknesses:\n- While the theoretical framework is important to analyse these shortcuts from a formal perspective, the given assumptions are unlikely to hold in practice.\n- The clarity of motivation and setup can be improved.", "was_revised": true, "final_justification": "During the rebuttal, my main concerns have been addressed.\nIn particular, the authors addressed the clarity issues of the paper (in an answer to a different reviewer), discussed the assumptions and their implications in practice in more detail, and answered several smaller questions.\n\nHowever, while I appreciate the theoretical analysis of reasoning shortcuts in CBMs, I am not sure how much this impacts the practical development of these models.\n\nNevertheless, I overall recommend the acceptance of the paper as it advances the theoretical understanding of shortcuts in reasoning settings.", "rebuttal": "We thank the reviewer for finding the addressed problem important and for appreciating our theoretical contribution. Below, we reply to the points of their review.\n\n> **Clarity of presentation**\n\nThank you for the corrections and suggestions, we will implement them. We will be more explicit in Sections 1 and 2 about the problem we aim to solve, what we learn, and how we use supervision. We have also made use of the **extra page** to include a table of notation to help navigate the formalization. Below, we address different points separately. See also the reply to reviewer D2Sw.\n\n> **Validity of assumptions**\n\nAssumptions 4.1 and 4.2 are mild and in fact they hold in all the tasks available in the largest benchmark of NeSy reasoning shortcuts [Bortolotti et al., 2024], including the ones we experiment with. They hold because, for each input image $\\mathbf x$, it is possible to recover the ground-truth concepts in the image $\\mathbf g$ and the corresponding labels $\\mathbf y$.\n\nWe agree that it would be useful to lift these assumptions assumptions, but doing so is technically challenging. It is possible to relax Assumption 4.2 (i.e., labels cannot be entirely determined by the concepts), following [Marconato et al. 2023]; however, this can lead to a scenario where Theorem 4.9 no longer holds. Precisely, the absence of deterministic RSs does not inform us about whether non-deterministic RSs would appear or not [Marconato et al. 2023, Proposition 3]. \n\nWe view extending the current theoretical framework to the case where the assumption can be violated as an exciting research direction.\n\n> **Question: Intended semantics with fixed inference layer. Is it then implied that no permutations are allowed?**\n\nYes, you are correct. When learned in an unsupervised fashion, concepts are “anonymous”: their meaning can only be figured out in a post-hoc manner.\n\nIf the inference layer is fixed, e.g., in the MNIST-Addition task, _concepts are no longer anonymous_, and permutations of the concepts (as in Eq. (5, left)) result in reasoning shortcuts, as in [Marconato et al. 2023]. These permutations can yield wrong results on other tasks. E.g., permuting the two values of the MNIST digits, while giving correct predictions in MNIST-Addition, would give incorrect results in “MNIST-Subtraction”.\n\nExcluding the permutations when the inference layer is fixed is accounted for in the deterministic RSs count of Corollary 3.7, where only one solution (precisely the identity) has the intended semantics. We will make this more explicit in the text.\n\n> **Question: How CBNMs are trained and the use of language-guided supervision**\n\nIf concept supervision is not available at all, then it is unclear how to train CBNMs “independently” (that is, concept extractor first, inference layer later).\n\nWe train CBNMs with joint training [1] using only label supervision: both the concept extractor and the inference layer are trained to minimize the cross-entropy loss on the labels. \n\nWe do not consider weak supervision obtained from VLMs like CLIP, as done by recent architectures. While exploring JRSs in this setup is interesting future work, we stress that this setup does not resolve issues with concept quality. Although VLMs keep improving, recent works [2,3] show that the concepts they produce are not necessarily high quality even for widely used datasets (like CUB), meaning that it is unclear whether VLM-based concept supervision can be safely integrated to avoid joint reasoning shortcuts.\n\nWe will discuss this in the revised manuscript.\n\n> **Question: Evaluation of the inference layer**\n\nThe procedure we follow is described in Appendix A5.  Intuitively, we assess whether the learned inference layer can handle the ground-truth concept annotations properly. For this to work, we first permute the g-t annotations to reflect the position of the concepts learned by the model, using the (inverse of the) permutation returned by Hungarian matching. We will clarify the intuition in the text.\n\n----\n\n**References**\n\n[1] Koh et al. Concept Bottleneck Models. ICML 2020.\n\n[2] Srivastava, Yan, Weng.  VLG-CBM: Training Concept Bottleneck Models with Vision-Language Guidance. NeurIPS 2024.\n\n[3] Debole, Barbiero, Giannini, Passerini, Teso, Marconato. If Concept Bottlenecks are the Question, are Foundation Models the Answer? arXiv 2025.\n\n[4] Zheng, Xie, Zhang. Nonparametric Identification of Latent Concepts. ICML 2025.\n\n[5] Rajendran et al. From Causal to Concept-Based Representation Learning. NeurIPS 2024."}]

Author rebuttal:

Meta-review: The paper reveal how JRSs lead models to learn low-quality concepts and inference layers, thereby compromising interpretability and OOD performance through theoretical analysis and empirical validation. It introduces the notion of "Intended Semantics" and derives theoretical conditions under which JRSs can be avoided. 
All reviewers acknowledged the innovative combination of CBMs and reasoning shortcuts presented in this paper, as well as its solid theoretical contributions. However, some concerns remain regarding the sufficiency of the experimental validation and the clarity of certain theoretical sections. Overall, I recommend accepting this paper, but I strongly encourage the authors to include additional experimental results and to further improve the exposition of the theoretical parts in the camera-ready version
Decision: Accept (poster)