Can I read Can Transformers Reason Logically? A Study in SAT Solving on EtoBox?

Can Transformers Reason Logically? A Study in SAT Solving by Pan, Leyan; Ganesh, Vijay; Abernethy, Jacob; Esposo, Chris; Lee, Wenke is a scholarly article available to read on EtoBox.

What is Can Transformers Reason Logically? A Study in SAT Solving about?

We formally study the logical reasoning capabilities of decoder-only Transformers in the context of the boolean satisfiability (SAT) problem. First, we prove by construction that decoder-only Transformers can decide 3-SAT, in a non-uniform model of computation, 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, we implement our construction as a PyTorch model with a tool (PARAT) that we designed to empirically demonstrate its correctness and investigate its properties. 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'') from our theoretical construction. The trained models demonstrate strong out-of-distribution generalization on problem sizes seen during training but has limited length generalization, which is consistent with the implications of our theoretical result

Author

Pan, Leyan; Ganesh, Vijay; Abernethy, Jacob; Esposo, Chris; Lee, Wenke

Published

2024

Language

EN