ICLR 2026poster0 citations
Transformers are Inherently Succinct
Pascal Bergsträßer, Ryan Cotterell, Anthony Widjaja Lin
Abstract
We propose succinctness as a measure of expressive power of a transformer in describing a concept. To this end, we prove that transformers are highly expressive in that they can represent formal languages substantially more succinctly than standard representations of formal languages like finite automata and Linear Temporal Logic (LTL) formulas. As a by-product of this expressivity, verifying even simple properties of transformers is shown to be provably intractable (i.e. EXPSPACE-complete).
TransformerscomplexityexpressivityautomataLTL
BibTeX
@inproceedings{
bergstraer2026transformers,
title={Transformers are Inherently Succinct},
author={Pascal Bergstr{\"a}{\ss}er and Ryan Cotterell and Anthony Widjaja Lin},
booktitle={The Fourteenth International Conference on Learning Representations},
year={2026},
url={https://openreview.net/forum?id=Yxz92UuPLQ}
}