mlsanityData to 14 Oct 2026

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

arXiv 2310.16076 ↗First posted 24 Oct 2023cs.LGcited by 20

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 20 papers in the map (data through 14 Oct 2026). Builds on 42 of its 83 references that are in the map. First posted on arXiv 24 Oct 2023.

Builds on

42 of 83 references.

References · 42

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,057
  3. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
  4. 2020Rethinking Attention with Performerscited by 1,601
  5. 2021Linear Transformers Are Secretly Fast Weight Programmerscited by 502
  6. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  7. 2021Random Feature Attentioncited by 354
  8. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  9. 2022Neural Networks and the Chomsky Hierarchycited by 217
  10. 2019Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernelcited by 213
  11. 2021Thinking Like Transformerscited by 184
  12. 2016Using Fast Weights to Attend to the Recent Pastcited by 170
30 more
  1. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  2. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  3. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
  4. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  5. 2019Language Modeling with Deep Transformerscited by 96
  6. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  7. 2021Going Beyond Linear Transformers with Recurrent Fast Weight Programmerscited by 89
  8. 2016Quasi-Recurrent Neural Networkscited by 87
  9. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  10. 2015Inferring Algorithmic Patterns with Stack-Augmented Recurrent Netscited by 76
  11. 2017Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamplescited by 66
  12. 2020A Formal Hierarchy of RNN Architecturescited by 62
  13. 2015Learning to Transduce with Unbounded Memorycited by 54
  14. 2019Sequential Neural Networks as Automatacited by 54
  15. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
  16. 2022The Dual Form of Neural Networks Revisited: Connecting Test Time Predictions to Training Patterns via Spotlights of Attentioncited by 46
  17. 2019LSTM Networks Can Perform Dynamic Countingcited by 45
  18. 2022A Modern Self-Referential Weight Matrix That Learns to Modify Itselfcited by 41
  19. 2019On the Computational Power of RNNscited by 35
  20. 2019Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languagescited by 31
  21. 2017Recurrent Neural Networks as Weighted Language Recognizerscited by 30
  22. 2019Learning Deterministic Weighted Automata with Queries and Counterexamplescited by 22
  23. 2023Exploring the Promise and Limits of Real-Time Recurrent Learningcited by 19
  24. 2018Rational Recurrencescited by 18
  25. 2020On the Linguistic Capacity of Real-Time Counter Automatacited by 17
  26. 2020A Survey of Neural Networks and Formal Languagescited by 17
  27. 2022Neural Differential Equations for Learning to Program Neural Nets Through Continuous Learning Rulescited by 16
  28. 2020Learning Context-Free Languages with Nondeterministic Stack RNNscited by 15
  29. 2017The Neural Network Pushdown Automaton: Model, Stack and Learning Simulationscited by 10
  30. 2022Images as Weight Matrices: Sequential Image Generation Through Synaptic Learning Rulescited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 8; 2025: 7; 2026: 4.

20 papers.

Sort:

By area:

  1. 2024Gated Delta Networks: Improving Mamba2 with Delta Rulecited by 532
  2. 2024Parallelizing Linear Transformers with the Delta Rule over Sequence Lengthcited by 396
  3. 2024Learning to (Learn at Test Time): RNNs with Expressive Hidden Statescited by 355
  4. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 101
  5. 2025DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Productscited by 75
  6. 2025It's All Connected: A Journey Through Test-Time Memorization, Attentional Bias, Retention, and Online Optimizationcited by 64
  7. 2025End-to-End Test-Time Training for Long Contextcited by 62
  8. 2026Self-Improvements in Modern Agentic Systems: A Surveycited by 19
  9. 2025TempoPFN: Synthetic Pre-training of Linear RNNs for Zero-shot Time Series Forecastingcited by 17
  10. 2024Autoregressive Large Language Models are Computationally Universalcited by 15
  11. 2025Blending Complementary Memory Systems in Hybrid Quadratic-Linear Transformerscited by 12
  12. 2024Rethinking Transformers in Solving POMDPscited by 9
8 more
  1. 2025Sequential-Parallel Duality in Prefix Scannable Modelscited by 8
  2. 2025Fast weight programming and linear transformers: from machine learning to neurobiologycited by 8
  3. 2023Metalearning Continual Learning Algorithmscited by 7
  4. 2024Why Are Positional Encodings Nonessential for Deep Autoregressive Transformers? Revisiting a Petroglyphcited by 6
  5. 2024Overcoming classic challenges for artificial neural networks by providing incentives and practicecited by 3
  6. 2026Self-Modulating Quantum Fast-Weight Programmers for Efficient Adaptive Sequential Learningcited by 2
  7. 2026Universal computation is intrinsic to language model decodingcited by 1
  8. 2026Why Depth Matters in Parallelizable Sequence Models: A Lie Algebraic Viewcited by 1