A learnability analysis on neuro-symbolic learning
Authors: Hao-Yuan He
Ming Li
Venue: NeurIPS 2025 spotlight ()
Keywords: neuro-symbolic learning
machine learning
learnability
reasoning shortcuts
abductive learning
probabilistic neuro-symbolic learning
Primary area: general_machine_learning

Abstract: This paper presents a comprehensive theoretical analysis of the learnability of neuro-symbolic (NeSy) tasks within hybrid systems. 
  We characterize the learnability of NeSy tasks by their derived constraint satisfaction problems (DCSPs), demonstrating that a task is learnable if and only if its corresponding DCSP admits a unique solution. 
  Under mild assumptions, we establish the sample complexity for learnable tasks and show that, for general tasks, the asymptotic expected concept error is controlled by the degree of disagreement among DCSP solutions. 
  Our findings unify the characterization of learnability and the phenomenon of reasoning shortcuts, providing theoretical guarantees and actionable guidance for the principled design of NeSy systems.

A Learnability Analysis on Neuro-Symbolic Learning
Hao- Yuan He, Ming Li
National Key Laboratory for Novel Software Technology, Nanjing University School of Artificial Intelligence, Nanjing University (hehy, lim] alamda.n juj.eeu.ccc
Abstract
This paper presents a comprehensive theoretical analysis of the learnability of neuro-symbolic (NeSy) tasks within hybrid systems. We characterize the learn- ability of NeSy tasks by their derived constraint satisfaction problems (DCSPs), demonstrating that a task is learnable if and only its corresponding DCSP admits unique solution. Under mild assumptions, for learnable tasks and show that, for general tasks, the asymptotic expected con- cept error is controlled by the degree of disagreement among DCSP solutions. Our findings unify the characterization of learnability and the phenomenon of rea- soning shorteuts, providing theoretical guarantees and actionable guidance for the principled design of NeSy systems.
establish the sample complexity
1
Introduction
Neuro-symbolic learning (NeSy) seeks to integrate data-driven learning with knowledge-drive rea- soning within unified framework (Hitzler & Sarker, 2022: Marra et al., 2024). State-of-the-an NeSy approaches predominantly employ hybrid systems that map input queries x to concepts 2 via learning model, subsequently utilizing a symbolic system KB deduce the final answer Feed- back from KB KB-such as pseudo-labels in abductive learning (ABL) (Zhou, 2019; Dai et al., 2019) or weighted model counting in DeepProbLog (Manhaeve et al., 2018, 20idee-guides further learning. This paradigm has found broad application in domains including puzzle solving, code generation, and autonomous path planning (Jiao et al., 2024; Li et al., 2024; Hu al., 2025a).
central challenge in NeSy is that systems are typically trained end-to-end in a weakly supervised manner, relying solely on (x, y) pairs, with the underlying concepts remaining unobserved. The objective is to learn a model f + Z that generalizes effectively, minimizing the concept risk:
Roy1 (f) = E(r,)) II (f(x) * =)].
However, in the absence of supervision 2, only the surrogate NeSy risk is accessible:
Ryssy (f) (. [T (f KB H y)]
This motivates a fundamental question regarding the learnability of NeSy tasks:
Under what conditions can the concept risk be minimized through empirical risk minimization over the NeSy risk, given a finite sample set its size approaches infinity?
Recently, Marconato et al. (2023b) identified the reasoning shorteut problem, wherein a reason- ing shorteut (RS) refers to concept distribution that achieves maximal likelihood training data yet deviates from the true underlying concept distribution. This phenomenon is closely related to the statistical learnability of NeSy systems, models may minimize empirical NeSy risk without necessarily minimizing the concept risk. While several approaches have been proposed to address reasoning shortcuts Marconato et al. (2023a, 2024), rigorous theoretical framework connecting RSs to the statistical learnability of NeSy tasks remains underexplored.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To address this gap, we analyze the learnability of the NeSy task within the bobbabl--aproximaate correct (PAC) framework (Valiant. 1984), focusing on restricted hypothesis spaces (cf. section 3.3). Our key insight is to formulate NeSy tasks as derived constraint satisfaction problems (DCSPs): task learnable if and only if its DCSP has a unique solution.
We further introduce disagreement d among DCSP solutions as finer-grained measure of uncer- lainty. For learnable tasks, we establish the sample complexity 1/x- log (IBl/e), where K, [B] are lask-specific and is the desired concept error (cf. theorem 3.6). For general NeSy tasks, we derive an upper bound on the expected concept error, showing is bounded by d/ L. where L is the concept space size (cf. theorem 3.7). Moreover, with the DCSP perspective, we find that aggregating un- learnable tasks multi-task learning manner reduces the degree of ambiguity, thereby enhancing overall task learnability.
Our analysis aligns with the RS phenomenon (Marconato al., 2023a,b), wherein models may achieve low empirical risk yet incur high concept risk. The existence of deterministic RSs corre- sponds to the presence of multiple DCSP solutions. We show that concept error correlates more strongly with solution disagreement than with the number of solutions (cf remark 1), underscoring disagreement d as a more informative indicator.
In summary, our contributions are as follows:
We establish rigorous theoretical foundation for NeSy learnability within the hybrid systems paradigm and derive both sample complexity and asymptotic bounds on concept error.
The DCSP framework proposed facilitates intuitive analysis of learnability using CSP solvers, while solution disagreement provides a detailed perspective on concept error analysis.
Empirical studies are conducted to validate our theoretical findings.
The remainder of the paper is organized as follows: Section reviews the background and related work on NeSy. Section 3 presents our theoretical analysis of NeSy task learnability. Section details empirical validations of our theoretical results. Section 5 discusses limitations, and section concludes the paper.
2
Preliminaries
This section first introduces the problem setup of neuro-symbolic learning, followed by presen- tation of the two principal syrro-y methods: probabilistic neuro-symbolic learning and abductive learning. Subsequently, we discuss the most related works, including those reason- ing shorteuts and theoretical analyses of NeSy.
2.1 Problem Setup
A typical hybrid neuro-symbolic system consists of two components: machine learning model (e.g.. neural network) and logical reasoning model (e.g., a first-order logic solver). The learning model X + Z maps instance (e.g., image, text, or audio) from the input space X' to in- termediate concept z (e.g., primitive facts or predicates) within the symbol space 2, where |2| = L. The reasoning model KB consists of rules over the concept space and can be implemented using any logic-based system, such as Problog (De Raedt al., 2007) or answer set programming (Dimopou- los al., 1997). Assume that labeling function g X + Z exists such that g(x). The learning model, belonging to a hypotheses family F, is parameterized by 0, and po(-) represents the likelihood estimated by the model, where f(x) arg max po(z x).
During inference, the learning model f accepts multiple instances sequence x (I (#1...... ................................ Fmm
and outputs a sequence of concepts 2 = (2....., ). The output & is then passed to the reasoning model KB, which infers the final label y E y' through logical entailment, i.e., AAKB } y. To simplify the inference process of KB, we represent it by logical forward operator (-)) such that (2)) = In
a standard neuro-symbolic learning setup (Dai al., 2019; Manhaeve et al., 2021a; Li et al., 2023; Marra et al., 2024), the training data ((x;, N are sampled from data distribution D = (2mm )))- Therefore, neuro-symbolis task can be formally defined as triple T = (B)..
Example 1 (Addition). The input E X², where X' denotes digit images. The concepts 2 consist of digits from 0 to 9. The data takes the form (o. 1 + 1, with the logical forward function at.) := SUM(..). The label space y is defined as the addition results, i.c., from 0 to 18.

---

Note that when all final labels y are identical (e.g., > KB K T), as in the case of code generation where all code must satisfy syntax constraint (Jiao et al., 2024), the final label y can be omitted for simplicity. The analysis presented in this paper can be easily adapted to such cases.
The success of NeSy systems highly depends the recognition of intermediate concepts. To eval- uate the concept-level performance, we define the concept risk as follows:
(o/1(f:g) = Eaz (f(x)) # g(x)))
For simplicity, we omit g and denote (1) as (f) However, optimizing (1) is challenging due to the lack of supervision regarding the intermediate concept.
2.2 Neuro-Symbolic Methods
To minimize the concept risk (I), the key idea of current NeSy methods (Manhaeve et al., 2018; Dai et al., 2019) is to optimize the neuro-symbolic risk as a surrogate, which aims to minimize the discrepancy between the learning and reasoning models.
Rxesy (f) ((a [I (f(x)) A KB / y)].
The optimization process is to select the optimal f* E F that minimizes the NeSy risk; that is:
f arg min (f)
SEF
Probabilistic Neuro-Symbolic Learning. Probabilistic neuro-symbolic learning (PNL, Man- haeve et al. 2021b) methods adopt reasoning models via probabilistic logic programming, such as DeepProblog (Manhaeve et al., 2018, 2021a), NeurASP (Yang et al., 2020), and Scallop (Li al., 2023). Since the NeSy risk (2) is non-continuous, PNL aims to minimize the following objective: P..))Pl [y/ <;; f, KB]
(4)
Reformulating (4), we can express the objective as follows:
(m.).)) log 2 I(
KB + y) p|z f.
(5)
Equation (5) is referred to as the probabilistic neuro-symbolic learning risk, denoted as Rf)
The key operation for calculating the PNL risk is Σ3 I(>/ABB + v) x; f. KB), also well-known as weighted model counting (WMC), which requires enumerating all possible worlds that satisfy the constraints of the symbolic system. This operation can be performed using various approaches, such as ProbLog (De Raedt et al., 2007), answer set programming Dimopoulos et (1997), and so on. However, in general, the computational complexity of WMC is #P (Maene et al., 2024), which makes PNL methods challenging to scale.
Abductive Learning. Unlike PNL methods, abductive learning methods (ABL) (Dai et al., 2019; Huang et al., 2021; Hu et al., 2025a) infer the most plausible concepts through abductive reasoning and use them to update the model. The objective of ABL is to minimize the risk:
(6) where # = min Score(z, f(x)) represents the most likely candidate in the abduction set. The abduction set A(y) includes all possible concepts z that satisfy the constraints of KB and have a non-zero measure, i.e., p|z] >> 0. The score function measures the alignment between a candidate and the model's prediction (ar) For instance, Dai et al. (2019) use the Hamming distance.
(ABL()) = - (m.,)) log (p jy, z æ;; J, KB)),
ABL enhances computational efficiency by concentrating on the most plausible candidates, thereby avoiding the enumeration of all possible worlds. However, the inherent ambiguity of abduction can lead to incorrect candidate selection, introducing bias into the learning process (He et al., 2024b).
We now present unified perspective: both PNL and ABL approaches are capable of effectively op- timizing (2), thereby allowing the analysis to be uniformly applicable to both methods. Accordingly, formally state the following theorem, with its proof provided in section B.I.
Theorem 2.1. A minimizer of RpNl or RABL is also a minimizer of RNeSy- For each surrogate R, E (ReM,, RABL), we have;
arg min Rf) C arg min RNss (f)ss(f)
JeF
fef
3

---

2.3
Related Works
Here review related works below that focus reasoning shorteuts and the theoretical analysis of neuro-symbolic learning. A more comprehensive review of related works is available in section A.
Reasoning Shortcuts. A reasoning shorteut (RS) formally defined as distribution that max- imizes the training likelihood while deviating from the true concept distribution (Marconato et al., 2023b). To address RS, a variety of mitigation strategies have been proposed, including contin- ual learning paradigms that structure tasks sequentially to promote knowledge retention (Marconato et al., 2023a), entropy regularization to encourage more faithful concept representations (Marconato et al., 2024), and the development of dedicated benchmarks for systematic evaluation (Bortolotti et al., 2024). Recent works have also introduced new metrics and theoretical analyses to better characterize and quantify shortcut risks (Yang al., 2024). Despite these advances, comprehen- sive theoretical understanding of RS remains limited, particularly regarding the specific concept error analysis under the statistical learning framework. Our work builds upon these foundations by providing a unified theoretical framework that elucidates the learnability of neuro-symbolic tasks, offering new insights into this phenomenon.
Theoretical Analyses. Prior theoretical frameworks, such as multi-instance partial label learning with the M-unambiguity condition (Wang et al., 2023), provide concept error bounds based on the VC-dimension. However, this analysis assume repetitive input patterns, such as (.. thereby limiting the applicability to real-world scenarios that require heterogeneous predicates and facts as logical inputs. Tao et al. (2024) examine scenarios where randomly selecting abduction can- didates results in a consistent optimization objective within the ABL framework. They formulate the learning process as a weakly supervised learning problem and analyze its consistency through probabilistic matrix Q. However, construction of such a matrix Q requires full knowledge of the underlying concept sequence distribution, which is not easily obtainable. Additionally, Yang et al. (2024) introduce shortcut risk metrie R, to quantify the discrepancy between true risk and surrogate risk. While they establish error bounds for this metric, a low shortcut risk does not neces- sarily guarantee low concept error. Thus, comprehensive theoretical analysis of the concept error remains lacking.
In summary, our work advances the field by providing a unified and comprehensive theoretical framework for analyzing the learnability of neuro-symbolic learning tasks. We establish necessary and sufficient conditions for learnability under mild assumptions, introduce constraint satisfac- tion perspective that enables systematic verification, and derive meaningful error bounds even in unlearnable cases.
3 Learnability Analysis
In this section, we examine the learnability of neuro-symbolic (NeSy) tasks, specifically whether the concept risk can be minimized via empirical risk minimization (ERM) over the NeSy risk as the sample size approaches infinity. While learnability is attainable in certain scenarios, it is not universally guaranteed. To elucidate the underlying reasons, we conduct a rigorous learnability analysis to address the question: Which classes of NeSy tasks are learnable?
Analogous to the standard probably approximately correct (PAC) learning framework (Valiant, 1984), formalize the learnability of NeSy task follows:
Definition 3.1. Let N denote the size of samples drawn i...d. from D, T represent NeSy task, and F denote the hypothesis space. We say that T learnable if: for any 0 < e, 8 < 1 and distribution D. there exists algorithm A and an integer Ne.s such that, whenever N 2 Ne.6. the selected hypothesis f = A(D) satisfies pl R(R (f) S 2 6. Otherwise, we say that it unlearnable.
Our analysis focuses on the ERM algorithm as A. given its proven efficacy in common learning settings such as supervised classification and regression, where a problem is learnable if and only it is learnable by HRM (Blumer et al., 1989; Alon et al., 1997).

---

3.1 Restricted Hypothesis Space
Unlike conventional supervised learning, which learns a hypothesis x + y from pairs (2; y), a NeSy task seeks mapping æ + from pairs (æ, v), where denotes latent symbolic vari- ables constrained by the reasoning module. Idcally, each y determines a unique x; that is, Vy E V. |A(y)] = 1. In this case the task reduces to a standard learning problem (Vapnik, 1999). In practice this is rarely true: many y admit multiple feasible solutions Z1...., Zs. making the task in- herently ambiguous. We call the task ambiguous if there exists y E y with [A(y) 2 2. In statistical learning theory, the complexity of a hypothesis space is characterized by the notion of shattering.
Definition 3.2 (Shattering). A hypothesis space F shatters a finite set X = {oı,..., Fmm with respect label space 2 if, for every labeling function & X Z, there exists hypothesis f E F such that fx;; = (xx)) for all 2; E X.
Using this notion, we obtain the following proposition.
Proposition 3.3. For an ambiguous NeSy task T. if the hypothesis space F shatters the task, then there exists hypothesis f" that minimizes Ryesy but does not minimize Ran-
The proof is provided in section B.2. Proposition 3.3 suggests that ambiguous NeSy tasks may be unlearnable when the hypothesis space is very complex, such nearest neighbor, whose Vapnik- Chervonenkis dimension is infinite (Karacali & Krim, 2003), or deep neural networks (Bartlett & Maass, 2003) without any regularization terms. This issue arises due to overfitting caused by the high memorization capacity of models (Zhang et al., 2021). Previous studies emphasize the importance of constraining the hypothesis space in NeSy tasks (Yang et al., 2024). For example, pre-training mod- els or self-supervised learning methods (Sohn et al., 2020) have been shown to promote clustering properties in neural networks, further enhancing generalization performance.
Consider a scenario where pre-trained model satisfies a clustering property (Huang et al., 2021), meaning that instances representing the same concept are grouped together in feature space. In the ambiguous task described in example 1, if the model correctly processes a key sample such as SUM O 0 0, it can reliably identify 0. This, in turn, simplifies subsequent tasks. For example, once the model recognizes SUM e A = 1, it can correctly identify 1. By iteratively applying this process, the model can learn to recognize all relevant concepts despite initial ambiguity.
The above process highlights the need to restrict the hypothesis space for the learning system. This hypothesis space ensures consistent mappings between concepts and labels. Let J be restricted hypothesis space which ensures that instances with the same label correspond to the same concept, and vice versa. Given the labeling function g. formally, for any f E F*:
V2 D2 E X, g(m)) = 2(x2) = f(z)) = f(22).
3.2 Derived Constraint Satisfaction Problem
The restricted hypothesis space implicitly partitions the raw input space X' into L clusters. We use (r); to denote the cluster {a x E X. f(x) = i). The learning process is to establish a mapping between the clusters (()),..... (z)) } and Z that minimizes the NeSy risk. This process inherently transforms the NeSy learning problem into a constraint satisfaction problem (CSP). In this paper, refer to it as a derived CSP (DCSP).
The derived constraint satisfaction problem for NeSy task T defined as triple (V,D, C), where: == (Vi..., Vi.} are the variables, D = {Di = Z,..., Dr = 2} are the domains, and C = =C ON are the constraints. Each V42 corresponds to a mapping from (x); to a con- cept label. For convenience, we slightly abuse notation by letting V(x) denote mapping from an input sequence to the corresponding concept sequence determined by the mapping set V. Each C, corresponds to constraint (z), My e.g., (zzz) = Vj Solving the DCSP is to find a consistent assignment that satisfies all constraints.
A DCSP solution I corresponds to an assignment of values to variables, expressed as I ((Vi, vi),...... (Vi,, ). where each vi the value assigned to the variable V,, For simplicity, we denote the solution as 7 (Vi,..., vr.) by omitting the variables. Here we only discuss the case when the DCSP has solution; Otherwise, the learning model will inevitably conflict with the background KB.
5

---

3.3 Conditions of Learnability
In general, the solution DCSP may not be unique, i.e. multiple distinct solutions may exist. We denote the solution space as S = .II.....Jy To characterize the relationships among these solutions, we define an operation Union(). which captures the common assignments among the solutions. When the input set consists of single element, this operation simply returns that element. The DCSP solution disagreement d quantifies the inconsistency among all solutions:
d == L - [Union[S)]
The disagreement d measures the number of variables whose values differ across the solutions in S. If d = O, i... |S] = 1. there is a unique solution. In this case, the optimal hypothesis can be identified by minimizing the NeSy risk. Formally, we have:
Lemma 3.4. For NeSy lask T, if the DCSP solution disagreement d 0, then the NeSy risk is consistent with the concept risk. Formally, for any f E F:
RNeS, (f) +0 = Ron(f) -.
Proof Sketch. The direction from the right-hand side to the left-hand side is straightforward: here, focus proving the reverse direction. We demonstrate this by showing that if the concept risk is non-zero, then the NeSy risk cannol be zero (contraposition). If the concept risk is non-zero, there must be least misclassified instance where assigns incorrect label. Given that the DCSP solution is unique and there no disagreement (i.e., d = 0), any such misclassification directly results in non-zero NeSy risk. Therefore, if the NeSy risk is zero, it follows that the concept risk must also be zero.
The detailed proof is in section B.3. To proceed, introduce the following mild assumption. Assumption 3.5. The set of possible concept sequences, B = Uysy A(y), where A(y) is the set of valid concept combinations for label y, has finite cardinality; and the probability of sampling concept sequence is at least K. > 0
With this assumption, we formally present the main result of this paper as follows.
Theorem 3.6. For a neuro-symbolic task T with a restricted hypothesis space F", learnability is determined by the following conditions:
If the derived constraint satisfaction problem has a unique solution, the task is learnable. Specif- ically, the concept error is bounded by provided that the sample size N satisfies:
1 K
N
log (1B1/c).
Otherwise, the task is unlearnable.
The proof is in section B.4. Theorem 3.6 establish that NeSy task T is learnable if and only if the DCSP solution is unique, i.e., disagreement d = 0. Conversely, if the DCSP has multiple solutions (i.e., d 2 1), the task is unleurnable, implying that concept error remains unavoidable regardless of additional training data.
Building upon the concept of DCSP solution disagreement, derive offering deeper insights into learning errors in a restricted hypothesis space F As the sample size approaches infinity, the hypotheses learned via ERM asymptotically converge to: FÜRM arg min (NNesy(f). The average error of the ERM result, denoted by E*, is the expected con- cept risk of an arbitrarily selected hypothesis: E- Eyerts [Ro(())
general theorem
Theorem 3.7. The average error Ex is bounded by:
d
Ex S T
The proof is in section B.5. Theorem 3.7 provides an asymptotic emror analysis for NeSy tasks, indicating that as the DCSP solution disagreement increases, the upper bound of the concept error also increases. Revealing that the disagreement d is crucial to the learnability of NeSy tasks.

---

3.4 Examples
Here, we present examples to better understand the learaailltyy conditions of NeSy task. To il- lustrate the distinction between learnable and un- learnable tasks, use digital images input data. We model the data as a = (2), x2) E X²² where X' represents the space of digit im- ages (e.g..
Table I: Examples of (un)learnable tasks.
Learnable
Addition
y
Multiplication
y/ y= R1 A2
Unlearnable
Exclusive OR
y ym (9 69.R2
}). The intermediate concept space Z and the label space Y' depend on the spe- cific knowledge base. Table summarizes these ex- amples, where modular addition task 2 S k < 10.
Modular Addition
y == mod
and vice versa, minimizes the NeSy risk. For the modular addition task (A: 9, d 0.2), swapping the mappings of 0 and 9, i.e., 0 O, + 9 and vice versa, minimizes the NeSy risk.
For the XOR task (d/L = 1), interchanging the concepts O and 1, i.c., Ø
- 0. 1
Remark 1. A direct implication from theorem 3.7 is that the expected concept error does not in- crease monotonically with the number of DCSP solutions but instead with the disagreement d. For example, in the modular addition task: (i) When & = 8, there are 4 solutions, with d/L 0.4; However, (ii) when & 10, there are only 2 solutions, yet d/L = 1. This occurs because the significant disagreement between the two solutions leads to an unbounded worst-case concept error.
3.5 Aggregation of Unlearnable Tasks
Certain NeSy tasks are inherently unlearnable because they admit multiple solutions their DC- SPs, resulting in ambiguity. This ambiguity cannot be resolved by increasing data or improving the learning algorithm,
it stems from intrinsic task properties. Interestingly, however, such unlearn- able tasks may become learnable when combined under a multi-task learning paradigm. The key insight is that tasks can mutually constrain each other, reducing ambiguity.
Consider two unlearnable tasks, Ti and T2. with their solution spaces S₁ and S2, where |Si| 2 and [S2] 2 2. In multi-task learning setting, the combined task requires satisfying constraints from both tasks at the same time, creating the solution set Sage = S1 Sgg For the combined task to become learnable, two key conditions must hold: (1) concept space overlap: 21 n Z2 & Ø; and (2) reduced DCSP disagreement: dage = 2 U Z2| [Union(Sagg) < min(d), d2). This reduction of the solution space reduces ambiguity and may lead unique solution, making the combined task learnable. Therefore, by using the mutual constraints from overlapping solution spaces, combining unlearnable tasks in aggregation framework can enable learnability. From the perspective of DCSP, we can formally state the corollary as follows:
Corollary 3.8. NeSy tasks become learnable in an frameeattonn if combining their DCSPs results in a unique solution.
4 Empirical Study
To empirically validate the theoretical results, conducted series of experiments, including arith- metic tasks shown in table I and BDD-OIA Xu et al. (2020), which is evaluated in Marconato et al. (2023b) realistic application. Due space limitations, some experimental results presented in the appendix.
Setup Manhaeve et al. (2018) proposed the digit addition task by incorporating the handwrit- ten MNIST (LeCun al., 1994) and predefined addition rules. We extend the setup by including KMNIST (Clanuwat et al., 2018), CIFARIO Krizhevsky (2009), and SVHN (Netzer et al., 201 1), mapping class indices digits, e.g., CIFAR-10 classes (airplane
O....) and enriching the background knowledge as depicted in table 1. The learning model for MNIST and KMNIST is LeNet (LeCun & Bengio, 1998), while ResNet50 (He et al., 2016) is used for CIFARIO and SVHN. Besides that, we also adopt BDD-OIA from Bortolotti et al. (2024), which is a multi-label au- tonomous driving task for studying RSs in real-world, high-stakes scenarios. All experiments were conducted five times with different random seeds. Details can be seen in section C.
7

---

Mod Adliion
Ailion
Medl Addiio
Mal Nitiio
Mai Adliion
pakeo Gropp
Any Agropedd Doard
Adiiiie
Mod Allibrr
Mei Adliinn bwd
Med MAlioan Lom
Mal Malionle
Mal Adliiie 2
Crncug
Doard
Figure I: Accuracies versus sample size for different NeSy tasks (top MNIST and bottom KMNIST). The shadowed area denotes the standard error. The number of the DCSP solutions (#Sols) is shown at the top left of each plot. The asymptotic bound (green line) from theorem 3.7 indicates that concept accuracy should exceed this bound the sample size grows.
Method To effectively optimize the NeSy risk (2), we adopt the following surrogate (cf. proof in section B.1):
(B(r))) log
Σ
P plV, x; f, KB]
SEN(()
which is flexible, where Nwy S. A(v) represents several valid candidates for the final answer y. By restricting the size of N(r) from the entire set A(y) to the most likely candidate 2, we achieve a balance between PNL and ABL, and we set the size of (yy) is min (16, [A(y))). The implementation is based on the code of He et al. (2024b). For brevity, detailed experiments on PNL and ABL are provided in section C.
4.1 Empirical Analysis on Learnability
We empirically evaluate the learnability of NeSy tasks based on theorem 3.6, focusing on two key aspects: (i) validating that minimizing the NeSy risk consistently minimizes the concept risk for learnable tasks, and (ii) examining how DCSP solution disagreement affects learnability.
1.00
Aoaney
0.75
0.30
0.25
0101
Chenept
Reconiing Aox
(i) Validation of learnable tasks. We first vali- date the learnability conditions (ef. theorem 3.6) by examining addition and multiplication tasks
Figure 2: Accuracies on the learnable tasks.
(cf. table 1). Solving the DCSP shows that both tasks are learnable, and their learnability remains unaffected by increases in digit size (e.g., from PROD H F 2 to PROD
2 200).. The
raw dataset in figure MNIST, and additional results for other datasets are in the appendix. We further substantiate learnability by examining tasks with varying digit sizes, ranging from one to four digits. As depicted figure the results confirm that: (a) Optimization of the surrogate risk (7) effectively minimizes the NeSy risk. (b) For learnable tasks, good minimizer of the NeSy risk also serves as reliable minimizer of the concept risk.
(ii) Impact of DCSP solution disagreement. We further investigate how disagreement in DCSP solutions impacts learnability. According to theorem 3.7, the asymptotic error is bounded by the ratio of DCSP solution disagreement d to the size of the concept space L. Experiments involving addition and modular addition tasks with varying modular bases reveal that altering the knowledge base changes the DCSP solution space, directly influencing learnailliy.. For clarity, we plot the asymptotic accuracy bound for each task, i.e.. d/ L, showing that higher disagreement results in lower bound line (green). As shown in figure 1: (a) Tasks with unique DCSP solution are learnable; (b) Tasks with high DCSP disagreement struggle to achieve low concept risk, even as the sample size increases.
8

---

Mod Acaition
Mld Additon
Apprgation 1)
Additia
Med Naltic
Agangatinn:
Prodedd
Upen
lpeck
Appegation 9)
=3
Apprrptions..
Touse
Cirecy Aet
Prodeod
Procicol
Droladt
Epoch
Figure 3: Aggregation of unlearnable NeSy tasks. The left shows confusion matrices and the right displays accuracy curves. (a) The top row illustrates unlearnable case, where combining the tasks still results in multiple DCSP solutions. (b) The bottom row illustrates a learnable case, where combining the tasks reduces the DCSP solutions to single one.
In summary, our empirical analysis confirms the theoretical learnability conditions by demonstrating that minimizing the NeSy risk reliably minimizes the concept risk for learnable tasks. Furthermore, tasks with lower disagreement exhibit better learnability, while those with high disagreement suffer from ambiguity due to multiple conflicting solutions.
4.2 Further Evaluation on Realistic Task: BDD-OIA
We further extend our experiments to the real- istic BDD-OIA task, a multi-label autonomous driving benchmark in real-world, high-stakes scenarios. The knowledge base KB encodes, for example, that it is unsafe to move forward when pedestrians are present, using set of 21 binary concepts indicating various obstacles on the road. The constraints specify condi- tions for proceeding (greenlight V follow V clear + forward), stopping (red V stop sign V obstacle = stop), turning left and right, and relationships between actions (e.g., stop = -forward). In this task, there are 74,240 DCSP solutions, and the disagreement among these solutions is 15, indicating typically unlearnable problem under our criterion. We evaluate several methods on this task: LTN and DeepProbL.og are implemented using the rsbench code- base (Bortolotti al., 2024), whereas ABL and A BL use their official implementations.
Table 2: Accuracies and standard deviations the BDD-OIA task across five seeds.
Method
Reasoning Ace
Concopt, Ace
LTN (Badreddine et al., 2022)
27 27.22_.5. 50
20.41
DeepProbl (Manhaeve al., 2021a) al., 2019)
0.00
16
20.0236.0
A'BL (He et al., 2024b)
60 60.91:m00
88.37
4.3 Aggregation of Unlearnable NeSy Tasks
With the DCSP framework, we find that certain NeSy tasks are inherently unlearnable because their DCSPs admit multiple solutions, resulting in inherent ambiguity. However, when combined in an aggregation framework within a multi-task learning setting, such tasks may become learnable by enforcing mutual consistency, as shown in corollary 3.8. We evaluate corollary 3.8 using mod addi- tion tasks with mod bases Yj and 22 under two specific configurations: an unlcarnable aggregation (k) 2, 22 3) and a learnable aggregation (k1 = l2 4). For k 2, 3, 4, the degree of DCSP solution disagreement d is 10. The experiments in figure are based on the raw MNIST dataset. Additional details and experiments are provided in section C.2.3.
In the top of figure 3, the unlearnable case (k: = 2, k2 = 3) shows that while the aggregation nar- rows the solution space, reducing the disagreement d to 8, it does not converge to a unique solution, and the task remains unlearnable. In the bottom of figure 3, the learnable case (k) 3, ką = 4) illustrates that both tasks initially admit multiple DCSP solutions, causing reasoning accuracy to exceed concept accuracy, as shown in figure 3. Through the aggregation, the intersection of solution spaces shrinks, with the disagreement d reduced to 0, making the aggregation task learnable.

---

This experimental result supports corollary 3.8, demonstrating that forming aggregations of different NeSy tasks can enhance learnability by mutually constraining DCSP solution spaces. This finding suggests that collecting tremendous NeSy tasks and jointly learning them in an aggregation manner could improve the learnability and potentially introduce a "scaling law" (Kaplan et al., 2020) in the NeSy domain.
Limitations and Future Directions
This paper focuses exclusively on hybrid neuro-symbolic systems, e.g., probabilistic neuro-symbolic and abductive learning methods. Thus the findings may not directly extend to other types of neuro- symbolic methods. The analysis of this study relies on restricted hypothesis space, which is in- herently satisfied by models such as neural networks equipped with manifold regularization (Belkin et al., 2006) self-supervised pretraining (Liu et al., 2021). However, extending the framework to encompass more general hypothesis spaces without requiring this specific property remains an open challenge.
Future work may involve a deeper investigation into extending the learnability framework to en- compass broader range of NeSy systems. Additionally, exploring the learnability of the semi- supervised case of NeSy tasks, where some training examples are supervised for intermediate con- cepts, could be an interesting direction. Developing practical strategies for constructing effective task aggregations aslo represents a promising avenue for improving learnability in many scenarios.
Moreover, because solving CSPs is NP-hard in general. the DCSP framework may face compu- tational scalability challenges for large-scale knowledge bases. Future directions include approx- imation methods such as compling-based estimation (e.g., uniform sampling Heradio et al. 2020), incorporating practical heuristics (e.g., exploiting symmetries the knowledge base), and decom- posing complex knowledge bases into simpler sub-tasks with tractable CSPs (Hu et al., 2025b).
Conclusion
We establish that neuro-symbolic task is learnable if and only if the derived constraint satisfac- tion problem (DCSP) has a unique solution. This conclusion is consistent with previously found conduct comprehensive analysis
reasoning shortcuts problem. With the DCSP framework, on sample complexity and concept error based on the disagreement d among these solutions. This framework also implies that forming aggregations of unlearnable tasks reduces the disagreement d, thereby enhancing overall task learnability.
Acknowledgements
This work was supported by the National Natural Science Foundation of China (62076121) and the Major Program (JD) of Hubei Province (2023BAA024), Prof. Ming Li the corresponding author. The authors thank Lue Tao for helpful feedback on earlier drafts of the paper and the anonymous reviewers for their valuable comments.
References
Agiollo, A., Rafanelli, A., Magnini, M., Ciatto, G., and Omicini, A. Symbolic Knowledge Injection Meets Intelligent Agents: QoS Metrics and Experiments. Autonomous Agents and Multi-Agent Systems, 37(2), June 2023.
Alon, N., Ben-David, S., Cesa-Bianchi, N., and Haussler, D. Scale-sensitive Dimensions, Uniform Convergence, and Learnability. Journal of the ACM, 44(4):615 631,, July 1997.
Badreddine, S., d' Avila Garcez, A., Serafini. L.. and Spranger, M. Logic Tensor Networks. Artificial Intelligence, 303(C), 2022.
Bartlett, P. and Maass, W. Vapnik-CCerrvoenkiis Dimension of Neural Nets. The Handbook of Brain Theory and Neural Networks, pp. 1198, 2003.
10

---

Belkin, M., Niyogi, P., and Sindhwani, V. Manifold Regularization: A Geometrie Framework for Learning from Labeled and Unlabeled Examples. Journal of Machine Learning Research, 7(11), 2006.
Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M. K. Learnability and The Vapnik- Chervonenkis Dimension. Journal of the ACM, 36(4):929-96) October 1989.
Bortolotti, S., Marconato, E., Carraro, T., Morettin, P., van Kricken, E., Vergari, A., Teso, S., and Passerini, A. A Yeuro-Syybollt Benchmark Suite for Concept Quality and Reasoning Shortcuts. In Advances in Neural Information Processing Systems 37, pp. 115861-115905, 2024. Datasets and Benchmarks Track.
Cai, L.-W., Dai, W.-Z.,, Huang, Y.-X., Li, Y.-F., Muggleton, S., and Jiang, Y. Abductive Learning with Ground Knowledge Base. In Proceedings of the 30th International Joint Conference on Artificial Intelligence, pp. 1815-1821, Virtual, 2021.
Ciatto, G., Sabbatini, F., Agiollo, A., Magnini. M., and Omicini, A. Symbolic Knowledge Extraction and Injection with Sub-symbolic Predictors: A Systematic Literature Review. ACM Computing Surveys, 56(6), March 2024.
Clanuwat, T., Bober- Irizar, M., Kitamoto, A., Lamb, A.. Yamamoto, K., and Ha, D. Deep Learning for Classical Japanese Literature. CoRR, abs/ 1812.11718, 2018.
Dai, W.-z., Xu, Q. Yu, Y., and Zhou, Z.-H. Bridging Machine Learning and Logical Reasoning by Abductive Learning. In Advances in Neural Information Processing Systems 32, pp. 2815-2826, Vancouver, BC, Canada, 2019.
De Raedt, L., Kimmig, A., and Toivonen, H. ProbLog: A Probabilistic Prolog and Its Applica- tion in Link Discovery. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, pp. 2468-248200 2473, Hyderabad. India, 2007.
Dimopoulos, Y., Nebel, B., and Koehler, J. Encoding Planning Problems in Nonmonotonic Logic Programs. In Proceedings of the 4th European Conference on Planning, pp. 169-181, Toulouse, France, 1997.
Gao, E.-H., Huang, Y-X., Hu, W.-C., Zhu, X.-H., and and. W.-.. Knowledge-nhhaneed Histor- ical Document Segmentation and Recognition. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, pp. 8409 8416, Vancouver, BC, Canada, 2024.
Garcez, d., Gabbay, M., and Broda, B. Seuuol-Symbolic Learning System: Foundations and Applications. Springer-Verile Verlag, Berlin, Heidelberg, 2002.
He, H.-Y,, Dai, W.-Z., and Li, M. Reduced Implication-bias Logic Loss for Neuro-symbolic Learning. Machine Learning, 113:3357-3377, 2024a.
He, H.-Y., Sun, H., Xie, Z., and Li, M. Ambiguity-aware Abductive Learning. Proceedings of the 41st International Conference Machine Learning, volume 235, pp. 18019-18042, Vienna, Austria, 2024b.
He, K., Zhang, X., Ren, S., and Sun, J. Deep Residual Learning for Image Recognition. In Proceed- ings of the 2016 IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, Las Vegas, NV, USA, 2016.
Heradio, R., Fernandez-Amoroo D.,, Galindo, J. A., and Benavides, D. Uniform and Scalable SAT- sampling for Configurable Systems. In Proceedings of the 24th ACM Conference on Systems and Software Product Line, SPLC '20, New York, NY, USA, 2020. Association for Computing Machinery.
Hitzler, P. and Sarker, M. K. (eds.). Neuro-Symbolic Artificial Intelligence: The State the Art. IOS Press, Amsterdam, 2022.
Hu, W.C.., Dai, W.-.., Jiang, Y., and Zhou, Z.-H. Efficient Rectification of Neuro- Neuro-Symbolic Rea- soning Inconsistencies by Abductive Reflection. In Proceedings of the 39th AAAI Conference on Artificial Intelligence, Philadelphia, USA, 2025a. 17333-17341.

---

Hu, W.-C., Li, Q.JJ,, L.-H., Ge. Li, Y.-F.. Jiang. Y., and Zhou, Z.-H. Curriculum Abductive Learning. Advances in Neural Information Processing Systems, 38, pp. To appear. San Diego, CA, USA, 2025b.
Huang, Y.X.,, Dai, W.-z., Cai, L.-W., Muggleton, S. H., and Jiang, Y. Fast Abductive Learning by Similarity- basted Consistency Optimization. In Advances in Neural Information Processing Systems 34, pp.
Virtual, 2021.
Huang, Y.-X., Hu, W.-C., Gao, E.-H., and Jiang, Y. ABLkit: A Python Toolkit for Abductive Learning. Frontiers of Computer Science, 18(6):86354,, 2024.
Jiao, Y., De Raedt, I.., and Marra, G. Valid Text-to-SQL. Generation with Unification-Basel Deep- Stochl.og In NNural-Symbol Learning and Reasoning: 18th International Conference, NeSy, pp. 312-330, Berlin, Heidelberg, 2024. Springer- Verlag.
Kaplan, J.. McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A. Wu, J., and Amodei, D. Scaling Laws for Neural Language Models, 2020. URL https: //arziv. werg/aba/2000 2ttp//200..8.....
Karacali, B. and Krim, H. Fast Minimization of Structural Risk by Nearest Neighbor Rule. IEEE Transactions on Neural Networks, 14(1): 14(1):127-137, 2003.
Kingma, D. P. and Ba, J. Adam: A Method for Stochastic Optimization. In The 2nd International Conference on Learning Representations, San Diego, CA, USA, 2015.
Krizhevsky, A. Learning Multiple Layers of Features from Tiny Images. Technical Report, Depurt- ment of Computer Science, University of Toronto, 2009.
LeCun, and Bengio, Y. Convolutional Networks for Images. Speech, and Time Series. In The Handbook of Brain Theory and Neural Networks, pp. 255-258. MIT Press, Cambridge, MA, USA, 1998.
LeCun, Y., Cortes, C., and Burges, C. C. The MNIST Database of Handwritten Digits, 1994. URL http:: //yan.. lecun. com/exdb// wudb/mmist/.....
Li, Z., Huang, J., and Naik, M. Scallop: A Language for Neurosymbolic Programming, Proceedings of the ACM on Programming Languages, 7(LDII), June 2023.
Li Z. Huang, Y., Li, Z., Yao, Y., Xu, J., Chen, T., Ma, X., and Lü, Neuro-Symbolie Learning Yielding Logical Constraints. In Advances in Neural Information Processing Systems, 38, pp. 21635 21657, New Orleans, LA, USA, 2024.
Liu, X., Zhang, F., Hou, Z.,, Mian, L.., Wang, Z.,, Zhang, J.,, and Tang, J. Self-Supervised Learning: Generative or Contrastive. IEEE Transactions on Knowledge and Data Engineering, 35(1):857- 876, 2021.
Maene, J., Derkinderen, V., and De Raedt, L. On the Hardness of Probabilistic Neurosymbolic Learning. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 34203-3422 Vienna, Austria, 2024.
Magnini, M., Ciatto, G., and Omicini, A. On the Design of PSyKI: A Platform for Symbolic Knowledge Injection into Sub-symbolic Predictors. In Explainable and Transparent Al and Multi- Agent Systems: 4th International Workshop, EXTRAAMAS 2022, pp. 90-108, Berlin, Heidelberg, 2022.
Manginas, N., Paliouras, G., and Raedt, L. D. NeSyA: Neurosymbolic Automata. In Proceedings of the 34th International Joint Conference on Artificial Intelligence, pp. 5950-5958, Montreal, Canada, 2025.
Manhaeve, R., Dumančić, S., Kimmig, A., Demeester, T., and De Raedt, L. DeepProbLog: Neural Probabilistic Logic Programming. In Advances in Neural Information Processing Systems 31, pp. 3753-3763, Montréal, Canada, 2018
Manhaeve, R., Dumančić, S., Kimmig, A., Demeester, T., and De Raedt, L.. Neural Probabilistic Logic Programming in DeepProbL.og. Artificial Intelligence, (98(C))10350) 2021a.
12

---

Manhaeve, R., Marra, G., Demeester, T., Dumancic, S.. Kimmig, A., and De Raedt, L. Neuro- Symbolic AI Neural + Logical + Probabilistic AL. Neuro-Symbon Artificial Intelligence: The State of the Art, volume 342 of Frontiers in Artificial Intelligence and Applications, pp. 173- 191. IOS Press, 2021b.
Mao, J.. Gan, C., Kohli, P.. Tenenbaum, J. B., and Wu, J. The Souro-Symbolic Concept Leamer: Interpreting Scenes, Words, and Sentences From Natural Supervision. In The 7th International Conference on Learning Representations, New Orleans, LA, USA, 2019.
Marconato, E., Bontempo, G., Ficarra, E., Calderara, S., Passerini, A., and Teso, S. Neuro-Symbolic Continual Learning: Knowledge, Reasoning Shortcuts and Concept Rehearsal. In Proceed- ings of the 40th International Conference on Machine Learning, volume 202, pp. 23915-23936. JMg..org, 2023a.
Marconato, E., Teso, S., Vergari, A., and Passerini, A. Not All Neuro- Seuro-Symbolic Concepts Are Cre- ated Equal: Analysis and Mitigation of Reasoning Shortcuts. In Advances in Neural Information Processing Systems, volume 36, pp. 72507-72539, 2023b.
Marconato, E., Bortolotti, S., van Krieken, E., Vergari, A., Passerini, A., and Teso, S. BEARS Make Neuro-Symbolln Models Aware of their Reasoning Shortcuts. In Proceedings of the 40th Conference on Uncertainty in Artificial Intelligence, volume 244, pp. 1399-2433 PMLR, 2024.
Marra, G., Dumančić, S., Manhaeve, R., and De Raedt, L. From Statistical Relational to Neuro- symbolic Artificial Intelligence: A survey, Artificial Intelligence,
2024.
Netzer, Y.. Wang, T., Coates, A., Bissacco, A., Wu, B., and Ng, A. Y. Reading Digits in Natural Images with Unsupervised Feature Learning. In NIPS Workshop on Deep Learning and Unsuper- vised Feature Learning, Granada, Spain, 2011.
Prud homme, C. and Fages, J.-G, Choco-solver: A Java Library for Constraint Programming. Jour- nal of Open Source Software, 7(78):4708, 2022.
Roychowdhury, S., Diligenti, M., and Gori, M. Regularizing Deep Networks with Prior Knowledge: A Constraint-based Approach. Knowledge-Based Systems, 222: 106989, 2021.
Smet, L. D., Venturato, G., Raedt, L. D., and Marra, G. Relational Neurosymbolic Markov Models. In Proceedings of the 39th AAAI Conference on Artificial Intelligence, Philadelphia, USA, 2025. 16181-16189
Sohn, K., Berthelot, D., Carlini, N., Zhang, Z., Zhang, H., Raffel, C., Cubuk, E. D., Kurakin, A., and Li, C. FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence. In Advances in Neural Information Processing Systems 33, pp. 596 608, Virtual Event, 2020.
Sun, R. Integrating Rules and Connectionism for Robust Commonsense Reasoning, pp. 273. John Wiley& & Sons, Inc., 1994.
Tao, L., Huang, Y.-X., Dai, W.-z., and Jiang, Y. Deciphering Raw Data in Neuro-Symbol Learning with Provable Guarantees. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, pp. 15310 - 15318, Vancouver, BC, Canada, 2024.
Towell, G. G. and Shavlik, J. W. Knowledge-based Artificial Neural Networks. Artificial Intelli- gence, 7011):119-165, 1994.
Valiant, L. G. A Theory of The Learnalle. Communications of the ACM, 27(1111134-1142, November 1984.
van Krieken, E., Acar, E.,, and van Harmelen, F. Analyzing Differentiable Fuzzy Logic Operators. Artificial Intelligence, 302:103602. 2022.
Vapnik, N. An Overview of Statistical Learning Theory. IEEE Transactions on Neural Networks, 10(5):988 999899991111 1999.
Verreet, V., De Raedt, I.., and Bekker, J. Modeling PU Learning Using Probabilistic Logic Program- ming. Machine Learning, 135-311335--1322,, 2023.
13

---

von Rueden, L., Mayer, S., Beckh, K., Georgiev, B., Giesselbach, S., Heese, R., Kirsch, B., Pfrom- mer, J., Pick, A., Ramamurthy, R., Walczak, M.. Garcke, J., Bauckhage, C., and Schuecker, J. Informed Machine Learning- A Taxonomy and Survey of Integrating Prior Knowledge into Learning Systems. IEEE Transactions on Knowledge and Data Engineering, 35(1):614-633, 2023.
Wang, J., Deng, D., Xie, X., Shu, X.., Huang, Y.-X., Cai, L.-W., Zhang, H., Zhang, M.-L., Zhou, Z.- H., and Wu, Y. Tac- Valuer: Knowledge-baseee Stroke Evaluation Table Tennis. Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pp. 3688-3696 3696, Virtual Event, Singapore, 2021.
Wang, K., Tsamoura, E., and Roth, D. On Learning Latent Models with Multi-instance Weak Supervision. In Advances in Neural Information Processing Systems 36, pp. 9661 9694, New Orleans, LA, USA, 2023.
Xu, J., Zhang, Z., Friedman. T., Liang, Y., and Van den Broeck, G. A Semantic Loss Function for Deep Learning with Symbolic Knowledge. In Proceedings of the 35th International Conference on Machine Learning, pp. 5502-5511, Stockholm, Sweden, 2018.
Xu, Y., Yang, X., Gong, L., Lin, H.-C., Wu, T--., Li, Y., and Vasconcelos, N. Explainable Object- Induced Action Decision for Autonomous Vehicles. In Proceedings of the 2020 IEEE Conference Computer Vision and Pattern Recognition, pp.
Vritual, 2020.
Yang, X.-W., Wei, W.-D., Shao, J.JJ,, Li, Y.-F,, and Zhou, Z.-H. Analysis for Abductive Learning and Symbol-Symbolic Reasoning Shortcuts. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 56524-56541, Vienna, Austria, 2024.
Yang, Z., Ishay, A., and Lee. NeurASP: Embracing Neural Networks into Answer Set Program- ming. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pp- 1755-1762 1762, Yokohama, Japan, 2020.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding Deep Learning (Still) Requires Rethinking Generalization. Communications of the ACM, 64(3):007-115, 2021. 2021.
Zhou, Z.-H. Abductive Learning: Towards Bridging Machine Learning and Logical Reasoning. Science China Information Sciences, 62(7):76101, 2019.
14

---

Appendix
The appendix is structured as follows.
Section A contains discussion about reasoning shortcuts and previous theoretical works.
Section contains proofs omitted in the main paper, because of the space limit.
Section C contains more details and additional experiments.
A Extended Related Works
To contextualize and highlight the distinct contributions of this work, we undertake comprehensive and critical analysis of several closely related studies in neuro-symbolic learning.
A.1 Neuro-Symbolic Methods
The combination of leamingg and reasoning remains the holy grail problem of Al for decades now (Towell & Shavlik, 1994; Sun, 1994; Gareez et al., 2002). One promising approach is to di- rectly incorporate logical constraints into the loss function as the optimization objective (Xu al., 2018; Roychowdhury et al., 2021; Badreddine et al., 2022). However, since the logical constraint is discrete, the optimization must projected into the continuous space. This requires an approxima- tion of logical reasoning. Such approach can lead to issues when approximating discrete logical computations (van Kricken et al., 2022; He et al., 2024a). It is also worth noting that there is a line of research on knowledge extraction and injection for perception models (Ciatto et al., 2024; von Rueden et al., 2023; Agiollo et al., 2023; Magnini et al., 2022).
A more effective approach is the hybrid system, where both the learning and reasoning mod- els function their full capacity. For instance, DeepProbLog (Manhaeve al., 2018, 2021a), NeurASP (Yang et al., 2020), and Scallop (Li et al., 2023) employ probabilistic logic program- ming as their reasoning model. ABL (Zhou, 2019; Dai et al., 2019) employs abductive reasoning for logical inference. Recently. there have been some studies on NeSy with auto-regressive or temporal models (Manginas et al., 2025; Smet et al., 2025). Building on the hybrid approach, there have been many successful applications (Mao et al., 2019; Wang al., 2021: Cai et al., 2021; Verreet et al., 2023; Gao et al., 2024; Jiao et al., 2024). Since the hybrid approach has shown its superiority, is worthwhile to establish a theoretical framework for analyzing its learnability.
A.2 Reasoning Shortcuts Works
Marconato al. (2023b) gave a formal definition of reasoning shorteut (RS):
A reasoning shortcut is distribution PC X) that achieves maximal log- likelihood on the training set but does not match the ground truth concept dis- tribution, C(ps. D. K) = max D(pg, A Po x
8'E0
They further proposed several approaches mitigate this issue. Furthermore, Marconato et al. (2023a) propose a new paradigm that combines continual learning with neuro-symbolic learning by structuring multiple NeSy tasks as a sequential process, which may help mitigate the RS problem. Subsequently, Marconato et al. (2024) use entropy regularization to address the RS problem. Bor- tolotti et al. (2024) construct benchmark evaluate this problem. Although the RS problem has been studied, an in-depth theoretical explanation and analysis still lacking.
Our analysis provides new insights into the RS problem. From the perspective of DCSP, we can gain deeper understanding of the RS problem. The presence of multiple DCSP solutions directly corresponds to the existence of deterministic RSs, as defined in Marconato et al. (2023b). Instead of simply counting solutions, we argue that disagreement offers a more nuanced characterization of concept error. Moreover, key implication of theorem 3.7 is that concept error does not increase monotonically with the number of DCSP solutions; instead, it depends on their level of disagree- ment (cf. remark l).
15

---

A.3 Theoretical Works
Several works have explored theoretical insights into neuro- suuro-yymooli learning. Below, we provide discussion of these efforts and contrast them with our contributions.
Wang et al. (2023) introduces multi instance partial label learning (MI-PLL) and proposes an "M- unambiguity" condition for learnability. They define this condition as follows:
A transition is M-unambiguous if. for any two diagonal label vectors and x' E ZM such that # z', we have (z)) & ozz)).
Here, we slightly modify the notation ensure consistency with this paper. diagonal label vector consists of identical elements in every position. When M 1, the concept label can be directly inferred from the transition function a, reducing the problem to standard supervised learning setting with well-established learnability guarantees. Building upon this condition, they derive concept error bound based on the VC-dimension.
Compare with Wang et al. (2023), the advantages of our work are:
a) Their learnability condition assumes repetitive imput patterns (c.g.. (....... to satisfy sym- bolic constraints, which is unrealistic in practical applications. For example, in autonomous driving scenarios, neuro-symbolic systems usually process diverse predicates and facts, contra- dicting this assumption. In contrast, our framework provides a more general learnability analy- sis that is both easier to verify using modern constraint satisfaction problem (CSP) solvers and applicable to both probabilistic neuro-symbolic learning and abductive learning.
b) Even unlcarnable cases, our approach establishes lower bound for concept error by analyz- ing the disagreement among DCSP solutions, offering insights into these unlearnable scenarios.
Tao et al. (2024) examine scenarios where randomly selecting abduction candidates results a consistent optimization objective within the abductive learning (ABL) framework. They formulate the learning process as a weakly supervised learning problem and analyze its consistency through a probabilistic matrix Q E Rexx pee((m=22 (m (cf. Section 3 in Tao et al. (2024)).
Let & E (0....,12] 1} and o tm + k, Qio represents the probability of the class j occuring at the k-th position sequence of final label
If Q is full-rank, the concept-level supervision be fully recovered, ensuring that the task is learnable under their ABL formulation. However, construction of such a matrix Q requires full knowledge of the backhind concept sequence distribution, which is not easy to derive.
Yang et al. (2024) introduce shortcut risk metric R, quantify the discrepancy between true risk and surrogate risk:
R, = - Ex, (o (x) +
Σ
log Σ 1| KB = y] po(2 xx)
(æ.8)ED
LEZ
They further establish an upper bound on R, based the complexity of the knowledge base:
Em,y Reg] S log (C DRB) + +
where Dxs :- Ez [EzEz I( KB / v)] measures knowledge base complexity, C is the size of concept sequence space, and 7 is a constant dependent on the hypothesis space. However, a low R. does necessarily imply low concept error, meaning their results do not directly establish the Icarnability of NeSy tasks. Furthermore, their complexity measure does not account for depen- dencies between concept sequences. Consequently, the derived bound loose and they classify the addition task as "unbounded" (cf. Definition 4. in Yang et al. (2024)). In contrast, our analysis and experiments demonstrate that it is learnable under a restricted hypothesis space.
16

---

B Proofs
In this section, we give the proofs that are omitted in the main text. For the convenience of the reader, we re-state the assumptions, lemmas, propositions, and theorems in the appendix again.
B.1 Proof of Theorem 2.1
Theorem 2.1. A minimizer of RpNL RABL is also minimizer of RNesy- For each surrogate Rg E (Beai, RAML), we have:
arg min R,(f) S arg min RNesy(J FEF
JEF
Proof. First, we recall the risks as follows:
x; KBBB] RFxL(f) = E(e.v) log Σ I(z A KB F v) piz
(ABL(f) = (w log (p [y+ # x;; f.KB)
To unify the proof, we introduce (7) as a surrogate form:
(f* (a) log
Σ
ply x;; f. KB]
$EN(w)
where the (yy) denotes the candidate set satisfying:
Vz EN, A y
Furthermore, we reformulate the PNL risk using a union-based representation:
ReNu (f) (mr,) log
Σ
I(z A KB 1 v)
i= æ;; KB]
zEA(y)
= --E log
Σ *EA(N)
Plu.
x; f. KB]
Consequently, Rx* emerges flexible surrogate. By adjusting the size of the candidate set, interpolate between the ABL risk and the PNL risk. Thus, it suffices to prove that for any candidate set (y), RAi achieves the desired objective.
Since the following properties hold:
For any f E F, the risk R (f) 2 O.
For the labeling function g, the risk Rga(g) =0
Therefore, the minimum achievable value of this risk is strictly 0. For any f E arg minjer RA (f), have Rx* which implies that, for fixed candidate set N(y) and any (æ, v):
Σ ply. z (ffKKB xEN(y)
Σ I[EAXB v) po (2 x) $EN(M)
Consequently, any predicted by the learning model f with a probability greater than zero will satisfy the knowledge base, i.e., 2 A KB - y. This ensures that the NeSy risk RNesy (J) B. (x*( A KB / v)] also zero. Since the NeSy risk should also be greater or equal to
zero, which means the hypothesis f is minimizer of NeSy risk. Hence, the proof is complete. D
17

---

B.2 Proof of Proposition 3.3
Proposition 3.3. For an ambiguous NeSy task T, if the hypothesis space F shatters the task, then there exists hypothesis f" that minimizes Riesy but does not minimize Ran-
Proof. By the definitions of RNeSy and Ran, we have:
Rxesy (ʃ) = E( [T (f((z) A KB /f v)],
and, thus,
Ron (f) = Bu,, [I( + 2)]
Since T is ambiguous, i.c., there exists a E Y such that [A(y) 2 2, we assume, without loss of generality, sample pair (æo, vo) E (2eT .)) such that (21, 22) C A(bo).
Given that the hypothesis space sufficiently complex to shatter the task, we assume the existence of two hypotheses fi and fz that yield identical correct predictions for all inputs except æp:
(xo0 21, (x) f2(x)
f2(
if x 3o. otherwise.
By definition, as fi and f2 yield identical predictions except at Lo. we have RNesy (f1) RNesy (f2). However, since 21 * ø2, there exists at least one index E [m]] such that (z1)R + (z2)x- Thus, by the definition of Ron. we observe that Rao (fi) + Roo (f2), as at the sample (æo)), they produce two distinct recognition results.
In this scenario, even if fi represents the underlying ground truth mapping function, it is indistin- guishable from f2. as both achieve zero risk under the optimized objective RNesy. This concludes that RNesy 0) * RRnn + 0).
B.3 Proof of Lemma 3.4
Lemma 3.4. For a NeSy task T, if the DCSP solution disagreement d 0, then the NeSy risk consistent with the concept risk. Formally, for any I E F;;
RieSs (f) -0 + Ran(f) +
Proof. We first prove the direction:
(Rresy 0) (Ray 0)
This is evident because, as Ryi approaches zero, f must correctly classify all input-output pairs, which consequently drives Ryesy to zero as well.
Next, we prove the direction: (Ryesy + 0) = (Ran + 0). Equivalently, we prove the contraposi- tive:
(Ron A 0) + (Rresy A 0).
Suppose Roi A 0. Then, there exist integers i, [7.] with * such that / misclassifies elements of the set
(x); = (x x E g())) =i]
as belonging to class j.
Recall that the DCSP of T has a unique solution, which ensures that the correct labels are unam- biguous. As the training size grows, there must exist sample (æ, v) E (X",))) such that set(x:) O (x)) * ø and f'(x) & A(y). This implies that Riesy / O.
Thus, by proving both directions, complete the proof.
18

---

B.4 Proof of Theorem 3.6
First, we recall that the learnability analysis depends on two assumptions.
Assumption 3.5. The set of possible concept sequences, B = Uysy A(y), where A(y) is the set of valid concept combinations for label y, has finite cardinality; and the probability of sampling concept sequence is at least 6. > 0
Based on the assumptions, we first prove the below lemma, which states the sample complexity under the learnable case, when the hypothesis space is restricted hypotheses space.
Lemma B.1. Consider NeSy task T with above assumptions and d O. By applying empirical risk minimization, the hypothesis f arg jen- Rf ensures that Rai(f) S for any e > O, provided that the training size N satisfies the inequality:
1 K
B
N
-log
E
Proof. Recall that empirical risk minimization, based on the neuro-symbolic risk Rsasy. corresponds solving derived constraint satisfaction problem over the restricted hypothesis space FF. By lemma 3.4, if the training set includes all possible concept sequences, the minimum value of ANesy becomes zero. This ensures that Ron also attains value of zero. Therefore, it crucial analyze the sampling process of the training data.
Let Q denote the event that "not all concept sequences sampled in the training data". The concept risk is the probability of event that "for a random sample (æ,, 2). the learned hypotheses wrongly classified, i.e., p*f * 2)". It is obvious that event P is included by event Q in the probabilistic space. Therefore, we conclude that the true risk bounded by the probability of event Q:
Rav (f) = p(f(()) # p(Q).
To bound Ran, it suffices to bound p(Q). For any individual concept sequence 2,, the probability that it is not sampled after N draws is given by:
(1 p.) 5 (1-x)) K)
Applying the union-bound inequality, we derive:
p[Q] < |B] (1 k)
Since (1 1)) S (xp((xx) holds for x 2 0, we can further bound Ron (f) as follows:
Rai (f) < p[Q] < [ exp(-N k).
Given that Ron (f) S e, it follows that:
B E
N
log
This completes the proof of the proposition.
Theorem 3.6. For mymoosymbolic task T with restricted hypothesis space F*, learnability is determined by the following conditions:
the derived constraint satisfaction problem has a unique solution, the task is learnable. Specif- ically, the concept error is bounded by provided that the sample size N satisfies:
1 K
N
log (IB)/e).
Otherwise, the task is unlearnable.
Proof. The proof is divided into two parts:
19

---

1. If the disagreement d equals zero, the task is learnable, and the sample complexity is ( lo)(())/c))
2. If the disagreement d is greater than zero, the DCSP solution space contains least two distinct solutions, making the task unlearnable.
The first part follows directly from lemma B.I. Hence, focus on proving the second part by contradiction.
If the DCSP has multiple solutions, there exists (æ, v) E (2 )/) such that two distinct concept sequences 21 and 22 are valid, i..., 21 A F y and 22 A KB + y.
Since both (ar) = 21 and [x) z2 are valid solutions for (ar, y), and 2 and 22 are distinct, follows that their true risks cannot be simultaneously zero. Thus, at least one of them must have
Ryv greater than zero. Without loss of generality, assume that Ron (fi)
0.
Since both fi and f2 achieve the minimal NeSy risk (which is zero), it is impossible to distinguish between them using learning techniques or by adding more data. Consequently, there is no integer N. such that for any 0 < c < co. Raa (f) < c holds when N 2 Ne. This implies that the task is unleamable.
Combining both parts completes the proof.
B.5 Proof of Theorem 3.7
Theorem 3.7. The average error Ex is bounded by:
d
3 S L
Proof. Recall that the DCSP solution disagreement d is given by = Union(S). where Union(S) represents the common assignments among the solutions. Since the restricted hypoth- esis space ensures that instances with same assigned label correspond to the same concept and vice versa. In the worst case, errors occur in at d classes, so the maximum true risk is max max (J) = d/L. Thus, the average error is bounded by: Ex S max Ryy (f)
d/L.
20

---

C Experiments
We first introduce the experimental details, including data preparation, model setup, optimizer con- figurations, hyperparameters, and implementation details. After that, we present experiments omit- ted from the main context due to space constraints.
C.1 Experiment Details
Arithmetic tasks The raw datasets are based on MNIST (LeCun el., 1994), KMNIST (Clanuwat al., 2018), CIFAR-I0 (Krizhevsky, 2009). and SVHN (Netzer et al., 2011). For MNIST-style datasets, the learning model is based on LeNet (LeCun & Bengio, 1998); other datasets use ResNet (He al., 2016).
The dataset are based on Xu al. (2020), all evaluated methods are using the same backbone, i.e., Conceptizer defined in rsbench (Bortolotti et al., 2024). For the abduction-based methods, we adopt their official implementations.
BDD-OIA
The results were obtained using an Intel Xeon Platinum 8538 CPU and an NVIDIA A100-PCIE- 40GB GPU on an Ubuntu 20.04 platform.
C.1.1 Preparing data and model
The construction of datasets is heavily based on algorithmic operations; thus, we rely on digit in- dices mapping from class indices to digit indices. After that, different knowledge bases require different rules. Here, we base our approach on ABLKit (Huang et al., 2024)' and the code of He et al. ( During the dataset construction process, we control the sample size by sampling data until the sequence size exceeds a threshold, denoted as sample sample_size _size. For figure 2, the sample_s e_size is set 30, 000, while for aggregation experiments is 120, 000; other values are specified in the respective plots. The reasoning model employs abductive reasoning, implemented using cache-based search program (Huang et al., 2024).
For an example of addition, the knowledge base is programmed as follows:
class KB (KBBase):
def logic_forward (self, nums):
numsi, nums2 split_lies (nums)
return digits_ to number (numsi) bigits_tt_nuubbee (nums2)
Figure 4: Example addition knowledge base with Python program form.
For the modular addition task, the knowledge base is more complex:
class Mod_KB (KBBase):
def logic_forvard (self, lsts):
numsl, nums2, mod parse_nums_ num__ums__aa and___ndd_ddeeeee mods (1sts)
numsi, nuns2 digits_ tetts_st__uubbee (numsi), tigits_to_number (
nums2)
return (numsi numa2) mod
Figure 5: Example of modular addition knowledge base with Python program form.
hstpe: h/ggts////ttttt wttp//bberrtieeeerrraaaaalaaaaaa
brtpo /ithbb..cc.... cww//lao-
21

---

Algorithm DCSP Solution
Require: NeSy task T and training set (( vi)
1: V,D, C + [Vi) {D; 2) 0
Initialize the CSP triple
2: for = 1......... N do
3: C U (V(z,) KB = ys}
Initialize the constraints
4: end for
5: S SOLVECSP(V,DDCC
Call the CSP solver
6: d I, Union(S)
7: return S,d
C.1.2 Implementation details
For all experiments, the random seeds are set to {2023, 2024, 2025, 2026, 2027] for repeating five times. To ensure the clustering property depicted in the definition of the restricted hypothesis space, the learning models are pre-trained. For LeNet5, we use self-supervised methods, with the weights available in the supplementary materials. For ResNet50, we load the pre-trained weights from the official PyTorch library, named ResNet50 ResNet50.Weights. IMAGENETIK v2, and replace the last linear layer with Linear ineer 10).
Optimizer Configurations. All experiments use AdamW, a weight-decay variant of Adam (Kingma & Ba, 2015), as the optimizer, with a learning rate of 0.0015 and betas set (0.9, 0.99). The batch size set to 256, and unless otherwise noted, the number of epochs is set to 10. The loss function used for optimization is cross-entropy, with further details available in the support code.
C.2 Additional Experiments
The additional experiments include setups using raw datasets not covered in the main text, specifi- cally the CIFAR-10 10 and SVHN cases. Additionally, beyond the empirical analysis on the surrogate (7), here we refer to this as ALLL (He et al., 2024b), we also include an analysis of ABL and PNL. to ensure comprehensive evaluation.
C.2.1 Observations of the structure of DCSP solution space
The configurations the modular addition task and their aggregations are illustrated in fig- ure 6. These configurations were computed using algorithm 1 with the open-source library Choco (Prud'homme & Fages, 2022). Through the investigation of the modular addition task, we observe that: the number of DCSP solutions is highly related to DCSP solution disagreement; how- ever, this relationship is not monotonic. Specifically, even a small number of DCSP solutions can result in high disagreement, observed in the modular addition task with base k 10.
10
1.00
5:50
06
80
000
0:80
0.00
0.00
0:00
10
6.00
0.00
04
0:40
0:40
0.00
0.00
0.40
1.00
0.00
5.00
0.00
00
Figure 6: Configurations of modular additions and their aggregations. The center value represents the ratio disagreement to concept size L, while the number of DCSP solutions is shown at the bettom-left.
22

---

Mod Aition
Mid Addtion Loo
Mal Niticon
Adliicn
Crocge Aee
Bewnniy Are
(a) CIFAR-10
Adtifce
Additin
Adtionta
Med Adttion
Mad Adttinn
37
12
127
17
Samgl
Samgle BL.0)
Songle
(b) SVHN
Figure 7: Accuracies versus sample size for different NeSy tasks of ALLL. The shadowed area denotes the standard error. The number of the DCSP solutions (#Sols) is shown at the top left of each plot. The asymptotic bound (green line) from theorem 3.7 indicates that concept accuracy should exceed this bound as the sample size grows.
C.2.2 Impact of DCSP solution disagreement
figure we present results under the same settings but using different raw datasets, specifically CIFAR- 10 and SVHN, as shown in figure 7. As illustrated in the figure, the learnable case follows trend similar to that in figure 1, However, in the unlearnable case, optimization becomes significantly more challenging due to high conflicts among valid DCSP solutions. While might suspect that this issue stems from the specific surrogate used, applying the same settings to ABL and PNL produces similar results (ef. figure 8 and figure respectively), confirming the generality of this observation.
23

---

Addtion
Mad A
MNIST
Aw
AAliinn
Songle
Stert
Crncpe
KMNIST
Sucrle Six vale
Sundk soll
Sanda Starhe rolk
Scpple Sca Scr
Anggl
All Coonugt
All
(c) CIFAR-10
Adlikn
AMd
Mal AiSiioldd
Sengle Sertkggcilo
Donte ABL Coergee Sec
(d) SVHN
Figure 8: Accuracies versus sample size for different NeSy tasks of ABL. The shadowed area de- notes the standard error. The number of the DCSP solutions (#Sols) is shown at the top left of each plot. The asymptotic bound (green line) from theorem 3.7 indicates that concept accuracy should exceed this bound as the sample size grows.
24

---

Adtiion
A
MNIST
A
Sungle
Crocpe
KMNIST
Suctpe Six vale
Sungk Siz solls
Sanda Sta
Scaple Siur malo
Scpll Scrikgiil
Angll
FAL Coonugh
WitL Reserein
(c) CIFAR-10
Ailikn
Add
Mal AiSicold
Sengle Strtiggeite
Craee PML Conrgee Sec
PAL Eauwiing
(d) SVHN
Figure 9: Accuracies versus sample size for different NeSy tasks of PNL. The shadowed area denotes the standard error. The number of the DCSP solutions (#Sols) is shown at the top left of each plot. The asymptotic bound (green line) from theorem 3.7 indicates that concept accuracy should exceed this bound as the sample size grows
25

---

C.2.3 Aggregation of unlearnable NeSy tasks
Here we present additional combinations of unlearnable NeSy tasks. In figure 10, we provide an overview of all aggregation combinations using heatmap. After that, we present more fine- grained analysis. In figure 1l and figure 12, we show cases where the aggregation approach fails and succeeds respectively.
Noo fane
10
36
16
2:9
cat
Madl Neoe
Mudl hone
Figure 10: Heatmaps aggregation mod addition tasks. Left: reasoning accuracy for different aggregations of mod bases; Right: concept accuracy for different aggregations of mod bases. The bottom-left corner of each cell shows the number of DCSP solutions.
By observing the experiments, we find that adopting the aggregation perspective can enrich the benchmark diversity in the NeSy field rsbench, Bortolotti et al. 2024), providing clear and controllable methodology to achieve this.
Moil Addiiinn #2
Mai Adlioo
Insemble22. 4)
Midl AAlii 2
Midl NaRia k
lisurbbe22.
64
Mol AlBik
Mal Adlioo
Essentle5.. 5
Aatiia k=
Mid Malii
Insemtied..9
Insembeess
Ansent Cuand Aoe
1pan
Ipes
Moi Addion
Mal Adllii
Adfiia
Adliio
Jasettg Ac:
Figure 11: aggregation of unlearnable NeSy tasks, failed case. The left shows confusion matrices and the right displays accuracy curves. After the aggregation, the tasks are still unlearnable.
26

---

Imose Ao Orand Aue
Epac
Moil Addiio #
Mai Alliic k 7
Insertlo6.7)
Mid Adliia k =
Mad MAflio 7
lnsembin0 71
Mol AmBink=
Mad Adliion
Enserttee 33
Madl Adliie
Mai Milio
Prokeed
Enenttes
UzammHaas, V)
Caeer Ave
Figure 12: aggregation of unlearnable NeSy tasks, successed case. The left shows confusion matri- and the right displays accuracy curves. After the aggregation, the tasks become learnable.
27

---

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:
As stated in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the section of limitation.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Ys]]
28

---

Justification:
All the proof' are included.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yss]
Justification: See the appendix.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
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?
29

---

Answer: [Yes]
Justification:
See the supplemental materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nipp cc/
oolicyllylyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.c.. cc/ wtt.ccccpppcccc.eeee wttpc/guudee//oeeeeeeeeeeeeeeeee
ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
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: [Ye]]
Justification:
See the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We include standard deviation color block in all figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
30

---

is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproducc the experiments?
Question:
Answer: [Yes]
Justification:
The computational requirements are included in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / /ttp///eerpp/.ee/ee//ee cc cc/ppbbicc/tthhccsuueeleee...ee.
Answer: [Yes]
Justification: Of course.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See impact statement.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
31

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
This is theoretical work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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: All code/datw/mode are included with their url.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
32

---

Answer:
[NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codd/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: This is theoretical work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it 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.
Question:
Answer: [NA]
33

---

Justification:
This research does not involve LLMs as any important, original, or non- standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standarr components.
Please refer to our LLM policy (https:/ /ttps////neuuuueeeeee httpps///errrps..c//Cfeeeeeeeee CCc/Conffrencces/22///11.. for what should or should be described.
34


Reviews:
[{"review_id": "iAhF4CobHz", "reviewer": "Reviewer_xjEQ", "summary": "The authors propose a well-structured and grounded theoretical analysis of the learnability of neuro-symbolic (NeSy) tasks. Such a theoretical analysis relies on mapping NeSy tasks into constraints satisfiability problems, showcasing that a task is learnable if and only if its corresponding DCSP admits a unique solution. This finding represents a very relevant result of this paper, which will probably become helpful for the NeSy community. Moreover, the authors provide a brief experimental evaluation to empirically back their theoretical findings, proving a solid paper. Overall, the paper is also relatively easy to read and follow, and its main limitations are linked to a shallow discussion of some relevant aspects, a somewhat limited experimental evaluation, and the missing source code to reproduce the experimental results. Therefore, the paper is of good quality while still requiring quite some polishing from a presentation and experimental perspective.", "questions": "- I know that the authors do not have enough space to provide detailed proof of the theorems and lemmas in the main body of the paper. However, the authors should also consider giving an intuition of the theorems' proofs in the main body of the paper to ease its understandability. For example, it would be great to have an intuition of why Theorem 2.1 holds true at the end of section 2.2. Could the authors elaborate on this point?\n- What is L in the definition of the DCSP solution disagreement d in Section 3.3? L does not seem to be used in the paper before the equation in which d is defined and is not described after.\n- Can the authors provide more details about the definition of the Union() operation in the solutions set? The authors mention that the Union captures the common assignments among the solutions. However, it is not completely clear what that means. Is it the way to identify solutions that map different concepts to the same label?\n- Can the authors provide more details on the feasibility of Assumption 3.4 in a real-world scenario? This assumption is presented very quickly and without much justification, thus making it complex for the reader to understand if it makes sense or not. I understand that this is a mild assumption, but I do not understand in which cases it does or does not hold. It seems that it should not hold only in the case of a continuous concept space; is this correct?\n- The authors skim through the results of Theorem 3.5 too quickly if considering the relevance of the provided Theorem. Could the authors provide a more in-depth discussion of the findings connected with Theorem 3.5? From my understanding, it seems that whenever the DCSP solution is not unique (i.e., d > 0), the NeSy task is not learnable, and thus, there will always be a concept risk greater than 0. This, in turn, would mean that reasoning shortcuts are unavoidable whenever the DCSP solution is not unique. Moreover, my understanding is that in general real-world scenarios DCSP solutions are not unique with a high probability. Thus, the findings suggest that in real-world scenarios, reasoning shortcuts and other issues related to concept risks are unavoidable. Is this correct?\n- From Table 1, it seems that the addition and multiplication tasks are perfectly learnable tasks. However, these tasks can still be affected by reasoning shortcuts. For example, whenever a model learns to swap the representation of the two digits being summed up, the addition or multiplication will result in the proper label but the wrong concepts. Therefore, it is not clear what the connection between learnability and reasoning shortcuts is. Could the authors clarify this distinction and discuss it more in-depth? I believe that this is an important aspect to clarify the contributions and impact of the paper better.\n- Why did the authors consider focusing only on digit summation and multiplication tasks? Several other NeSy tasks exist that are much more relevant to real-world scenarios. I would suggest the authors extend their experimental evaluation to other datasets and tasks.\nThe paper focuses only on probabilistic neuro-symbolic and abductive learning methods while not considering other available NeSy models, such as symbolic knowledge injection (SKI) models [1]. I would suggest the authors add a brief discussion about this, as well as some references to other NeSy models like SKI [2,3,4]. Could the authors add such a discussion?\n\n[1]. Ciatto, Giovanni, et al. \"Symbolic knowledge extraction and injection with sub-symbolic predictors: A systematic literature review.\" ACM Computing Surveys 56.6 (2024): 1-35.\n\n[2]. Agiollo, Andrea, et al. \"Symbolic knowledge injection meets intelligent agents: QoS metrics and experiments.\" Autonomous Agents and Multi-Agent Systems 37.2 (2023): 27.\n\n[3]. Von Rueden, Laura, et al. \"Informed machine learning–a taxonomy and survey of integrating prior knowledge into learning systems.\" IEEE Transactions on Knowledge and Data Engineering 35.1 (2021): 614-633.\n\n[4]. Magnini, Matteo, Giovanni Ciatto, and Andrea Omicini. \"On the design of PSyKI: a platform for symbolic knowledge injection into sub-symbolic predictors.\" International Workshop on Explainable, Transparent Autonomous Agents and Multi-Agent Systems. Cham: Springer International Publishing, 2022.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper tackles a relevant issue of NeSy models.\n- The paper showcases relevant and important findings about some NeSy models, which will probably become helpful for the NeSy community.\n- The theoretical analysis proposed seems solid and well-grounded.\n- The experimental evaluation backs the theoretical findings identified by the authors.\n\nWeaknesses:\n- A few aspects should be discussed more in detail.\n- Experimental evaluation could be made more extensive.\n- The paper focuses only on probabilistic neuro-symbolic and abductive learning methods while not considering other NeSy models, such as symbolic knowledge injection (SKI) models [1].\n- Missing source code.\n\n[1]. Ciatto, Giovanni, et al. \"Symbolic knowledge extraction and injection with sub-symbolic predictors: A systematic literature review.\" ACM Computing Surveys 56.6 (2024): 1-35.", "was_revised": true, "final_justification": "The rebuttal addressed all of the concerns and questions I had about the paper. The paper provides a very valuable contribution to the NeSy community presenting relevant theoretical findings that will be foundational for future developments.", "rebuttal": "Thank you for your constructive feedback. We address each point below:  \n\n---\n> W1. A few aspects should be discussed more in detail. \n\nWe will incorporate a detailed discussion of references [1-4] in the related work section (see W3).\n\n---\n> W2. Experimental evaluation could be made more extensive. \n\nThanks for the suggestion, we have extended our analysis to BDD-OIA [6], a real-world autonomous driving benchmark involving safety-critical decision making. This multi-label classification task uses 21 binary concepts (traffic lights, pedestrians, obstacles, etc.) with complex logical constraints such as safety rules (${\\tt red\\\\_light} \\lor {\\tt stop\\\\_sign} \\lor {\\tt obstacle} \\Rightarrow {\\tt stop}$), progression rules (${\\tt green\\\\_light} \\lor {\\tt follow} \\lor {\\tt clear} \\Rightarrow {\\tt forward}$), and consistency constraints (${\\tt stop} \\Rightarrow \\lnot {\\tt forward}$).\n\nBy DCSP analysis, we find that BDD-OIA has 74,240 possible solutions with disagreement $d=15$, confirming this as an unlearnable problem. Experimental validation using PNL (3 independent runs) confirms our theoretical predictions:\n\n| Split | Reasoning Accuracy | Concept Accuracy |\n| - | - | - |\n| Train | 0.824 (±0.003)     | 0.000 (±0.000)   |\n| Test  | 0.435 (±0.002)     | 0.000 (±0.000)   |\n\nThe zero concept accuracy demonstrates reasoning shortcuts exactly as our theory predicts for unlearnable tasks. This validates our framework's applicability to high-stakes, real-world scenarios beyond arithmetic domains. Comprehensive results and analysis will be included in the revised version.\n\n---\n> W3. The paper focuses only on probabilistic neuro-symbolic and abductive learning methods while not considering other NeSy models, such as symbolic knowledge injection (SKI) models [1]. \n\nWe thank the reviewer for raising this important point about symbolic knowledge injection (SKI) models. As noted in the taxonomy of [1], guided learning strategies (e.g., semantic loss [5]) are indeed relevant and applicable to our analysis framework. However, other SKI approaches, like structuring and embedding strategies, may require different analytical considerations. \n\nWe will expand the related work section in the revised version to provide a more comprehensive discussion of these relevant aspects.\n\n---\n> W4. Missing source code. \n\nComplete source code was included in the supplementary materials.\n\n---\n> Q1. [...] it would be great to have an intuition of why Theorem 2.1 holds true at the end of section 2.2. Could the authors elaborate on this point?\n\nThanks for this suggestion. We will add more intuitive explanations of Theorems 2.1, 3.5, and 3.6 in the revised version.\n\n**Theorem 2.1 intuition:** PNL performs weighted model counting (WMC) over concept assignments satisfying symbolic constraints. Minimizing this weighted count finds the concept predictor that maximizes probability mass on valid concept-label combinations, which is equivalent to minimizing NeSy risk. ABL performs abductive reasoning to select the most plausible concept-label combinations. When the model achieves zero ABL risk, it simultaneously minimizes the NeSy risk.\n\n---\n> Q2. What is L in the definition of the DCSP solution disagreement d in Section 3.3? [...]\n\n$L$ is defined in line 60 as the size of the concept space $\\mathcal{Z}$. We will clarify this notation more clearly in the revised version.\n\n---\n> Q3.  Can the authors provide more details about the definition of the Union() operation [...]\n\nThe `Union` operator aggregates assignments across all solutions. For each concept $i$ (where $i$ ranges from $0$ to $L - 1$), it collects the set of labels assigned to concept $i$ by all solutions. If a concept receives the same label assignment in every solution, it is excluded from the union. The following Python-style pseudocode illustrates this process:\n```py\n# Initialize dictionary to store label sets for each concept\nunion_sols = defaultdict(set)\n\n# Collect all label assignments for each concept across solutions\nfor solution in Solutions:\n    for i in range(L):\n        union_sols[i].add(solution[i])\n\n# Remove concepts that have the same label in all solutions\nfor i in list(union_sols):\n    if len(union_sols[i]) == 1:\n        del union_sols[i]  # Remove concepts with unique assignments\n```\n---\n> Q4.  Can the authors provide more details on the feasibility of Assumption 3.4 in a real-world scenario? [...]\n\nAssumption 3.4 (finite concept space with non-zero measure) is widely applicable in practice. It holds for most common scenarios including image classification, NLP tasks, and structured prediction where concepts represent discrete categories or finite domains. While it may not apply to continuous concept spaces, to the best of our knowledge, such cases are rare in neuro-symbolic learning.\n\n---\n> Q5.  [...] Could the authors provide a more in-depth discussion of the findings connected with Theorem 3.5? [...]\n\nYes. Theorem 3.5 establishes that when the DCSP solution is not unique ($d > 0$), the NeSy task becomes unlearnable with unavoidable nonzero concept risk. This directly explains the emergence of reasoning shortcuts: ambiguity in the solution space allows models to find alternative concept-label mappings that achieve low empirical risk while making systematic concept errors.\n\nThe disagreement measure $d$ serves as a quantitative indicator of task difficulty—higher disagreement implies greater ambiguity and increased susceptibility to reasoning shortcuts. Our framework also suggests a practical solution: combining multiple unlearnable tasks in a multi-task setting can reduce overall ambiguity. When the intersection of their DCSP solution spaces yields a unique solution, the combined task becomes learnable, potentially eliminating reasoning shortcuts (cf. sections 3.5 and 4.2). For a detailed discussion of task combination strategies, please refer to the response to C3 of Reviewer `1naA`.\n\n---\n> Q6. [...] For example, whenever a model learns to swap the representation of the two digits being summed up, the addition or multiplication will result in the proper label but the wrong concepts. Therefore, it is not clear what the connection between learnability and reasoning shortcuts is. Could the authors clarify this distinction and discuss it more in-depth? [...]\n\nThank you for this important question. We first clarify that: \n\n*the reasoning shortcut [6] is defined on the entire dataset rather than individual samples*.\n\nThis means that addition and multiplication tasks have no reasoning shortcuts. While swapping digits `1` and `2` might work for some samples (e.g., `1+2=3` becomes `2+1=3`, which remains valid for addition), it fails systematically across the dataset. For example, the sample `1+0=1` would become `2+0=1` (incorrect), the sample `2+0=2` would become `1+0=2` (incorrect), and so on.\n\n**Connection to learnability:** Reasoning shortcuts occur when a model achieves correct reasoning outputs despite making concept errors. This phenomenon happens because the task is unlearnable. \n\n---\n> Q7. Why did the authors consider focusing only on digit summation and multiplication tasks? [...] I would suggest the authors add a brief discussion about this, as well as some references to other NeSy models like SKI [2,3,4]. Could the authors add such a discussion?\n\nFor the experimental concerns please refer to W2.\n\nRegarding SKI models, we thank the reviewer for this important point. As noted in [1], guided learning strategies (e.g., semantic loss [5]) are relevant to our framework, while other SKI approaches may require different analytical considerations. We will expand the related work section to discuss these connections more comprehensively in the revised version.\n\n---\n**Revision Summary**\n\nGiven our response above, we will make the following key revisions:\n\n**1. Expand Experiments and Discussion (W1, W2, W3, Q7)**\n- Add BDD-OIA real-world experimental validation\n- Add discussion of other NeSy approaches, especially SKI models [1-4]\n\n**2. Improve Clarity and Intuitions (Q1, Q2, Q3)**\n- Provide intuitive explanations for Theorems 2.1, 3.5, and 3.6 in main text\n- Clarify the notation of $L$\n- Provide algorithmic description of `Union()` operation in appendix\n\n**3. Deepen Conceptual Analysis (Q4, Q5, Q6)**\n- Expand discussion on Assumption 3.4 for justification\n- Explain implications of theorem 3.5 and potential practical approach to mitigate unlearnable tasks\n- Add justification on the understanding of \"reasoning shortcut\" and its relationship to learnability in the related work section\n\n--- \nWe hope our responses have addressed your concerns.\nIf you have any further questions, please do not hesitate to ask. \n\n---\n\n### References\n\n[1] Ciatto et al. \"Symbolic knowledge extraction and injection with sub-symbolic predictors: A systematic literature review.\" ACM Computing Surveys, 2024.\n\n[2] Agiollo et al. \"Symbolic knowledge injection meets intelligent agents: QoS metrics and experiments.\" AAMAS, 2023.\n\n[3] Von Rueden et al. \"Informed machine learning–a taxonomy and survey of integrating prior knowledge into learning systems.\" IEEE TKDE, 2021.\n\n[4] Magnini et al. \"On the design of PSyKI: a platform for symbolic knowledge injection into sub-symbolic predictors.\" EXTRAAMAS, 2022.\n\n[5] Xu et al. \"A Semantic Loss Function for Deep Learning with Symbolic Knowledge.\" ICML, 2018.\n\n[6] Marconato et al. \"Not all neuro-symbolic concepts are created equal: Analysis and mitigation of reasoning shortcuts.\" NeurIPS, 2023.\n\n[7] Yang et al. \"Analysis for abductive learning and neural-symbolic reasoning shortcuts.\" ICML, 2024.\n\n[8] Bortolotti et al. \"A neuro-symbolic benchmark suite for concept quality and reasoning shortcuts.\" NeurIPS, 2024. \n\n[9] He et al. \"Ambiguity-aware abductive learning.\" ICML, 2024."}, {"review_id": "MgXKeLxmJ6", "reviewer": "Reviewer_gMsj", "summary": "The authors propose a theoretical framework to characterise the \nlearnability within hybrid NeSy systems with respect to the \nsample complexity asymptotically bounding the concept error.  \n\nThe theoretical analysis considers the derived constraint \nsatisfaction problem (DCSP) for a NeSy learning task and \nproposes as an indicator of its ambiguity *solution disagreement*, \nmeasuring the degree of disagreement among DCSP solutions\n\nThe main results of the paper are Theorem 3.5 and 3.6 showing \nrespectively that a task is learnable iff the associated DCSP has \na unique solution, and the asymptotic expected concept error is \ncontrolled by solution disagreement", "questions": "See the Strengths and Weaknesses section.", "limitations": "The paper clearly discusses the limitations of the framework,\nnamely the exclusive focus on hybrid NeSy models and the \nrestricted hypothesis space. Among the two the latter is \nargubly the one limiting the most the applicability of the \nframework proposed.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Soundness\nThe paper is technically sound, the main results precisely fromulated\nand the proofs presented with the appropriate rigor. The experimental\nsection is correctly focused on assessing the content of the main \ntheoretical results.  \n\n# Presentation\nThe article is well-written and its presentation is satisfactory.\nThe content of Sections 3.5 and 4 could benefit from further additions\n(please refer to 'Other Comments') \n\n# Contribution\nThe main contribution of the article is the DCSP framework allowing \nto define learnable and unlearnable NeSy tasks and bounding the \nexpected concept risk of an arbitrary hypothesis. The experimental\nevaluation briefly validates the findings.\n\n# Strengths\nThe DCSP framework addresses a relevant problem, it is quite \nstraighforward in its construction and application and succeeds \nin giving a detailed perspective for concept error analysis.\nIt is applicable both for Probabilistic Neuro-Symbolic and \nAbductive Learning. The analysis considers ERM algorithm that \nis in line with a large part of the literature on this topic.\nLastly, the perspective of DCSPs combination for unlearnable \ntasks gives interesting insights. \n\n# Weaknesses \nThe main issues lie in the assumptions this work is making.\nFirst, the *restricted hypothesis space* assumption. \nSecond, some other assumptions limiting the applicability of \nthe framework are implicit. In particular, Assumption 3.4. \nentails that all the possible combinations of concepts yielding\nsome final label y must have non-zero probability of occurring.\nHowever, in many cases the support of the data is not full\n(e.g. in MNIST-EvenOdd for y = 9 the concept combination \n<3,6> never occurs as only pairs of odd/even digits are observed).\nPlease also see the 'Other Comments' Section of the review.\n\n\n# Other Comments\nPlease consider the additional comments below.\n\nThe article would benefit from an extention of Section 3.5.,\nfor example the authors could give further insights on the \n*conditions* that are generally required in order for the \ncombination of unlearnable tasks to become learnable.\n\nIn Definition 3.1., $\\mathcal{A}$ should be expressively \nlinked to the learned hypothesis $\\hat{f}$ \n(e.g., $\\mathcal{A} = \\hat{f}$).\n\nProposition 3.2. should be more clear, as defining the hypothesis space\nas *sufficiently complex* is not formal enough. I suggest making the \nshattering property explicit in the statement and not in brackets.\nHere the authors could consider to insert an inline definition for \nshattering right before the Proposition and explain shortly it is\nrelated to the complexity of the space.\n \nThe experimental evaluation is restricted to cases where the \nbackground knowledge are simple mathematical operations. \nIt would be interesting to see some examples with other types\nof (more complex) constraints.  \n\n# Overall Evaluation\nThe theoretical framework proposed by the article is relevant \nand sound. The Presentation is clear and the contributions \nallow to characterise prominent learnability problems.\nHowever the assumptions are quite limiting and the experimental\nevaluation could be extended with at least another more complex\ncase. In its current state I consider this article to be \nmarginally below the acceptance threshold.", "was_revised": true, "final_justification": "The paper is sound and can be of interest for a sub-community of NeurIPS.", "rebuttal": "Thank you for your insightful comments. We address each point below:\n\n---\n> W1. The main issues lie in the assumptions this work is making. First, the restricted hypothesis space assumption.\n\nThank you for raising this important point. We appreciate your concern about the restricted hypothesis space assumption.\n\nOur assumption is actually well-supported by recent findings in deep learning. The Neural Collapse phenomenon [5] shows that deep neural networks naturally form simplex structures in their final layers, which aligns perfectly with our approach. Additionally, modern techniques like pre-training and self-supervised learning help satisfy this assumption in practice.\n\nWe agree that extending to more general hypothesis spaces would be valuable, and we plan to explore this direction in future work.\n\n---\n> W2. Second, some other assumptions limiting the applicability of the framework are implicit. In particular, Assumption 3.4. entails that all the possible combinations of concepts yielding some final label y must have non-zero probability of occurring. However, in many cases the support of the data is not full (e.g. in MNIST-EvenOdd for y = 9 the concept combination <3,6> never occurs as only pairs of odd/even digits are observed).\n\nThanks for question, we would like to clarify this concern on Assumption 3.4. \nFor clarity, we restate the assumption: \n\n*The set of possible concept sequences, $\\mathcal{B} = \\bigcup_{y\\in \\mathcal{Y}} A(y)$ has finite cardinality; and the probability of sampling a concept sequence is at least $\\kappa > 0$.*\n\nWe emphasize that this assumption applies specifically to valid concept combinations, not arbitrary ones. Our assumption is grounded in the definition of notation $A$ (lines 110-112): \"[...] set $A(y)$ includes all possible concepts $\\boldsymbol{z}$ that satisfy the constraints of $\\mathtt{KB}$ and have a non-zero measure [...]\" \nTherefore, our analysis only considers concept combinations that are both consistent with the knowledge base constraints and within the support of the data distribution. \n\nThe MNIST-EvenOdd example mentioned (where <3,6> never occurs) would not be included in $A(y)$ as it violates the task constraints. We will revise the assumption statement in the paper to make this distinction more explicit as: \n\n**Revised assumption 3.4** The set of possible concept sequences, $\\mathcal{B} = \\bigcup_{y\\in \\mathcal{Y}} A(y)$, where $A(y)$ is the set of possible concept combinations for label $y$, has finite cardinality; and the probability of sampling a concept sequence is at least $\\kappa > 0$.\n\n\n---\n> C1. The article would benefit from an extention of Section 3.5., for example the authors could give further insights on the conditions that are generally required in order for the combination of unlearnable tasks to become learnable.\n\nThank you for this valuable suggestion. We will expand Section 3.5 to provide deeper insights into the conditions under which combining unlearnable tasks yields learnable aggregated tasks. \n\nConsider two unlearnable NeSy tasks $\\mathcal{T}_1 = \\langle \\mathcal{X}_1, \\mathcal{Y}_1, \\mathtt{KB}_1 \\rangle$ and $\\mathcal{T}_2 = \\langle \\mathcal{X}_2, \\mathcal{Y}_2, \\mathtt{KB}_2 \\rangle$ with DCSP solution sets $\\mathcal{S}_1$ and $\\mathcal{S}_2$. The aggregated task requires satisfying constraints from both tasks simultaneously, resulting in solution set $\\mathcal{S}\\_{agg} = \\mathcal{S}_1 \\oplus \\mathcal{S}_2$. For the aggregated task to achieve learnability benefits, two necessary conditions must hold:\n- (1) Concept space overlap: $\\mathcal{Z}_1 \\cap \\mathcal{Z}_2 \\neq \\varnothing$. \n- (2) Reduced DCSP disagreement: $d\\_{agg} = |\\mathcal{Z}_1 \\cup \\mathcal{Z}_2| - |\\textrm{Union}(\\mathcal{S}\\_{agg})| < \\min(d_1, d_2)$.\n\nThe fundamental result is that an aggregated task becomes learnable if and only if $|\\mathcal{S}\\_{agg}| = 1$. By Theorem 3.5, this occurs when the DCSP solution disagreement $d\\_{agg} = 0$. The aggregation reduces disagreement according to $d\\_{agg} = |\\mathcal{Z}_1 \\cup \\mathcal{Z}_2| - |\\textrm{Union}(\\mathcal{S}_1 \\oplus \\mathcal{S}_2)| < \\min(d_1, d_2)$, where the reduction is maximized when tasks exhibit complementary ambiguity patterns on shared concepts. \n\nTo illustrate this mechanism, consider the following example:\n\n```\n# Task 1 solution space (gt concept : possible concept assignment):\nS1 = {0:{0}, 1:{1}, 2:{2,3}, 3:{3,2}, 4:{4}, 5:{5}, 6:{6}, 7:{7}}\n\n# Task 2 solution space (gt concept : possible concept assignment):\nS2 = {0:{0,1}, 1:{1,0}, 2:{2}, 3:{3}, 4:{4,5}, 5:{5,4}}\n\n# Aggregated solution space after intersection:\nS_agg = {0:{0}, 1:{1}, 2:{2}, 3:{3}, 4:{4}, 5:{5}, 6:{6}, 7:{7}}\n```\n\nIn this example, concepts 2 and 3 are ambiguous in Task 1, while concepts 0, 1, 4, and 5 are ambiguous in Task 2. The aggregation resolves all ambiguities, yielding a unique solution mapping that enables learnability. \n\nThis analysis provides a principled framework for multi-task design in NeSy systems, enabling us being able to strategically combine tasks to achieve learnability even when individual tasks are unlearnable. \n\n---\n> C2. In Definition 3.1., $\\cal A$ should be expressively linked to the learned hypothesis $\\hat{f}$ (e.g., $\\mathcal{A} = \\hat{f}$). \n\nThanks for suggestion, we will revise the definition to emphasis that $\\hat{f} = \\mathcal{A}(D)$, to denote the learned hypothesis is given by algorithm $\\mathcal{A}$ on dataset $D$.\n\n---\n> C3. Proposition 3.2. should be more clear, as defining the hypothesis space as sufficiently complex is not formal enough. I suggest making the shattering property explicit in the statement and not in brackets. Here the authors could consider to insert an inline definition for shattering right before the Proposition and explain shortly it is related to the complexity of the space. \n\nThanks for the suggestion. We will improve the proposition to make it more clear in the revised version of the paper. Specifically, we will add a formal definition of shattering and revise Proposition 3.2 as follows:\n\n**Definition (Shatter).** A hypothesis space $\\mathcal{F}$ *shatters* a set $X = \\\\{x_1, x_2, \\ldots, x_m\\\\}$ with respect to a label space $\\mathcal{Z}$ if for every possible labeling function $\\ell: X \\to \\mathcal{Z}$, there exists a hypothesis $f \\in \\mathcal{F}$ such that $f(x_i) = \\ell(x_i)$ for all $s_i \\in S$. \n\nThe shattering property captures the expressive power of a hypothesis space—the ability to realize any possible multi-class labeling of a given set of instances.\n\n**Revised Proposition 3.2.** For an ambiguous NeSy task $\\mathcal{T} = \\langle \\mathcal{X}, \\mathcal{Y}, \\mathtt{KB} \\rangle$, if the hypothesis space $\\mathcal{F}$ can shatter the input space, then there exists $f^* \\in \\mathcal{F}$ that minimizes $\\mathcal{R}\\_{\\text{NeSy}}(f)$ but not $\\mathcal{R}\\_{\\text{0/1}}(f)$.\n\n---\n> C4. The experimental evaluation is restricted to cases where the background knowledge are simple mathematical operations. It would be interesting to see some examples with other types of (more complex) constraints.\n\nThanks for the suggestion. To address this concern, we have extended our analysis to BDD-OIA [3], a real-world autonomous driving benchmark involving safety-critical decision making. This multi-label classification task uses 21 binary concepts (traffic lights, pedestrians, obstacles, etc.) with complex logical constraints such as safety rules (${\\tt red\\\\_light} \\lor {\\tt stop\\\\_sign} \\lor {\\tt obstacle} \\Rightarrow {\\tt stop}$), progression rules (${\\tt green\\\\_light} \\lor {\\tt follow} \\lor {\\tt clear} \\Rightarrow {\\tt forward}$), and consistency constraints (${\\tt stop} \\Rightarrow \\lnot {\\tt forward}$).\n\nBy DCSP analysis, we find that BDD-OIA has 74,240 possible solutions with disagreement $d=15$, confirming this as an unlearnable problem. Experimental validation using PNL (3 independent runs) confirms our theoretical predictions:\n\n| Split | Reasoning Accuracy | Concept Accuracy |\n| ----- | ------------------ | ---------------- |\n| Train | 0.824 (±0.003)     | 0.000 (±0.000)   |\n| Test  | 0.435 (±0.002)     | 0.000 (±0.000)   |\n\nThe zero concept accuracy demonstrates reasoning shortcuts exactly as our theory predicts for unlearnable tasks. This validates our framework's applicability to high-stakes, real-world scenarios beyond arithmetic domains. Comprehensive results and analysis will be included in the revised version.\n\n--- \n\n**Revision Summary**\n\nGiven our response above, we will make the following key revisions:\n\n**1. Clarify Theoretical Definitions and Assumptions (W1, W2, C2, C3)** \n- Clarify restricted hypothesis space and Assumption 3.4 more clearly\n- Revise Definition 3.1 to explicitly state $\\hat{f} = \\mathcal{A}(D)$\n- Add formal shattering definition before Proposition 3.2\n\n**2. Add Experimental Validation on Real-World Scenarios (C4)**\n- Add BDD-OIA, a real-world experimental validation\n\n**3. Expand Task Aggregation Analysis (C1)**\n- Expand Section 3.5 with deepper insights and examples\n\n---\nWe hope our responses have addressed your concerns and would appreciate your consideration for a score raise.\nIf you have any further questions, please do not hesitate to ask. \n\n---\n**References** \n\n[1] Yang et al. \"Analysis for abductive learning and neural-symbolic reasoning shortcuts.\" ICML, 2024.\n\n[2] Bortolotti et al. \"A neuro-symbolic benchmark suite for concept quality and reasoning shortcuts.\" NeurIPS, 2024. \n\n[3] Marconato et al. \"Not all neuro-symbolic concepts are created equal: Analysis and mitigation of reasoning shortcuts.\" NeurIPS, 2023. \n\n[4] He et al. \"Ambiguity-aware abductive learning.\" ICML, 2024.\n\n[5] Súkeník et al. \"Deep Neural Collapse Is Provably Optimal for the Deep Unconstrained Features Model.\" NeurIPS, 2023."}, {"review_id": "b56aAHuNyT", "reviewer": "Reviewer_1naA", "summary": "This paper provides a formal theoretical analysis of the learnability of neuro-symbolic (NeSy) tasks, particularly within hybrid systems combining neural learning and symbolic reasoning. It introduces the concept of mapping a NeSy task to a Derived Constraint Satisfaction Problem (DCSP) and shows that a NeSy task is learnable if and only if the associated DCSP admits a unique solution (i.e., zero solution disagreement). The authors derive sample complexity bounds, an asymptotic error bound related to solution disagreement, and discuss how unlearnable tasks may become learnable through aggregation. Empirical results using tasks like addition and modular addition support the theoretical claims.", "questions": "- Your framework requires formulating the DCSP and computing its solution set and the disagreement measure $d$ (Definition 3.3). For realistic neuro-symbolic tasks with large or continuous concept spaces, how tractable is it to exactly compute or approximate all DCSP solutions? If exact enumeration is infeasible, what approximate methods or heuristics would you recommend to estimate disagreement in practice?\n\n- Your Corollary 3.7 proposes that aggregating multiple unlearnable tasks can reduce solution disagreement and yield learnability. s there an algorithmic selection method, or must this be done manually via domain knowledge?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Novel Theoretical Framework: The use of DCSPs as a lens for understanding learnability is novel, precise, and potentially impactful for both theory and practice in NeSy.\n- Connection to Reasoning Shortcuts: It links its theoretical results to practical phenomena like reasoning shortcuts, which is a major known challenge in NeSy.\n- Empirical Validation The experiments demonstrate how solution disagreement affects learnability in practice, providing convincing evidence for the theory.\n\nWeaknesses:\n- Experiments: While the experiments are relevant, they are mostly based on toy tasks (digit operations) and do not yet extend to more realistic or open-ended NeSy benchmarks.\n- Scalability Concerns: For large-scale tasks or richer symbolic domains, solving DCSPs can be intractable.", "was_revised": true, "final_justification": "The authors responses and clarifications, both to myself and to the other reviewers, have satisfactorily addressed the concerns and questions I had regarding the paper.  Therefore, I lean towards acceptance.", "rebuttal": "Thank you for your insightful comments. We address each point below:\n\n---\n> W1. Experiments: While the experiments are relevant, they are mostly based on toy tasks (digit operations) and do not yet extend to more realistic or open-ended NeSy benchmarks. \n\nThanks for your valuable question. We respectfully disagree that our experimental setup is limited to toy tasks. Our choice of arithmetic domains is methodologically sound for several reasons. First, arithmetic tasks provide a controlled setting where ground truth concept-reasoning relationships are precisely known, enabling rigorous validation of our theoretical predictions without confounding factors. Second, leading NeSy works extensively use arithmetic domains for validation (e.g., [1-4]), making our results directly provide insights into existing literature.\n\nMeanwhile, we acknowledge that extend our experiments should be helpful. To further address this concern, we have extended our analysis to BDD-OIA[3], a real-world autonomous driving benchmark involving safety-critical decision making. This multi-label classification task uses 21 binary concepts (traffic lights, pedestrians, obstacles, etc.) with complex logical constraints such as safety rules (${\\tt red\\\\_light} \\lor {\\tt stop\\\\_sign} \\lor {\\tt obstacle} \\Rightarrow {\\tt stop}$), progression rules (${\\tt green\\\\_light} \\lor {\\tt follow} \\lor {\\tt clear} \\Rightarrow {\\tt forward}$), and consistency constraints (${\\tt stop} \\Rightarrow \\lnot {\\tt forward}$).\n\nBy DCSP analysis, we find that BDD-OIA has 74,240 possible solutions with disagreement $d=15$, confirming this as an unlearnable problem. Experimental validation using PNL (3 independent runs) confirms our theoretical predictions:\n\n| Split | Reasoning Accuracy | Concept Accuracy |\n| ----- | ------------------ | ---------------- |\n| Train | 0.824 (±0.003)     | 0.000 (±0.000)   |\n| Test  | 0.435 (±0.002)     | 0.000 (±0.000)   |\n\nThe zero concept accuracy demonstrates reasoning shortcuts exactly as our theory predicts for unlearnable tasks. This validates our framework's applicability to high-stakes, real-world scenarios beyond arithmetic domains. Comprehensive results and analysis will be included in the revised version.\n\n---\n> W2. Scalability Concerns: For large-scale tasks or richer symbolic domains, solving DCSPs can be intractable.\n\nWe answer this concern with Q1 together.\n\n> Q1. Your framework requires formulating the DCSP and computing its solution set and the disagreement measure $d$ (Definition 3.3). For realistic neuro-symbolic tasks with large or continuous concept spaces, how tractable is it to exactly compute or approximate all DCSP solutions? If exact enumeration is infeasible, what approximate methods or heuristics would you recommend to estimate disagreement in practice?\n\nWe note that there are several practical approaches that can be used to address this limitation:\n\n**Decomposition**: \n- Break complex tasks into simpler sub-tasks with tractable CSPs [7,8]\n\n**Approximation methods**:\n- *Relaxation and optimization*: Relax constraints to continuous values and use optimization techniques [5]\n- *Sampling-based estimation*: Randomly sample concept assignments to estimate solution spaces [6]\n\n**Practical heuristics**:\n- *Symmetry exploitation*: Utilize constraint symmetries (e.g., in Sudoku) to simplify problems\n- *Uniform sampling*: Use hash-based techniques [9] for solution space estimation\n- *Early stopping*: Terminate when disagreement $d$ is approaches a certain threshold.\n\nThanks for valuable question, we will add such discussion as future directions in the revised version of this paper.\n\n---\n> Q2. Your Corollary 3.7 proposes that aggregating multiple unlearnable tasks can reduce solution disagreement and yield learnability. Is there an algorithmic selection method, or must this be done manually via domain knowledge?\n\nYes, there are algorithmic methods for systematic task selection. Once NeSy tasks are formulated as DCSPs, we can automatically identify combinations that yield learnability.\n\n**Theoretical Foundation:**\nConsider two unlearnable NeSy tasks $\\mathcal{T}_1 = \\langle \\mathcal{X}_1, \\mathcal{Y}_1, \\mathtt{KB}_1 \\rangle$ and $\\mathcal{T}_2 = \\langle \\mathcal{X}_2, \\mathcal{Y}_2, \\mathtt{KB}_2 \\rangle$ with DCSP solution sets $\\mathcal{S}_1$ and $\\mathcal{S}_2$ where $|\\mathcal{S}\\_1| \\geq 2$ and $|\\mathcal{S}\\_2| \\geq 2$. The aggregated task requires satisfying constraints from both tasks simultaneously, resulting in solution set $\\mathcal{S}\\_{agg} = \\mathcal{S}_1 \\oplus \\mathcal{S}_2$. For the aggregated task to achieve learnability benefits, two necessary conditions must hold:\n  - (1) Concept space overlap: $\\mathcal{Z}_1 \\cap \\mathcal{Z}_2 \\neq \\varnothing$. \n  - (2) Reduced DCSP disagreement: $d\\_{agg} = |\\mathcal{Z}_1 \\cup \\mathcal{Z}_2| - |\\textrm{Union}(\\mathcal{S}\\_{agg})| < \\min(d_1, d_2)$.\n\n**Algorithmic Selection:**\nA simple algorithm can systematically find learnable combinations among a list of unlearnable tasks:\n\n```python\ndef find_learnable_combinations(tasks: List[CSP]):\n    \"\"\"Find task combinations that yield unique DCSP solutions\"\"\"\n    for combined_task in combinations(tasks):\n        solutions = solve(combined_task)\n        if len(solutions) == 1:  # Unique solution → learnable\n            yield combined_task\n```\n\nThis demonstrates the effectiveness of our DCSP framework in enabling principled multi-task design for NeSy systems.\n\n\n---\n**Revision Summary**\n\nGiven our response above, we will make the following key revisions:\n\n**1. Extended Experiments (W1)**\n- Add a more realistic BDD-OIA benchmark to experiments section.\n\n**2. Discuss Scalability and Practical Implementation (W2, Q1)**\n- Discuss potential approximation methods and practical heuristics for large-scale applications in future direction section.\n\n**3. Formalize Task Aggregation Methods (Q2)**\n- Add algorithmic approach for task combination selection to Section 3.5\n\n--- \nWe hope our responses have addressed your concerns.\nIf you have any further questions, please do not hesitate to ask. \n\n---\n**References** \n\n[1] Yang et al. \"Analysis for abductive learning and neural-symbolic reasoning shortcuts.\" ICML, 2024.\n\n[2] Bortolotti et al. \"A neuro-symbolic benchmark suite for concept quality and reasoning shortcuts.\" NeurIPS, 2024. \n\n[3] Marconato et al. \"Not all neuro-symbolic concepts are created equal: Analysis and mitigation of reasoning shortcuts.\" NeurIPS, 2023. \n\n[4] He et al. \"Ambiguity-aware abductive learning.\" ICML, 2024. \n\n[5] Bhangale et al. \"Approximation Algorithms for Satisfiable CSPs via a Mixed Invariance Principle\", STOC, 2025. \n\n[6] He et al. \"Sampling Lovász Local Lemma for General Constraint Satisfaction Solutions in Near-Linear Time\", FOCS 2022. \n\n[7] Gottlob et al. \"Fast and parallel decomposition of constraint satisfaction problems\", Constraints (27), 284–326, 2022.\n\n[8] Hu et al. \"Curriculum Abductive Learning\", Arxiv 2505.12275, 2025.\n\n[9] Golia et al. \"Designing Samplers is Easy: The Boon of Testers\", FMCAD, 2021."}, {"review_id": "K3raElGlFq", "reviewer": "Reviewer_vQUA", "summary": "The paper provides a theoretical analysis of learnability in neurosymbolic AI, specifically of the well-known concept of distant supervision. The authors do this by modelling the task as a constraint satisfaction problem (CSP). They define the conditions for learnability in terms of this CSP and provide theoretical error bounds. They link this learnability to the well-established problem of reasoning shortcuts.", "questions": "- In [1], the authors provide an algorithm for counting the number of reasoning shortcuts. They also use something similar to constraint solving (WMC). Is this not similar to the derived CSP you introduce? Can you elaborate on the difference?\n- Line 45: You link your analysis with deterministic reasoning shortcuts. Is there also a link with probabilistic reasoning shortcuts (as defined by [2])?\n- Equation 4: Shouldn’t there be a logarithm in front of p, like in Equation 5?\n- Lines 141-145 of the related work are not really clear to me. What does “full knowledge of the underlying concept sequence distribution” mean exactly?\t\n- Line 178-184 and 191-194: This is not clear to me. Does the hypothesis space F refer to (1) the logic rules to compute the task from the concepts, or (2) the neural networks mapping input to concepts, or (3) both? To me, it seems either (1) or (3) is the case due to Proposition 3.2, but then lines 191-194 and the equation below line 194 point to (2). If (1), then why do these lines refer to for instance neural networks? If (2) or (3), then why does f map input to concepts in the equation below line 194? \n- As a consequence of the above point, I’m not sure what the “restricted hypothesis space” exactly refers to (as I’m not sure what the “hypothesis space” exactly refers to).\n- Line 202: Is there a reason why the different variables V_i have the same domain Z?\n- Lines 265-270: I would work this example more out. I don’t immediately see why, when k=8, there are 4 solutions and d/L=0.4. What are the exact values for d and L, and maybe you can briefly give some examples of solutions.\n- In Figure 3, can you give some intuition on why the reasoning accuracy is bad for the aggregation?\n- What is the setup for the CIFAR-10 and SVHN datasets (Appendix line 756)?\n- Can you elaborate on what you state in lines 769-770: “optimization becomes significantly more challenging due to high conflicts among valid DCSP solutions”. Why is reasoning accuracy so low when there are shortcuts (e.g. Figure 9 for k=2)?\n\nI would be happy to increase my score if the above remarks are clarified.\n\n[1] A Neuro-Symbolic Benchmark Suite for Concept Quality and Reasoning Shortcuts. Bortolotti et al.\n\n[2] Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts. Marconato et al.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "- Strengths\n    - The paper is generally well-written and should be well-understandable by members of the community.\n    - The paper provides formal theoretical bounds on the concept error.\n    - The paper contains experiments on multiple datasets that provide empirical evidence for the theory.\n- Weaknesses\n    - Some parts of the text are not clear to me (see questions below).\n    - The experiments in the main text are all MNIST-based. While the appendices seem to have experiments on other datasets, I don’t find any information about their setup (somehow they seem to use the same “knowledge” as in MNIST, but I don’t understand how).\n    - Some figures are very hard to read due to the small font (e.g. Figures 1, 2, 3).", "was_revised": true, "final_justification": "All issues were resolved. I believe the paper is interesting and merits acceptance.", "rebuttal": "Thank you for your insightful comments and thorough review. We address each point below:\n\n---\n> W1. The experiments in the main text are all MNIST-based. While the appendices seem to have experiments on other datasets, I don't find any information about their setup (somehow they seem to use the same \"knowledge\" as in MNIST, but I don't understand how). \n\nFor CIFAR-10 and SVHN, we map class indices to digits (0-9) to create arithmetic tasks analogous to MNIST. For example, CIFAR-10 classes (airplane=0, automobile=1, ..., truck=9) are treated as digit concepts for addition/multiplication tasks. This enables evaluation across different visual domains while maintaining identical logical structure.\n\n---\n> W2. Some figures are very hard to read due to the small font (e.g. Figures 1, 2, 3).\n\nWe will increase font sizes and improve figure readability in the revised version.\n\n---\n> Q1. In [1], the authors provide an algorithm for counting the number of reasoning shortcuts. They also use something similar to constraint solving (WMC). Is this not similar to the derived CSP you introduce? Can you elaborate on the difference? \n\nYes, [1] uses model counting for reasoning shortcuts. Technically, they formulate the problem as a logical formula and then adopt an automated reasoning solver to count the possible worlds while our DCSP framework uses constraint solving. However, the main difference between our DCSP framework and their $\\texttt{countrss}$ approach is:\n\n**Beyond counting**: While [1] counts shortcuts, we analyze disagreement patterns among solutions to derive theoretical guarantees and error bounds. \n\nFurthermore, our work aims to provide formal learnability conditions, whereas [1] focuses on practical benchmark evaluation. Additionally, with the lens of our proposed DCSP framework, we can suggest solutions (e.g., task aggregation, cf. section 3.5) when tasks are unlearnable.\n\n---\n> Q2. Line 45: You link your analysis with deterministic reasoning shortcuts. Is there also a link with probabilistic reasoning shortcuts (as defined by [2])? \n\nYes, there is a natural connection. Probabilistic reasoning shortcuts in [2] can be viewed as convex combinations of deterministic reasoning shortcuts, which creates a bridge to our DCSP framework.\n\nOur DCSP framework can be extended to handle probabilistic shortcuts by incorporating prior probabilities over DCSP solutions. Assigning a prior probability $\\pi_i$ to each DCSP solution $I_i$ enables more refined expected error bounds that account for probabilistic effects. This extension leaves a promising direction for the future work.\n\n---\n> Q3. Equation 4: Shouldn't there be a logarithm in front of p, like in Equation 5? \n\nThe logarithm appears in Equation 5 because we convert likelihood to log-likelihood for practical optimization. We will clarify this mathematical transformation in the revision.\n\n---\n> Q5. Lines 141-145 of the related work are not really clear to me. What does \"full knowledge of the underlying concept sequence distribution\" mean exactly? \n\nThis refers to knowing the true joint distribution $P(\\mathcal{Z}^m)$ over concept sequences. In [3], their analysis requires constructing a probabilistic matrix $\\tilde{Q}$ that captures the relationship between true and predicted concept distributions. However, constructing this matrix requires knowing how concept sequences are distributed in the true data-generating process, which is typically unavailable in practice.\n\n---\n> Q6. Line 178-184 and 191-194: This is not clear to me. Does the hypothesis space F refer to (1) the logic rules to compute the task from the concepts, or (2) the neural networks mapping input to concepts, or (3) both? [...]\n\nThe hypothesis space $\\mathcal{F}$ refers specifically to (2) - neural networks mapping inputs to concepts. The logical rules $\\mathtt{KB}$ are fixed as part of the task definition. In our framework:\n- $f \\in \\mathcal{F}$: concept predictor (neural network) mapping $\\mathcal{X} \\to \\mathcal{Z}$\n- $\\mathtt{KB}$: fixed logical rules for reasoning\nProposition 3.2 discusses how restricting $\\mathcal{F}$ (the neural network family) affects learnability, not the logical rules.\n\nWe will revise proposition 3.2 for a better clarity, plese refer to our response to C3 of Reviewer `gMsj` for details.\n\n---\n> Q7. As a consequence of the above point, I'm not sure what the \"restricted hypothesis space\" exactly refers to (as I'm not sure what the \"hypothesis space\" exactly refers to). \n\nIn learning theory, hypothesis space refers to the set of learning models (e.g., linear models for linear classification). Here, \"restricted hypothesis space\" refers to hypothesis spaces with limited complexity to avoid overfitting. The formal definition is provided in lines 192-195.\n\n---\n> Q8. Line 202: Is there a reason why the different variables V_i have the same domain Z? \n\nYes, this reflects the typical NeSy setup where all concept positions share the same concept space. For example, in digit arithmetic, each position can be any digit 0-9. However, our framework can be extended to heterogeneous domains where different $V_i$ have different domains $\\mathcal{Z}_i$.\n\n---\n> Q9. Lines 265-270: I would work this example more out. I don't immediately see why, when k=8, there are 4 solutions and d/L=0.4. What are the exact values for d and L, and maybe you can briefly give some examples of solutions. \n\nFor $k=8$, the DCSP solutions are:\n```python\nSolutions = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], # ground truth\n             [0, 9, 2, 3, 4, 5, 6, 7, 8, 1], \n             [8, 9, 2, 3, 4, 5, 6, 7, 0, 1], \n             [8, 1, 2, 3, 4, 5, 6, 7, 0, 9]]\n```\nHere, disagreement $d = 4$ and concept space size $L = 10$, giving $d/L = 0.4$.\n\nFor $k=10$:\n```python\nSolutions = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], # ground truth\n             [5, 6, 7, 8, 9, 0, 1, 2, 3, 4]]\n```\nHere, $d = 10$ and $d/L = 1.0$. \n\nWe can find that: despite case-$k=10$ having fewer solutions than case-$k=8$, the disagreement is worse because all positions can be varied, which shows our DCSP framework can perform a more nuanced analysis than simply reasoning shortcuts counting.\n\n---\n> Q11. What is the setup for the CIFAR-10 and SVHN datasets (Appendix line 756)? \n\nPlease refer to W1.\n\n---\n> Q10. In Figure 3, can you give some intuition on why the reasoning accuracy is bad for the aggregation?\n> \n> Q12. Can you elaborate on what you state in lines 769-770: \"optimization becomes significantly more challenging due to high conflicts among valid DCSP solutions\". Why is reasoning accuracy so low when there are shortcuts (e.g. Figure 9 for k=2)?\n\nThe low reasoning accuracy reflects optimization failure due to conflicting signals from multiple DCSP solutions. When multiple valid solutions exist, the optimization landscape becomes multi-modal, causing the model to oscillate between different concept assignments rather than converging consistently.  Similar training instabilities have been documented in other neuro-symbolic literature (e.g., Table 3 in [2], Table 12 & Figure 7 in [4], and Figure 1 in [5]), confirming this is an open challenge in the field.\n\n**Clarification on \"shortcuts\"**: While [2] refers to multiple valid solutions as \"reasoning shortcuts,\" *this terminology emphasizes solution diversity rather than optimization ease*. These shortcuts represent alternative valid reasoning paths, not computational shortcuts that simplify optimization. Despite the name suggesting ease, multiple shortcuts actually make optimization harder by creating conflicting optimization signals.\n\n---\n**Revision summary**\n\nGiven our response above, we will make the following key revisions:\n\n**1. Enhance Experimental Setup (W1, Q11)**\n- Add detailed dataset configuration for CIFAR-10/SVHN setup\n\n**2. Improve Presentation Quality (W2, Q3)**\n- Increase font sizes in necessary figures\n- Clarify relationship between Equations 4 and 5\n\n**3. Expand Examples and Analysis (Q9, Q10, Q12)**\n- Provide detailed DCSP solution examples\n- Analyze experiment results comprehensively as response of Q10, Q12.\n- Clarification on \"reasoning shortcuts\"\n\n--- \nWe hope our responses have addressed your concerns.\nIf you have any further questions, please do not hesitate to ask. \n\n---\n**References** \n\n[1] A Neuro-Symbolic Benchmark Suite for Concept Quality and Reasoning Shortcuts. Bortolotti et al.\n\n[2] Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts. Marconato et al. \n\n[3] Deciphering Raw Data in Neuro-Symbolic Learning with Provable Guarantees. Tao et al. \n\n[4] BEARS Make Neuro-Symbolic Models Aware of their Reasoning Shortcuts. Marconato et al. \n\n[5] Ambiguity-Aware Abductive Learning. He et al."}]

Author rebuttal:

Meta-review: Solid technical paper of interest to NeSy practitioners and researchers alike. All reviewers agree that its strengths outweight its weaknesses, which aren't many. The author-reviewer discussion was very polite and productive. I recommend the authors integrate all the promised changes (i.e., improving clarity of the text and figures where requested; including the BDD-OIA experiment) into the revision.
Decision: Accept (spotlight)