acceptodds
Under review as a conference paper at ICLR 2027

Training Mixed-Monotone Neural Networks for Verification Without Set Propagation

Abstract

​Most formal verification approaches for neural networks conservatively enclose the output set of the neural network. However, computing a tight output enclosure is in general computationally hard. We sidestep this challenge with a novel neural network architecture that realizes mixed-monotone functions as the difference of monotone subnetworks. By utilizing the theory on mixed-monotone systems, this reduces the computation of a tight output enclosure from complicated set propagation to two simple forward passes of opposite corners of an input interval. Moreover, because the size of resulting enclosure is a closed-form function of the weights of the neural network, we can directly minimize it during training. We prove a lower bound on the size of any such enclosure, given by the monotone variation of the represented function, which makes the tightness of the enclosure measurable against an optimum. Our evaluation uses regression and dynamical-system benchmarks, to demonstrate that our training reaches within of this lower bound at no cost in prediction accuracy. Computing our enclosure is orders of magnitude faster than CROWN and -CROWN and on deep networks it is also tighter than zonotope propagation and CROWN, and stays within of -CROWN.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
neural network verification, mixed-monotone systems, monotone neural networks, reachability analysis, verification-aware training

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_evjbOpenReview ↗
Rating
3(+2)
Confidence
4
Informativeness
2(+1)
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes to use a neural architecture that is a *mixed-monotone function; specifically, the paper investigates the difference of two sign-constrained (think: monotonic) networks. The motivation is that interval output bounds (for given input bounds) can be computed by normal forward passes of only two normal inputs (namely the minimum and maximum bounds). The experiment investigates the performance of this architecture and how the bound propagation compares to other bound-propagation tools.

Critical strengths
  • The observations made in this paper are interesting and worthy publishing.
Critical weaknesses
  • The difference of two monotonic networks does not sound convincing to me for any but the simplest tasks. As the authors argue, they obtain interval bounds, which are known to be too coarse in most practical cases.

  • I am not sure that the paper contains significant conceptual contributions. The theory of mixed-monotone functions has been developed before, and the authors went for the simplest possible choice (which was also known before): the difference of two monotonic networks.

  • The experiments are not sufficient to convince me. While the networks are quite deep (up to 8 layers), I could not find any mention of how many neurons were used, and from the very simple environments, I presume that the answer is "not many." I really think that the practicality of mixed-monotone networks must be demonstrated viable in challenging scenarios (beyond simple control tasks) to be competitive at a top ML conference.

  • The paper contains quite a few obvious errors. This lowers my confidence in the paper significantly. Examples:

    • Definition 2 is not sufficient for a neural network to be monotonic. It misses the requirement that the activations are monotonic.
    • Example 1 is completely broken. Eq. (3) should say 2 \max(1-x, 0) to match the figure. Two lines below, the interval computation is also wrong (0 - (-2) is not -2). Similarly, the second network is also broken.
Questions for authors
  • The significance of the contribution would be demonstrated if you can do something that other approaches cannot. So you need to take a network that is too large for other approaches and verify an interesting property. Can you do that?

  • If your approach computes IBP results, why do you improve over the zonotope approach in Fig. 3? I expect your bounds to be looser. Also, why do you not show the results for (\alpha-)CROWN?

7 comments

Dear reviewer evjb,

we thank you for your detailed feedback and for finding our core observations interesting. We are particularly grateful for your precise list of technical corrections. We have fixed the omission in Def. 2 and clarified Fig. 2, which caused the confusion about Example 1. For your convenience, we mark the changes in our revised paper in blue.

We have rewritten the appendix for clarity and therefore marked it entirely in blue; the changes most relevant to your review are the revised proof of Prop. 3 (App. A.1), the architectures and parameter counts of all compared neural networks (App. A.4 and Tab. 7), and the details of the evaluation over multiple time steps in Fig. 3, including a corrected size of the zonotope enclosure (App. A.9).

W4 — Errors (Def. 2 and Example 1) Thank you for catching the omission in Def. 2. You are correct that it required a non-decreasing activation condition, which we have now added. Regarding Example 1, we apologize for the confusion about the figure. The math in Eq. (3) is correct as written, but Fig. 2 plots the negated subnetwork (−Φ−-\Phi_{-}), causing Φ−(2)=2\Phi_{-}(2) = 2 to visually appear as −2-2. To prevent this confusion, we have updated the caption of Fig. 2. We hope this revision makes the example clearer and easier to follow.

W3 — Network size We thank you for pointing it out. Each subnetwork of our fully connected networks has 32 neurons per hidden layer, i.e., 194 to 26k parameters in total (Tab. 7); the new MNIST CNN has 1.7M parameters. We ensured the total parameter count of every compared baseline architecture agrees with ours to within 2%. We have added this detail to Sec. 5 and provided a comprehensive parameter count table and architecture details in App. A.4.

W1/Q2 — IBP, zonotopes, and α\alpha-CROWN On our architecture, the enclosure coincides with IBP. IBP is coarse on general networks because it adds an abstraction error at every layer; on our architecture it adds none, since each monotone subnetwork is evaluated exactly at the two corners of the input interval. The only overapproximation stems from the decomposition, which our training minimizes and Prop. 3 bounds from below. This relies on the sign constraints: for the monotone Lipschitz-constrained subnetworks (Kitouni et al., 2023), IBP is looser by factors of 1.15 to 1.49 (App. A.6). Our contribution is thus not a tighter bound computation for a given network, but an architecture on which computing bounds does not require a per-layer abstraction error, together with a training objective that minimizes the enclosure size. Regarding Fig. 3: the two enclosures are computed for different networks (App. A.9), ours for our trained mixed-monotone network and the zonotope for an unconstrained network trained on the same data. The zonotope accumulates abstraction errors over layers and time steps, whereas our enclosure has no per-layer abstraction error and, for the cooperative Tanks system, a nearly exact decomposition (Tab. 3). On the same networks (Tab. 2, Tab. 10), α\alpha-CROWN is tighter but up to 20,600$\times$ slower (at eight layers, our enclosure is 5.1% larger). We omitted it from Fig. 3 because of this runtime (4.3 s vs. 0.21 ms per input set at eight layers, Tab. 2).

W2 — Novelty We completely agree that the mathematical difference of two monotone networks is an established concept and we have updated the related work accordingly. We believe our core contribution lies in how this structure is utilized: explicitly training the decomposition to minimize enclosure size (Eq. 5), computing bounds without layerwise set propagation. Moreover, Prop. 3 characterizes the smallest enclosure that any difference of two monotone functions can achieve (the total variation along chains, which is attained), so we can measure how close a trained decomposition is to the optimum (within 0.5%, Tab. 3).

Q1 — Scaling to harder tasks We appreciate you pushing us to demonstrate practicality beyond simple control tasks. We have added a convolutional MNIST benchmark with 1.7M parameters (Tab. 6). At an equal parameter count, our enclosure certifies 94.60% of the test images at ϵ=0.1\epsilon = 0.1 in 0.59 ms per image from two forward passes. Zonotope propagation on the same network certifies 92.30% in 825 ms per image, and α\alpha-CROWN exceeds the budget of 100 s on every test image; without a budget, it requires at least 3,263 s per image on the first 23 test images (App. A.6). Our certified accuracy stays below that of state-of-the-art certified training (about 98% on MNIST at ϵ=0.1\epsilon = 0.1), which we state in our limitations; our contribution is the cost of the enclosure, not the certified accuracy.

Thanks for the clarifications.

The new results indeed look promising. How did you select ϵ=0.1\epsilon = 0.1? For MNIST, does this mean you analyze robustness up to 25 grayscale levels for each pixel (25/255≈0.125/255 \approx 0.1)?

Regarding the precision, I still do not understand why your approach is more precise than the zonotope baseline. As far as I understand, it should be expected that you get quite loose output bounds as shown in Figure 1. This is because IBP loses dependencies in the many multiplications in the layers. You only obtain these bounds faster than before. The zonotope baseline, while not perfect, should preserve at least some of these dependencies. Am I missing something?

Thank you for your follow-up and for your positive assessment of the new results. Your question showed us that the paper did not explain why IBP is precise on our architecture; we have added this explanation, and that all methods in Tab. 2 run on the same networks, to Sec. 5.2 (marked in blue).

Choice of ϵ\epsilon. We use ϵ=0.1\epsilon = 0.1, one of the standard perturbation radii for MNIST in certified training (Gowal et al., 2019; Mao et al., 2024; Sec. 5.4). Yes: with pixel values in [0,1][0, 1], every pixel can change by up to ±25.5\pm 25.5 of 255255 gray levels simultaneously.

Precision. Fig. 1 is a schematic; its sets are not computed. You are right that IBP loses dependencies in the linear layers of general networks. This happens when the neurons of a layer attain their bounds at different inputs, which requires weights of mixed signs. In our subnetworks, all weights are non-negative and all activations are non-decreasing, so every neuron attains its lower bound at the lower corner x‾\underline{x} and its upper bound at the upper corner x‾\overline{x} of the input interval. IBP therefore computes exactly the ranges [Φ+(x‾),Φ+(x‾)][\Phi_+(\underline{x}), \Phi_+(\overline{x})] and [Φ−(x‾),Φ−(x‾)][\Phi_-(\underline{x}), \Phi_-(\overline{x})]: within the subnetworks, there is no dependency to lose. The only lost dependency is the one between Φ+\Phi_+ and Φ−\Phi_-, whose extremes lie at opposite corners. This loss occurs once, at the output; our training minimizes it (Eq. (5)), and Prop. 3 bounds it from below. With the enclosure penalty, our enclosure is within 0.4% of the sampled image (Tab. 3). Hence, we do not compute loose bounds faster; we change the network so that its interval bounds are exact up to the decomposition, and we train the decomposition to be tight.

Zonotope propagation preserves dependencies through the linear layers, but it relaxes every activation whose input interval is not within a linear region, i.e., every unstable ReLU and every tanh neuron, and each relaxation adds an error term that all subsequent layers propagate. In Tab. 2 and Tab. 10, we propagate one zonotope through both subnetworks of the same networks (trained without the enclosure penalty, β=0\beta = 0), so it even keeps the dependency between Φ+\Phi_+ and Φ−\Phi_- that our enclosure loses. Still, its tightness degrades from 1.08 at two layers to 1.44 at eight layers, while ours improves from 3.58 to 1.05: the zonotope is tighter for shallow networks, ours for deep ones. Tab. 5 shows the same crossover over the radius against the unconstrained baseline: the radius above which our enclosure is smaller shrinks from 1.0 at three layers to 0.025–0.04 at six and eight layers. On MNIST, zonotope propagation through our network certifies 92.30% of the test images and our enclosure 94.60% (Tab. 6).

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

This paper proposes a neural network architecture that makes output enclosures efficient to compute. The network is constructed as the difference of two sign-constrained monotone subnetworks, allowing an output enclosure for a box-shaped input set to be computed through two forward passes without layerwise set propagation. The authors also introduce a training objective that combines the regression loss with a penalty on enclosure width, so that enclosure tightness can be directly optimized during training. On the theoretical side, they derive a lower bound on enclosure size based on the monotone variation of the represented function within this class of decompositions.

The experiments evaluate prediction accuracy, enclosure tightness, and computational cost on analytic regression and dynamical-system benchmarks. The paper also investigates scalability with respect to network depth, input dimension, and repeated evaluations in a closed-loop setting.

Critical strengths

This paper introduces a clever mixed-monotone neural network architecture that avoids layerwise set propagation during verification, thereby preventing the associated accumulation of abstraction errors. The core idea is simple and intuitive, and it also allows enclosure tightness to be directly optimized during training. The theoretical analysis provides a lower bound on enclosure size based on monotone variation, while the experimental evaluation examines prediction accuracy, enclosure tightness, computational cost, and scalability from several perspectives.

Critical weaknesses

Some aspects of the experimental design could be strengthened, and several results would benefit from further explanation. Please see the Questions section for details.

Questions for authors
  1. The accuracy comparison in Table 1 considers a one-dimensional analytic function and two low-dimensional dynamical systems. Although both architectures achieve high R2R^2 scores, these benchmarks may not fully reveal differences in their approximation capabilities. How does the proposed architecture perform on more demanding tasks? Do the monotonicity constraints on the two subnetworks introduce trade-offs in predictive accuracy or parameter efficiency? Extending the comparison to more complex tasks will help clarify these trade-offs.

  2. Table 7 shows a substantial improvement in enclosure tightness as network depth increases. While avoiding the accumulation of layerwise abstraction errors helps explain the method’s scalability, it does not directly explain why enclosure tightness improves with depth. Could the authors clarify the mechanism underlying this trend and discuss whether it is a general phenomenon or specific to the benchmark and training setup considered?

3 comments

Dear reviewer Bk7X,

we greatly appreciate your positive assessment of our work and your thoughtful questions. Your feedback directly highlighted where our experimental evaluation needed expansion, and addressing it has strengthened the paper. For your convenience, we mark the changes in our revised paper in blue.

We have rewritten the appendix for clarity and therefore marked it entirely in blue; the changes most relevant to your review are the architecture and training details of the new MNIST experiment (App. A.4 and Tabs. 7 and 8).

Q1 — Harder tasks and trade-offs We completely agree that evaluating the trade-off on more complex tasks is essential. In response, we have added a convolutional MNIST benchmark to the main text (Tab. 6): Our network achieves 97.30% clean accuracy (compared to the baseline's 99.50%) and certifies 94.60% of test images from just two forward passes. We now explicitly discuss this trade-off in the text: the monotonicity constraints do incur a minor cost to clean accuracy in exchange for the highly efficient certification guarantees.

Q2 — Why tightness improves with depth This is a very insightful question. You are right that avoiding per-layer abstraction errors only explains why our tightness does not degrade with depth. The networks in Tab. 7 of the submission (now Tab. 10) are trained without our enclosure penalty (β=0\beta = 0). The size of our enclosure equals the summed increase of both subnetworks over the input interval (Eq. (7), App. A.1), so it is small only if Φ+\Phi_+ rises only where the target rises and Φ−\Phi_- only where it falls. We attribute the improvement to the higher expressivity of deeper subnetworks, which makes such decompositions easier to represent, so that training finds them even without the penalty. We observed this trend on the scalar analytic model and do not claim that it is general. Importantly, depth is not required for a tight enclosure: with the enclosure penalty (β≥0.05\beta \geq 0.05), a three-layer network already reaches a tightness of at most 1.004 (Tab. 3). We have clarified this in Sec. 5.4.

Dear reviewer Bk7X,

As the discussion period is coming to an end, we would like to check whether our response has addressed your questions about the accuracy trade-off and the effect of depth on tightness, and whether any open concerns remain.

In the discussion with Reviewer evjb, we additionally showed that our architecture is a universal approximator: the sign constraints restrict how a function is decomposed, not which functions can be approximated. This complements our answer to your question on trade-offs, where the constraints cost 1.1 percentage points of clean accuracy on MNIST at equal parameter count (Tab. 6).

Thank you for the response and the additional experiment, which address my main concerns. I will maintain my original rating of 3.

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

The paper studies the verification problem for neural networks, more precisely, the task to give bounds on the output set. While previous work usually propagated input intervals through the network, the paper proposes a different approach. It is based on a simple observation: if we represent a function f as difference of two monotone functions g and h, so f = g - h, then on an interval [a,b], the range f([a,b]) is enclosed in [g(b)-h(a),g(a)-h(b)].
To make use of this, the authors propose to train a network that is the difference of two monotone subnetworks, where monotonicity is achieved by imposing non-negativity on the network weights. The authors introduce an additional regularization term (Equation 5) to strengthen the bounds on the ranges in the training process, as the convex decomposition of a function is not unique.
The efficiency of the method is shown with computational experiments, in particular highlighting lower running times compared to existing verification tools.

Critical strengths
  • It is nice how a simple idea for modifying the neural network architecture gives tight bounds on output ranges with better running times in the presented experiments.
Critical weaknesses
  1. The paper omitted existing work around DC-decompositions. In particular, a significant part of the setup of two monotone subnetworks already appears in the paper `Hidden Monotonicity: Explaining Deep Neural Networks via their DC Decomposition' (Zimmermann, Loho; CVPR 2026) in the context of explainability; though the latter does not discuss output ranges and the regularization (Equation 5) is new. Even further, the latter paper uses the same network structure to train a DC-decomposition but also addresses how the idea of using a DC-decomposition can be applied to already trained networks, which is not addressed here.

  2. The description of the benchmarks in Section A.2 indicate that the considered tasks are rather easy and low-dimensional anyway. Furthermore, also the description of the conceptual insights seems overly complicated and imprecise in detail; for example:

  • In Definition 2, there should be more conditions on the nonlinear function, otherwise the network does not represent a convex function.
  • Definition 1, Proposition 1 and Proposition 2 mostly rely on Coogan 2020 or Coogan&Arcak 2015; though looking into these references it is not entirely clear how to match their statements to the presented statements and actually it is anyway simple to state directly for a DC-decomposition as explained above.
Questions for authors
  1. Do I understand correctly that your argument for your approach is based on the experiments, showing that your enclosures are similar to the tightness of existing approaches but you have a significantly better running time for more layers? Please elaborate on your choice of experiments to show that it is also a viable to tool for more complicated tasks, or discuss limitations of your experiments.

  2. Can the paper be generalized to a framework using DC-decompositions more generally?

4 comments

Dear reviewer NDDe,

we thank you for your careful reading and constructive feedback. For your convenience, we mark the changes in our revised paper in blue.

We have rewritten the appendix for clarity and therefore marked it entirely in blue; the changes most relevant to your review are the revised and more precise proof of Prop. 3, which now proves step by step that the lower bound is attained (App. A.1), and the details of the new MNIST experiment (App. A.4).

W1 — Zimmermann & Loho (2026) Thank you for pointing us to this related work; we have updated the related work section. You are correct that they also utilize a difference of two monotone networks. The key distinction is their application: they utilize this structure for explainability. Our approach, by contrast, actively trains the decomposition to achieve a tight output enclosure, leveraging mixed monotonicity without layerwise set propagation.

W2a — Def. 2 (Nonlinear Function Conditions) Thank you for catching this oversight that additional conditions were needed. We have corrected Def. 2 to explicitly require a non-decreasing activation function. For our approach, convexity is not required; Prop. 2 relies solely on the monotonicity of sub-networks.

W2b — Coogan & Arcak Citations We appreciate you pushing us for greater precision here. To ensure the connections to the foundational theory are clear, we have updated the citations of Prop. 1, which now specifically cites Def. 2, Def. 3, and Thm. 1 of Coogan & Arcak (2015) specialized to the disturbance-free case.

Q1 — Choice of experiments & harder tasks Partly: besides the experiments, our argument rests on the complexity analysis (Sec. 3) and on Prop. 3, which measures how close a trained decomposition is to the optimum. Our initial focus on small benchmarks was deliberate, as they allow us to compare our bounds against the densely sampled image and the theoretical lower bound from Prop. 3. However, to better demonstrate scalability, we have added a convolutional benchmark on MNIST (Tab. 6). Comparing networks with an equal parameter count, our architecture certifies 94.60% using just two forward passes. Furthermore, our claim extends beyond runtime: on deep networks, our enclosure actually becomes tighter than zonotope propagation and CROWN because we avoid accumulating per-layer abstraction errors (e.g., Tab. 10 shows our bounds tightening to 1.05 with depth, while zonotope degrades to 1.44). We discuss the remaining limitations in Sec. 6.

Q2 — General DC decompositions Yes, the framework can be generalized. Because every ReLU network admits a difference of two monotone networks, Prop. 2 can theoretically apply to any already-trained network. However, the standard decomposition of a trained ReLU network, which splits its weights by sign, yields bounds no tighter than IBP; a tight decomposition therefore has to be obtained during training. More broadly, a decomposition function does not strictly need to be separable; our architecture represents a highly efficient, separable special case. We have added a brief discussion of this generalization potential in the conclusion.

Dear reviewer NDDe,

As the discussion period is coming to an end, we would like to check whether our response has addressed your concerns, in particular regarding the relation to Zimmermann & Loho (2026), the scope of our experiments, and the generalization to DC decompositions, and whether any open concerns remain.

In the discussion with Reviewer evjb, we additionally showed that our architecture is a universal approximator: every ReLU network is a difference of two monotone maxout networks (Hertrich & Loho, 2026), whose parts our sign-constrained subnetworks can approximate (Runje & Shankaranarayana, 2023); hence, our architecture is a universal approximator.

If our responses have addressed your concerns, we would appreciate if you would consider updating your score.

I appreciate that the authors added clarifications concerning existing literature. I still think that Section 2.1 is overly complicated: can't you just write explicitly the (very simple?!) derivation of the property for differences of convex functions?

While I still think that there is overall not much technical novelty, it is positive to see how the ideas lead to nice computational results. Therefore, I decided to raise the score.

Thank you for raising your score. We agree that Sec. 2.1 is more general than needed: we introduced mixed monotonicity, on which our architecture is based, but we only use the difference of monotone functions. For the final version, we will specialize Sec. 2.1 and derive the enclosure explicitly.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the rebuttal and discussion

We thank the reviewers for their constructive feedback. The reviewers found the core idea clever and simple (Bk7X, NDDe) and the observations worth publishing (evjb). We summarize the main improvements in the revision and the discussion (changes are marked in blue):

  1. Scalability (all reviewers). We added a convolutional MNIST benchmark with 1.7M parameters (Tab. 6): at ϵ=0.1\epsilon = 0.1, our enclosure certifies 94.60% of the test images in 0.59 ms per image, compared to 92.30% in 825 ms for zonotope propagation on the same network, while α\alpha-CROWN exceeds a budget of 100 s per image. All network sizes are now reported (Tab. 7).
  2. Precision (evjb). We clarified why our enclosure is tight although it coincides with IBP: on sign-constrained subnetworks, IBP loses no dependencies, so the only overapproximation stems from the decomposition, which our training minimizes.
  3. Expressivity (evjb, Bk7X). We showed that our architecture is a universal approximator, with a formal proof to be added in the final version.
  4. Related work and corrections (evjb, NDDe). We added the related work on differences of monotone networks (Zimmermann & Loho, 2026; Hertrich & Loho, 2026), completed Def. 2, clarified Example 1, specified the citations of Prop. 1, and rewrote the proof of Prop. 3.

We especially thank Reviewer evjb for an engaging and constructive discussion. Reviewer evjb raised their score twice and noted that they now have "a very different view of the paper".

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.