mlsanityData to 7 Oct 2026

NLocalSAT: Boosting Local Search with Solution Prediction

arXiv 2001.09398 ↗First posted 26 Jan 2020cs.AIcited by 25

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 6; 2024: 5; 2025: 3; 2026: 3.

25 papers.

Sort:

By area:

  1. 2021A Syntax-Guided Edit Decoder for Neural Program Repaircited by 57
  2. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  3. 2022Machine Learning Methods in Solving the Boolean Satisfiability Problemcited by 22
  4. 2022NSNet: A General Neural Probabilistic Framework for Satisfiability Problemscited by 18
  5. 2023G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networkscited by 17
  6. 2022SATformer: Transformer-Based UNSAT Core Learningcited by 14
  7. 2023HardSATGEN: Understanding the Difficulty of Hard SAT Formula Generation and A Strong Structure-Hardness-Aware Baselinecited by 12
  8. 2022DeepSAT: An EDA-Driven Learning Framework for SATcited by 11
  9. 2024Efficient Rectification of Neuro-Symbolic Reasoning Inconsistencies by Abductive Reflectioncited by 9
  10. 2021Generalized Equivariance and Preferential Labeling for GNN Node Classificationcited by 7
  11. 2021Can Graph Neural Networks Learn to Solve MaxSAT Problem?cited by 5
  12. 2024Circuit Transformer: A Transformer That Preserves Logical Equivalencecited by 5
13 more
  1. 2023Addressing Variable Dependency in GNN-based SAT Solvingcited by 3
  2. 2024Understanding GNNs for Boolean Satisfiability through Approximation Algorithmscited by 3
  3. 2024Application of AI to formal methods - an analysis of current trendscited by 2
  4. 2025Structure based SAT dataset for analysing GNN generalisationcited by 1
  5. 2025HyperSAT: Unsupervised Hypergraph Neural Networks for Weighted MaxSAT Problemscited by 1
  6. 2025MILP-SAT-GNN: Yet Another Neural SAT Solvercited by 1
  7. 2023Learning Interpretable Heuristics for WalkSATcited by 0
  8. 2023Machine Learning for SAT: Restricted Heuristics and New Graph Representationscited by 0
  9. 2023Using deep learning to construct stochastic local search SAT solvers with performance boundscited by 0
  10. 2024IB-Net: Initial Branch Network for Variable Decision in Boolean Satisfiabilitycited by 0
  11. 2026Transfer Learning from Foundational Optimization Embeddings to Unsupervised SAT Representationscited by 0
  12. 2026Unsat Core Prediction through Polarity-Aware Representation Learning over Clause-Literal Hypergraphscited by 0
  13. 2026Target-Aware Data Augmentation for SAT Predictioncited by 0