acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Confidence Neural Logic Machines

Abstract

Quantum annealing offers a promising approach to Boolean satisfiability (SAT); however, existing encodings frequently require large numbers of qubits and produce energy landscapes with narrow spectral gaps, increasing susceptibility to spurious minima. This work introduces Adaptive Confidence Neural Logic Machines (AdaptCNLM), a neural-symbolic framework designed to jointly reduce the representation size of SAT instances and enhance the resulting optimization landscape. AdaptCNLM initially employs neural structural-equivalence encoding (NSEE), a label-free graph neural network that identifies and aggregates structurally equivalent variables while provably preserving satisfying assignments within the induced subcube. Subsequently, dual-confidence scaling is applied, integrating structural and search-derived signals to recover information lost during aggregation and to guide the search toward satisfying assignments. Across five quantum-annealing encodings, NSEE significantly reduces qubit requirements and achieves the highest solve rate with fewer logical qubits. As a complete SAT solver, AdaptCNLM surpasses 16 data-driven and non-data-driven baselines across six SATLIB benchmark families. These findings indicate that learned structural compression, combined with confidence-guided search, enhances both resource efficiency and solving performance in quantum-annealing-based SAT.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
SAT solver, Graph Neural Network, Quantum optimisation

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_2RjxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes AdaptCNLM, a SAT model-finding framework that combines variable aggregation with adaptive clause weighting. A variable-clause GNN supplies grouping information; tying variables reduces the Boolean search space, simplifies clauses, and lowers the size of a subsequent QUBO. The deployed pipeline additionally builds a pool through confidence-weighted WalkSAT, fixes variables that agree across the sampled pool, performs affinity-filtered greedy merges, and selects reduced models using projected-pool violation counts. Static clause difficulty weights, dynamic increases for currently violated clauses, probabilistic smoothing, and a global energy scale guide subsequent search.

Critical strengths
  1. A clear and useful characterization of lossy restriction. Theorem 1 then establishes exact weighted-objective agreement at every lifted assignment and a bijection to the original solutions that lie in the restricted image. Theorem 2 gives a simple, explicit first-moment warning about overly aggressive instance-independent compression. These results do not guarantee the learned grouping succeeds, but they provide an appropriate mathematical foundation and make the loss of feasible assignments visible instead of hiding it. This is a substantive positive for a heuristic compression method.

  2. Promising measured resource savings with useful budget transparency. Table 1 reports materially smaller logical and embedded models alongside improved verified success under the same simulated-annealing sampler. The SATLIB comparison covers multiple families and includes strong classical local-search references as well as learned methods. These details make the result more credible as an end-to-end empirical observation, even though component attribution remains unresolved.

Critical weaknesses
  1. The learned-compression contribution is not isolated, and the QUBO construction is under-specified. The appendix relies on extensive classical preprocessing and model construction, including variable fixing and certificate-based selection, so the ablation cannot show whether the neural component drives the gains. A direct control would compare the no-network setting and random affinities while holding the pool, fixing, guard, gadget, and time budget identical. Successes from pre-annealing certificates should also be separated from new solutions found by the sampler, and the ancilla-count, penalty, and certificate-acceptance details need explicit definition.

  2. The evidence does not yet justify the claimed additional confidence or general solver benefits. The ablation’s marginal contrast is small, and the reported uncertainty concerns the full method versus the baseline rather than that contrast; repeated runs with paired uncertainty are needed. The dynamic weighting also needs sharper positioning against prior precedent and a closely related control, since reweighting cannot recover assignments excluded by aggregation. The quantum interpretation remains conditional: the theorem assumes a WKB-style rate law and common prefactor, so it does not establish applicability to the reported QUBOs or the plotted gap scaling without further validation or a narrower claim.

Questions for authors
  1. With the same elite pool, empirical fixings, merge procedure, compact gadget, and total time budget, how do the trained affinities compare with rho=1 and random affinities at rho=0.6? Please also report how many instances already have a verified solution during pool/certificate construction, and the sampler's additional success on the unresolved cases. A clear advantage here would materially strengthen the central neural-compression claim.

  2. What are the exact compact-gadget polynomial, t(kappa), sufficient penalty weights, simplification rules, and candidate-merge acceptance conditions? Does the guard constrain cert(g), and how are harmful empirical fixings or failed reduced models handled? Explicit pseudocode and the precise represented objective would resolve the present gap between the CNF theorem and the deployed solver.

  3. Can you provide per-instance, repeated-seed results for A+B+ versus A+B-, separating static weighting, dynamic weighting, and the global scale/effective-temperature schedule, together with a closely related dynamic-weighting baseline? Please give paired uncertainty for both this marginal effect and the reported 105-versus-102 SATLIB comparison. This would determine whether the second component and overall classical advantage are reliable.

  4. For which explicit driver, problem Hamiltonian, and annealing schedule does Fig.4's minimum-gap scaling hold, and what evidence supports using the assumed WKB law for the proposed QUBOs? A derivation or small exact spectral calculation would help; alternatively, would you limit these statements to an illustrative conditional model and state the demonstrated contribution in terms of classical search and encoding resources?

1 comment

Once again, we sincerely thank you for your valuable comments. We hope that our responses have adequately addressed all of your concerns. We would be happy to address any further questions or provide additional clarification regarding the novelty and contributions of our work.

Reviewer_CAE5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary
  1. Large reduction in qubit requirements. The reported numbers are large. At n=40n = 40, NSEE needs 44 physical qubits versus 589 for the best baseline encoding. At n=140n = 140 it still embeds (408 qubits), while none of the baselines finds an embedding within the time budget.

    Using minor embedding on Pegasus is a good choice, because it measures the actual hardware cost instead of just counting variables. Qubit count and embeddability are the main limits of current annealers, so this would be practically important. The attribution issues I raise below do apply to these numbers, though.

Critical strengths
  1. Large reduction in qubit requirements. The reported numbers are large. At n=40n = 40, NSEE needs 44 physical qubits versus 589 for the best baseline encoding. At n=140n = 140 it still embeds (408 qubits), while none of the baselines finds an embedding within the time budget.

    Using minor embedding on Pegasus is a good choice, because it measures the actual hardware cost instead of just counting variables. Qubit count and embeddability are the main limits of current annealers, so this would be practically important. The attribution issues I raise below do apply to these numbers, though.

Critical weaknesses

1. It is unclear how much of the improvement comes from the neural component (the GNN), and the encoding comparison is not like-for-like.

Appendix A describes a large classical pipeline around the GNN. Before the GNN runs, WalkSAT builds an elite pool of 48 assignments from 12×4000=48,00012 \times 4000 = 48,000 flips. Variables that are constant across the pool are then fixed, which removes 20–47% of the variables (Appendix C).

The GNN itself plays a limited role:

  • It is optimized for only 10 Adam steps at learning rate 10−310^{-3} from random initialization (Table 3), so its parameters likely stay close to their initial values.

  • It mainly decides which candidate pairs are allowed to merge (the top 60%). The actual merges are made by a guarded procedure checked against the pool.

  • Its training objective is only a balance term plus an entropy term, with nothing that measures whether solutions are preserved.

Because of this, I cannot tell how much of the result comes from learning rather than from WalkSAT and the classical heuristics. The paper is missing the ablations that would show this: ρ=1\rho = 1 (which the authors themselves say removes the network's influence), random pair ranking, and no backbone fixing.

The same problem affects Table 1. The five baseline encodings receive none of this preprocessing. Wall-clock time is matched (Appendix C), but the baselines are run as raw encodings while NSEE works on a problem that WalkSAT has already partly solved. If the pool already contains a satisfying assignment, the annealing step adds little. For a fair comparison, the baselines should get the same backbone fixing, or WalkSAT alone should be reported at the same budget.

This matters because the title and abstract rest on "learned structural compression," and the current experiments do not show it.

2. The effectiveness and quantum relevance of dual-confidence scaling are not demonstrated.

In the ablation, NSEE alone improves the solve rate by 0.472, and the full method by 0.486. That difference is about one instance out of 72. Dual-confidence scaling on its own (A-B+) gives no measurable improvement. There is no ablation table and no significance test.

The dynamic clause weighting is very close to existing local search methods (additive weight bumps as in PAWS, probabilistic smoothing as in SAPS), which are not cited. The global confidence ε\varepsilon multiplies ΔE\Delta E in the Metropolis rule, so it is mathematically the same as changing the temperature to T/εT/\varepsilon.

On the quantum side, all solve rates come from a classical simulated annealer, not from hardware. The tunneling result (Theorem 4) uses a one-dimensional WKB estimate for a many-qubit system. The paper's own Fig. 4c shows the spectral gap scaling as about ε\sqrt{\varepsilon}, so lowering ε\varepsilon makes the gap smaller, which goes against the motivation in the introduction. The stagnation-based ε\varepsilon schedule also needs to watch the search state, which is not possible during a single anneal.

Smaller issues that also lowered my confidence:

  • The text says 120 instances for the encoding study, but its own setup gives 5×12=605 \times 12 = 60.
  • At n=100n = 100 the text says the alternatives need "at least 616" logical qubits, while two baselines use 516.
  • n=200n = 200 is in the experimental design but missing from Table 1.
Questions for authors

Questions For Authors

  1. (Requested experiment) Could you report results with ρ=1\rho = 1, with random candidate-pair ranking, with pairs ranked by how often two variables agree in the elite pool, and with backbone fixing disabled, keeping everything else the same? This would show what the GNN actually adds.

  2. (Clarification) For what fraction of the instances in Table 1 and Table 2 does the WalkSAT elite pool already contain a satisfying assignment (cert = 0) before annealing? How much of the qubit reduction comes from backbone fixing alone, before any grouping?

  3. (Requested experiment) How do the baseline encodings perform if they get the same pool-based backbone fixing? And how does WalkSAT alone perform on these instances with the same total time budget?

  4. (Clarification) The loss in Eq. (4) only pushes groups to be balanced and assignments to be decisive. How does minimizing it lead to groupings that preserve satisfying assignments? Why should good groups have equal size? Did you try an objective tied to the reduced formula, for example a relaxed count of violated clauses in φA\varphi_A?

  5. (Clarification) What is the exact acceptance condition in guarded ascent? As written in Appendix A, the feasibility certificate does not seem to be part of the condition for accepting a merge.

  6. (Requested experiment) Could you provide the full ablation table, with results over multiple random seeds and a significance test for A+B+ versus A+B-?

  7. (Clarification) How does NSEE relate to earlier work that shrinks problems before solving? This includes multilevel coarsening for SAT/MaxSAT and for QUBO on quantum hardware, QUBO preprocessing that fixes variables in advance (Lewis & Glover), equivalent-literal substitution in SAT solvers, and neural backbone prediction (NeuroBack). Could you compare against at least one of these?

1 comment

Once again, we sincerely thank you for your valuable comments and requested experiments. We hope that our responses have adequately addressed all of your concerns. We would be happy to address any further questions or provide additional clarification regarding the novelty and contributions of our work.

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

The paper proposes Adaptive Confidence Neural Logic Machines (AdaptCNLM), a framework combining GNN-guided variable aggregation with adaptive clause weighting and global energy scaling for SAT solving. Its implementation uses local-search candidates, empirical variable fixing, and greedy merging to construct smaller CNF/QUBO models. The theoretical analysis establishes objective preservation within the restricted assignment space and characterizes limitations of instance-independent aggregation. Experiments using classical simulated annealing, hardware-graph embedding, and SATLIB benchmarks report reduced qubit requirements and a modest improvement in aggregate solve rate over the strongest evaluated baseline, WalkSAT.

Critical strengths

The reported reductions in logical and embedded qubit counts address a concrete resource bottleneck in SAT-to-QUBO encoding (Table 1). This offers potential value for resource-constrained annealing. Theorem 1 also establishes objective preservation within the restricted assignment space, while verification against the original CNF ensures that returned satisfying assignments are valid.

Critical weaknesses

1. The methodological contribution is unclear.

The framework combines several heuristics without isolating the GNN’s contribution. Eq. (4) rewards balanced, low-entropy partitions without distinguishing whether they preserve solutions. Global scaling simply adjusts the effective temperature in the classical kernel. The ablation tests the entire compression pipeline, omitting the otherwise-identical ρ=1\rho=1 baseline that removes the network.

2. The evaluation does not establish meaningful progress in SAT solving.

Table 2 gains only three instances over WalkSAT (105/123 versus 102/123), without repeated-seed evidence or comparisons with CaDiCaL or Kissat. Dual confidence adds approximately one instance out of 72. Moreover, cert⁡(g)=0\operatorname{cert}(g)=0 already identifies a solution before annealing, whose additional

Questions for authors

How many instances are first solved by the elite-pool search, certificate evaluation, and final annealer, respectively?

Do the gains over WalkSAT and NSEE alone persist across random seeds? How does the full pipeline compare with CaDiCaL or Kissat under the same total time budget?

2 comments

Once again, we sincerely thank you for your valuable comments. We hope that our responses have adequately addressed all of your concerns. We would be happy to address any further questions or provide additional clarification regarding the novelty and contributions of our work.

Thank you for the additional experiments. Qubit reduction can be valuable without outperforming classical SAT solvers. However, Table R1 shows the same 53/60 solves without the GNN, with fewer logical qubits at four of five sizes. Table R3 shows no new solves from annealing, and no clear advantage remains over WalkSAT with matched unit propagation. Even within the quantum-encoding scope, these results do not establish the claimed benefits of learned compression or the additional search components. I therefore maintain my rating of 2 (Weak rejection).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.