Research map / Architectures and efficiency / RNNs and normalization
The Effect of Weight Precision on the Neuron Count in Deep ReLU Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical study showing that ReLU networks with high-precision weights can compute any boolean function with exponentially fewer neurons (via exponential-time construction), proposes a precision-sensitive size measure that matches Shannon's bound, and proves polynomial-time-printable networks compute exactly P.
Problem
How weight precision trades off against neuron count in ReLU networks, and whether high-precision weights give unreasonable computational power when the network description is generated under time constraints.
Approach
Encode the full truth table of a boolean function into a single high-precision weight and use ReLU gadgets to look it up, achieving O(2^(n/2)) neurons; then define a precision-sensitive size (bit count of rational weights) under which Shannon's 2^n/n lower bound holds again, and show polynomial-time printable networks equal P.
Key results
- Every boolean function on n inputs can be computed by a ReLU network of size O(2^(n/2)) using an exponential-time construction, below Shannon's Omega(2^n/n) bound for constant fan-in circuits.
- Under the precision-sensitive size measure p-SIZE, almost every boolean function requires size greater than 2^n/n, matching Shannon's bound.
- ReLU networks whose description is printable in polynomial time decide exactly the languages in P.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use unbounded-precision weights with exponential-time preprocessing | ReLU networks computing Boolean functions · Boolean functions on n inputs | ReLU network size (edges): O(2n/2) vs. Ω(2n/n) | Helped |
| Count weight precision in the network-size measure | ReLU networks computing Boolean functions · Boolean functions on n inputs | Network size lower bound: > 2n/n | Hurt |
| Restrict network-description generation to polynomial time | ReLU networks with arbitrary-precision weights · Boolean languages | Computational power | Hurt |
| Use high-precision weights without exponential-time preprocessing | ReLU networks · Boolean functions | Neuron count | No clear effect |
Surprising findings
- Exponentially fewer neurons are possible with high weight precision, implying neuron count alone is an insufficient complexity measure.
- Polynomial-time generated high-precision ReLU networks gain no extra power beyond P, so precision helps only with super-polynomial preprocessing time.
Limitations
- No training algorithm shown that exploits high weight precision; results are purely theoretical.
- Constructed networks are as deep as their size (O(2^(n/2))), and the exponential-time generator makes them impractical.
- Results are stated only for ReLU activation; other activations such as softmax or sigmoid are open.
Experimental setup
Builds on: Shannon circuit lower bound Lupanov construction Dančík 1996 unbounded fan-in circuit construction
Closest papers by meaning
- Functional vs. parametric equivalence of ReLU networks (ICLR 2020 · similarity 0.87)
- Network size and size of the weights in memorization with two-layers neural networks (NeurIPS 2020 · similarity 0.87)
- Understanding Deep Neural Networks with Rectified Linear Units (ICLR 2018 · similarity 0.87)
- Convergence of Near-Linear Width ReLU Networks with Unbalanced Initialization (NeurIPS 2026 · similarity 0.87)
- Neural Characteristic Activation Analysis and Geometric Parameterization for ReLU Networks (NeurIPS 2024 · similarity 0.86)
- Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.