The Role of Logic and Automata in Understanding Transformers

Anthony W. Lin, Pablo Barcelo
9/28/2025
cs.FLcs.CLcs.LG

No confident code implementation found for this paper.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Cite this paper

@article{lin2025role,
  title  = {The Role of Logic and Automata in Understanding Transformers},
  author = {Anthony W. Lin and Pablo Barcelo},
  year   = {2025},
  eprint = {2509.24024},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2509.24024v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2509.24024.svg)](https://codeofpaper.com/paper/2509.24024)

Discussion