Continuous Optimization for Satisfiability Modulo Theories on Linear Real Arithmetic
arXiv:2603.22877v1 Announce Type: new Abstract: Efficient solutions for satisfiability modulo theories (SMT) are integral in industrial applications such as hardware verification and design automation. Existing approaches are predominantly based on conflict-driven clause learning, which is structurally difficult to parallelize and therefore scales poorly. In this work, we introduce FourierSMT as a scalable and highly parallelizable continuous-variable optimization framework for SMT. We generalize the Walsh-Fourier expansion (WFE), called extended WFE (xWFE), from the Boolean domain to a mixed Boolean-real domain, which allows the use of gradient methods for SMT. This addresses the challenge of finding satisfying variable assignments to high-arity constraints by local updates of discrete variables. To reduce the evaluation complexity of xWFE, we present the extended binary decision diagram (xBDD) and map the constraints from xWFE to xBDDs. We then show that sampling the circuit-output
arXiv:2603.22877v1 Announce Type: new Abstract: Efficient solutions for satisfiability modulo theories (SMT) are integral in industrial applications such as hardware verification and design automation. Existing approaches are predominantly based on conflict-driven clause learning, which is structurally difficult to parallelize and therefore scales poorly. In this work, we introduce FourierSMT as a scalable and highly parallelizable continuous-variable optimization framework for SMT. We generalize the Walsh-Fourier expansion (WFE), called extended WFE (xWFE), from the Boolean domain to a mixed Boolean-real domain, which allows the use of gradient methods for SMT. This addresses the challenge of finding satisfying variable assignments to high-arity constraints by local updates of discrete variables. To reduce the evaluation complexity of xWFE, we present the extended binary decision diagram (xBDD) and map the constraints from xWFE to xBDDs. We then show that sampling the circuit-output probability (COP) of xBDDs under randomized rounding is equivalent to the expectation value of the xWFEs. This allows for efficient computation of the constraints. We show that the reduced problem is guaranteed to converge and preserves satisfiability, ensuring the soundness of the solutions. The framework is benchmarked for large-scale scheduling and placement problems with up to 10,000 variables and 700,000 constraints, achieving 8-fold speedups compared to state-of-the-art SMT solvers. These results pave the way for GPU-based optimization of SMTs with continuous systems.
Executive Summary
The article introduces FourierSMT, a novel framework that leverages an extended Walsh-Fourier expansion (xWFE) to enable scalable, parallelizable continuous-variable optimization for SMT problems involving linear real arithmetic. By generalizing the WFE to a mixed Boolean-real domain, the authors address scalability challenges inherent in traditional conflict-driven clause learning methods. The use of extended binary decision diagrams (xBDDs) and mapping constraints to these structures, coupled with the equivalence between sampling circuit-output probability (COP) and expectation values of xWFE, provides a novel computational pathway for efficient constraint evaluation. Benchmarking on large-scale problems demonstrates significant speedups, validating the framework’s practical efficacy. This work represents a meaningful advancement in SMT solving, particularly for applications requiring continuous systems.
Key Points
- ▸ Introduction of xWFE as a generalized Walsh-Fourier expansion for mixed domains
- ▸ Use of xBDDs to reduce evaluation complexity
- ▸ Demonstrated empirical speedups in large-scale applications
Merits
Scalability Innovation
The framework introduces a novel parallelizable approach that overcomes the limitations of conflict-driven clause learning, enabling efficient processing of high-arity constraints.
Computational Efficiency
By leveraging gradient methods and probabilistic equivalences, the authors enable efficient constraint evaluation without compromising soundness.
Demerits
Domain Constraint
The solution is specifically tailored to linear real arithmetic and may require adaptation for broader mixed-domain SMT applications.
Implementation Complexity
Mapping constraints to xBDDs and integrating xWFE extensions may introduce initial implementation barriers for existing SMT infrastructures.
Expert Commentary
This work represents a significant theoretical and practical leap in SMT solving. The innovation lies not only in the mathematical extension—extending the Walsh-Fourier to mixed Boolean-real domains—but in the architectural ingenuity of coupling this with xBDDs and probabilistic sampling equivalences. The authors demonstrate exceptional foresight by aligning computational efficiency with theoretical soundness, ensuring that the optimization framework preserves satisfiability. Furthermore, the benchmarking results, particularly the 8-fold speedup on large-scale problems, validate their claims with compelling empirical evidence. The implications extend beyond academia: the framework’s potential for GPU acceleration opens new avenues for real-time industrial applications. While the current scope is limited to linear real arithmetic, the architectural model is generalizable, suggesting future work may extend to nonlinear domains. This is not merely an incremental improvement—it is a paradigm shift in how continuous SMT problems are approached, and it sets a new standard for scalable SMT solvers.
Recommendations
- ✓ 1. Extend FourierSMT’s framework to support nonlinear real arithmetic constraints to broaden applicability.
- ✓ 2. Develop open-source implementations and benchmark suites to facilitate adoption by industry researchers and tool developers.
Sources
Original: arXiv - cs.AI
