mlsanityData to 7 Oct 2026

Looped ReLU MLPs May Be All You Need as Practical Programmable Computers

arXiv 2410.09375 ↗First posted 12 Oct 2024cs.LG cs.AI cs.CCcited by 19

Not on the map. Why?

Abstract (arXiv)

Previous work has demonstrated that attention mechanisms are Turing complete. More recently, it has been shown that a looped 9-layer Transformer can function as a universal programmable computer. In contrast, the multi-layer perceptrons with mathsfReLU activation (mathsfReLU-mathsfMLP), one of the most fundamental components of neural networks, is known to be expressive; specifically, a two-layer neural network is a universal approximator given an exponentially large number of hidden neurons. However, it remains unclear whether a mathsfReLU-mathsfMLP can be made into a universal programmable computer using a practical number of weights. In this work, we provide an affirmative answer that a looped 23-layer mathsfReLU-mathsfMLP is capable of performing the basic necessary operations, more efficiently and effectively functioning as a programmable computer than a looped Transformer. This indicates simple modules have stronger expressive power than previously expected and have not been fully explored. Our work provides insights into the mechanisms of neural networks and demonstrates that complex tasks, such as functioning as a programmable computer, do not necessarily require advanced architectures like Transformers.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 56 of its 94 references that are in the map. First posted on arXiv 12 Oct 2024.

Builds on

56 of 94 references.

References · 56

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  4. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  6. 2022Large Language Models are Zero-Shot Reasonerscited by 4,323
  7. 2021Finetuned Language Models Are Zero-Shot Learnerscited by 3,747
  8. 2022Emergent Abilities of Large Language Modelscited by 2,483
  9. 2024Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phonecited by 1,883
  10. 2021ViViT: A Video Vision Transformercited by 1,610
  11. 2022Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?cited by 1,413
  12. 2021Transformers in Vision: A Surveycited by 1,009
38 more
  1. 2022In-context Learning and Induction Headscited by 930
  2. 2022Transformers learn in-context by gradient descentcited by 714
  3. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 671
  4. 2020A Survey on Visual Transformercited by 653
  5. 2018Universal Transformerscited by 613
  6. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  7. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  8. 2023Transformers learn to implement preconditioned gradient descent for in-context learningcited by 274
  9. 2022Transformers Learn Shortcuts to Automatacited by 260
  10. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  11. 2023Looped Transformers as Programmable Computerscited by 224
  12. 2019Universal Approximation with Deep Narrow Networkscited by 198
  13. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  14. 2021Thinking Like Transformerscited by 182
  15. 2023One Step of Gradient Descent is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attentioncited by 168
  16. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  17. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  18. 2023Teaching Arithmetic to Small Transformerscited by 121
  19. 2024Is A Picture Worth A Thousand Words? Delving Into Spatial Reasoning for Vision Language Modelscited by 111
  20. 2023Fast Attention Requires Bounded Entriescited by 102
  21. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  22. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 99
  23. 2024Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning?cited by 60
  24. 2022A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Featurescited by 49
  25. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  26. 2024Induction Heads as an Essential Mechanism for Pattern Matching in In-context Learningcited by 46
  27. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  28. 2024Why Larger Language Models Do In-context Learning Differently?cited by 44
  29. 2024On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysiscited by 41
  30. 2024Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalabilitycited by 39
  31. 2024Discovering the Gems in Early Layers: Accelerating Long-Context LLMs with 1000x Input Token Reductioncited by 39
  32. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  33. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  34. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 29
  35. 2024Unraveling the Smoothness Properties of Diffusion Models: A Gaussian Mixture Perspectivecited by 24
  36. 2024OmniControlNet: Dual-stage Integration for Conditional Image Generationcited by 24
  37. 2023Dolfin: Diffusion Layout Transformers without Autoencodercited by 23
  38. 2024Fourier Circuits in Neural Networks and Transformers: A Case Study of Modular Arithmetic with Multiple Inputscited by 22

50 most cited of 56 All 56 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 8; 2025: 10; 2026: 1.

19 papers.

Sort:

By area:

  1. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 35
  2. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  3. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 21
  4. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  5. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  6. 2025High-Order Matching for One-Step Shortcut Diffusion Modelscited by 15
  7. 2025A Formal Comparison Between Chain of Thought and Latent Thoughtcited by 14
  8. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  9. 2025Force Matching with Relativistic Constraints: A Physics-Inspired Approach to Stable and Efficient Generative Modelingcited by 12
  10. 2025Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolationcited by 11
  11. 2025Circuit Complexity Bounds for Visual Autoregressive Modelcited by 10
  12. 2025On Computational Limits of FlowAR Models: Expressivity and Efficiencycited by 10
7 more
  1. 2025Theoretical Guarantees for High Order Trajectory Refinement in Generative Flowscited by 9
  2. 2024Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Studycited by 4
  3. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  4. 2024Unlocking the Theory Behind Scaling 1-Bit Neural Networkscited by 3
  5. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformerscited by 3
  6. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  7. 2026Loom: A Scalable Analytical Neural Computer Architecturecited by 0