Boolean Satisfiability via Imitation Learning
Authors: Zewei Zhang
Huan Liu
YUANHAO YU
Jun Chen
Xiangyu Xu
Venue: ICLR 2026 Poster (2026)
Keywords: Boolean Satisfiability
Imitation Learning
Autoregressive Modeling
Branching Heuristics
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: We propose ImitSAT, a branching policy for conflict-driven clause learning (CDCL) solvers based on imitation learning for the Boolean satisfiability problem (SAT). Unlike previous methods that predict instance-level signals to improve CDCL branching indirectly, or rely on reinforcement learning and insufficient CDCL information to enhance branching, ImitSAT learns from expert KeyTrace that collapses a full run into the sequence of surviving decisions. Replaying a KeyTrace on the same instance is nearly conflict-free, providing dense decision- level supervision and directly reducing propagations—the dominant contributor to wall-clock time. This prefix-conditioned supervision enables ImitSAT to reproduce high-quality branches without exploration, yielding faster convergence, stable training, and seamless integration into CDCL. Extensive experiments demonstrate that ImitSAT reduces propagation counts and runtime, outperforming state-of-the-art learned approaches. We released the source code and trained model at https://github.com/zewei-Zhang/ImitSAT.

Published as a conference paper at ICLR 2026
BOOLEAN SATISHIABILITY VIA IMITATION LEARNING
Zewei Zhang' Huan Liu'
Yuanhao Yu! Jun Chen
Xiangyu Xu
McMasser University 2 Jiaotong University {zhanz561, jun xuxiangyu2014e com
@atuin/mmmstttteeeeeee @mcnaster. ca
(liuh127, dr. Jt.yyhyuJoutlloo..cm
ABSTRACT
We propose ImitSAT, a branching policy for conflict-driven clause learning (CDCL) solvers based on imitation learning for the Boolean satisfiability prob- lem (SAT). Unlike previous methods that predict instance-level signals to improve CDCL branching indirectly, or rely on reinforcement learning and insufficient CDCL information to enhance branching, ImitSAT learns from expert Key Trace that collapses full run into the sequence of surviving decisions. Replaying a KeyTrace on the same instance is nearly conflict-free, providing dense decision- level supervision and directly reducing propagations- the dominant contributor to wall-clock time. This prefix-conditioned supervision enables IT to repro- duce high-quality branches without exploration, yielding faster convergence, sta- ble training, and scamless integration into CDCL. Extensive experiments demon- strate that ImitSAT reduces propagation counts and runtime, outperforming state- of-the-art learned approaches. We released the source code and trained model at https: /tttt//gtttti thub. com / zewei Zhang/ ImitSAT
INTRODUCTION
The Boolean satisfiability (SAT) problem is cornerstone of theoretical computer science and ar- tificial intelligence (Cook) 1971 Karp 1972). Beyond its foundational role, SAT serves as the computational backbone of numerous applications. including formal verification, planning, and combinatorial optimization. Modern solvers for SAT are dominated by the conflict-driven clause learning (CDCL) framework (Silva & Sakallah, 1996] [Beree et al., (2009), which has scaled to indus- trial benchmarks of immense complexity. A CDCL run interleaves branching, unit propagation, and conflict analysis. Among these components, the branching rule largely determines the search tra- jectory, while unit propagation often dominates runtime (Zhang & Malik] 20022] Davis et al. 2008) Moskewicz et al., 2001). As result, more informed branching decisions can translate directly into faster solving.
Classical branching heuristics, however, are hand-crafted and limited in their adaptability. Recent work has sought to improve solver performance by integrating learning- based guidance. For ex- ample, SATformer (Shi et al. (023) learns instance-level signals to adjust variable activities during initialization, but it exerts no influence once the branching loop begins. Graph-Q-SAT (Kurin et al. 2020) introduces online agent within CDCL,, yet it relies on reinforcement learning (RL), which requires extensive exploration and can be unstable due to sparse rewards and delayed feedback. Moreover, Graph-Q-SAr does not utilize the full CDCL execution history; each branching con- ditioned only on compact graph snapshot of the current state, so the history influences the agent only indirectly.
In contrast, we adopt imitation learning, which trains directly from expert traces. Specifically, we introduce ImitSAT, a CDCL branching learner trained on expert trace replays. Replaying an ex- pert trace on the same instance is nearly conflict-free, eliminating redundant propagations and pro- viding clean training targets. Since branching is inherently prefix-conditioned, we formulate it as an autoregressive sequence modeling problem, and implement ImitSAT with Transformer-bas learner /Vaswani et al. 2017). Our model captures long-context dependencies while keeping runtime costs practical through lightweight autoregressive attention (Hawthorne al. 2022)
"Corresoonding author

---

Published as a conference paper at ICLR 2026
To obtain expert traces, collapse full solver runs into sequences of surviving decisions, yielding dense, step-level supervision at every branching point. This approach enables the learner to repro- duce high-quality decisions without costly exploration, resulting in faster convergence, more stable training, and natural alignment with the prefix-conditioned structure of branching. During inference, ImitSAT reads the instance together with KeyT Trace prefix and autoregressively predicts the next signed variable as the branch decision. The policy is queried under a small budget, reverting to the native heuristic when uncertain, while all other CDCL components remain unchanged, preserving completeness and robustness.
We evaluate AT on held-out random 3-SAT instances ranging from 100 variables, as well as on structured families including satisfiable and unsatisfiable instances and non-k-SAT formu- las. Under limited query budgets, ImitSAT consistently reduces propagations relative to a standard CDCL solver and outperforms prior learning- based methods, SATformer and Graph-Q-SAT,, across most settings while matching their performance elsewhere. Wall-clock measurements show that Im- itSAT achieves favorable runtime performance against SOTA methods (Shi et al. 2023 Kurin al.) 2020), Remarkably, although trained solely on simple random 3-SAT, ImitSAT transfers effectively to unsatisfiable and non-k-SAT benchmarks without modification.
We summarize the contributions of this work as below.
We propose Im, the first branching policy for CDCL solvers based on imitation leamn- ing. Unlike prior methods that rely on reinforcement learning, ImitSAT leverages dense, decision-level supervision from expert traces.
We cast branching as a sequential modeling problem by collapsing solver runs into compact sequences of surviving decisions. These sequences serve as clean, conflict-free training targets and align naturally with prefix-conditioned autoregressive modeling.
Extensive experiments demonstrate that ImitSAT yields both practical efficiency and strong generalization.
RELATED WORKS
Neural guidance for SAT and CDCL. Early learning approaches focused on instance-level pre- diction, using Graph Neural Network (GNNs) (Scarselli et al. 2008 to classify SAT or UNSAT, as
seen in NeuroSAT (Selsam et al. 2019 Selsam & Bjørner 2019) and (Cameron et al., 2020). Re- cent work has explored whether Transformers can learn solver behavior directly (Pan et al. 2025
In parallel with these model-based approaches, complementary efforts target data and benchmark- ing, including G2SAT (You al. 2019) and G4SATBencc (Li et al. 2024). Building on these foundations, a second line integrates learning inside solvers to shape specific components: for ex- ample, NeuroSelect (Liu et al. (2024) learns clause deletion policies, NeuroBack (Wang al. 2024) improves phase initialization with GNNs, and RDC-SAT (Zhai & Ge 2025) adopts a divide-and- conquer strategy via reinforcement learning. This approach leads targeted enhancements within solver mechanisms. More concretely, within the CDCL branching loop, several methods exemplify this integration: NeuroSAT (Selsam Bjorner] 2019) has been used to guide variable selection; Graph-Q-SAY (Kurin et al. 2020) trains an RL agent queried online during search based on instance information; and fATformer (Shi et al. 2023) trains a GNN Transformer model to initialize the CDCL that indirectly influences branching thereafter.
Imitation learning for control. Imitation learning (IL) learns policies directly from expert demonstrations, that is, sequences of states with associated actions (Osa et al., 2018 Zare et al., 2024). A simple example is behavior cloning (BC), which utilizes supervised learning to map observed situations to expert choices (Pomerleau) 199T). Building on the principles of imitation learning, the Decision Transformer (Chen et al. 2021) is similar to behavior cloning, framing rein- forcement learning as sequence modeling, where an autoregressive Transformer' is trained predict the next action given sequence rollout of returns, states, and actions. This view connects control to next-token prediction and attains competitive performance without explicit value function learn- ing. The application of imitation learning extends beyond traditional domains. For instance, beyond robotics and games, IL has guided decision decision-making making in exact optimization solvers. In -nteeernttger linear programming, policies learned to imitate strong branching can be used within branch-and-
2

---

Published as a conference paper at ICLR 2026
Stage
Stage
Stage 3
TeyTeace
X4
X4
X4
Xk Variable
Decide True
xs
X3
X3
Xi
Collapse
X1
Decide Folse.
Backtrack
x2
x2
Conflict
CDCL Run
Solved
Figure 1: From a CDCL run KeyTrace The left pane sketches one run in three stages: (1) decide = T, then = T, hit conflict, backtrack to the decision on 23i (2) set and solve. Unit assignments are omitted for clarity. Collapsing backtracks removes detours and keeps only the surviving root-to-current decisions, yielding the compact KeyTrace on the right, which serves as the expert for imitation. A step-by-step walkthrough is in Appendix H
1,
conflict again, backtrack 24: (3) set 14 7. then decide 21 T and Z2
bound and achieve strong results (Gasse et al. 2019). Related work also learns branching policies within branch-and-bound (B&B) for mixed-integer programming (MIP) (Zarpellon et al. [021] He al., 2014, Khalil et al. 2016). While these methods are close in spirit, the underlying search dynamics differ: MIP B&B explores monotone tree with stoon-branching oracles and immedi- ate, node-local feedback, whereas SAT CDCL performs non-monotone search with restarts, clause learning, and delayed, non-local feedback. From the imitation-learing perspective, prior MIP ap- proaches typically learn local ranking models on MIP features, whereas we train transformer-bant autoregressive policy that imitates entire CDCL KeyTraces. Thus, our setting complements IL for MIP branching, differing both in the target solver dynamics and the learning formulation.
Motivated by the limitations of neural guidance for SAT detailed above, and drawing inspiration from imitation learning, we propose ImitSAT. The branching policy for CDCL clones a near conflict- free KeyTrace distilled from solver runs. To achieve this, cast branching sequence prediction and train an autoregressive next-decision model on compact sequences of sur- viving decisions. This provides dense, decision-leve supervision at low per-query cost. These design choices help reduce propagation and improve wall-clock time under small query budgets.
prefix-conditioned
PRELIMINARIES ON SAT
Boolean Satisfiabllity Problem. The Boolean satisfiability problem (SAT) is the canonical deci- sion problem in propositional logic. It asks whether Boolean formula F over variables .1...... can be made true by assigning each variable a value [T, L), where denotes true and denotes false. A literal is either variable u; its negation -x;, clause disjunction of literals,
C₁ = (Li,1 V... V...V (...)
(1)
and formula is in conjunctive normal form (CNF) Plaisted & Greenbaum 1986 if is conjunc- tion of clauses:
C, A.., C...
An assignment is mapping (xi,..., Fn) L). It satisfies a clause if at least one literal in the clause evaluates to under a, and satisfics the entire formula F if every clause is satisfied. We say that F' is satisfiable (SAT) if such an assignment exists, and unsatisfiable (UNSAT) otherwise.
special case is the k-SAT problem, where each clause contains exactly & literals. The case (3-SAT) is of particular importance: it is NP-complete (Karp) 1972) and widely used in theoretical analysis and empirical benchmarks. For example, consider the CNF formula
(x] V -gg V x44) (-w1 22 TTa) (-02 2 V -ag V -aa)).

---

Published as a conference paper at ICLR 2026
This formula is SAT, since the assignment 21 T, 22 true. no assignment satisfies all clauses, the instance would be UNSAT.
T, 23 L. 24 makes every clause
In practice, SAT formulas often represented in the standard DIMACS CNF format (Johnson & Trick 1996). In this encoding, each clause is written as a sequence of nonzero integers terminated by 0, where the integer denotes variable 2; and -i denotes its negation -z;- For the formula in Equation 3 the DIMACS form is:
FDIMACS 1 -3 0 -1 2 -2 -3 0.
This compact numeric encoding is convenient for algorithmic solvers and sequence-bae based models.
Conftict-driven Clause Learning. Conflict-driven clause learning (CDCL) is the dominant algo- rithmic framework for practical SAT solvers (Silva & Sakallah 1996] Biere et al. 2009). A CDCL solver incrementally explores branching search tree through three fundamental operations: deci- sion (D), where the solver assigns a value to a chosen literal and thus extends the current partial as- signment; unit propagation (A), also known Boolean Constraint Propagation (BCP) (Moskewicz) ct al. (001), where implied literals are deduced from unit clauses; and backtracking (BT), where a detected conflict triggers clause learning and non-chronological jump to earlier decision level.
At each decision level, the solver selects a decision literal, after which propagation infers additional assignments, possibly none. If a clause is falsified, conflict analysis derives new learned clause, identifies its asserting literal, and adds the clause to the solver's s database. The solver then backjumps the highest decision level where the learned clause becomes unit and enqueues the asserting literal. A conflict at decision level 0 establishes that the formula is UNSAT, while complete assignment with no conflicts proves SAT.
Branching Heuristic and Implementation. Branching is the central operation in CDCL: at each step of the search, the solver selects variable and its polarity to branch on. The quality these choices is critical. Strong decisions can greatly reduce the number of propagations and conflicts, whereas weak ones may cause the search to grow exponentially.
Usually, the choice of the next decision variable, together with its phase, is determined by branch- ing heuristic. The most influential family of hcuristics is the Variable State Independent Decaying Sum (VSIDS) (Moskewicz al. 2001). In VSIDS, variables are assigned activity scores that are increased whenever they appear in learned clauses. These scores are then periodically decayed, en- suring that recently relevant variables are favored for branching. This dynamic prioritization enables the solver to focus on the most promising parts of the search space. A notable implementation is MiniSAT (Eén & Sörensson| 2003), lightweight and extensible open-source CDCL solver. Despite its minimalistic codebase, MiniSAT has become standard platform for both research and industrial applications due its clarity and efffcttiveness.
IMITSAT
S branching plays pivotal role in CDCL: the quality of branching decisions largely determines the efficiency of unit propagation, which is the dominant cost in practice. Traditional heuristics such VSIDS are highly effective but ultimately hand-crafted, leaving open the possibility of more principled approaches that can exploit structural patterns in solver traces. In this paper, we introduce ImitSAT, framework that leverages expert- guided sequence modeling to learn high-quality branching policies for CDCL solvers.
As reviewed in Section
propagation
conflict
decision
MiniSAT
88.9%
9.2%
1.9%
20
40
60
80
100
percentage total time
Propagation dominates CDCL time. MiniSAT spends about 88.9% in propagation, 9. 9.2% in conflict analysis, and 1.9% in branching. Reducing propagation is therefore the main route to wall-clock gains.
Figure 2:
Our approach consists of two main compo- nents: (i) KeyTrace construction, which com- presses solver runs by collapsing backtracks into concise sequence of expert decisions (Section 4.1 and (ii) autoregressive learner, which
4

---

Published as a conference paper at ICLR 2026
imitates the Rrycrraee to predict the next branching decision in sequence (Section 4.2) These com- ponents are seamlessly integrated into the CDCL framework. Together, they provide clean supervi- sion signals and enable plug-and woug-and-pul and-play deployment.
4.1 EXPERT KEYTRACE REPLAY
We seek an expert that guides the solver toward effective branching decisions while avoiding wasted detours. Raw CDCL trails are often long and contain many decisions that are later undone by backtracking. An ideal expert should preserve only the decisions that survive and discard detours, thereby yielding clean training targets and eliminating steps that do not advance the search. In CDCL, unit propagation dominates runtime, typically accounting for 80%-90% of the total solving time Zhang & Malik, 2002; Davis et al. 2008 Moskewicz et al. 2001). trend we also confirm in Figure This observation suggests that an expert which avoids wasted branches can substantially reduce propagation and thereby improve overall efficiency.
In order to extract expert supervision for branching, first examine the execution trace of CDCL solver. Each run on an instance F produces a trail, namely a chronological sequence of decision, propagation, and backtracking events annotated with decision levels:
T = ((TI, Å1, ,
(Te, Az, he))
(5)
where T; E {D, A, BT) representing a decision, a unit propagation assignment, or a backtrack event, respectively. A; is a signed variable with À; E {+1,.... tm). We interpret A; +j as Ijj T and X = jj as zj = L. The value h2 is the decision level after the event. Raw trails Tr are often long and contain numerous events that are eventually undone by backtracking. Such redundant segments do not contribute to solving progress, yet they inflate computational cost and inject noise into the context, making it harder to isolate the key decisions that drive the search.
To remove these detours, we construct an expert KeyTrace through a systematic extraction proce- dure. Specifically, scan T, from left to right while maintaining a working sequence I. that starts empty:
K 0.
For each event (Ti, As hi) we update
K. ll (D, Az hi),
if T2 D, T; = A, if T; BT,
K. (A, A1,
trimen, (A)) (D, A,, ha),
where || denotes concatenation. The operator trimŞN removes all suffix events whose level is above h. Restarts are handled by trimming level 0, i.e., IC + trimgu(K.). After the scan, the resulting sequence
K2 KC
taken the expert KeyTrace for trail Tr.
is worth noting that the above procedure preserves only the decision and propagation events that survive backtracking, effectively collapsing backtracks into prefix truncations while treating restarts as full resets. This results a considerably shorter and more stable trail representation, capturing the minimal necessary context for advancing the search.
Empirical evidence demonstrates that replaying the decision sequence encoded in Kr, on the same problem instance renders the solver's run nearly conflict-free, drastically reducing the number of propagation events to approximately 4% of those recorded in the raw MiniSAT trail see Figure Since propagation constitutes the dominant runtime component of CDCL solvers, this reduction translates directly into significant improvements in solver efficiency.
4.2 AUTOREGRESSIVE IMITATION FOR CDCL BRANCHING
Given this compact expert KeyTrace, our goal to train a learner that can imitate expert-quality branching decisions. In this setting, the expert demonstrations surviving decision, together with its implied propagations, forms a supervised training target. Unlike reinforcement-style exploration, this approach offers dense, step-level supervision and eliminates
provided by KeyTraces: each
5

---

Published as a conference paper at ICLR 2026
MiniSAT 100%
KeyTrace % of MiniSAT
conflict
0.2%
decision
19.6%
100
propagation
1.3%
100
20
40
60
80
100
percentage
Figure 3: Compact Key KeyTrace replay. The expert replayed only a small share of MiniSAT events: 0.2% conflicts, 19.6% decisions, and 4.3% propagations.
detours, allowing the learner to acquire high-quality decision policies with faster convergence and greater stability.
Formally, since a CDCL solver queries one branch at a time, the learning task is to map the for- mula I together with a KeyTrace prefix K, to the next signed variable, while operating under small computational budget. This task is inherently sequential, as each decision depends on the prefix of earlier assignments. An autoregressive (AR) model is therefore natural choice, as it con- ditions on the serialized prefix and predicts the next element in the sequence. To realize this, we first serialize the solver state into compact sequence tailored for autoregression, then specify the AR next-decision learner and its behavior-cloning objective, and finally describe how the learner is integrated into CDCL inference time.
Serialization. To make the AR learner effective, both the CNF F and the KeyTrrac prefix K are serialized into one deterministic sequence. The CNF written DIMACS integer format FDIMACS, followed by separator tokens [SEP]. The KeyTrrace is then presented as blocks, where each decision literal is followed by the unit assignments produced by propagation. Level fields and assignment tags omitted for compactness. The sequence ends with decision probe marker [D] that signals request for the next branch. Formally, with K, = ((11, m.)..... (Te, Ae, ht)).
enc(CG)) = |1:=_ (D, di, 0i,1, a..k))
dis ai, E (+1,...,tt,)
(9)
and the full serialized input
KG, [CNF] || FDimacs || [SEP] enc(Ke) [D]. This compact representation aligns exactly with next-decision prediction for an AR learner.
(10)
Next-decision AR learner.
The learner implements the policy
(>(exex
F, K,,,,,, Anext (=1,...,
(11)
using an AR model defined over 2 [, Kc).. For a generic sequence Z1..... Es. the AR factorization
(o rs) = II (o x<e),
(12)
s=1
where s is the index immediately following the decision probe marker [D]. Under this serialization,
predicting the next CDCL decision exactly next-symbol prediction at position
(neext F.K.) po Anext.
di =FFF
(13)
Training follows the standard behavior cloning paradigm in imitation learning. Let Q be the set of triples (F, Kr, d.41). Training minimizes the average negative log- ligeliill of the expert decisions:
(())
1
Σ
- log (d [=(F
(14)
Q
(F.KC,dc11)E
which is equivalent to cross- entropy at the decision probe positions. In other words, the learner directly imitates the expert policy encoded in the KeyTraces.

---

Published as a conference paper at ICLR 2026
Online integration into CDCL. At each decision point, the learner is queried under small bud- get. The current trail is collapsed into the KeyTrace, the instance and prefix are serialized, and the model predicts signed variable. If the prediction is legal (i.e., within the variable range and currently unassigned), the solver accepts it and decrements the query budget. Otherwise, the solver immediately falls back VSIDS heuristic. This design preserves completeness and keeps overhead small. A front-loaded query schedule is particularly effective, as early decisions strongly shape most of the search shown in Appendix E complete Algorithm (aahhmmm@eescri description is provided in Appendix
EXPERIMENTS
In this section, we evaluate ImitSAT as a learned branching policy for CDCL solvers. We first describe the experimental setup, including baselines, solver implementation, datasets, model, and evaluation metrics. We then compare ImitSAT with SATformer and Graph-Q-SAT on random 3- SAT test sets and on a range of structured SAT families. Wall clock behaviour studied both in Section (oction[5.44jnne and through direct comparison with pure MiniSAT in Appendix O and we also exam- ine generalization to industrial benchmarks from SATCOMP in Appendix MM] Finally, we summarize several additional analyses whose full results are deferred the appendices, including a query bud- get ablation, GNN augmented variant, a Top-K masking versus fallback study, and integrations with more advanced solvers such CaDiCal (Biere al. 2024a) and Kissat (Biere al. 2024b).
detailed in Appendices N and R
5.1 IMPLEMENTATION DETAILS
Baselines. We compare against SATformer (Shi et al. 2023) and Graph-Q-Sa QAST (Kurin et al. 2020), which are trained using their public implementations and specified training data. We also retrain them on our dataset, with equivalent training volume, denoted as SATformer* and GQSAT*.
CDCL Solver. A Python reimplementation of MiniSAT 2.2 (Eén & Sörensson, 2003 is used and validated against the official C++ version on full trails T. This version streamlines the integration of learning methods, ensuring that all approaches are evaluated a consistent environment.
Datasets. We generate the random SAST training dataset with a planted assignment (Mezard & Montanari 2009 Achlioptas et al. 2000 2005). The clause-variable ratio is in [4.1, 4.4]. Variable ranges include to 15, 16 to 30, 31 to 60, and 61 to 100, with additional fixed sizes of 50 and 100. For each formula, MiniSAT expert Key Trace is extracted using Equation| 7 Every decision position provides one supervision pair, KeyTrace prefix K., and its next decision de+1. For evaluation, we first use the test set, which is drawn from the same generators and variable ranges as those used for training. Generalization then assessed on different SAT families from SATLIB (Hoos & Stützle, 2000). Further dataset details appear in Appendix
yields the level-annotated trail as Equation 5 Then, the
AR learner and training. Perceiver AR (Hawthorne et al. 2022) serves as our architecture for predicting the next decision. Specifically, the model uses an output latent array that cross-attends to the input. Since only one output is needed for the next branching, we set the latent length to 1. This results in each query having (NN) complexity terms of input length, avoiding the ( cost associated with standard Transformer decoder. Furthermore, our model configuration follows the recommendations in (Hawthorne et al.) 2022). We use 16 attention heads for cross-attention and self-attention, 12 Transformer blocks, an MLP expansion of 4x, squared-Rele ReLL activations, and cross-attention dropout 0.1.
Metrics. Propagation dominates CDCL time
Zhhng & Malik 2002 Davis et al., 2008
in Figure and Table 6 We therefore the number of prop- agation as the primary signal. Since instances vary in size and difficulty, we normalize by MiniSAT on per-instance basis and aggregate with the median to reduce the influence of outliers.
Moskewicz al. 2001),
7

---

Published as a conference paper at ICLR 2026
Table 1: MRPP F (Q) and one percent win ratio W1% (1) on 3-SAT test sets. GQSAT denotes Graph- Q-SAT.
Metric
Method
5-15
16-30
31-60
61-100
50
100
KeyTrace
0.57
0.39
0.21
0.10
0.17
0.03
GQSAT-3call
1.00
0.94
0.89
1.15
0.71
0.85
GQSAT-5calls
1.00
0.90
0.82
0.94
0.70
0.80
SATformer
1.00
0.89
0.84
0.78
0.88
0.81
MRPP F (4)
GQSAT
1.38
1.36
1.46
1.59
1.37
1.41
(QSAT*-5cally
1,43
1.44
1.53
1.51
1.23
1,40
SATformer*
1.00
0.88
0.80
0.83
0.86
0.82
Ours-3calls
0.75
0.83
0.75
0.78
0.74
0.76
Ours-Scalls
0.73
0.77
0.75
0.80
0.66
0.83
KeyTrace
0.71
0.87
0.96
0.98
0.97
0.99
GQSAT-3calls
0.45
0.53
0.54
0.48
0.57
0.55
GQSAT-5calls
0.46
0.54
0.56
0.53
0.59
0.58
SATformer
0.48
0.55
0.58
0.57
0.60
0.57
W1% (1)
G
0.25
0.33
0.34
0.38
0.38
0.36
GQSAT
0.23
0.30
0.35
0.34
0.37
0.36
SATformer*
0.48
0.56
0.58
0.53
0.57
0.56
Ours-3calls
0.68
0.65
0.65
0.64
0.69
0.60
Ours-5calls
0.67
0.64
0.61
0.59
0.64
0.56
Let ps be the propagation count of the evaluated method on instance F;, and let p\ be the correspond- ing count for Min We report the Median Relative Propagation Percentage (MRPP)
med
(15)
values F < 1 indicate fewer propagation than MiniSAT and hence an improvement.
To capture instance-wise gains, we also report one-percent win rate. With margin 6 = 0.01
W.
Σ [p S (1 - 8) 81
(16)
N
This is the fraction of problems which the method reduces the propagation number by least 1% relative to MiniSAT; therefore, larger W1% is better.
5.2 COMPARISON ON TEST SETS
We compare ImitSAT with Graph-Q-SAT and SATformer on held-out random 3-SAT. To align wall- clock budgets, ImitSAT is queried at 3 or 5 times per instance. Graph-Q-SAT putational budgets. SATformer updates the VSIDS variable scores once at initialization. We report MRPP and the one percent win rate W1%. We also include the GQSAT* and SATformer* variants, which are trained on our random 3-SAT dataset to have a fair comparison. On the test set, GQSAT* performs much worse than GQSAT, while SATformer* remains close to SATformer.
the same com-
Table (top) shows that ImitSAT achieves the lowest MRPP F in nearly all ranges. With 3 or 5 calls, is best on 5-15, 16-30, 31-60, 50, 100, and ties SATformer on 61-100. These results indicate that imitation of the expert, as demonstrated by KeyTrace, consistently reduces propagation under small query budgets. Building on these MRPP results, Graph-Q-SS the 100 dataset, indicating weaker guidance under the same budget. Finally, in Table (bottom) we report W to show instance- wise gains. ImitSAT with 3 calls achieves the highest win rate in all ranges.
increases propagation number on
8

---

Published as a conference paper at ICLR 2026
Table 2: MRPP (L) and one percent win ratio Wi% (1) on structured SAT families.
Metric
Method
JNH
AIM
PARITY
PHOLE
PRET
KeyTrace
0.18
0.55
0.11
0.97
0.56
GQSAT-3calls
1.29
1.20
0.82
1.03
0.88
GQSAT-5calls
1.11
1.18
0.56
0.82
0.92
SATformer
1.36
1.01
0.73
1.00
1.00
MRPP F (4)
GQSAT*-3calls
1.39
1.15
0.66
1.05
1.00
GOSAT*-5calls
1.84
0.82
0.51
0.77
0.54
SATformer*
1.75
0.95
0.73
1.00
1.00
Ours-3calls
1.00
0.88
0.30
1.00
0.42
Ours-Scalls
0.85
0.81
0.30
0.82
0.42
KeyTrace
1.00
0.75
1.00
0.50
1.00
GQSAT-3calls
0.38
0.31
0.80
0.50
0.50
GQSAT-5calls
0.44
0.38
0.80
0.75
0.50
SATformer
0.25
0.44
0.60
0.00
0.00
W1% (1)
AT*Bcals
0.38
0.31
0.60
0.50
0.25
GQSAT
0.31
0.56
0.80
0.75
0.75
SATformer*
0.13
0.50
0.60
0.00
0.00
Ours-3calls
0.44
0.63
0.80
0.50
1.00
Ours-5calls
0.50
0.63
0.80
0.75
1.00
5.3 GENERALIZATION ON SPECIAL SAT FAMILIES
In this section, we assess the ability to transfer to structured families that differ from the training generator, covering SAT and UNSAT, 3-SAT, and non-k-SAT, without any retraining or tuning. Query budgets match the test sets, with or 5 calls per instance for ImitSAT and Graph-Q-SAT, whereas SATformer adjusts the VSIDS variable scores only once at initialization.
Across all families, ImitS AT attains the lowest MRPP or ties for best as shown in Table (top). The gains are large on PARITY and PRET, and with 5 calls ImitSAT best on JNH and AIM, and matches the best on PHOLE. Graph-Q-SAY does not reduce propagation number on JNH and AIM, and in fact increases the propagation number. SATformer only shows a gain on the PARITY dataset; all other datasets exhibit gain worse performance than MiniSAT. Table 2 (bottom) reports the W1.. ImitSAT achieves the highest or tied win rate on families, including perfect score on PRET and matching the best PARITY and PHOLE. These outcomes indicate that imitation of the expert KeyTrace transfers from random 3-SAT to structured regimes without finetuning. We report additional experiments on industrial benchmarks from SATCOMP (Iser & Jabs (024) in Appendix M using instances with at most 100 variables and a DIMACS encoding that fits within context budget. On this filtered subset, ImitSAT and SATformer solve the harder instances substantially faster in wall-clock time than Graph-Q-SAT under the same query budget as shwon in Figure
5.4 WALL-CLOCK TIME
To measure practical impact, end-to-end solve time is recorded for each instance. The timer starts when the CDCL solve loop begins and stops when the instance is solved; CNF parsing and sim- plification are excluded from the timing. All model inference costs are included. ImitSAT and Graph-Q-SAT receive 3 calls per instance match compute budgets. SATformer adjusts VSIDS variable scores once at initialization.
Across random 3-SAT test sets and structured families, ImitSAT traces the lowest curves under these budgets, which means more instances are solved in less time, as shown in Figure Learning model-bate branching introduces query overhead, wall-clock gains appear only once propaga- tion savings exceed this cost. We also compare ImitSAT directly with pure MiniSAT on 16-30, 3 31-60, and 61-100, summarized in Table 12 and detailed in Appendix O On the easier 16-30

---

Published as a conference paper at ICLR 2026
and 31-60 ranges, MiniSAT remains faster while ImitSAT is the strongest learned method and stays close in runtime; on the harder 61-100 range. ImitSAT achieves the lowest wall-clock time overall, showing that its propagation savings translate into net speedup once instances are sufficiently large and challenging.
120
Ours
175
Dur
Ours
Oun--Solle
150
OuroSccals SATSormet IQSAT OQSAT--calle
Qunseoulll
100
CQSSAT
SATTomnec
Wallelox Time
123
Wallelock Time
30
SATtomnnr CISAAT
G0SAF-Seall
100
Scall
Wallelock
60
20
20
do
Instances Solved
Instances Solved
Salved
(a) 5-15
(b) 16-30
(0) 31-60
Wallelock Time (S)
Wallelock Time (5)
2.5
SAThorme
20
SATERcuerr
Unire
Wallekock Time
0.20
Oura-Soalla RATOrmer DOSAT
0.8
COSAT Scalls
COSAT
1.5
Scalls
0.15
DOSAT-Scalle
1.0
0.3
0.3
Instances Solved
Instances Solved
Instances Solved PRET-UNSAT
AIM-SAT
(e) JNH-SAT
Figure 4: Wall-clock time versus instances solved on random test sets and structured families. Curves show end-to-end solver time per instance with all model calls included and preprocessing excluded. ImitSAT and Graph-Q-SAT use 3 calls per instance. SATformer performs a single VSIDS initialization. The lower curve better.
5.5 IMPROVED TRAINING TECHNIQUES
We observe that ImitaSAT is prone to overfitting. To address this issue, we introduce improved training techniques. First, apply variable permutation augmentation, where variable IDs randomly permuted when forming training examples. As shown in Figure S both training and val- idation losses decay steadily with augmentation, whereas without augmentation the validation loss peaks early and then rises despite continued decrease training loss. Second, we employ a staged curriculum learning strategy that gradually expands the variable range from small to large (Nagat- suka et al. 2021: Pouransari et al. 2024). This accelerates convergence on simple instances while ensuring comprehensive coverage of larger problem sizes. More details for variable permutation augmentation and curriculum learning are provided in Appendix and G
6 CONCLUSION
We presented ImitSAT, a CDCL branching policy based on imitation learning. By collapsing solver runs into compact sequences of surviving decisions, we obtain expert traces that capture high-quality branching behavior. These traces allow to formulate branching as autoregressive prediction problem, yielding dense, conflict-free supervision that enables stable and efficient training. Exten- sive experiments show that ImitSAT reduces propogations, achieves favorable runtime, and gener- alizes well beyond 3-SAT, outperforming prior learning-basee methods. Future work could extend this approach to richer expert demonstrations, hybrid broader domains of combinatorial reasoning.
learning schemes, or
ACKNOWLEDGMENTS
X. Xu acknowledges support from the National Natural Science Foundation of China (62302385).
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Dimitris Achlioptas, Carla Gomes, Henry Kautz, and Bart Selman. Generating satisfiable problem instances. In Proceedings of the AAAI/IAAI Conference, pp. 256-261, 2000.
Dimitris Achlioptas, Haixia Jia, and Cristopher Moore. Hiding satisfying assignments: two are better than one. Journal of Artificial Intelligence Research, 24:623-639, 2005.
Yuihci Asahiro, Kazuo Iwama, and Eiji Miyano. Random generation test instances with controlled attributes. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 377- 393, 1996.
Armin Biere, Marijn Heule, and Hans van Maaren. Handbook of satisfiability, volume 185. IOS press, 2009.
Armin Biere, Tobias Faller, Katalin Fazekas, Mathias Fleury, Nils Froleyks, and Florian Pollitt. CaDiCal, 2.0. In Arie Gurfinkel and Vijay Ganesh (eds.), Computer Aided Verification 36th International Conference, CAV 2024, Montreal, QC, Canada, July 24-27, 2024, Proceedings, Part I, volume 14681 Lecture Notes in Computer Science, pp. 133-152. Springer, 2024a. doi: 0-1199788---1---66777-
Armin Biere, Tobias Faller, Katalin Fazekas, Mathias Fleury, Nils Froleyks, and Florian Pollitt. CaDiCaL, Gimsatul, IsaSAT and Kissat entering the SAT Competition 2024. In Marijn Heule, Markus Iser, Matti Järvisalo, and Martin Suda (eds.). Proc. of SAT Competition 2024 Solver, Benchmark and Proof Checker Descriptions, volume B-2024-1 of Department of Computer Sci- ence Report Series B, pp. 8-10. University of Helsinki, 2024b.
Chris Cameron, Rex Chen, Jason Hartford, and Kevin Leyton-Browt Brown. Predicting propositional satis- fiability via end-to-end learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3324-3331 2020.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. In Advances in Neural Information Processing Systems, volume 34, pp. 15084 15097, 2021.
Stephen A Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing, pp. 151-158, 1971.
John D Davis, Zhangxi Tan, Fang Yu, and Lintao Zhang. A practical reconfigurable hardware ac- celerator for boolean satisfiability solvers. In Proceedings the 45th annual Design Automation Conference, pp. 780-785, 2008.
Niklas Eén and Niklas Sörensson. An extensible sat-solver. In International conference on theory and applications of satisfiability testing, pp. 502-518. Springer, 2003.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
Armin Haken. The intractability of resolution. Theoretical computer science, 39:297-308, 1985.
Xiaotian Han, Tong Zhao, Yozen Liu, Xia Hu, and Neil Shah. Mlpinit: Embarrassingly simple gnn training acceleration with mip initialization. In The Eleventh International Conference on Learning Representations, 2024.
Curtis Hawthorne, Andrew Jaegle, Cătälina Cangea, Sebastian Borgeaud, Charlie Nash, Mateusz Malinowski. Sander Dieleman, Oriol Vinyals, Matthew Botvinick, Ian Simon, al. General- purpose, long-context autoregressive modeling with perceiver ar. In International Conference on Machine Learning. pp. 8535 8558. PMLR. 2022.
He He, Hal Daumé, and Jason Eisner. Learning to search in branch and bound algorithms. In Advances in neural information processing systems, volume 27, 2014.

---

Published as a conference paper at ICLR 2026
Holger H. Hoos and Thomas Stützle. SATLIB: An online resource for research SAT. In I. P. Gent, H. van Maaren, and T. Walsh (eds.), SAT 2000, pp. 283-292. IOS Press, 2000. SATLIB is available online at http:// //wp: sat 1 ib. org
Alexey Ignatiev, Antonio Morgado, and Joao Marques-Silee PySAT: A Python toolkit for prototyp- ing with SAT oracles. In SAT, pp. 428 437, 2018. doi: 10. 001107/978---311 311199788--19999144--883 URL hittps://do....
0 1007/978 3-319- 94144- 8_26
Markus Iser and Christoph Jabs. Global Benchmark Database. In Supratik Chakraborty and Jie- Hong Roland Jiang (eds.). 27th International Conference on Theory and Applications of Sat- isfiability Testing (SAT 2024), volume 305 of Leibniz International Proceedings in Informat- ics (LIPics), pp. 18: 10: Dagstuhl, Germany, 2024, Schloss Dagstuhl Leibniz-Zentrum für Informatik. ISBN 978-3-95977-934-8. doi: /2wp://ettt./...23///PP...... SAT. 2024.
18. URL https:
7/
David S. Johnson and Michael A. Trick (eds.). Cliques, Coloring, and Satisfiability; The Second DIMACS Implementation Challenge, volume 26 of DIMACS Series Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1996.
Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller, James W. Thatcher, and Jean Bohlinger (eds.), Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85-103. Springer, Boston, MA, 1972. doi: 10.1007/ 978- 1144884-201-255
Elias Khalil, Pierre Le Bodic, Le Song. George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. Can q-learning with graph networks learn generalizable branching heuristic for sat solver? In Advances in Neural Infor- mation Processing Systems, pp. 9608-9621, 2020.
Zhaoyu Li, Jinpei Guo, and Xujie Si. G4satbench: Benchmarking and advancing sat solving with graph neural networks. Transactions on Machine Learning Research, 2024.
Hongduo Liu, Peng Xu, Yuan Pu, Lihao Yin, Hui-Ling Zhen, Mingxuan Yuan, Tsung- Yi Ho, and Bei Yu. Neuroselect: Learning to select clauses in sat solvers. In Proceedings of the 61 ACM/IEEE Design Automation Conference, pp. 1-6, 2024.
Zirui Liu, Chen Shengyuan, Kaixiong Zhou, Daochen Zha, Xiao Huang, and Xia Hu. Rse: accelerate graph neural networks training via randomized sparse computations. In International Conference on Machine Learning, pp. 21951-21968 PMLR, 2023.
Mare Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
Matthew W Moskewicz, Conor Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik. Chaff: Engineering an efficient sat solver. In Proceedings of the 38th annual Design Automation Con- ference, pp. 330-535, 2001.
Koichi Nagatsuka, Clifford Broni-Bediako, and Masayasu Atsumi. Pre-training a bert with curricu- lum learning by increasing block-size of input text. In Proceedings of the International Confer- ence on Recent Advances in Natural Language Processing (RANLP 2021). pp. 989-996,9099999 2021.
Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J Andrew Bagnell, Pieter Abbeel, Jan Peters, et al. An algorithmic perspective on imitation learning. Foundations and Trendy@ in Robotics, 7(1-2): 1-179, 2018.
Leyan Pan, Vijay Ganesh, Jacob Abernethy, Chris Esposo, and Wenke Lec. Can transformers reason logically? a study in SAT solving. In International Conference on Machine Learning, 2025. URL htttps://openreeee
net /ttp//ouumm-m--2222255550-1
David A Plaisted and Steven Greenbaum. A dimeture-presenvve clause form translation. Journal of Symbolic Computation, 2(3):293-304, 1986.
12

---

Published as a conference paper at ICLR 2026
Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neu- ral computation, 3(1):88 97, 1991.
Hadi Pouransari, Chun-Liang Li, Jen-Hao Chang, Pavan Kumar Anasosalu Vasu, Cem Koc, Vaishaal Shankar, and Oncel Tuzel. Dataset decomposition: Faster IIm training with variable sequence length curriculum. In Advances in Neural Information Processing Systems, volume 37, pp.
36121-36147, 2024.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):61-80, 2008.
Bart Selman, David G Mitchell, and Hector J Levesque. Generating hard satisfiability problems. Artificial intelligence, 81(1-2):17-29, 1996.
Daniel Selsam and Nikolaj Bjørner. Guiding high-performance sat solvers with unsat-core predic- tions. In International conference on 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 SAT solver from single-bit superviiion. International Conference on Learning Representations, 2019. URL [RRLLttts///ppeeeeeeeee
wwwp:erumteer. ?id HJMC iA5tm
Zhengyuan Shi, Min Li, Yi Liu, Sadaf Khan, Junhua Huang, Hui- Zhen, Mingxuan Yuan, and Qiang Xu. Satformer: Transformer-based unsat core learning. In 2023 IEEF/ACM International Conference on Computer Aided Design (ICCAD), pp. 1-4. IEEE, 2023.
JP Marques Silva and Karem Sakallah. Grasp-a new search algorithm for satisfiability. In Pro- ceedings of International Conference on Computer Aided Design, pp. 220-221 IEEE, 1996.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, volume 30, 2017.
Wenxi Wang, Yang Hu, Mohit Tiwari, Sarfraz Khurshid, Kenneth McMillan, and Risto Miikku- lainen. Neuroback: Improving CDCL SAT solving using graph neural networks. In The Twelfth International Conference on Learning Representations, 2024. URL
net htte//ooum?2i0 iic sdd.ddddssayuss
Joost P Warners and Hans Van Maaren. A two-phase algorithm for solving class of hard satisfia- bility problems. Operations research letters, 23(3-5):81-88, 1998.
Jiaxuan You, Haoze Wu, Clark Barrett, Raghuram Ramanujan, and Jure Leskovec. G2sat: Learning to generate sat formulas. In Advances in Neural Information Processing Systems, volume 32, 2019.
Maryam Zare, Parham M Kebria, Abbas Khosravi, and Saeid Nahavandi. A survey of imitation learning: Algorithms, recent developments, and challenges. IEEE Transactions on Cybernetics, 2024.
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and-boum search trees to learn branching policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3931-3939, 2021.
Shumao Zhai and Ning Ge. Learning splitting heuristics in divide-and-conquee SAT solvers with reinforcement learning. In The Thirteenth International Conference on Learning Representations, 2025. URL /ttttp:://ppereeee wttp://wwwweeettttnnteeeeeeeeeee idmuu (e0ruU0s17BBB. BBsMA
net forum?
Guibin Zhang. Xiangguo Sun, Yanwei Yue, Chonghe Jiang, Kun Wang. Tianlong Chen, and Shirui Pan. Graph sparsification via mixture of graphs. In The Thirleenth International Conference on Learning Representations, 2025.
Lintao Zhang and Sharad Malik. The quest for efficient boolean satisfiability solvers. In Interna- tional conference computer aided verification, pp. 17-36. Springer, 2002.
13

---

Published as a conference paper at ICLR 2026
A ALGORITHM
The integration of the CDCL and ImitSAT is shown in Algorithm
Algorithm Online CDCL branch with ImitSAT.
Require: CNF F. learner pe, total query budget B
Ensure: terminal outcome (SAT/UNSAT) or next branching decision Anext
1: < B
2: Ti < CURRENTTRAILL)
level-annotated trail as in Equation
3: if CONLICTAALLLVLIZRROT17 then
4: return UNSAT
5: end if
6: if (LLASSIGNED(T)) then
7: return SAT
8: end if
9: KG2 < EXTRACTKEYTRACH(TT
D collapse backtracks, Equation
10: i > O then
11: b-b-1
D consume one model query
12:
Anext < arg max (A (FF.C.))
13: LEuAL( F, T:) then
> unassigned and within the variable range
return Anext.
15: end
16: end if
17: return VSIDS(F, Tr)
>> fallback decision
B DATASETS
This section details the training corpus, held-out test sets, and the structured SAT families used in evaluation. For the synthetic data, both train and test, all instances are random 3-SAT with planted assignment and clause-variable ratio in [4.1, 4.4] (Mezard & Montanari 2009 Achlioptas et al. 2000 (005). We categorize instances by the number of variables n, to control difficulty and balance the number of decision probes contributed by each category. Since larger n. produces longer trails and thus more supervision per instance, we allocate fewer instances at larger ny This ensures each bucket contributes similar amount of training signal. We define buckets ranges of variable counts (e.g., "5-15"), with each bucket grouping instances by the number of variables ny they contain.
Training dataset. Counts denote the number of CNF instances per bucket.
Table 3: Training buckets for random 3-SAT with planted assignment.
Bucket (variables n.))
# Instances
5-15
2,000,000
16-30
1,000,000
31-60
500,000
61-100
100,000
50
1,000,000
100
100,000
Held-out test buckets. To keep evaluation time reasonable, we use fewer instances at larger n., For 1100, we increase the sample size reduce variance.
14

---

Published as a conference paper at ICLR 2026
Table 4: Held-out test buckets for random 3 3-SAT,
Bucket (variables n,))
# Instances
5-15
5,000
16-30
5,000
31-60
1,000
61-100
100
50
100
100
500
Structured families from SATLIB. To assess cross-distribution generalization, evaluate classic structured benchmarks from SATLIB (Hoos & Stützle, 2000). The suite spans both SAT and UNSAT, and includes 3-SAT and non-k-SAT regimes. Specifically,
AIM (Asahiro et al, 1996). which equivalent to 3-SAT, focusing on the nh 100 SAT portion. We also consider the SAT subset of JNH (Selman et al. 1996) with n. 100 and PARITY (Warners & Van Maaren Hoos & Stützle| 2000) 2000) in the compressed series, both as structured SAT families distinct from our random generator. Additionally, PRET (Johnson & Trick, 1996 Hoos & Stützle (2000 is
1998
two-coloring UNSAT problem with nhe 60, and the pigeonhole principle (PHOLE) (Haken 1985) used as a non-k k -AT and UNSAT stress test. All subsets described above are considered with n, < 100. Table 5 lists the families.
Table 5: The structured families referenced in generalization experiments are all sourced from SATLIB.
Family AIM
k-SAT?
SAT/UNSAT
3-SAT
SAT
JNH
non SAT
SAT
PARITY
BOA-
SAT
PHOLE
non-k-SAL SAT
UNSAT
PRET
non SASA
UNSAT
C CDCL RUNTIME BREAKDOWN
To quantify the main cost drivers in CDCL, we instrument the Python MiniSAT on the 61-100 test range and time each major component. Table 6 and Figure 2 show that propagation accounts for about 89% of the mean runtime, conflict analysis for about 9%, and decision selection for under 2%. Reducing needless propagation is therefore the most direct path wall-clock gains.
Table 6: The CDCL runtime breakdown the 61-100 test Propagation dominates the runtime, motivating metrics and methods that reduce propagation.
Event
mean ms
median ms
share of mean %
Propagation
65.624
38.378
88.88
Conflict
6,809
9.22 3.999
Decision
1.400
0.975
1.90
D KEYTRACE REPLAY
We confirm Key Trace is a suitable expert because replaying it yields a near conflict-free run with far fewer propagations. To demonstrate its effectiveness, for each instance, replay the extracted Key Trace by applying its decisions order and running unit propagation after each step. As shown in Table 7 and Figure the event counts during the KeyTrrace replay be compared to those of the
15

---

Published as a conference paper at ICLR 2026
original MiniSAT run. Notably, conflicts essentially eliminated, decisions drop by about 80%, and propagations fall to roughly 4% of the MiniSAT total. Together, these results support using Key Trace as the expert for behavior cloning: it isolates the surviving branch sequence and removes the detours that drive most propagation.
Table Effect KeyTrace replay on the 61-100 range. Means over instances and the share relative to MiniSAT. Replay is nearly conflict-rree and uses only small fraction of propagation.
Event
Mi mean
Key
KeyTrace % of MiniSAT
Conflict 71.96
0.11
0.15%
Decision
103.94
20.38
19.61% %
Propagation 1474.64
62.74
4.25%
EARLY DECISIONS SHAPE CDCL
In this section, we study how the timing of model queries affects the overall CDCL search.
We first compare two methods that use single model call and have identical compute budgets the 5-15 test set: (1) querying ImitSAT at the very first branching decision (call at first decision), and (2) making three branching decisions using the VSIDS heuristic before making single model query (call after VSIDS). We report MRPP 7 and W1% in T showing that delaying the single query (2) does not reduce propagations and substantially decreases the win rate, whereas front-loading the query (1) improves hoth metrics. This supports allocating the model budget to early decisions, as they exert strong influence the subsequent search.
To further investigate this effect on larger datasets, we evaluate three query strategies on the 100 test set and AIM: (a) three model calls after completing three VSIDS decisions (3 calls after VSIDS), (b) three model calls, each separated by three VSIDS decisions (3 calls, 1 per VSIDS), and (c) three model calls issued immediately the start of the search calls first decision). All subsequent decisions in each case use the native VSIDS heuristic. In Table 9 method (c) achieves the best MRPP and Wi 1i% indicating that simple greedy policy that spends the budget as early as possible is already strong baseline.
Table 8: Early guidance more effective. One model calls on the 5-15 test set. Front-loading the call at the first decision yields larger gains than delaying it.
Method
(L)
Wi% (f)
call after 3 VSIDS
1.00
0.27
call at first decision
0.91
0.55
Table Comparison of query heuristics. Using the model greedily the beginning of the search is much more effective than distributing calls across later VSIDS decisions.
Metric
Method
100
AIM
3 calls after 3 VSIDS
0.87
1.02
MRPP F (L)
3 calls, per VSIDS
0.95
1.09
calls at first decision
0.76
0.88
3 calls after 3 VSIDS
0.57
0.13
Wix V (t)
3 calls, per VSIDS
0.52
0.19
3 calls at first decision
0.60
0.63
16

---

Published as a conference paper at ICLR 2026
F VARIABLE PERMUTATION AUGMENTATION
Permutation augmentation is designed to mitigate overfitting and enhance the robustness of the learner. We train models on 5-15 variables for 20 epochs, or about 300k steps. Figure X plots the training and validation losses. With permutation augmentation, the two curves track each other and decay steadily. Without augmentation, the training loss continues to decrease, while the valida- tion loss peaks early and then rises, classic sign of overfitting variable identities. The aggregate metrics confirm this, as in Table that removing permutation leads to higher MRPP i and a low win rate, whereas the augmented model achieves a strong MRPP and a much higher win rate 1% The slightly higher training loss under augmentation is expected, as the task is more challenging: however, the gain is evident in generalization.
3.2
train
2.0
train
validation
1.8
validation
3.0
1.6
loss
2.8
1.2
2.4
1.0
80k
180k
240k
80k
160k
240k
steps
steps
(a) w/ pommuaation
(b) w/o permutation
Figure 5: Training and validation loss curves with and without prriable-permutativn augmentation on the 5-15 range for 20 epochs. Permutation keeps training and validation closely aligned and prevents overfitting, while removing it lowers training loss but drives validation loss up.
Table 10: Effect of variable-penee permutation augmentation. Models trained on 5-15 for 20 epochs. Augmentation prevents overfitting and improves test set metrics.
Method
i (L)
Wi% (1)
w/o permutation
1.00
0.28
w/ permutation
0.75
0.64
G STAGED CURRICULUM ACROSS VARIABLE RANGES
The staged curriculum is designed to accelerate learning and maintain competence across a wide range of variables (Nagatsuka al. 202T Pouransari al. 2024). The currieulum trains 5-15 for 20 epochs, then continues on 16 30 for 4 epochs, about 130k steps in the second stage. Two baselines are used on 16-30 without any curriculum. The first matches the second-stage budget by only about 130k steps. The second uses total of 430k steps that match the curriculum training steps.
Table summarizes the results. At the matched 130k steps budget on 16-30, the staged model achieves a much lower and a higher W1% than training the model "w/o stage" from scratch; this shows clear sample efficiency. When step counts are fully matched as "w/o stage*", training from scratch on 16-30 narrows the gap and slightly edges out the staged model that range. This suggests that the primary benefit of the curriculum is faster and more stable convergence, rather than better performance. Crucially, when the curriculum progresses through all stages, it preserves strong performance on 5-15, whereas models trained only 16-30 fail to generalize smaller instances.
17

---

Published as a conference paper at ICLR 2026
Table 11: Stage-training ablation. Ours curriculum that trains 5-15 for 300k steps, then continues on 16-30 for I 130k steps. The w/o stage trains only on 16-30 with the same second-stage budget, about 130k steps. And w/o stage* trains only on 16-30 with total of about 430k steps that matches the overall curriculum steps. Curriculum improves sample efficiency and yields better coverage of the 5-15 range.
Method
5-15 F (4)
5-15 Wix (f)
16-30 F (4)
16-15 W (1)
w/o stage
1.00
0.05
1.00
0.49
w/o stage*
1.00
0.43
0.80
0.66
w/ stage 0.75
0.67
0.83
0.63
H KEYTRACE EXAMPLE
This section walks through Figure on an example instance, showing short CDCL run and how it collapses into KeyTrace. Consider the CNF F over æ1, 22, T3, Jig.
F= (z) V -x3) (-r, -2 v va)
V V V=
(17)
A (~03 -I V -x1) (33 A 2
(~ V
One CDCL trail. CDCL run interleaves decisions (D). unit propagations (A), and backtracks (BT), each annotated with the decision level. One plausible trail is
T= (D. +4, 1), (D, +3,2), (BT, -3. 1); (BT, -,0), (D, (D,+1,1) 1), (D, +2, 2), (A,)3,2)
(18)
can be read in three stages, matching the left panel of Figure [ Stage I: branch F4 T, then Iy = T; a conflict is reached and the solver backtracks, forcing = L at lower level. Stage 2: second conflict occurs and the run backtracks level 0, flipping the earlier choice to 24 = 1. Stage T and 22 = T; unit propagation assigns 2: = and all clauses are satisfied, so F is declared SAT.
3: branch
Collapsing a KeyTrace. Applying the extraction rule Equation 7 trims away backtracked suffixes and keeps only the surviving root-to-current decisions. For the trail above, the resulting expert KeyTrace
= (BBT, 0, (D, +1,1111 1), (D, (A, (3, 2)),
(19)
ie., the final branch x = L = 22 = and then propagate I3 = 1 shown in the right panel of Figure I Replaying K. on the same instance with unit propagation between steps is nearly conflict-free and avoids the detours taken in the original run, which why KeyTrace provides clean targets for imitation.
I LARGE LANGUAGE MODELS (LLMs) USAGE STATEMENT
We used LLMs as general-purpose purpose assistants to scaffold small analysis or plotting scripts, suggest debugging tips, and polish wording. All technical ideas, algorithms, model designs, experiments, and reported results are the sole responsibility of the authors. LLM outputs were reviewed and edited for correctness and clarity. No proprietary data were provided to LLMs, and LLMs are not authors.
ETHICS STATEMENT
This work uses procedurally generated SAT instances and public SATLIE benchmarks; no human subjects or personally identifiable information are involved. The research poses minimal foresecable risks to society. We will relcase code and models under a permissive license to encourage transparent and responsible use.
18

---

Published as a conference paper at ICLR 2026
K REPRODUCIBILITY STATEMENT
We will release the following: (i) pretrained models; (ii) our Python reimplementation Min- iSAT 2.2, as well the integration code for ImitSAT; (iii) training code, including all hyperparame- ters; (iv) generators for random planted 3-SAT data, along with the exact train/test datasets; and (v)
environment specifications. The dataset definitions and splits detailed in Appendix B
L LIMITATIONS
The study limited by computational resources, all models were trained four V100 GPUs, which restricted both model size and training duration. To address these constraints, staged curricu- lum learning was used accelerate training. With greater access GPUs, it would be possible to train models for longer periods on larger datasets and scale model size, potentially leading to improvements in imitation quality and wall-clock performance.
M COMPARISON ON SATCOMP
To gauge performance on industrial-style problems, we also benchmark on subset SATCOMP instances (Iser & Jabs| 2024) that fits our current text-based interface. We focus on formulas with up to 100 variables whose DIMACS representation fits within the model context, so that the entire CNF can be passed to the policy without truncation. This yields set of real competition benchmarks with nontrivial structure that are compatible with our current model scale. Within this regime, MiniSAT, SATformer, GQSAT, and ImitSAT under the same query budgets in the main experiments, capping MiniSAT at 10 seconds per instance to keep the evaluation tractable. Figure reports mean wall-clock time over batches of 30 solved instances.
For the easier and medium batches, the three learned methods have very similar runtimes. On the hardest groups, however, GQSAT develops a much heavier time tail, while ImitSAT and SATformer remain substantially faster. Across this SATCOMP subset, ImitSAT matches SATformer and clearly improves wall-clock time over GQSAT the most challenging competition formulas. These results show that our evaluation already includes nontrivial SATCOMP instances within our size regime and that, this subset, Imi attains competitive or best wall-clock performance among the learned branching methods.
Ours
Mean Wallclock Time (s)
SATformer
GQSAT
2
30
60
120
150
180
Instances Solved
Figure 6: Wall-clock time on the SATCOMP subset. Instances are sorted by runtime and grouped into batches of 30 solved instances; the mean wall-clock time per group is plotted. Across the easier and medium groups. GQSAT, SATformer, and ImitSAT behave similarly, while on the hardest groups (rightmost), GQSAT develops much heavier time tail and is noticeably slower. In this regime, Am is the fastest and slightly outperforms SATformer wall-clock time.
19

---

Published as a conference paper at ICLR 2026
N QUERY BUDGET ANALYSIS
In this section, we study how the query budget, the number of times the solver consults the model during search, affects both effectiveness and computational cost. We vary the budget from 1 to 10 calls, and also include an all-calls configuration, to understand how much benefit each additional model query provides.
As shown in Figure 7 the performance gain exhibits clear diminishing returns: the majority of improvement obtained from the first three queries, while additional calls beyond six provide only marginal benefits. Because each query introduces non-trivial latency, interpret the reduction in propagations achieved by the model as a benefit that must be weighed against the computational overhead of issuing more queries. Based this trade-off, This choice is further supported by the wall-clock results Figure where GQSAT's runtime worsens noticeably the query budget increases from 3 to 5.
adopt a default budget of 3 queries.
0.90
66%
MRPP 7(L)
0.85
63%
0.80
60%
0.75
57%
0.70
1
6
10 all
1
3
6
10 all
Query Budget
Query Budget
Figure 7: Query budget ablation for ImitSAT on the 5-15 test set. MRPP F (left) and W1% (right) versus query budget with 1 to 10 calls and the all calls setting, showing that most of the benefit is obtained from the early calls.
O WALL-CLOCK TIME COMPARISON WITH MINISAT
In this section, we compare the wall-clock performance of ImitSAT with that of pure MiniSAT and with the other learned baselines. We measure the time (in seconds) required to solve 50 instances for each random 3-SAT range, including all model-inference overheads.
Table 12 reports the results. In the easier 16-30 range. MiniSAT is fastest, as expected, since each instance has few propagations and the cost of handful model calls dominates; nevertheless, Imit- SAT remains clearly faster than both GQSAT and SATformer in this regime. For the medium 31-60 range, ImitSAT and MiniSAT have almost identical wall-clock runtimes, and both are substantially faster than the other learned methods. In the 61-100 range, ImiISAT achieves the best wall-clock performance overall, outperforming MiniSAT, GQSAT, and SATformer. Combined with the MRPP i values below one in Tables [ and 2, these results show that the propagation reductions delivered by ImitSAT translate into net time gains once instances are large and hard enough, while keeping competitive with AT and ahead of other Iearned branching policies even smaller ranges.
P EVALUATION OF NAIVE GNN COMBINATION
To assess whether incorporating embeddings from a trained GNN encoder can improve ImitSAT, we design the following experiment. We adopt the GNN configuration from SATformer and train a besssage-passing encoder with a self-supervised objective, each true literal-clause edge is treated positive sample, and for each positive pair, we construct negative sample by pairing the same literal with a clause that does not contain it. This yields a GNN encoder that produces embeddings for the CNF formula, which then be consumed by downstream autoregressive model.
20

---

Published as a conference paper at ICLR 2026
Wall-clock time (seconds) to solve 50 instances random 3-SAT ranges. For each range, we select the 50 hardest test instances in reverse curriculum order to highlight behaviour on challenging problems. In the easier 16-30 and 31-60 ranges, ImitSAT is the strongest learned method: in the harder 61-100 range, ImitSAT AT attains the lowest wall-clock runtime overall.
Table 12:
Method GQSAT
16-30
31-60
61-100
1.47
3.26
7.72
SATformer
2.56
3.38
6.50
MiniSAT
0.53
2.54
6.44
ImitSAT
0.85
2.70
6.11
Table 13: Effect replacing the CNF tokens with GNN embeddings. MRPP F and Wi% on the 5-15 and 16-30 random 3-SAT test sets. The naive GNN-augmented variant underperforms the text-based ImitSAT.
Metric
Method
5-15
16-30
GNN embedding
1.00
0.99
MRPP F (1)
ImitSAT
0.75
0.83
use GNN embedding
0,46
0.50
W1% (1)
ImitSAT
0.68
0.65
Given the trained GNN, we replace the tokens between [CNF] and [SEP] with the correspond- ing variable emheddings. In other words, substitute the CNF token sequence with the
GNN-generated representation in an attempt to inject structural information into the model. We then train the Perceiver-AR model the 5-15 and 16-30 datasets using this modified input. How- ever, this naive GNN combination does not improve performance. As shown in Table 13 it in fact underperforms the text-only ImitSAT AT baseline.
In addition, the overall inference cost within the SAT solver must be taken into account. Augmenting the system with GNN introduces substantial computational overhead during both training and inference, and prior work has shown that GNNs are generally less GPU-friendly and scale poorly on large graphs (Zhang et al. 2025 Han al., 2024 Liu et al., 2023). Under this naive integration, the GNg-augmented variant is therefore neither more effective nor more efficient than the original text-based ImitSAT.
Q TOP-K AND FALLBACK ANALYSIS
This section studies the effectiveness of enforcing decision legality through Top-K masking strat- egy. We report the results of the Top-K K approach in Table which strictly masks invalid cases and selects the highest-scoring valid decision. On relatively simple on-distribution datasets such as 5-15, 16-30, and 31 31-60, we observe almost no difference between using or not using Top-K. However, on more challenging out-of-distribution datasets such as JNH and AIM, the Top-K approach leads to degraded performance. One possible cxplanation is low model confidence in these regimes. When the instance is difficult to model or the solver reaches a hard decision point, the confidence scores become flatter and the selected action is often suboptimal. In these cases, falling back to the original CDCL decision procedure is more reliable than forcing a low confidence model prediction, as shown in Table 14]
R INTEGRATION WITH ADVANCED SOLVERS
CaDiCaL. We first study how ImitSAT integrates with the modern CDCL solver CaDiCaL (Biere) et al. 2024a). using its PYSAT (Ignatiev et al.) 2018) interface and changing only the branching pol- icy. The preprocessing in CaDiCaL may outright solve small fraction of instances, metrics computed on the remaining instances, but this effect is modest across most benchmarks. Tables [5] and 16 report MRPP & and W under 3 and query budgets, against CaDiCal. default branch-
21

---

Published as a conference paper at ICLR 2026
Table 14: Effect of masking illegal literals with Top-K. MRPP i and W1% for ImitSAT with and
without Top-K in-distribution (5-15, 16-30, 31-60) and out-of-disrribution (JNH, AIM) test sets. Top-K performs similarly on easy instances but degrades on harder benchmarks, where simple fallback VSIDS performs better.
Metric
Method
5-15
16-30
31-60
JNH
AIM
w/ "Top---3aall
0.75
0.82
0.76
1.33
0.94
w/ --5alls
0.73
0.77
0.75
1.68
1.04
MRPP F (1)
w/o Top-K-3calls
0.75
0.83
0.75
1.00
0.88
w/o Top-K-5calls
0.73
0.77
0.75
0.85
0.81
"To----3call K-3calls
0.68
0.65
0.65
0.31
0,50
w/ Top--Ka --Scals
0.67
0.64
0.61
0.31
0.44
Wix (1)
w/o Slop-K3ccalle
0.68
0.65
0.65
0.44
0.63
w/o Top- K-Scals
0.67
0.64
0.61
0.50
0.63
Table 15: ImitSAT with CaDiCaL on random 3-SAT test sets. ratio W (t), where F is the ratio of propagations compared CaDiCal with its default branching (baseline = 1.0).
MRPP F (1) and one percent win
Metric
Method
5-15
16-30
31-60
61-100
50
100
CaDiCaL baseline
1.00
1.00
1.00
1.00
1.00
1.00
MRPP (1)
AT-3AATs
0.73
0.74
0.73
0.63
0.73
0.66
ImitSAT-Scalls
0.73
0.72
0.69
0.75
0.69
0.69
CaDiCaL baseline
0.00
0.00
0.00
0.00
0.00
0.00
Wix (1)
ImitSAT-3calls
0.73
0.68
0.66
0.62
0.62
0.64
ImitSAT-5calls
0.71
0.68
0.66
0.62
0.62
0.61
ing. On random 3-SAT test sets, ImitSAT consistently reduces MRPP 7 and attains strong win ratio W Wi%, and on structured families it yields clear gains on AIM, PARITY, PHOLE, and especially PRET. These results indicate that ImitSAT transfers effectively to advanced CDCL solver and improves its performance while only modifying the branching policy.
Table 16: ImitSAT with CaDiCaL on structured SAT families. MRPP F (L) and one percent win ratio Wix (t), where f is the ratio of propagations compared to CaDiCaL with its default branching
(baseline = 1.0).
Metric
Method
JNH
AIM
PARITY
PHOLE
PRET
CaDiCaL baseline
1.00
1.00
1.00
1.00
1.00
MRPP F (4)
ImitS AT-3all-
1.15
0.92
0.84
0.96
0.13
ImitSAT-Scalls
1.46
0.95
0.66
0.99
0.10
CaDiCaL baseline
0.00
0.00
0.00
0.00
0.00
Wix (1)
ImitS AmitSAT-3calls
0.33
0.63
0.80
0.67
1.00
AT-5calss
0.33
0.56
0.80
0.67
1.00
Kissat. Kissat (Berre et al. 2024b) is an aggressively engineered successor of CaDiCaL with heavy pre-/inprocessing. including probing and "lucky" assignments that try speculative assign- ments before and after preprocessing. On synthetic 3-SAT benchmarks, these mechanisms often solve the instance without making any CDCL decisions, so the branching callback is rarely invoked. Consistent with this, under the default configuration, the relative propagation statistics of Kissat and Kissat+ImitS AT are almost identical on most random buckets (MRPP 1.0), with noticeable im- provements only the structured datasets. To better isolate the effect of the branching policy, also consider a search-focused configuration that disables probing, while keeping all other options their defaults. Table [7 reports results on structured SAT families in this configuration.
22

---

Published as a conference paper at ICLR 2026
Table 17: ImitSAT with Kissat (probing disabled) on structured SAT families. For each family,
MRPP 8 (L) is the median ratio of propagations relative to Kissat without ImitSAT (baseline = 1.0),
and Wix 1% (f) is the fraction of instances where ImitSAT reduces propagations by at least 1%.
Metric
Method
JNH
AIM
PARITY
PHOLE
PRET
Kissat baseline
1.00
1.00
1.00
1.00
1.00
MRPP F (L)
IT-ISATs
0.98
0.94
0.90
0.95
0.21
ImicSAT-Scalls
1.00
1.03
0.81
0.96
0.06
Kissat baseline
0.00
0.00
0.00
0.00
0.00
Wis (t)
ImitSAT-3eas -calllss
0.50
0.56
0.80
0.75
1.00
AT-SSATs
0.44
0.44
0.80
0.75
1.00
23


Reviews:
[{"review_id": "4xm8rJrCYJ", "reviewer": "Reviewer_csYm", "summary": "Conflict Driven Clause Learning (CDCL) is the state of the art approach for solving boolean satisfiability (SAT) problems. During CDCL solving, the majority of the solving time is spent on unit propagation, the efficiency of which is heavily influenced by the branching decisions quality.\n\nThis paper introduces ImitSAT, which learns to branch in a CDCL solver using imitation learning. To do this, key traces are first extracted by collapsing a CDCL branching search tree into a single sequence of decisions. Then, an autoregressive learner is trained to predict the key traces sequentially through imitation learning. By learning to make better quality branching decisions, ImitSAT is able to cut down solving time. Experiments show that ImitSAT outperforms SATFormer and Graph-Q-SAT.", "questions": "How does the efficiency of ImitSAT maintain as the size of the SAT problem changes? To what sized instance can it generalize?\n\nHow is the query budget determined?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is easy to follow and the idea is simple but effective. \n\nThe method is well-motivated by the run-time analysis that propagation is the most time-consuming part of CDCL solving.\n\nThe algorithm introduces a budget for querying the model to ensure efficiency.\n\nThe approach shows good performance, beating Graph-Q-SAT and SATFormer on structured SAT families outside of training distribution.", "weaknesses": "The idea of using imitation learning for branching is not new. For example, it has been successfully applied to guide branch-and-bound for mixed integer programming [1,2].\n\nThe algorithm consumes the query budgets greedily, which, given the limited budget could potentially be far from optimal for instances larger than those in Appendix E. Are there simple heuristics that can improve this?\n\nThe experiments are on very small sized SAT problems, which provides limited insight to how ImitSAT can be used in practice.\n\nTraining is computationally expensive, since CDCL solvers are used to solve a problem entirely to produce a single key trace as a training instance. Therefore, the generalization ability of the method is crucial and calls for a deeper look. \n\n\n[1] He H, Daumé H, Eisner J. Learning to search in branch and bound algorithms. Advances in neural information processing systems. 2014;27.\n\n[2] Khalil E, Le Bodic P, Song L, Nemhauser G, Dilkina B. Learning to branch in mixed integer programming. InProceedings of the AAAI conference on artificial intelligence 2016 Feb 21 (Vol. 30, No. 1).", "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": "5l3MqO3hPK", "reviewer": "Reviewer_mcE8", "summary": "The paper introduces ImitSAT, a framework for learning a CDCL decision policy by imitation learning on condensed solver runs. This works by post-processing solver trails to eliminate intermediate conflicts and backtracking steps, which results in compact trails that only contain the key decisions made by the solver. In doing so, the model learns to imitate an improved version of the underlying solver, which can then be used to guide the solver decisions under a certain query budget. The authors compare their method to two other learned hybrid solvers, namely GQSAT and SATformer, in terms of solver-relative performance and wall-clock time on both in-distribution and out-of-distribution benchmarks. Results show that ImitSAT considerably outperforms both baselines on almost all benchmarks under a much lower runtime.", "questions": "1. Have you tried applying your method to industrial benchmarks like SATCOMP? It does not have to outperform the baseline solver, but it would be good to know where ImitSAT stands in real-world settings. \n2. How does the performance look if you only use the model decisions? \n3. Have you experimented with higher query budgets than 5? It would be interesting to plot performance over query budget. \n4. Equation (10) does not index $F_{DIMACS}$ by $t$, so is it always the original input formula? That is, does it not include the learned clauses? If so, wouldn't that compromise the decision optimality since the model does not see the clauses that were learned during the run? \n5. When the model's top answer is illegal, you fall back to the VSIDS heuristic. Why not mask out the illegal variable decisions from the model's output logits/probabilities? In doing so, you could use the model's top legal decision. \n6. In Figure 4, can you also include the time of the baseline un-augmented MiniSAT solver? \n7. Have you considered bootstrapping the training process by using the model to improve the trails dataset? For example, whenever the model produces a trail with fewer propagations, you could use the produced model trail for subsequent epochs instead of the KeyTrace one. \n8. Were the two baselines trained on the same 3-SAT dataset on which ImitSAT was trained, or were they trained on their original papers' datasets? \n9. Can you also include the KeyTrace ratios in Tables 1 & 2? \n10. To see the time scaling with query budgets, can you include the 5-call ImitSAT to Figure 4, possibly accompanied by higher query budget variants?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is clear and easy to follow. \n2. The key idea is fairly interesting: distilling a post-processed solver policy into a neural network. \n3. The authors compare their method against two somewhat recent baselines. \n4. The paper evaluates the method on both in-distribution and out-of-distribution instances.\n5. The method outperforms the reported baselines while having a lower runtime.", "weaknesses": "1. The authors do not evaluate their method on industrial instances, so it's unclear how well it scales to real-world settings. \n2. The attempted query budgets are quite low (up to 5 decisions), so it's unclear how well the method scales with higher budgets. \n3. Wall clock time comparisons are missing the pure VSIDS heuristic baseline (i.e., without the model), which would be the ultimate test to see if the proposed method speeds up the CDCL solver. \n4. It is unclear in Section 5.1 whether the SATformer and Graph-Q-SAT baseline models were pertrained on their original papers' dataset or on the same random 3-SAT dataset that ImitSAT was trained on. If it's the former, then the comparison in Table 1 is quite unfair since the baselines were trained on a different dataset. \n5. Using a text model is arguably not ideal for embedding formulas compared to GNNs as it fails to capture key properties such as invariance to clause permutation and variable renaming. However, I do understand that it might be more convenient to work with text.", "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": "9w7W2BwVQ8", "reviewer": "Reviewer_LTZA", "summary": "This paper studies SAT problem. As claimed by the authors, previous learning-based method were limited. In this work, they propose a branching policy for CDCL SAT solvers based on imitation learning. The authors conduct experiments to evaluate the effectiveness of their approach. They claim that their proposed method reduces propagation counts and outperforms previous learning-based method.", "questions": "Please reply to my comments listed in ‘Weaknesses’.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is generally well-written, with clear explanations.\n\n2. The description of the dataset construction method is detailed and reasonable.\n\n3. Experimental results are satisfactory.", "weaknesses": "1. What is the SAT solver integrated by SATformer in the experiment? According to the SATformer paper, combining it with CaDiCaL and Kissat can produce performance improvements.\n\n2. MiniSAT, used by ImitSAT, is relatively outdated. How does ImitSAT perform compared to current SOTA solvers (such as Kissat and CaDiCaL)? Can combining ImitSAT with these solvers bring further performance improvements?", "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)