用分阶段优化解决浮点数可满足性,速度快且结果准确。
Scalable Floating-Point Satisfiability via Staged Optimization
- 分三阶段逐步提升精度,从粗略搜索到精确求解
- 在相同时间内解决更多公式,99.4%可满足例召回率,零误报
- 无需底层位级推理,适合需要高可靠性的工程验证
本文提出StageSAT,一种基于分阶段优化的浮点数可满足性求解方法。该方法将浮点公式转化为三个精度逐步提升的优化问题:首先通过投影加速下降快速定位可行区域;接着采用ULP²优化实现位级精度;最后进行n-ULP格点精修。最终阶段的目标函数仅在满足所有约束时为零,优化至零即保证解的有效性,提供内在完备性。为避免优化停滞,引入线性约束的局部单调下降机制,通过正交投影实现。该求解器不依赖复杂的位级推理或特殊抽象,将复杂算术视为黑箱,通过运行时评估探索输入空间。在SMT-COMP'25及先前难题集上测试表明,StageSAT比现有优化型求解器更高效准确,在相同时间预算下解决公式数量更多,对可满足实例的召回率达99.4%,误报率为0%,显著优于以往方法。同时相较传统位精确SMT与数值求解器提速5–10倍。结果证明分阶段优化能显著提升浮点可满足性求解的性能与正确性。
原文摘要 · Abstract (English)
This work introduces StageSAT, a new approach to solving floating-point satisfiability that bridges SMT solving with numerical optimization. StageSAT reframes a floating-point formula as a series of optimization problems in three stages of increasing precision. It begins with a fast, projection-aided descent objective to guide the search toward a feasible region, proceeding to bit-level accuracy with ULP$^2$ optimization and a final $n$-ULP lattice refinement. By construction, the final stage uses a representing function that is zero if and only if a candidate satisfies all constraints. Thus, when optimization drives the objective to zero, the resulting assignment is a valid solution, providing a built-in guarantee of soundness. To improve search, StageSAT introduces a partial monotone descent property on linear constraints via orthogonal projection, preventing the optimizer from stalling on flat or misleading landscapes. Critically, this solver requires no heavy bit-level reasoning or specialized abstractions; it treats complex arithmetic as a black-box, using runtime evaluations to navigate the input space. We implement StageSAT and evaluate it on extensive benchmarks, including SMT-COMP'25 suites and difficult cases from prior work. StageSAT proved more scalable and accurate than state-of-the-art optimization-based alternatives. It solved strictly more formulas than any competing solver under the same time budget, finding most satisfiable instances without producing spurious models. This amounts to 99.4% recall on satisfiable cases with 0% false SAT, exceeding the reliability of prior optimization-based solvers. StageSAT also delivered significant speedups (often 5--10$\times$) over traditional bit-precise SMT and numeric solvers. These results demonstrate that staged optimization significantly improves performance and correctness of floating-point satisfiability solving.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。