acceptodds
Under review as a conference paper at ICLR 2027

Aggregation/Optimization Stability Gap in Neuro-Symbolic Inference

Abstract

Neuro-symbolic systems compute two structurally different kinds of query over the same representation: aggregation (marginalizing or averaging over hypotheses) and optimization (selecting a single best witness). We show these obey different stability laws. Aggregation is provably Lipschitz-continuous under belief perturbations, for any bounded-weight aggregation and any Lipschitz neural scorer. Optimization is not: we construct, explicitly, a neural scorer of arbitrary smoothness under which an arbitrarily small input perturbation produces an arbitrarily large change in the selected witness. We show both the magnitude and frequency of an optimization failure. We instantiate this result on three structurally unrelated representations – model-based diagnosis, abductive explanation, and constrained route planning under belief uncertainty – and validate it empirically on all three, including a controlled, timed comparison of aggregation and optimization on identical trained representations. We further show optimization-side intractability is not inevitable: two independent mechanisms, structural (bounded treewidth) and algorithmic (randomized restart), recover practical tractability.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
neuro-symbolic inference, stability

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_yHLmOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper analyses the stability of two operators: aggregation and optimization under perturbations. It finds that aggregation is provably Lipschitz continous under belief perturbations, but optimization is not. Which is not suprising since argmax-optimization under belief perturbations is not a continous functions with the change being essentially only bounded by the hypothesis space.

The paper, being theory-heavy, is very hard to understand and confusingly written. Concepts are not properly defined, arguments to not support each other properly and contents of sections do not support the title. In its current form, it is hard to parse and not possible to review.

Critical strengths

None in it's current form

Critical weaknesses

The paper is extremely hard to parse. keywords are constantly introduced without being explained, sentences seemingly refer to each other without any obvious connection. For example, even the abstract is hard to understand: first off, the connection to neuro-symbolic systems is not clear: one can study the stability of a weighted sum versus computing the argmax without being embedded into a neuro-symbolic system. It is not clear how it connects to the title. Then, after establishing that the optimization is unstable, the abstract pivots to "We further show optimization-side intractability is not inevitable: (...)", but there is no tractability discussion to refer to!

Furthermore, section 3 is very crucial for the paper. It introduces the whole setting but is just reduced to a list of arbitrary keywords without explanation, definition or motivation. E.g. why is definition 1 now the object of interest for the optimization, whereas in the introduction we were concerned with the argmax? Every symbol in section 3 must be properly defined, explained and motivated, right now it is not possible to discern what is going on. Examples of unclear symbols/definitions/sections in section 3 are:

  • Remark 1: is in unclear how it fits into the into the preliminaries, as message passing is neither mentioned not defined the computational object. Even more so, it is completely unclear how it would fit into the general architecture
  • "a neural scorer fθ (assumed L-Lipschitz) produces soft confidences p∈[0,1]m over m candidate predicates;" what are these candidates predicates? What is the setting of the neural scorer?
  • "a discretization step τ produces a predicate set P" What is the discretization step? A Thresholding?
  • "a decision operator Ψ maps P to a solution ∆" So apparently this decision operator is both for aggregation and optimization, but for some reason the thresholding is not analyzed in the aggregation context?
  • "Definition 1 (Optimization-mode inference)" unclear how it connects to the previous argmax-based explanation of the optimization
  • "Given interpretations Ω, a satisfaction predicate µ :L×Ω →{0,1}over a predicate family L, and a target family K⊆L(derived from P above via τ), optimization-mode inference computes" What are the interpretations Omega? of what? What is L? "target family K⊆L(derived from P above via τ)" how is K derived from P via τ? What is the connection?
  • " ω inclusion-minimal with this property " what does it mean to be inclusion-minimal with this property (probably refers to satisfaction predicate µ?)
  • Motivation, intuition and interpretation of definition 1 is completely omitted
  • "dP(P1,P2) is the symmetric-difference cardinality between two predicate families" unclear what the symmetric-difference cardinality is
  • Definition 2: "|P1⋄P2|" unclear if this is now another symbol for dP(P1,P2)
  • Decision sensitivity is entirely unmotivated, e.g. what does it measure? Why is this a useful concept to analyze?

This continues to section 2, the 6 hypothesis, which are central to the paper:

  • "as the relevant uncertainty problem size/number of required waypoints (K) grows." waypoint were never defined, unclear what they should refer to
  • "with the size of the discontinuity governed by margin, not by perturbation size" not clear what margin is referring to
  • H4 (Recoverable tractability): unclear which intractability this refers to, as previously we were discussing stability. Also, these approaches restrict the function class (of message-passing), are well known, and message passing is never so far introduced. it is unclear how it embeds into the architecture
  • "H5 (Margin CDF Predicts Optimization Instability). The empirical instability frequency is upper-bounded by the empirical margin CDF." it is unclear, and never mentioned what a margin cdf is, "empirical instability frequency" is also unclear, despite these being the main hypothesis of the paper
  • "H6 (Impact of Temperature Scaling on Calibration and Instability)" calibration is also unclear how it fits into the picture, e.g. there is not uncertainty covered. also, we never defined the temperature inside the pipeline. Therefore, the main hypothesis section is hard to read and not understandable

This theme continues in section 5 (Theory), leading to sections like 5.1.2 ("WHAT ACTUALLY MAKES OPTIMIZATION UNSTABLE") which is not answered in this section, a seemingly unrelated definition is given instead. Or 5.2 ("INSTANTIATIONS"), with example like this:

"Instantiation 1: model-based diagnosis. Ω = 2^U for component universe U, µ = “hits every conflict,” K= the reported conflict family. Reiter diagnosis, structural diagnosis, MUS-based repair, and geometric MBD are recovered as instances by the same argument."

It is unclear what a component universe U is, µ = “hits every conflict,” is not a proper mathematical definition and unclear from the context what it should be. "K= the reported conflict family" is not a proper instantiation, it is unspecific prose. What Reiter diagnosis, structural diagnosis, MUS-based repair, and geometric MBD refer to is not defined. Also, which argument is referenced here?

Questions for authors
  • What is the connection to neuro-symbolic learning?
  • What are all the definitions/unclear prose mentioned above in "Critical Weaknesses"
3 comments

Response to Reviewer yHLm

Thank you for the detailed list. We accept that Section 3 as submitted was not reviewable, and we have rewritten it.

Connection to neuro-symbolic learning. The objects studied are pipelines of Kautz's Neuro;Symbolic type: a neural network outputs beliefs over a fixed vocabulary of symbolic facts, and a symbolic engine reasons over the facts the network asserts. Examples include diagnosis engines fed by learned fault detectors, explanation engines over learned classifiers, and planners over learned hazard maps. The question is specific to this setting. When the neural component is trained and certified at the level of facts, does that guarantee transfer to the symbolic engine's answer? Decision sensitivity (Section 3) is exactly the exchange rate between fact-level and answer-level error. Theorem 1 shows it is bounded for aggregation and unbounded for optimization.

Why the result is not "argmax is discontinuous." See General response, item 1. Both query families now read the same thresholded input and are both discontinuous in x. They differ in whether one flipped fact has a bounded or unbounded effect.

Itemized definitions (all now in Section 3):

  • Candidate predicates: a finite vocabulary of Boolean facts, with examples per domain.
  • The scorer's setting: fθ : ℝⁿ → [0,1]^m, one confidence per fact.
  • τ: a per-predicate threshold. Yes, it is thresholding.
  • Aggregation and thresholding: aggregation is now analysed in both soft and hard (thresholded) forms. This resolves the asymmetry you noted.
  • Definition 1 versus argmax: Definition 1 now defines both the minimal-witness family and the single selected witness (the argmin of the introduction).
  • Ω, L, K, µ:
    • Ω is a finite set of candidate witnesses (e.g. sets of components);
    • µ(c, ω) = 1 means witness ω accounts for fact c;
    • the target family is simply the asserted set P;
    • L is removed as redundant notation.
  • Inclusion-minimal: no strict subset also accounts for every asserted fact.
  • Symmetric difference: A △ B is the set of elements in exactly one of A and B, and |A △ B| is its size. The ⋄ symbol is removed.
  • Motivation for decision sensitivity: added (see above).
  • Waypoints, margin, margin CDF, temperature: each is defined where it is introduced. H6 is reduced to a remark.
  • Remark 1 (message passing): moved to related work, as it was not part of the architecture.
  • The "intractability" pivot in the abstract: the abstract now introduces the complexity result before referring to tractability.
  • Instantiation 1 in symbols: U is the set of system components. Each asserted fact is a conflict C ⊆ U, meaning at least one component of C is faulty. µ(C, D) = 1 iff D ∩ C ≠ ∅. Ψ(P) is then the set of minimal diagnoses of Reiter (1987). The list of named diagnosis variants has been removed.

I want to thank the reviewers with engaging with my points. While explaining some points to me helps me understand the paper, other points were not addressed. I also do not see a revision, which I think is possible in the ICLR-reviewing process? The critique was less me personally understanding the paper but the poor quality of the submission. The points raised were also examples that illustrate the poor readability and not a "checklist" to explain in the rebuttal, as I was not satisfied with the quality of the writing and struggled to understand the paper (despite being familiar with neuro-symbolic approaches). I think the paper would immensely benefit from a careful reading and a major revision, while looking out for the underlying issues of the paper:

  • is every symbol, concept or name sufficiently defined and explained? This was a major issue during reading, a paper should be self-contained except background that can be assumed from the typical reader
  • is the underlying problem properly explained and motivated? What is the setting and why do we care about it? Here, an example would help to understand what the paper is talking about, instead of just starting with the formalization (which was unreadable, see the above point)
  • What is the role of each section, and does the content support its title?

I will not increase my score based on this response and i encourage the authors to contemplate improving the readability of the submission with a careful rewrite.

AuthorsOpenReview ↗

rewrite now uploaded

FYI, we have an updated draft uploaded, so we hope that this improves readability.

Reviewer_1VfUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper examines whether aggregation and optimization queries behave differently when applied to the same neurosymbolic representation. It argues that aggregation can be stable under bounded-gradient assumptions, while threshold-based optimization can produce large changes in its solutions after a small perturbation. A minimal hitting set example illustrates this possibility. The paper also studies how decision margins relate to instability and tests its ideas in diagnosis, abductive explanation, and route planning. Finally, it considers when structural restrictions or randomized restarts can make optimization more tractable.

Critical strengths
  1. The distinction between aggregation and optimization is useful, and the minimal hitting set example makes the possible instability concrete.
  2. The paper takes the analysis beyond one example, examining diagnosis, abductive explanation, and route planning. The discussion of margins and randomized restarts also gives the work practical direction.
Critical weaknesses
  1. I could not tell from the proof of Theorem 1(b) how the constructed output is kept within [0,1]m[0,1]^m. The paper should also state the norms and function domain. This may be a missing detail in the presentation rather than a problem with the result, but it needs clarification.
  2. The H1/H2 timing comparison is difficult to interpret as a comparison of query types alone. Aggregation evaluates route safety, while optimization searches for a route. The results are informative for this routing setup, but the paper should be careful about drawing a broader conclusion from them.
  3. The H5 and H6 experiments do not directly establish the theoretical bounds. For H5, LL is estimated from sampled input pairs rather than verified as a global bound. For H6, ECE is not the uniform calibration error assumed by Theorem 4. The paper acknowledges these limitations, so the claims should be framed accordingly.
  4. The link between Theorem 2, H4, and the randomized-restart experiment hard to follow. It is not clear which part of the theorem the experiment is meant to support.
Questions for authors
  1. Could the authors clarify how the construction in Theorem 1(b) keeps the output within [0,1]m[0,1]^m, and specify the norms and function domain?
  2. What exactly is timed in the H1/H2 comparison? Does aggregation evaluate a supplied route while optimization searches over routes?
  3. How should readers interpret the H5 and H6 results, given that the empirical LL is not a certified global bound and ECE is not the error bound used in Theorem 4?
  4. Which claim in Theorem 2 or H4 is tested by the randomized-restart experiment?
3 comments

Response to Reviewer 1VfU

Thank you for the precise questions; each has led to a concrete change.

Q1: range [0,1], norms, domain. The domain is ℝⁿ with the ℓ₂ norm, and belief vectors use the ℓ₁ norm. This convention is now stated in Section 3. The construction in Theorem 1(c) now clips the active coordinate to [0,1]. Clipping is 1-Lipschitz, so the Lipschitz bound is unchanged. The perturbation size is chosen as η = min{ε, 2·min(τ, 1−τ)/L}, so both evaluation points stay strictly inside (0,1) and the clip never binds where the result is witnessed. The submitted unclipped affine map did leave [0,1] far from the origin. Thank you for catching this.

Q2: what is timed in H1/H2. You are right. Aggregation evaluated the safety of one supplied route, while optimization searched over waypoint orderings (Held–Karp). The comparison measures evaluation versus search for this routing problem. It is not a comparison of query types in general, and its 2^K growth is the cost of the underlying ordering problem, independent of the beliefs. We have moved it to the appendix and labelled it accordingly. The main-text query-type contrast now rests on Theorem 1, plus the known separation between marginal and MAP inference on sum-product networks, which compares the two query types on one representation. [TBD: if time allows, a matched marginal-vs-MAP timing on the same factored belief.]

Q3: interpreting H5 and H6.

  • H5 tests the inequality of Theorem 3 with a plug-in estimate L̂, not a certified bound. It supports the bound's form and monotonicity, not its constants. We now say so.
  • One more point we found while revising: the essential set was restricted to cells on the current route. An off-route cell becoming free can also change the optimum, so the measured margin can overstate the true minimum essential margin. [TBD: rerun with the full essential set, or state this as a limitation.]
  • H6: ECE is not the uniform δ of Theorem 4, and the experiment is underpowered. We have reduced it to a remark.

Q4: which part of Theorem 2 the restart experiment tests. Part 2 only: the amplification bound R ≥ ln(1/γ)/p. The K = 14 miss illustrates that p depends on the instance. The structural route (part 1) is not tested empirically; it is a theoretical statement only. Section 4 now says this explicitly.

Reviewer_1VfUOpenReview ↗

Response

Thank you for the detailed response. The revised construction resolves my concern about the output range in Theorem 1. I agree that the routing timings are informative when interpreted as a comparison between evaluating a given route and searching for one. Your explanation of the restart experiment answers my question about H4, and treating H6 as exploratory is appropriate.

H5 remains the main issue for me. A cell outside the current route can change which route is optimal, so restricting the analysis to the current route may miss the smallest relevant margin. The Lipschitz constant is also estimated from samples. The reported frequencies are consistent with the proposed bound, but they give me limited confidence in how informative that bound is in practice.

The response clarifies several points without substantially changing my overall assessment. I do see a case for acceptance on the strength of the minimal hitting set construction.

AuthorsOpenReview ↗

clarification on question about H5

Response to Reviewer 1VfU

Thank you for the follow-up question, and for seeing a case for acceptance on the strength of the minimal hitting set construction. In the following we address your primary issues regarding H5, and hope that this new information provides more reasons for acceptance beyond just the minimal hitting set results.

We agree that H5 needed more than a sampled check, and we have strengthened it as follows. The updated PDF revises Section 7.3, Figure 2 and Table 4; the code is in the supplementary material of the revised submission. We have run additional experiments in order to clarify your issue with H5, and we provide more material as follows.

1. Cells off the current route. You are indeed correct that these can change which route is optimal. The revised H5 uses the exact essential set: we flip every cell in turn, including off-route cells, and test each flip with Held–Karp. This matters in practice. An off-route cell sets the minimum essential margin in 1,420 of the 3,000 states. In the submitted analysis, about half of the instability events could only be explained by off-route cells (25 of 50 at ε = 0.1). With the exact set, all 120 events satisfy M(x) ≤ L̂ε.

2. The sampled Lipschitz constant. We now provide material that provides a clear certified bound that uses no Lipschitz constant. The hazard network is small (6–16–8–1, ReLU), so interval bound propagation gives a sound interval for every cell's belief under every admissible perturbation of size ε. A state is certified stable if no combination of the cells whose interval crosses the threshold changes the optimal route; we check this exactly. To show how tight the certificate is, we also run projected-gradient attacks. Each success is a verified perturbation that changes the route, so the attack rate is a lower bound on worst-case instability.

εRandomAttack (lower bound)Margin-CDF plug-inCertified (upper bound)
0.0050.00030.0190.0210.049
0.010.00170.0300.0380.098
0.020.00700.0590.0750.181
0.050.01430.1460.1780.402
0.100.01670.2710.3170.620

Across all 15,000 state–radius pairs, no state that was destabilized, by a random perturbation or by an attack, was certified stable.

3. How informative the bound is. Theorem 3 bounds instability against any perturbation of size ε, including a worst-case one. The submitted version compared it with random-direction perturbations, which are 20–70× weaker than the worst case. That comparison made the bound look loose by 10–70×. Against worst-case instability, the margin-CDF prediction lies inside the certified bracket at every ε, within 1.1–1.3× of the verified attack rate. So it is a close estimate of how often a worst-case ε-perturbation changes the optimal route.

The plug-in itself still uses the sampled L̂ and is not certified; the certified bound is 2.3–3.3× above the attack rate. Without any Lipschitz estimate, 95% of states are certified stable at ε = 0.005, and 82% at ε = 0.02. This also illustrates Section 8's design point 3, certified abstention: the margin certifies most states and abstains only near the threshold.

We hope this addresses your remaining concern about H5. We have tried to directly address your questions and to revise the draft based on these questions.

Reviewer_5gDpOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies neuro-symbolic inference from the angle of what kind of query is asked over the same learned representation: aggregation (e.g. expected safety along a route, Fagg(p)=∑iwipiF_{\mathrm{agg}}(p) = \sum_i w_i p_i) versus optimization (selecting a minimal witness set, Ψ(τ(fθ(x)))\Psi(\tau(f_\theta(x)))).

The authors show that aggregation is provably Lipschitz-stable under belief perturbations, while optimization can change arbitrarily: for any LL, ε\varepsilon, and M′M' they construct an LL-Lipschitz scorer whose ε\varepsilon-perturbation changes the witness set by at least M′M'.

The sharpest part is the construction behind this: for minimal-cover operators, flipping a single predicate can change the family of minimal witnesses by 3⋅2k3 \cdot 2^{k}, so the decision sensitivity is infinite and no constant can convert predicate-level error into solution-level error.

They then turn the worst case into a frequency statement, bounding the instability probability by the CDF of the minimum "essential margin" at LεL\varepsilon (plus calibration error δ\delta), and test six hypotheses on a grid-world hazard predictor, with diagnosis and abductive explanation validated on ISCAS-85 circuits in the appendix.

Critical strengths
  • Clean Theoretical Contribution: The impossibility result is the main contribution and is very clean. Theorem 5 shows that adding one conflict changes the minimal-cover family by 3⋅2k3 \cdot 2^{k} (dP=1d_P = 1, dΔ=2k+2k+1d_\Delta = 2^{k} + 2^{k+1}), and Corollary 5 turns it into a clear takeaway for practitioners: no bound on predicate-level error, however tight, guarantees a bound on solution-level error. The minimal construction is transparent, verifiable by brute force at small kk, and practical because systems reporting witness lists can completely swap output families under minimal input variations.
  • Exemplary Reporting Discipline: I want to explicitly praise the paper's reporting discipline, which is well above the conference average. The authors voluntarily disclose that NN was reduced from 10,000 to 3,000, that positive H3 cases required engineered near-threshold beliefs, that the heuristic misses at K=14K = 14, that a SAT solver outperforms their search by orders of magnitude on c432 (Table 2), and that the H6 correlation is not statistically significant (r=0.393r = 0.393, p=0.441p = 0.441). This level of transparency substantially increases confidence in the empirical findings.
Critical weaknesses
  • Continuous vs. Thresholded Instability: The core mathematical source of instability in Theorem 1(b) arises from τ\tau, a hard per-candidate threshold step. Because any hard threshold composed with a continuous scorer introduces step-discontinuities, the instability is primarily a property of hard-thresholded discrete inference rather than optimization queries in general (e.g., soft or randomized optimization variants with smoothed selection could preserve Lipschitz stability). Clarifying that this instability specifically targets thresholded discrete queries would make the paper's main theoretical claim more precise.
  • Domain Application vs. Mathematical Generality: Instantiation 1 (model-based diagnosis) and Instantiation 2 (abductive explanation) both rely on the minimal hitting set problem (as explicitly connected by the AXp/CXp duality in Corollary 3). While demonstrating this instability across two different subfields is practically useful, structurally they represent the same combinatorial operator. Additionally, for the routing instantiation, single-flip unbounded sensitivity is not formally established (Section 5.1.2). The paper should clarify that these domains illustrate different practical applications of the same core combinatorial instability, rather than three structurally independent mathematical representations. Furthermore, Section 4's claim that H1–H3 follow from Theorem 1 overstates the theoretical linkage, as stability guarantees do not directly imply computational complexity separations.
  • Empirical Nuances: While the experimental setup is sound, a few empirical limitations warrant discussion. First, positive H3 cases rely on hand-built near-threshold beliefs, and the naturalistic pilot observed 0/400/40 positive crossings, indicating that while the mechanism can fire, its natural occurrence rate may be low. Second, because estimating exact global Lipschitz constants is intractable and reliance on finite-difference estimates is standard, the empirical bounds derived using L≈0.403L \approx 0.403 should be contextualized as local approximations rather than strict analytical upper bounds. Finally, H6 lacks sufficient statistical power under the current sample size (N=800N = 800 per temperature with 1–2% event rates), and the trade-offs of Algorithm 1 versus optimized SAT solvers (Glucose3) in Table 2 would benefit from further discussion regarding non-shortcut regimes.
Questions for authors
  1. Practical Design Implications: What does this result imply for system design? As the paper presents primarily a negative result, it would be valuable for the authors to elaborate on the design trade-offs available to practitioners. Specifically, how do the authors view the trade-offs between staying on the continuous/aggregation side, retaining discrete queries with abstention contracts (Proposition 6), or utilizing the minimum-essential-margin distribution as an evaluation metric? A brief discussion on what current theory supports versus what remains open would significantly enhance the paper's practical impact.
  2. Connection to Abductive Learning (ABL): How does this theory extend to framework-level paradigms like Abductive Learning (ABL)? In ABL, abduction candidate selection (selecting the single most consistent/probable explanation) involves a hard selection step over candidates, whereas weighting multiple explanations mirrors aggregation. It would be valuable to hear the authors' perspective on:
    • Whether hard selection operators in ABL fall directly under Definition 3 or closer to the routing instantiation;
    • Whether Theorem 3's margin prediction holds in ABL settings where candidate consistency score margins dominate over individual predicate probabilities;
    • Whether aggregation with bounded weights (e.g., ambiguity-aware ABL as in He et al., ICML 2024) formally sits on the stable side of Theorem 1(a). A discussion connecting the current stability bounds to these ABL selection regimes would strengthen the broader context of the work.
4 comments

Response to Reviewer 5gDp

Thank you for the detailed and constructive review, and for the comments on reporting discipline.

Thresholded versus optimization instability. You are right, and the revision builds on this point (see General response, item 1). We also answer the follow-up: soft or randomized selection does preserve stability. New Proposition (Smoothed optimization is stable) shows that Gaussian smoothing of any hard query makes the distribution over outputs Lipschitz in total variation, with constant 1/(σ√(2π)). This holds independently of Ψ, of τ, and of the Lipschitz constant of the scorer. The mechanism confirms the paper's thesis: smoothing turns the optimization output into an expectation, i.e. an aggregation. A new remark notes the limit. Committing to the single most probable witness under the smoothed distribution re-introduces a threshold. The remedy is certified abstention (Proposition 6 of the submission).

Same operator, different domains. Agreed and revised (Section 5.2): one operator class with two application domains, plus routing, which is outside the class and for which single-flip unbounded sensitivity remains open.

H1–H3 and Theorem 1. Agreed and retracted. H1/H2 are timing claims and do not follow from a stability theorem. They are moved to the appendix and reframed (see the H1/H2 answer to Reviewer 1VfU).

Empirical nuances.

  • Engineered near-threshold beliefs for H3. We state this explicitly in the main text. We describe the natural crossing rate as an open question rather than suggesting it is common.
  • Empirical L̂. All bounds that use L̂ are now described as local, finite-difference estimates, not certified global constants.
  • H6. Reduced to a remark. With N = 800 per temperature and 1–2% event rates, it has too little statistical power to test Theorem 4.
  • Algorithm 1 versus Glucose3. The discussion now says plainly that SAT wins whenever the monotonicity shortcut exists (Proposition 3). Algorithm 1 is justified only in regimes with no known shortcut.

Design implications. A new remark now sets out three design points, each backed by a result:

  1. report aggregates (soft-aggregation Lemma and Theorem 1(a));
  2. report a smoothed distribution over witnesses (smoothing Proposition);
  3. commit to a witness with certified abstention (Proposition 6 of the submission, the abstention contract). The expected abstention rate is the margin CDF of Theorem 3.

Open: whether margin-aware training can shift the margin distribution enough to make option 3 cheap in practice.

Abductive Learning (ABL).

  • Hard abduction selection (committing to the single most consistent candidate) is a selected witness in the sense of Definition 1(2). the Selected-witness Proposition therefore applies whenever the candidate space has hitting-set structure. Where it does not, the situation is like our routing instantiation: the margin mechanism applies, and unbounded sensitivity must be established case by case.
  • Theorem 3 in ABL. The proof uses only that the output changes through a threshold crossing within distance Lε. It therefore holds with "predicates" replaced by candidate consistency scores, as long as the essential set and margins are defined on those scores.
  • Ambiguity-aware ABL (He et al., ICML 2024). Bounded weighting over a fixed candidate set is on the stable side, by the soft-aggregation Lemma. If the candidate set is itself produced by a hard selection step, its support can jump. The weighted output is then stable only in the smoothed sense of the smoothing Proposition.

We have added this discussion to the related work.

Thank you for your detailed response. It appears that the revised manuscript has not yet been uploaded, as I can still only see the original version. I will reconsider my assessment once the revised manuscript is available, so that I can evaluate the changes in context.

AuthorsOpenReview ↗

uploads now present

FYI, I have now uploaded my revised pdf and Supplementary materials.

Thank you for taking the time to revise the paper and for your thoughtful responses. I appreciate the care you have put into addressing the reviews. The revised manuscript addresses most of my concerns, so I am happy to raise my score by one point.

I do think the paper could still benefit from further work on its readability, and I encourage the authors to keep refining the presentation.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.