Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions
Open accessAbstract
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.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Delta-rule-based recurrent models face theoretical limitations and moderate performance in practice.
“Despite significant advantages, even these delta-rule-based recurrent models face theoretical limitations (Irie et al. 2023) with moderate performance in practice (Yang et al. 2024c).”
From It's All Connected: A Journey Through Test-Time Memorization, Attentional Bias, Retention, and Online Optimization (2025) · cites this paper as Irie et al. 2023
Cites
Rethinking Attention with Performers
Choromanski, K., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J., Mohiuddin, A., Kaiser, L., et al. (2020) · arXiv · doi:10.48550/arxiv.2009.14794 · Cited by 695 · cited 1× · see citing works
“Here we focus on auto-regressive Transformers with linearised attention a.k.a. linear Transformers (LTs; Katharopoulos et al. (2020); Choromanski et al. (2021); Peng et al. (2021)) or Fast Weight Programmers (FWPs; Schmidhuber (1991, 1992a); Schlag et al. (2021); Irie et al. (2021)).”
BackgroundIrie, K., Csordás, R., & Schmidhuber, J. (2022) · arXiv · doi:10.48550/arxiv.2202.05798 · Cited by 6 · cited 1× · see citing works
“Note that this relation is analogous to the one that connects the perceptron to kernel machines (Aizerman et al., 1964; Irie et al., 2022a).”
BackgroundSelf-citation
Flagged first, then by citations
Cited by
Sorted by citations
Learning to (Learn at Test Time): RNNs with Expressive Hidden States
Sun, Y., Li, X., Dalal, K., Xu, J., Vikram, A., Zhang, G., Dubois, Y., Chen, X., Wang, X., Koyejo, S., et al. (2024) · arXiv · doi:10.48550/arxiv.2407.04620 · Cited by 18 · see citing works
“In addition, [40] builds an image generator using the images as fast weights, [37] applies continuous-time extensions of FWPs to time-series classification, while [36] and [26] demonstrate how the choice of update rules a ff ects the expressiveness of FWPs on formal language recognition tasks.”
Nested Learning: The Illusion of Deep Learning Architectures
Behrouz, A., Razaviyayn, M., Zhong, P., & Mirrokni, V. (2025) · arXiv · doi:10.48550/arxiv.2512.24695 · Cited by 1 · see citing works
End-to-End Test-Time Training for Long Context
Tandon, A., Dalal, K., Li, X., Koceja, D., Rød, M., Buchanan, S., Wang, X., Leskovec, J., Koyejo, S., Hashimoto, T., et al. (2025) · arXiv
“…by themselves, [51] builds an image generator using the images as fast weights, [48] applies continuous-time extensions of FWPs to time-series classification, while [47] and [31] demonstrate how the choice of update rules a ff ects the expressiveness of FWPs on formal language recognition tasks.”
Behrouz, A., Razaviyayn, M., Zhong, P., & Mirrokni, V. (2025) · arXiv · doi:10.48550/arxiv.2504.13173
- Authors
- Irie, K., Csordás, R., & Schmidhuber, J.
- Affiliations
- Harvard University (US)
- University of Applied Sciences and Arts of Southern Switzerland (CH)
- Corresponding author
- Irie, Kazuki
- ORCID
- Schmidhuber, Jürgen
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2023
- Pages
- 9455-9465
- arXiv
- 2310.16076
- OpenAlex
- W4389519032
- Cited by
- 3
- References
- 2
- Citations by year
- 2025: 3
- FWCI
- 1.24
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Conference on Empirical Methods in Natural Language Processing (EMNLP) (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Funders
- National Science Foundation
- Nvidia
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
- Centro Svizzero di Calcolo Scientifico
- National Supercomputing Centre Singapore
- H2020 European Research Council (742870)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Keywords
- linear transformer, recurrent neural networks, self-attention, computational power, language identification, parity problem, finite precision computation, real-time processing, sequence processing
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
