TurboSAT: Gradient-Guided Boolean Satisfiability Accelerated on GPU-CPU Hybrid System
Steve Dai * , Cunxi Yu, Kalyan Krishnamani, Brucek Khailany · 2025
Read TurboSAT: Gradient-Guided Boolean Satisfiability Accelerated on GPU-CPU Hybrid System by Steve Dai * , Cunxi Yu, Kalyan Krishnamani, Brucek Khailany (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07737.txt.
Description
Steve Dai, Cunxi Yu, and Kalyan Krishnamani speed up Boolean satisfiability solving with graphics processors. SAT solvers decide whether logical formulas can be satisfied, a core task in verification and planning. Champion solvers search sequentially with clever conflict heuristics, leaving parallel hardware mostly idle.
TurboSAT recasts SAT as a binarized matrix multiplication that a differentiable objective can optimize, much like training a neural network. Gradient-guided search runs in parallel on the hybrid system, then combines with sequential conflict search. Mixing both styles aims for scale neither reaches alone. Faster SAT would ripple through chip design, scheduling, and automated reasoning.
Catalog record
| CREATOR | Steve Dai * , Cunxi Yu, Kalyan Krishnamani, Brucek Khailany |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-07737