Loading Events

« All Events

  • This event has passed.

Can Transformers Reason Logically? A Study in SAT-Solving

December 4, 2024 @ 2:00 pm - 3:00 pm

New Technologies in Mathematics Seminar

Speaker: Leyan Pan, Georgia Tech

Title: Can Transformers Reason Logically? A Study in SAT-Solving

Abstract: Transformer-based LLMs have apparently demonstrated capabilities that resembles human reasoning. In our recent work, we investigated the Boolean reasoning abilities of decoder-only Transformers equipped with Chain-of-Thought, establishing that a Transformer model can decide all 3-SAT instances up to a bounded size (i.e., number of variables and clauses). In this talk, I will first review recent studies that formally examine the expressiveness of Transformer models. Next, I will explain how we establish an equivalence between Chain-of-Thought reasoning and algorithm, in our case, the DPLL SAT-solving algorithm. I will then discuss how to encode 3-SAT formulas and partial assignments as vectors so that the high-level operations in DPLL can be represented as vector operations and implemented using attention mechanisms within Transformers. Finally, I will present experimental results that support our theoretical predictions. I will also address why standard Transformers can only solve reasoning problems of bounded length, leading to failures in length-generalization, and discuss potential solutions to overcome this limitation.

Details

Date:
December 4, 2024
Time:
2:00 pm - 3:00 pm
Event Category:

Venue

CMSA Room G10
CMSA, 20 Garden Street
Cambridge, MA 02138 United States
+ Google Map
Phone:
6174967132