Massively Parallel Continuous Local Search for Hybrid SAT Solving on GPUs

Yunuo Cen, Zhiwei Zhang, Xuanyao FongAAAI 2025 · DOI

TL;DR

This paper introduces FastFourierSAT, a novel SAT solver that leverages GPUs for massively parallel continuous local search. By reformulating SAT problems as polynomial optimization and using FFT-based techniques for efficient gradient computation, FastFourierSAT achieves significant speedups, particularly for hybrid SAT problems, and demonstrates promising scalability on larger instances.

What Problem Does This Paper Address?

The Boolean Satisfiability (SAT) problem is a fundamental challenge in computer science with applications spanning various domains. While state-of-the-art SAT solvers, particularly those based on Conflict-Driven Clause Learning (CDCL), have achieved remarkable success, their inherently sequential nature limits their ability to fully exploit the parallelism offered by modern hardware like GPUs. Continuous Local Search (CLS) methods offer an alternative by transforming SAT into a continuous optimization problem, but their performance has been bottlenecked by slow gradient computations. This paper addresses the challenge of accelerating CLS-based SAT solving by developing a massively parallel approach that can effectively utilize GPU resources.

Methods

The core innovation of this paper lies in the development of FastFourierSAT, a hybrid SAT solver that combines Continuous Local Search (CLS) with GPU acceleration. The key technical contributions are:

  • FFT-based Convolution for ESPs: The paper proposes a parallel algorithm inspired by the Fast Fourier Transform (FFT) for efficiently computing Elementary Symmetric Polynomials (ESPs). ESPs are a crucial component in previous CLS methods for evaluating the Walsh expansion (WE) of constraints. This new algorithm allows for vectorized evaluation of WEs, matching the best known complexity of O(k²) for gradient computation for a constraint of length k.
  • GPU Acceleration: The FFT-based approach is inherently parallelizable, enabling it to leverage the GPU's architecture. The authors exploit three levels of parallelism: data-level (SIMD), instruction-level, and thread-level, mapping them to the GPU's hierarchy of threads, warps, and streaming multiprocessors.
  • Autodiff for Gradient Computation: The paper utilizes an automatic differentiation (Autodiff) approach. By constructing an evaluation trace of the WE computation, gradients can be efficiently computed by traversing this trace backward. This allows for a theoretical ideal execution time of O*(log k) with unlimited resources.
  • Hybrid MaxSAT Integration: For MaxSAT problems, the authors integrate FastFourierSAT with CDCL solvers. This involves using CDCL to solve hard constraints and then using the found solutions to warm-start the CLS component, leading to a solver named FastFourierMaxSAT.

Datasets

The paper evaluates FastFourierSAT on several benchmarks:

  • Benchmark 1 (Gradient Computation Time): Synthetic instances with varying numbers of cardinality constraints and lengths.
  • Benchmark 2 (Hybrid SAT Formulas): Includes random cardinality constraints and parity learning with error problems.
  • Benchmark 3 (Hybrid MaxSAT for graph problems): Graph coloring and Hamiltonian cycle problems encoded with hybrid constraints.
  • Benchmark 4 (SAT Competition (SC) and MaxSAT Evaluation (MSEval) 2023): Selects satisfiable instances from SC'23 and unweighted instances from the anytime track in MSEval'23.

No new benchmarks were introduced; instead, existing problem types were used to evaluate the solver's performance.

Key Insights and Ideas

  • FFT as a Game-Changer for CLS: The paper demonstrates that by applying FFT-based techniques to the computation of ESPs, a significant bottleneck in CLS-based SAT solvers can be overcome. This unlocks the potential for massive parallelism.
  • GPU's Natural Fit for CLS: The inherent structure of the FFT-based approach aligns well with GPU architectures, allowing for substantial speedups through data-level, instruction-level, and thread-level parallelism.
  • CLS as a Complement to CDCL: While CDCL solvers remain dominant for standard CNF problems, CLS, especially when accelerated by GPUs, shows promise for tackling hybrid constraints and non-CNF problems where CDCL might struggle or be less efficient.
  • Autodiff Simplifies Gradient Calculation: The use of Autodiff streamlines the process of computing gradients, making the implementation more manageable and efficient.

Key Results

  • Gradient Computation Speedup: FastFourierSAT on GPU computes gradients over 100 times faster than previous CPU-based CLS algorithms (GradSAT and FourierSAT). For the largest instances in Benchmark 1, speedups of up to 472x and 1280x were observed compared to GradSAT and FourierSAT, respectively.
  • Scalability: FastFourierSAT demonstrates promising scalability on larger instances, outperforming previous CLS methods.
  • Performance on Hybrid Problems: For hybrid SAT problems (Benchmark 2), FastFourierSAT (both CPU and GPU versions) could solve all instances, outperforming some CDCL solvers that struggled with these problem types.
  • MaxSAT Performance: In MaxSAT benchmarks (Benchmark 3 and 4), FastFourierMaxSAT showed competitive performance, especially when leveraging CDCL for initialization, though it did not surpass top-tier solvers from competitions for highly engineered CNF problems.
  • GPU vs. CPU: While the GPU implementation of FastFourierSAT generally offers significant speedups, the CPU version also shows substantial improvements over prior CLS solvers due to the vectorized approach.

Limitations and Future Work

  • Rounding Errors: The paper acknowledges that rounding errors in Walsh coefficients and frequency domain computations can affect numerical stability. While they used higher bit precision, they suggest exploring computationally efficient methods for improving numerical stability.
  • Completeness: CLS is an incomplete framework, meaning it cannot prove unsatisfiability. The authors suggest exploring global optimization techniques, such as using the Moreau envelope, to potentially improve completeness guarantees.
  • Industrial-Scale CNF Problems: For highly engineered CNF problems from competitions, FastFourierSAT (and CLS in general) may not be competitive with mature CDCL solvers due to the latter's arc-consistency and efficient propagation mechanisms. The encoding of these problems into hybrid formats can lead to extremely large formulas.
  • Future Work: The authors are interested in developing global optimizers for CLS and studying their completeness. They also aim to explore more computationally efficient methods for numerical stability.

Summary updated

BibTeX
@inproceedings{cen2025massively,
  author = {Yunuo Cen and Zhiwei Zhang and Xuanyao Fong},
  title = {{Massively Parallel Continuous Local Search for Hybrid SAT Solving on GPUs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33211},
}
Figure