Transformers as Transducers

arXiv:2404.02040v1 Announce Type: cross
Abstract: We study the sequence-to-sequence mapping capacity of transformers by relating them to finite transducers, and find that they can express surprisingly large classes of transductions. We do so using variants of RASP, a programming language designed to help people "think like transformers," as an intermediate representation. We extend the existing Boolean variant B-RASP to sequence-to-sequence functions and show that it computes exactly the first-order rational functions (such as string rotation). Then, we introduce two new …

abstract arxiv capacity cs.fl cs.lg express intermediate language mapping people programming programming language representation study them think transformers type variants