On Continuous Local BDD-Based Search for Hybrid SAT Solving

Anastasios Kyrillidis, Moshe Y. Vardi, Zhiwei Zhang

Introduction

The Boolean Satisfiability problem (SAT) remains a cornerstone of computational complexity. While modern solvers have achieved remarkable efficiency in handling formulas in Conjunctive Normal Form (CNF), they often encounter significant performance bottlenecks when faced with "hybrid" constraints. These complex logical structures—including XOR constraints used in cryptography, cardinality constraints (e.g., "at least $k$ variables must be true"), and Pseudo-Boolean constraints—frequently appear in real-world optimization and verification tasks.

Standard approaches typically involve encoding these complex constraints into simple CNF. However, this process often leads to an explosion in the number of variables and clauses, severely hindering search performance. Continuous Local Search (CLS) offers an alternative by relaxing discrete variables into a continuous range, allowing the use of calculus-based optimization. Historically, CLS methods like FourierSAT have been limited by the high computational cost of gradient calculation or a restricted range of supported constraint types. This paper introduces GradSAT, a framework designed to overcome these limitations by bridging discrete logic and continuous optimization through Binary Decision Diagrams (BDDs).

The GradSAT Framework: Differentiable Logic

GradSAT represents constraints using Binary Decision Diagrams (BDDs) rather than the algebraic polynomials employed by previous state-of-the-art methods. BDDs are compact, graph-based data structures capable of representing complex logic functions efficiently. The core innovation of GradSAT lies in its treatment of satisfiability as a continuous objective function.

The authors demonstrate that evaluating the "satisfiability" of a constraint within a continuous space is mathematically equivalent to calculating the circuit-output probability on its corresponding BDD. This allows the solver to frame the search for a satisfying assignment as a maximization problem over a continuous cube.

Efficient Gradient Computation

A critical bottleneck in continuous SAT solving is the cost of finding the gradient—the direction of steepest improvement. GradSAT addresses this with a novel belief-propagation-inspired algorithm. By performing a top-down and bottom-up pass over the BDD, the solver can compute gradients for all variables simultaneously in $O(S)$ time, where $S$ is the size of the BDD.

Algorithm 2: The Probability-Assignment Algorithm, which forms the basis for evaluating satisfiability in a continuous space.

This efficiency means that determining the optimal direction to move in the search space is now as computationally "cheap" as evaluating the current state. Furthermore, GradSAT utilizes Multi-Rooted BDDs (MRBDDs) to share sub-structures between different constraints, significantly reducing the memory footprint for large-scale problems.

Empirical Evaluation and Results

The researchers evaluated GradSAT against a variety of benchmarks, including hybrid random formulas (CNF, XOR, Cardinality, and Pseudo-Boolean mixtures) and 570 instances from the 2016–2019 MaxSAT Competitions.

GradSAT demonstrated substantial performance gains over previous continuous search methods. As shown in the table below, GradSAT achieved a 6x to 15x speedup in gradient computation compared to FourierSAT on standard CNF benchmarks.

Performance comparison showing the acceleration achieved by GradSAT over FourierSAT across different instance types.

Beyond speed, GradSAT proved highly versatile. On hybrid constraints, it outperformed all other tested local search and CDCL solvers, trailing only RoundingSAT (a specialized complete solver). In MaxSAT benchmarks, the GradSAT portfolio achieved higher average scores and more "wins" (finding the best-known solution) than established solvers like WalkSAT and Loandra.

Discussion and Future Directions

While GradSAT excels at random and crafted benchmarks, challenges remain for industrial-scale instances involving hundreds of thousands of variables, where the overhead of BDD construction and traversal becomes significant. Additionally, while GradSAT handles XORs more effectively than many local searchers, it still lags behind CDCL solvers on XOR-rich formulas due to "solution-space shattering," where valid solutions are too fragmented for continuous paths to be easily found.

Future work will focus on implementing more sophisticated dynamic weighting schemes for MaxSAT and exploring Stochastic Gradient Descent (SGD) to further reduce the computational burden on massive industrial problems. By treating logic as a differentiable landscape, GradSAT opens new avenues for solving the most challenging classes of Boolean constraints.

Summary updated

Abstract

We explore the potential of continuous local search (CLS) in SAT solving by proposing a novel approach for finding a solution of a hybrid system of Boolean constraints. The algorithm is based on CLS combined with belief propagation on binary decision diagrams (BDDs). Our framework accepts all Boolean constraints that admit compact BDDs, including symmetric Boolean constraints and small-coefficient pseudo-Boolean constraints as interesting families. We propose a novel algorithm for efficiently computing the gradient needed by CLS. We study the capabilities and limitations of our versatile CLS solver, GradSAT, by applying it on many benchmark instances. The experimental results indicate that GradSAT can be a useful addition to the portfolio of existing SAT and MaxSAT solvers for solving Boolean satisfiability and optimization problems.
BibTeX
@inproceedings{kyrillidis2021continuous,
  author = {Anastasios Kyrillidis and Moshe Y. Vardi and Zhiwei Zhang},
  title = {{On Continuous Local BDD-Based Search for Hybrid SAT Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=A40vxBBclVS},
}
Figure