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

CREATORSteve Dai * , Cunxi Yu, Kalyan Krishnamani, Brucek Khailany
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-07737

Browse the full library · About the Tower of Babel