The Role of Logic and Automata in Understanding Transformers
This is an incremental review that synthesizes existing knowledge to clarify theoretical foundations for researchers in machine learning and formal methods.
The paper addresses the limited understanding of transformers' capabilities by reviewing recent progress that highlights the integral role of logic and automata in analyzing what transformers can do, without presenting new experimental results or concrete numbers.
The advent of transformers has in recent years led to powerful and revolutionary Large Language Models (LLMs). Despite this, our understanding on the capability of transformers is still meager. In this invited contribution, we recount the rapid progress in the last few years to the question of what transformers can do. In particular, we will see the integral role of logic and automata (also with some help from circuit complexity) in answering this question. We also mention several open problems at the intersection of logic, automata, verification and transformers.