Depth-Bounds for Neural Networks via the Braid Arrangement
Authors: Moritz Leo Grillo
Christoph Hertrich
Georg Loho
Venue: NeurIPS 2025 oral ()
Keywords: Neural Networks
Piecewise Linear Functions
Exact Representations
Polyhedral Geometry
Braid Fan
Boolean Lattice
Primary area: theory

Abstract: We contribute towards resolving the open question of how many hidden layers are required in ReLU networks for exactly representing all continuous and piecewise linear functions on $\mathbb{R}^d$. 
While the question has been resolved in special cases, the best known lower bound in general is still 2. 
We focus on neural networks that are compatible with certain polyhedral complexes, more precisely with the braid fan.  
For such neural networks, we prove a non-constant lower bound of $\Omega(\log\log d)$ hidden layers required to exactly represent the maximum of $d$ numbers. Additionally, we provide a combinatorial proof that neural networks satisfying this assumption require three hidden layers to compute the maximum of 5 numbers; this had only been verified with an excessive computation so far.
Finally, we show that a natural generalization of the best known upper bound to maxout networks is not tight, by demonstrating that a rank-3 maxout layer followed by a rank-2 maxout layer is sufficient to represent the maximum of 7 numbers.

Depth-Bounds for Neural Networks via the Braid Arrangement
Moritz Grillo
Christoph Hertrich
Max Planck Institute for Mathematics in the Sciences moritz. grriitt.rr... lo@mis mpg. de
University of Technology Nuremberg christoph. www.tpph.eertriihtu.....
Georg Loho
Freie Universität Berlin University of Twente
georg www.@mathhhhhooooomoo fu-berlin.de
Abstract
We contribute towards resolving the open question of how many hidden layers required in ReLU networks for exactly representing all continuous and piecewise linear functions Rd. While the question has been resolved in special cases, the best known lower bound in general is still 2. We focus on neural networks that are compatible with certain polyhedral complexes, more precisely with the braid fan. For such neural networks, we prove non-constant lower bound of (log log d) hidden layers required exactly represent the maximum of d numbers. Additionally, we provide a combinatorial proof that neural networks satisfying this assumption require three hidden layers to compute the maximum of 5 numbers; this had only been verified with an excessive computation so far. Finally, we show that natural generalization of the best known upper bound to maxout networks is not tight, by demonstrating that rank-3 maxout layer followed by a rank-2 maxout layer sufficient to represent the maximum of numbers.
Introduction
Among the various types of neural networks, ReLU networks have become particularly prominent [Glorot et al., 2011, Goodfellow et al., 2016]. For a thorough theoretical understanding of such neural networks, it is important analyze which classes of functions Classical universal approximation theorems [Cybenko, 1989, Hornik, 1991] ensure that just one hidden layer can approximate any continuous function on a bounded domain with arbitrary precision. However, establishing an analogous result for exact representations remains an open question and is the subject ongoing research [Arora et al., 2018, Hertrich al., 2023, Haase et al., 2023, Valerdi, 2024, Averkov et al., 2025].
represent with which depth.
While in practical settings approximate representations often sufficient, studying the exact piecewise linear structure neural network representations enabled deep connections between neural networks and fields like tropical and polyhedral geometry [Huchette al., 2023]. These connections, in turn, are important for algorithmic tasks like neural network training [Arora et al., 2018, Goel et al., 2021, Khalife and Basu, 2022, Froese al., 2022, Froese and Hertrich, 2023, Bertschinger al., 2023] and verification [Li et al., 2019, Katz et al., 2017, Froese et al., 2025b.a, Stargalla et al., 2025], including understanding the computational complexity of the respective tasks.
Arora et al. [2018] initiate the study of exact representations by showing that the class of functions exactly representable by ReLU networks is the class of continuous piecewise linear (CPWL) functions.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Specifically, they demonstrate that every CPWL function defined on Rd can be represented by ReLU network with [log2(d d + 1)] hidden layers. This result is based on Wang and Sun [2005]. who reduce the representation of a general CPWI. function to the representation of maxima of d + affine terms. By computing pairwise maxima in each layer, such a maximum of d + terms can be computed with logarithmic depth overall in the manner of binary tree. Very recently, Bakaev et al. [2025b] improved the upper bound by proving that every CPWL function can be represented with [logs(d (d 1)] + 1 hidden layers. Their results refute the conjecture of Hertrich et al. [2023] that [logg (d + 1)1 hidden layers are indeed necessary to compute all CPWL functions.
Based on the result by Wang and Sun [2005], Hertrich et al. [2023] deduced that it suffices to determine the minimum depth representation of the maximum function. While it easy to show that max(0, 21, ]2} cannot be represented with one hidden layer [Mukherjee and Basu, 2017], Bakaev et al. [2025b] showed that two hidden layers are sufficient to represent max (0, 21, R2, 33, ..4- However, remains open if there exists a CPWL function on E that really needs logarithmic many hidden layers to be represented. In particular, it is already open whether there is a function that needs more than two hidden layers to be represented.
Understanding depth lower bounds is important for clarifying the potential advantages of architectural choices. In particular, proving depth lower bounds on computing the max function helps formally explain why elements like max-pooling layers are powerful and cannot be easily replaced by shallow stacks of standard ReI.U layers, regardless of their width.
In order to identify tractable special cases to prove lower bounds on the necessary number of hidden layers to compute the max function, two approaches have been pursued so far. The first restricts the possible breakpoints of all neurons in a network computing x + max I1, ................................ xa). A breakpoint of a neuron is an input for which the function computed by the neuron is non-differentiable. A neural network is called B3- P2-conforming if breakpoints only appear where the ordering of some pair of coordinates changes (i.e., all breakpoints lie hyperplanes I2 Ij or 22 0). While B8gcooforming networks can compute the max function with [log2 (d + 1)] hidden layers, Hertrich et al. [2023] show that 2 hidden layers are insufficient to compute the function max I1, 22, 33, } using computational proof via mixed integer programming formulation of the problem. The second approach restricts the weights of the network. Averkov et al. [2025] show that, if all weights are log d
N-ary fractions, the max function can only be represented by neural network with depth 2 log log N by extending an approach of Haase et al. [2023]. Furthermore, Bakaev et al. [2025a] proved lower bounds for the case when some or all weights are restricted to be nonnegative. To the best of our knowledge, the two approaches of restricting either the breakpoints or the weights are incomparable.
Our contributions We follow the approach from Hertrich et al. [2023] and prove lower bounds on 13- -of-onforiing networks. On one hand, following Hertrich et al. [2023], we believe that understanding B -onfofrorg networks might also shed light on the expressivity of general networks, for example, by studying different underlying fans instead of focusing on the braid fan as an intermediate step. On the other hand, By ey--ooffrringg also appears in Brandenburg et al. [2025] and Froese et al. [2025b] due to the connection to submodular functions and graphs.
In Section 4 we prove for d = 2²' -1 thht the function x + max Z1.... rd } is not representable with a conforming ReLU network with E hidden layers. This means that depth ?(log log d) is necessary for computing all CPWL functions, yielding the first conditional non-constant lower bound without restricting the weights of the neural networks.
To prove our results, the first observation is that the set of functions that are representable by a 19 -on-ooffrinngg network forms a finite-dimensional vector space (Proposition 2.2). While one would like to identify subspaces of this vector space representable with certain number of layers, taking the maximum of two functions does not behave well with the structure of linear subspaces. To remedy this, we identify a suitable sequence of subspaces (k( for = 1, 2.... that can be controlled through inductive construction. These auxiliary subspaces arise from the correspondence between By -9-conforming functions and set functions. This allows us to employ the combinatorial structure of the collection of all subsets of finite ground set. This is also reflected in the structure of the breakpoints of -8-conforin functions. Hence, we are able to show that applying a --maoutt- layer to functions in Fe(k) yields function in Fe (x2 + k). lterating this argument yields the desired bounds.

---

In Section 5, we focus on the case d = 4. We provide combinatorial proof of the result of Hertrich et al. [2023] showing that the function z + max(0, 21, 22, 43, I3,,44) not representable by a B8-conforming ReLU network with two hidden layers.
Finally, in Section 6, we study maxout networks natural generalization of ReLU networks. A straightffrward generalization of the upper bound of Arora et al. [2018] shows that -8-conforming maxout network with ranks r; in the hidden layers ,,..., l can compute the maximum of I r; numbers. We prove that this upper bound is not tight: a maxout network with one rank-3 layer and one rank-2 layer can compute the maximum of 7 numbers, that is, the function max (0, 21,-.. F8).
Further Related Work In light of the prominent role the max function for neural network expressivity, Safran et al. [2024] studied efficient neural network approximations of the max function.
In an extensive line of research, tradeoff's between depth and size of neural networks have been explored, demonstrating that deep networks can be exponentially more compact than shallow ones [Montúfar et al., 2014, Telgarsky, 2016, Eldan and Shamir. 2016, Arora et al., 2018, Ergen and Grillo, 2024]. While most of these works also involve lower bounds the depth, they usually proven under assumptions on the width. contrast, we aim towards proving lower bounds on the depth for unrestricted width. The opposite perspective, namely studying bounds the size of neural networks irrespective of the depth, has been subject to some research using methods from combinatorial optimization [Hertrich and Skutella, 2023, Hertrich and Sering, 2024, Hertrich and Loho, 2024].
One of the crucial techniques in expressivity questions lies in connections to tropical geometry via Newton polytopes of functions computed by neural networks. This was initiated by Zhang al. [201 8], see also Maragos et al. [2021], and subsequently used to understand decision boundaries, bounds on the depth, size, or number of linear pieces, and approximation capabilities [Montúfar et al., 2022, Misiakos et al., 2022, Haase et al., 2023, Brandenburg et al., 2024, Valerdi, 2024, Hertrich and Loho, 2024].
Preliminaries
In Appendix A, the reader can find overview of the notation used in the paper and in Appendix B detailed proofs of all the statements.
Polyhedra We review basic definitions from polyhedral geometry; see Schrijver [1986]. Ziegler [2012] for more details.
A polyhedron P is the intersection of finitely many closed halfspaces and polytope is bounded polyhedron. A hyperplane supports P if it bounds closed halfspace containing P, and any intersection of P with such a supporting hyperplane yields a face F of P. A face is proper face F Ç P and + 0 and pnclusion-maximeee proper faces are referred to as facets. A (polyhedral) cone C' C I is polyhedron such that Au + wvv E C' for every E C' and X, l E Rzo. A cone is pointed if does not contain a line. A cone C is simplicial, there are linearly independent vectors
Ul..... Uk E R." such that C' = {> Apu > 2 03.
A polyhedral complex P is finite collection of polyhedra such that (i) 0 E (ii) P P then all faces P are in P. and (ii)) if P, p' E P, then P Pr a face both of P and P'. A polyhedral fan is a polyhedral complex where all polyhedra are cones. The lineality space of a polyhedron P is defined as {u E Rd x + U E P for all x E P}. The lineality space of a polyhedral complex P is the lineality space of one (and therefore all) P E
Neural networks and CPWL functions A continuous function f ER - R is called continuous and piecewise linear (CPWL), if there exists polyhedral complex P. such that the restriction of f to each aall-dimensiona polyhedron P E pm is an affine function. this condition is satisfied, we say that f and P are compatible with each other. We denote the set of all CPWL functions from Rdd to IR by CPWL.-
For number of hidden layers é. 2 0, a neural network with rectified linear unit (ReL.)) activation defined by sequence of & affine maps T, R -> RT, E [8 1]. We assume that no = d and 1441 = 1. If a denotes the function that computes the ReLU function + max 0}
3

---

in each component, the neural network is said to compute the CPWL function f: R - R given by 1 1 oa T3 a a TT.
A rank-r-maxone layer is defined by affine maps T( F + R" for q E [r] and computes the function + (max((T() j....., (T(7))) [es((] For number of hidden layers & 2 0 and rank vector r (ri...., re) E N rank-r-maxout neural network is defined by maxout layers fi 1 + _ of rank for i E [C] respectively and an affine transformation Tou: R + R. The rank-r-maxout neural network computes the function f: R - IR given by f f= Tout o fro. f1- rank-r-maxout neural network with input dimension
Let Mă be the set of functions representable d. Morcover, let (4) be the set of functions representable with networks with mank-2-mxxou layers.
The braid arrangement and set functions
Definition 2.1. The braid urrangement in IRd the hyperplane arrangement consisting of the (g) hyperplanes 2; 23. with 1 S i < j S d. The braid fan B& is the polyhedral fan induced by the braid arrangement.
Sometimes we will also refer to the fan given by the (d+1) hyperplanes I, = 2 and x; 0 for i d, which we denote by 152
We summarize the properties of the braid fan that relevant for this work. For more details see Stanley [2007]. The k-dimensional cones of B, are given by
{cone( s. ...., ss ) + span(1 (4)) 0 & S S S..... S Sz & [d].
where 1s = = Cj. The braid fan has span( (44) lineality space. Dividing out the lineality space of Ba yields _ See Figure la for an illustration of B4.
Using the specific structure of the cones of Ba in terms of subsets of [d] allows to relate the vector space VB, of CPWL functions compatible with the braid fan Ba with the vector space of set functions Fa = 2 restricting to the values on {1 SC(d] yields a vector space isomorphism t: VB, - Fa whose inverse map is given by interpolating the values on {1s} Jeia to the interior of the cones of the braid fan. Detailed proofs of all statements can be found in Appendix B.
Proposition 2.2. The linear map :: VB. + Fa given by F(S) = +(f(()) = f(lls) is an isomorphism.
This implies that VB, has dimension 24. Another basis for VB, is given by {ax M 2 where the function σM Rd + IR is defined by (M)))) maxieM Iy [Danilov and Koshevoy, 2000, Jochemko and Ravichandran, 2022]. We have the following strict containment linear subspaces:
VB, (0) & VB.(1) S ....S. VB, (d) VB.
where VB, == spanfaw | M S. [d].IM] S k).. In order to describe the linear subspaces & (VB, (k)), we now describe the isomorphism & with respect to the basis fa M 24d 3.
Let X and Y be finite sets such that X C Y, then the interval [X,]] = {S C [X]
X CCS)
Boolean lattice with the partial order given by inclusion. The rank of [X, YJ given by YY \ X). Sometimes we also write X1 I. for the set (#1...., In,)...,,)) E L and I1 ... Vn for the set For Boolean lattice C = [X, Y] of rank n, the rank function r: - [n]o X and r(S) is called the rank of S. Moreover, we define the levels of a Boolean lattice by C. = r (i) and introduce the notation Czi= == U, i C, for the set of elements whose rank is bounded by i. For S,T with T, we call [S, T" a sublattice of L and define 1. The set Fc = y of real-valuee
X UY (ZI,...,
is given by r(S)
the vector a' E C by uss = functions on L is a vector space, and for any fixed S,T E L, the map F + (as.r, F)) is a linear functional of Fe. Furthermore, let
( span(as, S.T L, T such that r(T) r(S) k+ 1}
and Fe(k) = (R) = (F E Fc (aS.T, F) = for ast E [k)) be a linear subspace of Fc. To simplify notation, we also set F Fa(k) = F21 (k)).

---

Proposition 2.3. The isomorphism c: VBa 7 Fa maps the function = EMgla AM OM to the set function defined by F(S)
AM оM. The inverse T- Fa + VB, of 4
MCId [
MnSH
given by the Möbius inversion formala + -Mcla-(MU)))MMMM F). particular, it holds
that ((VB, Fa(k) for all k S and dinn(Fa(k)) = dim(Vs, (k)) = Ei=1 (9) See also
Figure 1b for illustration of Proposition 2.3.
3 Neural networks conforming with the braid fan
For polyhedral complex P. we call a maxout neural network P-conforming, if the functions at all neurons are compatible with P. By this we mean that for all [e] and all coordinates j of the codomain of fi, the function πy o fi ...... o fi is compatible with P, where и the projection on the coordinate j. We denote by Mr the set of all functions representable by P-conforming rank-r-maxout networks. For the remainder of this article, we only consider the cases MB, and
M 8g
Lemma 3.1. The function x + max N0xx00,2 20.2......,.. 1) can be represented by Boo--confonning can be represented by
rank-r Lonk-r-maxonn r-maxout network if and only if the function r + Ba-conforingg rank-r-maoou network.
By computing r; maxima in each layer, we can compute the basis functions of Vo, (T r:) with Ba Ba-comnomiigg rank-r r-maxout network.
Proposition 3.2. For any rank vector E No, it holds that all functions in VB, M. ri) are representable by a Ba-conforming rank-r-maxout network.
Most of the paper is concerned with proving that .Mg, is contained in certain subspaces of VB.,
Let F% = Die(r) Fc be the r-fold direct sum of Fz with itself. In order to model the application of the rank-r-maxout activation function for a set function under the isomorphism Φ we define for (F1...., F+) Fz the function max F,] E Fc given by FF...F.... ((()),
=
For fr. E VR,, the function max ... [r] is Ba-compatible if taking the maximum does not create breakpoints that do not lie on the braid arrangement, that is, on every cone C of the braid arrangement, it holds that max(fi...... f+] = -fg for g E [r]. Next, we aim to model the compatibility with the braid arrangement for set functions. We call a tuple (Fi....,F; F,) e F conforming if for every chain (S, max ........ (S;) for all i E [n].. Then, the set C. S Fi of conforming tuples are exactly those tuples of CPWL functions such that applying the maxout activation function yields function that is still compatible with the braid fan as stated in the next lemma. Again, to simplify notation, we also set Cj Cr
So S S ç ... & Sn C [m] there is a E [r] such that
2/41-
Lemma 3.3. For (Fi....,FF) E (Fa)", the function max c conforming if and only if (Fi,...,Fr)
Ba-
Fr) E CJ In this case,
max ( + (Fi)......... (F,) = t (max
Fz))
The statement ensures that taking the maximum of the set functions is the same as taking the maximum of the piccewise-linear functions exactly for compatible tuples.
4 Doubly-logarithnic lower bound
In this section, we prove that for any number of layers E N, the function max (0, #1,... ... -igt-1)
not computable by a confooonngg rank-2-maxout neural network (or equivalently ReLU neural network) with é hidden layers. Due the equivalence of B3 and B. we will prove that M3 (f) S VB, (22 -1) for d > 21 +
First, we define an operation A on subspaces VB,, that describes rank-2-maxout layers that maintain compatibility with B,, For any subspace U C VB let A(U) S VB, be the subspace containing all
5

---

1234
abed
0. x1 $ x9
4
2
1
abe abd acd bed ab ad be
S 5
13
23
34
cd
0.5 mg $
3
a
#1 S S
0
505 105m
(b) Illustration of Proposi- tion 2.3. The coefficient of the function {2.4) in the lin- combination for F is given by (011,12244 F).
(c) Illustration of Lemma 4.5. F E Fx(2) n C. and F( e, d]) < 0, then there is a S (b, (bb,,,d) with F(S) since (adg =
2/ S 0
(a) The braid arrangement B.
Figure 1
the functions computable by a B.-conforming rank 2-maxout layer that takes functions from as input. Formally,
A(U) span(max(511 f2 E U, max f2) E Vs.)-
Clearly, A(U)) a subspace of A(U2) whenever U1 subspace U2. We recursively define
(U) (U)) This recursive definition allows to describe the of Ba-conforming network with E 2anxo2- layers Mag (f).
Lemma 4.1. It holds that (1) M (1) A(VB,(1) Vs, (2), and (2) for all & N, M (4) A(M (6 1)) AVV8 (1)).
Since it holds that max fe) max f1 f2] + f2. we can assume wlog that one of the functions is the zero map, as stated in the following lemma.
Lemma 4.2. holds that A(U) = (max / I max
ma,(0, (0, VB,).
To prove that (e) (0) (VB, (1)) is proper subspace of Vs, for 2 22 + 1, we perform a layerwise analysis and inductively bound ny depending on k such that A(VB, (k)) S Vs, (nz) for all N. In this attempt, translate this task the setting of set functions on Boolean lattices using the isomorphism Φ Recall that the pairs (Fi, F2) E C² are precisely the functions such that the maximum of the corresponding CPWL functions fi and is still compatible with B3, Moreover, it is easy to observe, that the pair (0, F) E F2 is conforming if and only if F is contained in the set
Cc = (F Fcl F(S) and F(T) do not have opposite signs for S T)-
Again, simplify notation, we also set Ca == C2141 and use the notation F+ max (0. F}. By slightly overloading notation, for any subspace U C Fc, let A(U) spanfF+ F Uc). Lemma 3.3 justifies this notation and allows us to carry out the argumentation to the world set functions on Boolean lattices, as we conclude in the following lemma.
Lemma 4.3. It holds that A()(U)) = +b ((U)) for all subspaces U C VB,- In particular, for any lattice L X, Y), it holds that A(Fc(1)) Fc(2).
In the following, we prove that A(Fz(()) C F2(k2 k)) by an induction on and Lemma 4.3 serves the base case.
Next, we describe properties of the vector space IR that will be useful for the induction step. Every sublattice of L of rank k + 1 is of the form [S, S TJ, where S n T = and [T] k + 1. For [X, into the sublattices [S, SUT for all C YTA,,
any T Y X, one can decompose resulting in the following lemma.
Lemma 4.4. Let C = XX Y] be lattice of rank n. Then, (1) for every T CYY X. holds that ax,Y E span(as.sur
Y (T) and (2) for every T C Y X with [T] k. it holds that as,SuT S'T E R ( for all S, [X,Y
See Figure for a visualization of Lemma 4.4. Lemma 4.4 implies that suffices to find T Y such that (Oss,Su,, F+) = 0 for all S S YY) T,, in order to prove that Fe(n 1). The idea of the

---

abed
abed
abed
obe
abd
aed
bed
abeiabd acd
bed
abeiabd acd
bed
ab
ac
ad
bc
bd
cd
ab
ac
ad
bc
bd
cd
ab
ac
ad
be
bd
ed
a
a
b
C
d
a
b
C
d
0
(a) dp..ddc
Ckg,be
Caa
(b) O. CxQ,bc
-ddbbed
(c) Oddbbod
Ola,abc
bl0.bed
-ig,abe
Figure 2: Illustration of Lemma 4.4. The solid line in Figure 2a, decomposes the lattice in [0, abe] U [d, abcd]. which implies that appabedd = Ogp,ab ad,obed- The dashed line further decomposes
[0, abc] = [0, be] U abe]. The 3 figures illustrate that as,su((.c) s'(bee E (2) for all S,S' S {a, d}.
abcde
abcde
d b a
e d
C
b
a
abe abd abe acd ace ade bed boe bde cde
abc abd abe
acd
ace
ade
bed
bee bdd
cde
ab ac ad ae be bd be cd
ce
de ab ac
ad
ae
be
bd
be
cd
ce
de
a
d
0
(a)
(b)
Figure 3: An illustration of the induction step. Let Y F (2) n Cg. If F(a) < and F(b) O, then follows that F(R) for all UU for S= ab and T = cde (Figure 3a). In particular, F E Fs,sLr(1) and thus, by Lemma 4.4, it holds that ur) for all 5' _ Y \
= 0, c- X,y] and
Figure 3b shows the decomposition of the lattice L = [X, Y] for == fc,, into the sublattices [S, TT] for all C (T. For every such sublattice we have that F E F(s,surr]()) n (s and thus by induction (assssU,, F+)) 0.
induction step is find a T of cardinality at least -1-1))(+-1111 such that F FiS.sUr (k-1) for all S C Y T. Then, applying the induction hypothesis each sublattice (S, S yields (ag,suT, F+) = O and hence F+ E Fz(n 1).
If E (k()), Lemma 4.4 implies that for any T" " YYX of cardinality k the value (ass, F.) independent S" C YY.T". Hence, in this case, it suffices to find a such that Fis.suz for only one S Y since is equivalent F E Fis,SuTT
1) for all S SYY Y
Given F E Fo(k) n Cg. it remains to find such S and T. We define the support of F by supp(F) = E F(S) & 0} and the positive and negative support by supp (FF)+ = {SEL) F(S) > 0} respectively supp (F) (S L F(S) < 0}. In particular, F E Ce implies that for X+ E supp (F) and X E supp (F), it holds that F F(R) = for all R x
Lemma 4.5 says that, given that the positive and negative support are not empty, we can always "push the elements X and X- in the support down in the lattice", that is, we can find elements in the supports that are of relatively low rank. See Figure le for illustration.
Lemma 4.5. Let L = [X, Y] be lattice of rank n. Let F E Fe(k) n Ce such that F E 0 and F E 0. Then, there are X =L*k supp" (F) and X Lex suppt as well as - E =Zznk O supp (F) and Y Czn-N n supp" (F).
Let S x then F E Cc implies that for Y S, we have that F(R) for all R E [S,SUT]. In particular, it holds that F Fis,sum (k 1). Thus, by Lemma 4.4, if F E Fo(k).
7

---

abcde
abcde
a
7
c
b
a
de abc abd abe aed jact ade bed bce
bde
cde
abc abd abe
acd
ace
ade
bed
bee bde cde
ab ac
ad rac) be bd
be (dd)
cc
de
ab ac
ad
ac
be
bd
be
cd
ce
a
d
a b
d
Figure 4: An illustration of Lemma 5.1 (left) and Lemma B.1 (right). If supp(F) S L2 Us. then can match every S L2 with T L3 such that F(T) F(S) which implies aoegea F+) = Esec, F+ (S) - Etec, F+(() = 0. If F(a) < 0 and F(bode) > 0, then it holds that (a'g F) = (01) F) = =.
it follows that F E Fist, 1) for all S' Y T'. Since |S] is at most 2h it follows by counting that if n 2 (A:2 + + 1), the cardinality of T is at least (k 1)2 (k 1. This allows to apply the inductions hypothesis to all sublattices [S", S" U UT] for S' C Y resulting in the following proposition. See also Figure 3b for an illustration of the induction.
Proposition 4.6. For k E N. let C = [X, be lattice of rank k² +++ 1 and F E Fe(k))nc. Then holds that (axX, ; F+) =
Applying Proposition 4.6 to every sublattice rank 122 + k + allows to sharpen the bound.
Proposition 4.7. Let C be a lattice and l E N, then it holds that A(Fz(R)) S F2(k? + k).
Translating this result back the CPWL functions and applying the argument iteratively for rank-2 m-axuut network, layer by layer, we obtain the following theorem.
Theorem 4.8. For a number of layers E E N, holds that Ma, (1) S VB, (22
Corollary 49. The function x + {0, ,., -1 (oppt. is not computable by a -Bccooformiin ReLU neural network with & hidden layers.
5 Combinatorial proof for dimension four
In this section, prove that the function max .I) cannot be computed by Bq- conforming rank-(2, (022)mmama 2amxuut networks or equivalently ReLU neural networks with hidden layers. This completely classfies the set of functions computable by Ba-conforming ReLU neural networks with hidden layers.
If L is a lattice of rank and F E F2(2) we know by Lemma 4.5, given that the supports of are not empty, that there are X L2 suupp* (F) and X E L2 supp (F). We first argue that in the special case of rank 5 we can even assume that there are X+ E L1 O supp (F) and X- Li Ssuppp (F). Then, with analogous arguments as in Section 4, we prove that F+ E Fc(4), resulting in the sharp bound for rank-(2, 2)- 2)-maxout networks.
If the positive support of a function every S E supp ( L2 there must be a 7 E supp (F) LL such that T' 2 S and F(S) < F(T) since (as,y, F) = 0. Applying the same argument to T. we conclude that F(S)
F2(2) Cc is contained in the levels C2 and C3. then for
F(T) and that there are no further subsets in supp* (F) that are comparable to S or T. Thus, we can match
the subsets S L2 with the subsets T E L3 such that F(S) F(T) and hence it follows that
(ax,v. F+) = = Se F*(() (S) (18)~Etea, Erec, F+) = 0. By symmetry, the same holds if supp (F) S
Le U L3. See Figure for an illustration. Following this idea, we state the lemma for more general case.
Lemma 5.1. Let L = [X,Y] be a lattice of rank and F E Fc(kk nCe with > 2k + 1. If there are i, [n]o such that supp+(F) C L, bo or supp (F) S L, Lz, then holds that F+ E Fc(n- 1)).

---

If there is X E L1 ssupp"(F) and X E C1 ssupp" (F), then it holds that (ax.y F+) = (ax+,y, F) (Figure 4 and Lemma B.1 in the appendix). Thus we can assume that there are X C1 n suupp*(F) (F) and X C1 Nsupp (F). By proceeding analogously in Section we prove the following theorem.
Theorem 5.2. holds that M2 VB, (4). In particular, the function x + {0, "0,,,,,..,,..... is not computable by a conforming ReLU neural network with 2 hidden layers.
6 The unimaginable power of maxouts
By Proposition 3.2, all functions in VB, (II ry) are representable by Ba-conforming rank-r- maxout network. In Section 5, we have seen that this bound is tight for the rank vector (2, In this section, we prove that this bound in general not tight by demonstrating that the function x + f0,, ]6 is computable by B cooffrrmingg rank-(3, - network.
Proposition 6.1. Let f1, E VB+(3)
(3) be the functions given by
fi = (1.2) + (1.4.5 + (1.6.7) + (2,4,6) + (2.577) f2 - (3,4,3) + (3.6.7) + (11244) + (1.2.5) + (1.2,6) + (12277)
Then holds that max f2] VB, (7) (8)
in) and 11 ...... 2 for [7] \ fi.....,a,, in} and note that the sublattices [12, 3]. [13, 2], [23, I}, [3, 12], [2, 13), [1, 23), [0, 123), [123, [7]] form a partition of [0, [7]].
Proof Sketch. Let Fi (fi) and F2 = ((2).. We write in ...in for {i1,-.. :.......pp]
We first show that on any of the above sublattices except [1, 23,, either F1 or F2 attains the maximum
on all elements of the sublattice and that for F == Fi F2 it holds that supp * *(F) S [1, 23)41661661
and (oro0,17)) F+) (0',2,3, 3, F) - F(146) - F(667) = -2 and thus F+ E Fe. FF( Then by looking at the partition into sublattices, we argue that F E C2 and thus by Lemma 3.3, we conclude that max f2] E VB, (6).
Hence max(fi. EMEM AmoM with Ap1 * and since all functions in (6) are com- putable by rank-(3, (3)) network, we conclude that +> f.1,..., Ø7) is computable by rank-(3, -maxout network or equivalently:
Theorem 6.2. The function x (0, (0, v6 is computable by a rank-(3, 3,
2) -maxout network.
Remark 6.3. One can check (e.g., with a computer) that + {0, Ii...., x6} is computable by rank-(3, (3, 2) 2)-maxout network with integral weights. This is particularly interesting in light of Haase et al. [2023], who prove [log, + 1)] lower bound for the case of integral weights and ReLU networks.
Conclusion and Limitations
Characterizing the set of functions that a ReLU network with fixed number layers can compute remains an open problem. We established a doubly-logarithmii lower bound under the assumption that breakpoints lie on the braid fan. This assumption allowed properties of the braid arrangement. In the specific case of four dimensions, we reprove the tight bound for confoormng networks of Hertrich al. [2023] with combinatorial arguments. Given that Bakaev et al. [2025b] showed that one can compute the maximum of 5 numbers with 2-layers, this implies that considering B -offofofrgg networks is a real restriction. While this indicates that the houbly-logarithma lower bound may not extend to all networks, our approach provides a foundation for adapting these techniques toward more general depth lower bounds, for example, by looking at different underlying fans instead of just the braid fan.
exploit specific combinatorial
Acknowledgments Moritz Grillo was supported by the Deutsche Forschungsgemeinschatt (DFG, German Research Foundation) - project 464 164109215 within the priority programme SPP 2298 "Theoretical Foundations of Deep Learning." " and by Germany's 's Excellence Strategy MATH+: The Berlin Mathematics Research Center (EXC-2046/1,, project ID: 390685689). Part of this work

---

was completed while Christoph Hertrich was affiliated with Université Libre de Bruxelles, Belgium, and received support by the European Union's Horizon Europe research and innovation program under the Marie Sklodowska-Curie grant agreement No 1053187-NeeuFxCo..
References
R. Arora, A. Basu, P. Mianjy, and Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations, 2018.
G. Averkov, C. Hojny, and M. Merkert. On the expressiveness of rational ReLU neural networks with bounded depth. In The Thirteenth International Conference on Learning Representations, 2025. URL https: pettps://openee /pppp//eeeeeee.ee////e/ee net / forum? ? i id=uREg3OHHLL
E. Bakaev, F. Brunck, C. Hertrich, D. Reichman, and A. Yehudayoff. On the depth of monotone relu neural networks and icnns. arXiv preprint arXtv:2505.06166 2025a.
E. Bakaev, F. Brunck, C. Hertrich, J. Stade, and A. Yehudayoff. Better neural network expressivity: Subdividing the simplex, 2025b. URL https: /ataaaiiirrgaaaaaaaea/aa/eeaaaae 2505. 14338.
D. Bertschinger, C. Hertrich, Jungeblut, ing fully connected neural networks is -R-oopllcte URL 71c31ebf577ffadd5faalll 5al.ffaad ras Conference. html.
Miltzow, and S. Weber. Train- In NeurIPS, 2023. nips ec wttpc///pppp http/appr__fieet files sailees/aper/2000 hasas//h////// Abst
M.-C. Brandenburg, G. Loho, and G. Montufar. The real tropical geometry of neural networks for binary classification. Transactions Machine Learning Research, 2024.
M.-C. Brandenburg, M. Grillo, and C. Hertrich. Decomposition polyhedra of piecewise linear functions. In The Thirteenth International Conference on Learning Representations, 2025. URL https:/ /tggs////pae http:///ppeeeeeeeeeeee net / forum? d
G. V. Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of Control, Signals and Systems, 2:303-314, 1989.
V. I. Danilov and G. A. Koshevoy. Cores of cooperative games, superdifferentials of func- tions, and the minkowski difference sets. Journal of Mathematical Analysis and Applica- fions, 247(1):1-14, 2000. ISSN 0022-247X. doi: 10. 10.1006/jmaa.2000067777 URL https: // //www.a... www.sssiiiiiciieeee rectt.dirreeee..
R. Eldan and O. Shamir. The power of depth for feedforward neural networks. In V. Feldman, A. Rakhlin, and O. Shamir, editors, 29th Annual Conference Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 907-940, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https: httpss://rrocceeee httpp/ppoceeens..///e////. mllr press/v49/ eldan1 html.
Ergen and M. Grillo. Topological expressivity of relu neural networks. In S. Agrawal and A. Roth, editors, Proceedings Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1,99-16422, PMLR, 30 Jun-03 Jul 2024. URL html.
https:/ /pppppeeeinggs../////ppp/ ..l..rr..............m.... m.l..press/ ///////4////////
V. Froese and C. Hertrich. Training neural networks is np-hard in fixed dimension. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023, Curran Associates Inc.
V. Froese, C. Hertrich, and R. Niedermeier. The computational complexity of relu network training parameterized by data dimensionality. Journal of Artificial Intelligence Research, 14:1775-1790, 2022.
V. Froese, M. Grillo, C. Hertrich, and Stargalla, Parameterized hardness of zonotope containment and neural network verification. arXiv preprint arXiv:2509.22846 2025a.
10

---

V. Froese, M. Grillo, and M. Skutella. Complexity of injectivity and verification of relu neural networks (extended abstract). In N. Haghtalab and Moitra, editors, Proceedings Thiryy Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 2188 2189. PMLR, 30 Jun-04 Jul 2025b. URL https: /proceed ngs. ml presss/s/ v291 / Frose25a html.
X. Glorot, A. Bordes, and Y. Bengio. Deep sparse rectifier neural networks. In G. Gordon, D. Dunson, and M. Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 315- 323, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR. URL https: https::/prrceeeeeeee //ppoceeeccc..s.../.. mlr. wtl.ppress/vll v15/ glorotlla lla. html.
S. Goel, A. Klivans, P. Manurangsi. and D. Reichman. Tight Hardness Results for Training Depth-2 ReLU Networks. In J. R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1-22:14, Dagstuhl, Germany, 2021. Schloss Dagstuhl Leiibii--eentrmm für Informatik. ISBN 978-3-95977-177-1. doi: 10.4230/LIPccssITSSS 2021.22 22. URL https: drops dagstuhl. de/entities: document /00. 4.300/LIPIII. ITCS 22.1.22.
J. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT Press, Cambridge, MA, USA, 2016. http:://wwtt deep 1 ea rn ngbook. .org.
earn
C. A. Haase, C. Hertrich, and G. Loho. Lower bounds on the depth of integral ReLU neural networks via lattice polytopes. In International Conference on Learning Representations, 2023.
C. Hertrich and G. Loho. Neural networks and (virtual) extended formulations. arXiv preprint arXiv:2411.03006, 2024.
C. Hertrich and I.. Sering. Relu neural networks of polynomial size for exact maximum flow computation. Mathematical Programming, pages 1-30, 2024.
C. Hertrich and M. Skutella. Provably good solutions to the knapsack problem via neural networks of bounded size. INFORMS journal computing, 35(5):1079-1097, 2023.
C. Hertrich, A. Basu, M. Di Summa, and M. Skutella. Towards lower bounds on the depth of relu neural networks. SIAM Journal on Discrete Mathematics, 37(2):997-1029, 2023. doi: 10.1137/22M4489332. URL https: / ort//0. 11.700.113/2221 01222149333 93332.
K. Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4: 251-257, 1991.
J. Huchette, G. Muñoz, T. Serra, and C. Tsay. When deep learning meets polyhedral theory: A survey. arXiv preprint a:Xiv:2305.00241, 2023.
K. Jochemko and M. Ravichandran. Generalized permutahedra: Minkowski linear functionals and URL https:
ehrbart positivity. Mathematika, 68(1):217-236, 2022. doi: / //londmathsoc. conlinelibraan wiley www/doi/////ccccccco abs 10. 1al112/mtkk 12122.
G. Katz, C. Barrett, D. Dill, K. Julian, and M. Kochenderfer. Reluplex: An efficient solver for verifying deep neural networks. In R. Majumdar and V. Kunčak, editors, Computer Aided Verification, page 97-117, Cham, 2017. Springer International Publishing. ISBN 978-3-319-63387- 9.
S. Khalife and A. Basu. Neural networks with linear threshold activations: Structure and algorithms. In K. Aardal and Sanità, editors, Integer Programming and Combinatorial Optimization, page 347-360, Cham, 2022. Springer International Publishing. ISBN 1--03--06901177
J. Li, J. Liu, P. Yang, L. Chen, X. Huang, and I.. Zhang. Analyzing deep neural networks with symbolic propagation: Towards higher precision and faster verification. B.-Y. E. Chang, editor, Static Analysis, page 296-319, Cham, 2019. Springer International Publishing. ISBN 978-3-030-32304-2.
Maragos, Charisopoulos, and Theodosis. Tropical geometry and machine learning. Proceed- ings of the IEEE, 10965):728-755 2021.

---

P. Misiakos, G. Smyrnis, G. Retsinas, and P. Maragos. Neural network approximation based on hausdorff distance of tropical zonotopes. In International Conference on Learning Representations. 2022.
G. Montúfar, R. Pascanu, K. Cho, and Y. Bengio. On the number of linear regions of deep neural networks. Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 2, NIPS' 14, page 2924-2932 Cambridge, MA, USA, 2014. MIT Press.
G. Montúfar, Y. Ren, and L. Zhang. Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums. SIAM Journal on Applied Algebra and Geometry, 6(4):618-649 2022.
A. Mukherjee and Basu. Lower bounds over boolean inputs for deep neural networks with relu gates, arXiv preprint arXiv: 1at:::111..00000 1.03073, 2017.
I. Safran, D. Reichman, and P. Valiant. How many neurons does it take to approximate the maximum? In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3156-3183, SIAM, 2024.
A. Schrijver. Theory of Linear and Integer programming. Wiley-Interscience, 1986.
R. Stanley. An introduction to hyperplane arrangements, pages 389-496. 10 2007. ISBN 9780821837368. doi: 10. 10.00090mm///0///0/
M. Stargalla, C. Hertrich, and D. Reichman. The computational complexity of counting linear regions in relu neural networks. arXiv preprint arXiv:2505.16716. 2025.
M. Telgarsky. benefits of depth neural networks. V. Feldman, A. Rakhlin, and Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1517-1539, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https:/ ptettt::s/ppccceedrreee http://s........eee/////////eeee
html.
J. L. Valerdi. On minimal depth in neural networks. arXiv preprint arXiv:2402.15315. 2024.
S. Wang and X. Sun. Generalization of hinging hyperplanes. IEEE Transactions on Information Theory, (111):4442-4443 4431, 2005.
L. Zhang, G. Naitzat, and L.-H. Lim. Tropical geometry of deep neural networks. In International Conference on Machine Learning, pages 5824-5832. PMLR, 2018.
G. M. Ziegler. Lectures on Polytopes. 038794365X. URL https://wwwtt ebook. de /3//e///roooutt331660888 /ttpt//////16000/eueeettr..r
Springer New York, May 2012. ISBN
[ieggler_eccuuree_____ooopp htmll. html.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claimed results proven in the main part appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We clearly and openly discuss the assumptions and limitations of our theorems in the introduction and the theorem statements.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

All assumptions are mentioned in the statements. All proof' are given in the main text or appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https: /ttsss////pp..//ee cc/
publ / guides/
des CoodeSuomi ssionn ceiionPoliien icy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. cc/ wttppccccppccccccccceeeccecccc.a pppppuplc//// /wwpi//us////////ee//eee/cecssse / (CodeSubmin commisssionP cesssoooolioooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /tt///neripppp cc hc/ppbblic/tthiicuuuueee
Answer: [Yes]
Justification: Purely theoretical research.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Purely theoretical research.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to
16

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Purely theoretical research.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No assets used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of the package should be provided. For popular datasets, papers sewiswwi hhoprodee thoode com/ dataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
17

---

Answer:
[NA]
Justification: No new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
18

---

Justification:
No non- ntanstandard LLM usage.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: : / ctterippss.c/ccooffreeeeeee / 2025/ LLM) for what should or should not be described.
19


Reviews:
[{"review_id": "GW4bsRsrgp", "reviewer": "Reviewer_LfjK", "summary": "The paper tackles the questionn of depth lower bounds for ReLU networks that are conforming with braid fan and gave a lower bound on how many ReLU hidden layers needed to exactly represent the maximum of d number in such a network: log log d.", "questions": "I do not have any questions.", "limitations": "Yes", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "As someone who is outside this field, I appreciate the motivation of the paper. Using lattice-theoretic arguments to derive a log log lower bound is elegant, even if most of the proof machinery was beyond what I can comfortably follow without spending more time on the background. \n\nI also found the maxout network section quite interesting. The fact that the natural generalization of the upper bound (based on the product of ranks) doesn't hold in general and that (3,2)-maxout can already represent max of 7 variables  was unexpected. It's a neat contrast to the tightness results for (2,2)-ranked networks.\n\nThat said, this is pretty far from the type of work I usually engage with, so I don’t have the right context to assess novelty nor significance within this area. But the writing was clear enough to follow the high-level structure, and the results seem carefully stated with appropriate proofs.", "was_revised": true, "final_justification": "I didn't have any concerns with this paper and keep my rating as is.", "rebuttal": "We thank the reviewer for carefully reading and evaluation our paper and for the positive and encouraging feedback."}, {"review_id": "pEftqGyfX3", "reviewer": "Reviewer_jBBb", "summary": "This paper studies the problem of determining minimal depth required for representing continuous piecewise linear (CPWL) functions exactly using ReLU neural networks. Specifically, it aims to resolve an open problem regarding the number of hidden layers needed for exact representation. The authors focus on neural networks conforming to specific polyhedral complexes, the braid arrangement, and provide novel theoretical results. The authors prove that $\\Omega(\\log \\log d)$ layers are required to represent the function $\\max\\{0,x_1,\\ldots,x_d\\}$. This is the first non-constant lower bound in this setting without weight restrictions. It also provides a combinatorial proof that two hidden layers are insufficient to compute  $\\max\\{0,x_1,\\ldots,x_4\\}$ under this model, and shows that a rank-(3,2) maxout network can compute $\\max\\{0,x_1,\\ldots,x_6\\}$, disproving a natural upper bound based on rank multiplication.", "questions": "1.Could one empirically confirm that a ReLU network with $l < \\log \\log d$ layers fails to approximate $\\max\\{0, x₁,...,x_d\\}$? How would you test this?\n2.Are there concrete examples where the Ω(log log d) lower bound is actually tighter for specific values of d or other specific cases?\n3.Is it possible to prove more generally that for certain rank vectors,  the expressivity of maxout networks indeed exceeds the bound given by $\\prod_i r_i$?", "limitations": "Suggestions:\nThis paper presents reliable theoretical analysis and establishes a novel lower bound related to the depth on the expressivity of ReLU networks within specific conditions. However, it lacks empirical verification, even on simple network architectures such as fully connected networks, which limits its significance. As such, it is difficult to consider it a theoretical contribution with substantial impact.\n\nIf the authors could provide experimental results to support the $\\omega(\\log \\log d)$ lower bound in a future revision, the paper would have strong potential for acceptance. Moreover, while the definition of $B_d$-conforming networks is theoretically well-defined and precise, the main claims would be significantly strengthened if the authors could empirically demonstrate—or at least provide some examples—showing that real-world neural networks tend to exhibit such structure, either inherently or approximately. Establishing this connection would enhance the practical relevance of the proposed lower bounds and make the results more compelling to a broader audience. Otherwise, the current submission resembles a combinatorial-algebraic exploration whose contribution falls short of the standards for acceptance at NeurIPS. \n\nFinally, although the main results of this paper are clearly presented, I could not find a summary or discussion of the work, particularly regarding its limitations, despite the authors' claim in the checklist that such limitations and conclusions are discussed. If I have misunderstood or overlooked this, I would appreciate clarification.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n\nThe $\\Omega(\\log \\log d)$ lower bound improves the previous constant-depth bounds.\nThis paper presents a clear description of its results with strict and reliable analytical techniques.\n\nWeakness:\nAbsence of empirical verification on its main results (even on vanilla examples of fully connected networks, see Suggestions).", "was_revised": true, "final_justification": "I have no other concerns.", "rebuttal": "We thank the reviewer for carefully reading and evaluation our paper and for the constructive feedback.\n\n> Weakness: Absence of empirical verification on its main results (even on vanilla examples of fully connected networks, see Suggestions).\n\nOur work is fundamental research on the expressive power of ReLU networks, and as such of theoretical nature. Many related previous papers published at top-tier ML conferences are purely theoretical papers, including the cited papers by Hertrich et al. 2023; Haase et al. 2023; Averkov et al. 2025. We agree that an empirical verification would be a nice add-on, but designing it in an insightful way would be nontrivial and is beyond the scope of our paper.\n\n> 1. Could one empirically confirm that a ReLU network with l < log log d layers fails to approximate max{0,x_1,...,x_d}? How would you test this?\n\nSee response above.\n\n> 2. Are there concrete examples where the Ω(log log d) lower bound is actually tighter for specific values of d or other specific cases?\n\nWe are not aware of tight examples. The best upper bound is singly-logarithmic in d. Nevertheless, our lower bound is the first proof of a non-constant lower bound, and as such a big step towards matching upper and lower bounds eventually.\n\n> 3. Is it possible to prove more generally that for certain rank vectors, the expressivity of maxout networks indeed exceeds the bound given by $\\prod_i r_i$?\n\nOur result can be stacked: by alternating $\\ell$ rank-2 and $\\ell$ rank-3 layers, one can compute the maximum of $7^\\ell$ numbers. We are, however, not aware of a more general construction of this type.\n\n> This paper presents reliable theoretical analysis and establishes a novel lower bound related to the depth on the expressivity of ReLU networks within specific conditions. However, it lacks empirical verification, even on simple network architectures such as fully connected networks, which limits its significance. As such, it is difficult to consider it a theoretical contribution with substantial impact. If the authors could provide experimental results to support the $\\omega(\\log \\log d)$ lower bound in a future revision, the paper would have strong potential for acceptance. Moreover, while the definition of B_d-conforming networks is theoretically well-defined and precise, the main claims would be significantly strengthened if the authors could empirically demonstrate—or at least provide some examples—showing that real-world neural networks tend to exhibit such structure, either inherently or approximately. Establishing this connection would enhance the practical relevance of the proposed lower bounds and make the results more compelling to a broader audience. Otherwise, the current submission resembles a combinatorial-algebraic exploration whose contribution falls short of the standards for acceptance at NeurIPS.\n\nSee above. We kindly disagree and think that the theoretical contribution alone is a significant contribution to the NeurIPS audience.\n\n> Finally, although the main results of this paper are clearly presented, I could not find a summary or discussion of the work, particularly regarding its limitations, despite the authors' claim in the checklist that such limitations and conclusions are discussed. If I have misunderstood or overlooked this, I would appreciate clarification.\n\nThanks for pointing this out. While we think that all assumptions, implications, and limitations are appropriately discussed around the theorem statements in the introduction, we are happy to include a specific paragraph summarizing these points. In such a paragraph we are also happy to discuss potential approaches for empirical verification, as you suggest."}, {"review_id": "Y1cW0HodZM", "reviewer": "Reviewer_7cCK", "summary": "This paper studies the theoretical question of how many layers a deep ReLU network requires to exactly represent any continuous piecewise linear function in d dimensions. The conjectured lower bound is log(d) and the present paper proves a conditional lower bound of log(log(d)). Specifically, the authors show that if the outputs of each neuron in the network are piecewise linear functions commensurate with a certain lattice, then the network requires a depth of at least log(log(d)) to represent the maximum of d numbers.\n\nThe authors also give a combinatorial proof a previous result which was proved using a large computed calculation and, interestingly, show that maxout networks don't satisfy the analogous depth lower bound.", "questions": "I think that there is a typo on line 70. It seems that the required depth of the network grows as $N\\rightarrow \\infty$, which doesn't make sense since the restriction on the weights is now weaker. Should the $\\log N$ be in the denominator?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper addresses a very interesting theoretical question, namely the minimal depth required for deep ReLU networks to exactly represent and CPWL function. Despite its simple statement, this problem has proved to be surprisingly technically challenging. The authors make very interesting partial progress toward this problem despite its apparent difficulty. In addition, the results on general maxout networks are highly interesting and suggest that something is special about the ReLU network problem.\n\nWeaknesses: The main theorem proved in the paper is conditional on the structure of the neural network, so a complete solution to the desired problem is still missing. However, the exceptional difficulty of this combinatorial problem makes this perhaps inevitable.", "was_revised": true, "final_justification": "This is a technically interesting and solid paper. The authors have answered all of my questions and I have no concerns. I stick with my original assessment of accept.", "rebuttal": "We thank the reviewer for carefully reading and evaluation our paper and for the positive and encouraging feedback. \n\n> Weaknesses: The main theorem proved in the paper is conditional on the structure of the neural network, so a complete solution to the desired problem is still missing. However, the exceptional difficulty of this combinatorial problem makes this perhaps inevitable.\n\nWe agree with your estimation of the situation.\n\n> I think that there is a typo on line 70. It seems that the required depth of the network grows as $N\\rightarrow \\infty$, which doesn't make sense since the restriction on the weights is now weaker. Should the $\\log N$ be in the denominator?\n\nYes, this is a typo, d and N should be exchanged in the expression. Thanks for pointing it out."}, {"review_id": "5L2lsxUGtQ", "reviewer": "Reviewer_AdUU", "summary": "This work studies the expressive power of multi-layer perceptrons with ReLU activation function. They show a lower bound on the depth $l$ required to exactly express the maximum function in dimension $d$, ie the function $max(x_1, ...x_d)$. Their main result establishes that the depth of such network must be at least $l \\geq \\lceil\\log(\\log(d))\\rceil$. Additionally, they show that a natural generalization of a conjecture on the expressive power of ReLU networks to any rank of maxout network is not true by providing a counter example for the max of 7 numbers.", "questions": "- This work focuses on exact representation of the target function. Have you thought about a similar lower bound on the depth when allowing for some approximation error with the target?\n- At lines 107-109 you state that you disprove the conjecture with a counter example in dim 6. Do you think that the conjecture could still hold asymptotically with the same bound up to constants?\n- It would be valuable to add a conclusion section to wrap-up your results.\n- Finally, I noticed some lines which I think may contain typos or unclear sentence:\n\n-- line 67: what does \"integral\" weights\" mean?\n\n-- line 89-90: could you link to the lemma or proposition that proves the \"observation is that the set of functions that are representable by a B0d-conforming network forms a finite-dimensional vector space\"?\n\n-- line 110-112 Does it constitues a matching upper-bound to your lower bound? If yes, it could be nice to highlight it.\n\n-- line 165: \"fan\" was not defined?\n\n-- line 179: do you denote $F = \\Phi \\circ f$ here? If yes it would be good to add it.\n\n-- line 190: Do you denote $[n]_0 = [n] \\bigcup \\{0\\}$?\n\n-- line 194: what is the * in $(R^L)^*$?\n\n-- line 199: if I understand well $\\sigma_M$ is a function, and hence should be $F(S)$. But don't we expect $F(S)$ to be scalar?\n\n-- line 226: should you add $S_n\\subset [d]$?", "limitations": "The authors discuss adequately the limitations of their work. This is a theoretical work, which does not seem to present obvious negative societal impact.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The motivation of this work is clearly motivated: the expressive power of depth of ReLU networks is not fully understood yet and subject to numerous ongoing works.\n- The contributions are new and interesting: the main result provides a new non-trivial depth lower bound for expressing any piecewise linear function using ReLU networks.\n- The paper writing is clear and formal, and I did not notice any major flaw.\n\n**Weaknesses**\n- This paper is *extremely* heavy in notations which makes it very hard to follow. I acknowledge that the notations are overall clearly defined and I do not immediately know how to simplify the notations but it really makes the reading hard currently.\n- The setting of this work is quite restrictive: it applies to a single activation function and focuses on a setting which requires *exact* representation of the target function.", "was_revised": true, "final_justification": "I believe this work should be accepted: the main contribution of proving a lower bound on the depth of a ReLU network to approximate the max function is new and a good contribution. Regarding the absence of experiments raised by a reviewer, I believe that this work is theoreticaI and does not require experiments, especially given the nature of the results proved (requiring exact approximation is a hard requirement to impose in experiments I believe).\n\nNote that I could not carefully check all math details in the proof, which is extremely heavy in notations. The authors explained some of them in the rebuttal and I believe that adding some explanation/intuition in the notations could strengthen the paper.", "rebuttal": "We thank the reviewer for carefully reading and evaluation our paper and for the positive and encouraging feedback. \n\n> This paper is extremely heavy in notations which makes it very hard to follow. I acknowledge that the notations are overall clearly defined and I do not immediately know how to simplify the notations but it really makes the reading hard currently.\n\nThanks for sharing this impression. We are happy to implement any concrete suggestion on how to improve this issue, including your comments below.\n\n> The setting of this work is quite restrictive: it applies to a single activation function and focuses on a setting which requires exact representation of the target function.\n\nOur results can be transferred to any activation function that is piecewise linear (including ReLU, leaky ReLU, maxout, ...). You are correct in that they don't apply to smooth activation functions. In our current version, our results do not imply anything for approximation, but we see the exact representations as a necessary base case, that is already substantially non-trivial.\n\n> This work focuses on exact representation of the target function. Have you thought about a similar lower bound on the depth when allowing for some approximation error with the target?\n\nSee above.\n\n> At lines 107-109 you state that you disprove the conjecture with a counter example in dim 6. Do you think that the conjecture could still hold asymptotically with the same bound up to constants?\n\nIt could be either way, we do not want to make a guess at this point.\n\n> It would be valuable to add a conclusion section to wrap-up your results.\n\nWe will do this, see also our discussion with Reviewer jBBb.\n\n> line 67: what does \"integral\" weights\" mean?\n\nIt means that all weights are in $\\mathbb{Z}$.\n\n> line 89-90: could you link to the lemma or proposition that proves the \"observation is that the set of functions that are representable by a B0d-conforming network forms a finite-dimensional vector space\"?\n\nThis is implied by Prop. 2.2. We are happy to add such a reference.\n\n> line 110-112 Does it constitues a matching upper-bound to your lower bound? If yes, it could be nice to highlight it.\n\nUnfortunately, the problem setups are slightly different, so while morally the two bounds match, this is not a formal match.\n\n> line 165: \"fan\" was not defined?\n\nWe will add a definition: A fan is a polyhedral complex in which every polyhedron is a cone anchored at the origin.\n\n> line 179: do you denote $F=\\Phi\\circ f$ here? If yes it would be good to add it.\n\nNot exactly: the meaning is that $\\Phi(f)$ is defined as the set function $F$ that sends $S$ to $f(1_S)$. We will make this clearer in the final version.\n\n> line 190: Do you denote $[n]_0 = [n]\\cup 0$?\n\nYes\n\n> line 194: what is the * in $(R^L)^*$?\n\nIt is a standard notation for the dual space, the set of linear functions mapping from $R^L$ to $R$. We will add an explanation.\n\n> line 199: if I understand well $\\sigma_M$ is a function, and hence should be $F(S)$. But don't we expect $F(S)$ to be scalar?\n\nThis is indeed a typo. $F(S)$ is a scalar, as you say. The formula should not contain the $\\sigma_M$, it should just be a linear combination of the $\\lambda$s.\n\n> line 226: should you add $S_n\\subset[d]?\n\nYes, this can be added here.\n\n> Paper Formatting Concerns: The font used seems different than the usual Neurip format font.\n\nYou are correct and we are sorry about this. By accident, we loaded the package lmodern, which changes the font. But our font takes up more space than the usual NeurIPS font, so we do not overshoot the page limit when changing it back to the NeurIPS font. In contrast, we will even have a little bit of additional space for the final version."}]

Author rebuttal:

Meta-review: The reviewers were overwhelmingly positive, with all four reviewers recommending acceptance. The paper is technically solid, clean, clearly written, and addresses a highly relevant theoretical question. Since the result is neat and closes a research path, I'd recommend the paper for an oral.
The minor issues raised by the reviewers, such as typos and notation clarity, were addressed by the authors and do not detract from the overall quality of the work. For these reasons, I recommend acceptance.
Decision: Accept (oral)