Simulating Weighted Automata over Sequences and Trees with Transformers

arXiv:2403.09728v1 Announce Type: new
Abstract: Transformers are ubiquitous models in the natural language processing (NLP) community and have shown impressive empirical successes in the past few years. However, little is understood about how they reason and the limits of their computational capabilities. These models do not process data sequentially, and yet outperform sequential neural models such as RNNs. Recent work has shown that these models can compactly simulate the sequential reasoning abilities of deterministic finite automata (DFAs). This leads to …

abstract arxiv capabilities community computational cs.ai cs.cc cs.cl data however language language processing natural natural language natural language processing nlp process processing reason transformers trees type