acceptodds
Under review as a conference paper at ICLR 2027

Shallower ReLU Network Representations via Exact Linear Algebra

Abstract

We study the number of hidden layers required by ReLU networks to represent piecewise-linear functions exactly, focusing on the maximum function. This problem has recently received significant attention in both the ML and TCS literature. We prove that is exactly representable with two hidden layers for every . Previously, the largest known arity was [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC '26]. We obtain our constructions through an exact computer-assisted search within a space of candidate solutions. After a symmetry reduction, we obtain a finite system of linear equations over such that any solution yields a valid representation of the maximum function. The resulting constructions have a structured first hidden layer, which enables recursive substitution into networks with more hidden layers. This yields an exact ReLU representation of with at most hidden layers. Consequently, every continuous piecewise-linear function on admits an exact representation with at most hidden layers. In particular, two hidden layers suffice for . These results improve upon Bakaev, Brunck, Hertrich, Stade, and Yehudayoff [STOC '26], who proved analogous logarithmic bounds with base three.

Primary area:
learning theory
Keywords:
ReLU networks, exact representations, neural network expressivity, computer-assisted proofs, polyhedral geometry

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.25 over 4 reviews, above 96% of the others.
Reviewer_nxDTOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies an important question in expressivity: whether there is a depth separation in the expressivity of finite-width ReLU networks. It provides a O(log⁡12(d))O(\log_{12}(d)) upper bound for the number of hidden layers required to express a dd-dimensional CPWL function, significantly improving upon the previous O(log⁡3(d))O(\log_3(d)) upper bound, although a lower bound better than 2 remains unaddressed.

Critical strengths

The studied problem is long-open and this work presents a solid progress on the upper bound. No major proof mistake is identified during review. The approach is well-described and readable, the idea of using symmetry to reduce candidates is elegant, and the proof cleverly combines computer-aided solving in small dimensions with theoretical argument to scale to large dimensions.

Critical weaknesses

The main weakness is a still open lower bound, which does not present a reason for rejection, since it is commonly believed to be substantially harder. The existing result already gounds its importance.

Questions for authors

It seems there is no specific reason to stop at log⁡12\log_{12} and perhaps the restricted candidate family excludes too many possible solutions. Is there any potential future direction that authors may believe to be helpful, in particular to resolve the conjecture proposed in this work?

2 comments

We thank the reviewer for the positive review.

There is no mathematical reason to stop at n=12n=12. As the size of the linear system of equations undergoes a combinatorial explosion, for n≥13n \ge 13 we weren't able to find a solution due to computational limits. Using more time and more computational resources, together with some algorithmic improvements, it might be feasible to push this limit a bit, but we would only expect very small incremental increases. You are right that the candidate family may exclude valid representations. We need a candidate family that is expressive enough while keeping the search computationally feasible.

We point out that our conjecture has been resolved for all nn after the submission by Brunck, Hertrich, Rueß, Stade and Yehudayoff in arXiv:2610.28587. Their combinatorial proof builds on several ideas from this paper and we believe our intermediate result provided a useful step towards resolving the conjecture for all nn. In particular, our paper established that the earlier discovery of a two-hidden-layer construction for max⁡5\max_5 by Bakaev et al. was not a low-dimensional exception.

Dear authors,

Thanks for the reply. I have also seen the new work on establishing lack of depth separation. I am happy to have rated this positively to support this work.

Reviewer_4BUgOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the number of hidden layers required by ReLU networks to represent continuous piecewise-linear functions exactly, if we are given no limitation on the width of the network.

  1. The paper proves that max⁡n\max_n is exactly representable with two hidden layers for every n≤12n\le12. Previously, the largest known arity was 5 (Bakaev et al., 2026).

  2. The paper gives an exact ReLU representation of max⁡n\max_n with at most ⌈log⁡6(n/2)⌉+1\lceil\log_6(n/2)\rceil+1 hidden layers, improving the previous logarithmic bound from base three to base six. This also improves the depth bound for general continuous piecewise-linear functions.

  3. The paper finds these constructions through symmetry reduction and exact linear algebra, reducing the search to a finite system of linear equations over Q\mathbb{Q}. The previous max⁡5\max_5 construction used geometric arguments.

For validation, the authors use computer programs to verify that their networks compute the maximum correctly for up to 12 inputs. They also give worked examples for five and six inputs.

Critical strengths

The mathematical arguments appear sound. The authors also provide proofs and separate programs to verify the constructions. This gives me confidence that the claimed depth bounds are valid.

Critical weaknesses
  1. The paper strengthens existing representation guarantees without establishing a practical benefit. It extends the two-hidden-layer construction from max⁡5\max_5 to max⁡12\max_{12}, improves the logarithmic depth bound from base three to base six, and separates rational from finite-decimal weights. These advances leave the main practical gap unchanged: exact representability still provides little guidance for designing, training, or running efficient networks. Even when judged purely as a theoretical study of exact expressivity, the results do not change the asymptotic depth bound, resolve the general two-hidden-layer representability problem, or provide a unified structural explanation for the discovered constructions. The paper does not show what these stronger guarantees enable in practice. I therefore find the impact of pushing these bounds further too limited to justify acceptance.

  2. The paper reduces depth without adequately examining the cost in network size. The direct two-layer construction has an unoptimized factorial upper bound on width (lines 897–924). The widths and parameter counts of the recursive construction are not quantified or compared with earlier constructions. The paper therefore leaves unclear how much additional size is needed to use fewer layers. Its depth improvement establishes no corresponding improvement in computational efficiency.

  3. The search for new two-hidden-layer constructions is difficult to scale. The authors could not complete the case n=13n=13 because it exceeded their available computing resources (lines 473–474). They also found no common construction explaining the solutions across input sizes (lines 475–478). Extending the two-layer results therefore still depends on separate, expensive searches. This limits the reach of the proposed discovery method.

Questions for authors
  1. Earlier work already guarantees exact representation (lines 039 and 078–083). The new general bound improves the leading constant (lines 105–107). What concrete benefit does this stronger guarantee provide for network design, training, or inference? Please clarify what follows from the current results beyond reducing the number of hidden layers under unrestricted width.

  2. Appendix E gives an unoptimized width bound for the direct two-layer construction (lines 897–924). What are the layer widths and total parameter counts after the recursive substitution in Section 4 (lines 399–424)? How do they compare with the binary-tree and Bakaev et al. constructions for the same number of inputs? This comparison would clarify the computational cost of the depth reduction.

2 comments

We thank the reviewer for the careful assessment and raising concrete questions about the size of the recursive construction and comparisons with existing approaches.

  1. Significance of the results

    Our results concern exact expressivity and do not directly imply improvements in training or inference. Beyond improving depth bounds, we show that the set of functions representable by two-hidden-layer ReLU networks depends on the class of allowed weights, even when considering relatively unrestricted classes like decimal fractions with arbitrary precision. For example, previous work showed that exact representation of max⁡10\max_{10} requires at least three layers with decimal fractions, whereas we establish a two-hidden-layer network with rational coefficients that are not decimal fractions.

    The motivation for studying these questions is theoretical and guided by the general question of what role depth plays in the expressivity of ReLU networks. Such questions have received considerable and sustained attention in the TCS and ML communities. For example, recent works at ICLR (Arora et al., 2018, Haase et al., 2023, Averkov et al., 2025 [Spotlight]), NeurIPS (Hertrich et al., 2021, Grillo et al., 2025 [Oral]), STOC (Bakaev et al., 2026) and COLT (Safran, 2026) have investigated the role of depth in expressivity of ReLU networks, particularly for exact representations of the maximum function.

    In particular, even fundamental and seemingly simple questions, such as whether max⁡6\max_6 can be represented with two-hidden-layer ReLU networks, remained open before our work despite considerable previous efforts. Resolving these fundamental questions provides valuable insights into the expressive power of ReLU networks. Our results also establish that the earlier geometric two-hidden-layer construction for max⁡5\max_5 is not an isolated lower-dimensional exception, but indicates that two-layer networks possess greater expressive power than previously known.

  2. Width and parameter counts

    Thank you for the suggestions for giving explicit upper bounds on the number of nonzero weights and the width of the construction obtained by the recursive composition of the smaller networks in the paper. Both are at most quadratic in the arity, once we fix the network that acts as the base case of the recursive construction. We stated this as Proposition 4.2 after the construction and added a proof in Appendix E.2. We also added a comparison of depth, width, and nonzero parameter counts with the binary-tree and Bakaev et al. constructions in Table 3.

Hi, thanks for answering the question!

I feel like I still don’t understand the significance of this research. I have not done this kind of theory research and thus unable to find this work interesting (which is my fault).

I have being thinking about how to rate this paper for very long time. It is solid work and it is clear authors have being working on this hard… I still can’t convince myself to raise the score to 3, but I will raise my score to 2. Good luck!

Reviewer_b3rWOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The manuscript studies the minimum hidden depth required for exact representation of continuous piecewise-linear (CPWL) functions by ReLU networks of unrestricted width. It constructs rational two-hidden-layer representations of the maximum of up to twelve inputs through permutation symmetry and exact linear algebra. The first-layer structure enables recursion, yielding at most ⌈log⁡6(n/2)⌉+1\lceil\log_6(n/2)\rceil+1 hidden layers for max⁡n\max_n and ⌈log⁡6((d+1)/2)⌉+1\lceil\log_6((d+1)/2)\rceil+1 for general CPWL functions on Rd\mathbb R^d. Two hidden layers suffice through dimension eleven. The construction also separates rational from decimal-fraction weights.

Critical strengths
  • The finite-arity construction improves a universal depth bound for an entire function class.
  • The search produces exact rational identities and separates verification from discovery.
  • The structured recursion and rational-versus-decimal separation give the result significance beyond the computed examples.
Critical weaknesses
  1. Explain the limit of the two-hidden-layer construction and the prospect of extending it to all dimensions (Section 5 and Appendix D).

    The universal two-hidden-layer guarantee reaches d≤11d\le11, since the certificates reach max⁡12\max_{12} and n=d+1n=d+1. Thus d=12d=12 corresponds to the unresolved max⁡13\max_{13}. Section 5 attributes this case to resource limits; a more concrete diagnosis would help. At n=13n=13, Corollary D.2 forces kk to increase from 5 to at least 6, while Table 2 already reports about 12.3 million candidate orbits and 1.5 million reduced directions for n=12n=12. Which stage becomes prohibitive: candidate enumeration, feature expansion, matrix storage, or exact solution?

    Section 5 also acknowledges the restricted ansatz and the absence of a common construction. Building on that discussion, is there structural evidence for solvability at kmin⁡k_{\min}, or at some larger kk, as nn grows? The substitution theorem handles all dimensions by increasing depth, so it cannot establish universal depth two. Please clarify what further idea would be needed to preserve two layers. A qualitative explanation would suffice; I am not asking for resolution of Conjecture 1.4.

  2. Explain the depth–width tradeoff and parameter costs for finite-element representations (Theorem 4.1, Corollary 1.3, and Appendix E).

    For the certified two-hidden-layer cases, Appendix E already gives widths at most (n2)+2n\binom n2+2n and 3Kcertn!3K_{\mathrm{cert}}n!. Please supplement these with a bound on nonzero weights and biases, and propagate the estimates through the recursion and Wang–Sun decomposition. Coarse upper bounds would suffice. For a general CPWL target, specify the dependence on its number of affine pieces or decomposition terms, in addition to dimension. Please distinguish layer widths, sparse parameter counts, and the number of entries in a fully connected architecture.

    For a linear finite-element function fh=∑i=1Nciϕif_h=\sum_{i=1}^N c_i\phi_i, sequential and parallel evaluation of the local basis contributions lead to different architectures. For fixed dimension and uniformly bounded local mesh complexity, serializing bounded-size hat networks gives O(N)O(N) depth and O(1)O(1) width; parallel evaluation gives depth independent of NN and O(N)O(N) width. Both can have O(N)O(N) nonzero parameters. Please discuss this tradeoff in relation to the mesh-based constructions of He–Li–Xu–Zheng, “ReLU Deep Neural Networks and Linear Finite Elements” (2020), Sections 3 and 5, and Longo–Opschoor–Disch–Schwab–Zech, “De Rham compatible Deep Neural Network FEM” (2023), Proposition 5.7.

    Applying the present certificates to each local hat before parallelization should also give a coarse linear-in-NN size bound at two hidden layers for d≤11d\le11, but potentially with very large constants. Please make the local decomposition cost, certificate-size dependence, and mesh assumptions explicit. How do the resulting widths and sparse parameter counts compare with these existing FEM representations? A coarse estimate and discussion would suffice to clarify the cost accompanying the depth reduction.

  3. State the certificate equations explicitly after reduction (Section 3.2 and the proof of Theorem 1.1).

    The initial LA,BL_{A,B} and cA,B,dc_{A,B,d} describe the raw permutation expansion. As written, raw equation (5) cannot hold for n≥3n\ge3: formula (17) places every raw LA,BL_{A,B} in the span of ∑jxj\sum_jx_j and ∑j(j−1)xj\sum_j(j-1)x_j, which excludes xnx_n. For the printed n=6n=6 coefficients, the raw linear combination is 115∑j(j−1)xj\frac1{15}\sum_j(j-1)x_j; the reduced combination is correctly x6x_6.

    Remark 3.1 instructs simplification before assembly, and I verified the printed reduced identities. Please introduce reduced quantities L~A,B\widetilde L_{A,B} and c~A,B,d\widetilde c_{A,B,d} and use their equations in the proof and verifier description. This focused formal correction makes the central certification step precise.

  4. Clarify the certificate and search metadata (Section 3.4, Table 2, and Appendix F).

    The separate Python and Rust verifiers are valuable. Please report verification time and peak memory for n=12n=12 and explicitly confirm both reduced-hinge cancellation and the exact linear vector e12e_{12}. Specify the candidate restrictions used for each Table 2 row and their relation to Remark 3.2. The printed examples use repeated or diagonal pairs, so their relationship to the restricted certificates also merits clarification.

Questions for authors
  • Regarding Conjecture 1.4, do you expect the current candidate family, allowing kk to grow, to yield two-hidden-layer representations for every max⁡n\max_n?

  • What mathematical difficulty remains beyond the computational limits encountered at n=13n=13?

3 comments
AuthorsOpenReview ↗

Respone (Part 1)

We thank the reviewer for the positive assessment and the detailed suggestions for improving the manuscript.

Critical weaknesses

  1. After submission, Brunck, Hertrich, Rueß, Stade and Yehudayoff resolved our conjecture for all nn, building on several ideas from this paper (see the answer to your first question below). Whether our candidate family admits representations at kmin⁡k_{\min} for all nn remains open.

    For n=13n=13, the lower bound requires at least kmin⁡=6k_{\min} = 6. Even in the restricted setting of Remark 3.2 there are 7,976,4047\\,976\\,404 candidate orbits and 5,469,4395\\,469\\,439 reduced nonlinear directions (see revised Table 2). Storing the full dense coefficient matrix at eight bytes per entry would require

    \approx349\text{ TB}.$$ Storing the full dense matrix, let alone solving the system of linear equations, seems prohibitive with the computational resources available to us. The counts in Table 2 suggest that the number of matrix entries grows by roughly three orders of magnitude whenever $k_{\min}$ increases by one, i.e., $n\mapsto n+2$. Even if solving the case $n=13$ became feasible, we would expect another increase of this scale at $n=15$, making further computations difficult without substantial new algorithmic or structural insights. We don't have structural evidence that solvability at $k_{\min}$ extends to larger $n$. However, it suffices for every tested $n$, namely $5\le n\le12$, so we expect this to continue for larger $n$. Using substitution to retain two layers for all $n$ seems out of reach. To show that there are representations within our candidate family at $k_{min}$ for all $n$, one probably needs to find a structural insight that helps prove that the system of linear equations has a solution instead of computing one for every $n$.
  2. We thank you for the suggestions to add upper bounds on the number of neurons, (nonzero) parameters and the width of the resulting recursive constructions. For a fixed base network, we obtain quadratic upper bounds on the number of neurons, nonzero parameters and width, and a quartic upper bound on the number of all parameters. We also compare those numbers to the existing construction in Table 3.

    We thank the reviewer for highlighting connections to finite-element representations. Let d≤11d\le11 and assume each hat function Φi\Phi_i can be extended to a CPWL function on Rd\mathbb{R}^d with at most mm Wang–Sun terms. Write w1(d),w2(d)w_1^{(d)},w_2^{(d)} for the widths of our two-hidden-layer network for max⁡d+1\max_{d+1}. Applying these networks in parallel gives a representation of f=∑i=1NciΦif=\sum_{i=1}^N c_i\Phi_i with two hidden layers, widths Wj≤Nmwj(d)W_j\le Nm w_j^{(d)} for j=1,2j=1,2, and at most

    Nm[(d+1)w1(d)+(w1(d)+2)w2(d)]+1Nm \left[(d+1)w_1^{(d)}+(w_1^{(d)}+2)w_2^{(d)}\right]+1

    nonzero parameters. For fixed dd and mm, those are linear in NN. Sequential evaluation gives O(N)\mathcal{O}(N) depth, O(1)\mathcal{O}(1) width and O(N)\mathcal{O}(N) nonzero parameters. The constants can be very large, so these estimates do not show that our networks are competitive with specialized FEM constructions. Our result does extend the dimension from 44 to 1111 where representation of CPWL hat functions with two-hidden-layer networks is known.

  3. We agree that the reductions were only applied implicitly and we used the same notation for the unreduced and reduced equations. We made this more explicit in the revised manuscript by introducing separate notation for the reduced system of linear equations.

  4. The Rust program took 15:32 min to verify the n=12n=12 solution on an author's laptop using 8 cores (AMD Ryzen 7 4700U) and had a peak memory usage of 16.34GB. For n≤10n\le10, verification is almost immediate, taking less than a second. The Python implementation is only useful up to n=8n=8, as it is simpler and less efficient. Both explicitly compute the reduced forms and add up all linear contributions and all nonlinear terms. It is checked that the linear part equals ene_n and all nonlinear terms cancel. Table 2 now gives counts for both the unrestricted family and the restricted family of Remark 3.2. For the examples we have chosen solutions with repetitions, as they use fewer orbits than the ones we found in the setting of Remark 3.2 and therefore keep the examples short and easier to verify by hand.

AuthorsOpenReview ↗

Response (Part 2)

Questions for authors

  • Solvability within the candidate family

    Yes, we expect that the family leads to a solution for all nn, when using kmink_{min}. Our conjecture was resolved a few weeks after submission in arXiv:2610.28587 by Brunck, Hertrich, Rueß, Stade and Yehudayoff. Their combinatorial proof builds on several ideas from this paper, including summing over permutations in the symmetric group and using a first layer of pairwise comparisons. We believe our results provided a useful step towards resolving the conjecture for all nn. In particular, they showed that the two-hidden-layer representation of max⁡5\max_5 was not a low-dimensional exception. The generating segments of their parallelepipeds also correspond to edges of a tree, connecting their construction to the restricted family in this paper. The stronger result that max⁡n∈Vn,⌊(n−1)/2⌋\max_n \in V_{n, \lfloor (n-1)/2 \rfloor} that is established in this paper for 3≤n≤123 \le n \le 12, is not covered by the general proof to the best of our knowledge.

  • Remaining mathematical difficulty

    The remaining mathematical difficulty is to understand why solutions within our candidate family exist at kmin⁡k_{\min} for the tested values of nn, and whether this extends to all nn. To the best of our knowledge, the subsequent general two-hidden-layer result does not establish this stronger statement. A structural argument proving solvability of the reduced linear systems for arbitrary nn would remove the need for separate computations at each arity.

I am very happy to see that the authors also noticed the work by Brunck, Hertrich, Rueß, Stade and Yehudayoff. Furthermore, the authors' comments about the relation between their work and the work by b Brunck et al. are useful and resolve most of my concerns about the novelty and significance. I would like to suggest that the authors mention the work by Brunck et al. and add their comments to clarify the meaning of this work in the following revision version. Consequently, I would like to raise the final score, as this work is an important step in solving the minimal depth problems in representing CPWL functions by ReLU DNNs.

Reviewer_KCKQOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies how many hidden layers a ReLU network needs to represent a maximum function exactly when its width is unrestricted. The construction combines functions built from pairwise maxima so that the nonlinear terms cancel. Symmetry reduces the search for suitable coefficients to a finite system of linear equations, which the authors solve using exact rational arithmetic. The resulting certificates can be verified independently of the search.

Critical strengths

The paper extends the known range of maximum functions representable with two hidden layers from 5 inputs to 12. Because the first layer uses pairwise maxima, the construction can also be reused to handle larger inputs with fewer additional layers. This improves the general logarithmic depth bound from base three to base six and shows that two hidden layers suffice for every CPWL function in dimensions up to eleven.

Critical weaknesses

There is an apparent mismatch between the additional restrictions in Remark 3.2 and the supplied certificates, as detailed below. I would like this clarified, although I do not currently view it as a reason for rejection.

Questions for authors

Clarification of Remark 3.2: The remark states that solutions exist without diagonal pairs, repeated pairs, pairs shared by AA and BB, or cycles within either edge set. The proof of Theorem 1.1 also says that these restrictions were used for n=11,12n=11,12. However, the supplied n=12n=12 certificate includes diagonal pairs (7,7)(7,7) and (3,3)(3,3), and the second term includes a triangle on vertices (3,5,6)(3,5,6).

Are there separate certificates satisfying all the restrictions in Remark 3.2? Please clarify how the supplied files relate to that remark and the proof of Theorem 1.1. If the restricted constructions have not been verified, please clarify which statements need revision.

2 comments

We thank the anonymous reviewer for the feedback and the positive stance on the submission.

Thank you for finding the discrepancy between the claim about the restricted family and the certificates in the supplementary material. The certificates in the original supplementary material used slightly modified search code that was also allowed to use (some) elements outside the restricted setting. The claim that the restricted family allows for a solution for all 5≤n≤125\le n\le12 is still true and we added corresponding certificates for n=5,…,12n=5,\ldots,12 that only use elements of this restricted family to the supplementary material. The original certificates are now in certificates_unrestricted/ and the additional restricted certificates are in certificates_restricted/.

Thank you for the clarification. I will maintain my original score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.