Understanding Transformers through the Lens of Logic and Automata
summary
Claim: transformers without chain-of-thought map to logico-automata classes and explain why PARITY is hard; tools: reductions to circuit complexity (AC0/ATC0), translations to LTLf‑past and letter-to-letter transducers, plus controlled experiments that show parity miscounts (example gave 19 vs actual 22). Built: hard‑attention/Uhat and counting‑LTL (CRASP) encodings that express majority and balanced‑parentheses frequency; results include an exponential LTL blowup, proofs of undecidability for richer counting, and partial positive verification procedures. Softmax attention remains technically open.
AI-written summary · about
chapters (20)
- 0:00Introduction
- 1:08Transformers basics and limits
- 3:59Transformers struggle with counting
- 7:33Formal language view
- 10:01Transformer architecture basics
- 15:05How attention works
- 21:46Hard vs soft attention
- 25:27Formal models and expressivity
- 27:59Upper bounds with Uhat
- 30:04Uhat and starfree languages
- 33:15LTL to Uhat translation
- 39:50Trainability and verification
- 42:46Open questions on Uhat
- 45:19Introduction to Ahat
- 46:44Counting LTL in Ahat
- 50:37C-Rasp translation challenges
- 52:25Why C-Rasp matters
- 55:33Undecidability and verification
- 56:36Future research directions
- 58:03Q&A
related talks
18mGuiding machine design using insights from simple sandboxes
39mComputational Thinking on Learning Models
21mHow hard can it be! Practical uses of complexity theory
01h 05mLogic and Probabilistic Circuits 1
01h 03mLogic and Probabilistic Circuits 2
40mAn Occam's Razor Principle for Transformers?
28mEverything you need to know about Transformer Models
38mHow Transformers Learn Causal Structure with Gradient Descent