Complete identification of deep ReLU networks through Łukasiewicz logic

Authors

Yani Zhang and Helmut Bölcskei

Reference

Journal of Machine Learning Research, Sept. 2026, submitted.

Abstract

Two deep ReLU networks can have entirely different architectures and parameters, yet realize the same function. We provide a complete characterization of this nonuniqueness, by building a symbolic calculus for deep ReLU networks, equivalence and simplification of networks becoming derivation of formulae, in close parallel to Shannon’s analysis of switching circuits through Boolean logic. Two non-degenerate ReLU networks realize the same function on the unit cube if and only if one is obtained from the other by finitely many applications of the axioms of many-valued (MV) logic for integer weights and biases, of divisible MV logic for rational ones, and of Riesz MV logic for real ones. These axioms characterize all symmetries of ReLU networks, single-layer ones, the only kind for tanh networks, and deep ones spanning three or more layers. Our framework consists of three steps, extraction of a substitution graph whose represented formula has the network’s input–output map as its truth function, a completeness theorem making functionally equivalent formulae interderivable, and construction returning from graphs to networks. The substitution graph encodes the network uniquely and induces a new normal form for MV logic, compositional rather than flat, with three local operations realizing every derivation.

Keywords

Neural network identifiability, deep ReLU networks, Łukasiewicz logic, MV algebras, normal forms

Download this document:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.