Complete Identification of Deep ReLU Networks through Łukasiewicz Logic

Deep learning has transformed how machines see, speak, and reason, yet the inner workings of these systems often remain a black box. At the heart of this mystery lies a simple but profound puzzle: two neural networks can look completely different on the inside—one might have a wide, shallow structure while another is narrow and deep, or they might use entirely different numbers to tune their connections—yet they produce the exact same result for every possible input. For years, scientists have known this happens, but they could not fully explain why or map out every way it could occur. This uncertainty matters because if we cannot tell when two models are truly distinct, we cannot fully understand the landscape of learning, nor can we be sure what a model has actually learned versus what is merely a coincidence of its design. The question is not just about counting possibilities; it is about finding a complete rulebook that describes every single way a machine can be rearranged without changing its behavior.

A team of researchers at ETH Zürich has now solved this problem for a specific, widely used type of artificial intelligence known as a ReLU network. These networks are the workhorses of modern image recognition and many other applications, relying on a simple mathematical rule that turns negative values to zero while leaving positive values unchanged. The researchers discovered that the reason these networks can be so different yet functionally identical is that they are governed by a hidden set of logical laws, much like the rules of arithmetic or the logic of switches in an electrical circuit. By translating the network's structure into a language of logic, they proved that any two networks performing the same task can be transformed into one another through a finite series of specific, allowed moves. This finding provides a complete map of the "symmetries" of these networks, revealing that the redundancy is not random chaos but a structured, predictable system.

To understand the breakthrough, one must first grasp the nature of the problem. A deep neural network is built in layers, where each layer processes information and passes it to the next. The researchers found that for a long time, scientists only knew about "shallow" symmetries—ways to rearrange the connections within a single pair of layers without changing the outcome. For example, you could swap the order of two neurons in a layer and adjust their weights accordingly, and the network would behave exactly the same. However, the researchers showed that this was only part of the story. They demonstrated that there are "deep" symmetries that span across three or more layers, allowing for massive structural changes that cannot be achieved by simply tweaking one layer at a time. These deep symmetries can fundamentally alter the architecture of the network, merging or splitting sections in ways that were previously thought to be impossible without changing the function.

The key to unlocking this mystery was to stop looking at the networks as collections of numbers and start viewing them as expressions of a specific kind of logic. The researchers built a symbolic system that translates the network's input and output into a logical formula. In this system, the network's behavior is equivalent to a statement in a many-valued logic, a system that extends traditional true-or-false logic to a continuous scale of possibilities. Just as a mathematician can prove that two different algebraic equations are actually the same by applying a set of standard rules, the researchers showed that two different networks are functionally identical if and only if their corresponding logical formulas can be transformed into one another using the axioms of this logic. This means that the question of whether two networks are the same is no longer a matter of guessing or testing; it is a matter of derivation, a step-by-step logical proof.

The team developed a three-step process to make this work. First, they created an algorithm to extract the logical formula hidden inside any given network, effectively reading the network's mind to find its underlying truth. Second, they applied the rules of their logical system to show that any two networks producing the same output must have formulas that can be derived from one another. This step relies on a deep mathematical theorem that guarantees no possibilities are missed; if two networks do the same job, there is a logical path connecting them. Third, they built a reverse algorithm that can take a logical formula and reconstruct the exact network that produced it. This closed the loop, proving that the logical description is a perfect, faithful representation of the physical network.

What makes this result particularly powerful is that it covers every possible scenario, from networks with simple whole-number weights to those with complex fractions or even infinite decimal values. The researchers showed that the same logical framework applies regardless of the precision of the numbers used, provided the network is not "degenerate"—meaning it does not contain useless parts that do nothing. They also identified that some of the rearrangements allowed by these rules are "pseudo-deep," meaning they look like they span multiple layers but are actually just a combination of simpler, single-layer tricks. By distinguishing between genuine deep symmetries and these superficial ones, the researchers provided a clear taxonomy of how these networks can be reshaped.

This work does more than just solve a theoretical puzzle; it offers a new way to think about the identity of artificial intelligence models. Before this, if two models produced the same results, it was unclear if they were fundamentally the same or just lucky coincidences. Now, we know that their equivalence is a matter of logical derivation. If you can transform one network into another using the specific rules discovered by the researchers, they are the same. If you cannot, they are genuinely different. This clarity is essential for understanding the geometry of learning, helping scientists see the true shape of the space in which these models operate. It suggests that the vast redundancy in neural networks is not a flaw but a feature, a structured flexibility that allows for multiple paths to the same solution.

The researchers' approach mirrors a famous historical breakthrough in electrical engineering, where the logic of circuits was mapped to the logic of switches, allowing engineers to design complex systems with mathematical certainty. Here, the same principle is applied to the complex, layered structures of deep learning. By treating the network as a logical object rather than just a statistical one, the team has provided a complete characterization of its symmetries. They have shown that the universe of ReLU networks is governed by a set of rules that are as rigorous and complete as the laws of arithmetic. This means that the mystery of why different networks can do the same thing is no longer a mystery at all; it is a solved equation, with every possible solution accounted for by the axioms of many-valued logic. The result is a definitive guide to the identity of deep neural networks, turning a landscape of confusion into a map of precise, navigable connections.