# NLocalSAT: Boosting Local Search with Solution Prediction

arXiv: https://arxiv.org/abs/2001.09398 · HTML: https://mlsanity.com/paper/2001.09398/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2020.

## Built on by (most cited first, 25 of 25)

- [A Syntax-Guided Edit Decoder for Neural Program Repair](https://mlsanity.com/paper/2106.08253/) (2021)
- [One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction](https://mlsanity.com/paper/2208.10227/) (2022)
- [Machine Learning Methods in Solving the Boolean Satisfiability Problem](https://mlsanity.com/paper/2203.04755/) (2022)
- [NSNet: A General Neural Probabilistic Framework for Satisfiability Problems](https://mlsanity.com/paper/2211.03880/) (2022)
- [G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networks](https://mlsanity.com/paper/2309.16941/) (2023)
- [SATformer: Transformer-Based UNSAT Core Learning](https://mlsanity.com/paper/2209.00953/) (2022)
- [HardSATGEN: Understanding the Difficulty of Hard SAT Formula Generation and A Strong Structure-Hardness-Aware Baseline](https://mlsanity.com/paper/2302.02104/) (2023)
- [DeepSAT: An EDA-Driven Learning Framework for SAT](https://mlsanity.com/paper/2205.13745/) (2022)
- [Efficient Rectification of Neuro-Symbolic Reasoning Inconsistencies by Abductive Reflection](https://mlsanity.com/paper/2412.08457/) (2024)
- [Generalized Equivariance and Preferential Labeling for GNN Node Classification](https://mlsanity.com/paper/2102.11485/) (2021)
- [Can Graph Neural Networks Learn to Solve MaxSAT Problem?](https://mlsanity.com/paper/2111.07568/) (2021)
- [Circuit Transformer: A Transformer That Preserves Logical Equivalence](https://mlsanity.com/paper/2403.13838/) (2024)
- [Addressing Variable Dependency in GNN-based SAT Solving](https://mlsanity.com/paper/2304.08738/) (2023)
- [Understanding GNNs for Boolean Satisfiability through Approximation Algorithms](https://mlsanity.com/paper/2408.15418/) (2024)
- [Application of AI to formal methods - an analysis of current trends](https://mlsanity.com/paper/2411.14870/) (2024)
- [Structure based SAT dataset for analysing GNN generalisation](https://mlsanity.com/paper/2502.11410/) (2025)
- [HyperSAT: Unsupervised Hypergraph Neural Networks for Weighted MaxSAT Problems](https://mlsanity.com/paper/2504.11885/) (2025)
- [MILP-SAT-GNN: Yet Another Neural SAT Solver](https://mlsanity.com/paper/2507.01825/) (2025)
- [Learning Interpretable Heuristics for WalkSAT](https://mlsanity.com/paper/2307.04608/) (2023)
- [Machine Learning for SAT: Restricted Heuristics and New Graph Representations](https://mlsanity.com/paper/2307.09141/) (2023)
- [Using deep learning to construct stochastic local search SAT solvers with performance bounds](https://mlsanity.com/paper/2309.11452/) (2023)
- [IB-Net: Initial Branch Network for Variable Decision in Boolean Satisfiability](https://mlsanity.com/paper/2403.03517/) (2024)
- [Transfer Learning from Foundational Optimization Embeddings to Unsupervised SAT Representations](https://mlsanity.com/paper/2604.15448/) (2026)
- [Unsat Core Prediction through Polarity-Aware Representation Learning over Clause-Literal Hypergraphs](https://mlsanity.com/paper/2605.04819/) (2026)
- [Target-Aware Data Augmentation for SAT Prediction](https://mlsanity.com/paper/2605.06931/) (2026)

## Abstract (arXiv)

The Boolean satisfiability problem (SAT) is a famous NP-complete problem in computer science. An effective way for solving a satisfiable SAT problem is the stochastic local search (SLS). However, in this method, the initialization is assigned in a random manner, which impacts the effectiveness of SLS solvers. To address this problem, we propose NLocalSAT. NLocalSAT combines SLS with a solution prediction model, which boosts SLS by changing initialization assignments with a neural network. We evaluated NLocalSAT on five SLS solvers (CCAnr, Sparrow, CPSparrow, YalSAT, and probSAT) with instances in the random track of SAT Competition 2018. The experimental results show that solvers with NLocalSAT achieve 27% ~ 62% improvement over the original SLS solvers.