A Hybrid SMT-NRA Solver: Integrating 2D Cell-Jump-Based Local Search, MCSAT and OpenCAD
Organizations: Peking University, China · Zhongguancun Laboratory, China
Abstract
In this paper, we propose a hybrid framework for Satisfiability Modulo the Theory of Nonlinear Real Arithmetic (SMT-NRA for short). First, we introduce a two-dimensional cell-jump move, called 2D-cell-jump, generalizing the key operation, cell-jump, of the local search method for SMT-NRA. In contrast to the existing cell-jump, which updates assignments exclusively along a given line, the 2D-cell-jump enables search over an arbitrarily selected plane. Then, we propose an extended local search framework, named 2D-LS (following the existing local search framework, LS, for SMT-NRA). Finally, we present a hybrid framework for SMT-NRA integrating 2D-LS, MCSAT and OpenCAD, to improve search efficiency through information exchange. The experimental results demonstrate improvements in local search performance, highlighting the effectiveness of the proposed methods.
Figures & tables
| ID | Research Question | Evidence |
|---|---|---|
| RQ1 | How does the performance of HELMS compare to SOTA SMT solvers in the context of SMT-NRA? | Observation 1, 6 |
| RQ2 | Does the integration of MCSAT, local search, and OpenCAD successfully combine their individual advantages? | Observation 2, 3 |
| RQ3 | What are the specific advantages of extending the local search range from 1D to 2D (2D-LS)? | Observation 4, 5 |
| RQ4 | How do the three stages of HELMS contribute to performance, and are alternative stage combinations effective? | Observation 7, 8 |
| Baseline Solvers | SOTA Solvers | |||||||
| Benchmark | LS | LiMbS | HELMS | Z3 | CVC5 | MathSAT5 | Yices2 | |
| SMTLIB (2139) | #SAT | 1513 | 1524 | 1547 | 1552 | 1520 | 1308 | 1544 |
| #UNSAT | - | 574 | 578 | 576 | 575 | 462 | 576 | |
| #ALL | 1513 | 2098 | 2125 | 2128 | 2095 | 1770 | 2120 | |
| RandInst (100) | #SAT | 100 | 57 | 100 | 17 | 0 | 0 | 23 |
| SpecInst (21) | #SAT | 4 | 7 | 7 | 7 | 4 | 1 | 3 |
| HELMS Components | |||||
| Benchmark | 2D-LS | LiMbS | OpenCAD | HELMS | |
| SMTLIB (2139) | #SAT | 1546 | 1524 | 1544 | 1547 |
| #UNSAT | - | 574 | 577 | 578 | |
| #ALL | 1546 | 2098 | 2121 | 2125 | |
| RandInst (100) | #SAT | 100 | 57 | 0 | 100 |
| SpecInst (21) | #SAT | 7 | 7 | 2 | 7 |
| Stages of HELMS | HELMS Variants | |||||||||
| Benchmark | Stage 1 | Stage 2 | Stage 3 | HELMS | V1 | V2 | V3 | V4 | V5 | |
| SMTLIB (2139) | #SAT | 1546 | 1 | 0 | 1547 | 1546 | 1546 | 1546 | 1547 | 1546 |
| #UNSAT | 0 | 573 | 5 | 578 | 575 | 577 | 574 | 576 | 575 | |
| #ALL | 1546 | 574 | 5 | 2125 | 2121 | 2123 | 2120 | 2123 | 2121 | |
| RandInst (100) | #SAT | 100 | 0 | 0 | 100 | 100 | 100 | 100 | 15 | 100 |
| SpecInst (21) | #SAT | 7 | 0 | 0 | 7 | 5 | 4 | 7 | 5 | 7 |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Satisfiability Modulo Theories
Satisfiability modulo theories (SMT) checks whether logical formulas are satisfiable under theories such as arithmetic, strings, and bit-vectors.
See all 22 papers