Transformers are Inherently Succinct
RPTU Kaiserslautern-Landau · Swiss Federal Institute of Technology · Max-Planck Institute for Software Systems, University of Kaiserslautern-Landau
PDF 由论文原始站点提供，PaperCompass 不保存论文文件。
摘要
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).