arXiv：cs.LG· Yuanzhuo Zhang·· 4 小时前AI 评分31
GradSAT：用梯度归一化加速浮点可满足性求解
Accelerating Floating-Point Satisfiability Solving via Gradient Normalization
AI 导读
GradSAT 框架将 SMT 的每个子句视为独立的多任务学习任务，通过动态梯度归一化（GradNorm）在运行时平衡各子句梯度大小，缓解梯度支配问题。它采用两阶段流水线：GPU 加速的 PyTorch 后端配合符号编译与算子融合导航连续松弛，再由位精确局部搜索求解器完成精确赋值。
正文
Abstract:Satisfiability Modulo Theories (SMT) solvers are foundational to software verification, program analysis, and compiler testing, particularly over the theory of Quantifier-Free Floating-Point (QF_FP). While recent optimization-based SMT solvers have successfully applied gradient descent to continuous relaxations of logical formulas, they are fundamentally bottlenecked by gradient domination, a phenomenon where a small subset of difficult clauses hijacks the optimization trajectory, preventing the solver from satisfying the broader formula and trapping it in local minima.
To overcome this, we present GradSAT, a novel framework that bridges optimization-based SMT solving with Multi-Task Learning (MTL). GradSAT reformulates the constraint satisfaction process by treating each SMT clause as an independent MTL task. By applying dynamic gradient normalization (GradNorm), GradSAT actively balances the gradient magnitudes across all clauses at runtime, systematically penalizing dominant gradients and accelerating lagging clauses to ensure uniform convergence. GradSAT implements this through a highly optimized, two-stage hybrid pipeline. First, a GPU-accelerated PyTorch backend leveraging symbolic compilation and operator fusion navigates the continuous relaxation to a high-quality basin. Second, the candidate assignment is handed off to a bit-precise local search engine to rapidly resolve the exact, rigorous assignment. By stabilizing the continuous search dynamics, GradSAT mitigates the brittleness of prior gradient-based solvers and provides a robust, highly parallelizable architecture for complex constraint solving.
| Subjects: | Artificial Intelligence (cs.AI); Machine Learning (cs.LG) |
| ACM classes: | D.2.4; F.3.1; F.4.1 |
| Cite as: | arXiv:2610.08808 [cs.AI] |
| (or arXiv:2610.08808v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2610.08808 arXiv-issued DOI via DataCite |
Submission history
From: Yuanzhuo Zhang [view email]
[v1]
Mon, 14 Sep 2026 13:22:32 UTC (26 KB)
来源：arXiv：cs.LG · arxiv.org