acceptodds
Withdrawn from ICLR 2027

Explanation Selection in Abductive Learning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Abductive learning (ABL) offers a promising framework that connects machine learning and logical reasoning in a mutually beneficial loop. However, this bidirectional feedback can also reinforce incorrect concept semantics, since different interpretations of intermediate concepts may explain the same observed reasoning outcomes. Static analyses characterize this ambiguity but leave open which explanation training selects and whether its labels can still be corrected. We develop a dynamical analysis of a fixed-feature binary ABL model that links the local stability of competing explanations to differences in their concept labels. We prove that Gram matrices with identical spectra can select different explanations even under the same supervision, objective, and initialization. We further identify conditions under which a selected explanation is guaranteed to persist despite subsequent changes in optimization geometry. Changing its labels would require crossing a region with lower probability of satisfying all constraints, creating an evidence barrier. Even when the correct explanation is the only realizable one, the updates can converge to a finite, strictly suboptimal state with incorrect concept labels. Experiments on visual ABL tasks support this distinction between selecting among compatible explanations and recovering a uniquely realizable correct explanation.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Abductive learning, Learning dynamics

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_G8BzOpenReview ↗
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
  1. Restrictive theoretical setting: The analysis is limited to fixed-feature, binary ABL models.
  2. 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?
  3. 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.
  4. Experiments are only diagnostic and the biggest let down of the paper due to the following reasons:
  5. 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.
  6. 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.
  7. 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
AuthorsOpenReview ↗

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.

  • Wrong attractors (A1). Ordinary random initializations reach the wrong attractors of Section 6.3, without any construction, and wrong explanations are also reached under Sudoku rules with four classes.
  • From explanation to recovery (A2). In the setting of Section 6.3, the dynamical theory yields a recovery guarantee.
  • Ordinary training (A3). With a jointly trained ResNet-18, SGD and Adam select different explanations of the same supervision, and the more errors an explanation contains, the lower the accuracy on unseen data.
  • Scope of the theory (A4 and A5). The preservation of the selected labels extends to multiclass concepts and, under gradient flow, to jointly learned representations. For minibatch updates, we cannot yet give an advance guarantee, but we provide a test that is checked after each update. In the experiment, the selected labels do not change during 12,544 further training updates.

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 ρ\rho 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.

  • Random initializations are trapped. At ρ=0.92\rho=0.92, 0.94, 0.96, 0.98, and 0.99, the number of runs that end with every image mislabeled is 0, 2, 7, 25, and 42 of 96.
  • They reach the wrong state of our analysis. Continuing the 25 failed runs at ρ=0.98\rho=0.98 brings each into a neighborhood in which we prove contraction to the wrong state, so these random initializations lie in its basin.
  • Equal weights suffice when few images are identified. With equal weights for all queries, but directly identifying queries for only 4 of the 256 images, 49 of 96 runs remain entirely wrong, although the labels are still uniquely determined.

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.

Boards that reveal one cellRuns that learn the correct conceptsOther runs: training boards on which every rule and revealed cell holdsOther runs: training concept accuracy
100%8 of 8––
20%2 of 8100%5%–54%
2%1 of 8100%0.4%–50%

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.

AuthorsOpenReview ↗

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 ρc=22−2≈0.828\rho_c=2\sqrt2-2\approx0.828 on the weight ρ\rho of the ambiguous queries. Gradient descent recovers every concept from every finite initialization exactly when ρ<ρc\rho < \rho_c, and for ρc<ρ<1\rho_c < \rho < 1 a wrong attractor exists. The threshold suggests a correction: lower ρ\rho below ρc\rho_c for a while, and restore it once all observed counts are correct and the original loss is below 2log⁡2/n2\log2/n, where nn 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.

AuthorsOpenReview ↗

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).

TrainingRuns satisfying all countsMislabeled training imagesTest concept accuracyLost vs. referenceTest count accuracyLost vs. reference
Count supervision, Adam32/327.72%87.467.563.9418.0
Count supervision, SGD28/3210.61%84.7210.257.5924.3
Correct concept labels (reference)32/320%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 E>1/2E > 1/2, where EE 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 E>1/2E > 1/2, and none of their 12,544 further minibatch updates changes a label.

AuthorsOpenReview ↗

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 E>1/2E > 1/2, 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 E>1/2E > 1/2, an update can change a training label only if it raises, by at least log⁡(2E)\log(2E), 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 E>1/2E > 1/2.
  • 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.

Reviewer_ZhGVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies how abductive learning selects among competing concept explanations. It theoretically shows that optimization geometry can determine the selected explanation, derive conditions under which an explanation becomes permanently captured, and demonstrate that incorrect attractors may exist even when the correct explanation is uniquely realizable.

Critical strengths
  1. The paper addresses an important distinction between static identifiability and the explanation actually selected by optimization.
  2. The common-potential formulation provides a clean foundation connecting posterior refresh, soft-label training, and optimization geometry.
Critical weaknesses
  1. The analysis assumes binary concepts, a fixed feature representation, exact enumeration of the legal-code posterior, detached marginal targets, and full-batch updates. In realistic ABL systems, the encoder is often trained jointly, reasoning may be approximate, and optimization is stochastic. Representation learning can change both the Gram geometry and which explanations are realizable during training, so it is unclear which conclusions extend beyond the fixed-feature model.
  2. The isospectral theorem is mathematically interesting, but the experiments instantiate it using specially designed positive-definite parameter metrics. These metrics validate the theoretical construction, yet they may not resemble the geometries induced by commonly used optimizers such as SGD or Adam.
  3. The explanation-selection experiment uses 24 CIFAR-10 images per training set, while the identifiable-count experiment uses 256 images with a frozen ImageNet-pretrained encoder. Most analysis concerns training-label assignments, count satisfaction, and local convergence. It remains unclear whether different selected explanations lead to meaningful differences in held-out concept classification, reasoning accuracy, or robustness on larger ABL tasks.
Questions for authors
  1. The theoretical analysis assumes fixed features, exact posterior refresh, and full-batch updates. Which results are expected to remain valid under approximate inference, minibatch training, or jointly learned representations?
  2. The explanation-selection experiments use specially constructed preconditioners. Can the authors show that standard optimizers such as SGD, Adam, or natural-gradient approximations also select meaningfully different explanations from the same initialization?
3 comments
AuthorsOpenReview ↗

Response to Reviewer ZhGV (1/3)

We thank Reviewer ZhGV for the insightful review and for appreciating the distinction between static identifiability and the explanation that optimization actually selects. Your comments pointed out a real gap between our analysis and ordinary ABL training, and addressing them has made the paper considerably stronger. We answer your questions below.

Summary of the changes.

  • Ordinary training (A1 and A2). With a jointly trained ResNet-18, SGD and Adam select different explanations of the same supervision, and the more errors an explanation contains, the lower the accuracy on unseen data.
  • A second task (A2). Under Sudoku rules with four classes, most runs satisfy the entire supervision with wrong concepts when few cells are revealed.
  • Scope of the theory (A3). The preservation of the selected labels extends to multiclass concepts and, under gradient flow, to jointly learned representations. For minibatch updates, we cannot yet give an advance guarantee, but we provide a test that is checked after each update. In the experiment, the selected labels do not change during 12,544 further training updates.

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 2 and Question 2). The isospectral experiments use specially designed metrics. Can standard optimizers such as SGD and Adam also select different explanations from the same initialization?

A1. Yes. In 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 (Section 6.1, Figure 3, and Appendix F.3).

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.

Result. 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). With a frozen encoder, the setting of our theory, SGD and Adam also select different explanations in all 32 cases.

The designed metrics of the submission isolate why the selected explanation depends on the optimization geometry. This experiment shows that the dependence also appears with ordinary optimizers.

AuthorsOpenReview ↗

Response to Reviewer ZhGV (2/3)

Q2 (Weakness 3). The experiments are small and mostly concern training labels. Do different selected explanations change held-out concept and reasoning accuracy on larger tasks?

A2. Yes: every selected explanation is partly wrong, and the accuracy lost on unseen data grows with its errors.

Setup. The experiment of A1 has 1,024 training images, against 24 in the original selection experiment. We evaluate its models on 2,000 unseen images (concept accuracy) and on 500 unseen bags (count accuracy, the reasoning accuracy that you mention). As a reference, each initial network is also trained with Adam on the correct concept labels, with the same data, minibatches, and budget.

TrainingRuns satisfying all countsMislabeled training imagesTest concept accuracyLost vs. referenceTest count accuracyLost vs. reference
Count supervision, Adam32/327.72%87.467.563.9418.0
Count supervision, SGD28/3210.61%84.7210.257.5924.3
Correct concept labels (reference)32/320%94.93–81.92–

Result. Each of the 60 count-satisfying models mislabels some training images and is less accurate than its reference. The concept accuracy lost is nearly proportional to the fraction of mislabeled training images (correlation 0.97; 0.95 for SGD and 0.99 for Adam).

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.

Wrong explanations are also selected under a different logical structure, with four classes (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.

Boards that reveal one cellRuns that learn the correct conceptsOther runs: training boards on which every rule and revealed cell holdsOther runs: training concept accuracy
100%8 of 8––
20%2 of 8100%5%–54%
2%1 of 8100%0.4%–50%

Each row has eight runs. A run learns the concepts when its training concept accuracy is at least 99%.

Result. When every board reveals a cell, all runs learn the concepts and match training on the true labels on unseen images (median 93.8% against 93.9%). 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.

AuthorsOpenReview ↗

Response to Reviewer ZhGV (3/3)

Q3 (Weakness 1 and Question 1). Which results remain valid under approximate inference, minibatch training, or jointly learned representations?

A3. Label preservation extends to jointly learned representations under gradient flow, and stability and capture tolerate small posterior errors. For minibatch updates, we cannot yet give an advance guarantee, but we provide a test that is checked after each update (Appendices E.5 and E.6). Below, EE is the probability, under the model's predictions, that all training constraints hold.

  • Jointly learned representations and multiclass concepts. Representation learning changes the Gram during training, as you point out. The update still follows the gradient of a single potential, and once E>1/2E > 1/2, 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 E>1/2E > 1/2, an update can change a training label only if it raises, by at least log⁡(2E)\log(2E), 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.
  • Approximate inference. In the fixed-feature model, stability and capture tolerate posterior errors that are small relative to the exact residual, under a tighter step-size bound. Our submission contains this result, although we stated it only briefly in the main text (Sections 3.1 and 5.1 of the submission; Appendices C.10 and E.3 in the revision). 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 E>1/2E > 1/2.
  • 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.

What we observe in ordinary training. Of the 64 models of A1, 49 end with E>1/2E > 1/2. 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 test (Appendix F.3).


Thank you again for your valuable comments. They led to the new experiments and the 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.

Reviewer_YeqGOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how abductive learning selects among concept-label assignments that are all compatible with the same logical supervision. It analyzes a fixed-feature binary model in which the learner predicts independent labels, computes the exact posterior over legal complete assignments, and uses the posterior marginals as detached soft targets for a full-batch update. The resulting margin dynamics ascend a common legal-evidence potential, while the sample Gram matrix determines the direction of ascent.

The main theoretical results are: 1. in native uniform-prior, unit-temperature model, a legal code is locally asymptotically stable precisely when its minimum Hamming distance to another legal code is at least two; 2. Gram matrices with identical spectra can route a common open set of initial states to different locally attracting explanations; 3. the legal evidence above one half provides a capture certificate under stated spectral and step-size conditions, preserving the selected hard labels even under later history-dependent metric changes; and 4. identifiability of the legal code within a shared predictor does not guarantee recovery, since finite, strictly suboptimal attracting states with incorrect predictions can exist.

The experiments use frozen ImageNet-pretrained ResNet 18 features and CIFAR-10 bird/cat count supervision. They demonstrate different fitted assignments under matched-spectrum Gram orientations, preservation of captured labels under metric interventions , and attraction to deliberately constructed incorrect stationary points despite uniquely identifying count constraints. The paper provides proofs in Appendices B–E and experimental protocols and code in Appendix F and the supplementary repository.

Critical strengths
  1. A coherent dynamical formulation with a shared potential: The observation that the detached posterior marginal residual is the gradient of a common legal-evidence potential makes it possible to compare different Gram matrices without changing the underlying objective. This is an strong organizing insight for the analysis.
  2. Meaningful separation of stability and selection: The Hamming-distance criterion explains when individual legal explanations can attract nearby states, while the isospectral construction shows that eigenvalues alone do not determine which explanation is selected. Theorem 3 strengthens the illustrative symmetric example by establishing routing from a common open neighborhood of initializations and neighborhoods of Gram matrices.
  3. A useful capture result with a clear interpretation: Theorem 4 identifies a finite-state certificate, E(y) > 1/2, after which hard labels cannot change under the stated uniform positive-definiteness and step-size bounds. The extension to history-dependent metrics and the shared-head corollary make the result more relevant than a fixed-Gram statement alone. The paper does not conflate identifiability with optimization success. Proposition 5 and the accompanying analysis make the important point that a unique realizable legal code does not rule out finite incorrect attractors. The authors also state the fixed-representation and arbitrary-initialization limitations rather than claiming a general recovery theory.
Critical weaknesses
  1. The scope of the theory is substantially narrower than general ABL: The analysis consider binary concepts, a finite set of complete legal codes, fixed features, exact posterior refresh, uniform priors and unit temperature for the central results, and detached marginal targets. These assumptions are appropriate for obtaining sharp results, but actual ABL systems can involve multiclass concepts, learned representations, approximate or sampled abduction, nonuniform candidate weighting, and changing logical structures. The paper discusses some extensions (for example priors and temperature, and controlled posterior errors), but it remains unclear which qualitative conclusions survive the broader settings most commonly used in practice.
  2. The empirical study is primarily a controlled mechanism demonstration, not a broad assessment of practical prevalence. In Sections 6.1–6.2, the disjoint-bag experiment has 24 images per training set and a head capable of freely controlling the training predictions. The restricted-head experiment is a useful step toward a shared predictor, but it still uses a frozen encoder and a specially designed count-supervision setup. These experiments establish that the proposed effects can occur; they do not establish how frequently they occur in standard ABL pipelines or on larger, more varied tasks.
  3. The identifiable-count experiment tests local attraction around specially constructed wrong centers: In Section 6.3, six incorrect heads are constructed using the true labels and selected loss weights, then perturbed by a small RMS logit distance of 0.01. The observed return toward these centers is convincing evidence of local attraction. However, the 192 random-initialization runs recover all labels, so the experiment does not show that ordinary random training commonly enters these basins. The paper appropriately claims existence and local attraction, but the practical significance would be clearer with basin-size estimates or a systematic initialization study.
  4. relationship between the abstract Gram analysis and ordinary parameter training deserves more emphasis: The isospectral routing theorem is stated for positive-definite sample-space Grams, while a shared linear head induces K = X M Xᵀ, which can be singular when the feature matrix is rank deficient. The paper addresses this distinction for capture through Corollary 1 and Section 6.2, but the main isospectral selection result is not demonstrated in the same way for the rank-deficient shared-head setting. This is an important boundary on how directly the central selection theorem transfers to standard parameter-space optimization.
  5. Some practical implications of the capture certificate are not fully explored. The threshold is a sufficient certificate under uniform lower and upper spectral bounds and a step-size restriction; it is not a general characterization of when labels become immutable in arbitrary implementations. The experiments show that the condition is met and then verify preservation under admissible interventions. It would help to clarify how often comparable bounds and evidence thresholds are available or estimable in realistic ABL training, and how conservative the certificate is in practice.
  6. The empirical comparisons leave some questions about sensitivity and generality: The central experiments use one dataset family, one frozen pretrained architecture, and specific count constructions. The paper includes multiple disjoint training sets and heads, which is helpful, but broader datasets, concept domains, and representation choices would strengthen the claim that the phenomena are not artifacts of this particular setup.
Questions for authors
  • Can the authors quantify the basin of attraction of the incorrect stationary points in Section 6.3? For example, can they report what fraction of a systematic range of initializations or perturbation radii converges to the incorrect center, and how this fraction depends on ρ\rho?

  • How sensitive are the results in Section 6.3 to the construction of the wrong centers and the selected weights ρ∈{0.85,0.9}\rho \in \{0.85, 0.9\}? Do comparable wrong attracting states arise without using the true labels to construct these centers?

  • Can the authors demonstrate the isospectral explanation-selection phenomenon for a rank-deficient shared-head Gram matrix induced by parameter-space metrics, rather than only for the positive-definite sample-space construction? If not, what precise obstruction prevents this extension?

  • How conservative is the E>1/2E > 1/2 capture condition in the experiments? Do trajectories typically cross this threshold well before convergence? Can the authors report how capture time and label preservation change as the step size approaches the allowed bound?

  • Which parts of the stability and capture results extend to nonuniform priors, temperatures other than one, multiclass concepts, or approximate posterior computation?

  • Can the authors include an end-to-end or representation-learning experiment, even on a small task, to test whether the selection and capture effects persist when the feature representation is not frozen?

4 comments
AuthorsOpenReview ↗

Response to Reviewer YeqG (1/4)

We thank Reviewer YeqG for the insightful and detailed review and for appreciating the shared-potential formulation, the separation of stability from selection, and the capture result. Your questions were precise and constructive, and answering them has substantially improved the paper. We answer them below.

Summary of the changes.

  • Wrong attractors (A1 and A2). We prove an exact threshold on the weight ρ\rho of the ambiguous queries, below which gradient descent recovers the correct concepts from every initialization and above which a wrong attractor exists, and we measure how often random initializations are trapped.
  • Rank-deficient shared head (A3). We prove isospectral selection for a shared head whose sample Gram is singular.
  • Capture threshold (A4). We prove that the threshold 1/2 is optimal and measure when capture occurs as the step size approaches its bound.
  • Scope of the theory (A5). The preservation of the selected labels extends to multiclass concepts and, under gradient flow, to jointly learned representations. For minibatch updates, we cannot yet give an advance guarantee, but we provide a test that is checked after each update.
  • Learned representations (A6). Two new experiments train a ResNet-18 jointly with its classifier, one with SGD and Adam under count supervision and one under Sudoku rules.

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 (and Weakness 3). Can the authors quantify the basin of attraction of the incorrect stationary points in Section 6.3, and its dependence on ρ\rho?

A1. Yes. Random initializations are trapped only when ρ\rho is large, the wrong states survive perturbations far larger than those of the submission, and we prove exactly for which ρ\rho a wrong state exists (Section 6.3, Appendices E.9 and F.8).

Random initializations. We draw the head from the default initialization of a linear layer, using no label, and train it for 500,000 updates with full-batch gradient descent (GD) or minibatch SGD. The table counts, among 96 runs for each ρ\rho, those that end with every image mislabeled; all others recover all labels.

ρ\rho0.84–0.920.940.960.980.99
GD0272542
SGD0262642

No run is trapped up to ρ=0.92\rho=0.92, and the number then grows with ρ\rho.

Larger perturbations. We perturb the wrong states at four values of ρ\rho by up to 300 times the radius used in the submission. Every random perturbation of up to 30 times the original radius returns to the wrong state, and 1,112 of the 1,296 trajectories return overall. At 300 times the original radius, 4, 15, 22, and 24 of 24 trajectories return for ρ=0.835\rho=0.835, 0.85, 8/9, and 0.9 (random parameter directions). Across these sampled perturbations, the basin extends well beyond the neighborhood tested in the submission and widens as ρ\rho grows.

An exact threshold. For the query system of Section 6.3, where every image has a directly identifying query, we prove a threshold ρc=22−2≈0.828\rho_c=2\sqrt2-2\approx0.828. Gradient descent recovers every concept from every finite initialization exactly when ρ<ρc\rho < \rho_c, and for ρc<ρ<1\rho_c < \rho < 1 a wrong attracting state exists. The proof assumes full-batch gradient descent with a sufficiently small step and features of full row rank.


Q2 (and Weakness 3). How sensitive are the results to the construction of the wrong centers and to ρ∈{0.85,0.9}\rho\in\lbrace 0.85,0.9\rbrace? Do comparable wrong states arise without using the true labels?

A2. Comparable wrong states arise without the true labels and are not specific to these two weights.

They arise without any label. In the experiment of A1, no concept label is used at any point, and 25 of the 96 GD runs at ρ=0.98\rho=0.98 still end with every image mislabeled. When we continue these runs, each enters a neighborhood of the wrong state in which we prove convergence to it, so they lie in its basin (Appendices E.8 and F.8).

They are not specific to the two weights. By A1, a wrong attracting state exists for every ρ\rho between ρc\rho_c and 1, including ρ=8/9\rho=8/9, where all 1,152 queries carry equal weight. Wrong states also appear at equal weights when few images have an identifying query: with such queries for only 4 of the 256 images, 49 of 96 GD runs remain entirely wrong, although the labels remain uniquely determined (Appendix F.8).

They can be corrected. The threshold suggests a correction: lower ρ\rho below ρc\rho_c for a while and restore it under a stopping rule. For the model of A1, we prove that the rule is met after finitely many updates and that every concept stays correct afterwards, and the correction recovers all 25 trapped runs (Appendix E.9).

AuthorsOpenReview ↗

Response to Reviewer YeqG (2/4)

Q3 (and Weakness 4). Can isospectral selection be shown for a rank-deficient shared-head Gram induced by parameter-space metrics?

A3. Yes, for a class of rank-deficient shared heads. As you note, the submission treats capture for such a head (Corollary 1 and the restricted-head experiment of Section 6.2). The revision adds a selection result for heads that tie the two predictions within each pair of inputs (Appendix D.10, summarized in Section 4.2).

Such a head cannot set all predictions independently, so every sample Gram that it induces is singular. We show that parameter metrics with identical spectra induce singular sample Grams whose spectra are also identical, zero eigenvalues included. From a common open set of initial heads, these metrics still select different explanations, and the selection is robust to small perturbations of the metrics.

Singularity does not prevent selection here because the representation keeps every direction that distinguishes the candidate explanations. The obstruction to a general result is that a rank-deficient head can follow only part of the direction in which the soft labels pull the predictions. In our class this part is the whole direction, because the soft labels respect the same ties as the predictions. For an arbitrary rank-deficient head it is not, and our proof does not cover that case. We regret that we could not settle it in this revision and leave it as an open question.


Q4 (and Weakness 5). How conservative is the E>1/2E > 1/2 condition? Do trajectories cross it well before convergence, and how do capture time and label preservation change as the step size approaches the bound?

A4. The condition is only mildly conservative, runs reach it at about 65% of the time that they need to fit the counts with high confidence, and increasing the step size only makes capture come earlier. Below, EE is the probability, under the model's predictions, that all training constraints hold, and a run is captured at the first update at which E>1/2E > 1/2.

How conservative is the condition?

  • The value 1/2 cannot be lowered. For every threshold below 1/2, we give a state whose EE exceeds that threshold and an update allowed by Theorem 4 that changes its labels (Appendix E.1).
  • The condition holds soon after the labels can no longer be changed. On each of the 96 original runs, we searched for the latest point from which updates allowed by Theorem 4 still change a label, and found one on every run. Capture occurs between 161 and 322 updates after it, with a median of 240 updates, which is a median 26.6% of the number of updates until capture (Appendix F.5). On each run, the delay of the condition is at most this long.

Do runs cross the threshold well before convergence? Yes. We measure convergence by the first update at which a run fits all counts with high confidence (Appendix F.2). Capture occurs at a median of 65% of this number of updates.

What happens as the step size approaches the bound? We repeated the six-bag experiment of the submission, which used 80% of the bound, at four step sizes (20%, 50%, 80%, and 95% of the bound), with 96 runs at each. All 384 runs are captured and reach this fit. The numbers of updates until capture and until the fit both decrease in inverse proportion to the step size: the median until capture falls from 3,608 at 20% of the bound to 763.5 at 95%. Capture therefore stays at a median of about 65% of the fitting time. After capture, every intervention preserves the labels, 1,152 of 1,152 across the four step sizes.

Are such bounds available in realistic ABL training? In part. EE can be computed whenever the exact posterior is tractable, as for disjoint bags, and the spectral and step-size bounds of Theorem 4 are available for a head on fixed features. For a deep network, we cannot yet estimate these bounds. There, what we can offer is the per-update test of A5, which needs neither bound and is computed from the predictions before and after an update. In Experiment 1 of A6, it passes at all 12,544 updates.

AuthorsOpenReview ↗

Response to Reviewer YeqG (3/4)

Q5 (and Weakness 1). Which parts of the stability and capture results extend to nonuniform priors, other temperatures, multiclass concepts, or approximate posterior computation?

A5. As you note, the submission treats priors and temperature (Proposition 2, for local stability) and controlled posterior errors (Appendices C.10 and E.3, for stability and capture), so we do not repeat those results here. Capture itself is proved for uniform priors and unit temperature only, and the same holds for the label-preservation results below. The revision adds results for multiclass concepts and jointly learned encoders, and a weaker one for minibatch updates. Below, EE is again the probability that all training constraints hold.

  • 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 E>1/2E > 1/2, 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 E>1/2E > 1/2, an update can change a training label only if it raises, by at least log⁡(2E)\log(2E), 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.
  • Approximate inference. 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 E>1/2E > 1/2.
  • 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.

AuthorsOpenReview ↗

Response to Reviewer YeqG (4/4)

Q6 (and Weaknesses 2 and 6). Can the authors include an end-to-end or representation-learning experiment? More broadly, the experiments use one frozen architecture and specific count constructions.

A6. Yes. The revision adds two experiments in which the whole network is trained. Together, they replace the frozen encoder by a jointly trained one and vary the constraints (counts, Sudoku rules) and the number of classes (two, four).

Experiment 1: SGD and Adam under count supervision (Section 6.1, Figure 3, and Appendix F.3).

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 persists. 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).

TrainingRuns satisfying all countsMislabeled training imagesTest concept accuracyLost vs. referenceTest count accuracyLost vs. reference
Count supervision, Adam32/327.72%87.467.563.9418.0
Count supervision, SGD28/3210.61%84.7210.257.5924.3
Correct concept labels (reference)32/320%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 labels are preserved. Of the 64 models, 49 end with E>1/2E > 1/2. 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.

Experiment 2: a different logical structure, Sudoku rules with four classes (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.

Boards that reveal one cellRuns that learn the correct conceptsOther runs: training boards on which every rule and revealed cell holdsOther runs: training concept accuracy
100%8 of 8––
20%2 of 8100%5%–54%
2%1 of 8100%0.4%–50%

Each row has eight runs. A run learns the concepts when its training concept accuracy is at least 99%.

Result. When every board reveals a cell, all runs learn the concepts and match training on the true labels on unseen images (median 93.8% against 93.9%). 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. The per-update test, applied to each board, passes at all 102,944 checks on the mislabeled boards over 32 further minibatch updates.


Thank you again for your precise and constructive questions. They led to the new theorems and experiments 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.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.