Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions (2023)

Abstract: Recent studies of the computational power of recurrent neural networks (RNNs) reveal a hierarchy of RNN architectures, given real-time and finite-precision assumptions. Here we study auto-regressive Transformers with linearised attention, a.k.a. linear Transformers (LTs) or Fast Weight Programmers (FWPs). LTs are special in the sense that they are equivalent to RNN-like sequence processors with a fixed-size state, while they can also be expressed as the now-popular self-attention networks. We show that many well-known results for the standard Transformer directly transfer to LTs/FWPs. Our formal language recognition experiments demonstrate how recently proposed FWP extensions such as recurrent FWPs and self-referential weight matrices successfully overcome certain limitations of the LT, e.g., allowing for generalisation on the parity problem. Our code is public.

## introduction recurrent neural networks (rnns) are turingcomplete, given assumptions of infinite precision and unbounded computation @xcite for the sigmoid activation; @xcite for relu; see also an alternative setting of @xcite ). this insight has a certain theoretical value, however, its implication for practical, real-world scenarios is limited. in contrast, many recent works (e.g., @xcite ; @xcite ; @xcite ; @xcite ) strive to obtain results of practical relevance on the computational power of sequence-processing neural networks (nns). typical assumptions of such studies are finite precision and "input-bound" computation (i.e., the number of computational steps is determined by and limited to the number of input tokens; a.k.a. real-time assumption), essentially reflecting the reality of practical † work done at idsia. 1 https://github.com/idsia/fwp-formal-lang rnns. although such analyses typically further assume models to be saturated @xcite ; which is not always the case for real-world rnns), they provide useful results and insights that can be empirically confirmed, e.g., on formal language recognition tasks. for example, the long shortterm memory (lstm; @xcite ) can learn to solve and generalise on certain counter-language tasks (gers and @xcite ; @xcite ; @xcite ; @xcite ), unlike its simplified versions such as the gated recurrent unit (gru; @xcite ), the quasi-rnn @xcite ; see @xcite ) or the simple sigmoid rnn @xcite . tools from the theory of computation (see, e.g., @xcite ) provide a formalism to compare the practical computational power of these nn architectures, allowing for categorisation into a hierarchy @xcite ; see appendix a for further references). more recent works @xcite @xcite derive results for the now-popular transformer @xcite . for example, @xcite show (we review in sec. 3) that transformers can learn to solve and generalise on certain counter-language tasks (including the contextsensitive a n b n c n ), while they fail to learn certain simple regular languages (many examples of which are non-star-free languages) including the parity task (see also @xcite ). for further theoretical studies, we refer to, e.g., hahn (2020); @xcite ; @xcite . here we focus on auto-regressive transformers with linearised attention a.k.a. linear transformers (lts; @xcite ; @xcite ; @xcite ) or fast weight programmers (fwps; @xcite ; @xcite ; @xcite ). lts are special, as they can be equivalently expressed as an rnn-like sequence processor with a constantsize state (the fwps from the 1990s; @xcite ), while they are originally formulated as self-attention networks. this property is interesting for discussions of computational power, since it removes one of the classic distinctions between transformers and rnns: rnns are "automata-like" constant-size stateful models, while transformers are not. building upon @xcite ; bhattamishra et al. (2020a); merrill et al. (2020) , we show that many existing results on transformers directly transfer to lts/fwps. also, prior work proposes several extensions to lts inspired by its rnn-like form, including recurrence @xcite and self-reference @xcite , showing their practical benefits on actual real-world tasks (e.g., reinforcement learning in game environments). here we demonstrate how both recurrent and self-referential extensions enhance lts' practical computational power on formal language recognition tasks. ## background here we briefly review lts and fwps. let d in , d out , d key , t be positive integers, and ⊗ denote outer product. an fwp @xcite is a sequence-processing nn that, at each time step t, transforms an input x @xmath0: delta-rule. @xcite replace the purely additive update rule of eq. 2 by the classic delta-rule for error correction @xcite ; eq. 8 below. the slow weight matrix in the resulting model, called deltanet, is w @xmath1. with the delta rule, ϕ's output elements need to be positive and sum up to one (e.g., we use softmax) for stability. note that this introduces an extra dependency to lts; the update term σ(β t )(v tvt ) ⊗ ϕ(k t ) in eq. 8 is a function of w t-1 unlike in eq. 2. we'll empirically illustrate how this modification introduces an explicit forget mechanism to the lt, using the "reset dyck-1" language (sec. 4). recurrence. one trivial extension to the lts/deltanet above is to add "proper recurrent connections" by feeding back the output y t-1 from the previous step t -1 as an input at step t (for other recurrent extensions we refer to @xcite ). the resulting recurrent deltanet @xcite (or recurrent delta) is obtained by replacing eq. 6 in the deltanet by: self-reference. another extension of the deltanet above is the modern self-referential weight matrix (srwm). motivated by recursive self-improvement @xcite and the original srwm @xcite , irie et al. (2022c) extend the fwp that generates weight changes for another nn to obtain an nn that modifies itself. at each time step t, an srwm w t-1 ∈ r (dout+2 * d in +1)×d in transforms an input x @xmath2, and updates itself to w t as follows: here we focus on this specific self-referential extension. ## expressive power of lts here we revisit several existing results on the practical computational power of transformers for normalised lts (nlts; eqs. 1-2;4-5). results in this section directly build upon prior work @xcite . as we'll see, some of the results are not obvious from eqs. 1-2;4-5. however, their connection to transformers allows us to trivially derive them. while one can come up with certain custom positional encoding methods that empower transformers to specifically recognise certain languages, here we focus on generic transformers without positional encoding @xcite @xcite . we start by noticing that the hidden "state" update of nlts (eq. 2) is element-wise. this is reminiscent of simplified lstms such as quasi-rnns @xcite , which are known to be limited @xcite : in particular, quasi-rnns are rationally recurrent @xcite ). however, we have the following result: proposition 3.1 ("rational recurrence"). nlts are not rationally recurrent. proof. merrill et al. (2020)'s proof by construction for their theorem 15 remains valid for nlts. it should be noted that the actual output of nlts is y t (eq. 5), not w t . in fact, nlts can recognise certain counter languages, inheriting the properties of the transformer: given the original proofs by @xcite and @xcite , the proofs above are straightforward for normalised lts. for further discussions on these proofs and their extension for unnormalised lts (eqs. 1-3), we refer to appendix c.1. in sum, these statements on the expressiveness of transformers remain valid for both normalised and unnormalised lts. ## experiments here we provide several empirical results on capabilities and limits of unnormalised lts/fwps and their extensions, using formal languages. ## conclusion we discuss the computational power of transformers with linearised attention in the context of formal languages. we show that such linear transformers (lts) a.k.a. fast weight programmers (fwps) inherit several capabilities and limitations of transformers. we demonstrate that their recurrent and self-referential extensions successfully overcome some of those limitations. we hope this work will inspire the development of formally more powerful transformer models.