Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions
Authors: Kazuki Irie
Róbert Csordás
Jürgen Schmidhuber
Venue: EMNLP 2023 Main (2023)
Keywords: recurrent neural networks
RNNs
transformers
computational power
automata
counter machines
formal languages
linear transformers
self-reference
self-referential weight matrix
TL;DR: We study the practical computational power of linear Transformers and their extensions using formal languages

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.

Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referente Extensions
Kazuki Irielt Róbert Csordás² Jürgen Schmidhuber
Harvard University "The Swiss AI Lab IDSIA, USI & SUPSI "AI Initiative, KAUST kirieefas. harvard.. (robert, juergeneeidsii..c
Abstract
RNNs. Although such analyses typically further sume models to be saturated (Merrill al. (2020); 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 short- term memory (LSTM; Hochreiter and Schmidhu- ber (1997)) learn to solve and generalise certain counter-lanuuage tasks (Gers and Schmid- huber (2001); Schmidhuber et al. (2002); Weiss et al. (2018b); Suzgun et al. (2019a)), unlike its simplified versions such as the gated recurrent unit (GRU; Cho et al. (2014); Gers et al. (2000)), the Quasi-RNN (Bradbury et al. (2017); see Merrill et al. (2020)) or the simple sigmoid RNN (Elman, 1988). Tools from the theory of computation (see, e.g., Sipser (1996)) provide a formalism to com- pare the practical computational power of these NN architectures, allowing for categorisation into a hicrarchy (Merrill et al. (2020); see Appendix A for further references).
Recent studies of the computational power of recurrent neural networks (RNNs) reveal a hier- archy RNN architectures, given real-time and finite-precision assumptions. Here study auto-regressive Transformers with lin- earised attention, a.k.a. linear Transformers (L.Ts) Fast Weight Programmers (FWPs). LTs are special in the sense that they are equiv- alent RNN-like sequence processors with a fixed-size state, while they can also be ex- pressed as the now-popular self-attention net- works. We show that many well-known results for the standard Transformer directly transfer LTs/FWPs. Our formal language recogni- tion experiments demonstrate how recently pro- posed FWP extensions such as recurrent FWPs and self-referential weight matrices success- fully overcome certain limitations of the LT, e.g.. allowing for generalisation on the parity problem. Our code is public.
1 Introduction
Recurrent neural networks (RNNs) are Turing- complete, given assumptions of infinite precision and unbounded computation (Siegelmann and Son- tag (1991) for the sigmoid activation; Chen al. (2018) for ReLU; see also an alternative setting of Chung and Siegelmann (2021)). This insight has a certain theoretical value, however, implication for practical, worldworld scenarios is limited. In con- trast, many recent works (c.g., Weiss et al. 120;;b); Suzgun et al. (2019a); Merrill et al. (2020); Bhat- tamishra et al. (2020a)) strive to obtain results of practical relevance the computational power of sequence-processing neural networks (NNs). Typi- cal assumptions of such studies are finite precision and finput-boundh computation (i.e., the number of computational steps determined by and limited to the number of input tokens; a. a.k.a real-time assump- tion), essentially reflecting the reality of practical
More recent works (Bhattamishra et al., 2020a,b; Ebrahimi et al., 2020; Yao et al., 2021) derive results for the now now-popular Transformer (Vaswani et al., 2017). For example, Bhattamishra et al. (2020a) show review in Sec. 3) that Transform- can learn to solve and generalise on certain counter-language tasks (including the context- sensitive a a")"c")) while they fail to learn certain simple regular languages (many examples of which are non-star-fiee star-fre languages) including the parity task (see also Chiang and Cholak (2022)). For further theoretical studies, we refer to, e.g., Hahn (2020); Merrill al. (2022); Hao et al. (2022).
Here we focus auto-regressive Transformers with linearised attention a.k.a. linear Transformers (LTs; Katharopoulos et al. (2020); Choromanski et al. (2021); Peng al. (2021)) or Fast Weight Programmers (FWPs; Schmidhuber (1991, 1992a); Schlag et al. (2021): Irie et al. (2021)). LTs are special, as they can be equivalently expressed as
Work done at IDSIA.
htttps: / thub. com htwp:/DSSAA/fuo--ooo--------e

---

RNN-Iike sequence processor with a constant- size state (the FWPs from the 1990s; Schmidhuber (1991, 1993)), while they are originally formulated as self-attention networks. This property is interest- ing 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 Weiss et al. (2018b); Bhat- tamishra 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 (Irie et al.. 2021) and self-reference (Irie et al., 2022c), show- ing their practical benefits on actual real-world tasks (e.g., reinforcement learning in game envi- ronments). Here we demonstrate how both recur- rent and self-referential extensions enhance LTs' practical computational power on formal language recognition tasks.
the following additional computation:
21 - zt-1 + ((ki)
(4)
yt 2, (
Wc)(g:)
(5)
where Zt E Rdy with 20 0, and denotes dot product, i.e., 2, p(q.) E IR, replacing Eq. 3. In practice, this normalisation can be removed with- out loss of performance (Schlag al., 2021; Irie et al., 2021), which convenient no extra vector 2 needs be stored. All standard Transformer components including feedforward blocks, residual connections, and layer-norm are used in LTs.
This equivalence has inspired a series of extensions to Transformers. Here we highlight three such examples: delta-rule, recurrence, and self-reference, which study in Sec. 4.
Delta-rule. Schlag et al. (2021) replace the purely additive update rule of Eq. by the clas- sic delta-rule for error correction (Widrow and Hoff, 1960); Eq. below. The slow weight ma- trix in the resulting model, called DeltaNet, is Wstow E td +1)xda that also generates dynamic learning rate 3r C R (to which we apply the sigmoid function o). With the delta rule, d's output elements need to be positive and up one (c.g., we use softmax) for stability.
2 Background
Here we briefly review LTs and FWPs. Let din, dout, dkey. & be positive integers, and @ denote outer product. An FWP (Schmidhuber, 1991, 1992a) sequence-proceste
NN that, each time step t, transforms an input 2y E Rd to an output E Redo as follows:
qt. kr, Ut, 3r Wlloow Dt
(6)
0. 1
(7)
W Wi- + ( 8,) @ Φb (k:)
(8)
qi k1, Vi = slloow xt
(1)
W.- W, + 2 (ki)
(2) Note that this introduces an extra dependency to
(3) LTs: the update term o (B)) vz) @ d(ki) in Eq. 8 is function of W unlike in Eq. 2. We'll empirically illustrate how this modification intro- duces an explicit forget mechanism to the LT, using the "reset Dyck- language (Sec. 4).
yt = (.)(q))
where ki, Radayy C Rdo and Wsstow R( (2d +daa) Xdn is a weight matrix (the "slow" weights), and @ is activation function. The "fast" weight matrix W, Rdda is initially set to 0, i.e., Wo O. This can be viewed as system of two NNs where one net (the slow net; Eq. 1) learns to "program" the fast net (Eq. 3) by gen- erating its weight changes (Eq. 2). This a,-to-y: transformation can be also expressed as linear at- tention using ((kt), Vi p(q)) as key, value, query vectors (Katharopoulos al. (2020); Schlag et al. (2021); Ba et al. (2016); see also our brief review in Appendix B). To be more specific, such FWPs cor- respond to unnormalised LTs. LT' with normalised linear attention (NLTs; Katharopoulos et al. (2020); Choromanski et al. (2021), I); Peng et al. (2021)) use
C
Recurrence. One trivial extension to the LTs/DeltaNet above to add "proper recurrent connections" by feeding back the output y:-1 from the previous step { - 1 input at step (for other recurrent extensions refer to Irie et al. (2021)). The resulting Recurrent DeltaNet (Irie et al., 2021) (or Recurrent Delta) is obtained by replacing Fq. 6 in the DeltaNet by:
(9) (R(ddduury don 1))((dm dou)), and [zt, canh(zt-1)). E tos denotes concatena- tion of the two vectors.
qi ki, Ut, Br Wsslow (23, tanh(y: 1)]
where W slow

---

Self-Reference. Another extension of the DeltaNet above is the modern self-referential weight matrix (SRWM), Motivated by recursive self-imprrvement (Good, 1965; Schmidhuber, 1987) and the original SRWM (Schmidhuber, 1992b), 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, SRWM Wi-1 C R 2-dmn +1) xdm transforms an imput 2t E JR an output yt Rdda, and updates itself to W, as follows:
It should be noted that the actual output of NLTs yt (Eq. 5), not W, In fact, NLTs can recognise certain counter languages, inheriting the properties of the Transformer:
Proposition 3.2 ("Simple Counter Languages"). NLTs can recognise certain counter languages.
Proof. Bhattamishra et al. (2020a)'s 's proof for their Proposition 4.1 is valid for NLTs: NLTs can recog nise Shufile-yyck languages.
However, similar to Transformers, NLTs are fun- damentally limited:
yr. Ki, at, 3: = 12
(10)
Proposition 3.3 ("Regular Languages"), NLT's can
0: = W 16()) 8. = (V-1)((k))
(11)
not recognise certain regular languages.
W. - W + (B:)( T²) & (kkr)
(12)
Proof. Bhattamishra et al. (2020a)'s 's proof for their Lemma C.4 remains valid for NLTs; NLTs can not recognise the regular language (aa)".
where Uz. 02 E 2(dur+2ndo+1) qi kt Id and 3, E R. The initial values Wo are the only train- able parameters of this layer. Note that it is straight- forward to further extend this model with recur- rence as in Eq. 9. Here we focus on this specific self-referential extension.
Finally, we comment on the "state complexity" as defined by Merrill et al. (2020):
Proposition 3.4 ("State complexity"). The state complexity of single-layer NLT is Ollo((n) (same as the regular self-attention and LSTM).
3 Expressive Power of LTs
Proof. Merrill et al. (2020)'s 's proof for Theorem 16 remains valid for normalised linear attention.
Here we revisit several existing results on the prac- tical computational power of Transformers for nor- malised LTs (NLTs: Eqs. 1-2;4-5). Results in this section directly build upon prior work (Bhat- tamishra et al., 2020a; Merrill et al., 2020). As we'll see, some of the results are not obvious from Eqs. 1-2;4-5, However, their connection to Trans- formers allows 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 (Bhattamishra et al., 2020a; Irie et al., 2019; Tsai et al., 2019).
Given the original proofs by Bhattamishra et al. (2020a) and Merrill et al. (2020), 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.
trivially derive them. While
Experiments
Here we provide several empirical results capabilities and limits of unnormalised LTs/FWPs and their extensions, using formal languages.
We start by noticing that the hidden "state" up- date of NLTs (Eq. 2) is element-wise. This is remi- niscent of simplified LSTMs such as Quasi-RNNs (Bradbury et al., 2017), which are known to be limited (Merrill et al., 2020): in particular, Quasi- RNNs are rationally recurrent (Peng et al. (2018)). However, we have the following result:
4.1 Tasks
We evaluate LT models on formal language recognition tasks using several non-star- free regular languages languages-parity, (aa)", (ahab)--, and counter languages
anng a²b". a"b"c", Shuffle-2, and reset Dyck-1. This choice is guided by Bhattamishra et al. (2020a)'s results on the standard Transformers to specifically evaluate LTs' capabilities and limits. Following prior work (Gers and Schmidhuber, 2001), for bd and c"
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. D

---

Table 1: Accuracies various models on the formal language recognition tasks.
Mon-Star-Fre Regular
Counter
Parity
(aa)
(abab)
a"b"
a"b"c" c
Shuffl-2
Model
BinO
Bin1
BinO
Binl
BinO
Binl
BinO
Binl
Bin0
Bin1
BinO
Binl
LSTM
100.0
100.0
100.0
100,0
100.0
100.0
100.0
100,0
100.0
100.0
100.0
100.0
e-I.TTM
100.0
100.0
100.0
100.0
100.0
100.0
100.0
90.0
100.0
22.0
100.0
85.7
Transformer
47.1
0.1
0.0
0.0
0.0
0.0
100.0
100,0
100.0
100.0
100.0
100.0
Linear
77.9
0.2
0.0
0.0
0.0
0.0
100.0
100.0
100.0
100.0
100.0
100.0
DeltaNet
97.3
11.8
0.0
0.0
0.0
0.0
100.0
100.0
100.0
100.0
100.0
100,0
Recurrent Dolta
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100,0
SRWM
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
100.0
we define the language recognition task as the next character prediction task. For example, for the context-free language adb", if the input to the model is aaabbb, the model has to output NNNbbS where N denotes (raamot-predict-yvee S denotes the sequence-end token. Appendix C.2 contains corresponding descriptions for other tasks. We train models on positive examples of up to a cer- tain length, and validate them on positive examples with longer lengths. We denote the corresponding data splits as "BinO" (sequences with lengths seen during training) and "Binl" (longer sequenees). For evaluation, for each position of the sequence, we define the model prediction as the token that is
Table 2: Accuracies of single-layer models.
Dyck-1 I
Reset Dyck-1
Model
BinO
Binl
BinO
Bin1
token, and
Linear
100.0
100,0
44.5
41.1
DeltaNet
100.0
100,0
100.0
100.0
Recurrent Delta
100.0
100.0
100.0
100.0
SRWM
100.0
100.0
100.0
100.0
We also confirm that all LT variants can learn representative counter languages that the original Transformer can learn (Table 1/Right). One inter- esting empirical trend (not reflected in Table 1) is that the base Transformer and LT tend to more the most likely according to the model. We re- port accuracy on the sequence level; we count a sequence correctly recognised only if the model prediction is correct for all tokens in the sequence. Further experimental details (e.g., hyper- parameters) can be found in Appendix C.2.
easily find solutions that generalise. For DeltaNet, Recurrent Delta and SRWM, many configurations achieve 100% accuracy on BinO, without achieving exactly 100% on Binl.
Reset Dyck-1. The main experiment above does not emphasize the benefits of the delta-rule which by itself cannot help LTs to recognise parity, (aa)* and (abab)*. However, the delta rule is typically reported to be crucial across many practical tasks (including reinforcement learning game environ- ments (Trie et al., 2021), image generation (Irie and Schmidhuber, 2023), or long time-series clas- sification (Irie et al., 2022b)). Here we use reset Dyck-1 to illustrate its benefits. Bhattamishra et al. (2020a) prove that one-layer self-aticntion net- work cannot recognise reset Dyck-1 as it has no mechanism to rewrite memory. As shown in Table 2, the delta-rule by itself allows LT's to recognise this language.
4.2 Results
Main Results. Table 1 shows our main results. The top part of the table shows three reference baselines: LSTM, Transformer, and an LSTM with wise recurrence and tied forut- gate (denoted as e-LSTM; see details in Appendix C.3). Table 1/Left shows the results for the regular lan- guage tasks: parity, (aa)", and (abab)", on which Bhattamishra et al. (2020a) report Transformers to fail. Inheriting their properties, the standard LT fail on all these tasks (recall, however, stated by Bhattamishra et al. (2020a): non-star-free regular languages are not the strict set of regular languages on which Transformers fail). We also confirm that the delta rule is not enough to help LTs succeed in these tasks. In contrast, both the recurrent (Recur- rent Delta) and self-referential (SRWM) extensions successfully solve and generalise on these tasks.
Outlook: Self-Modifying Automata
Here we discuss a potentially interesting perspec- tive for further studying SRWM models. Self- Modifying Automata (SMAs) and Self-Modifying

---

Finite Automata (SMFAs; Rubinstein and Shutt (1993, 1995); Shutt (1995); Wang et al. (1999))² are "FAs" with capabilities to modify their transition function at runtime. Despite its name containing "finite automata," they are provably computation- ally more powerful than FAs: the least restricted versions thereof are Turing-complete, certain re- stricted ones can still recognise certain context- sensitive languages (meta-linear languages). It may be interesting to connect SMFAs with SR- WMs future work. For example, we may try to extract SMFAs from SRWMs trained on certain meta-liinerrccounter languages.
diverse tasks, e.g,, those presented in Delétang et al. (2023).
Acknowledgements
This research was partially funded by ERC Ad- vanced grant no: 742870, project AlgoRNN, and by Swiss National Science Foundation grant no: 200021 200021_192356, project NEUSYM. We are thank- ful for hardware donations from NVIDIA and IBM. The resources used for this work were partially pro- vided by Swiss National Supercomputing Centre (CSCS) project d123.
6 Conclusion
References
Joshua Ackerman and George Cybenko. 2020. A survey of neural networks and formal languages. Preprint arXiv:2006. 01338.
We discuss the computational power of Trans- formers with linearised attention in the context of formal languages. We show that such linear Transformers (LTs) a.k.a. Fast Weight Program- mers (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.
Mark A. Aizerman, Emmanuil M. Braverman, and Lev Rozonoer. 1964. Theoretical foundations of potential function method in pattern recognition. Automation and Remote Control, 25(6)9917-936.
Robert B Allen. 1990. Connectionist language users. Connection Science, 2(4):279-311
Jimmy Ba, Geoffrey Hinton, Volodymyr Mnih, Joel Z Leibo, and Catalin Ionescu, 2016. Using fast weights to attend to the recent past. In Proc. Advances in Neu- ral Information Processing Systems (NIPS), pages 4331 -339,, Barcelona, Spain.
Limitations
Our study follows prior work on the computational power of RNNs, in particular, Bhattamishra et al. (2020a)'s results on Transformers, and Merrill et al. (2020)'s discussion of state-complexity and ratio- nal recurrence. Naturally, this is not an exhaus- tive study of LT properties, and we cannot defini- tively compare the expressivity of LTs to the one of standard Transformers solely based on what is presented here. Also, while it is rather obvious that the recurrent extension enhances the computational power of LT's future work should provide more insights the power of self-reference; see also our outlook Sec. 5 on self-modifying automata. A comparison of such models to
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020a. On the ability and limitations of transformers to recogmize formal languages. In Proc. Conf. on Empirical Methods in Natural Language Processing (EMNLP), pages 7096-7116, 16, Virtual only.
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. 2020b. On the computational power of transformers and implications in sequence modeling. Proc. Conf. on Computational Natural Language Learning (CoNLL), pages 455-475, Virtual only.
James Bradbury, Stephen Merity, Caiming Xiong, and Richard Socher. 2017. Quasi-recurrent neural net- works. In Int. Conf. on Learning Representations (ICLR), Toulon, France.
Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, and Kevin Knight. 2018 Recurrent neural net- works as weighted language recognizers. In Proc. North American Chapter of the Association for Com- putational Linguistics on Human Language Technolo- gies (NAACL-HLT) pages 2261-2271, New Orleans, LA, USA.
RNNs (Graves et al., 2016; Suzgun et al., 201 9b; Delétang et al., 2023) is also left for future work.
We focus on eight tasks by Bhattamishra al. (2020a) to illustrate the capabilities and limitations of Transformers (and thus, those of LTs). Future work will extend experimental results to more
David Chiang and Peter Cholak, 2022, Overcoming a theoretical limitation of self-attention. In Proc. Asso- ciation for Computational Linguistics (ACL), pages 7654-7664, Dublin, Ireland.
"hhese SMFAs are different from another model with the same name by Moulin (1992, 1999, 2006) which is not a formal model of computation, unlike SMFAs.

---

Kyunghyun Cho. Çaglar Gülçehre, Bart van Merriën- boer, Dzmitry Bahdanau, Fethi Bougares Holger Schwenk, and Yoshua Bengio. 2014. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proc. Conf. on Empirical Methods in Natural Language Processing (EMNLP), pages 1724-1734, Doha, Qatar.
Felix Gers. Jürgen Schmidhuber, and Fred Cummins. 2000. Learning to forget: Continual prediction with LSTM. Neural computation, 12(10))2451-22 1-2471.
C. Lee Giles, Clifford B. Miller, Dong Chen, Hsing- Hen Chen, Guo-Zheng Sun, and Tee-Chun Lee. 1992. Learning and extracting finite state automata with second-order recurrent neural networks. Neural Com- putation, 4(3):93 405.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sar- los. Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. 2021. Rethinking attention with performers. In Int. Conf. on Learning Representa- tions (ICLR), Virtual only.
C. Lee Giles, Christian W. Omlin, and Karvel K. Thom- ber. 1999. Equivalence in knowledge representation: automata, recurrent neural networks, and dynamical fuzzy systems. Proc. IEEE, 87(9)
IJ Good. 1965. Speculations concerning the first ultrain- telligent machine. Advances in Computers, pages 31-88.
Stephen Chung and Hava T. Siegelmann. 2021. Turing completeness of bounded-precisson recurrent neural networks. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 28431-28441 Virtual only.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwinska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, al. 2016. Hybrid computing using a neural network with dynamic extermal memory. Nature, 538(7626):477- 476.
Axel Cleeremans, David Servan-Schreiber and James L McClelland. 1989, Finite state automata and simple recurrent networks. Neural computation, 133):772- 381.
Sreerupa Das, C Lee Giles, and Guo-Zheng Sun. 1992. Learning context-free grammars: Capabilities and limitations a recurrent neural network with an ex- ternal stack memory. In Proc. Conf. of Cognitive Science Sociery, Bloomington, IN, USA.
Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. 2015. Learning to transduce with unbounded memory. In Proc. Ad- vances in Neural Information Processing Systems (NIPS), pages
Montreal, Canada.
Sreerupa Das and Michael Mozer. 1993. A uni- fied sendienttdeseem///luttrnnnngg architecture for finite state machine induction. In Proc. Advances in Neu- ral Information Processing Systems (NIPS), pages 19-26, Denver, CO, US.
Michael Hahn. 2020. Theoretical limitations of self- attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156 171.
Yiding Hao, Dana Angluin, and Robert Frank. 2022. Formal language recognition by hard attention trans- formers: Perspectives from eircuit complexity. Trans. Assoc. Comput. Linguistics (TACL), 10:800-810.
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Marcus Hutter, Shane Legg, and Pedro A Ortega. 2023. Neu- ral networks and the Chomsky hierarchy. In Int. Conf. on Learning Representations (ICLR), Kigali, Rwanda.
Sepp Hochreiter and Jüürgen Schmidhuber. 1997. Long short-term memory, Neural computation, 98)):1735 1780.
Brian DuSell and David Chiang. 2020. Learning context-free languages with nondeterministic stack RNNs. In Proc. Association for Computational Lin- guistics (ACL), pages 507-519, Virtual only.
Kazuki Irie, Róbert Csordás, and Jürgen Schmidhuber. 2022a. The dual form of neural networks revisited: Connecting test time predictions to training patterns via spotlights of attention. In Proc. Ins. Conf. on Machine Learning (ICML), Baltimore, MD, USA.
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. 2020. How can self-attention networks recognize Dyck-n languages? In Proc. Findings of Conf. on Empirical Methods in Natural Language Processing (EMNLP. Findings), pages 4301 4301-436,, Virtual only.
Kazuki Trie, Francesco Faccio, and Jürgen Schmidhu- ber. 2022b. Neural differential equations for learning to program neural nets through continuous learning rules. In Proc. Advances in Neural Information Pro- cessing Systems (NeurIPS), New Orleans, LA, USA.
Jeffrey L Elman. 1988. Finding structure in time. CRL Tech. Rep. 9901. Center for Research in Language, University of California, San Diego, CA.
Kazuki Irie, Anand Gopalakrishnan, and Jürgen Schmid- huber. 2023. Exploring the promise and limits of real- time recurrent learning. Preprint arXiv:2305. 19044.
Felix A Gers and Jürgen Schmidhuber. 2001. LSTM recurrent networks learn simple context-free and context-sensitive languages. IEEE Transactions on Newral Networks, 12(6): 1333-1340.
Kazuki Irie, Imanol Schlag, Róbert Csordás, and Jürgen Schmidhuber. 2021. Going beyond linear transform- ers with recurrent fast weight programmers. In Proc.

---

Advances Neural Information Processing Systems (NeurlPS), Virtual only.
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. 2020. A formal hierarchy of RNN architectures. In Proc. As- sociation for Computational Linguistics (ACL), pages 443-459, Virtual only.
Kazuki Irie, Imanol Schlag, Róbert Csordás, and Jür- gen Schmidhuber. 2022c. modern self-referential weight matrix that learns to modify itself. In Proc. Int. Conf. on Machine Learning (ICML), Baltimore, MA. USA.
Jean-Paul Moulin. 1992.
Modifiable automata self- Acta biotheoretica, 40(2-
modifying automata. 3):195-201 204.
Kazuki Trie and Jürgen Schmidhuber. 2023. Images weight matrices: Sequential image generation through synaptic learning rules. In Int. Conf. on Learning Representations (ICLR), Kigali, Rwanda.
Jean-Paul Moulin. 1999. Very simple models, the self- modifying automata and chain of self- aeff-modifying au- tomata, can explain self-referential properties of liv- ing beings. Acta Biotheoretica, 47:353-365.
Kazuki Irie, Albert Zeyer. Ralf Schlüter, and Hermann Ney. 2019. Language modeling with deep Transform- ers. In Proc. Interspeech, pages 3905-3909, Graz, Austria.
Jean-Paul Moulin. 2006. Adaptive properties of liv- ing beings: Proposal for a generic mechanism (self- programming machines IIl). Comptes Rendus Biolo- gies, 337
Armand Joulin and Tomás Mikolov. 2015. Inferring algorithmic patterns with stack-augmented recurrent nets. In Proc. Advances in Neural Information Pro- cessing Systems (NIPS), pages 190-198, Montreal, Canada.
Christian W. Omlin and C. Lee Giles. 1996. Construct- ing deterministic finite-state automata in recurrent neural networks. Journal of ACM, 43(6):937- 972.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pap- pas, and François Fleuret. 2020. Transformers are RNNs: Fast autoregressive transformers with linear attention. In Proc. Int. Conf. on Machine Learning (ICML), Virtual only.
Hao Peng. Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A Smith, and Lingpeng Kong. 2021. Random feature attention. In Int. Conf. Learning Representations (ICLR). Virtual only.
Hao Peng. Roy Schwartz, Sam Thomson, and Noah A. Smith. 2018. Rational recurrences. Proc. Conf. on Empirical Methods in Natural Language Processing (EMNLP), pages 1203-1214, Brussels, Belgium.
Stephen C Kleene. 1956. Representation of events in nerve nets and finite automata. Automata studies, 34:3-41.
John F. Kolen. 1993. Fool's gold: Extracting finite state machines from recurrent network dynamics. In Proc. Advances in Neural Information Processing Systems (NIPS). pages 501-508, Denver, CO, US.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. 2021. Attention is turing complete. The Journal of Machine Learning Research, 22(1):3463-3497.
Jordan B Pollack. 1990. Recursive distributed represen- Lations. Artificial Intelligence, 46(1-2):77-105.
Samuel A Korsky. 2019. On the computational power of RNNs. Master's ' thesis, Department of Electrical Engineering and Computer Science, Mussachusetts Institute of Technology.
Roy S Rubinstein and John N Shutt. 1993. Self- modifying finite automata. In Tech. Rept. WPI-CS- TR-93 1R-93-11.
Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. 2022. Trans- formers leamn shorteuts to automata. Preprint MrXiv:2210.10749
Roy S Rubinstein and John N Shutt. 1995. Self- modifying finite automata: An introduction. Infor- mation processing letters, 56(4):185-190.
Warren S McCulloch and Walter Pitts. 1943. A logical calculus of the ideas immanent in nervous activity. The bulletin of mathematcaal biophysics, 5(4):115- 133.
Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. 2021. Linear Transformers are secretly fast weight programmers. In Proc. Int. Conf. Machine Learn- ing (ICML), Virtual only.
William Merrill. 2019. Sequential neural networks as automata. Preprint rrXiv:1906.0140
Jürgen Schmidhuber. 1987. Evolutionary principles in relf-referential learning, or on learning how to learn: the meta-meta... hook. Ph.D. thesis, Technische Universität München.
William Merrill, 2020. On the linguistic capacity of real- time counter automata. Preprint arXiv:2004.06866
William Merrill, Ashish Sabharwal, and Noah A Smith. 2022. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics (TACL), 10:843-856.
Jürgen Schmidhuber. 1991. Learning to control fast- weight memories: An alternative to recurrent nets. Technical Report FKI-147-91, Institut für Informatik. Technische Universität München.

---

Jürgen Schmidhuber. 1992a. Learning to control fast- weight memories: An alternative to dynamic recur- rent networks. Neural Computation, 4(1):131-139
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 5998-6008, Long Beach, CA,, USA.
Jürgen Schmidhuber. 1992b. Steps towards "self-
referential" learning. Technical Report CU-CS-627. 92, Dept. of Comp. Sci., University of Colorado at Boulder.
Yue Wang, Katsushi Inoue, Akira Ito, and Tokio Okazaki, 1999. A note on modifying finite au- tomata. Information processing letters, 72(1-2): 19- 24.
Jürgen Schmidhuber. 1993. Reducing the ratio between learning complexity and number of time varying vari- ables in fully recurrent nets. In International Confer- ence on Artificial Neural Networks (ICANN), pages 460-463, Amsterdam, Netherlands.
Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018a. Extracting automata from recurrent neural networks using queries and counterexamples. In Proc. Int. Conf. on Machine Learning (ICML), pages 5244- 5253, Stockholm, Sweden.
Jürgen Schmidhuber, Felix Gers, and Douglas Eck. 2002. Learning nonregular languages: A comparison of simple recurrent networks and LSTM. Neural Computation. 1409)2203--241.
Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018b. On the practical computational power of finite precision for language recognition. In Proc. Association for Computational Linguistics (ACL), pages 740-745, Melbourne, Australia.
Jürgen Schmidhuber, Sepp Hochreiter, and Yoshua Ben- gio. 1999. Evaluating benchmark problems by ran- dom guessing. Field Guide to Dynamical Recur- rent Networks, Chapter 9, pages 231 231-235.
Gail Weiss, Yoav Goldberg, and Eran Yahav. 2019. Learning deterministic weighted automata with queries and counterexamples. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pages 8558-8569, Vancouver, Canada.
John N Shutt. 1995. Self-modifying finite automata- power and limitations. Computer Science technical Report WPI-CS-TR-95-4 Worcester Polytechnic In- stitute.
Hava T Siegelmann. 1996. Recurrent neural networks and finite automata. Computational intelligence, 12(4)5567-574.
Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021. Thinking like transformers. In Proc. Int. Conf. on Machine Learning (ICML), pages 11080-11090, Vir- tual only.
Hava T. Siegelmann and Eduardo D. Sontag. 1991. Tur- ing computability with neural nets. Applied Mathe-
Bernard Widrow and Marcian E Hoff. 1960. Adaptive switching circuits. In Proc. IRE WESCON Conven- tion Record, pages 104, Los Angeles, CA, USA.
matics Letters, 4(6))77-80.
Michael Sipser. 1996. Introduction to the Theory of Computation. ACM New York, NY, USA.
Shunyu Yao, Binghui Peng, Christos H. Papadimitriou, and Karthik Narasimhan. 2021. Self-attention net- works can process bounded hierarchical languages. In Proc. Association for Computationnal Linguistics (ACL), pages -7770-375,, Virtual only.
G Z Sun, C Giles, H H Chen, and Y C Lee. 1993. The neural network pushdown automation: model, stack and learning simulations. Technical report, University of Maryland at College Park, Technical report Nos. UMIACS-TR-93-77 CS-TR-3118.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. 2020. Are transformers universal approximators of sequence- to-sequence functions? In Int. Conf. on Learning Representations (ICLR), Addis Ababa, Ethiopia.
Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. 2019a. LSTM networks can perform dynamic counting. Proc. Workshop on Deep Learning and Formal Languages: Building Bridges, pages 44-54, Florence, Italy.
A RNNs and Theory of Computation
Mirac Suzgun. Sebastian Gehrmann, Yonatan Belinkov, and Stuart M Shieber, 2019b. augmeey-augmented recurrent neural networks can learn generalized Dyck languages. Preprint arXiv: 1913.3329.
RNNs have been related to Finite Automata (FAs) for many decades (McCulloch and Pitts, 1943; Kleene, 1956; Cleeremans et al., 1989; Siegelmann, 1996; Weiss et al., 2019; Korsky, 2019). Many works explore the extraction of FAs from trained RNNs (Giles al., 1992; Das and Mozer, 1993; Kolen, 1993; Omlin and Giles, 1996; Giles et al., 1999; Weiss et al., 2018a) (note that our work hints at the possibility to extract FAs also from LTs). Others use synthetic and formal languages
Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov. 2019. Transformer dissection: An unified under- standing for transformer's 's attention via the lens of kernel. In Proc. Conf. on Empirical Methods in Nat- urul Language Processing (EMNLP), pages 4344- 4353, Hong Kong, China.

---

For Proposition 3.3, the original proof of Bhat- tamishra et al. (2020a)'s Lemma C.4 shows that (13) Transformers without positional encoding can not recognise (aa)" because the output of the Trans- former is the same for all steps for this language benchmark RNNS (Allen, 1990; Schmidhuber al., 1999). The connection between RNNs and FAs also motivates certain architectural enhance- ments of RNNs, such as augmented RNNs (Pollack, 1990; Das et al., 1992; Sun et al., 1993; Joulin and Mikolov, 2015; Grefenstette et al., 2015; DuSell and Chiang. 2020).
solving certain counting tasks-a task checking whether two alphabets appear the same number of times in a sequence, in the former, and the Shuffle- languages in the latter. In both cases, as softmax is not explicitly required for computing normalised attention weights, the proofs directly remain valid for NLTs. Now. the question is whether they still hold for ULTs: is the normalisation of attention weights required? The answer is in both constructions. The core function of the layer consists in counting and comparing the occurrence of two symbols (e.g., opening and closing brackets in the case of Shuffle-k). The actual comparison is done by computing the difference between the two counts and comparing it against zero. This function is preserved without normalisation of attention weights. Therefore, these proofs can be directly adopted for ULTs.
For further references on theoretical works study- ing RNNs, see also Merrill (2019, 2020); Acker- man and Cybenko (2020), and for Transformers, see also Hahn (2020); Weiss et al. (2021); )); Liu et al. (2022); Yun et al. (2020); Pérez et al. (2021).
B Review of Linear Attention vs. FWPs
Here we briefly review the formal connection be- tween the "RNN-form" of LTs shown in Sec. 2 and attention (Katharopoulos et al., 2020; Schlag et al., 2021; Ba al., 2016). Starting from Eq. 5, using the definition of W, (Eq. 2) and 21 (Eq. 4),
yt:
2t )(q)) Woo(gt
(Ei=1 ey @ (k:t)) ((q))
(14) defined using a single symbol. There is no way to distinguish between odd and even steps, which is
E 0f (k. p(q))
r= v. Tó(qi)
(15) essential to recognise (aa)*. While this remains true for normalised linear attention resulting in uni- form attention weights, this argument does not di- rectly hold for unnormalised variants. Nevertheless, if we assume an extra layer normalisation layer fol- lowing the self-attention layer (which is typically the case in practice), the constant-output argument also holds for unnormalised linear attention.
Et= )
(16)
Φ k (p(:t)
where 01,7 Σt= okk,') TØ(q)) We can recog-
nise that this effectively attention with nor- malised weights at, using okk)), ut ((q)) as key, value, query vectors. For LTs/FWPs without nor- malisation of Eq. 5 (i.e., Eqs. 1-3), the derivation above is similar, but the corresponding attention weights are not normalised.
Finally, for Proposition 3.4, Merrill et al. (2020)'s proof for their Theorem 16 consists in "counting" the number of configurations of layer activations. This is independent of normalisation schemes, and remains valid for both unnormalised and normalised linear Transformers.
Note that this relation is analogous to the one that connects the perceptron to kernel machines (Aizerman et al., 1964; Irie et al., 2022a).
C.2 Experimental Details
Further details
Task Definition. For parity, (aa)", and (abab)", the output to be predicted at each step is the result for the prefix presented so far. For example for parity, if the input sequence is 0010, the output sequence should be TTFF, where T and F denote 'true' and "false" for parity. For Shuffle-2 (Suzgun et al. (2019a): mixture of two Dyck-1 languages, i.e., with two kinds of parentheses), we encode the task as follows. By denoting the parenthesis () as type-0 and [] as type-1, we consider four cases: '0'
C.1 Further Comments on Proofs
Here we provide some more comments on the proofs of our propositions presented in See. 3.
For both Proposition 3.1 and Proposition 3.2, the original proofs, i.e., the proof of Merrill al. (2020)'s Theorem 15 and that of Bhattamishra et al. (2020a)'s Proposition 4.1 respectively, consist in constructing a self-attention layer capable of

---

Table Hyper-paramenn search space.
Parameters
Values
Number of layers
[1, 2]
Hidden size
{8, 16, 32)
Feedforward block multiplier
{1, 2,
Number of heads
21,2,4)
Learning rate
(le-2, 2e-2, 3e-2, 1e-3, 2e-3, 3e-3)
Batch size
(16. 32, 64)
(both are closed), '1' (type-O is open), '2' (type-1 is open), '3' (both are open); for example, for the input (CJ), the output should be 2320.
deviation of 0.01/v //eaa while other sub-matrices //vdd use an std of 1/v Ahead (this is motivated by the fact that a generated query vector immediately mul- tiplied with the same SRWM to produce a value vector).
Dataset. We use the official (pre-generated) dataset made publicly available by Bhattamishra et al. (2020a), except for reset Dyck-1 which we generate ourselves using their official public code. "BinO" split contains sequences of "lengths" shorter than 50, while "Binl" contains those with "lengths" between 51 and 100. The exact definition of "length" above depends on the tasks; for tasks such as parity, directly refers to the actual sequence length; for tasks such as c"" it refers to n, i.e., the actual lengths of BinO sequences are up to 150 for b while they are between 153 and 300 for Binl sequences.
C.3 Details of e-LSTM
In the main text, evaluate the element-wiss LSTM with tied input-forget gates (e-LSTM; Irie al. (2023)) as an illustrative example of compu- tationally limited RNNs. e-LSTM is essentially an LSTM with only element recurrence, which can be seen as a Quasi-RNaa RNN (Bradbury et 2017) with element-wise recurrent gate functions. Here we provide its detailed description. Let dia and dout denote positive integers. At each time step I, e-LSTM transforms an input vector æ(t) E Rd to recurrent hidden state c(t) E Rd follows:
Hyper-parameter search spaces for all Trans- former family models (i.e., all models except LSTM and e-LSTM) are shown in Table 3. Note that "Feedforward block multiplier" refers to the factor Ni that relates the hidden size dmoddl of the Transformer to its feedforward up-projection size du, i.e., dr Nodmmode- For LSTM and e-LSTM, we use the same search space except that the num- ber of layers in (1. 2), and the hidden size is in (8, 16, 32, 64), and irrelevant parameters (i.e., the feedforward block multiplier and the number of heads) are ignored. The reported results are the best performance across all the hyper-paramelee search, done in previous work (Bhattamishra al., 2020a). Tables 4 and 5 display the best hyper-parameter configurations on each task for Recurrent Delta and SRWM models, respectively. For further details, we refer to our public code.
f()) = o (F + w o cll 1))
(17)
x() = (anh(Z w² U c(l 1))
(18)
c(f) = f(t) o c(t
f())
(tt)
(19)
o()) o (Ox(1) Woe(t)
(20)
h(() o(1) o c(l)
(21)
where f(1) Rddu x(1) E R and o(t) Rd
are activations, F Rdda Z E Bd xda O e Pdde xdin and W Rduu are trainable weight matrices, and finally, w IRd and w Rdon are trainable weight vectors.
Any other configurations for the SRWM fol- low those of Irie et al. (2022c), except that initialise the "query' projection sub-matrix in the reffereferential weight matrix using a normal dis- tribution with a mean value of and a standard

---

Table 4: Best hyper-yaratee pper--prrametrs for Recurrent Delta. When there more than one best configurations, report the one that converges the fastest.
Parameters
Parity
(aa)"
(abab)
a a"b"
b"
Shuffle-2
Dyck-1
Reset Dyck-1
Number layers Hidden size
2
8
8
16
16
Feedforward block multiplier
Number heads
4
Learning rate
2e-2
2e-2
2e-2
3e-2
2e-2
2e-2
3e-2
Batch size
16
16
16
16
32
Table 5: Best hyper- parameters for SRWM. When there are more than one best configurations, we report the one that converges the fastest.
Parameters
Parity
(aa)*
(abab)*
a"b"
c"
Shuffle-2
Dyck-1
Reset Dyck-1
Number of layers
1
2
1
2
1
1
Hidden size
8
16
16
16
8
8
16
16
Feedforward block multiplier
1
1
2
2
2
2
Number of heads
2
4
2
4
2
2
I Leanning rate
3c-2
2e-2
3e-2
le-2
2e-2
3e-2
3e-2
3c-2
Batch size
16
16
16
16
16
32
16
16


Reviews:
[{"review_id": "VO9IGoAlwU", "reviewer": "Reviewer_RMs4", "summary": "", "questions": "(A) The task description in 4.1 defines an output encoding different from the work cited before. Is there a reason to not use the same prediction scheme, sigmoid over possible classes and enumerating all classes that are possible (having a value greater than 0.5), instead of introducing class N for non-predictable?\n", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable time spent on reviewing our work and for very relevant/useful comments.\n\n> “*The four properties were rather briefly listed with notes on \"trivial\" proofs that follow previous work.*”\n\nYes, the reviewer is right.\nAt the same time, without highlighting these properties this way, we doubt that these results are trivial at all when the readers simply look at Eqs. 1-2;4-5. \nOverall, we consider that it is necessary (even unavoidable) and useful to have this “summary” of properties with specific pointers to the proof, which sets the stage to the main experimental section.\n\nFollowing Reviewer AXki’s suggestion, we plan to add a section in the appendix that highlights the key idea of each proof. This would also allow us to more specifically explain why the proof does not hold for the *unnormalized* variant (which we only briefly mention for Prop. 3.3 Line 239 *“For unnormalised LTs (Eqs. 1-3), certain proofs are not valid (e.g., the constant-output argument used for Prop. 3.3”*)). Hopefully this will also alleviate the reviewer’s concern (if the reviewer has any other suggestions, we’ll be very happy to take).\n\n> *”it remains unclear to me, whether these results are single-run experiments or whether they refer to best-k results from all corresponding configurations via hyperparameter search, as done in previous work.”*\n\nThank you for asking this clarification question: the reported results are the best performance across all the hyper-parameter search, as done in previous work.\nWhile we specified our hyper-parameter search space (in Appendix C, Line 717), the reviewer is right to point out that this specific information has not been explicitly mentioned. We’ll add this in the final version. In fact, we should also specify the best configuration found for each case. We will add a big table displaying the best hyper-parameter configuration for each model for each task in the appendix. Thank you very much for drawing our attention to this important aspect.\n\n> *”In section 4.1 task, prior work refers to Gers et al. 2000. I wonder, whether Gers et al. 2001 would fit better at this position.”*\n\nThank you very much for pointing this out. This is effectively a typo. We will replace “Gers et al. 2000” by “Gers et al. 2001” in the final version.\n\n> *”(A) The task description in 4.1 defines an output encoding different from the work cited before. Is there a reason to not use the same prediction scheme, sigmoid over possible classes and enumerating all classes that are possible (having a value greater than 0.5), instead of introducing class N for non-predictable?”*\n\nThank you for this expert question. It should be noted that the reference in question is rather old (Gers et al. 2001). In the modern context, we find it more natural to define the task as a simple *one-to-one sequence mapping problem*. This unifies the formulation across all the tasks used in this work, also allowing us to use the same code for all the tasks. Since this preserves the fundamental nature of the task, we opted for this formulation which we find more natural/convenient/elegant.\n\n> *”The motivation for two different tables should be more clear: why do they have different structures and why are experiments split into main vs Reset Dyck-1?”*\n\nUnlike in the experiments of Table 1, the hyper-parameter search space (specified in Appendix C) for the Reset Dyck-1 experiments (Table 2) is restricted to the *single-layer* case (following Bhattamishra al. (2020)’s observation that single-layer transformers fail at this task). This difference explains the separation into two tables. In the end, this also turned out to be good for space management, as Table 1 is already very large.\n\nRegarding the structure, the main goal of this table is to highlight the benefit of the delta rule; Table 2 compactly shows this in isolation (any other models are irrelevant for this discussion). Nevertheless, if the reviewer still thinks it's better to use exactly the same structure in Table 2 as in Table 1, we’ll be happy to change that in the final version.\n\n> *”L256: what CERTAIN languages? --> would be better to specify the described languages more concretely”*\n\nWe agree with the reviewer. We’ll replace it by an explicit sentence: “for $a^nb^n$ and $a^nb^nc^n$, we define…”. Thank you for pointing this out.\n\n> *”L300: solution\\_s”*\n\nThank you for pointing this out. We’ll fix it.\n\n> *’LL692: using input samples that correspond to the defined alphabet improves the comprehensibility, rather \"aabb\" than \"0011\"’*\n\nSince this example is for the parity task and using alphabets used in other tasks (“a” and “b”) may give rise to other confusions, we’ll use “T” and “F” as in True and False.\nThat is, Line 694 becomes “For example for parity, if the input sequence is 0010, the output sequence should be TTFF where “T” and “F” denote “true” and “false”’ for parity.” Thank you for pointing this out.\n\n> *”L250 \\& Table1: should refer to non-star-free regular languages instead”*\n\nYes, absolutely. We will fix it. Thank you very much.\n\nWe hope our response above brings clarifications to all the concerns raised by the reviewer.\nIf you find our response useful, we will appreciate it a lot if the reviewer can consider increasing the scores. Thank you.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Interesting work that combines theoretical aspects and empirical experiments for a better understanding of the capabilities of linear Transformers learning to recognize formal languages.\nWith their experiments, they give evidence that the mentioned extensions improve performance on some tasks and lead to higher capabilities of the LT architecture.\n", "reasons_to_reject": "The authors state in the beginning that many well-known results transfer directly from Transformers to linear Transformers.\nThe four properties were rather briefly listed with notes on \"trivial\" proofs that follow previous work.\n\nThe results in the paper are described as accuracies of various models but solely from this description, it remains unclear to me, whether these results are single-run experiments or whether they refer to best-k results from all corresponding configurations via hyperparameter search, as done in previous work.\nAccordingly, it is difficult to decide how much significance the results finally have.\n", "questions_to_authors": "(A) The task description in 4.1 defines an output encoding different from the work cited before. Is there a reason to not use the same prediction scheme, sigmoid over possible classes and enumerating all classes that are possible (having a value greater than 0.5), instead of introducing class N for non-predictable?\n", "paper_topic_and_main_contributions": "In their paper, the authors study variants of auto-regressive Transformers with linearized attention, focusing on linear Transformers (LT).\nThey argued that previous work on the language capabilities (recognition of formal languages) of RNN and Transformer architectures also holds for normalized LTs (Section 3).\nFurther, they empirically study the capabilities of unnormalized LTs using the challenge sets studied by Bhattamishra et al. (2020) and further examine three recently published architecture extensions in their experiments (delta-rule, recurrence, self-reference).\nThey show improvements in non-star-free regular language examples by recurrence and self-reference.\nFurther, they show that the delta rule allows LTs to recognize Reset Dyck-1, which is not possible without this extension.\n", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "In section 4.1 task, prior work refers to Gers et al. 2000. I wonder, whether Gers et al. 2001 would fit better at this position. Also using a different encoding seems rather confusing, without giving an argument here.\n\nThe motivation for two different tables should be more clear: why do they have different structures and why are experiments split into main vs Reset Dyck-1?\n\nL256: what CERTAIN languages? --> would be better to specify the described languages more concretely\nL300: solution_s\nLL692: using input samples that correspond to the defined alphabet improves the comprehensibility, rather \"aabb\" than \"0011\"\nL250 & Table1: should refer to non-star-free regular languages instead\n\n"}}, {"review_id": "rEFRZUZCaF", "reviewer": "Reviewer_5khN", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 1, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable time spent on reviewing our work.\n\n> *\"I do not see how these observations can lead to advances in the field.\"*\n\nWe acknowledge that this research topic is not the reviewer’s area (“Reviewer Confidence: 1: Not my area”), and therefore, we can understand that this type of question may arise (even though, generally speaking, we respectfully note that some might perceive such a statement as highly offensive).\n\nWe first would like to point out that the research approach studying neural networks using formal languages is a well-established domain. Our work builds upon many prior works (please refer to our introduction as well as Appendix A for further references). It consists of studying capabilities of neural architectures to learn to recognise formal languages.\n\nFormal languages allow us to evaluate *in isolation* some *specific* computational/generalisation abilities or shortcomings (such as counting abilities) that are the essence of more complex computations. These abilities/shortcomings are often difficult to identify when directly working on complex real-world tasks which involve a combination of various computational abilities. Beyond the scholastic values of answering the fundamental question of “what models can learn to compute”, experiments using formal languages allow us to analyse/characterise the impact of certain architectural changes on the model’s computational capabilities.\nFor example, in this work, we showed that the recurrent or self-referential extensions of linear Transformers fix the deficiency of the original models on non-star-free languages including the parity. Prior works focused only on real-world applications have failed to identify these properties. Given that the Transformer’s deficiency on the parity task is a very famous problem in this field (see Hahn 2020, inter alia), it is important to demonstrate that these architectural changes address this fundamental limitation.\n\nWe hope that our response brings novel perspectives to the reviewer's vision and perception of research on neural networks using formal languages. This topic, as evidenced by the numerous prior works we have cited, holds significant interest within the EMNLP/*ACL community.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The paper is clear and well written.\n- The paper provides some interesting results.", "reasons_to_reject": "- I do not see how these observations can lead to advances in the field.", "questions_to_authors": "", "paper_topic_and_main_contributions": "In this paper, the authors discuss the computational power of Transformers with linearised attention (Linear Transformers) in the context of formal languages.\nThe authors show that Linear Transformers inherit several limitations and capacities of the vanilla transformer: failing on non-star regular languages and performing well on counter languages.\nThe authors also show that the delta-rule does not improve these results but recurrence and self-reference do.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HoWRQasqQQ", "reviewer": "Reviewer_Dg9f", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable time spent on reviewing our work.\n\n> *\"(1) The paper focuses on a narrow set of formal language recognition tasks that may not reflect the real-world performance or challenges of linear Transformers or their extensions.\"*\n\nThis *“narrow”* set of formal language has been specifically selected based on the prior works exploring computational capabilities of Transformers (namely Bhattamishra et al. (2020)). This allowed us to focus on the most relevant formal languages.\n\nRegarding real-world performance vs. formal languages, this criticism generally applies to any works studying neural networks using formal languages (please see all the papers we cited in the introduction and Appendix A). Formal languages allow us to evaluate *in isolation* some *specific* computational abilities or shortcomings (such as counting abilities) that are the essence of more complex computations. These abilities/shortcomings are often difficult to identify when directly working on complex real-world tasks which involve a combination of various computational abilities. Beyond the scholastic values of answering the fundamental question of “what models can learn to compute”, experiments using formal languages allow us to analyse/characterise the impact of certain architectural changes on the model’s computational capabilities.\nIn this work, we showed that the recurrent or self-referential extensions of linear Transformers fix the deficiency of the original models on non-star-free languages including the parity. Prior works focused on real-world applications have failed to identify these properties. Given that the Transformer’s deficiency on the parity task is a very famous problem in this field (see Hahn 2020, inter alia), it is important to demonstrate that these architectural changes address this fundamental limitation.\n\n> *\"(2) The paper does not compare linear Transformers with other existing models that can also recognize formal languages, such as RNNs with external memory or stack-augmented RNNs. \"*\n\nHere our focus is on tasks/formal languages on which the vanilla LTs and Transformers fail (based on Bhattamishra et al. 2020's prior work), to demonstrate how the three extensions enhance the LTs' capabilities. As can be seen in Table 1, the vanilla LSTM can perfectly recognise all these tasks, and any more powerful models (not shown here) can also do so. So further comparison with memory-augmented RNNs will not add much more value into this picture (than comparing to the LSTM baseline) within the scope of this work.\n\nNethertheless, going beyond the scope of this work, further (theoretical) investigations into recurrent or self-referential extensions may benefit from proofs (e.g., by Merrill et al. 2020) or tasks (e.g. Delétang et al (2023); see also our limitation section Line 351) used in the existing works studying computational abilities of memory-augmented RNNs. We leave this for future work. We will be happy to mention this more explicitly in our limitation section (starting from Line 340).\n\n> *\"(3) The paper does not provide enough details or analysis on how the recurrent and self-referential extensions affect the computational complexity or scalability of linear Transformers.\"*\n\nWe’d like to emphasise that the architectures themselves are not a contribution of this work. They have been proposed in prior works (Schlag et al, 2021, Irie et al, 2021/2022c) *along with discussions on their computational complexity*. In fact, the result is simple: *all* these models have a linear time complexity w.r.t. the sequence length (this is why they are “linear” Transformers) unlike the standard Transformers with the quadratic complexity. Naturally, actual per-time-step computational costs differ from one model to another (which also depend on the actual implementation). For further discussions on wall-clock time comparisons etc., we directly refer to Schlag et al. (2021) and Irie et al. (2021) which have dedicated discussions about this.\nHere we focus on “computational abilities” of these models which have never been discussed in prior works.\n\nFinally, regarding the “Reproducibility” score of 2, as we promised in the first page of our paper (footnote 1), we will release our entire code publicly if the paper is accepted. As we specified in Line 704, the used dataset is also from the public repository by Bhattamishra et al. (2020); we will specify the exact link in our public repository. Hopefully this will improve the reviewer’s view on the reproducibility of this work.\n\nWe hope our response brings clarifications to the major concerns raised by the reviewer. \nIf you find our response useful, we will appreciate it a lot if the reviewer can consider increasing the scores. Thank you.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The paper provides both theoretical and empirical results that shed light on the properties and limitations of linear Transformers, a computationally efficient variant of standard Transformers. \n", "reasons_to_reject": "(1) The paper focuses on a narrow set of formal language recognition tasks that may not reflect the real-world performance or challenges of linear Transformers or their extensions.\n(2) The paper does not compare linear Transformers with other existing models that can also recognize formal languages, such as RNNs with external memory or stack-augmented RNNs.\n(3) The paper does not provide enough details or analysis on how the recurrent and self-referential extensions affect the computational complexity or scalability of linear Transformers.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The main contributions of the paper are: (1) This paper provides a theoretical analysis of the expressive power of normalised linear Transformers, showing that they inherit several capabilities and limitations of standard Transformers. For example, they can recognize certain counter languages, but not certain regular languages. (2) The paper empirically evaluates unnormalised linear Transformers and their extensions on several formal language recognition tasks, using both positive and negative examples. The paper demonstrates that recurrent and self-referential extensions can successfully solve and generalize on tasks that the standard linear Transformer fails on, such as parity, (aa) ∗ , and (abab) ∗ .", "excitement": 4, "reproducibility": 2, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UprKez6xXS", "reviewer": "Reviewer_AXki", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 1, "soundness": 2, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable time spent on reviewing our work.\nWe acknowledge that this topic is not the reviewer’s area (“Reviewer Confidence: 1: Not my area”).\n\n> *\"The authors should at least review the proof details in the Appendix so that the paper is at least self-contained.\"*\n\nThis is indeed a good idea. This will also allow us to add more comments on WHY the proof in question does not hold for the unnormalized variants (we only hinted at this for one proposition in Line 239: *“For unnormalised LTs (Eqs. 1-3), certain proofs are not valid (e.g., the constant-output argument used for Prop. 3.3”*). We will add such a section in the appendix in the final version of this paper. Thank you for this suggestion.\n\n> *\"My main concern is the lack of novelty. All proofs in the paper are borrowed from previous works with one or two sentences of description.\"*\n> *\"As it stands, it is difficult to judge the technical contribution as well as the correctness of the proofs in the paper.\"*\n\nWe would like to emphasise that our core technical contributions and “novelty” are mainly in the experimental part. Our experiments show that the recurrent or self-referential extensions of linear Transformers enable them to recognise certain non-star-free languages including the parity. Since Transformers’ deficiency on the parity task is a very famous problem in this field (see Hahn 2020, inter alia), it is important to demonstrate how these architectural changes address this fundamental limitation. To the best of our knowledge, no prior work on linear Transformers has discussed these perspectives/benefits.\n\nAlso regarding the proofs, without highlighting these properties this way, we doubt that these results are trivial at all when the readers simply look at Eqs. 1-2;4-5 (we hope the reviewer concurs). Overall, we think it is useful to have this “summary” of properties with specific pointers to the proof, which sets the stage to the main experimental section.\n\nHopefully, our response successfully directs the reviewer's attention to our experimental section and the corresponding contributions, which (as we respectfuly note) are *completely* ignored in the original review.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The paper considers a class of Transformers that so far has not been studied closely for its computational expressivity.", "reasons_to_reject": "My main concern is the lack of novelty. All proofs in the paper are borrowed from previous works with one or two sentences of description. The authors should at least review the proof details in the Appendix so that the paper is at least self-contained. As it stands, it is difficult to judge the technical contribution as well as the correctness of the proofs in the paper.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper investigates the computational expressivity of linear Transformers as well as several of its variants. By borrowing proofs from previous papers, the paper concludes that linear Transformers share some properties with the original Transformer. The paper conclude by performing experiments on linear Transformer's ability to model formal languages.", "excitement": 2, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7KobWcNbfD", "reviewer": "Reviewer_Vzz8", "summary": "", "questions": "It is generally a belief that LTs are weaker than vanilla Transformers. Can you make some discussions about that?", "limitations": "", "rating": 2, "confidence": 2, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable time spent on reviewing our work.\n\n> *\"Theoretical contributions is incremental since the proofs from previous studies remain valid for LTs. \"*\n\nYes, our core technical contributions and “novelty” are mainly in the experimental section. At the same time, without highlighting these properties this way, we doubt that these results are trivial at all when the readers simply look at Eqs. 1-2;4-5 (we hope the reviewer concurs). Stating that these proofs remain valid (and also observing that they are no longer valid for the *unnormalised* case) is a necessary/important step. Overall, we think it is useful to have this “summary” of properties with specific pointers to the proof, which sets the stage to the main experimental section.\n\n> *\"Additionally, experiments suggest that LTs inherit Transformer properties, which also appears trivial.\"*\n\nThis statement is not fully accurate. It is true that the *vanilla* LTs directly inherits some of the standard Transformers’ properties discussed here, but this is not the case for their extensions.\nOur experiments show that the recurrent or self-referential extensions of linear Transformers enable them to recognise certain non-star-free languages including the parity. Since Transformers’ deficiency on the parity task is a very famous problem in this field (see Hahn 2020, inter alia), it is important to show that these architectural changes address this fundamental limitation. To the best of our knowledge, no prior work on linear Transformers has discussed these perspectives/benefits.\n\n> *\"It is generally a belief that LTs are weaker than vanilla Transformers. Can you make some discussions about that?\"*\n\nBy *\"weaker\"* we assume that the reviewer is referring to the *empirical* performance\n(we have to be careful with the usage of the word *“weak”* here, since the paper is about computational capabilities).\n\nIt is not a *“belief”*: there are many empirical evidences showing that the (in particular, vanilla) LTs underperform the standard Transformers (see, e.g. Schlag et al. 2021 which also show how the delta rule closes the gap between LTs and the standard Transformers).\nHowever, LTs have their unique benefits. In addition to their linear time-complexity advantage, LTs/FWPs have constant-size states which facilitate certain applications (e.g., reinforcement learning in game environments), and also bring novel/conceptual insights to Transformers as networks generating weights for other networks (for example, understanding in-context learning [von Oswald et al. Transformers learn in-context by gradient descent ICML 2023]). We generally consider the argument of type “this is believed to be weak, so it is not interesting” (we are not sure if this is what the reviewer is hinting at) is unfortunate as it may miss many opportunities and insights.\nIf the reviewer wishes, we'll be happy to add a few sentences about this discussion in Appendix B.\n\nWe hope that our response successfully draws the reviewer's attention to the core contributions of our empirical results (we respectfully point out that they are completely ignored in the original review), and improves the reviewer’s overall rating of this work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The paper theoretically reveals the computational power of LTs, and empirically verifies LTs' abilities on formal language recognition tasks. It is nice to have such results for reference.", "reasons_to_reject": "Theoretical contributions is incremental since the proofs from previous studies remain valid for LTs. Additionally, experiments suggest that LTs inherit Transformer properties, which also appears trivial.", "questions_to_authors": "It is generally a belief that LTs are weaker than vanilla Transformers. Can you make some discussions about that?", "paper_topic_and_main_contributions": "This paper discusses the computational power of linear transformers (LTs) and fast weight programmers (FWPs). It also tests these methods and their extensions, such as delta-rule, recurrence, and self-reference, to see how effective they are in formal language recognition tasks.", "excitement": 2, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: **Summary of Reviews and Post-Rebuttal Discussion:**

Reviewer RMs4 appreciated the combination of theoretical and empirical aspects of the paper and acknowledged the deeper understanding it offers on the capabilities of linear Transformers. However, they raised concerns regarding the clarity of certain results, whether results were from single-run experiments or hyperparameter searches, and pointed out specific issues related to citations, task descriptions, and the overall presentation. The authors addressed these concerns in their rebuttal, providing explanations for their design choices, acknowledging and promising to fix some issues, and clarifying certain aspects of their experimental design.

Reviewer 5khN recognizes the clarity and well-written nature of the paper, and commends it for its interesting results. The main criticism stems from uncertainty about how the findings might advance the field, which the authors addressed in their rebuttal by pointing out the importance and relevance of studying neural networks using formal languages.

Reviewer Dg9f praised the paper for its theoretical analysis of normalized linear Transformers' expressive power and their empirical evaluations on formal language recognition tasks. The paper effectively provides insights into the properties and limitations of linear Transformers, a computationally efficient alternative to standard Transformers. Criticisms include the paper's limited focus on certain formal language tasks, not comparing linear Transformers to models like RNNs with external memory, and not thoroughly exploring the computational complexity of certain extensions. In response, the authors argued that their chosen languages are based on prior research and are meant to assess specific computational capabilities. They defended the absence of comparisons by focusing on tasks where traditional linear Transformers falter and clarified that their main contribution isn't the architecture but the insights provided, with computational complexities discussed in earlier research.

Reviewer Vzz8 highlighted that while the theoretical aspects are incremental, the paper makes novel contributions in the experimental section. The experiments indicate that the extensions of linear Transformers allow the model to recognize specific non-star-free languages. The authors defended their contributions in the rebuttal, emphasizing the importance of their results.

Reviewer AXki criticized the submission for its lack of novelty, noting an over-reliance on proofs from previous works. The authors defended their work, emphasizing the technical contributions and novel findings in the experimental section, particularly about the capabilities of linear Transformers to recognize non-star-free languages. Despite the authors' rebuttal, the reviewer remained skeptical about the paper's novelty, citing unfamiliarity with the extensively cited prior works.

It should be noted that overall confidence of reviewers was very low. Reviewers 5khN and AXki reported confidence 1 and the rest reported confidence 2. Still, reviewers mainly align in their judgment of soundness and excitement of the paper.

**Soundness:**
The paper appears to be mostly sound in its claims and arguments. The reviewers' concerns were mainly about clarity and presentation rather than the validity of the results. The authors have proposed solutions to address the clarity issues.

**Excitement:**
There is a mixed reception to the paper's excitement level. Some reviewers have reservations about the paper's potential to advance the field. However, the authors' rebuttal was strong, indicating the importance of studying neural architectures with formal languages.
Decision: Accept-Main