Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification
Authors: Yuhao Mao
Yani Zhang
Martin Vechev
Venue: ICLR 2026 Poster (2026)
Keywords: certification
convex relaxation
theory
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We show that multi-neuron relaxations alone may never be complete verifiers, and the conditions required to enhance them to be complete.

Abstract: Neural network certification methods heavily rely on convex relaxations to provide robustness guarantees. However, these relaxations are often imprecise: even the most accurate single-neuron relaxation is incomplete for general ReLU networks, a limitation known as the *single-neuron convex barrier*. While multi-neuron relaxations have been heuristically applied to address this issue, two central questions arise: (i) whether they overcome the convex barrier, and if not, (ii) whether they offer theoretical capabilities beyond those of single-neuron relaxations.
In this work, we present the first rigorous analysis of the expressiveness of multi-neuron relaxations. Perhaps surprisingly, we show that they are inherently incomplete, even when allocated sufficient resources to capture finitely many neurons and layers optimally. This result extends the single-neuron barrier to a *universal convex barrier* for neural network certification. 
On the positive side, we show that completeness can be achieved by either (i) augmenting the network with a polynomial number of carefully designed ReLU neurons or (ii) partitioning the input domain into convex sub-polytopes, thereby distinguishing multi-neuron relaxations from single-neuron ones which are unable to realize the former and have worse partition complexity for the latter.
Our findings establish a foundation for multi-neuron relaxations and point to new directions for certified robustness, including training methods tailored to multi-neuron relaxations and verification methods with multi-neuron relaxations as the main subroutine.

Published as a conference paper at ICLR 2026
EXPRESSIVENESS OF MULTI-NEURON CONVEX RELAXATIONS IN NEURAL NETWORK CERTIFICATION
Yuhao Mao Yani Zhang & Martin Vechevi
'Department of Computer Science
*Department of Information Technology and Electrical Engineering
ETH Zürich, Switzerland {yuhao. mao, www.miarnnnni.m wer.tiin.veeeeeeeintt www....eteetcccc ch, yanizhang@mins.cm ee.
ABSTRACT
Neural network certification methods heavily rely on convex relaxations to pro- vide robustness guarantees. However, these relaxations are often imprecise: even the most accurate single-neuron relaxation is incomplete for general ReLU net- works, a limitation known as the single-neuron convex barrier. While multi- neuron relaxations have been heuristically applied to address this issue, two cen- tral questions arise: (i) whether they overcome the convex barrier, and if not, (ii) whether they offer theoretical capabilities beyond those of single-neuron relax- ations. In this work, we present the first rigorous analysis of the expressiveness of multi-neuron relaxations. Perhaps surprisingly, we show that they are inherently incomplete, even when allocated sufficient resources capture finitely many neu- rons and layers optimally. This result extends the single-neuron barrier to a uni- versal convex burrier for neural network certification. On the positive side, we show that completeness can be achieved by either (i) augmenting the network with a polynomial number of carefully designed ReLU neurons or (ii) partitioning the input domain into convex sub-polytopes thereby distinguishing multi-neuro relaxations from single-neuron ones which are unable to realize the former and have worse partition complexity for the latter. Our findings establish foundation for multi-neuron relaxations and point to new directions for certified robustness, including training methods tailored to multi-neuron relaxations and verification methods with multi-neuron relaxations as the main subroutine.
INTRODUCTION
Neural networks are vulnerable to adversarial attacks (Szegedy et al., 2014), where a small perturba- tion the input can lead misclassification. Adversarial robustness, which measures the robustness of a model with respect to adversarial perturbations. has received much research attention in recent years. However, computing the exact adversarial robustness of general neural network is coNP- hard (Katz et al., 2017). while adversarial attacks (Carlini & Wagner, 2017: Tramèr et al., 2020) that try to find an adversarial perturbation can only provide a heuristic upper bound on the robustness of the model. To tackle this issue, neural network certification has been proposed to provide robustness guarantees. the context of robustness certification, the task boils down to providing a numerical bound on the output of a neural network for all possible inputs within given set. A central property of certification is completeness, which requires the method to provide exact bounds for all cases.
Certification methods based on convex relaxations can provide efficient certification by computing an over-approximation of the feasible output set of a given network, with certain trade-off on the precision (Wong& & Kolter, 2018; Singh al., 2018; Weng et al., 2018; Gehr al., 2018; Xu et al., 2020). They can also be incorporated in the training process to deliver models that are easy to certify (Shi et al., 2021; Müller et al., 2023; Mao et al., 2023; 2025; Palma al., 2024; Balauca et al., 2025). Due to the central role of convex relaxations in the context of certified robustness, is crucial understand their theoretical properties.
"Equal contribution

---

Published as a conference paper at ICLR 2026
The Single-Neuron Convex Barrier Single-neure neuron relaxations widely studied due to their popularity and simplicity. However, the single-neuron convex barrier (Salman et al., 2019; Palma et al., 2021) prevents single-neuron convex relaxations from providing exact bounds for general ReLU networks. Baader et al. (2024) further show that even the most precise single-neuron relax- ation, namely Triangle (Wong & Kolter, 2018), cannot exactly bound any ReLU network encoding the "max" function in IR? To overcome this limitation, multi-neuron relaxations have been proposed (Singh et al., 2018; Müller al., 2022: Zhang al., 2022), achieving higher empirical precision. Yet, their theoretical properties remain largely unexplored. In particular, it is unclear whether multi- neuron relaxations are able to provably bypass the convex barrier and provide complete certification for general ReLU networks, if given sufficient resources. A key challenge is that, unlike the single- neuron setting- where proving barrier only requires exhibiting a concrete network for which the most precise single-neuron relaxation fails-a multi-neuron relaxation can always be made more precise by allocating more resources, thus this question cannot be answered via empirical studies. Moreover, solving multi-neuron relaxations is significantly more computationally expensive, mak- ing empirical exploration of their limits difficult.
This Work: Quantifying the Expressiveness and Completeness of Multi-Neuron Relaxations In this work, we formalize the notion of multi-ncuron relaxations and rigorously investigate their ex- pressiveness. We address two central questions: (i) whether they overcome the single-neuron convex barrier, and if not, (ii) whether they offer fundamental advantages over single-neuron relaxations.
Key Contributions
We prove that multi-neuron relaxations are inherently incomplete for general ReLU networks, even provided with sufficient resources capture all neurons in each individual layer optimally ($3). This incompleteness result is extended to relaxations involving finitely many layers and networks with non-polynomial activations, e.g., tanh, establishing a universal convex barrier for neural network certification with convex relaxations ($4).
We prove that with gquivalence-preservve network transformations, layerwise multi-neuron relaxation can be complete verifier, which impossible for any single-neuron relaxation. This shows that the expressivity of general ReLU networks is preserved under multi-neume nellinneeronnn relax- ations: every continuous piecewise linear function can be encoded by a network that is exactly bounded by some layerwise multi-neuron relaxation ($5.1). This stands in sharp contrast the impossibility result established for single-neuron relaxations (Baader et al., 2024): in a case study, we demonstrate that a simple network implementing the "max" function [0, 1]d can be exactly bounded by a cimensson-innependenl multi-neuron relaxation far weaker than required by the general theorem.
We analyze the properties of multi-neuron relaxations under convex polytope partitioning and show that their partition complexity required achieve complete certification is strictly lower than that of single-neuron relaxations ($5.2).
We discuss the practical implications of the above theorems, including training strategies tai- lored to multi- neuron relaxations and verification methods with multi-neuron relaxations as the main subroutine ($6).
Aside from the prior works mentioned, an extended discussion of related work can be found in $A.
2 BACKGROUND
2.1 CONVEX RELAXATIONS FOR CERTIHICATION
Given a function f Rdd Rd and a compact domain X C Rd, we denote the graph of the function f(=)) x E X} by f[X]. The certification task boils down to computing the upper and lower bounds of f(X) == {f(r)< X). in order to verify that these bounds meet certain requirements, e.g., adversarial robustness. To this end, convex relaxations approximate f[X] by conditioned con- vex polytopes S C dd+d' satisfying S 2 f[X], where the condition depends the concrete relaxation method. We then take the upper
vs +
12
820
Figure I: Triangle relaxation of ReLU with input E [ [[-1,1]
2

---

Published as a conference paper at ICLR 2026
and lower bounds of S (projected onto R=) as over-approximation of the bounds of f(X). We
denote by C(x(1) ....., (()) a set of affine constraints the variables x(1, x (()) Its feasible set is the intersection of the feasible set of each included affine constraint. When context is clear, we
use C to refer to both the affine constraint set and its feasible set; for two constraint sets C1 and C2, we use C1 A C2 to denote the combination of the constraints in C1 and C2, i.e., their feasible sets are intersected. For an affine constraint set C(x,, y) dependent on æ, we denote by T= the projection of the feasible set onto the æ-space, which can be computed by. e.g., applying the "ourier-Motzkin algorithm to remove the variables in C. other than a. We assume the domain X be convex poly- tope, e.g,, Los neighborhoods of a reference point, which is the common practice in certification. Such convex sets S can be represented by a set of affine constraints C(x, f(z)) as well. For exam- ple, consider the ReI.U function y p(x) max 0) on the domain X = [-1.]] represente by Co = (* 2 11 x S 1}. One possible convex relaxation is the Triangle relaxation (Wong & Kolter, 2018), represented by the affine constraints C1 {y 2 z, y 0,y S {xxxx)) Figure illustrates
this, where the black thick line represents f f[X] and the colored area stands for S. In this example,
T (Cu A C2) [-1, and Ty A C1) [0, 1].
2.2 RELU NETWORK ANALYSIS WITH LAYERWISE AND CROSS-LAYER CONVEX RELAXATIONS
Consider a network' f = WL o po....... po W1 where W are the affine layers for j E [L] and P is the ReLU function. Denote the input variable by æ. the first layer by ((1) = Wi (z)) the second layer by u22) := p(u(1)), and so on?. Assume the input convex polytope X is defined by the affine constraint set Co(æ)). A layerwise convex relaxation works as follows. Given the input convex polytope' (ar), apply the convex relaxation to the first layer (1) (zz to obtain a set of affine constraints C₁ (1)) Then, based on a (Cu A C1), apply it to the second layer (2) = p()( to obtain set of affine constraints C2(v(1), e2)).. Proceeding by layer, we obtain affine constraint sets ()(i() ,.(++1), for j E [2T.-2] All the constraints pertain to single layer and no explicit constraint across layers is allowed, e.g.. C(æ,, v(22-1)) would not appear explicitly in the above procedure. Finally, we combine all constraints to get C = Co(æ)) A Ci (ar, (()) A A C21-1(((2L--)) ((2(-1)) and solve C to obtain the upper and lower bounds of the output variable (2L-1), These bounds are then used to certify the network.
In contrast to layerwise relaxations which consider every layer separately, cross-layer relaxations (Zhang et al., 2022) include constraints involving multiple consecutive layers. Concretely, let r E N+, for the network/ f above, a cross-r-layer relaxation processes the first r layers jointly and returns a set of affine constraints C₁ (Iz v(1), "")....,,f e()). Proceeding again by layer, we obtain affine constraint sets C2(v(() ..... ...., v(+tr)),.. ..... C2L-, (v ...., (22,-1)), and the intersection of all feasible sets is solved return bounds on (21-1)) We denote by P, the convex relaxation that always returns the convex hull of the function graph of every adjacent layers on an input convex polytope to the considered layers, which is, by definition, the most precise cross-r-layer convex relaxation, and likewise denote by P, the most precise layerwise (cross-l-layer) convex relaxation. In other words, given feasible set S in the (+)) space, P, returns constraint set equivalent to the convex hull of (v)())
e(++r)) | v(() E S} for all i. All cross-r-layer relaxations cannot be made more precise than P, by definition.
For a set H. we denote its convex hull by cony (H). For a compact set X C Rd. we denote by min X the d-dimensional vector whose elements are the minimum value of points in X on each coordinate. For example, min [0, 1 = 0j. Given a relaxation method P, a network f. and an input set X, we denote by {f P, X) the vector of lower bounds on each dimension of f computed by with respect to X; likewise we denote by u(f. PP X) the upper bounds. In this work, we assume linear programming is employed to solve the constraint sets generated by the convex relaxation methods, and it always returns optimal bounds based on the constraints, without indicating the existence or nonexistence of a feasible point attaining the bounds. A glossary of all notations is detailed in SB.
Unless explicitly stated otherwise, the term network is understood ReLU neural network. A We consider affine transformation and ReI.U as separate layers throughout the paper. We always assume the input convex polytope is non-empty.
3

---

Published as a conference paper at ICLR 2026
2.3 LINGLE-NEURON AND MULTI-NEURON RELAXATIONS
Within the framework of layerwise convex relaxations, the optimal constraint set affine layer = Ax + is always C( y) = (Ax + S 0, Ax b b-2 y S 0). which translates to the equality y Ar. b. Such constraints introduce no loss of precision, and thus adopted by most convex relaxation methods. Concretely, other than IBP, all convex relaxation methods considered in this paper use the exact constraints on affine layers. The core difference between relaxation methods is how they handle the ReLU function. Single-neuron relaxation methods process each ReLU neuron separately and disregard the interdependence between neurons, while multi-neuron relaxations consider a group of ReLU neurons jointly. For the vector æ, let æ; denote its i-th entry and xy be the vubtvrctor of x with entries corresponding to the indices in the set I. For the ReLU layer y p(z=) with E Rd, the constraint sets computed by single-neuron relaxations are of the form C(,, y:) with i E [d]. In contrast, multi-ncuron relaxations produce constraints of the form C( )1,)) with 41, 12 S [d]. We only consider multi-ncuron relaxations that are at least as precise as single-neuron relaxations, i.e., for every i E [d], there exist /, 12 such that i E J 0 Tz.
Singh et al. (2019a) propose the first multi- relaxation called l- ReReLU. For the ReLU layer = p()), it considers at most k unstable neurons jointly- we call neurons that switch their activa- tion states within the input set as unstable, otherwise we call them stable- and returns C(x,, yr), with / C [d]. [7| S k. However, k-ReI.U reduces to the single single-neuron Triangle relaxation in some cases (see the case study in $5.1), thus we consider stronger multi-neuron relaxation which only re- stricts the number of output variables in the constraints, allowing Cax,, y) to be of the form C(x, yr) al. (2020). We denote
with 1 S [d], |4| I k. Similar tricks are also used in Tjandraatmadja this special multi-neuron relaxation as Ma. and assume it always computes the convex hull of (x. p(xr)), while only one index set I is allowed per ReLU layer. We emphasize that M₁ is allowed to consider unstable and stable neurons together, while R-ReLU only considers unstable neurons and the corresponding inputs jointly, thus MM is more precise even when k-ReLU also computes the convex hull of the considered variables. Neurons that are not considered by a multi- neuron relaxation are processed by the single-neuron Triangle relaxation. For ReLU networks of width more than k, MA. as a layerwise relaxation, is equivalent the most precise layerwise relaxation P1. We note that Pp is a multi-neuron relaxation by definition, for every r E N A toy example is provided in $C to further illustrate the concepts introduced above. We refer inter- ested readers to Baader et al. (2024) for more detailed introduction to concrete single-neuron and multi-neuron relaxation methods.
LAYERWISE MULTI-NEURON INCOMPLETENESS
In this section, establish the incompleteness result for layerwise multi- relaxations. We consider Pi, the most precise layerwise multi-neuron relaxation by definition, and show that it is incomplete, and the relaxation error be arbitrarily large. This result naturally extends to all layerwise ReLU network verifiers, as they cannot be more precise than Pt.
We start with simple example to demonstrate the idea. Consider the input set X = 1-, and the ReLU network f = f' f'opo Wi, where I' = p(æ; p(1 21) + p(0) - + 2x2) encodes the function f'(11,, 202 [00- 11-1 111 2-2-211 11, R.2 and Wi is the affine transformation Wi (x)
(=1 11.5
0.5
x +
for x E R Let
((W((x)) As illustrated in Figure 2, the affine
1.5
0.5
layer W2 and the subsequent ReLU transform the input set into the polytope union U {uj > 0, u2 2 O, u1 + u2 S 1) S 4n 2. 0} U O1 u2 S 2, 41 0}. The minimal value of f on X is thus min f(X) min ('( = However, we will show e( X) S 0. hence it impossible to obtain the exact lower bound. To see this, consider the specific point u² = (1, On one hand, since P1 is a sound convex relaxation, the affine constraints obtained on the layer p and W1 characterize a convex superset of U, thus superset of the convex hull of U which contains u.. On the other hand, since P1 prohibits affine constraints across nonadjacent layers, the affine constraints induced by the subsequent layers f' cannot remove u" from the feasible set (formalized later in Lemma 3.1). Hence, the returned lower bound satisfies E(f, PI, I f'(")) 0.
We observe a general phenomenon from the example above: for a ReLU network f = f2 o fi. where fi and fa are its subnetworks, if (1) fi maps the input set set U whose convex hull is its strict
4

---

Published as a conference paper at ICLR 2026
Wits)
Blue area shows how the input box transforms under W1 and ReLU; shaded area is the feasible set computed by Pl.
Figure 2:
superset, that is, conv(U) \ U * 0, and (2) the subsequent network fo attains its extremal values some point E conv(U) U, then layerwise convex relaxation method cannot provide exact bounds on ff for the given imput set. This reveals a fundamental limit of layerwise multi-neurge verifiers: there exist networks for which verifier can provide exact bounds. In other words, all layerwise multi-neuron relaxations are incomplete, regardless of how many neurons a single layer are jointly considered. Further, as we shall show next, the relaxation error can be unbounded. The rest of this section is devoted to formalizing and proving the ideas above.
We first establish two lemmata characterizing properties of layerwise convex relaxations. Lemma 3.1 below states that affine constraints induced by layerwise convex relaxations on some hidden layer cannot reduce the feasible set on its preceding layers.
Lemma 3.1. Let L E N and let X be a convex polytope. Considera a ReLU network J o..... f1- Denote the variable of the j-th hidden layer of f by v0)), for j E [T. 1], and the variable of the output layer by e(L) For < set of all constraints obtained by applying Pi to the first and L layers of respectively. Then, Toto (2x o()),.... ))))) = Te, (C2( v1)) (())).
L, let C1 (ax, e ...... (()) and Cz(x, v(").. ....... v(() be the
The proof is based on the definition of layerwise convex relaxations and is straightforward: we defer it to $E.1. Lemma 3. shows that the constraints induced by the deeper-than-i layers do not affect the feasible set of (()) Despite the simplicity, this observation leads to Lemma 3.2, which states that the bounds computed by Pi cannot be better than splitting the network into two subnetworks some hidden layer and then computing their convex hulls separately.
Lemma 3.2. Let X be convex polytope and consider network 1 == f2 fi, where fi and f2 are its subnetworks. Then, PI. s min((2(conv((i(X)) and max(fa(conv(iiX))
The proof of Lemma 3.2 as follows: for fi, the best approximation that a convex relaxation can attain is the convex hull of the output set of fi; consequence of Lemma 3.1, when processing fe, Pi will take the whole set conv (fa(f)()) into account. Thus, the best bound that P1 can achieve no better than bounding f2 (conv (So (X)(X)).. The detailed proof of Lemma 3.2 is deferred to $E.2.
Now we are ready to show that the layerwise multi-neuron relaxation Pi is incomplete.
Theorem 3.3. Let d E N and let X be convex polytope in Rd. For every 0 < T < cc, there exists ReLU network f d E such that {(f, P1, < min f(X) T, and ReLU network 9: R.d + R such that ugg P1.X) 2 max (xx)(XX++ +T.
The proof is deferred $E.3. Informally, we construct a network such that the convex hull of the output set of the first subnetwork is strict superset of the output set, and the subsequent layers attain its extreme values at points outside the reachable set. The construction is similar to the example provided at the beginning of this section. Then, we can scale the weights of the output layer by large enough constant to make the relaxation error arbitrarily large.
Theorem 3.3 is an unfortunate result for layerwise multi-neuron relaxations. It shows that every layerwise convex relaxation has a failure case where the relaxation error is arbitrarily large, though calculating them, e.g., Pi, is already computationally expensive for large networks.
4 CROSS-LAYER MULTI-NEURON INCOMPLETENESS
For networks of L layers, Pr. can provide exact bounds as it computes the convex hull of the input- output function. Since P, is proven incomplete in $3, the natural question is whether there exists
5

---

Published as a conference paper at ICLR 2026
some E N+ for P. to be complete. Instead of fixing r to be constant, consider this question in its full generality by allowing r to depend on L and ask: does there exist a E (0,1) such that P (max(I.[ot.)) provides exact bounds for all networks with L layers? Our result is rather surprising: no such a exists. This directly implies the incompleteness of P, for all r E N Thus, the commonly believed "single-neuron" barrier of convex relaxations is actually a misnomer, as it extends to every multi-neuron convex relaxation, and should be renamed the universal convex barrier.
The key insight behind our result is that for every fixed a E (0, 1), the cross-layer relaxation P [a)x shares similar limitations to P1 for certain networks. Formally,
d,, Lemma 4.1. Let E (0, 1), d, d', Ln L2 E N+. and X C Rd be convex polytope. For every
L -layer network fi : IRd + Rd and Ln-layer network f2 Rd" + R. there exist I, L1 L2 and a L-layer network f such that (i) f(x)= = fo o fz(),, for Va E X, and (ii) E(f, P (mmx((1(aZ))) X) S min fiinf((con) fz(conv(fi (Xi())) and uff. P L.) X) 2 max fa(conv(f((X)))
Lemma 4.1 extends Lemma 3.2 to cross-layer convex relaxations. The idea behind its proof is similar to the pumping lemma: the original network /2 o f1 is pumped by adding dummy identity layers between fi and [2. While cross-layer relaxations allow direct information exchange across layers to improve bound preciseness, the pumped dummy layers block this information exchange, thereby disabling the relaxation from providing exact bounds. The formal proof is deferred 1F.1. We note that, however, only direct information exchange between fi and f2 is blocked by this construction, and the cross-layer relaxation is free to provide exact bounds for both fi and fz, which is easily done by P (max((.(of.)) when a - 1 for large enough L. This is also the key difference between layerwise and cross-layer relaxations. Nevertheless, merely blocking this information is sufficient to make the relaxation incomplete, as shown in Theorem 4.2.
Theorem 4.2. Let d E N and let X Rdd be convex polytope. For every a 10,1) and every constant T > 0, there exists a network ʃ : Rd - I such that E(,, P Pmss((, X) S min f(X) T, and a network Rd + I such that u(g, P mmxx(I.La..)) X) 2 max g(X) + T.
The proof based on the construction when proving Theorem 3.3. Specifically, we take the con- struction therein and apply Lemma 4.1 to obtain deeper network that has the same semantics. Then, since the convex hull and the exact output set of fi do not completely overlap, we use similar ar- gument in the proof of Theorem 3.3 to show that the P (lax((1|aaz) relaxation is incomplete for every a E (0, 1). The formal proof is deferred to $F.2. This result directly extends to P (l) for every constant k E N+
The implication of Theorem 4.2 is daunting: even though P Pmax(1.[oZ]) is much more powerful than every practical convex relaxation algorithm, it is still incomplete, and the bounding error can be arbitrarily large. This shows a hard threshold in the completeness of cross-layer convex relaxation verifiers: P|aL] is complete when a 1 and incomplete when < 1.
Beyond the ReLU activation. While the incompleteness results we established so far are for ReLU networks. they can be naturally extended to non- polynoool activation functions such sigmoid and tanh as follows. Recall that the extension to cross-layer incompleteness (Theorem 4.2) is based on the pumping construction of Lemma 4.1 which extends to other activations, thus it suffices to show that layerwise incompleteness extends to non-polynomial activations. The proof relies on two observations: (i) there exists a network and an input set X such that cf (X) * 0, thus there exists a nonempty open set A such that A C co)v(f(X)) \ (X).. and (ii) there exists another network g such that (conv(((X)) attains its minimum only inside A. Given a non-polynomial activation function, by the universal approximation theorem (Hornik et al., 1989), the network class dense in the space of continuous functions, thus the first condition is easy to satisfy. The second condition can be satisfied by constructing a network that approximates a continuous function that attains its unique minimum in A. With these two core ingredients, the rest of the proof is similar to that of ReL.U networks. We defer the formal statements and proofs to SJ. Further, while we focus on the absolute bounding error in the main text, the relative bounding error can also be shown to be arbitrarily large; we defer the formal statements and proofs to SI.

---

Published as a conference paper at ICLR 2026
5 MAKING MULTI-NEURON VERIFIERS COMPLETE
We have shown in $3 and $4 that no multi-neuron relaxation can be complete. In this section, we study techniques to augment multi-neuron methods into complete verifiers. First, $5.1 shows that layerwise multi-neuron relaxation, specifically Pi, can be turned into a complete verifier by an equivalence-presere practical algorithm. an immediate corollary is that every continuous piecewise linear function can be expressed by a ReLU network that is exactly bounded by a layerwise multi-neuron relaxation, which is unattainable by single-neuron relaxations. Second, $5.2 shows a sufficient and necessary condition for P1 to be complete under a convex polytope partition, and that single-neuron relaxations inherently require more partitions to be complete.
structural transformation. While this result does not directly yield a
5.1 COMPLETENESS VIA NETWORK TRANSFORMATIONS
In this section, consider a strong layerwise multi-neuron relaxation, namely Pi, and show that it can be turned into a complete verifier by equivalence-ppeserviing structural transformation of the network. Given a network f to be verified, we can always construct a network g equivalent structurally more amenable to Pı. so as to enable exact bounds. We formally state it in Theorem 5.1.
but
Theorem 5.1. For d, d' E N+ let s: IR + Rdd be network and let C Rd be a convex polytope. There cxists a network g Rdd - IR" satisfying g = f on X, such that E(g, XI. = min f (X) and (gg PI, max f(X).
The high-level idea is as follows: P1 considers constraints involving a single layer, thus we need to ensure sufficient information is passed through the hidden layers to the output layer for P1 to provide exact bounds. This is achieved by expanding the hidden layers of I on width and making the additional neurons copy the input variable. In this way, the last layer contains sufficient infor- mation of the input and as such PI. which ensures the convex hull of the last layer's variables, can cquivalently ensure the convex hull of f[X]. Detailed proof is deferred to SG.1.
Theorem 5.1 shows that P1 is powerful enough for complete certification if an equivalence- preserving transformation is allowed. While calculating Pi for the transformed network might be computationally expensive and potentially intractable, the core message from Theorem 5.1 is that the expressivity of ReLU networks no longer limited by the relaxation. As mentioned in $1, un- der single-neuron relaxations, the expressivity of exactly bounded ReLU networks is limited to 1-D continuous piecewise linear functions (Baader et al., 2024): beyond 1-D, even the simple "max" function in [0, 1 cannot be encoded by a ReLU network that is exactly bounded by single-neuron relaxations. In contrast, an immediate corollary of Theorem 5.1 is that multi-neuron preserves the full expressivity of ReLU networks representers of general continuous piecewise linear functions:
Corollary 5.2. For d E N+ let f Rd + RR be a continuous piecewise linear function, and let X C Rd be convex polytope. There exists a network g Rd - RR satisfying g f on X, such that {gg, P1 = min fX) and u(g, P1. X) max f(X).
Corollary 5.2 shows that for every continuous piccewise linear function, there exists a ReLU network encoding it that can be exactly bounded by Pi. In practice, multi-neuron relaxation much weaker than Pi may be enough for exact bounds. To illustrate this, we examine the concrete example of the "max" function in [0, 1j and show that Mi is sufficient to exactly bound network encoding it in the following.
Case study: max x.) can be exactly bounded by Mi in [0, 1]
#2,.....
The function range is [0, 1]. We can represent the "max" function by the ReLU network f = x2 + p(z1 22), as illustrated in Figure 3. This network has width two (nodes and d) and one un- stable neuron (node c). Recall that Mj computes the con- vex hull of (xx, p(x:)) for some i for each ReLU layer.
First, consider the case
Figure 3: A network encoding f max(#1, 22).
We now show that Mj computes the exact bounds of f. The input box is defined by the constraints (a) 2 0, 21 S
7

---

Published as a conference paper at ICLR 2026
1, 2 02 1}. Besides, the constraints the affine layers are {a = I1
F2.b x2. f
c+ d). Under these constraints, we compute bounds of the neurons of the first affine layer by linear programming, yielding E [-1, 1] and b [0, 1]. For the stable node d, the constraint is then (d= For the unstable node c, the constraint is {c 2 0, c 2 a, S 1 - b, C S a + b), where the first two inequalities are based on the property of the ReL.U function and the last two inequalities are based on the capability of M1 to compute conv b, c)) given conv((a, 6)) = {a 2 -b, a S
1- b [0, 1], a E [-1,1]] 1]]. Note that conv((a, 6)) is provided to M₁ because only single affine layer is parsed before the ReLU layer. Therefore, we have f c d = c + 22 2 0 + I2 2 0 and f d c + 22 I b+ + 22 S 1. Thus, M1 returns the exact upper and lower bounds. We remark that R-ReLU, equivalent to the Triangle relaxation in this case for every k 2 1 since there is only one unstable neuron, induces on node e the constraint set (c 2 0, c 2 a, c S 0.5a + 0.5). The resulting upper bound is 1.5, which is inexact, consistent to Baader et al. (2024).
Based on the 2-D case, we extend the result to [0, 1]d. Indeed, we can rewrite "max" in nested form according max( (2,,. .2.... zaa = max(maxx(()) 22), 22),..., T.). By the previous argument, a multi-neuron relaxation can bound u = max(#1, , Øz) exactly. Note that u has no interdependency with 23. Fdl thus we can repeat the procedure above for max 23, ; By induction on d, a multi multi-neuron relaxation, namely MM, can bound the output of a ReLU network expressing the "max" function in [0, 1] exactly.
5.2 COMPLETENESS VIA CONVEX POLYTOPE PARTITIONING
In this section, we discuss how to achieve completeness for general networks (without transforma- tion) by partitioning the input set into convex sub-poli tob-polytopes.
Branch-and-boume (BaB) is currently the most effective complete verifier. It progressively divides the current problem into subproblems, solves each subproblem recursively, and combines the results to yield the bounds. With similar strategy we call it polytope partitioning -Pi can be turned into a complete verifier. The idea is to partition the input set of every layer into smaller convex polytopes so that Pi exactly bounds each of them. The exact bounds of the original input set can then be obtained by aggregating bounds of the smaller polytopes. An algorithm provided in $D.
We first prove completeness, i.e., polytope partitioning enables Pi to calculate exact bounds.
Proposition 5.3. Let L E N and do di...., d E N+. Consider an input set X C R and a network f = WL+1 o p o ... o p a W1, where W, : R24 + Rd: are the associated affine transformations for j E [L 1). Denote the subnetworks of ʃ by ʃj Wj+1 o po o oo Wi. for j E [L]. Assume Hi...., He C X such that H1,..., Hy are convex polytopes, f(X) = U..)))... f(H.), and fy is a convex polytope for all j [L] and [p], then
min f(X) = -min P1, KEPp]
max f(X) = max u(f. (1 kE
Proposition 5.3 states that when we partition the input set into a finite collection of convex polytopes, such that each polytope remains as a convex polytope through the subsequent layers, then Pi can re- turn exact bounds the input set. The proof of Proposition 5.3 (c.f. $G.2) is based on investigating how affine and ReLU layers transform polytopes. Essentially, an affine transformation converts an input convex polytope into a convex polytope in the output space, and the ReLU function transforms a convex polytope into union of convex polytopes. See Figure 4 for a visualization. We note that the conditions in Proposition 5.3 are not only sufficient, but also necessary: if there is sub-polytope that is no longer convex polytope after some layer, then the convex hull of the output set of that layer on this sub-polytope strictly larger than the actual feasible set. From the discussion in $3, we have already known P, cannot return exact bounds for general networks when this occurs.
A key question with partitioning is: what is the complexity of partitioning, that is, the number of subproblems to be solved? In particular, how does it compare with BaB when single-neuron relaxations are used for bounding? Before answering this question, we first formally define the (worst-case) partition complexity.
Definition 5.4. Let P be complete certification method, f a network, and X input set. Define the partition complexity of P on f for X, denoted by #Partition ff X), to be the maximum number of subproblems P needs solve compute the exact bounds of f on X.
8

---

Published as a conference paper at ICLR 2026
b
A22
Figure 4: A partition of the input set where every part remains convex polytope through the layers.
Definition 5.5. Let f be ReLU network with & ReLU neurons, and X be an input set. For x E X, the activation pattern of f at is defined as the binary vector a E {-1,1] such that a, = 1 if the i-th ReLU neuron is activated at x, and a, = otherwise. Denote the number of distinct activation patterns of f on X by X),
Examples. BaB with DEEPPOLY (Singh et al., 2019b) as the bounding method has partition com- plexity equal to X), since enumerating all possible activation patterns is both sufficient and necessary for exact bounds. BaB with IBP (Gowal et al., 2018) as the bounding method has infinite partition complexity for the network 21 p(æ₂ 21). which encodes the "max" function on [0. 1J2. To see this, assume there exists a finite partition of the input set such that IBP returns exact bounds with this partition. Taking the right-upper partition,
always find subset of it in the form B = [p, x [g, 1] for some p, 4 < 1. Then, the IBP upper bound for 22 I1 on B is 1 - p. the IBP upper bound for p(22- 21) is p. and the IBP upper bound for æ1 1. Therefore, the IBP upper bound for f on B is at least 2 which is inexact compared to the exact upper bound 1.
In the following, we compare the partition complexity of BaB, when single-neuron relaxations and multi-ncuron relaxations are used for bounding, respectively, showing that they are separated by A(f, X). This result holds for every single-neuron and multi-neuron relaxation in general, and does not require any assumption on the network or input set.
Proposition 5.6. Let S be some single-neuron relaxation and M be some multi-ncuron relax- ation. For every ReLU network f and every input set X, #Partition(BaB(MM) XX) I X(f,X) < #Partition (BatiionnBa(BBB,,,. X).
For BaB, enumerating all possible activation patterns is necessary to obtain exact bounds even with the precise single-neuron bounding algorithm. In contrast, Proposition 5.6 states that the acti- vation pattern provides an upper bound on the polytope partition complexity. The proof is deferred SG.2. Although Proposition 5.6 establishes clear separation on partition complexity between BaB with single-neuron relaxations and multi-neuron relaxations, the upper bound can be quite con- servative for powerful multi in SH, in which P1 with polytope partition has exponentially smaller time complexity than BaB with DEEPPOLY.
multi-neuron neuron relaxations such as P1. We show this with a concrete example
DISCUSSION
Result Contexts Our results (both negative and positive) are limited the neural network veri- fication setting considered in this paper. Under the given setting, the universal convex barrier ($3 and $4) means that for all fixed convex relaxation which may have arbitrarily large but finite re- sources, for all non-polynomial activation functions, all non-empty input convex polytopes and all error thresholds, there always exists a network with the activation, such that the bounding error of the relaxation this network and input convex polytope greater than the emror threshold. This holds for both the absolute bounding error and the relative bounding error. The positive results ($5) further limited to finite ReLU networks.
Implications We established a universal convex barrier, essentially ruling out the possibility of complete verifiers based solely any convex relaxation. This implies that convex relaxations should only be applied as a subroutine a complete verification method, such as BaB. All ex- isting BaB methods apply single-neure relaxations for bounding the subproblems. However, results suggest that subproblem bounding with multi-neuron relaxations has strictly lower parti- tion complexity. This indicates potential interest in applying efficient multi-neuron relaxations to

---

Published as a conference paper at ICLR 2026
bound the subproblems during BaB. In addition, existing efforts training certified models focus on single-ncuron relaxations, despite the fact that none of the single-neuron relaxations can provide exact bounds for any networks encoding complex functions. In contrast, results established in $5.1 suggest that certified training with multi-neuron relaxations may be more effective, as they can pro- vide exact bounds for every continuous piecewise linear function encoded by some networks. We leave the further investigation of practical algorithms to future work.
7 CONCLUSION
We conducted the first in-depth study on the expressiveness of multi-neuron convex relaxations. We extended the established single-neuron convex barrier to universal convex barrier for multi-neuron relaxations, showing that they are inherently incomplete regardless of the resources allocated. On the positive side, we showed that completeness can be achieved by multi-neuron relaxations when augmented with cettvvaleee--peseeviin and established clear separations between multi-ncuron and single-neuron relaxations in both cases. Our findings lay solid foundation for multi-neuron relaxations and point to new directions for certified robustness.
network transformations convex polytope partitioning,
ACKNOWLEDGMENTS
This work has been done as part of the EU grant ELSA (European Lighthouse on Secure and Safe AI, grant agreement no. 101070617) and the SERI (Swiss State Secretariat for Education, Research and Innovation) grant SAFEAI (Certified Safe, Fair and Robust Artificial Intelligence, contract no. MB22,00088).. Views and opinions expressed are however those of the authors only and not necessarily reflect those of the European Union European Commission. Neither the European Union nor the European Commission can be held responsible for them.
REFERENCES
Ross Anderson, Joey Huchette, Will Ma. Christian Tjandraatmadja, and Juan Pablo Vielma. Strong mixed-integer programming formulations for trained neural networks. Math. Program., 183(1): 3-39, 2020. 2020.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In Proc. of ICLR, 2018.
Maximilian Baader, Matthew Mirman, and Martin T. Vechev. Universal approximation with certified networks. In Proc. of ICLR, 2020.
Maximilian Baader, Mark Niklas Mueller, Yuhao Mao, and Martin Vechev. Expressivity of reLU- networks under convex relaxations. Proc. of ICLR, 2024.
Stefan Balauca, Mark Niklas Müller, Yuhao Mao, Maximilian Baader, Marc Fischer, and Martin Vechev. Gaussian loss smoothing enables certified training with tight convex relaxations. Trans. Mach. Learn. Res., 2025.
Rudy Bunel, Jingyue Lu, llker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and M. Pawan Kumar. Branch and bound for piecewise linear neural network verification. J. Mach. Learn Res., 21, 2020.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEFE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, 2017. doi: 10.1/09//P2001..49
Nicholas Carlini, Florian Tramer, Krishnamurthy Dj Dvijotham. Leslie Rice, Mingjie Sun, and Zico Kolter. (certified!!) adversarial robustness for free! In Proc. of ICLR, 2023.
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via random- ized smoothing. In Proc. of ICML, volume 97, 2019.
10

---

Published as a conference paper at ICLR 2026
Claudio Ferrari, Mark Niklas Müller, Nikola Jovanović, and Martin T. Vechev. Complete verification via multi-neuron relaxation guided branch-and annuh-und--oudd. In Proc. of ICLR, 2022.
Timon Gehr, Matthew Mirman, Dana Trachsler-Cohens Petar Tsankov, Swarat Chaudhuri, and Mar- tin T. Vechev. A12: safety and robustness certification of neural networks with abstract interpre- tation. In IEEE Symposium on Security and Privacy, 2018.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy A. Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. ArXiv preprint, 18..11101.11.5... 2018.
Kurt Hornik, Maxwell Stincheombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-366, 1989. ISSN 0893-6080. doi:
https://doi..rg//10. 1.11100.0011000 1016/0003-000000//00 6008888888800000009990022223200
Joey Huchette, Gonzalo Muñoz, Thiago Serra, and Calvin Tsay. When deep learning meets polyhe- dral theory: A survey. CoRR, 000//233500024,, 2023.
Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. ArXiv preprint, abs/1702.01 2017.
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. IEFE Symposium on Security and Privacy, 2019.
Yuhao Mao, Mark Niklas Müller, Marc Fischer, and Martin T. Vechev. Connecting certified and adversarial training. In Proc. of NeurIPS, 2023.
Yuhao Mao, Mark Niklas Müller, Mare Fischer, and Martin T. Vechev. Understanding certified training with interval bound propagation. In Proc. ICLR, 2024.
Yuhao Mao, Stefan Balauca, and Martin Vechev. Ctbench: A library and benchmark for certified training. In Proc. of ICML, 2025.
Matthew Mirman, Timon Gehr, and Martin T. Vechev. Differentiable abstract interpretation for provably robust neural networks. Proc. of ICML, volume 80, 2018
Matthew Mirman, Maximilian Baader, and Martin T. Vechev. The fundamental limits of neural networks for interval certified robustness. Trans. Mach. Learn Res., 2022, 2022.
Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin T. Vechev. PRIMA: general and precise neural network certification via scalable convex hull approximations. Proc. ACM Program. Lang., 6(POPL), 2022. doi: 10. 145/3498704.
Mark Niklas Müller, Franziska Eckert, Marc Fischer, and Martin T. Vechev. Certified training: Small boxes are all you need. In Proc. of ICLR, 2023.
Alessandro De Palma, Harkirat S. Behl, Rudy Bunel, Philip H. S. Torr, and M. Pawan Kumar. Scaling the convex barrier with active sets. In Proc. of ICLR, 2021.
Alessandro De Palma, Rudy R Bunel, Krishnamurthy Dj Dvijotham, M. Pawan Kumar, Robert Stan- forth, and Alessio Lomuscio. Expressive losses for verified robustness via convex combinations. In Proc. of ICLR, 2024.
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. convex relaxation barrier to tight robustness verification of neural networks. In Proc. of NeurIPS. 2019.
Hadi Salman, Mingjie Sun, Greg Yang. Ashish Kapoor, and J. Zico Kolter. Denoised smoothing: A provable defense for pretrained classifiers. In Proc. of NeurIPS, 2020.
Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsich. Fast certified robust training with short warmup. In Proc. of NeurIPS, 2021.

---

Published as a conference paper at ICLR 2026
Zhouxing Shi, Qirui Jin, Zico Kolter, Suman Jana, Cho-Jui Hsieh, and Huan Zhang. Neural network verification with branch-and- and-bound for general nonlinearities. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 315-335 2025.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin T. Vechev, Fast and effective robustness certification. In Proc. of NeurIPS, 2018.
Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, and Martin T. Vechev. Beyond the single neuron convex barrier for neural network certification. In Proc. of NeurIPS, 2019a.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev. An abstract domain for certifying neural networks. Proc. ACM Program. Lang., 3(POPL), 2019b. doi: 10.1145/3290354.
Chenhao Sun, Yuhao Mao, Mark Niklas Müller, and Martin T. Vechev. Average certified radius is poor metric for randomized smoothing. In Proc. of ICML, 2025a.
Chenhao Sun, Yuhao Mao, and Martin Vechev. Dual randomized smoothing: Beyond global noise variance. ArXiv preprint, abs/2512.00182,, 2025b.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In Proc. of ICLR, 2014.
Christian Tjandraatmadja, Ross Anderson, Joey Huchette, Will Ma, Krunal Patel, and Juan Pablo Vielma. The convex relaxation barrier, revisited: Tightened single-neuron relaxations for neural network verification. In Proc. of NeurIPS, 2020.
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In Proc. of ICLR, 2019.
Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. Proc. of NeurIPS, 2020.
Calvin Tsay, Jan Kronqvist, Alexander Thebelt, and Ruth Misener. Partition-based formulations for mixed-integer optimization of trained relu neural networks. In Proc. of NeurIPS, pp. 3068-3080, 2021.
Zi Wang, Aws Albarghouthi, Gautam Prakriya, and Somesh Jha. Interval universal approximation for neural networks. Proc. ACM Program. Lang., 6(POPL), 2022. doi: 10. 10.1145/3498675.
Tsui- Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane S. Boning, and Inderjit S. Dhillon. Towards fast computation of certified robustness for relu net- works. In Proc. of ICML, 2018.
Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proc. of ICML, volume 80, 2018.
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In Proc. of NeurIPS, 2018
Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsich. Automatic perturbation analysis for scalable certified robustness and beyond. In Proc. of NeurlPS, 2020.
Kaidi Xu, Huan Zhang. Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsieh. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. Proc. of ICLR, 2021.
Huan Zhang, Tsui-Wei Weng, Pin-Yu Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Proc. of NeurIPS, 2018.
Huan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsieh, and J. Zico Kolter. General cutting planes for bound-propagation based neural network verification. Proc. of NeurIPS, 2022.
12

---

Published as a conference paper at ICLR 2026
A RELATED WORK
Neural Network Certification We focus on the deterministic certification of neural networks, which provides a deterministic guarantee on the robustness of a model rather than probabilistic one (Cohen et al.. 2019; Lécuyer et al., 2019; Salman et al., 2020; Carlini et al., 2023; Sun et al., 2025a;b). Existing methods for deterministic neural network certification can be categorized into complete and incomplete methods. Complete methods commonly rely on solving a mixeddinteger program (Tjeng et al., 2019; Anderson et al., 2020; Tjandraatmadja et al., 2020; Tsay et al.. 2021) to provide exact bounds for the output of network. The state-of-the-an arrt complete method (Zhang et al.. 2022: Shi et al., 2025; Xu et al., 2021; Ferrari et al., 2022) is based on solving the mixed (Bunel et al., 2020) on the integer variables. These meth-
integer program with ods are naturally computationally expensive and do not scale well. Incomplete methods, on the other hand, provide sound but inexact bounds, based convex relaxations of the feasible output set of a network. Xu et al. (2020) characterizes widely-recognized single-neuron convex relax- ations (Mirman et al., 2018; Wong et al., 2018; Zhang et al., 2018; Singh al., 2019b) by their induced affine constraints, where the bounds are yielded by efficient but not necessarily optimal solvers. However, Salman et al. (2019) empirically identify a single-neuron convex barrier, prevent- ing single-neuron relaxations from providing exact bounds for general ReLU networks, even with costly optimal solvers. To bypass this barrier, multi-neuron relaxations (Singh et al., 2018; Zhang et al., 2022; Müller et al., 2022) have been proposed and achieved higher precision empirically.
Multi-neuron Relaxations in Practice To bypass the single-neuron barrier, multi-neuron relax- ations (Singh et al., 2018; Zhang et al., 2022: Müller al., 2022) have been proposed, achieving higher precision empirically. In particular, Singh et al. (2019a) and Müller et al. (2022) are looser versions of Pi discussed in this paper; Zhang et al. (2022) is looser version of PL. Ferrari et al. (2022) combine multi-neuron relaxations with BaB and find that applying multi-neuron relaxations before BaB yields a superior overall performance. These practical applications motivate us rig- orously study the fundamental limit of multi-neuron relaxations. Furthermore, the certified training community (Müller et al., 2023; Mao et al., 2023; 2025) has already employed multi-neuron relax- ations in verification, but not yet in training. This also motivates us to explore the possibility of combining multi multi-neuron with certified training.
Certification with Convex Relaxations Existing work on the certification with convex relaxations focuses on the expressiveness of single-neuron relaxations. We distinguish three convex relaxation methods typically considered by theoretical work: Interval Bound Propagation (IBP) (Mirman al., 2018; Gowal et al., 2018), which ignores the interdependency between neurons and use intervals {(abb) la b E RR for relaxation; Triangle relaxation (Wong & Kolter, 2018), which approximates the ReLU function by triangle in the input-output space; and multi-neuron relaxations (Singh et al., 2018; Zhang et al., 2022: Müller et al., 2022) which considers a group of ReLU neurons jointly in a single affine constraint. On the positive side, Baader et al. (2020) show the universal approximation theorem for certified models, stating that for every continuous piecewise linear function f R" - IR and every > 0, there exists ReLU network that approximates for which IBP provides bounds This result is generalized to other activations by Wang et al. (2022). However,
within error Mirman et al. (2022) shows that there exists continuous piecewise linear function for which IBP analysis of every finite ReLU network encoding this function provides inexact bounds. Further, Mao al. (2024) shows that a strong regularization on the parameter signs is required for IBP provide good bounds. Beyond IBP, Baader et al. (2024) show that even Triangle, the most precise single- neuron relaxation, cannot exactly bound any ReLU network that encodes the "max" function in IR,, although it is provably more expressive than IBP in R. While Baader et al. (2024) also shows that every ReLU network with a single hidden layer can be exactly bounded by multi-neuron relaxations with sufficient budget, the theoretical properties of multi-neuron relaxations in the certification of general ReLU networks remain unknown. We remark that this review is not exhaustive, especially regarding convex relaxations beyond neural network certification, and refer readers to Huchette et al. (2023) for a more comprehensive survey on MILP formulations, polyhedral geometry and expressiveness of ReLU networks.
13

---

Published as a conference paper at ICLR 2026
a-c 2/ +
Calashedd Cca..)) ([-
Cala.)
Figure 5: Visualization the single-neuron multi-neuron relaxations for a network encoding f(x) = 0.
B NOTATION
We use lowercase boldface letters to denote vectors and uppercase boldface letters to denote ma- trices. For the vector æ, 2; denotes its i-th entry and æ; is the subvector of with entries cor- responding to the indices in the set I. IN is the N x N identity matrix and 1x and Ov denotes the N-dimensional column vector with all entries equal to and 0. respectively. e, is the column vector with the i-th element taking value and all other elements O. For 1 and without subscript, we understand them to be vectors of appropriate dimensions according to the context. For matrices A1, ..... An, we designate the block-diagonal matrix with diagonal element-matrices A1...., An. by diag( (iaag(A,,... (I,,..,, A.).
For H, denote the convex hull of H by conv H. We represent the ReLU function as p(x) = max(ax 0). For two vectors a, b E Rd a S b denotes elementwise inequality.
The real set is denoted by R. the natural numbers by N, the positive integers N+, and the d- dimensional real space by IRd For set S, |S| denotes the cardinality of S, which is the number of elements in S. Given r N+, [r] denotes the (1,2...., For function f and input domain X, we use f(X) to denote its range {f(x) E X} and f[x] to denote its image f(x)) X).
We use C(x) to denote a set of affine constraints on i.e., C = {Ax +b < 0} for some matrix
A and some vector b. For two sets of constraints (x) = (A x + b(1) < 0} and C2(x) =
(A x + ((2) < 0}, C1 A C2 {A()) x + b(1) < A A (2)x + ((2) s 0} denotes a combination of the two sets of constraints, i.e., their feasible sets are intersected.
Given a set H {(x.y) (x.y) E H}, we denote the projection of H onto the æ-space by Ta H)) (x: By (x.y) )) E H) and the projection onto the y-space by ny (H) (y Fa (æ, y) H). For feasible set C defined by the constraint set C(x., y). T (C) is the set of values of that satisfy the constraints in C.
For function f : dd + R, an input convex polytope X E R and a convex relaxation P, lower bound of on X under P denoted by E(S,P, X) and the upper bound is denoted by M(J,P, X). Concretely, let C(P) be the constraint set induced by P and v R be the output variable, then {(f, P.f. min n. (C(P)) and u[f,P,X) = max n. (C(P)).
We call neurons that switch their activation states within the input set as unstable, otherwise call stable.
C EXAMPLE ILLUSTRATION
This section contains toy example to illustrate the concepts we introduced, namely the ReLU network p(z) - p(z) encoding the zero function f(x) = O with input x [-1, 1]. This network visualized in Figure 5. The affine constraints are as follows: (i) for the input convex polytope, we have {x > -1, < 1): (ii) for affine layers, we have {a x, I. ReLU layer, a single neuron relaxation (Triangle) will have Ca A C, and a melti-neuron relaxation (M2) will have Cm (a, b, c, d). In this case, multi-neuron relaxation successfully solves that the upper bound and lower bound of are zero, while a single-neuron relaxation solves an inexact upper bound and an inexact lower bound -1.
d); (iii for the
14

---

Published as a conference paper at ICLR 2026
D PSEUDO-ALGORITHM FOR POLYTOPE PARTITION
In this section, we present pseudo-algorithm for the polytope partition in $5.2. It serves as a high- level description of the polytope partitioning algorithm. The actual implementation practice may vary depending on the specific problem and the desired performance.
Algorithm 1 Polytope Partition
Input: network f. input convex polytope X
Output: u = m (xx) and millgxx [(x))
Initialize H X)}
for each layer fg in do Initialize with convex polytope collection H' for each pair (H,,Sa, ) E H do
Compute the output of fj on Sk, denoted by fS()k)
if (S())) is convex polytope then
Add (Hy, (Sk) to II'
else
Decompose (Hg, Sk) into convex polytopes H HE, and the images
:......, Sky, such that (Jk,), is convex polytope for i 1 ,.... v, where should be as small as possible
Add (HK,, (Sx.) to H' for I.... end if end for Set H end for
Initialize e to and u -00
for each convex polytope H₁ H do
Update = min (L, {(f. P1, Hx)) Update max(u, uf,, Pı, Hk) end for return and L
Example. Running Algorithm 1 on the "max" example in $5.1, the input box [0, 1] is always mapped to convex polytope as passes through the network layers. Therefore, the partition com- plexity is 1.
We remark that there are two steps in the algorithm that might require high computational complex- ity in practice: (i) the partitioning of set into convex polytopes, and (ii) the merging of convex polytopes. The partitioning step is necessary because the output convex polytope, and need to partition it into smaller convex polytopes compute the bounds. The merging step is to merge redundant convex polytopes to reduce the number of subproblems. To design practical algorithm with low running time complexity is beyond the scope of this paper, and we leave it to the future work.
ReLU network may not
E DEFERRED PROOFS IN $3
E.1 PROOF LEMMA 3.1
We prove Lemma 3.1, restated below for convenience.
Lemma 3.1. Let I. E N and let X be convex polytope. Consider ReLU network or oo- Denote the variable of the j-th hidden layer of f by v03 for j E [L 1], and the variable of the output layer by v(L), For < < L, let C, (æ, ((1) ...., w())) and C2 (11) " v!4) be the set of all constraints obtained by applying P, the first and L layers of f. respectively. Then, Toto (C1 (ar, (1) ((()).,.....)))) म... (Cz(x,, (11)
v()))).
15

---

Published as a conference paper at ICLR 2026
Proof. As P does not consider constraints cross nonadjacent layers, C1 is in the form of C(x, o( C(v()) x(2)) U U C(oli-1) o()) and C2 C1 U C(v(f) o(it)) U... ((v(l-11) v(1)). Let C3 = C(v(o) vli+1)) U... UC(o(L-1), v(()). Note that the projection t (C1) is considered by P1 as the input set of the subnetwork fi+1 o ... o fL to instantiate further relaxations for deeper layers. Since P1 is sound verifier, the constraints C3 must allow the input set, iee.
Tet(i) (Ca) 2 t (C1).
Now Tcss (C2) is obtained by applying the Fourier-Motzkin algorithm to eliminate all the variables in C2 Ci n C3 except (1), W.l.o.g, assume we eliminate in the following order æ; o ..... o(1-1), v(++1), ..... ((4), The constraints in C3 remains unchanged eliminate æ, v ..... ((i-1), since they are not included C3. Therefore,
Tati (C2) TT)(t) (C1) n Tay (Ca).
Hence, TeCo (C2) Tu(t) (C1).
E.2 PROOF OF LEMMA 3.2
We prove Lemma 3.2, restated below for convenience.
Lemma 3.2. Let X be convex polytope and consider a network f == f2 fi, where fi and f2 its subnetworks. Then, ((J, X) < min((s(conv((1())) and u(J, 2
Proof. By the notation in Lemma 3.1,
(U,
min neT a (C2 m()))) /
S min
vEx (Ca(, ( ((,)) (())) f2(w)
min NER (Ex
f2(v),
where the last equality follows from Lemma 3.1. Since (xx, (1) is convex polytope containing the feasible set of (1), we have Tw( (C, v (1)) 2 conv (X)). Therefore,
min P) (C2a,,e f2(v)
< min (x))
f2(v)
min((2(conv( (X))))
The proof for the upper bound is similar.
E.3 PROOF THEOREM 3.3
Now we prove Theorem 3.3, restated below for convenience.
Theorem 3.3. Let d N and let X be convex polytope in Rd, For every 0 T oo, there exists a ReLU network f : IRd -> R such that {(ʃ, Pi, X) & min f(X) T, and ReLU network g: Rdd TR. such that u(g, Pi, X) ' max ((X) +T.
Proof. The proof is done by explicit construction of ReLU networks that satisfies the required prop- erty.
When d = 1, assume X |a, M C R. where a + b. Let - and (x) 27 - 1| 27
- -1 22). for x E R We construct the network as f'ppoonaaaaaoo
po W1 (b) (2, 1), conv(po W1 Wo((a, f Since ((t, te [0, 1]}. Thus. min f'conv(p W, (o(aa, b))) 0. Therefore, by Lemma 3.2, L S min ('covv W, Wo(la,b))) = 0.
(0,0) and
However, the ground-truth minimum is T. Likewise,
construct ReLU network such that
16

---

Published as a conference paper at ICLR 2026
applying any convex relaxation cannot provide the precise upper bound, by simply negating f' to be f()) = 22 - 1| 2T - -..]
Now assume d 2 2. We assume X does not degenerate, i..., X cannot be embedded in lower- dimensional space; otherwise, we can simply project X to a lower-dimensional space with a single affine layer and set d smaller value. Now, define the first affine layer to be the projection layer T(x) = 21, which simply projects a point to its first dimension. For every non-degenerate X, (XX) nonempty interval in R. We then construct ReLU network f f' po W o Wo n. By the analysis above, l S min ('(covv(p Wi o Wo(la, b()) - T.
F DEFERRED PROOFS IN $4
F.1 PROOF OF LEMMA 4.1
Now we prove Lemma 4.1, restated below for convenience.
Lemma 4.1. Let a E (0, 1), d, d', L1, L2 E N+, and X C Rd be a convex polytope. For every la-layer network fi .Rd - Rd and T--llayer network f2 Rdd + R. there exist I. T1 L2 and a L-layer network If such that (i) f(x) = f2 o (x)), for Vn E X, and (ii) ((J,Pmxx(,,aa)) X) s min fz (conv((f(X))) and u(f, P [max(1,|aL)) X) max f2 (x))((())
Proof. Intuitively, the proof is done by blocking direct information passing from fi to fz through adding dummy layers. Let = max(1, [aL]) and take
L = [maxx( L + +
(1)
1-a
We construct the network by pumping f2 fi through adding identity layers between f2 and fi, thus the name pumping lemma. Concretely, let f f2 o..... f2 where I is the
(L- LL-Li-La times
identify function in Rd Take. Thus, L- L1 - L2 2 k 1.1. Denote the input variable by (0) and the variables on the i-th layer of f by (0))_ By definition, Pa computes all constrains of the form C(v(f) ,..,))............. v(+4)) ((4)))) for = 0...... L - k. By the identity layer construction, we know (T1)) = (l++1) = =... = ((..-1g) By (1), L L1 - L2 2 k + 1, which means the constraints induced by P, are can be reduced to constraints of the form (()()),... ".......mmmmmi. ((mla(((t,,a))) for i o...., Lt. and (mx()))). ...., o()), for j L Lz...., L. For brevity, we slightly abuse notation and denote by C(Px) the union of all constraints induced by Pk, denote by Ci the union of constraint sets of the form C(v(1)) ,.... "ol")))..,..liila ((min((tth)L1)) for i O...., Tr, and denote by C2 the union of constraint sets of the form ((p(max(j-R. Thus, 12 (C(Pk)) = FOLL) = (CI). Since conv(f(()) S. TT (C1). E(f.PA. X) S min fz (2
b()) for = L L L.
min (C(T
I min fin fz(conv(f1
and
u(f. Pk. X) 2 max f2( (C(P.)))
max f2( (C1)
2 max fz(conv (f (X))).
F.2 PROOF OF THEOREM 4.2
Now prove Theorem 4.2, restated below for convenience.
17

---

Published as a conference paper at ICLR 2026
Theorem 4.2. Let d N and let X R be convex polytope. For every (0,1) and every constant T > O, there exists a network f : R - such that {(f. P mmx((11(at.]) x) S min ((X) - T, and a network R² + R such that u(g. P mmxx(L]aa()): 2 max g(X) +
Proof. We reuse the construction in the proof of Theorem 3.3, augmented by Lemma 4.1. In the proof of Theorem 3.3, we constructed feedforward network == -" popoo W3 o W2 o W o m. Let fi = o W3 W2 W1 и and f2 S". By Lemma 4.1, for some I. E N, there ex- ists an I.-layer network f such that f = f2 o f1 everywhere on X and P(SPPam mmxx(1 X) s I min(f(x) x X) T min(f(x)
E X} T and uff mmax(1, aL))) Z fax 2 max{f(x) : x X3 +T max(f(x)
min f2(conv(f1
+
G DEFERRED PROOFS IN $5
G.1 PROOF OF THEOREM 5.1 AND COROLLARY 5.2
We present technical lemma before proving Theorem 5.1.
Lemma G.1. Let H be compact set in Rdd, Then, for every E [d], minge a; min eccovv If 0; and m H v; maXpEconv H Vç.
Proof. We only show the equality for minimum values. The proof for maximum values is likewise. Fix an arbitrary i E [d]. Since H C conv H, we have
min
min V. vEconv
Since the convex hull of a compact set is closed, E0 E conv H such that mineeconv 8; = U.-
Furthermore, 7x" y² H and l [0. 1), such that v² lx + (1 l)y" Without loss of generality, assume x. S yr- But ox < tax + (1 t)y = of = min n, Therefore min 3; x S minugcoon H Us. Combining with (2) gives min H 2; minveconv H Vi. L
Now we prove Theorem 5.1, restated below for convenience.
Theorem 5.1. For d, d' N+ let Rd Rd be network and let X S Rd be convex polytope.
There exists a network g : Rdd TR." satisfying g f on X, such that E(g, Pi, X) = min (XX) and u(g, X) max f(X).
Proof. We construct the network g based on f as follows. First replicate the structure and weights of f verbatim. Then add d extra neurons in every hidden layer of g to make copies of the input neurons. This can be achieved based on the equality p(t u) + u = t, for t 2 u and t, u E R. See Figure for illustration. By construction, 9 represents the same function as f on X.
X. Now we prove Pi returns precise bounds for on X. Assume has L layers. Denote the variables of the i-th hidden layer by o0)), j I,..., L- 1, and the output layer by (44) By definition of Pi, the system of constraints generated by Pı includes all affine constraints the form of (lu(( z)), given those passed from the (L 1)-th layer. Since g!!-1) contains æ as a part, Pı computes the convex hull of (x)). Furthermore, by Lemma G.I, the bounds of the convex hull of the compact set g( X) characterizes exact upper and lower bounds of g(X). Therefore, Pi returns precise bounds of g on X.
We proceed to prove Corollary 5.2, restated below for convenience.
Corollary 5.2. For d E N+, let f Rd R be continuous piecewise linear function, and let X C dd be a convex polytope. There exists a network g Rd - satisfying g = f on X, such that (gg, Pi, X) min f(X) and u(g, P1, X) max f(X).
18

---

Proof. Denote the variable of the first hidden by (1), By definition, Pi computes the convex hull of the function graph (x, (1) fi (æ)), therefore the convex hull of the feasible of (1)), Since the convex hull of convex set is the set itself, Pi can precisely computes the feasible of (11), Simply Published as a conference paper at ICLR 2026
Figure 6: Top: the network f. Bottom: the network g. Labels on the edges are associated weights.
Proof. For a continuous piecewise linear function f Idd + R, by Theorem 2.1 of Arora et al.
(2018), there exists ReLU network g' R2d IR satisfying
f(x) = (x))
x E ERR..
(3)
By Theorem 5.1, there exists another ReI.U network Rd - IR satisfying g(x) = g (x), x x X,
(4)
and
{(g, Pı, X) = min (X)
u(g, P). max ( (X).
Combining (3) and (4), we get
g(x) = f(x), EEW X,
and
(gg, Pi, X) min S(X) u(g. Pı, X) max f(X).
G.2 PROOF OF PROPOSITION 5.3 AND PROPOSITION 5.6
We start with a technical lemma.
Lemma G.2. Let L N Consider network f ft transformation or the ReLU function for j E [L], and an input convex polytope X. Denote by (6) = Jq o..... ... fi. for E [L], the subnetworks of f. Assume (X) convex polytope, Vj [L]. Then, ((f.Pi X)= min fXX) and u(f.PI. P1. max f(X).
fi, where fy is either affine
progagate by the layers and take into account the assumption that (() is convex polytope, for all j E [Z], we get that P, exactly bounds the network output on X.
We proceed prove Proposition 5.3, restated below for convenience.
Proposition 5.3. Let E N and do, di....,, d E N+ Consider an input set C R and Wi, where W, Rd - Rd, are the associated affine
network f Wr++ p transformations for j E [L + 1]. Denote the subnetworks of f by f, := W o p..... o po W,, for j E [L]. Assume HI...., He C X such that HI,..., Hy
convex polytopes, f(X)
U...U...H.... and (H is a convex polytope for all j E [L] and E [p]. then max f(X) = max u(f. Pı, H₂) kE(M]
min f(X) = min (fF,P,, H²) KE[p]
19

---

Published as a conference paper at ICLR 2026
Proof. By Lemma G.2, P1 returns precise bounds for f on H3 for all & [v]. Since the output set f(X) is the union of f(H)) for all E [v], the theorem follows.
We now prove Proposition 5.6, restated below for convenience.
Proposition 5.6. Let & be some single-neuron relaxation and M be some multi-ncuron relax- ation. For every ReLU network f and every input set X, #Pattitio(BaB((M) (M), A(f,X) s PPartitionBBa((S5 f, X).
S A(f.X). Assume network has v := A(,, distinct activation patterns on X. Notice that M always returns a constraint set that is at least as tight as DEEPPOLY, thus a same partition process as BaB(DEEPPOLY) allows BaB(M) to compute exact bounds. Recall that BaB(DEEPPoOL)
Proof. We first prove (aartition(B((MMMM..
has partition complexity equal to on X, therefore (.B also has partition complexity at most v on X.
Now we prove X(f,)) I #Partition(BaBl (8), X.). It suffices to show the inequality for the tightest single-neuron relaxation, i.e., the triangle relaxation, denoted by BaB(A). Given a general subproblem to bound, the only guarantee for A to return exact bounds is that there is no unstable neuron in the subproblem. Therefore, if BaB(A) has partition complexity equal to K on X, then there are most K subproblems with unstable neuron. Thus, A(J, X) & K.
H AN EXAMPLE OF THE BENEFIT OF POLYTOPE PARTITION
For the network encoding max( (11 ........................ Fa) in the case study of $5.1, first note that it has 2d-1 distinct activation patterns on [0, 1jd. We show that BaB requires 2d-1 branching return precise bounds. Let Vi = max( 22), for i E [d -d-13 1], where
= 21. The i-th unstable neuron can then be rewritten as p(y: Z.+1), e.g., for node e in Figure which is the first unstable neu- ron, it can be rewritten as p(v1 22). After branching on it, this node plus ri+1 becomes either 34+1 when xi+1 2 3/s, or y: when x;+1 < ys- Therefore, this branching makes two subproblems, which are essentially the (d 1)-dimension "max" function. This directly implies that neither of the two subproblems can be precisely bounded by any single-neuron relaxation, thus the branching will not stop. Repeating this, BaB enumerates all 24-1 branches, confirming the lower bound estab- lished in Proposition 5.6. In contrast, P1 has partition complexity as shown in $5.1, leading to an exponential reduction.
Regarding the runtime, note that the number of constraints introduced by Pi grows linearly with d, while the number of branching grows exponentially with d for BaB with DeepPoly. Thus, for this example, the runtime of Pi grows polynomially with d, while that of BaB with DeepPoly grows exponentially with
I RELATIVE BOUNDING ERROR
Theorem 3.3 and Theorem 4.2 state that the absolute bounding error by layerwise and cross-layer relaxations can arbitrarily large. In this section, we look at the relative bounding error, namely the ratio between the length of the bounding interval and that of the exact interval. We shall show that the relative bounding error can be arbitrarily large as well. First, for Pı, we shall prove the following statement.
Theorem I.I. Let d N and let X RRd be convex polytope. For all T 0, there exist ReLU
network f Rdd > R, such that
max(f - min(f(X)) > T
Proof. Without loss of generality. we prove the case when T > 1; otherwise, we can simply take the threshold max(1, T) in the proof. Further, let X [-1, 1]: otherwise,
first project X to one of its non-empty dimensions and scale the projected set by a single affine layer, without changing the output range of any subsequent network and the bounds computed by P,.
20

---

Published as a conference paper at ICLR 2026
Let the ReLU network fi = p Wi, where Wi is the affine transformation Wi(+) = (-1) x +
for x R². The function fi maps X into the set {o IR #1 E [0, 11, 02 = 21 + U
{xr E R #1 = 0,1 22 v 2]. whose convex hull is {x2 < 22, + 2 0, 2 - + 1}.
Now consider the function h(x) x2(222 + 1). which is constantly zero the fi(X). We have that
min(M(conv((i
0, 8 = max((((con((((()))
Scaling h by 2 gives
21 min
27 h (Jo = 27.
((conv(((()))) = 0,
max
8
By the universal approximation (Arora et al., 2018), there exist a ReLU network f2 satisfying
27 h1
sup conv(fi(X))
1/2
Therefore,
2T
min(f2 o (X) 2 min( ho fi)
2 = 2'
21
1
max(ʃ2 (X) < max ho fi) fi) 2
and
2T
1
min (aafa(/cov S min( h(conv (f(onn((((X)))) +
2 = 2'
5
2T
1
max f2(conv (f()) 2 max h(conv (f(on)))
2T
2
Taking f = f2 f1, by Lemma 3.2 we know that
Pl..Pi.X) P(f 2 max (2(conv((1(()))) min (a 2 -
and
max(f2 o fi)( min(f2 0 f1(X) 1.
Hence,
2 2T - 1>>1 T. max(J(X)) min(J(X))
We proceed to show that the relative bounding error established above for Pi extends to all cross- layer relaxations. Just as in $4, we do not consider specifie P, for some fixed r E N, but rather directly look at the fully general case P Pmax(1,[of..) where the cross-layer is allowed to depend on the network depth L. Formally,
shall show
Theorem I.2. Let d Nf and let X Rd be a convex polytope. For all T 0, there exist a ReLU network f Rd + R of depth L, such that
w(f, Pmmx((, X) E(f, Pmxx(1 (aL)), > T.
max(f(X)) - min(f(X)
Proof. Without loss of generality, we prove the case when T > 1; otherwise, we can simply take the threshold max(1,T) in the proof.
We reuse the construction in the proof of Theorem I.1 and augment it by Lemma 4.1. Specifically, in the proof of Theorem I.1, constructed ReLUU network
fi satisfying
max(f(X)) min(f(X)) 1.
and
max (a(coo((((((()))))) min (J( 27 -1
21

---

Published as a conference paper at ICLR 2026
Now by Lemma 4.1, for some L E N, there exist L-layer network f such that f f everywhere on X and
u(f, P X) > (fcom
{(f, P (mxx(1 X) I min f2 (conv (f(())))
Therefore,
u(f, P Pmax((, P(f. (otx))
2 max (2(c)nv((((X)) - min (f
27-11 -.
Hence
u(ʃ, P Pmax(1,(aL))) X) e(f. (cxx() X)
max(f((X) - min(f(X))
u(f; P max((1, X) - {(f, P(f,Pmane (.,x(xXX,,LL]] X)
max(f(X)) min(f(X))
> T.
EXTENSION TO NON-POLYNOMIAL ACTIVATION FUNCTIONS
In this section, extend the negative results, namely Theorem 3.3 and Theorem 4.2, established for ReLU neural networks in $3 and $4 to networks with general non-polynomial activation functions. The key insight is that by universal approximation with non-polynomial activation functions, can always construct a network that approximates the construction for ReLU networks with arbitrary precision.
We start by introducing necessary notations. Let H and H' be two sets in Rd. Then, we define the Hausdorff distance (induced by the lg norm) between H and H' as
D(H, H²) max sup inf #eH WEH'
|| -ll2, sup inf ||=--yl [|1)) veH' æEH
We will use two properties of the Hausdorff distance, First, D(H, H') satisfies the triangle inequality (we omit the proof since it is a standard result), i.e., for any three sets H1, H2, H3 in Rd, we have D(H,, H3) < D(H,, H2) + D(H2, Hz).
Second, H > conv (H) is 1-Lipschitz with respect to the Hausdorff distance, stated as follows. Lemma J.1. For any two sets H1, H2 in Rd, we have D(conv(H,) conv (H2)) S D(H,, H2).
Proof. We prove that (U) inf (H)) | vll2 D(H1, H2); the other side can be proven by symmetry.
Fix arbitrary E conv(Hi.. By definition of convex hull, there exist h N+, x 2 0 for i E [k] with Σ X; = 1, and æ; H1 for E [k] such that æ Σ deT By definition of Hausdorff distance, for each E [M). there exists y: E H2 such that ||a: - yell2 S D(H, H2). Let
y Ekn d.y. Then, by Jensen's inequality and note that || ||a convex, we have
||e yl12 = Σ
Acla, y2)
1=1
<
A > vell2
1=1
< D H1, H2).
This implies that inf (nf | 8112 proof.
<
D(H, H2). Since æ is arbitrary, we finalize the
n
22

---

Published as a conference paper at ICLR 2026
Now ready to present the extended version of Theorem 3.3 for non-polynomial activation functions. We will show that for any non-polynomial activation Ø, there exists a sub-network ff and an imput polytope X such that conv(ff (X)) is strict superset of ff (X). Further, for the function [2 c) == (xc c)² where the point E conv(Jf ( ff (X),
there exists a network conv (X)) with arbitrary precision. Combining these two results, can construct a network f = f2 o fi such that the bounding error by any layerwise relaxation is arbitrarily large.
f approximating
Proposition J.2. Let N, a: R + be a non pol-poooloolll activation function and X Rd be convex polytope. Then, there exists network f", such that the conv (f (X)) is strict superset of (X).
Proof. Let f1 be some function where con)(fi(X)) (i(X is non-empty, e.g., the function structed in the proof of Theorem 3.3. By universal approximation, there exists a network ff such that
sup llf filla sc x
some > 0 to specified later. Let H := [1(X) and H' = (X).. This means
D(H, H') S..
Let A == D(conv(H), H). Since conv(H) H is non-empty, we have A 0. By triangle inequality and Lemma J.1, we have
D(conv(H), H) <
(H)) D(H', H)) - 2D(H H') + D(conv(HH)) H²)
< 2c + ((conv(HH)) H²).
Thus, taking c= A/4, we have
D(conv(H')) H1) (Iconv(H)) H) 2e
2 > 0.
This implies that conv (H') H' non-empty, finalizing the proof.
Theorem J.3, Let d E N, a R + R be non pon-polynomial activation function and X E Rd be convex polytope. For every constant T > O, there exists a network f Rd + R. such that {(f" X) < min ( T and u(f". 1 PI, ) 2 max f (X) +
Proof. We only prove the lower bound case; the upper bound case can be proven similarly.
By Proposition J.2, there exists network /f and an input polytope X, such that cf (X)) is strict superset of fí (X). Let e E conv(ff (X)) \ ff (X) such that å == minne (x) || c/22 > 0. Let f2 = | cll2. Thus, we have
min f2(h) 6, (X)
min heconv (X))
f2(h) = 0.
By universal approximation, there exists a network f such that
2T
sup 152 conv( (X))
f2l
5 55
for some e > 0 to be specified later. Let fo = fī fr. Then, we have
2T
min (x) >
min
f2(h) - 2T
heff (X)
2T
(U),Pi,X)) <
min
f2 [2(h) =
heronv (X)) 8
Thus, have
min (z < -2 + +
Let e T/2, we finalize the proof.
23

---

Published as a conference paper at ICLR 2026
We proceed to extend the result to cross-layer relaxations. The proof is similar that of Theo- rem 4.2, where we construct dummy layers to increase the network depth without changing the network output on X. The only difference is that now an identity layer might not be constructed exactly, but needs to he approximated.
Theorem J.4. Let d E N and let X E' be convex polytope. For every E (0, 1) and every constant T > 0, there exists a network f E No of depth L, f : Rd IR, such that {(f, Pma (1, X) I min f(X) T and u(f, P (1,a)) X) 2 max f(X) +T.
Proof. The proof directly follows that Theorem 4.2, as long as we can construct identity layers with arbitrary precision. By universal approximation, for any 0, there exists network få such that
sup (x)
x S
for i [d] where n. (X) is the projection of X onto its i-th dimension. By concatenating d such networks in width, we constructed network la such that
sup
[f((())
æ1100 S,
mE [-
and the every output neuron only depends on independent input neurons. Let cj := 21- and 6 for the k-th pseudo identity layer. Thus, by triangle inequality, the error introduced by such layers bounded by >x=1 6 S >x=1 2E < 6 for any m N+ Therefore, by following the same construction in the proof of Theorem 4.2 and taking into account the approximation error introduced by the pseudo identity layers, we can finalize the proof similar to Theorem J.3. J.3.
K
LLM USAGE
LLMs (GPT-5) were used to polish the writing of the paper, and were not used for any other purpose.
24


Reviews:
[{"review_id": "QuKHvz8h9j", "reviewer": "Reviewer_cWwu", "summary": "The submission analyzes the tightness a family of convex relaxations of neural networks. Convex relaxations are a fundamental tool for neural network verification, and are used to compute bounds on network (pre-)activations.\nThe authors focus on so-called \"multi-neuron\" relaxations, and in particular on $\\mathcal{P}_1$, which captures the convex hull of any single network layer.\nResults on its incompleteness for general networks are presented, and then followed by results on how to exploit these relaxations towards complete verification (that is, avoiding any loss of accuracy in the bounding computations).", "questions": "- It feels to me that the submission is not appropriately placed within the context of the wider convex analysis literature. Analyzing the tightness of convex relaxations is for instance extremely important within Mixed-Integer Linear Programming (MILP). Given that neural network verification over piecewise-linear function is a MILP, there are relevant results from that community [1] which should be at least cited and, better, put in relation with the presented results.\n\n- Do you see any way the lower partition complexity of multi-neuron convex relaxations could be exploited in practice over general neural networks?\n\n[1] Strong mixed-integer programming formulations for trained neural networks, Mathematical Programming, 2020, Anderson et al.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The theoretical study of the tightness of network convex relaxations is definitely an important topic for the area.\nResults-wise, I think the main contribution is Proposition 5.3, which states that $\\mathcal{P}_1$ is \"enough\" to exactly describe any locally convex part of the network. While this is not groundbreaking, I found the result interesting, along with the discussion of the resulting partition complexity.", "weaknesses": "A general weakness of the paper is that it is not \"operational\": it is exclusively theoretical, and while a short discussion of the potential implications of the results is provided, I think these results are very far from being practically useful in the area.\nA purely theoretical paper can be of course a great contribution to the literature, but I do not think the results here presented are impactful enough for that to hold.\n\nSpecifically, I think most of the presented results (except Proposition 5.3) are extremely underwhelming, as they eventually all boil down to the following statement: if the convex relaxation is not the convex hull of the entire network, the bounds will be incomplete. \nNote that the fact that optimizing a linear function over the convex hull of a set $S$ will yield the same result as optimizing over $S$ is a common textbook result in convex analysis.\n1) Sections 3 and 4 are devoted to showing that sequentially applying $\\mathcal{P}_1$ (the convex hull of a single layer) and $\\mathcal{P}_k$ (unless $k$ is the number of layers) will not yield the convex hull of the entire network. I do not quite see why it could have been the case. For instance, the Triangle relaxation is clearly the convex hull of the ReLU alone, but composing it with the preceding affine layer will not result in the convex hull of the composition.\n2) Theorem 5.1 is, I believe, just a trick to basically condense the entire input-output relationships of the whole network into a single layer, for which $\\mathcal{P}_1$ will then correspond to the convex hull of the entire network. In other words, the complexity of computing the network's convex hull is just hidden through the reformulation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xSthSE5qOO", "reviewer": "Reviewer_sc2X", "summary": "The paper studies the theoretical limits of convex-relaxation–based neural network certification. Previous work established that single-neuron convex relaxations are inherently incomplete, which is the so-called single-neuron convex barrier. This paper generalizes that observation to multi-neuron and cross-layer relaxations, claiming a universal convex barrier: even the strongest finite convex relaxation cannot achieve completeness for all networks. The authors further show that completeness can be restored through either (i) equivalence-preserving network transformations or (ii) convex partitioning of the input domain, and provide some complexity analysis comparing single- and multi-neuron settings.", "questions": "Is there any class of networks (e.g., affine-coupled, monotone, or linearly separable structures) for which completeness of convex relaxations can in fact be achieved without partitioning? It is a more interesting and non-trivial question than the result in this paper.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "- The result unifies several scattered intuitions in the verification literature into a single statement.\n- The theoretical arguments are self-contained and the structure of the results is clear.", "weaknesses": "- The central impossibility result follows almost directly from the geometric fact that convex hulls of non-convex sets are necessarily loose. A simple 2-layer, 2-neuron ReLU MLP already exhibits this property for any convex relaxation, regardless of neuron grouping or relaxation design. Thus, while the generalization to “all convex relaxations” is formally nice, it feels tautological to readers familiar with convex geometry and ReLU verification.\n\n- The conclusion that completeness can be recovered by network reformulation or domain partitioning — is already implicit in existing verification frameworks (e.g., PRIMA, β-CROWN, Planet + BaB hybrids). The paper primarily reiterates these insights under a more general theoretical framework.\n\nOverall, the paper's main results are mostly self-evident and insufficient for an ICLR paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HbHZDlHbAb", "reviewer": "Reviewer_wZ3Q", "summary": "This paper provides a theoretical analysis on the properties of multi-neuron convex relaxations when used for certifying the robustness of neural networks. Specifically, the authors extend the result from previous work that single-neuron convex relaxations are incomplete and show that multi-neuron convex relaxations are also incomplete (both layerwise and cross-layer). However, the paper then discusses a way to create a transformed network from any ReLU network for which multi-neuron convex relaxations can provide complete bounds. The authors also analyze the partitioning required for complete algorithms that use multi-neuron convex relaxations and show that it requires less partitioning complexity than single-neuron relaxations. The authors conclude with a discussion of the implications of their results in practice and recommendations for future work.", "questions": "How do you think the practical implications of the theoretical results fit in with the increased complexity of creating and working with multi-neuron convex relaxations?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is extremely well-written. The figures provide helpful visualizations for understanding the intuition behind each result.\n- The authors do a great job of backing up the math and theoretical results with intuitive wording and concrete examples.\n- The paper presents new theoretical results that extend past results from the single-neuron case to the more general multi-neuron case.\n- The authors clearly describe the practical implications of their work as well as the potential promising avenues for future work in neural network verification algorithm design based on their theoretical results.\n- The authors also discuss briefly how their results can be extended beyond ReLU networks.", "weaknesses": "The paper is focused largely on completeness for neural network verification. However, complete algorithms may not be necessary as long as the bounds from incomplete algorithms are tight enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K57rAcPM09", "reviewer": "Reviewer_ZUoG", "summary": "This paper studies the theoretical expressive power of multi-neuron convex relaxations in neural network certification. \nThe author systematically proves for the first time that even allowing layerwise multi-neuron relaxation, such methods still cannot achieve complete certification, thereby extending the 'single-neuron convex barrier' to a universal convex barrier.\nAt the same time, the paper also presents positive results: through equivalency-preserving network transformations or partitioning the input domain into convex sub-polytopes, multi-neuron relaxation can achieve completeness while maintaining the full expressiveness of ReLU networks.\nThe author further demonstrates that its partition complexity under the branch-and-bound is lower than that of the single-neuron method.\nOverall, this paper theoretically establishes the expressive boundaries of multi-neuron relaxations, clarifies its limitations and potential advantages, and provides a solid foundation for subsequent robust training and verifiable algorithms.", "questions": "1. Regarding the scope of 'universal convex barriers':Does this barrier apply to all forms of convex relaxations? Can the authors clarify its applicable boundaries and potential exceptions?\n2. Measure of boundary relaxation: The text mentions that 'the relaxation error can be arbitrarily large,' and ‘relaxation error can be unbounded.’but it does not define the specific way the error is measured. Does it refer to output range error, boundary gap, or some other norm?\n3. Applicability to non-ReLU activations: Although the paper claims that the conclusions can be extended to non-polynomial activations such as sigmoid and tanh, the proof is only briefly outlined. Could you provide a more detailed explanation of the key assumptions and limitations of this generalization?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Significant Theoretical Contribution: The paper systematically analyzes for the first time the expressiveness and completeness of multi-neuron convex relaxations, introducing the concept of the \"universal convex barrier,\" significantly extending the existing theoretical boundaries of single-neuron barriers.\n2. Rigorous Analysis and Complete Proofs: The author demonstrates clear logic in formal definitions, lemmas, and theorem derivations, with strict mathematical reasoning. The core conclusions(such as the incompleteness of multi-neuron and the conditions for completeness) are all supported by rigorous proofs.\n3. Both positive and negative outcomes, balanced viewpoints: While revealing the inherent limitations of multi-neuron approaches, the paper proposes two constructive schemes to achieve completeness (structural transformation and polytope partitioning), which are theoretically significant.", "weaknesses": "1. Insufficient discussion on feasibility: The proposed completion methods (structural transformation and polytope partitioning) are theoretically valid, but their computational complexity, scalability, and operability in large-scale networks have not been analyzed, so their practical application value remains unclear.\n2. The mathematical processes and formula representations in the examples in Part Three are not clear enough, which may affect the understanding of subsequent sections.\n3. The ⫋ symbol may not be clear in some fonts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)