Can Transformers Reason Logically? A Study in SAT Solving
<|reference_start|>Can Transformers Reason Logically? A Study in SAT Solving: We theoretically and empirically study the logical reasoning capabilities of LLMs in the context of the Boolean satisfiability (SAT) problem. First, we construct a decoder-only Transformer that can solve SAT using backtracking and deduction via Chain-of-Thought (CoT). We prove its correctness by showing trace equivalence to the well-known DPLL SAT-solving algorithm. Second, to support the implementation of this abstract construction, we design a compiler $\texttt{PARAT}$ that takes as input a procedural specification and outputs a transformer model implementing this specification. Third, rather than $\textit{programming}$ a transformer to reason, we evaluate empirically whether it can be $\textit{trained}$ to do so by learning directly from algorithmic traces ("reasoning paths") of the DPLL algorithm.<|reference_end|>
@article{pan2024can,
    title={Can Transformers Reason Logically? A Study in SAT Solving},
    author={Leyan Pan, Vijay Ganesh, Jacob Abernethy, Chris Esposo, Wenke Lee},
    journal={arXiv preprint arXiv:2410.07432},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.07432},
    primaryClass={cs.LG cs.AI cs.LO}
}