Transformers Are Inherently Succinct
Summary
The paper introduces succinctness as a measure of transformer expressiveness and demonstrates that transformers can describe formal languages more succinctly than traditional representations like finite automata and LTL formulas. It additionally shows that verifying properties of transformers is EXPSPACE-complete, highlighting both their expressive power and the inherent difficulty of formal analysis.