Transformers Encode Languages Far More Compactly Than Traditional Formalisms
A new theoretical study shows fixed‑precision transformers can represent certain languages with polynomial‑size models, while equivalent LTL formulas require exponential size and finite automata need doubly‑exponential size. This succinctness implies that basic verification tasks for transformers, like emptiness and equivalence, are EXPSPACE‑complete, highlighting inherent limits to formal analysis.