The Role of Logic and Automata in Understanding Transformers
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Transformers are Inherently Succinct
We study succinctness as a measure of the expressive power of transformers. Succinctness -- how compactly a formalism can describe a language relative to other formalisms -- is a classical notion in logic and automata th…
Robustness of Constraint Automata for Description Logics with Concrete Domains
Decidability or complexity issues about the consistency problem for description logics with concrete domains have already been analysed with tableaux-based or type elimination methods. Concrete domains in ontologies are …
Cross-Attention and Encoder-Decoder Transformers: A Logical Characterization
We give a novel logical characterization of encoder-decoder transformers, the foundational architecture for LLMs that also sees use in various settings that benefit from cross-attention. We study such transformers over t…
Automata Techniques for Temporal Answer Set Programming
Temporal and dynamic extensions of Answer Set Programming (ASP) have played an important role in addressing dynamic problems, as they allow the use of temporal operators to reason with dynamic scenarios in a very effecti…
Simulating Weighted Automata over Sequences and Trees with Transformers
Transformers are ubiquitous models in the natural language processing (NLP) community and have shown impressive empirical successes in the past few years. However, little is understood about how they reason and the limit…