- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper investigates the training dynamics of Abductive Learning (ABL), focusing on why models learn incorrect concept labels in spite of satisfying logical constraints. It establishes theoretical conditions for local stability, demonstrates how optimization geometry influences the selection of competing explanations, and derives guarantees for the persistence of learned explanations under changing optimization conditions. The paper further shows that learning can converge to incorrect suboptimal solutions even when the correct explanation is uniquely realizable.
Critical strengths
The paper addresses an important problem: why a model can learn incorrect concepts even when it satisfies the given logical rules. It provides mathematical explanations for how different incorrect solutions are selected and why they can be difficult to correct later. It also shows that training can fail to recover the correct solution even when that solution is uniquely determined. The experiments are very limited, but are carefully designed to support the theoretical findings.
Critical weaknesses
- Restrictive theoretical setting: The analysis is limited to fixed-feature, binary ABL models.
- Strong assumptions behind the capture certificate: Theorem 4 requires pairwise Hamming distance of at least two, uniformly positive-definite Gram matrices, exact posterior updates, and a sufficiently small step size. How frequently are these assumptions satisfied in practical ABL applications?
- The paper explains when incorrect explanations become stable but it does not propose a new algo for preventing incorrect concept learning or escaping these attractors.
- Experiments are only diagnostic and the biggest let down of the paper due to the following reasons:
- Artificial construction of suboptimal attractors: Section 6.3 starts from deliberately constructed incorrect stationary solutions rather than demonstrating that standard training reaches them. This limits the practical significance of the result.
- Limited generality of the findings: The theoretical analysis and experiments are restricted to fixed-feature binary models with relatively simple count constraints, leaving applicability to end-to-end ABL unclear.
- Limited investigation beyond the constructed theoretical regime: Explanation selection uses deliberately designed isospectral Gram matrices, while capture experiments use only interventions satisfying the sufficient conditions. The prevalence of these phenomena and the possibility of escaping them under natural training conditions remain unclear.
Questions for authors
Provide a rebuttal for the comments in weaknesses.
4 comments
Response to Reviewer G8Bz (2/4)
Q2 (Weakness 3). The paper explains when incorrect explanations become stable, but it does not propose a new algorithm for preventing incorrect concept learning or escaping these attractors.
A2. The aim of our paper is theoretical: to explain how ABL comes to learn incorrect concepts while satisfying its logical supervision. Existing analyses are static. They characterize which explanations are compatible with the supervision and when the correct one is identifiable, but leave open which explanation training selects and whether its labels can still be corrected. Our main contribution is a dynamical theory of explanation selection. It characterizes which explanations attract nearby states, how the optimization geometry selects among them, and when subsequent updates must preserve the selected labels. We believe that a principled remedy has to build on this understanding.
A recovery result (Appendix E.9, tested in Section 6.3). We prove it for one specific setting, the query system of Section 6.3, where the wrong attractor of A1 arises when the ambiguous queries outweigh the identifying ones. There, we obtain an exact threshold on the weight of the ambiguous queries. Gradient descent recovers every concept from every finite initialization exactly when , and for a wrong attractor exists. The threshold suggests a correction: lower below for a while, and restore it once all observed counts are correct and the original loss is below , where is the number of training images. We prove that this point is reached after finitely many updates and that every concept stays correct afterwards. The proofs assume full-batch gradient descent with a sufficiently small step and features of full row rank.
In the experiment, the correction uses only the existing supervision and recovers all 25 trapped runs of A1 within 600,000 updates, whereas unchanged GD recovers none in the same budget. The median accuracy on unseen inputs rises from 18.55% to 89.05% for concepts and from 36.63% to 79.65% for counts.
A general algorithm is beyond what we can offer in this revision, and extending this correction to other constraint systems and to jointly trained networks is what we will pursue next.
Response to Reviewer G8Bz (3/4)
Q3 (Weaknesses 4 and 7). The experiments are only diagnostic: selection uses designed Gram matrices, and capture uses interventions that satisfy the sufficient conditions. Prevalence and escape under natural training conditions remain unclear.
A3. To address this concern, the revision adds an experiment with standard optimizers and a jointly trained network (Section 6.1, Figure 3, and Appendix F.3). Selection occurs in it without designed Gram matrices, and the selected explanations persist without interventions.
Setup. An ImageNet-pretrained ResNet-18 and its classifier are trained jointly on 1,024 CIFAR-10 bird and cat images in 256 bags of four. The only supervision is the number of cats in each bag. From each of 32 initial networks, we train one model with SGD and one with Adam on the same data and minibatches, so the optimizer is the only difference. As a reference, each initial network is also trained with Adam on the correct concept labels, with the same data, minibatches, and budget. We evaluate on 2,000 unseen images and on 500 unseen bags.
Selection occurs under ordinary training. SGD and Adam select different explanations, that is, different concept labels for the training images, in every case in which both satisfy all bag counts. Adam satisfies all 256 bag counts in all 32 runs and SGD in 28 of them. In these 28 cases, the two models disagree on 48 to 200 of the 1,024 training labels (median 90).
The selection matters. Every selected explanation is partly wrong, and the accuracy lost on unseen data grows with its errors (correlation 0.97 across the 60 count-satisfying models).
| Training | Runs satisfying all counts | Mislabeled training images | Test concept accuracy | Lost vs. reference | Test count accuracy | Lost vs. reference |
|---|---|---|---|---|---|---|
| Count supervision, Adam | 32/32 | 7.72% | 87.46 | 7.5 | 63.94 | 18.0 |
| Count supervision, SGD | 28/32 | 10.61% | 84.72 | 10.2 | 57.59 | 24.3 |
| Correct concept labels (reference) | 32/32 | 0% | 94.93 | – | 81.92 | – |
The rows for count supervision average the runs that satisfy every training count, and each loss is measured against the reference from the same initial network. The four SGD runs left out are less accurate on unseen images than every other run, so leaving them out favors count supervision.
The selected explanations persist. Of the 64 models, 49 end with , where is the probability, under the model's predictions, that all training constraints hold. We continue each for 256 minibatch updates, with the encoder and the classifier both training. No update changes a training label, so each model keeps its explanation, including its errors, and all 12,544 updates pass the per-update test of A5.
Escape. We regret that we cannot yet offer a way to escape for the explanations captured in this experiment: our recovery result (A2) is proved for the query system of Section 6.3 only. Within the bounds of Theorem 4, captured labels persist under the same objective, which suggests that a remedy should act before capture or change the objective, as the correction of A2 does. We will explore this in future work.
Q4 (Weakness 2). Theorem 4 requires a pairwise Hamming distance of at least two, positive-definite Gram matrices, exact posterior updates, and a small step size. How often do these assumptions hold in practice?
A4. The first assumption is a property of the constraints, and the next two can be relaxed with results of the submission. We cannot yet remove the step-size bound, and we explain below what we can offer beyond it.
- Distance at least two. This is a property of the constraints alone, so it can be checked before training. It holds for count constraints, since two labelings with the same count differ in at least two labels.
- Positive-definite Gram. Corollary 1 of the submission removes this requirement for a shared classifier head.
- Exact posterior. Section 5.1 of the submission shows that capture tolerates posterior errors that are small relative to the exact residual, under a tighter step-size bound (Appendix E.3 in the revision). For disjoint bags, the exact posterior is directly computable in any case.
- Small step size. We cannot yet remove this assumption: Theorem 4 guarantees in advance that the labels are preserved only within its step-size bound. For step sizes beyond the bound and for adaptive optimizers, what we can offer for now is a weaker result, the per-update test of A5, which can confirm, after each update, that the labels were preserved. Turning it into an advance guarantee is part of our future work.
In practice, the jointly trained experiment of A3 lies outside the assumptions of Theorem 4. There, 49 of the 64 models reach , and none of their 12,544 further minibatch updates changes a label.
Response to Reviewer G8Bz (4/4)
Q5 (Weaknesses 1 and 6). Theory and experiments are restricted to fixed-feature binary models with simple count constraints, which leaves the applicability to end-to-end ABL unclear.
A5. This is a fair point, and we address it on both sides in the revision: we extend label preservation to jointly learned representations under gradient flow and add experiments in which the whole network is trained.
What the theory covers beyond a frozen encoder.
- Jointly learned representations and multiclass concepts. With a jointly trained encoder, the Gram changes during training. The update still follows the gradient of a single potential, and once , joint gradient flow of the encoder and the classifier preserves the selected labels (Appendix E.5). Both statements, and the per-update test below, hold for concepts with any number of classes.
- Minibatch updates. We regret that we cannot yet give an advance guarantee for minibatch updates. What we can offer for now is a weaker result, the per-update test (Appendix E.6): once , an update can change a training label only if it raises, by at least , the cross-entropy between the predictions and the soft labels computed before the update (summed over all training inputs). It is a sufficient condition in hindsight: it can only confirm after an update that the labels were preserved. The test also indicates a route to an advance guarantee, namely to bound in advance how much a minibatch update can raise this cross-entropy, and we will pursue it in future work. For incomplete reasoning, the per-update test remains valid over a verified subset of the explanations, provided that the posterior within the subset is exact and that the subset alone gives .
- Networks in the linearized regime. For a network linearized around its initialization, parameter updates give exactly the update of the paper, with the tangent kernel as the Gram. The stability and capture results therefore apply to it under their stated assumptions, provided that the tangent features have full row rank (Section 2.1 and Appendix E.5). This regime keeps the features fixed, so for learned features the result that applies is the gradient-flow one above.
Like the capture theorem, the gradient-flow result and the test assume an exact posterior, uniform priors, unit temperature, and explanations that differ in at least two labels, which holds for counts. They concern the preservation of labels only. We were not able to extend convergence and its rate, the classification of local stability, or the isospectral selection theorem beyond the binary fixed-feature model in this revision, and the revised conclusion says so. Extending them to learned representations and stochastic updates is the main direction of our future work.
The experiments now train the network end to end. The experiment of A3 trains a ResNet-18 jointly with its classifier using ordinary optimizers, and the Sudoku experiment of A1 goes beyond count constraints and binary concepts (Section 6.1 and Appendix F.9).
Thank you again for your valuable comments. They led to the new experiments and extensions above, which we believe have substantially improved the paper. We hope that our answers address your concerns, and we would be glad to discuss any remaining questions.
Response to Reviewer G8Bz (1/4)
We thank Reviewer G8Bz for the thoughtful review and for appreciating the problem that we study and our theoretical explanations. We are also grateful for your frank assessment of the experiments, which was the main motivation for the new experiments of the revision. We answer your comments below.
Summary of the changes.
New or rewritten passages of the main text and the titles of new appendix subsections are marked in blue. Appendix B now opens with an informal statement of each main result and the experiments that test it.
Q1 (Weakness 5). Section 6.3 starts from deliberately constructed incorrect stationary solutions rather than showing that standard training reaches them.
A1. We agree that our submission showed attraction only around constructed states. The revision shows that ordinary training also reaches these states from random initializations (Section 6.3, Appendices E.8 and F.8), and that wrong explanations are reached on a second task.
Setup. In the task of Section 6.3, same-class pairs identify both labels, mixed pairs leave open which image is which, and ρ is the weight of the mixed pairs. We draw 96 random heads from the default initialization of a linear layer, without using any label, and train them with plain gradient descent for 500,000 updates.
Results.
Wrong explanations are also reached on a second task, from a standard pretrained network (new Appendix F.9).
Setup. Each training example is a 4×4 Sudoku board whose cells are CIFAR-10 images of four classes, and a training set has 250 boards (4,000 images). The supervision consists of the Sudoku rules and, on a fraction of the boards, the class of one cell. An ImageNet-pretrained ResNet-18 is trained in full with Adam, using the exact posterior over the legal completions of each board.
Each row has eight runs. A run learns the concepts when its training concept accuracy is at least 99%.
Result. With fewer revealed cells, most runs satisfy the entire supervision with the wrong concepts. Each of these runs labels every revealed cell correctly and, on the boards without a revealed cell, follows one permutation of the classes on at least 99.7% of the cells.