Learning from Algorithm Feedback: One-Shot Sat Solver Guidance with GNNs

Jan Tönshoff, Martin Grohe · 2025

Read Learning from Algorithm Feedback: One-Shot Sat Solver Guidance with GNNs by Jan Tönshoff, Martin Grohe (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-16053.txt.

Introduction

SAT solvers sit under much of modern computing, and their speed hinges on branching choices usually tuned by hand. Jan Tönshoff and Martin Grohe let a solver teach its own guide. A graph neural network looks at a formula once and assigns every variable a weight and a preferred polarity, injected straight into the solver's branching rule.

Training treats the solver's running time as the only reward, a scheme they call reinforcement learning from algorithm feedback. The learned guides cut mean solve times sharply, sometimes more than twofold. Trained on small cases, they still helped on larger, harder ones. The 2025 results beat guides trained to imitate human-designed heuristics.

Catalog record

CREATORJan Tönshoff, Martin Grohe
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-16053

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning from Algorithm Feedback: One-Shot Sat Solver Guidance with GNNs Jan Tönshoff, Martin Grohe Abstract Boolean Satisfiability (SAT) solvers are foundational to computer science, yet their performance typically hinges on hand-crafted heuristics. This work introduces Reinforcement Learning from Algorithm Feedback (RLAF) as a paradigm for learning to guide SAT solver branching heuristics with Graph Neural Networks (GNNs). Central to our approach is a novel and generic mechanism for injecting inferred variable weights and polarities into the branching heuristics of existing SAT solvers. In a single forward pass, a GNN assigns these parameters to all variables. Casting this one-shot guidance as a reinforcement learning problem lets us train the GNN with off-the-shelf policy-gradient methods, such as GRPO, directly using the solver’s computational cost as the sole reward signal. Extensive evaluations demonstrate that RLAF-trained policies significantly reduce the mean solve times of different base solvers across diverse SAT problem distributions, achieving more than a 2x speedup in some cases, while generalizing effectively to larger and harder problems after training. Notably, these policies consistently outperform expert-supervised approaches based on learning handcrafted weighting heuristics, offering a promising path towards data-driven heuristic design in combinatorial optimization. 1 Introduction Solving computationally hard combinatorial problems, such as Boolean satisfiability ( Sat ), remains a cornerstone of computer science and is critical to diverse domains such as verification, planning, and cryptography ( Biere et al.,, 2021 ) . Complete search algorithms are of particular importance, as they are guaranteed to find a solution if one exists or prove unsatisfiability otherwise. The runtime of these classical algorithms heavily depends on hand-crafted heuristics to navigate the solution space, for example, by determining variable assignments during the search. Such heuristics are often rigid and hard to adapt to specific instance distributions without extensive expert knowledge and tuning. Machine learning offers a compelling alternative: Augmenting the heuristic components of classical search algorithms with trainable functions allows us to construct adaptable solvers. Specifically, reinforcement learning (RL) can train these extended solvers to learn improved, distribution-specific heuristics in a data-driven manner without direct expert supervision. In this work, we study how to leverage RL-trained Graph Neural Network (GNNs) to improve branching heuristics of Sat solvers. Our main contributions are as follows: First, we introduce a novel and generic method for integrating variable-wise weights into the branching heuristics of existing Sat solvers. Secondly, we construct a GNN-based policy that assigns a weight and polarity to each variable in one forward pass. This one-shot setting enables a single GNN pass to influence every branching decision, avoiding costly repeat passes. Thirdly, we phrase the task of inferring weights and polarities that reduce the solver’s cost as an RL problem. The reward signal is directly obtained from the observed computational cost of the guided Sat solver, requiring no expert supervision. We refer to this training paradigm as R einforcement L earning from A lgorithm F eedback (RLAF). Finally, we demonstrate empirically that modern RL techniques, such as GRPO ( Shao et al.,, 2024 ) , are capable of training effective RLAF policies for different base solvers. The learned policies substantially reduce solver runtimes, generalize to harder problems after training, outperform supervised baselines, and appear to capture solver-agnostic structural properties of Sat problems. 1.1 Background Sat Solving A Boolean formula in Conjunctive Normal Form (CNF) is a conjunction of clauses \phi=C_{1}\land\dots\land C_{m} , each clause being a disjunction of one or more literals C_{j}=(\ell_{j,1}\lor\dots\lor\ell_{j,k}) . We denote by \mathrm{Var}(\phi)=\{x_{1},\dots,x_{n}\} the set of Boolean variables of \phi . The Boolean Sat problem is to decide whether or not there exists a satisfying assignment \alpha:\mathrm{Var}(\phi)\rightarrow\{0,1\} that satisfies all clauses of a given formula \phi . This problem is well-known to be NP-complete and naturally arises in a wide range of applications ( Biere et al.,, 2021 ) . Modern Sat solvers predominantly stem from the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, a backtracking search approach enhanced by unit propagation and pure literal elimination. Algorithm 1 provides a pseudocode description of a DPLL Sat solver. Many extensions of this general idea have been proposed to scale Sat solvers to larger, industrial instances. In particular, Conflict-Driven Clause Learning (CDCL) solvers significantly extend the DPLL framework by introducing clause learning and non-chronological backtracking. A common property of DPLL-derived solvers is the importance of the branching heuristic that picks the next branching literal in each search step (line 11 in Algorithm 1 ). Various branching heuristics have been proposed, and which heuristic performs best often depends on the structure of the given Sat formula \phi ( Kullmann,, 2021 ) . Customizing branching heuristics towards a specific distribution of inputs generally requires expert knowledge and significant trial and error. Reinforcement Learning Reinforcement learning (RL) aims to learn policies for sequential decision-making problems where an agent interacts with an environment to learn through trial and error. An RL problem is usually formalized as a Markov Decision Process (MDP), which is defined as a tuple ({\mathcal{S}},{\mathcal{A}},P,R) , where {\mathcal{S}} is the set of states, {\mathcal{A}} is the set of possible actions, P denotes the transition probabilities between states and R is the reward function. In probabilistic settings, policies \pi are stochastic mappings from states to distributions over actions, i.e., \pi(a|s) indicates the probability of selecting action a in state s . More generally, for continuous action spaces, i.e. {\mathcal{A}}=\mathbb{R} , \pi(a|s) is the probability density that a policy assigns to an action a . The primary objective in RL is to determine an optimal policy \pi^{*} that maximizes the expected cumulative discounted reward \mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t})\right] , where \gamma\in[0,1) represents a discount factor that emphasizes earlier rewards. This formulation is the basis for various RL algorithms. Recently, RL algorithms based on policy gradients, such as PPO ( Schulman et al.,, 2017 ) and GRPO ( Shao et al.,, 2024 ) have been used extensively to fine-tune LLMs from human feedback (RLHF, Christiano et al., (2017) ; Ouyang et al., (2022) ) and from verifiable rewards (RLVR, Lambert et al., (2024) ; Guo et al., (2025) ). Algorithm 1 DPLL Solver 1: Input: Formula \phi 2: function Solve ( \phi ) 3: # Simplify formula 4: \phi\leftarrow Unit-Propagation ( \phi ) 5: \phi\leftarrow Pure-Literal-Elimination ( \phi ) 6: 7: if \phi=\emptyset : return Sat 8: if \emptyset\in\phi : return Unsat 9: 10: # Decide next branching variable 11: \ell\leftarrow Pick-Literal ( \phi ) 12: return Solve ( \phi\!\wedge\!\{\ell\} ) ​ \lor ​ Solve ( \phi\!\wedge\!\{\neg\ell\} ) 13: end function Algorithm 2 Decision Heuristic 1: Input: Formula \phi 2: function Pick-Literal ( \phi ) 3: \hat{x}\leftarrow\arg\!\max_{x}\textsc{Score}(x) 4: return \hat{x} if \textsc{Pick-Sign}(\hat{x}) else \lnot\hat{x} 5: end function Algorithm 3 Guided Decision Heuristic 1: Input: Formula \phi , Parameters {\mathcal{W}}\!=\!({\color[rgb]{0,0.5,0}w},{\color[rgb]{0,0.5,1}p}) 2: function Pick-Literal-Guided ( \phi,{\mathcal{W}} ) 3: \hat{x}\leftarrow\arg\!\max_{x}{\color[rgb]{0,0.5,0}w(x)}\cdot\textsc{Score}(x) 4: return \hat{x} if {\color[rgb]{0,0.5,1}p(\hat{x})=1} else \lnot\hat{x} 5: end function Figure 1 : DPLL Sat solver and branching heuristics. Algorithm 1 : A DPLL Sat solver performs backtracking search to solve a given CNF formula \phi . At each search step, the formula is simplified through unit propagation and pure literal elimination before selecting the next branching literal. Algorithm 2 : Branching heuristics are often implemented by choosing the variable that maximizes some hand-crafted scoring function. Algorithm 3 : We propose to extend existing branching heuristics by incorporating given

Read the complete text