acceptodds
Under review as a conference paper at ICLR 2027

Consistency-Driven Neuro-Symbolic SAT Ensemble

Abstract

Neural networks have recently emerged as a third paradigm for Boolean satisfiability (SAT) solving, alongside complete and stochastic local-search solvers, with independently trained models offering complementary predictions on the same formula, yet frequently disagreeing on the assignments they produce. To date, no ensemble method has been developed for aggregating the outputs of multiple neural SAT solvers, and a naive application of classical ensemble techniques would only reduce this disagreement to scalar per-variable metrics such as vote counts, discarding the relational structure between variables that is essential for constructing a consistent satisfying assignment. We present cdNSE, a new consistency-driven ensemble method for neuro-symbolic SAT solvers. We develop a mathematical framework to characterize consistency among solver outputs, capturing both agreement on variable assignments and on relationships between variables. These equivalence relations allow us to group variables where the ensemble shows consistent voting, which significantly reduces the search space for local search. We benchmark cdNSE against eleven fusion-based and ten learning-based methods on instances from six SATLIB datasets. cdNSE improves the solve rate by a relative improvement of over the strongest baseline and requires fewer flips to find a solution. When we increase the flip-budget for the local search engine, cdNSE achieves a solve rate, compared to for the strongest baseline method.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Neurosymbolic, SAT solvers, Ensemble Learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_PMX7OpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes an ensemble method for combining assignments from different ML-based SAT solvers. Traditional ensemble methods combine outputs for each variable separately, which for SAT would often lead to a worse assignment violating many clauses. To preserve consistency, the proposed ensemble method considers relationships between variables. The proposed algorithm starts from an assignment derived with a quality-weighted voting rule (independent for each variable) or a low-energy assignment given by one of the agents. Local search is run to repair the assignment iteratively. Variables for which the individual agents are confident are protected softly.

When local search does not improve with single bit flips, whole blocks of variables are flipped simultaneously. The proposed mathematical framework guides how those blocks are selected. Specifically, initial agent predictions are used to group variables into Heider blocks. For two variables u,vu,v in the same block, all agents either agree that u=vu=v or u≠vu\neq v. This guides larger flips in local search: variables in the same Heider block are all flipped simultaneously. Intuitively, this is because the agents agree that if uu is flipped, then vv should be flipped as well.

The paper evaluates the method on SAT formulas from SATLIB. As baselines, they use each individual solver, the solvers + a local search, a set of fixed fusion rules, and learning based ensemble methods. The proposed method achieves the highest solve rate, and the lowest PAR-10 score which suggests more reliable performance under the fixed search budget.

Critical strengths
  • The problem setting is interesting. Ensemble methods are widely used in supervised learning. Combinatorial problems pose a unique challenge for ensemble methods: naively combining different solutions does not necessarily work well because of dependencies between the variables.
  • The proposed mathematical framework for modeling dependencies between variables is elegant.
  • The algorithm uses information from the agents to guide search softly, rather than treating some variables or blocks as fixed.
  • The baselines are extensively evaluated. Per-model class reports the strongest individual agent after post-hoc local search, which is important to control for the effect of running local search on top of the agent solutions.
  • The relevant mathematical definitions are explained reasonably well with illustrative examples.
Critical weaknesses

W1: The paper is easy to follow until Algorithm 1. I needed substantial time to go through it, and I feel like many parts there were not explained in the text or sometimes completely undefined. The individual comments are mostly minor, but together they reduce clarity significantly

  • The pseudocode assumes familiarity with the local search framework on which it builds. It would be helpful to give a short high level overview to help understand the overall search procedure.
  • cw is never defined verbally (I'm guessing it is clause weights). Since w and c already stand for other things, using cw can be confusing
  • Similarly, u is never verbally defined.
  • Algorithm 1 calls a clause weighted local search algorithm (WLS) but it is never explained what the input parameters of this algorithm stand for. cw is not updated in the pseudocode. Does WLS update it?
  • "level A" is not defined
  • Is "no improvement" measured after a single WLS call or globally? stall is also not initialized

W2: The blocks are based on exact agreement between agents. A single bad agent can mess up the block structure by preventing variables being placed in the same block. Moreover, the bound on the number of blocks grows exponentially in the number of agents

Questions for authors

Q1: What is meant by "The equivalence relation (∼v,∼r)(\sim_v,\sim_r) on V\mathcal{V}"? The first is a relation on agents whereas the second one is on variables, so it is not clear what this notation means. Are the Heider blocks just the equivalence classes of ∼r\sim_r?

Q2: How often does Algorithm 1, line 2 go with best energy solution vs. the consensus solution?

Q3: The paper proposes this as an ensemble method for ML-based solvers. It seems like the proposed framework could combine assignments from incomplete classic solvers too. Is there a reason this is not considered?

Q4: How often are block flips actually happening? It would also be relevant to compare with randomly selected blocks to determine how much the Heider blocks help.

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

This paper presents a technique for producing new neural SAT solvers via ensembling existing neural SAT solvers. The basic idea is to establish a two level consistency relationship between two solutions for one SAT problem. The ensembled solver can be further used to reduce search space in local search solvers. This paper also reports an empirical evaluation of the proposed approach.

Critical strengths
  • The idea of ensembling multiple neural SAT solvers is novel to me.
  • The two-level consistency between SAT solutions is interesting.
Critical weaknesses
  • It is unclear whether the proposed ensemble approach can lead to a stronger SAT solver. Typically, when we ensemble multiple solvers into one ensembled solver, we expect the ensembled solver to be stronger than each individual solver before ensembling. However, this paper does not provide any concrete evidence on this issue.
  • There is lack of strong baselines in the empirical evaluation. This paper lists quite a few neural SAT solver, but adopts none of them as baselines in the empirical evaluation. So, it is unclear whether this paper has push the frontier forward.
  • As standalone neural SAT solvers may not be strong enough compared with traditional solvers (such as local-search solvers and CDCL solvers), it is common to integrate a neural SAT solver in an existing solver. This paper claims that the proposed ensembled solver can boost local search-based solvers, but provides no concrete evidence that a local search can solve more SAT instances or solve SAT instances faster by integrating the proposed solver.
Questions for authors

Q1: What exact solvers are ensembled in the empirical evaluation? Is the ensembled solver clearly stronger than each individual solver? Q2: If compared with the SOTA neural SAT solvers, is the ensembled solver clearly stronger? Q3: Can the proposed ensembled solver boost an existing local searh solver in terms of solving more SAT instances or reducing the solving time?

3 comments

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.

After reading the response, I think I would not change my score. The authors do provide some evidence in favor of the proposed SAT solver, but the evidence is based on only some internal measurement of neural SAT solvers. The crucial point is that if the proposed ensembling method cannot lead to a stronger SAT solver, how we could deem this ensembling method as a beneficial one. After saying that, I still think this paper is in a correct direction, and it only lacks more decisive evidence.

AuthorsOpenReview ↗

Responses for Follow-up Comments

Thank you for your follow-up comments. We address your questions below.

Q2.1. Does the proposed ensembling method lead to a stronger SAT solver?

Yes. Our results demonstrate that ensembling neural SAT solvers leads to a substantial improvement in solving performance. The strongest baseline achieves a solve rate of only 11.4% on the test instances without ensembling. Applying post-hoc local search increases the solve rate to 60.9%, while our proposed cdNSE further improves it to 69.5%. These results demonstrate the effectiveness of cdNSE in improving the solving performance of neural SAT solvers. Please see Table 2, page 9.

Q2.2. Internal measurement of neural SAT solvers

We have explicitly reported the training and test datasets in Section 4.1.1 and clarified that the implementations are adopted from the original works. We are also happy to release the trained model weights to facilitate reproducibility and further evaluation.

We appreciate your recognition of the potential of the cdNSE approach. We hope that these additional explanations and clarifications adequately address your concerns.

Reviewer_fuwYOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes CDNSE, a consistency-driven neuro-symbolic ensemble framework for Boolean satisfiability (SAT) solving. The key idea is to exploit two levels of agreement among neural SAT solvers: agreement on individual variable assignments and agreement on pairwise relationships between variables. Based on these consistency relations, the method partitions variables into blocks and incorporates block flipping into a local-search procedure to improve solving efficiency. Experiments on six SATLIB datasets demonstrate improvements in solve rate and search efficiency over several fusion-based and learning-based baselines.

Critical strengths
  • The paper investigates an interesting and relatively underexplored problem of combining predictions from multiple neural SAT solvers, moving beyond conventional variable-wise ensemble aggregation.
  • The proposed relational consistency formulation provides an intuitive way to capture structural dependencies among variable assignments and incorporate them into local search.
Critical weaknesses
  • In Section 3.2.2, the authors argue that agreement on individual variable values is not necessarily beneficial, since multiple agents may unanimously predict an incorrect value. They further motivate relational agreement by observing that agents may disagree on the values assigned to variables u and v while agreeing on how these variables relate. While this observation is reasonable, the underlying argument is not entirely convincing. In particular, relational agreement can also be incorrect, even when all agents agree on the relationship between two variables. It is therefore unclear why agreement on variable relationships should be inherently more reliable or beneficial than agreement on individual values. More importantly, the paper does not establish under what conditions relational agreement provides additional useful information for SAT solving. Although relational agreement preserves information about correlated predictions that may be lost through variable-wise aggregation, retaining more structural information does not necessarily imply that this information is more accurate or useful for finding satisfying assignments.
  • The paper presents two theoretical results: Theorem 1 establishes that the proposed relational agreement is an equivalence relation, while Theorem 2 provides an upper bound on the number of resulting blocks. Although these results formalize certain structural properties of the proposed framework, their implications for SAT-solving effectiveness remain unclear. First, Theorem 1 primarily establishes a mathematical property of the defined relation. However, being an equivalence relation does not necessarily imply that the resulting variable groups are meaningful for optimization or that flipping these groups is more likely to improve a candidate assignment. Second, Theorem 2 establishes that the number of blocks is bounded by min(n, 2^(M−1)). While this bound limits the number of available block-flipping moves for a fixed number of agents, it does not establish that the resulting moves are more effective than conventional variable flips or alternative grouping strategies. In particular, reducing the number of candidate moves does not necessarily translate into improved search efficiency, since the quality of the induced search neighborhood is equally important. The paper would benefit from a stronger connection between these theoretical properties and the effectiveness improvements.
  • The discussion in Section 5 reports that setting the consensus-prior strength λ = 0 still leads to performance that exceeds the strongest fusion-based and learning-based baselines. The authors also observe that substantially reducing the initial energy through consensus-based initialization does not produce a statistically distinguishable improvement in solve rate compared with random initialization, although it improves search efficiency. These observations are interesting, but they raise questions about the relative importance of the different components of CDNSE. In particular, they suggest that some mechanisms based on value agreement may not be essential to the observed improvements. While the results are consistent with the possibility that relational block flipping is the primary source of improvement, the current evidence does not conclusively isolate this effect from other aspects of the overall search procedure.
  • Although the paper compares against several methods, many of the ensemble strategies are adaptations of classical techniques, including bagging, boosting, random subspaces, and Bayesian model averaging. Classical ensemble aggregation methods are not necessarily designed to exploit structural dependencies among SAT variables, and therefore may not provide the most informative comparison for the proposed approach. Furthermore, the paper does not sufficiently establish how CDNSE compares with more recent neural SAT-solving approaches or stronger structure-aware local-search techniques.
Questions for authors
  • What theoretical or empirical evidence supports the claim that relational agreement is more useful than value agreement?
  • Beyond establishing the mathematical validity of the proposed equivalence relation and bounding the number of blocks, what do Theorems 1 and 2 imply about the effectiveness of the resulting search strategy?
  • Given that λ = 0 still achieves competitive performance, which specific components of CDNSE account for the observed gains? Can the authors further isolate the benefits of relational block flipping from those of the underlying local-search procedure?
  • Can the authors include stronger and more recent neural SAT or structure-aware local-search baselines to establish the competitiveness of the proposed method?
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.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.