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

INTRODUCTION

Transformers have demonstrated their potential across a variety of tasks, emerging as a dominant choice for a wide spectrum of practical applications, including natural language processing (NLP) and computer vision , among others. The success of Transformers is largely attributed to their ability to perform complex operations, such as induction head , in-context learning , information retrieval and chain of thoughts . Meanwhile, there is another line of research that explores the theoretical capability of Transformers. For instance, PBM has proven the Turing completeness of the attention mechanism. However, Turing completeness is not a feature unique to Transformers. SS , CS has demonstrated that Recurrent Neural Networks (RNNs) are also Turing complete. Other works have shown that the most basic module in deep learning, the Multi-Layer Perceptron (MLP), is a universal approximator.

However, the concept of Turing completeness inherently necessitates infinite memory, an impracticality in real-world scenarios due to the finite nature of available memory. In , they bridge the gap between the theoretical Turing machine and the practical Transformer-based programmable computer by illustrating that a looped $13$-layer Transformer possesses the necessary expressiveness to operate as a programmable computer. Given that ReLU-MLP also has the capability for achieving Turing completeness and itself is an universal approximator, this raises an interesting question:

Is ReLU-MLP expressive enough to be a practical programmable computer?

To the best of our knowledge, no practical solution for constructing a ReLU-MLP as a general-purpose computer has been proposed before. Therefore, we explore the conditions under which a ReLU-MLP can function as a universal programmable computer and prove that a $23$-layer looped ReLU-MLP is capable of emulating a general-purpose computer.

Our research centers on $\mathsf{MLP}$s equipped with the $\mathsf{ReLU}$ activation function, which is fundamental to their design. We commence by formally defining the $\mathsf{ReLU}$ activation function as follows:

Then, we introduce the definition of $\mathsf{MLP}$ with $\mathsf{ReLU}$ activation as follows:

The $m$-layer ReLU-MLP is then the compositions of $m$ such Perceptrons in Eq. (1), e.g., $\mathsf{ReLU}(W_{2}\cdot\mathsf{ReLU}(W_{1}x+b_{1})+b_{2})$ for $2$-layer ReLU-MLP.

In contrast to previous research , which utilized Transformers as the fundamental building block to create a universal computer, our approach harnesses the simple ReLU-MLP to accomplish the same objective. These findings suggest that basic ReLU-MLP modules are sufficiently expressive, and their potential is underexplored. With careful design, they might exhibit emergent abilities like in-context learning, indicating that complex architectures like Transformers may not always be necessary for certain computational tasks. Understanding the fundamental capabilities of neural networks before adopting complex models could lead to more efficient, less resource-intensive solutions. By challenging the belief that only advanced models can handle complex tasks, this opens avenues for research prioritizing simplicity and efficiency without sacrificing performance. In a world of finite computational resources, this discovery could lead to more sustainable and accessible AI solutions.

To sum up, we conclude our contributions as follows:

To the best of our knowledge, we are the first work to prove that a looped $23$-layer ReLU-MLP satisfies the conditions required to function as programmable computers (Theorem 4.1).

Our findings highlight the importance of understanding the capabilities of the fundamental ReLU-MLP component, demonstrating its powerful expressivity.

Our findings show that traditional neural networks, such as ReLU-MLP, have not been fully explored, challenging the belief that only advanced architectures can perform complex tasks.

The paper is organized as follows: In Section 2, we discuss related literature. In Section 3, we provide our notation system and key concepts and definitions. In Section 4, we introduce our main result that a looped $23$-layer ReLU-MLP can emulate a programmable computer. In Section 5, we demonstrate how implement basic operations such as read, write, conditional branching, and SUBLEQ using ReLU-MLP. In Section 6, we discuss the high-level intuition and potential future directions of our finding. In Section 7, we conclude our paper.

RELATED WORK

Circuit complexity, a branch of computational complexity theory, studies circuit families as models of computationWe refer the reader to the chapter $6$ and $14$ of AB or chapter $1$ and $2$ of Handbook of Theoretical Computer Science for more detailed background of circuit complexity.. Several circuit complexity classes are significant in machine learning. Specifically, $\mathsf{AC}^{0}$ represents problems highly parallelizable with standard logic gates, while $\mathsf{TC}^{0}$ extends this to include threshold gates, and $\mathsf{NC}^{1}$ denotes the language recognizable by $O(\log n)$-depth circuits with bounded gate arity . It is known that $\mathsf{AC}^{0}\subset\mathsf{TC}^{0}\subseteq\mathsf{NC}^{1}$, but whether $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$ remains an open question. Assuming this inequality, LAG+ show that Transformer depth must depend on input sequence length when simulating non-solvable semiautomata. LLZM explore relationships among constant-depth Transformers, Transformers with Chain-of-Thought (CoT), and circuit complexity. They demonstrate: $\mathsf{T}[\operatorname{poly}(n),1,1]\subseteq\mathsf{CoT}[\log n,\operatorname{poly}(n),1,1]\subseteq\mathsf{AC}^{0}$ and $\mathsf{T}[\operatorname{poly}(n),\log n,0]\subseteq\mathsf{CoT}[\log n,\operatorname{poly}(n),\log n,0]\subseteq\mathsf{TC}^{0}$ where $\mathsf{T}[d(n),s(n),e(n)]$ denotes a constant-depth Transformers with embedding size $d(n)$, precision $s(n)$ bits, and exponent bits $e(n)$ for input length $n$ and $\mathsf{CoT}[T(n),d(n),s(n),e(n)]$ denotes a $T(n)$-step CoT of a constant-depth Transformer $\mathsf{T}[d(n),s(n),e(n)]$. Their results provide theoretical insights into the emergent CoT ability of Transformers, showing that intermediate reasoning steps enable tackling more complex problems. The Strong Exponential Time Hypothesis (SETH), introduced by IP , strengthens the $\mathsf{P}\neq\mathsf{NP}$ conjecture by asserting that current best $\mathsf{SAT}$ algorithms are roughly optimal: for every $\epsilon>0$, there exists $k\geq 3$ such that $k$-$\mathsf{SAT}$ cannot be solved in $O(2^{(1-\epsilon)n})$ time, even randomly. SETH is widely used to prove fine-grained lower bounds for various algorithmic problems and has been applied to derive lower bounds for Transformer training/inference and tensor attention . Specifically, AS demonstrates that unless the $\mathsf{SETH}$ fails, no algorithm exists that can compute the forward pass of an attention network in truly-subquadratic time. On the other hand, AS24a establishes that the same condition applies to the backward computation of attention networks, i.e., unless the $\mathsf{SETH}$ fails, no truly-subquadratic time algorithm can be devised for the backward computation of attention networks. In essence, complexity theory provides a powerful framework for investigating the computational capabilities of neural networks, by rigorously analyzing the computational problems they can efficiently solve.

Turning Completeness of Neural Networks.

In recent years, neural networks ($\mathsf{NN}$s) have demonstrated great potential in performing tasks that were previously considered impossible for traditional numerical approximation methods. This remarkable capability is largely attributed to their properties as universal approximators and, in some cases, their Turing completeness . Specifically, PMB , PBM show that Transformers with attention mechanism under infinite precision are Turing complete, whereas DGV+ demonstrates that this is not the case under fixed precision. Another line of work focuses on recurrent neural networks ($\mathsf{RNN}$s) and proves their Turing completeness. Moreover, WCM demonstrates that ReLU-MLP can meaningfully approximate Boolean circuits and Transformers can meaningfully approximate Turing machines. It is important to note that Turing completeness deals with discrete computations, such as processing language, whereas universal approximation focuses on continuous functions. SWL show that ReLU-MLP is expressive and over fixed feature methods like kernels. Therefore, one property does not imply the other , and it is necessary to study these two subjects separately.

Limitations of Transformers.

Transformers have demonstrated remarkable capability in natural language processing tasks, yet their proficiency in mathematical computations remains a concern . Therefore, researches have been directed toward delineating the computational limits of Transformers when faced with mathematical tasks. MS has shown that if $\mathsf{L}\neq\mathsf{P}$ The class $\mathsf{L}$ represents the set of problems that can be resolved using logarithmic space, whereas $\mathsf{P}$ denotes the class of problems that can be solved within polynomial time constraints. (i.e. not all polynomial-time problems are solvable in logarithmic space), Transformers are incapable of accurately resolving linear inequalities or determining membership in an arbitrary context-free grammar that includes empty productions, and FZG+ illustrates that unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$, there is no log-precision Transformers is capable to solve arithmetic and equation-solving problems.

Neural Networks Can Perform Algorithms.

Given their Turing completeness, it is not surprising that neural networks ($\mathsf{NN}$s) can perform algorithms once properly trained. One example is their ability for in-context learning (ICL) , where Transformers produce the correct output based on the context provided by examples without adapting their parameters. Studies have shown that ICL can implement optimization algorithms like gradient descent across layers , and interestingly, Transformers can in-context fine-tune smaller Transformers . Moreover, LLZM shows that when equipped with enough steps of Chain-of-Thought (CoT) reasoning , constant-depth Transformers using constant-bit precision and embedding size can solve any problem solvable by Boolean circuits. Other studies observe that Transformers perform dynamic programming to generate text. Transformers have also been shown to efficiently learn arithmetic operations such as addition, multiplication, and elementary functions like square roots, and can even simulate a programmable computer . Additionally, HS proves that ReLU-MLP can solve exact max-flow problems.

Neural Networks as Practical Programmable Computer.

Programmable computer is known as a powerful and controllable compute architecture. Numerous studies strive to establish the equivalence of their proposed neural network architectures with the programmable computer, thereby illustrating the efficacy of their designs. GRS+ employs Transformers as the building block to build a programmable computer, showcasing the latent capabilities of Transformer-based neural networks. Additionally, other research initiatives adopt distinct methodologies to realize programmable computer architectures. For example, ÇDT introduces a construction utilizing optical neural networks. Studies such as LVdB , Lia are dedicated to investigating the feasibility of attaining universal computation through probabilistic circuits. Moreover, propose a computational model for the Transformer-encoder using a domain-specific language called the Restricted Access Sequence Processing Language (RASP). Building on this, introduce Tracr, a compiler that leverages RASP to use Transformer networks as programmable units.

PRELIMINARY

This section provides essential definitions used in this paper. In Section 3.1, we introduce some basic notations. In Section 3.2, we present several key concepts related to the state vector of the programmable computer constructed by ReLU-MLP.

2 Key Concepts

We begin with introducing the way we organize the data. Different from conventional $\{0,1\}$ representation of the data, we use $\{\pm 1\}$ to represent the data. This design will benefit the calculate of the address vectors, which will be discussed in Remark 3.5.

We define one bit data as $v\in\{-1,1\}$.

One bit is not capable of representing the integers or floats or other data types used in modern computers. Thus, we introduce the $d$-bits data vector as follows:

We define data as $v\in\{-1,1\}^{d}$ using two’s complement. Here, data dimension $d$ means the number of bits, and the data type can be int32 or float64 in a computer.

In this work, we consider all data as integers. Specifically, we use $2$’s complement to represent the integer. It is worth mention that the data type can be easily extend. Due to the limitation of the space, we temporary consider only the integer data.

For a $d$-bit data value $v\in\{-1,1\}^{d}$, which represents an integer with bits $b_{d},b_{d-1},\ldots,b_{2},b_{1}$, where $b_{i}\in\{\pm 1\}$ for $i\in[d]$, we denote $b_{d}$ as the most significant bit (MSB).

The integer value of $v$ is defined as follows:

If $b_{d}=-1$, the integer is considered positive, with a value given by: $\sum_{i=1}^{d-1}2^{i-1}\frac{b_{i}+1}{2}$.

If $b_{d}=+1$, the integer is considered negative, with a value given by: $-2^{d-1}+\sum_{i=1}^{d-1}2^{i-1}\frac{b_{i}+1}{2}$.

Suppose there are total $n$ bits in the programmable computer. Hence, we choose the length of the address vector as $\log(n)$, which is the most efficient way for locating the total $n$ address. We present the definition of address vector as follows:

We define the address of a data as $a\in\{-1,+1\}^{\log(n)}$ with state size $n$.

Since we choose $\{\pm 1\}$ instead of $\{0,1\}$ as our data representation, only the inner product of the address vectors with the same address will be $\log(n)$. Any inner product of address vectors with different address will be strictly less than $\log(n)$. This property facilitate our addressing operation.

In Definition 3.4, we use vectors with value $\pm 1$ to represent the address, which is different from classical $\{0,1\}$ representation. Under this setting, we have $\forall i\in[n],a_{i}^{\top}a_{i}=\log(n)$, and $\forall i,j\in[n],i\neq j$, we have $a_{i}^{\top}a_{j}<\log(n)$ because of Cauchy–Schwarz inequality.

In this work, we mainly focus on constructing ReLU-MLP for executing “SUBLEQ”. This focus stems from the fact that a One Instruction Set Computer (OISC) constructed with the “SUBLEQ” instruction is functionally equivalent to a programmable computer in terms of its computational capabilities . Since we only consider the “SUBLEQ” instruction, we do not need any bits to encode the type of the instruction. We only need to encode three address vectors used by the “SUBLEQ” instruction. By simply concatenate the three address vectors, we have the length of the instruction is $3\log(n)$.

Let “SUBLEQ” instruction be defined as in Algorithm 1. Let the address vector be defined as Definition 3.4. Then we define the instruction vector $c_{i}\in\{\pm 1\}^{3\log(n)}$ by simple concatenating three address vectors $a,b,c\in\{\pm 1\}^{\log(n)}$ required by the “SUBLEQ” instruction. Namely, we have $c_{i}$ satisfies the following equation: $c_{i}=[a,b,c].$

Based on all the crucial concepts introduced above, we move to introducing the state vector for our programmable computer. Namely, this state vector contains all registers, data/memory, and instructions of the computer.

We define our one-bit state of ReLU-MLP as follows:

MAIN RESULT

In this section, we introduce our thrilling finding, which demonstrates a looped $23$-layer ReLU-MLP is capable to emulate a programmable computer.

Let ReLU-MLP be defined as Definition 1.2. Let $n$ be the size of state vector. Let $m$ be the number of instructions. Let $k$ be the number of one-bit data stored in the memory. For $i\in[k]$, each data is $v_{i}\in\{\pm 1\}$ and the memory size $k$ satisfies $k=n-2-4\log(n)-3m\log(n)$. Let the address vector $a_{i}\in\{\pm 1\}^{\log(n)}$. Suppose we have two data registers $r_{d_{1}},r_{d_{2}}\in\{\pm 1\}$, one carry bit $r_{c}\in\{\pm 1\}$, three address registers $r_{a_{1}},r_{a_{2}},r_{a_{3}}\in\{\pm 1\}^{\log(n)}$, and one program counter $r_{pc}\in\{\pm 1\}^{\log(n)}$ in the scratchpad.

Then, a $23$-layer ReLU-MLP with width $n$ can emulate a programmable computer, where $d$ is the number of bits we use to store each integer. Namely, this “computer” supports integers within the range $[-2^{d-1},2^{d-1}-1]$.

The high-level idea of the proof is that we first prove the $23$-layer ReLU-MLP is capable to emulate the one-bit version “SUBLEQ” instruction. Then, we extend it to supporting $d$-bits version “SUBLEQ”. Finally, according to the finding in MP , the One Instruction Set Computer (OISC) constructed by the looped ReLU-MLP is Turing complete, which further indicates it is equivalent to a programmable computer. Due to the limitation of space, we refer the readers to Appendix E for more in-depth analysis.

KEY FUNCTIONS IMPLEMENTATIONS

In this section, we outline a selection of critical functions that the ReLU-MLP model is capable of executing. Due to the limitation of the space, the detailed proofs are deferred to the Appendix. Specifically, in Section 5.1, we implement the read operation. Section 5.2 covers the write operation. Section 5.3 presents addition, while Section 5.4 addresses subtraction. Conditional branching is implemented in Section 5.5, and the SUBLEQ operation is in Section 5.6.

We first consider the most basic “read” operation, which is to read any data or instruction from memory into a register. We begin with introducing the read operation for one-bit data as follows:

Let ReLU-MLP be defined as Definition 1.2. Let $n$ denote the number of data in the memory. For $i\in[n]$, each data $v_{i}\in\{\pm 1\}$. Let the address vector $a_{i}\in\{\pm 1\}^{\log(n)}$.

Then, a $2$-layer ReLU-MLP can read any one-bit data from the memory to the register.

Then, to achieve the read operation for $d$-bits data, we only need to use the ReLU-MLP introduced in the previous Lemma to perform a read operation on each bit in the $d$-bits data.

Let ReLU-MLP be defined as Definition 1.2. Let $n$ denote the number of data in the memory. For $i\in[n]$, each data $v_{i}\in\{\pm 1\}$. Let $v\in\{\pm 1\}^{d}$ denote a $d$ dimension vector. Let the address matrix $a_{i}\in\{\pm 1\}^{\log(n)\times d}$.

Then, a $2$-layer ReLU-MLP looped for $d$ times can read any $d$-bits data vector from the memory to the register.

2 Write

Corresponding to the read operation, in this section we introduce how to use ReLU-MLP to implement the “write” operation. We start with the write operation of one bit data.

Let ReLU-MLP be defined as Definition 1.2. Let $n$ denote the number of data in the memory. For $i\in[n]$, each data $v_{i}\in\{\pm 1\}$. Let the address vector $a_{i}\in\{\pm 1\}^{\log(n)}$.

Then, a $2$-layer ReLU-MLP can write any one-bit data from the register to the memory.

Subsequently, we can expand our approach to accommodate the “write” operation for $d$-bit data, by sequentially processing each bit within the $d$-bit data.

Let ReLU-MLP be defined as Definition 1.2. Let $n$ denote the number of data in the memory. For $i\in[n]$, each data $v_{i}\in\{\pm 1\}$. Let $v\in\{\pm 1\}^{d}$ denote a $d$ dimension vector. Let the address matrix $a_{i}\in\{\pm 1\}^{\log(n)\times d}$.

Then, a $2$-layer ReLU-MLP looped for $d$ times can write any $d$-bits data vector from the register to the memory.

3 Addition

Beyond the fundamental memory operations of reading and writing, a pivotal set of operations involves algorithmic functions. Consequently, we demonstrate how the addition and subtraction operations can be emulated by the ReLU-MLP. We begin with introducing the emulation of one-bit addition operation via ReLU-MLP.

Let ReLU-MLP be defined as Definition 1.2. Then, a $6$-layer ReLU-MLP can emulate the “addition” operation for any one-bit data.

We extend to $d$-bits addition as follows:

Let ReLU-MLP be defined as Definition 1.2. Then, a $6$-layer ReLU-MLP looped for $2d$ times (due to carry bit) can emulate the “addition” operation for any $d$-dimension vectors.

4 Subtraction

Then, we move on to introducing the subtraction operation. Since we use $2$’s complement (Definition 3.3) as the representation of the data, the subtraction operation can be decomposed into two steps. The first step is to negate the subtrahend, and the second step is to add the negated subtrahend to the minuend. Combing the above statement with the addition operation introduced in the previous section, we can easily perform subtraction operation with a $7$-layer ReLU-MLP.

Let ReLU-MLP be defined as Definition 1.2. Then, a $7$-layer ReLU-MLP can emulate the “subtraction” operation for any $d$-dimension vectors.

5 Conditional Branching

Conditional branching is an essential operation in computer design, since it enables the processor to make decisions and execute different paths of code based on the evaluation of conditions (the flag), thereby allowing for more complex and adaptable program flow. We present our design for conditional branching via ReLU-MLP as follows:

Let ReLU-MLP be defined as Definition 1.2. Let $n$ denote the number of data in the memory. For $i\in[n]$, each data $v_{i}\in\{\pm 1\}$. Let the address vector $a_{i}\in\{\pm 1\}^{\log(n)}$.

Then, a $4$-layer ReLU-MLP can emulate the “conditional branching” operation.

6 SUBLEQ Instruction

Now, we present our method for implementing the “SUBLEQ” instruction using a looped $23$-layer ReLU-MLP. The “SUBLEQ” instruction operates with three addresses as parameters, denoted as $a$, $b$, and $c$. It first computes the subtraction between the values stored at addresses $b$ and $a$, i.e. $\texttt{mem}[b]-\texttt{mem}[a]$, and then updates the memory at $\texttt{mem}[b]$ with this result. If the value at $\texttt{mem}[b]$ is zero or negative, the program counter will be transferred to the address specified by $c$; otherwise, the program counter will go to the next instruction without branching. Algorithm 1 demonstrates the execution process of “SUBLEQ” instruction.

We integrate the read and write operations, along with the addition and subtraction operations, and the conditional branching mechanisms discussed in the preceding sections to facilitate the implementation of the “SUBLEQ” instruction. The accompanying lemma is stated as follows:

Let ReLU-MLP be defined as Definition 1.2. Let $n$ denote the size of state vector. Let $m$ denote the number of instructions. Let $k$ denote the number of one-bit data stored in the memory. For $i\in[k]$, each data is $v_{i}\in\{\pm 1\}$ and the memory size $k$ satisfies $k=n-2-4\log(n)-3m\log(n)$. Let the address vector $a_{i}\in\{\pm 1\}^{\log(n)}$. Let the instruction $c_{i}\in\{\pm 1\}^{3\log(n)}$ be defined as Definition 3.6. Suppose we have three data registers $r_{c},r_{d_{1}},r_{d_{2}}\in\{\pm 1\}$, one carry bit $r_{c}\in\{\pm 1\}$, three address registers $r_{a_{1}},r_{a_{2}},r_{a_{3}}\in\{\pm 1\}^{\log(n)}$, and one program counter $r_{pc}\in\{\pm 1\}^{\log(n)}$ in the scratchpad.

Then, a $23$-layer ReLU-MLP with width $n$ can emulate the “SUBLEQ” operation (Algorithm 1).

To make it easier for readers to understand our proof, we provide a proof sketch here, which contains some high-level ideas used in our proof. Specifically, we first read the necessary address vectors and data required by the instruction from the memory. Then, we perform subtraction and conditional branching via the respective ReLU-MLPs discussed in the previous sections.

We use the state vector $x$ as defined in Definition 3.7. The first step is to read the “SUBLEQ” instruction and the data required by the instruction from the memory, where the read operation is supported by the ReLU-MLP discussed in Lemma 5.2. After this step, the state vector will change as follows:

where we first read the address vectors $a$ and $b$ from the memory to the address registers, then read the corresponding data $\texttt{mem}[a]$ and $\texttt{mem}[b]$ from the memory to the data registers.

In the second step, we calculate the subtraction of $\texttt{mem}[b]$ and $\texttt{mem}[a]$, store its result to $\texttt{mem}[b]$, and calculate the $r_{pc+1}$ according to $r_{pc}$, storing $r_{pc+1}$ at the address register which previously stores $b$. The above operations can be supported by Lemma 5.6 and Lemma 5.4. After this step, the state vector will change as follows:

Up to this point, we have obtained the execution result for the current “SUBLEQ” instruction. To process the subsequent instruction, we simply need to iterate through the provided $23$-layer ReLU-MLP once more, thereby executing the “SUBLEQ” instruction for the next cycle. ∎

We only provide a sketch of proof above. We refer the readers to Appendix D for more details.

DISCUSSION AND EXTENSION

In Section 6.1, we compare ReLU-MLP with attention mechaism. In Section 6.2, we discuss the potential capability of ReLU-MLP. In Section 6.3, we discuss the potential inspirations our work offers for designing more efficient neural network architectures.

As discussed in Section 4, we have demonstrated that a looped $23$-layer ReLU-MLP is capable of emulating a programmable computer. In contrast to the findings reported by , where a looped $13$-layer Transformer is shown to be capable of such emulation, our result indicates that even a basic component of deep learning, the ReLU-MLP, possesses the potential to handle complex computational tasks. This suggests that while advanced architectures like Transformers have shown proficiency in processing intricate tasks, this proficiency may not come from its advanced architecture design. Instead, it may derive from the inherent capabilities of fundamental components such as the ReLU-MLP. Our finding underscores the importance of investigating the core mechanisms behind the capabilities of advanced architectures, an area that warrant further exploration.

2 Exploring the Potential of ReLU-MLP

Our research has confirmed that the capabilities of the ReLU-MLP are on par with Transformers when it comes to constructing programmable computers. As noted in , ReLU-MLPs have been demonstrated to be universal approximators. Consequently, we conjecture the programmable computer represents just one of the many downstream tasks that ReLU-MLPs are capable of achieving. Building on the insights from this study, it is promising to further investigate the potential capabilities of ReLU-MLPs. Our approach to analyze the looped ReLU-MLP mitigates the black-box nature often associated with traditional deep learning training. We are confident that through the analytical methods outlined in our work, we can systematically probe the capacity of ReLU-MLPs as universal approximators to tackle more complex tasks. This line of works will be done in our future research.

3 Towards More Efficient Architecture Design for Specific Tasks

The construction-based proof in our work can inspire future explorations of the smallest feasible network structure for specific tasks. Since the main focus of our work is to prove the feasibility of ReLU-MLP-based computer construction, the ReLU-MLP-based construction we provide may not be the smallest construction that can support a programmable computer. Therefore, in fact, we provide a possible lower bound that can achieve a programmable computer. The current mainstream methods for model compression are mainly quantization and model pruning, which often provide model compression solutions based on experimental results, and lack theoretical measurements between model capabilities and model capabilities required by the downstream tasks. Thus, leveraging the methodologies applied in this study, we can first identify the minimal requirements to a model for a particular task, enabling researchers to create the smallest, yet efficient models to handle it. This strategy permits us to bypass the costly process of expensive process of scaling up data or model parameters. We leave these directions as our future directions.

CONCLUSION

In this work, we investigate the computational potential of a looped ReLU-MLP. We begin by demonstrating that a looped $23$-layer ReLU-MLP with a single pass is capable of emulating the execution process of the “SUBLEQ” instruction. Drawing on the conclusions presented in , we establish that the One Instruction Set Computer (OISC) implemented by the looped $23$-layer ReLU-MLP is functionally equivalent to a programmable computer. Contrary to previous research , which achieved the emulation of a programmable computer using a looped $13$-layer Transformer, our approach leverages a more fundamental building block of deep learning, a $23$-layer ReLU-MLP, to accomplish the same objective. This finding prompts us to consider two key insights: ($i$) The untapped potential of ReLU-MLPs warrants further exploration, offering a deeper understanding of the capability boundaries of existing neural networks; ($ii$) By adopting the methodologies employed in this study, it may facilitate us to gain insights for designing the minimal neural network requirements for any specific tasks.

Acknowledgement

Research is partially supported by the National Science Foundation (NSF) Grants 2023239-DMS, CCF-2046710, and Air Force Grant FA9550-18-1-0166.

References

Roadmap.

We organize our appendix as follows: In Section A, we introduce our construction of ReLU-MLP for emulating the read and write operation. In Section B, we present the way we achieving the addition and subtraction operation via ReLU-MLP . In Section C, we show that a $4$-layer ReLU-MLP is capable for emulating the conditional branching operation. In Section D, we illustrate the “SUBLEQ” can be emulated by a looped $23$-layer ReLU-MLP. In Section E, we demonstrate how the looped $23$-layer ReLU-MLP introduced in the previous section is capable to function as a programmable computer.

Appendix A READ AND WRITE

In this section, we mainly focus on construction a multi-layer ReLU-MLP for supporting read and write operation. We begin with the scenario where we read a one-bit data from the memory to the data register.

Let ReLU-MLP be defined as Definition 1.2.

Let $n$ denote the number of data in the memory. For $i\in[n]$, each data $v_{i}\in\{\pm 1\}$.

Let the address vector $a_{i}\in\{\pm 1\}^{\log(n)}$.

Then, we can show that, a $2$-layer ReLU-MLP can read any one-bit data from the memory to the register.

Consider a simplified case, where we have one data register $r_{d}\in\{\pm 1\}$ which stores data $v_{0}\in\{\pm 1\}$ initially, and one address register $r_{a}\in\{\pm 1\}^{\log(n)}$ which stores address $a_{i}\in\{\pm 1\}^{\log(n)}$ initially. The address $a_{i}$ points to the location where the data should be copied from. Namely, we want to perform the following operation:

Then we perform the following operations to get the location vector:

where the first step follows from we have $\forall i,a_{i}^{\top}a_{i}=\log(n)$ and $\forall i\neq j$, $a_{i}^{\top}a_{j}<\log(n)$ (Remark 3.5). Here, the $e_{i}$ denote the vector whose $i$-th entry is $1$ and other entries are .

Then, we extract $v_{i}$ by the following operation:

Then, we construct $x_{v_{i}}$ by concatenating $v_{i}$ with some zero vectors:

Finally, we add $x_{v_{i}}$ and $x_{1}$ together to get our final result.

Step 3 uses vector addition, so doesn’t use ReLU-MLP.

Therefore, we use a two-layer ReLU-MLP to emulate the “read” operation. ∎

Then, we move on to considering the read operation for $d$-bits data.

Let ReLU-MLP be defined as Definition 1.2.

Let $n$ denote the number of data in the memory. For $i\in[n]$, each data $v_{i}\in\{\pm 1\}$.

Let $v\in\{\pm 1\}^{d}$ denote a $d$ dimension vector.

Let the address matrix $a_{i}\in\{\pm 1\}^{\log(n)\times d}$.

Then, we can show that, a $2$-layer ReLU-MLP, looped for $d$ times, can read any $d$-bits data vector from the memory to the register.

By Lemma A.1, we can read one bit from memory to register via a two-layer ReLU-MLP.

We apply the two-layer ReLU-MLP to each column of $X$. Since $X$ has $d$ columns, we loop the two layers ReLU-MLP for $d$ times. Then, we can perform the “read” operation for any $d$-dimension vector from the memory to the register. ∎

Writing can be considered as the inverse process of reading. Summarily, we first consider write a one-bit data from the data register to the memory.

Let ReLU-MLP be defined as Definition 1.2.

Let $n$ denote the number of data in the memory. For $i\in[n]$, each data $v_{i}\in\{\pm 1\}$.

Let the address vector $a_{i}\in\{\pm 1\}^{\log(n)}$.

Then, we can show that, a $2$-layer ReLU-MLP can write any one-bit data from the register to the memory.

Consider a simplified case, where we have one data register $r_{d}\in\{\pm 1\}$ which stores data $v_{0}\in\{\pm 1\}$ initially, and one address register $r_{a}\in\{\pm 1\}^{\log(n)}$ which stores address $a_{i}\in\in\{\pm 1\}^{\log(n)}$ initially. The address $a_{i}$ points to the location where the data should be copied from. Namely, we want to perform the following operation:

For simplicity, we ignore the notations $r_{d}:$ and $r_{a}:$ in the following proof.

Then we perform the following operations:

where the first step follows from we have $\forall i,a_{i}^{\top}a_{i}=\log(n)$ and $\forall i\neq j$, $a_{i}^{\top}a_{j}<\log(n)$ (Remark 3.5). Here, the $e_{i}$ denote the vector whose $i$-th entry is $1$ and other entries are .

Then, we erase the $v_{i}$ in $x$ by first performing the following operation:

We use the $e_{i}$ acquired from Step 1 to perform the following operation:

Then, by concatenation, we have our final result:

Step 3 use concatenation, so doesn’t use ReLU-MLP.

Therefore, we use a two-layer ReLU-MLP to emulate the “write” operation. ∎

Then, we show how we extend writing one-bit data to writing $d$-bits data as follows:

Let ReLU-MLP be defined as Definition 1.2.

Let $n$ denote the number of data in the memory. For $i\in[n]$, each data $v_{i}\in\{\pm 1\}$.

Let $v\in\{\pm 1\}^{d}$ denote a $d$ dimension vector.

Let the address matrix $a_{i}\in\{\pm 1\}^{\log(n)\times d}$.

Then, we can show that, a $2$-layer ReLU-MLP, looped for $d$ times, can write any $d$-bits data vector from the register to the memory.

By Lemma A.3, we can write one bit from the register to the memory via a two-layer ReLU-MLP.

We apply the two layers ReLU-MLP to each column of $X$. Since $X$ has $d$ columns, we loop the two-layer ReLU-MLP for $d$ times. Then, we can perform the “write” operation for any $d$-dimension vector from the register to the memory. ∎

Appendix B ADDITION AND SUBTRACTION

In this section, we focus on implementing ReLU-MLP to support basic algorithmic operations, i.e. addition and subtraction.

We begin with introducing the construction for one-bit addition. It is worth mentioning that we also consider the carry bit in the addition.

Let ReLU-MLP be defined as Definition 1.2.

Then, we can show that, an $6$-layer ReLU-MLP can emulate the “addition” operation for any one-bit data.

Consider a simplified case, we have the following components in the scratchpad: two data register $r_{d_{1}},r_{d_{2}}\in\{\pm 1\}$, and one data register $r_{c}$ which stores the carry of the addition operation. We want to perform addition operation, and store the result in the first register. Namely, we want the following operation:

Here, we want the addition result $r_{d_{1}}+r_{d_{2}}\in\{\pm 1\}$ and $r_{c}=1$ if and only if $r_{d_{1}}=r_{d_{2}}=1$.

Step 1: $\{\pm 1\}$ representation to $\{0,1\}$ representation and reset $r_{c}$.

We apply one layer ReLU-MLP with the weight matrix $W_{1}$ be defined as follows:

Our goal is to reset the carry register $r_{c}$ and change the representation of $r_{d_{1}},r_{d_{2}}$ from $\{\pm 1\}$ to $\{0,1\}$. Namely, we perform the following operation:

Since $r_{d_{1}},r_{d_{2}}\in\{\pm 1\}$, $\mathsf{ReLU}(r_{d_{1}}),\mathsf{ReLU}(r_{d_{2}})\in\{0,1\}$.

Step 2: Construct two flag vectors for $\mathsf{ReLU}(r_{d_{1}})$.

Let $x_{11}:=\mathsf{ReLU}(r_{d_{1}}),x_{12}:=\mathsf{ReLU}(r_{d_{2}})$.

We construct the weight matrix $W_{2}$ of one ReLU-MLP as follows:

We construct the weight matrix $W_{3}$ and bias vector $b_{3}$ of one ReLU-MLP as follows:

Step 3: Construct two flag vectors for $\mathsf{ReLU}(r_{d_{2}})$.

We construct the weight matrix $W_{4}$ of one ReLU-MLP as follows:

We construct the weight matrix $W_{5}$ and bias vector $b_{5}$ of one ReLU-MLP as follows:

Recall in the previous two steps, we defined $x_{11}:=\mathsf{ReLU}(r_{d_{1}}),x_{12}:=\mathsf{ReLU}(r_{d_{2}})$, and we have the following four vectors:

Then, we construct $x_{6}$ with the following operation:

Our construction is reasonable because only when both $r_{d_{1}}$ and $r_{d_{2}}$ are $1$, the carry register $r_{c}$ will be set to $1$, otherwise it should be set to $-1$.

Step 5: Erase $r_{d_{1}}$ and add the addition vector $x_{6}$.

We construct the weight matrix $W_{6}$ as follows:

Then, we perform the following operation:

Therefore, we emulate the “addition” operation with a six-layer ReLU-MLP. ∎

Since we already have a ReLU-MLP for one-bit addition, then we extend it to support $d$-bits addition as follows:

Let ReLU-MLP be defined as Definition 1.2.

Then, we can show that, a $6$-layer ReLU-MLP, looped for $2d$ times, can emulate the “addition” operation for any $d$-dimension vectors.

By Lemma B.1, we have a six-layer ReLU-MLP can perform one-bit addition operation, and stores the carry result in the carry register.

For each dimension in $d$, we first perform the addition operation between the carry register from the previous dimension with one data register. Then, we perform the addition operation.

For each dimension, we need $2$ loops. Therefore, we can emulate the $d$-dimension vector addition via $2d$ loops of that six-layer ReLU-MLP. ∎

In this work, we use $2$’s-complement as the representation of data. Therefore, the subtraction can be viewed as first negating the subtrahend, then adding $1$, and adding to the minuend. We follow the aforementioned high-level idea to implement the subtraction as follows:

Let ReLU-MLP be defined as Definition 1.2.

Then, we can show that, a $7$-layer ReLU-MLP can emulate the “subtraction” operation for any $d$-dimension vectors.

By Lemma B.2, we have we can perform addition operation for $d$-dimension vectors via a six-layer ReLU-MLP with $2d$ loops.

In our setting, we use $2$’s complement (Definition 3.3) to represent our data. Therefore, to perform subtraction $x_{1}-x_{2}$, we can first calculate $-x_{2}$, then add $x_{1}$ and $-x_{2}$ to get the final result.

According to $2$’s complement, to calculate $-x_{2}$, we first need to invert all entries of $x_{2}$ ($1\rightarrow-1;-1\rightarrow 1$). This step requires a one-layer ReLU-MLP with weight matrix $W=-I_{d\times d}$.

The second step is to add $1$ to the inverted $x_{2}$, which can be achieved by the six-layer ReLU-MLP used for the addition operation.

This step keep uses the same six-layer ReLU-MLP with Step 1. Since that six-layer ReLU-MLP can perform addition operation, we can use that six-layer ReLU-MLP to perform $x_{1}+(-x_{2})$, which is our desired result.

To sum up, we need an additional layer to invert $x_{2}$ as discussed in Step 1, and the six-layer ReLU-MLP used for addition operation. Therefore, the subtraction operation requires a seven-layer ReLU-MLP. ∎

Appendix C CONDITIONAL BRANCHING

In this section, we implement the “conditional branching” instruction through ReLU-MLP. Conditional branching is a critical instruction in computer programs, since it enables the computer programs to achieve controllability.

Let ReLU-MLP be defined as Definition 1.2.

Let $n$ denote the number of data in the memory. For $i\in[n]$, each data $v_{i}\in\{\pm 1\}$.

Let the address vector $a_{i}\in\{\pm 1\}^{\log(n)}$.

Then, we can show that, a $4$-layer ReLU-MLP can emulate the “conditional branching” operation.

Step 1 uses one ReLU-MLP with width $3\log(n)+1$.

Step 2 uses one ReLU-MLP with width $3\log(n)+1$.

Step 3 uses one ReLU-MLP with width $3\log(n)+1$.

Step 4 uses one ReLU-MLP with width $3\log(n)+1$.

Therefore, we use ReLU-MLP with four layers and width $O(\log n)$ to emulate the “conditional branching” operation. ∎

Appendix D SUBLEQ

Based on the fundamental operations introduced in the previous sections, we are ready to construct the “SUBLEQ” instruction.

Let ReLU-MLP be defined as Definition 1.2.

Let $m$ denote the number of instructions.

Let $k$ denote the number of one-bit data stored in the memory. For $i\in[k]$, each data is $v_{i}\in\{\pm 1\}$ and the memory size $k$ satisfies $k=n-2-4\log(n)-3m\log(n)$.

Let the address vector $a_{i}\in\{\pm 1\}^{\log(n)}$.

Let the instruction $c_{i}\in\{\pm 1\}^{3\log(n)}$ be defined as Definition 3.6.

Suppose we have three data registers $r_{c},r_{d_{1}},r_{d_{2}}\in\{\pm 1\}$, one carry bit $r_{c}\in\{\pm 1\}$, three address registers $r_{a_{1}},r_{a_{2}},r_{a_{3}}\in\{\pm 1\}^{\log(n)}$, and one program counter $r_{pc}\in\{\pm 1\}^{\log(n)}$ in the scratchpad.

Then, we can show that, a $23$-layer ReLU-MLP with width $n$ can emulate the “SUBLEQ” operation (Algorithm 1).

Consider we organize our state vector as follows:

In this step, we read the instruction from the memory according to the address provided in $r_{pc}$. As shown in Algorithm 1, the instruction contains three address. Here we denote them as $a,b,c\in\{\pm 1\}^{\log(n)}$.

By Lemma A.2, we read the three address vectors from the memory to the three registers in the scratchpad, using two-layer ReLU-MLP. Then, the state $x$ transforms as follows:

Overall, this step requires a two-layer ReLU-MLP.

Step 2: Read the data required by the instruction.

In this step, we read the two data required by the instruction. Namely $\texttt{mem}[a]$ and $\texttt{mem}[b]$. By Lemma A.2, we achieve this operation by a two-layer ReLU-MLP. Then, the state $x$ transforms as follows:

Overall, this step requires a two-layer ReLU-MLP.

In this step, we perform the subtraction operation, $\texttt{mem}[b]-\texttt{mem}[a]$. By Lemma B.3, we achieve this operation by a seven-layer ReLU-MLP. Then, the state $x$ transforms as follows:

This step requires a seven-layer ReLU-MLP.

Step 4: Write back $\texttt{mem}[b]-\texttt{mem}[a]$.

In this step, we write back the $\texttt{mem}[b]-\texttt{mem}[a]$ to the memory according to the address vector $b$. By Lemma A.4, we achieve this operation via a two-layer ReLU-MLP.

In this step, we calculate $r_{pc+1}$ and store it at the place which stores $b$ previously. (Since the address vectors $a$ and $b$ will not be used in the following steps, and we can overwrite them with any other address vectors.) By Lemma B.2, we achieve this operation via a six-layer ReLU-MLP. Then, the state $x$ transforms as follows:

This operation requires a four-layer ReLU-MLP.

Step 1: Read the three addresses requires a two-layer ReLU-MLP.

Step 2: Read the data required by the instruction requires a two-layer ReLU-MLP.

Step 3: Perform subtraction requires a seven-layer ReLU-MLP.

Step 4: Write back $\texttt{mem}[b]-\texttt{mem}[a]$ requires a two-layer ReLU-MLP.

Step 5: Calculate $r_{pc+1}$ requires an six-layer ReLU-MLP.

Step 6: Conditional branching requires a four-layer ReLU-MLP.

Therefore, to emulate the “SUBLEQ” instruction, we need a twenty-three-layer ReLU-MLP with size $n\times n$. ∎

Appendix E LOOPED ReLU-MLP AS PROGRAMMABLE COMPUTER

Finally, in this section, we demonstrate the One Instruction Set Computer (OISC) constructed by the “SUBLEQ” instruction is equivalent to the programmable computer in terms of computational ability, which further indicates that the $23$-layer ReLU-MLP discussed in the previous section is capable to function as a programmable computer.

Let ReLU-MLP be defined as Definition 1.2.

Let $m$ denote the number of instructions.

Let $k$ denote the number of one-bit data stored in the memory. For $i\in[k]$, each data is $v_{i}\in\{\pm 1\}$ and the memory size $k$ satisfies $k=n-2-4\log(n)-3m\log(n)$.

Let the address vector $a_{i}\in\{\pm 1\}^{\log(n)}$.

Let the instruction $c_{i}\in\{\pm 1\}^{3\log(n)}$ be defined as Definition 3.6.

Suppose we have two data registers $r_{d_{1}},r_{d_{2}}\in\{\pm 1\}$, one carry bit $r_{c}\in\{\pm 1\}$, three address registers $r_{a_{1}},r_{a_{2}},r_{a_{3}}\in\{\pm 1\}^{\log(n)}$, and one program counter $r_{pc}\in\{\pm 1\}^{\log(n)}$ in the scratchpad.

Then, we can show that, a $23$-layer ReLU-MLP with width $n$ can emulate a programmable computer, where $d$ is the number of bits we use to store each integer. Namely, this “computer” supports integers within the range $[-2^{d-1},2^{d-1}-1]$.

In Lemma D.1, we have proved that a $23$-layer ReLU-MLP is capable for emulating the one bit version of “SUBLEQ” instruction.

Similar to the proof of Lemma A.2 and A.4, we can extend horizontally from one-bit version to $d$-bits version, where we apply the $23$-layer ReLU-MLP row by row, with totally $d$ loops.

By MP , the One Instruction Set Computer (OISC) with the instruction “SUBLEQ” is Turing complete, which means it can compute arbitrary programs. Therefore, we can conclude that our looped $23$-layer ReLU-MLP can actually function as a programmable computer. ∎