REVIEW 8 cited by
Looped ReLU MLPs May Be All You Need as Practical Programmable Computers
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
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 $\mathsf{ReLU}$ activation ($\mathsf{ReLU}$-$\mathsf{MLP}$), 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 $\mathsf{ReLU}$-$\mathsf{MLP}$ 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 $\mathsf{ReLU}$-$\mathsf{MLP}$ 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.
Forward citations
Cited by 8 Pith papers
-
LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers
LazyDiT learns small gates that decide when to reuse cached layer outputs, cutting diffusion transformer compute by up to half while matching or beating DDIM quality.
-
Numerical Pruning for Efficient Autoregressive Models
A Newton's method derived importance score plus a constrained least-squares compensation prunes LLaMA and LlamaGen models with reported gains over LLM-Pruner, SliceGPT, and FLAP.
-
Force Matching with Relativistic Constraints: A Physics-Inspired Approach to Stable and Efficient Generative Modeling
Force Matching replaces velocity matching in flow-based generative models with a relativistic force objective, but the toy experiments are designed so the model class matches the data generator exactly.
-
Universal Approximation of Visual Autoregressive Transformers
The paper's headline claim that VAR transformers universally approximate all Lipschitz image maps is not supported, because the theorem restricts the target class and its key lemma has an invalid linearity step.
-
High-Order Matching for One-Step Shortcut Diffusion Models
HOMO extends shortcut diffusion with acceleration and jerk supervision, but the proof of superior approximation is not supported and experiments lack error bars.
-
Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolation
VLFM models video latent patches as a HiPPO-LegS polynomial flow and trains a flow matching model to generate frames, claiming bounded interpolation and extrapolation error.
-
On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis
Under SETH, the paper claims VAR models cannot be approximated faster than O(n^4) when attention entries are Theta(sqrt(log n)), but can be approximated in O(n^{2+o(1)}) when entries are o(sqrt(log n)).
-
Circuit Complexity Bounds for Visual Autoregressive Model
The authors show that a simplified formalization of the VAR image generation model lies in DLOGTIME-uniform TC0, meaning it can be simulated by constant-depth threshold circuits with polynomial size and precision.
Discussion (0). Continue with ORCID to comment.