NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks
Authors: Wenxi Wang
Yang Hu
Mohit Tiwari
Sarfraz Khurshid
Kenneth McMillan
Risto Miikkulainen
Venue: ICLR 2024 poster (2024)
Keywords: Propositional satisfiability
Graph Neural Networks
CDCL SAT Solving
Backbone
Phase Prediction
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
TL;DR: The paper applies GNN to predict the backbone in an offline manner to obtain the phase information of important variables for improving CDCL solving.

Abstract: Propositional satisfiability (SAT) is an NP-complete problem that impacts many
research fields, such as planning, verification, and security. Mainstream modern
SAT solvers are based on the Conflict-Driven Clause Learning (CDCL) algorithm.
Recent work aimed to enhance CDCL SAT solvers using Graph Neural Networks
(GNNs). However, so far this approach either has not made solving more effective,
or required substantial GPU resources for frequent online model inferences. Aiming
to make GNN improvements practical, this paper proposes an approach called
NeuroBack, which builds on two insights: (1) predicting phases (i.e., values) of
variables appearing in the majority (or even all) of the satisfying assignments are
essential for CDCL SAT solving, and (2) it is sufficient to query the neural model
only once for the predictions before the SAT solving starts. Once trained, the
offline model inference allows NeuroBack to execute exclusively on the CPU,
removing its reliance on GPU resources. To train NeuroBack, a new dataset called
DataBack containing 120,286 data samples is created. Finally, NeuroBack is implemented
as an enhancement to a state-of-the-art SAT solver called Kissat. As a result,
it allowed Kissat to solve 5.2% more problems on the recent SAT competition
problem set, SATCOMP-2022. NeuroBack therefore shows how machine learning
can be harnessed to improve SAT solving in an effective and practical manner.

Published as a conference paper at ICLR 2024
NEUROBACK: IMPROVING CDCL SAT SOLVING USING GRAPH NEURAL NETWORKS
Wenxi Wang, Yang Hu, Mohit Tiwari, Sarfraz Khurshid, Ken McMillan, Risto Mikkuulainen The University of Texas at Austin Austin, TX 78712, USA
wenxiwêutexas. edu, huyangeutexas. http:euuttexs.eee.tteeeee edu, www.:tiwarriirm Caaaarr@uuuutii wtw.uuex.a.eee..e. thurshid@utexas. edu, kenmemê uttxas edu, ristolcs utexas edu
ABSTRACT
Propositional satisfiability (SAT) is an No-complete problem that impacts many research fields, such as planning, verification, and security. Mainstream modern SAT solvers are based on the Conflict-Driven Clause Learning (CDCL) algorithm. Recent work aimed to enhance CDCL SAT solvers using Graph Neural Networks (GNNs). However, so far this approach either has not made solving more effective, or required substantial GPU resources for frequent online model inferences. Aiming make GNN improvements practical, this paper proposes approach called NeuroBack. which builds on two insights: (1) predicting phases (i.e., values) variables appearing in the majority (or even all) of the satisfying assignments are essential for CDCL SAT solving, and (2) is sufficient to query the neural model only once for the predictions before the SAT solving starts. Once trained, the offline model inference allows NeuroBack to execute exclusively on the CPU, removing its reliance on GPU resources. To train NeuroBack, a new dataset called DataBack containing 120,286 data samples is created. NeuroBack is implemented as an enhancement allowed Ki ssat to solve up to 5.2% and 7.4% more problems on two recent SAT competition problem sets, SATCOMP 2022 and SATCOMP-2008 2023,, respectively. NeuroBack therefore shows how machine learning can be harnessed to improve SAT solving in an effective and practical manner.
state-of th- SAT solver called Ki ssat. As result, it
INTRODUCTION
Propositional satisfiability (SAT) solvers are designed check the satisfiability of given propo- sitional logic formula. SAT solvers have advanced significantly in recent years, which has fueled their applications in a wide range of domains. Mainstream modern SAT solvers are based on the CDCL algorithm Marques-Silva & Sakallah (2003). It mainly relies two kinds of variable related heuristics: 1) the variable branching heuristic Moskewicz et al. (2001); Liang et al. (2016), for deciding which variables are the best branch on; 2) the phase selection heuristic (Pipatsrisawat & Darwiche (atiiche(2000) (2007); Biere& & Fleury (2020): Fleurr & Heisinger] (2020), for deciding which phase (i.e.,
value) variable should have.
Recently, Graph Neural Networks (GNNs) have been proposed to improve CDCL SAT solvers by enhancing these two heuristics. However, this approach has not usually made solvers more effective Jaszczur et al. (2020); Kurin et al. (2019;1 Han (2020). One exception is NeuroCore (Sessm Bjørner (2019) which aims improve the variable branching heuristic in CDCL SAT solvers by predicting the variables involved in the unsatisfiable (unsat) core (i.e., subset of the SAT formula that remains unsat). It performs frequent online model inferences to adjust its unsat core prediction with dynamic information extracted from the SAT solving process. As result, NeuroCore helps two classic CDCL SAT solvers called Mi n Sa t. and G1 ucose solve more problems in the main track of SATCOMP-200 2018 Heule et al. (2018).
elfectivveasszzuur
However, frequent online inferences cause NeuroCore computationally intensive during its application.
The demand on GPU resources escalate, especially when deployed in parallel, a prevalent way for utilizing SAT solvers to tackle complex problems Hamadi et al. (2010); Schreiber & Sanders (202T) ; Martins et al. (2012). Obviously, lacking GPU resources would become the major bottleneck of NeuroCore's parallel performance. Note that, the setup of NeuroCore's experiments called for
network access to 20 GPUs distributed over five machines support 400 parallel NeuroCore runs.

---

Published as a conference paper at ICLR 2024
We propose NeuroBack, novel approach to make CDCL SAT solving more effective and avoid frequent online model inferences, thus making the GNN approach more practical. The main idea of NeuroBack is to make offline model inference, i.c. prior to the solving process, to obtain instructive static information for improving CDCL SAT solving. Once trained, the offline model inference allows NeuroBack to execute solely on the CPU, thereby making it completely independent of GPU resources. In particular, NeuroBack seeks to refine the phase selection heuristics in CDCL solvers by leveraging offline neural predictions on variable phases appearing in the majority (or even all) of the satisfying assignments.
The offline predictions on such phase information are based on the generalization of backbone variables, which are variables whose phases remain consistent across all satisfying assignments.
Recent work Biere et al. (202T); Al-Yahya et al.] (2022) has shown that backbone variables are crucial for enhancing CDCL SAT solving. Choosing the correct phase for backhone variable prevents conflicts, while an incorrect choice inevitably leads to backtracking in the search. Moreover, predicting the correct phases of non-backbone variables appearing in the majority of satisfying assignments is also important, because such phases prevent backtracking with high probabilities. Our conjecture is that the knowledge learned from predicting the phases of backbone variables can be transferred to predicting the phases of non-backbone variables exhibited in the majority of satisfying assignments. Therefore, NeuroBack applies GNN model, trained solely on predicting the phases of backbone variables, to predict the phases of variables appearing in the majority (or even all) of the satisfying assignments. We refer such variables as important variables for the rest of this paper.
NeuroBack converts the SAT formula with diverse scales into a compact and more learnable graph representation, turning the problem of predicting variable phases into a binary node classification problem. To make the GNN model both compact and robust, NeuroBack employs a novel Graph Transformer architecture with light-weight self-attention mechanisms. To train the model with supervised learning, a balanced dataset called DataBack containing 120,286 labeled formulas with diversity was created from five different sources: CNFgen Lauria et al. (2017), SATLIB (Hoos & Stürzle (2000), model counting competitions from 2020 to 2022 | (CC(2020) 202 2022), and main
and random tracks in SAT competitions from 2004 to 2021.
To evaluate the effectiveness of our approach, NeuroBack is incorporated into a state-of-the- art CDCL SAT solver called Kissat [iere & Fleury (2022), resulting in a new solver called HeuroBack-Kissal
The experimental results on all SAT problems from SATCOMP-200 -002 SAT (2022) and SATCOMP-2023 SAT (2023) show that NeuroBack allows Kissat to solve up to 5.2% and 7.4% more problems, respectively. The experiments thus demonstrate that NeuroBack is practical neural approach to improving CDCL. SAT solvers. The contributions of our paper are:
1. Approach. To our knowledge, NeuroBack presents the first practical neural approach to make the CDCL SAT solving more effective, without requiring any GPU resource during its application. 2. Dataset. A new dataset DataBack containing 120,286 data samples is created for backbone phase classification. DataBack is publicly available at ht / face. co/ da aasetsssss.........tt... s/ neuroback/Datasscc
3. Implementation. NeuroBack is incorporated into state-of-the-art SAT solver, Kissat. The source code of NeuroBack model and NeuroBack ssat is publicly available at https
7/gi thub. htt.hh..ooooo.....ommmmmh..hh.hh wenx wwww/ wwwp://wwwwwwwnnnnnnneeee
2 BACKGROUND
This section introduces the SAT problem, CDCL algorithm, phase selection heuristics in CDCL solvers, and basics of GNN and Graph Transformer.
Preliminaries of SAT In SAT, a propositional logic formula & is usually encoded in Conjunctive Normal Form (CNF), which is a conjunction (A) of clauses. Each clause is a disjunction (V) of literals. A literal is either a variable or its complement - Each variable can be assigned logical phase, (true) or (false). A CNF formula has a satisfying assignment and only every clause has at least one true literal. For example, CNF formula Ø (vi V -V2) A (22 V va) A U2 consists of three clauses 21 V - U/ V Vy and Dy: four literals U1. -02, V22 and Uy; and three variables U1, V2. and Uy. One satisfying assignment of ó is check a formula ø is sat or unsat. A complete solver either outputs a satisfying assignment for ø. or proves that no such assignment exists.
1, By 1, ets O. The goal of SAT solver is to
2

---

Published as a conference paper at ICLR 2024
The backbone of a sat formula is the set of literals that are true in all its satisfying assignments. Thus backbone variables are the variables whose phases remain consistent across all satisfying assignments. In the given CNF formula o, there are two backbone variables, in and v2., both maintaining phase of in all satisfying assignments of db
CDCL Algorithm CDCL makes SAT solvers efficient in practice and is one of the main reasons for the widespread use of SAT applications. The general idea of CDCL algorithm is as follows (see Marrques-Silve et al. (2021) for details). First, it picks a variable on which to branch and decides a phase to assign to it with heuristics. It then conducts Boolean propagation based on the decision. In the propagation, if a conflict occurs (i.e., least one clause is mapped 0), it performs conflict analysis; otherwise, it makes a new decision on another selected variable. In the conflict analysis, CDCL first analyzes the decisions and propagations investigate the reason for the conflict, then extracts the most relevant wrong decisions, undoes them, and adds the reason to its memory as learned lesson (encoded in a clause called learned clause) in order to avoid making the same mistake in the future. After conflict analysis, the solver backtracks to the earliest decision level where the conflict could be resolved and continues the search from there. The process continues until all variables are assigned a phase (sat), until it learns the empty clause (unsat).
Phase Selection Heuristics As indicated above, CDCL SAT solving mainly relies on two kinds of variable related heuristics: variable branching heuristics and phase selection heuristics, which are orthogonal to each other. Phase Saving Pipatsrisawat & Darwiche (2007) is a prevalent phase selection heuristic in modern CDCL solvers. It returns variable's last assigned polarity, either through decision or propagation. This heuristic addresses the issue of solvers forgetting prior valid assignments due non-chronological backtracking. Rephasing [Beree & Fleury (2020); Fleury &
Heisinger (2020) is more recent phase selection heuristic, proposed to reset or modify saved phases to diversify the exploration of the search space. The state-of-the-an CDCL solver, Kissat Biere &
Fleury 2022). incorporates the latest ad advancements in phase saving and rephasing heuristics.
GNN GNNs Wu al. (2020) Zhou et al. (2020) a family of neural network architectures that operate on graphs Gori et al. (2005); Scarselli et al. (2008); Gilmer et al. 2017); [Battagiaa et al. 2018).
Typical GNNs follow recursive neighborhood aggregation scheme called message passing Gilmer
et al. 20177. Formally, the input of GNN is graph defined as a tuple G = V E. W, H). where V denotes the set of nodes: E V x denotes the set of edges: W [W., (u. v) E} contains the feature vector W of each edge (u, v); and H [H E V) contains the feature vector H, of each node v. A GNN maps each node to a vector-space embedding by updating the feature vector of the node iteratively based on its neighbors. For each iteration, a message-passeeeee
layer L takes a graph G = (V, E, W, H) as an input and outputs a graph G" = (V. E, W, H() with updated node feature vectors, i.e., G" = L(G). Classic GNN models Gilmer et al. 2017 )) Kipf & Welling (0016); Hamilton et al. (017)) usually stack several message- passeeggssingggg layers to realize iterative updating. Prior work utilizing GNNs to improve CDCL SAT solving will be reviewed in the next section.
Graph Transformer Architecture Transformer Vaswani et al. (007) is a family of neural network architectures for processing sequential data (c.g., text or image), which has recently won great success in nature language processing and computer vision. Central to the transformer is the self-attention mechanism, which calculates attention scores among elements in sequence, thereby allowing each element to focus on other relevant elements in the sequence for capturing long-range dependencies effectively. Recent research MiinarchhMMnne et al. (2022) : /Wu al. (2021); Mialon al. (2021): I): Rong et al. (2020) has shown that combining the transformer with GNN results in competitive performance for graph and node classification tasks, forming the Graph Transformer architecture. Notably, GraphTrans Wu et al.] (201)) is representative model which utilizes GNN subnet consisting of multiple GNN layers for local structure encoding, followed by a Transformer subnet with global self-attention to capture global dependencies, and finally incorporates a Feed Forward Network (FFN) for classification. The GNN model design NeuroBack is inspired by GraphTrans.
RELATED WORK
This section presents related work on identifying the backbone and machine learning techniques for improving CDCL SAT solving.
3

---

Published as a conference paper at ICLR 2024
CNF
GNN-based
sat/
formula
Converter
phase selection
solver
unsat
Graph
Graph representation phase prediction
representation
NeuroBack
Figure I: Overview of NeuroBack. First, the input CNF formula is converted into a compact and more learnable graph representation. A trained GNN model is then applied once on the graph before SAT solving begins for phase selection. The SAT solver utilizes phase information in the resulting labeled graph an initialization to guide its solving process. Thus, with the offiine process of making instructive phase predictions, NeuroBack makes the solving more effective and practical.
Backbone for CDCL Solvers. Janota proved that identifying the backbone is co-NP complete Janota (2010). Furthermore, Kilby al. demonstrated that even approximating the backbone is generally intractable Kilby et al.] (2005). Wu Wu (2017) applies a logistic regression model to predict the phase of backbone variables to improve classic CDCL SAT solver called MiniSat Eén & Sörensson (003).
Although the approach correctly predicts the phases of 78% backbone variables, it fails to make improvements over MiniSat in solving time. In addition, recent works Biere et al.) (202T); YahYa
et al. (2022) have been focusing on enhancing CDCL SAT solving by employing heuristic search to
partially compute the backbone during the solving process. In contrast, NeuroBack applies GNN to predict the backbone in an offline manner to improve CDCL solving.
Machine Learning for CDCL Solvers. Recently, several approaches have been developed to utilize GNNs to facilitate CDCL SAT solving. NeuroS AT [Selsam et al. (2018) was the first such framework adapting a neural model into an end-to-end SAT solver, which was not intended as a complete SAT solver. Others Jaszczur et al. (2020); Davis et al. (962);; Kurin al. (2019) Han (2020); y Audemard Simon (2018) Zhang & Zhang (2021) aim to provide SAT solvers with better branching or phase selection heuristies. These approaches either reduce the number of solving iterations or enhance the solving effectiveness on selected small-scale problems with up to a few thousand variables. However, they do not provide obvious improvements in solving effectiveness for large-scale problems.
In contrast, NeuroCore Selsam & Bjørner (2019), the most closely related approach to this paper, aims make the solving more effective especially for large-scale problems in SAT competitions. It enhances the branching heuristic for CDCL using supervised learning to map unsat problems to unsat core variables (i.e., the variables involved in the unsat core). Based the dynamically learned clauses during the solving process, NeuroCore performs frequent online model inferences to tune the predictions. However, this online inference is computationally demanding. NeuroBack is distinct from NeuroCore in two main aspects. One, while NeuroCore is designed to refine the branching heuristic in CDCL SAT solvers, NeuroBack invented to enhance their phase selection heuristics. Two, while NeuroCore extracts dynamic unsat core information from unsat formulas through online model inferences, NeuroBack captures static backbone information from sat formulas using offline model inference. Details of NeuroBack are introduced in the following section.
4 NEUROBACK
4.1 OVERVIEW
In order to reduce the computational cost of the online model inference and to make CDCL SAT solving more effective, NeuroBack employs offline model predictions on variable phases to enhance the phase selection heuristics in CDCL solvers. Figure| shows the overview of NeuroBack. First, it converts the input CNF formula into compact and more learnable graph representation. Then, a well-designed GNN model trained to predict the phases of backbone variables, is applied on the converted graph representation to infer the phases of important variables. The model inference is performed only once before the SAT solving process. The resulting offline prediction is applied as an initialization for the SAT solving process. Finally, the enhanced SAT solver outputs the satisfiability of the input CNF formula. Key components of NeuroBack including the graph representation of CNF formulas, the based phase selection, and the phase prediction application in SAT solvers, are illustrated in the subsections below.
4.2 GRAPH REPRESENTATION FOR CNF FORMULAS
As in recent work Kurin et al. (2020): Yoleu & Póczos 20099 a SAT formula is represented using more compact undirected bipartite graph than the one adopted in NeuroCore. Two node types
4

---

Published as a conference paper at ICLR 2024
Transformer Subnet
Graph Self Attertion Transforer Block;
'Local Selt Attetion Tranatormer Btock
GNN Subnet
Black
Blocks
Blooks
Blocks
Figure 3: The architecture of NeuroBack model, consisting of three main components: a GNN subnet with I. stacked GNN blocks, transformer subnet with M GSA transformer blocks and N LSA transformer blocks, and FFN layer for node classification.
represent the variables and clauses, respectively. Each edge connects a variable node to clause node, representing that the clause contains the variable. Two edge types represent two polarities of a variable appearing in the clause, i.c., the variable itself and its complement. Although the representation is compact, its diameter might be substantial for large-scale SAT formulas, which could result in insufficient message passing during the learning process.
To mitigate this issue, we introduce meta node for each connected component in the graph, with meta edges connecting the meta node to all clause nodes in the component. With the added meta nodes and edges, every variable node not appearing in the same clauses can reach each other through their corresponding clause nodes and the meta node, thereby making the diameter at most four. Figure 2 shows an example of our graph representation for the CNF formula (vr V u2) A (12 V u3) A (t's V va). It includes one meta node, four variable nodes and three clause nodes C1. C2. C3. representing clauses en V2, 12 V 0g and 03 Vua, respectively. Without the added meta node and edges, the longest path in the graph runs from variable node in to variable node Ug, making the diameter six. However, by introducing the meta node and edges, the diameter is reduced to four.
v1 v2
Figure 2: An example graph representation of the CNF formula (v) u2) A (v2 U3) A (U3 V vy). A meta node m is added along with meta edges (represented by dashed lines) connecting to all clause nodes in the con- nected component, reducing the graph diameter from six to four.
Formally, for a graph representation G (V, E, W, H) of CNF formula, the edge feature We,v of each edge (u, v) is initialized by its edge type with the value 0 representing the meta edge, the value 1 rep- resenting positive polarity, and -1 negative polarity; the node feature
H, of each node is initialized by its node type with 0 representing meta node, representing a variable node, and - representing a clause node.
4.3 GNN-BASED BASED PHASE PREDICTION
Given that the phases of backbone variables remain consistent across all satisfying assignments, selecting the correct phase for a backbone variable prevents backtracking. Conversely, incorrect choice inevitably leads to a conflict. Moreover, the proportion of backbone variables is typically significant. For instance, during our data collection from five notable sources (i.e., CNFgen, SATLIB, model counting competitions, SATCOMP random tracks, and SATCOMP main tracks), backbone variables constitute an average of 27% of the total variables. Therefore, accurately identifying the phases of the backbone variables is crucial for efficiently solving a SAT formula. Furthermore, identi- fying the phases of the non- backbone variables appearing in the majority of satisfying assignments is also important. Because such phases could prevent backtracking with high probabilities.
Inspired by transfer learning Zhuang al. (2000) we first train GNN model predict the phases of backbone variables, and then leverage the trained model to predict the phases of important variables. Our key insight that the knowledge learned from predicting the phases of backbone variables can provide a valuable guidance on predicting the phases of banbbackoone variables exhibiting in the majority of satisfying assignments. With the converted graph representation, predicting the phases of all variables is a binary node classification problem for GNN, where 1 and 0 represent the positive and negative phases, respectively. To extract the phases of important variables, we introduce a threshold (set to 0.9 in current implementation). If the predicted probability is greater than a less than 1 - o, it is classified as the positive or negative phase of an important variable, respectively. The following subsections introduce the design, implementation, and training of our GNN model.
5

---

Published as a conference paper at ICLR 2024
4.3.1 GNN MODEL DESIGN
The sizes of converted graphs representing practical SAT formulas (usually with millions of variables and clauses) are typically substantial. To enable effective training within the constraints of limited GPU memory, it is essential for our model to be both compact and robust. Our GNN model design is inspired by the robust graph transformer architecture, GraphTrans Wu al. (022T). However, in our particular SAT application context, GraphTrans exhibits two limitations, both arising from the global self-attention mechanism within its transformer subnet. First, the mechanism does not explicitly integrate the topological graph structure information when determining attention scores. However, such information essential in characterizing SAT formula. Second, the global self- attention mechanism computes attention scores for all possible node pairs, leading to quadratic memory complexity with respect to the number of nodes in the graph. This is obviously infeasible for tackling the large-scale SAT formulas in our task.
To overcome the limitations, we introduce novel transformer subnet that both distinctly harnesses topological structure information and significantly enhances memory efficiency. It combines Graph Self-Attentio (GSA) and Local Self-Attention (LSA), replacing the original transformer's global self-attention. Instead of computing attention scores for all node pairs global self-attention GSA calculates attention scores solely for directly connected node pairs, leveraging information of edges and edge weights. This not only explicitly incorporates the topological structure information of the graph, but also reduces the memory complexity to linear in terms of the number of edges in the graph. Additionally; further reduce the memory complexity, LSA segments each node embedding into multiple node patches and computes attention scores for each pair of node patches. The results in a linear memory complexity in terms of the number of nodes in the graph.
Figure 3 iillustrates the design of our GNN model architecture. It consists of three main components: GNN subnet with L stacked GNN blocks, a transformer subnet with M GSA transformer blocks and N LSA transformer blocks, and FFN layer for node classification. Within each GNN block, a GNN layer preceded by a normalization layer, with a skip connection bridging the two. The transformer block is crafted to accelerate training on a significant collection of large-scale graphs. Inspired by the recent vision transformer architecture, ViT-22B Padlewski & Djolongal (2023). ) each transformer block integrates normalization layer, succeeded by both an FFN layer and GSA/LSA layer that operate concurrently to optimize training efficiency.
4.3.2 IMPLEMENTATION
The current implementation of NeuroBack model utilizes GTNConv Fey & I Lenssen 2023b) Xu cet al. (2018) to build the GNN layer. for its proficiency in distinguishing non-isomorphic graph structures. However, GINConv lacks the capability to encode edge weight information. To address this, we employ three GINConv layers, each corresponding to a distinct edge weight in our graph representation. Each GINConv layer exclusively performs message passing for edges with its corresponding weight. The node embeddings from these three GINConv layers are finally aggregated as the output of the GNN layer.
GATConv layers Fey & Lenssen (023a): Veličković et al. (017) is utilized to built the GSA transformer block. The patch encoder in the ViT transformer Dosovitskiy al. (2020) is applied to construct the LSA transformer block. LayerNorm Ba et al. (0166) is employed as our normalization layer. To avoid potential over-smoothing issues, as instructed in Chen al. 2020), the number of blocks in the GNN subnet is set to the maximum diameter of the graph representation (i.e., L = 4). To ensure the accuracy of our model, while taking into account our limited GPU memory, the number of both GSA and LSA blocks are set to three (i.e., M = 3 and N = 3). Additionally, FFNs within the transformer blocks contain no hidden layers, while the final FFN utilized for node classification is structured to include one hidden layer. The model is implemented using Py PyTorch Paszke et al. (0199) and Py Geometric Fey & Lenssen 2019).
4.3.3 MODEL PRE-TRAINING AND FINE-TUNING
The NeuroBack model undergoes two-stage training process. Initially, it is pre-trained an extensive and diverse dataset gathered from various sources. This pre-training equips it with the fundamental knowledge to classify the backbone variable phases across broad spectrum of CNF formulas. Subsequently, this pre- preitrdined model is refined or fine-tuned on a smaller, domain -spciff dataset. This fine-tuning process enhances the model's proficiency in classifying backbone variable

---

Published as a conference paper at ICLR 2024
DataBack-PT
CNFgen
SATLIB
MСCOMP
SATCOMP
Overall
DataBack-FT
SATCOMP
(random)
(main)
# CNF
21,718
80,306
11,560
4,876
118,460
CNF
1,826
Var
779
114
16,299
25,310
2.852
Var
206.470
# Cla
281,888
$29
63,501
88,978
61,898
# Cla
1,218,519
BackboneVar
280 (36%)
58 (51%)
8,587 (53%)
1,960 (8%)
1,009 (35%)
# Backhone Var
48,266 (23%)
Table 1: Details of DataBack. For each source, we summarize the number of CNF formulas; the average number of variables and clauses characterizing the size of each CNF formula; and the average number of backhone variables, with their proportion in total variables (indicated in brackets). Overall, for each dataset, we summarize the total number of CNF formulas and the corresponding average counts regarding all formulas in the set.
phases within a specific category of CNF formulas. Details about the pre-training and fine-tuning datasets are introduced in Section 5
Binary Cross Entropy (BCH) loss is adopted as our loss function. Besides, AdamW optimizer Loshchilov & Hutter (0177) with a learning rate of 10 is applied for model pre-training and fine-tuning. The number of epoch is set to 40 for pre-training, and 60 for fine-tuning. It took 48 hours in total to accomplish both the pre- pre-training and fine-tuning on our commodity computer.
4.4 APPLYING PHASE PREDICTIONS IN SAT
The goal is to leverage phase predictions derived from the GNN model to enhance the phase selection heuristics within CDCL SAT solvers. While numerous ways exist to integrate these neural predictions into CDCL SAT solvers, the most straightforward and generic approach is to initialize the phases of the corresponding variables in CDCL SAT solvers based on the predicted phases. In this paper, adopted the state-of-the-art solver Kissat [Bere & Fleury (2022) to support the phase initialization with NeuroBack predictions. The resulting implementation called NeuroBack Kissat.
5 DATABACK
We created a new dataset, DataBack, comprising sat CNF formulas labeled with phases of backbone variables, for pre-training (PT) and fine-tuning (FT) the NeuroBack model. Accordingly, there are two subsets in DataBack: the pre-training set, DataBack-PT, and the fine-tuning set, DataBack-FT. To get the backbone label, the very recent state-of-the art backbone extractor called CadiBack Biere et al. (2023) is utilized. Given that the fine-tuning formulas are typically more challenging to solve than the pre-training ones, label collection timeouts are set as 1,000 seconds for the pre-training formulas and 5,000 seconds for the fine-tuning formulas. DataBack includes formulas solved within the time limit with at least one backbone variable.
We observe that there exists a significant label imbalance in both DataBack-PT and DataBack- FT. To tackle this, for each labeled formula, we create a dual formula by negating all backbone variables the original formula. The labels of the dual formula are the negated phases of the backbone variables in the original formula. Formally, for formula f with backbone variables bi....,b,,
bn. let Cy (bl..... bn + {1,0) denote the mapping of each backbone variable to its phase. The dual formula f' is obtained from by negating each backbone variable: f' f[h, -b...., bn + =b,]]. The dual f' is still satisfiable and retains the same backbone variables as f. but with the opposite phases Ly (b:) = (b,(,,, E .l..... n]. For the given CNF formula example in Section - (v) V V A (02 V 03) A U2. having and U2 as its backbone variables with phases {V1, ) [1}. the dual formula is ø' = (-w1 V v2) A (-r02 V Uz) A -U2, still having V1 and 02 as the backbone variables but with opposite phases {e1, u2 + {0}. This data augmentation strategy doubles the size of DataBack with a perfect balance in positive and negative backbone labels. In the rest of the paper, DataBack-PT and DataBack-FT refer to the augmented, balanced datasets.
DataBack-PT The CNF formulas in DataBack-PP are sourced from four origins: 1) CNFgen Lauria et al. (2017), recent CNF generator renowned for crafting CNF formulas that feature in proof complexity literature; 2) SATLIB Hoos & Stützle (2000). an online benchmark library housing well-known benchmark instances, serving as foundational challenge for the SAT community; 3) model counting competitions from 2020 to 2022 Fichte et al. (202T): MCC 202T 2022). including wide range of CNF formulas for model counters count their satisfying assignments, which provide a good source for backbone extraction; 4) Random tracks in SAT competitions from 2004 to 2021, offering numerous challenging random SAT problems.
7

---

Published as a conference paper at ICLR 2024
metrics
model
precision
recall
F1
accuracy
pre-trained model
0.903
0.766
0.829
0.751
fine-tuned model
0.941
0.914
0.928
0.887
Table 2: The performance on the validation set of both pre-trained and fine-tuned NeuroBack models for classifying the phases of backbone variables, in terms precision, recall, Fl score and accuracy.
Table I shows the detailed statistics of the resulting dataset. CNFgen generated 10,859 labeled sat formulas (21,718 augmented formulas) grouped by five categories: random SAT, clique-coloring, graph coloring, counting principle, and parity principle. From SATLIB, 40,153 sat formulas with labels (80,306 augmented formulas) were collected, encoding seven kinds of problems: random SAT, graph coloring, planning, bounded model checking, Latin square, circuit fault analysis, and all-interval series. Model counting competitions and SAT competition random tracks contribute 5,780 (11,578 augmented) and 2,438 (4,876 augmented) labeled formulas, respectively. In total, 59,230 (118,460 augmented) formulas are included DataBack-PT.
The comparative size of formulas, as indicated by the average number of variables and clauses, reveals that formulas from model counting competitions and SAT competition random tracks are generally larger than those generated by CNFgen, which are in turn larger than those originating from SATLIB. In addition, formulas from model counting competitions and SATLIB exhibit relatively high average backbone proportions. These are followed by formulas from CNFgen, while formulas from the SAT competition 's random tracks demonstrate the lowest backbone proportion. DataBack-PT thus contains a diverse set of formulas.
DataBack- FT Given that NeuroBack will be tested on large-scale SAT formulas from the main track of recent SAT competitions, the fine-tuning dataset, DataBack-FT, incorporates CNF formulas from the main track of earlier SAT competitions spanning from 2004 to 2021. As shown in Table [ it contains 913 (1,826 augmented) labeled formulas. While DataBack-FT is considerably smaller size compared to DataBack-PP PT, its individual formulas are distinctly larger than those in DataBack-PT.
6 EXPERIMENTS
Platform All experiments were run on an ordinary commodity computer with one NVIDIA GeForce RTX 3080 GPU (10GB memory), one AMD Ryzen Threadripper 3970X processor (64 logical cores), and 256GB RAM.
Research Questions The experiments aim to answer two research questions:
RQI: How accurately does the NeuroBack model classify the phases of backbone variables?
RQ2: How effective is the NeuroBack approach?
RQ1: NeuroBack Model Performance The NeuroBack model was pre-trained on the entire DataBack-PT dataset, then fine-tuned on a random 90% of DataBack-FT samples, and evaluated on the remaining 10% as validation set. Table 2 details the performance of both the pre-trained and fine-tuned models in classifying the phases of backbone variables. Notably, the pre-trained model achieved 75.1% accuracy in classifying backbone variables, with a precision exceeding 90% and recall rate of 76.7%. Considering the distinct data sources of DataBack-PT and BackFac the results suggest that the pre-training enables the model to extract generalized knowledge about backbone phase prediction. Fine-tuning further augments model performance, with improvements ranging between 4% and 15% across all metrics, making precision, recall and Fl score all exceeding 90%. In conclusion, NeuroBack model effectively learns to predict the phases of backbone variables through both pre-training and fine-tuning
NeuroBack Performance To evaluate the solving effectiveness, we collect all 800 CNF formulas from the main track of SATCOMP-2023 SAT (2022) and SATCOMP-2022 SAT (023) as our testing dataset. For our baseline solvers, we selected the default configuration of K: ssa t, named Default. t tisisst,, which simply sets the initial phase of each variable to true. We implemented an additional baseline solver, Random Kissat, which randomly assigns the initial phase of each variable as either true or false. NeuroBack Kissattsstttt and its baseline solvers, were applied to all 800 SAT problems in the testing dataset, with the standard solving time limit of 5,000 seconds. Each solver utilized up to 64 different processes in parallel on the dedicated 64-core machine. The model inference for each NeuroBack solver was conducted solely on the CPU, with a memory limit of 10GB to mitigate memory contention issues. Consequently, 308 problems from SATCOMP-2022 and
RQ2:
8

---

Published as a conference paper at ICLR 2024
Delauli-Kisat
5000
Defaul-Kosat Kiund
NeuraBaskk Kisoat Random-Kiswet
Bardien-Kisal
3000
3000
Time
2000
2000
150
50
75
100
125
Problems salved
Probiems solved
(a) Solving progress in SATCOMP-2022
(b) Solving progress in SATCOMP-200
Figure 4: Progress of Default -ataauutt-issa,.,.. Random-Kissat. and NeuroBack-Kissal over time in solving problems (time in seconds) on SATCOMP-2021 (left) and SATCOMP-2023 (right), respectively. NeuroBack ssat outperforms the two baseline solvers on both testing sets.
353 problems from SATCOMP-2023 were successfully inferred. The CPU inference time for each of these problems ranged from 0.3 16.5 seconds, averaging at 1.7 seconds. Given that problems unsuccessfully inferred make the NeuroBack solver revert to its baseline, we exclude such problems from our evaluation of how NeuroBack contributes to SAT solving.
As a result, for 308 inferred problems in SATCOMP-2022, Default-Kiee Kissat and Random-Kissat solved 193 and 197 problems, respectively. In comparison, NeuroBack-Kisaa ssat solved 203 problems, representing an improvement of 5.2% over Default-Kissat and 3.0% over Random-Kissat, respectively. For 353 inferred problems in SATCOMP-2023, Default-Ki- 190 problems, respectively. In contrast, NeuroBack-Kiin improvements of 3.0% and 7.4% over Default- and Handom-Kisste respectively.
and Mondom--iissai successfully solved 198 and
solved 204 problems, making
The cactus plot is a commonly used plot in the SAT community for demonstrating the solving, as shown in Fig. 4 Random- Bonddom-Kissse performs better than Sefault-Kissad in SATCOMP- 2022, but worse in SATCOMP-2022 both baseline solvers. Specifically, NeuroBack-Kissar outperforms Default-Kisa 43 and 40 additional problems in SATCOMP 2022 and SATCOMP- 2023, respectively, reducing solving time by 117 and 36 seconds per problem. Similarly, NeuroBack -arroBack-KS ssat outperforms and SATCOMP-
In contrast, NeuroBack Kissat consistently outperforms
Random- K ssat in SATCOMP-200 tively, reducing solving time by 98 and 246 seconds per problem. For additional results, please refer to the Appendix section. Overall, results suggest that the phase initialization provided by NeuroBack outperforms both the default and random phase initializations in Ki Kissat, exhibiting enhanced proficiency in solving SATCOMP-200 and SATCOMP-2E problems.
on 22 and 29 more problems, respec-
DISCUSSION AND FUTURE WORK
The current implementation of NeuroBack has two main aspects to improve. First, pre-training the GNN model requires a large amount of data. Once trained, however, the model is able easily generalize to new problem categories, so the investment in putting together a large dataset is warranted. The dataset is publicly available benefit future research. Second, this paper employs neural phase predictions solely as an initial setting for variable phases in SAT solvers. However, multiple methods exist utilize these predictions in SAT, either in a static or dynamic manner, which are likely to yield further performance enhancements. For instance, phase predictions could be leveraged dynamically during rephasing to adjust or diversify the exploration of the search space.
8 CONCLUSION
This paper proposes machine learning approach, NeuroBack, to make CDCL SAT solvers more effective without requiring any GPU resource during its application. The main idea to make offline model inference on variable phases appearing the majority of satisfying assignments, for enhancing the phase selection heuristic in CDCL solvers. Incorporated in the state-of-the-art SAT solver, Kiss ssat, this approach significantly reduces the solving time and makes possible solve more instances in SATCOMP-202 and SATCOMP-2005 2023. NeuroBack is thus promising approach improving the SAT solvers through machine learning.

---

Published as a conference paper at ICLR 2024
9 ACKNOWLEDGMENT
We would like to thank the anonymous reviewers for their valuable feedback. This work was supported by a grant from the Army Research Office accomplished under Cooperative Agreement Number W91 1ENF-19-2-0333 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. This work was also supported in part by ACE, one of the seven centers in JUMP 2.0, Semiconductor Research Corporation (SRC) program sponsored by DARPA and by the Intel RARE center.
10
APPENDIX
10.1
ADDITIONAL EXPERIMENTAL RESULTS
The scatter plots is another commonly used plot in the SAT community for comparing the solving ef- fectiveness of two solvers each problem. Fig. shows the scatter plots of NeuroBack -iiccck--iie isst and its two baseline solvers, Default-Kin Kissat and Random Landom-Kissat,
is evident that more dots are present in the lower triangular area, indicating that there are more problems which BeuroBack-Kisstee
outperforms both Default-Kissal and Random Kissat. Randon-Kissat. Specifi-
cally, MeuroBack-Kissee outperforms Default-Kisaa on 43 and 40 additional problems in SATCOMP-2022 and EATCOMP-2023, respectively, reducing solving time by 117 and 36 seconds per problem. Similarly, NeuroBack - -isssat outperforms Random-Ki Kissat in SATCOMP- 2022 and SATCOMP-202 on 22 and 29 more problems, respectively, leading to reduction in solving time of 98 and 246 seconds per problem.
10.2 PERFORMANCE ON SOLVED SAT AND UNSAT PROBLEMS
Upon detailed analysis, for 661 problems from both SATCOMP-2095 and BATCOMP-202. testing sets, there are 194 unsat problems and 216 sat problems that are solved by either Default-Xisse NeuroBack-Kissal
For the 194 solved unsat problems, NeuroBack-Kissal out- performed Refault-Kissea in 121 cases (62.4%) while De Default-Kissat outperformed HeuroBack-Kissat in only 61 problems (31.4%). For the 216 solved sat problems, NeuroBack-Kissat outperformed Default-Kissat in 110 problems (50.9%), while Default-Kissat outperformed NeuroBack-Kissal in 87 problems (40.3%). While HeuroBack-Kissar showed higher improvement rate in unsat problems compared to sat ones (62.4% vs 50.9%), the extent of improvement was more significant in sat problems. On average, NeuroBack ssat enhanced the performance of sat problems by 53.2%, compared to an av- erage improvement of only 14.6% in unsat problems. These trends were similarly observed when comparing NeuroBack Kissat with Random Basloom-Kiissaa Kissat.
The experimental results highlight two key aspects. First, they demonstrate that NeuroBack's predicted variable phases can enhance the efficiency in solving unsat problems. Our explanation is that NeuroBack's 's phase predictions can aid in directing the search towards the unsatisfiable part of the search space. While NeuroBack cannot satisfy all components of given SAT problem, it may predict phases that satisfy certain components, thereby allowing the solver to concentrate on the unsat part. Furthermore, in modern SAT solvers such Default Kissat Biere Fleury (2020), an assignment that falsifies the fewer clauses is often preferred in the searching loop. allowing the solver specifically target the unsat portions of the clause set. Consequently, the phases predicted by NeuroBack can facilitate identifying an assignment that reduces clause falsification, thereby enhancing solving unsat problems.
Second, the experimental results also show that NeuroBack achieves more pronounced improvement in solving sat problems than in solving unsat problems. This distinction stems from the inherent nature of these problems. In sat problems, complete satisfying assignment exists, where each variable is assigned a phase that leads to a solution. Conversely, in unsat problems, only partial satisfying assignments exist, with phases assigned to just a subset of variables. Consequently, the phases predicted by NeuroBack have generally greater impact in resolving sat problems. This is because, for these problems, the predicted phases contribute directly to finding a satisfying assignment. In contrast, for unsat problems, the utility of predicted phases is somewhat restricted to identifying partial solutions refining the search scope. This fundamental difference in the nature of
10

---

Published as a conference paper at ICLR 2024
5000
5000
1000
4000
NeuroBack BauuoBaac-KKsaal Kissat
NeuroBack-Kissa Kissat
3000
3000
2000
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Default-Kissat
Random-Kissoe
(a) Default-Kissar
SouroBack-Kissa on
(b) Random-Kiisse vs. NeuroBack-Kot Kissat on SATCOMP-2022.
SATCOMP-2022.
5000
5000
NeuroBack-Kissat
NeurBBcck-KBse Dissa-
3000
3000
2000
2000
1000
1000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Default-Kissat
Random-Kissat
(c) Default-Kissat vs.
NeuroBack-Kissat on
(d) Random- Kissat vs. NeuroBack- Kissat on SATCOMP-2023,
SATCOMP-2D5
Figure 5: Time taken by Default-Kissee vs. NeuroBack BantBackk-Kssaar on SATCOMP- NeuroBack-Kissat on SATCOMP-2022 (b), Default-Kissat vs. NeuroBack-Kissat on SATCOMP-2023 (c), and Random-Ki Ksst seconds (for
2022 (a). Random-Kissat vs.
vs. NeuroBack-Kiss Kissst on SATCOMP-2023 (d) to solve each test problem problems that are solved by at least one solver). Each problem is represented by a dot whose location indicates the solving time of each method. The dots on the dashed lines 5,000 seconds indicate failures. It is evident that more dots present in the lower triangular arcas, indicating that there are more problems on which BeuuroBack-Kiie Handom-Kissal
outperforms both Default- -ouuul--issatt and
sat versus unsat problems underpins the varying degrees of effectiveness observed in NeuroBack's performance.
10.3 SETTING UP THE MEMORY LIMIT FOR NEUROBACK-KISE -KISAT
In our experimental setup, which includes a machine equipped with 256GB of memory running 64 solver instances in parallel, we have conservatively set the SAT formula size threshold 135 MB. This ensures that the memory usage of each solver instance does not exceed our specified memory threshold of 10GB. This threshold setting is based on our practical experience. Increasing this threshold could potentially lead to memory contention issues. Users might choose to adjust the formula size threshold based on their machine's memory capacity. Alternatively, they might simply establish a memory threshold for each solver instance based on their machine's memory capacity and allow model inference to proceed until this threshold is reached, which typically incurs an overhead of more than few seconds.
11

---

Published as a conference paper at ICLR 2024
REFERENCES
Model counting competition 2020 url, 2020. descriptions html
Model counting competition 2021 url, 2021.
https://mecompeiiiiiooooooo////0
descript html
Model counting competition 2022 url, 2022.
https://eccmmpttiiiooooo///22222
description.htn. html
Sat competition 2022. 2023-08-10.
httes///acccoettttooo.ghhho////2 2022. Accessed:
Sat competition 2023. httpes//satcomm::iiionggigi/o 1tt00///
2023. Accessed:
2023-11-23.
Tasniem Al-Yahya, Mohamed El Bachir Abdelkrim Menai, and Hassan Mathkour. Boosting the performance of edel-based sat solvers by exploiting backbones and backdoors. Algorithms, 15(9): 302, 2022.
Gilles Audemard and Laurent Simon. On the glucose sat solver. International Journal on Artificial Intelligence Tools, 184001, 2018.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.064500 2016.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 1a...10060.1111 2018.
Armin Biere and Mathias Fleury. Chasing target phases. In Workshop on the Pragmatics of SAT, 2020.
Armin Biere and Mathias Fleury. Gimsatul, IsaSAT and Kissat entering the SAT Competition 2022. In Tomas Balyo, Marijn Heule, Markus Iser, Matti Järvisalo, and Martin Suda (eds.). Proc. of SAT Competition 2022 - Solver and Benchmark Descriptions, volume B-2022-1 of Department of Computer Science Series of Publications B, pp. 10-11. University of Helsinki, 2022.
Armin Biere, Mathias Fleury, and Maximilian Heisinger. Cadical, kissat, paracooba entering the sat competition 2021. 2021. URL httth:t////pppi www.nteettsst.eeee commantisccolar..oom orw.://psc.oCoooCC
238996423
Armin Biere, Nils Froleyks, and Wenxi Wang. Cadiback: Extracting backbones with cadical. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Schloss Degstubl-LecbbnzzzZennne für Informatik, 2023.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference artificial intelligence, volume 34, pp. 3438-3445 2020.
Martin Davis, George Logemann, and Donald Loveland. A machine program for theorem-proving. Communications of the ACM, 5(7):394 1962.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 11929, 2020.
Niklas Fén and Niklas Sörensson. An extensible sat-solver. In International conference theory and applications of satisfiability testing, pp. 502-518. Springer, 2003.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
12

---

Published as a conference paper at ICLR 2024
Matthias Fey and Jan E. Lenssen. conv.gatconv.
http:://pytorch-qqomttttt http:////eeeeeee/eaaaa//////nana
readthedocs http:/.ooeennnnaaaaeeeeeee GATConv. html, 2023a.
Matthias Fey and Jan E. Lenssen. conv.ginconv. https://pytorcch-eeoettts readthedocs. 10/ http://///aaeeeeepaaaaaaaaaaaaaa org.paaateeatoorcc.e..eeeee.....
GINConv. html| 2023b.
Johannes K Fichte, Markus Hecher, and Florim Hamiti. The model counting competition 2020.
Journal of Experimental Algorithmics (JEA), 26:1-26, 2021.
ABKFM Fleury and Maximilian Heisinger. Cadical, kissat, paracooba. plingeling and treengeling entering the competition 2020. SAT' COMPETITION, 2020:50, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp.
1263-1272. PMLR, 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734. IEEE, 2005.
Youssef Hamadi, Said Jabbour, and Lakhdar Sais. Manysat: parallel sat solver. Journal Satisfiability, Boolean Modeling and Computation, 6(4):245 262 2010.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
arXiv preprint Jesse Michael Han. Enhancing sat solvers with glue variable predictions. arXiv:2007.02559, 2020.
Marijn JH Heule, Matti Juhani Járvisalo, Martin Suda, al. Proceedings of SAT competition 2018: Solver and benchmark descriptions. 2018.
Holger H Hoos and Thomas Stützle. Satlib: An online resource for research on sat. Sat, 2000: 283-292, 2000.
Mikoláš Janota. SAT solving in interactive configuration. PhD thesis, University College Dublin, 2010.
Sebastian Jaszczur, Michal Euszczyk, and Henryk Michalewski. Neural heuristics for sat solving. arXiv preprint arXiv:2005.13406, 2020.
Philip Kilby, John Slaney, Sylvie Thiébaux, Toby Walsh, et al. Backbones and backdoors in satisfiability, AAAI, volume 5, pp. 1368-1373, 2005.
Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint 1rX1v:1609.02900 2016.
Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. Improving SAT solver heuristics with graph networks and reinforcement learning. 2019.
Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. Improving SAT solver heuristics with graph networks and reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
Massimo Lauria, Jan Elffers, Jakob Nordström, and Marc Vinyals. Cnfgen: A generator of crafted benchmarks. In International Conference Theory and Applications Satisfiability Testing, pp. 464-473. Springer, 2017.
Jia Hui Liang Vijay Ganesh, Pascal Poupart, and Krzysztof Czarneck.. Learning rate based branching heuristic for sat solvers. In Theory and Applications of Satisfiability Testing-SAl -SAT 2016: 19th Inter- national Conference, Bordeaux, France, July 5-8, 2016, Proceedings 19, pp. 123-140. Springer, 2016.
13

---

Published as a conference paper at ICLR 2024
Iyy Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.S500. 2017.
Joao Marques-Sie Silva, Inês Lynce and Sharad Malik. Conflict-driven clause learning sat solvers. In Handbook of Satisfiability: Second Edition. Part 1/Part 2, pp. 133-182. IOS Press BV, 2021.
Joao P Marques Silva and Karem A Sakallah. Grasp a search algorithm for satisfiability. In The Best of ICCAD, pp. 73-89. Springer, 2003.
Ruben Martins, Vasco Manquinho, and Inés Lynce. An overview of parallel solving. Constraints, 17:304-347, 2012.
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106.0566 2021.
Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang, Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. arXiv preprint arXiv:2202.0844 2022.
Matthew W. Moskewiez, Conor F. Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik. Chaff: En- gineering an efficient sat solver. In Proceedings of the 38th Annual Design Automation Conference, DAC '01, pp. 530-535, New York, NY, USA, 2001. Association for Computing Machinery.
Piotr Padlewski and Josip Djolonga. Scaling vision transformers to billion parameters, https:/ a goog 1 ebl og. com wtt.ccmmm.moe. 2ttmm//2233333// sca ton www.ooottttaaoooooee-oeeeeeeee wwwooormrsttoooo fow.ers-toossst-2222... htm 2023.
oo-ssonttraanattt rans
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint arXiv:/912.01703, 2019.
Knot Pipatsrisawat and Adnan Darwiche. A lightweight component caching scheme for satisfiability solvers. In Theory and Applications of Satisfiability Testing-SAV SArinng--ATTaaa 2007: 10th International Conference, Lisbon, Portugal, May 28-31, 2007. Proceedings 10, pp. 294-2992 Springer, 2007.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Advances in Neural Information Processing Systems, 33:12559-12577 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008
Dominik Schreiber and Peter Sanders. Scalable sat solving in the cloud. In Theory and Applications of Satisfiability Testing-SAe SAT 2021: 24th International Conference, Barcelona, Spain, July 5.9, Springer, 2021.
2021, Proceedings 24, pp.
Daniel Selsam and Nikolaj Bjømnrr. Guiding high-performance SAT solvers with unsat-core pre- dictions. In International Conference Theory and Applications of Satisfiability Testing, pp. 336-353. Springer, 2019.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning a SAT solver from single-bit supervision. arXiv preprint arXiv:1802.0300 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Haoze Wu. Improving sat-solving with machine learning. Proceedings of the 2017 ACM SIGCSE Technical Symposium Computer Science Education, pp. 787-788, 2017.
14

---

Published as a conference paper at ICLR 2024
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and lon Stoica. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34:13266-13279 2021.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 2018.
Emre Yolcu and Barnabás Póezos. Learning local search heuristics for boolean satisfiability. In Advances in Neural Information Processing Systems, pp. 7992-8003, 2019.
Ziwei Zhang and Yang Zhang, Elimination mechanism of glue variables for solving sat problems in linguistics. In The Asian Conference on Language, pp. 147-167, 2021.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57-81, 2020.
Fuzhen Zhuang. Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He. A comprehensive survey on transfer learning. Proceedings of the IEEE, 109(1 10941)3337 2020.
15


Reviews:
[{"review_id": "sPwb0ygsOs", "reviewer": "Reviewer_w5iE", "summary": "The NeuroBack paper proposes a new approach to improve CDCL SAT solving using Graph Neural Networks. The proposed approach, called NeuroBack, gives an initial assignment to all variables and queries the neural model only once, allowing it to execute exclusively on the CPU and making GNN improvements practical. The paper also introduces a new dataset called DataBack and implements NeuroBack as an enhancement to a state-of-the-art SAT solver called Kissat. The authors evaluate NeuroBack on a variety of benchmarks and show that it outperforms Kissat and other state-of-the-art solvers on many instances.", "questions": "See the above comments.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Using ML to enhance CDCL SAT solver is promising research, which is more likely to yield improvement in SAT solving than end-to-end learning on SAT. I like the idea in this paper of using ML to give an initial assignment for the CDCL solvers by training on predicting the value of backdoor variables. The paper mentions the importance of backdoor valuables and the intuition of why training on backdoor variables can help predict the values for all variables that appear in the majority of the variables.\n\nIt is also promising to see that NeuroBack is actually able to improve Kissat, as state-of-the-art SAT solvers are well-engineered and very hard to optimize.", "weaknesses": "While training on backdoor variables yields a good predictor for the value of all variables, why this approach works is still a bit mysterious. It would be helpful to have more experiments showing that initialization is actually better than a random assignment. Therefore I would like to see some behavior studies of NeuroBack on different kinds of benchmarks. Possible ways include comparing the distance from this initial assignment given by NeuroBack with the nearest solution. Or evaluating the prediction accuracy of the value of a specific variable given by NeuroBack with the majority value of this variable in all solutions (this requires listing all solutions of a formula, which is only doable on small formulas).  \n\nThe experiment section also lacks a comparison with other initialization methods for SAT solving, as Neuro-back is in essence an initialization method. \n\nI am not quite convinced by the claimed advantage that NeuroBack only needs to be called once. This is a trivial property for any initialization approach for SAT solving. I believe that a more interactive collaboration between GNN and SAT solvers can further improve the performance of STA solvers, even if GNN needs to be called multiple times (correct me if I am wrong). I would be happy to change the evaluation if my concerns can be addressed.\n\nMinor comments:\nI would use \"value\" instead of \"phase\" and \"initial assignment\" instead of \"initialization\" to make it clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gtZ9cvJ19s", "reviewer": "Reviewer_HXv9", "summary": "This paper is devoted to improving propositional satisfiability (SAT)\nsolving by means of utilizing modern machine learning (ML) technology.\nNamely, the paper proposes to make use of a GNN architecture for\nrepresenting CNF formulas, which is trained to determine the variable\npolarity / phase following the ideas behind backbone literals.\nBackbone literals of a CNF formula are literals that must necessarily\nbe satisfied by every satisfying assignment of that formula. The\nauthors argue that the GNN architecture they propose can efficiently\ndetermine the polarities of all variables: including those appearing\nin backbone literals but also any other variables in the formula.\nAfterwards, when the predicted polarities are obtained, a\nstate-of-the-art SAT solver can be bootstrapped with these variable\nphases with the hope that such initialization can boost the solver's\nperformance. Experimental results shown in the paper demonstrate the\neffectiveness of this idea if implemented on top of a modern SAT\nsolver called Kissat.", "questions": "- Can you comment on the use of this heuristic for unsatisfiable\n  instances? Have you tried this? If yes, what is the performance\n  compared to Kissat? If not, why?\n\n- Can you comment on losing on 82 instances to Kissat if we consider\n  all the 400 instances in the benchmark set? Am I missing anything?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is clearly written and easy to follow. Normally, papers on\n  applying ML for improving combinatorial problem solving are written\n  in Greek, if seen from the perspective of a researcher with\n  expertise in the combinatorial problem of interest. This paper\n  serves as a nice exception.\n\n- The idea is reasonable. It is simple to implement and it can be used\n  with any SAT solver.\n\n- The experimental results reported although not amazing look solid.", "weaknesses": "- Although everything the paper describes is described well, there are\n  bits that aren't detailed sufficiently - some ML people may find it\n  to be a minus.\n\n- The paper says nothing about the usability of this heuristic for\n  unsatisfiable instances. There are no backbones in those but I\n  presume some variable phases may still be more useful in practice\n  than the others.\n\n- Despite the claimed experimental results, nothing is shown for the\n  unsatisfiable instances. This and the point above can be joined\n  together.\n\n- Although Neuroback+Kissat solves 10 more instances out of 308, there\n  are 92 more (308 + 92 = 400) where Neuroback fails to do anything\n  useful. Hence, the proposed solver configuration must clearly lose\n  to Kissat on those 92 instances as it spends additioanl time with no\n  effect. If this understanding of mine is correct then the results\n  aren't so positive.\n\n- Minor1: in CDCL description, the algorithm undoes not only\n  *wrong decisions* but also propagated literals.\n\n- Minor2: in CDCL description, the conventional algorithm backtracks\n  to the *latest* decision level where the conflict is resolved - not\n  *earliest*.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UthKXwGcnw", "reviewer": "Reviewer_7KxS", "summary": "This paper addresses the challenge of improving propositional satisfiability (SAT) problem-solving, a significant task in various research domains like planning, verification, and security. It introduces a novel approach called NeuroBack, which enhances Conflict-Driven Clause Learning (CDCL) SAT solvers using Graph Neural Networks (GNNs. The innovation lies in two key insights: predicting variable phases that frequently appear in satisfying assignments and requiring just one query to the neural model before starting the SAT solving process. Once trained, NeuroBack can operate entirely on the CPU, reducing the reliance on GPU resources.\n\nThe authors developed a new dataset, DataBack, comprising 120,286 data samples, to train NeuroBack and implemented it as an enhancement to the state-of-the-art SAT solver, Kissat. By incorporating NeuroBack into Kissat, the SAT solver exhibited a 5.2% improvement in problem-solving effectiveness, as demonstrated in the SATCOMP-2022 competition dataset. It also improved solving efficiency, resulting in an average time saving of 117 seconds per problem. This research introduces the first practical neural approach to enhance CDCL SAT solving without requiring GPU resources, provides a new dataset, and offers public access to the NeuroBack model and NeuroBack-Kissat source code.", "questions": "-", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Providing a dataset\nCompeting with SAT 2022", "weaknesses": "I think some citations are missing\n\nhttps://cs.stanford.edu/~jure/pubs/g2sat-neurips19.pdf\nNeurogift: Using a machine learning-based sat solver for cryptanalysis\nRole of Machine Learning for Solving Satisfiability Problems and its Applications in Cryptanalysis\n\nIt would be nice to have a use case in Cryptanalysis (solving AES or small AES instance)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6FVqJX5fU9", "reviewer": "Reviewer_bkSL", "summary": "This paper studies the proposition satisfiability (SAT) problem, which is an NP-complete problem. Recent algorithms focus on enhancing CDCL, the mainstream algorithm for solving SAT problems, using Graph Neural Networks (GNNs). While this can make the  solving process more effective, these methods require online model inferences, which consumes substantial GPU resources. In this paper, the authors design an approach called NeuroBack, which uses the trained model and can be executed on the CPU, avoiding the dependence on GPU resources. The authors claim that enhancing the state-of-the-art SAT solver Kissat with NeuroBack can achieve better results than Kissat itself.", "questions": "Please see my comments listed in \"Weaknesses\".", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. NeuroBack gets rid of the GPU resource dependence of the solving process and improves the practicality of using GNN to enhance SAT solving.\n\n2. The authors conduct experiments to evaluate the performance of their proposed method.", "weaknesses": "I have several comments regarding the experiment part, which are listed below.\n\n1. Regarding the baseline competitor. As described in the experiment part, the baseline competitor is kissat. Although kissat can be regarded as the latest breakthrough in the community of SAT solving, lots of kissat’s variants have been proposed since the introduction of kissat (as can be observed in the recent editions of SAT competitions). However, the authors only compare their solver with vanilla kissat. As a submission to a top-tier conference, this is not that thorough.\n\n2. Regarding the evaluation on SAT Competition 2022’s datasets. Actually, as a submission in SAT solving, the tradition is to evaluate their proposed solver on the dataset from the latest edition of SAT Competition. In fact, as of the submission deadline of ICLR, the latest edition of SAT Competition is SAT Competition 2023. According to the official website of SAT Competition 2023 (https://satcompetition.github.io/2023/), the dataset of SAT Competition 2023 was published in July, 2023. Since the submission deadline of ICLR is due on September 28. 2023, there left two months for the authors to conduct the comparative experiments on the dataset of SAT Competition 2023. Hence, such lack of experiments is indeed a minus.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)