acceptodds
Under review as a conference paper at ICLR 2027

CLAD: Constrained Abstract Domain for Neural Network Verification

Abstract

Neural network verification (NNV) formally verifies that a network satisfies a specified property for all inputs within a defined region. Modern NNV tools employ abstract domains to compute a sound over-approximation of the network's behavior from the given input region, thus the tightness of these abstractions essentially determines efficiency. A long line of increasingly precise domains has been developed, but they all describe the valid input region in the same restrictive way, e.g., an -norm ball. A practical input region is rarely a simple ball, but rather a combination ball with additional constraints. Verifying a network over such a region with existing abstraction produces a loose over-approximation, which results in either failing to verify a property or spurious counterexamples. We introduce Constrained Lagrangian Abstract Domain (CLAD), a new abstract domain that computes a sound over-approximation of neural networks over input regions defined by a combination of convex constraints. CLAD propagates these constraints and tightens bounds over the true feasible region. However, bounding a neuron over the intersection of these constraints has no closed-form solution, so CLAD relaxes each constraint into the objective with a Lagrange multiplier and solves the resulting max-min problem with a projected primal-dual method, alternating a projected gradient step on the input with a multiplier update. CLAD thus supports any differentiable convex constraint through automatic differentiation. We evaluate CLAD on 1944 instances across four convolutional networks with motion-blur structured perturbations with halfspace or -ball constraints. On standard unconstrained property, CLAD verifies as many instances as GCPCROWN at a similar runtime. On constrained properties, CLAD verifies 60% more instances than GCPCROWN on -ball properties, and 22% more in total.

Primary area:
interpretability and explainable AI
Keywords:
neural network verification, abstraction domain, lagrangian

Reviews

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

The paper proposes Constrained Lagrangian Abstract Domain (CLAD), a method for computing neural-network bounds over an input ball intersected with additional convex constraints. CLAD retains affine bound propagation and linear activation relaxations, while replacing conventional box-based concretization with constrained optimization. The method uses Lagrangian primal–dual updates and a supporting-tangent certificate that remains sound at intermediate iterations. The paper analyzes soundness and exact concretization under specified assumptions and reports partial Lean mechanization. Experiments on four convolutional networks and motion-blur perturbations show that CLAD certifies 1,146 class-margin properties, compared with 939 for GCP-CROWN, at generally comparable aggregate runtimes.

Critical strengths

-- The paper proposed a method -- CLAD, addresses a meaningful limitation of box-based concretization. Additional input constraints can exclude infeasible extremal points, producing tighter intermediate bounds and potentially stabilizing more activation units.

-- The method supports sound early termination in real arithmetic. Instead of using an unconverged Lagrangian value as a certificate, CLAD constructs a bound from a convex supporting tangent.

Critical weaknesses

-- In the Evaluation section, verified-instance counts and runtime metrics are appropriate, but the 1,944 instances are expanded class-margin checks derived from only three images per network/perturbation-strength combination. The paper does not report how many images have all nine margins certified. It also lacks direct measurements of bound gaps and evaluation across multiple simultaneous additional constraints. Consequently, the results demonstrate increased certification of selected subproperties more clearly than improved image-level robustness certification or general scalability to convex intersections.

-- The evaluation does not sufficiently establish the advantage over constraint-aware alternatives or isolate the contribution beyond existing bound propagation. Furthermore, although Sections 2–3 explain the conceptual difference from DeepPoly, a matched ablation using identical symbolic propagation and activation relaxations is missing. Comparisons against trusted constrained optimization on representative subproblems would also show how closely the practical solver approaches the claimed tight concretization.

Questions for authors

-- What are the exact differences between CLAD and the DeepPoly/CROWN baseline when no additional constraints are present? Are activation relaxations, intermediate-bound initialization, and optimization settings matched?

-- How many evaluated images have all nine class margins certified by each method? Please also clarify whether images are reused across perturbation strengths.

-- How do the tightness results apply to the hinge penalties used in the implementation? Please distinguish exact affine concretization from exact neural-network output bounds.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 7F65

We thank the reviewer for recognizing our meaningful contribution in broadening the support of DNN verification and for the constructive feedback to our experimental section.


W1. Image-level results and broader constraints are missing

Counts aggregate all specification types, with per-image totals counting fully certified image/specification settings.

MethodPer-classPer-image
CROWN/DeepPoly77733
alpha-CROWN92754
SDP-CROWN93054
GCP-CROWN93954
Clip-and-Verify109769
CLAD114674
  • CLAD leads both reported metrics, with each full image/specification certificate requiring all nine margins.
  • CLAD's substantially higher per-class count shows a clear precision advantage over the paper's baselines.

W2. The comparison does not isolate constrained concretization

alpha-CROWN use the same symbolic propagation approach as CLAD without handling input constraints. CLAD (1146) solved significantly more instances than alpha-CROWN (927), which shows a clear precision advantage of the constraint-aware concretization.


Q1. How does unconstrained CLAD differ from CROWN/DeepPoly?

CLAD (without linear slope optimization) and CROWN/DeepPoly baseline share the bound propagation and activation relaxation. CLAD uses the input constraints to tighten bounds on hidden neurons and network outputs on every concretization step. As a result, CLAD (1146) solved more instances than CROWN/DeepPoly (777) and alpha-CROWN (927).


Q2. How many images have all nine margins certified?

As shown in W1, CLAD solved 74 images (out of 216) with all nine margins certified, more than any baselines.


Q3.1. Do hinge penalties preserve tightness?

The tightness result carries over directly to the hinge penalty formulation. Because each hinge is zero on the feasible set and never falls below the original constraint function, the hinge bound is sound for any non-negative multipliers and is at least as tight as the bound in Theorem C.4. Assume convex constraints and under Slater's condition, the standard dual bound attains the exact optimum at optimal multipliers, which forces the hinge bound to achieve exact tightness as well. We will add this derivation to Appendix C.

Q3.2. Distinguish exact affine concretization from exact neural-network output bounds.

The concretization step optimizes on top of a linear bound that already approximates the network, so exact affine concretization is not exact neural network output bounds.

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

This work introduces the Constrained Lagrangian Abstract Domain (CLAD), an abstract domain for neural network verification over input regions defined by an ℓp\ell_p ball combined with additional convex constraints, e.g., halfspaces or ℓ2\ell_2 balls. Existing abstract domains concretize the linear bounds of each neuron over the ℓp\ell_p ball alone, which results in loose bounds when the feasible region is smaller. CLAD instead concretizes the bounds over the intersection of the ball and the constraints by relaxing each constraint with a Lagrange multiplier and solving the resulting max-min problem with a projected primal-dual method. Authors prove that every iterate of the solver gives a sound bound, allowing early stopping, and that the bound is tight under Slater's condition, mechanizing the duality results in Lean. On 1,944 instances across four convolutional networks with motion-blur perturbations, CLAD verifies 22% more instances than GCP-CROWN overall and about 60% more on ℓ2\ell_2-ball constrained properties, while matching GCP-CROWN on unconstrained ℓ∞\ell_\infty properties at a similar runtime.

Critical strengths
  • General and anytime-sound approach: CLAD handles any convex input constraint with a subgradient, and every iterate of the primal-dual solver yields a sound bound, so verification can stop early without losing soundness. Additionally, the soundness and tightness results are mechanized in Lean, which increases confidence in the correctness of the method.

  • Gains on constrained properties: When the input region includes an ℓ2\ell_2-ball constraint, CLAD verifies about 60% more instances than the strongest baselines, and the gap grows with the perturbation strength and the network size, e.g., 59 vs 18 verified instances on ConvLarge.

Critical weaknesses
  • Unfair comparison on constrained properties: Baselines only receive the smallest interval containing the constrained region, so they ignore the constraint and verify the same instances in the three property types. Therefore, all the gains in Table 1 come from constrained properties, while on unconstrained ℓ∞\ell_\infty properties CLAD verifies 316 instances vs 313 for GCP-CROWN. However, existing methods can use these constraints: SDP-CROWN [1] bounds over the intersection of an interval and an ℓ2\ell_2 ball, and Clip-and-Verify [3] solves the halfspace-constrained concretization exactly, as acknowledged in the related work. Without comparing against these methods when given access to the constraints, it is unclear whether CLAD improves over existing ways of using the constraints, which is the main question for the significance of this work.

  • Synthetic constraints and small benchmark: While the work is motivated by verifiable input spaces and preimage computation, the constraints in the evaluation are arbitrary: a halfspace through the center of the box and an ℓ2\ell_2 ball centered at a corner of the box. Additionally, only 3 images are used per network and perturbation strength. It is unclear whether the gains hold for constraints arising in practical applications.

[1] Chiu et al., SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming, ICML 2025

[3] Zhou et al., Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification, NeurIPS 2025

Questions for authors
  • How does CLAD compare with SDP-CROWN [1] when SDP-CROWN is given the intersection of the interval and the ℓ2\ell_2 ball, and with Clip-and-Verify [3] on the halfspace properties? Showing improvements over these methods would improve my assessment.

  • Clarification: Can the halfspace constraint be added as a cutting plane over the input in GCP-CROWN [2]? If so, how does it compare with CLAD?

  • Clarification: How were the halfspace and ℓ2\ell_2-ball constraints chosen? Can you evaluate CLAD on constraints arising from applications, e.g., verifiable input spaces or preimages, as motivated in the introduction?

[1] Chiu et al., SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming, ICML 2025

[2] Zhang et al., General Cutting Planes for Bound-Propagation-Based Neural Network Verification, NeurIPS 2022

[3] Zhou et al., Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification, NeurIPS 2025

3 comments
AuthorsOpenReview ↗

Response to Reviewer hdS4

We thank the reviewer for recognizing CLAD's anytime soundness, Lean mechanization, and suggestions on improving the experimental results.

W1 & Q1. How does CLAD compare with SDP-CROWN and Clip-and-Verify?

Counts aggregate all specification types. CLAD verified 1146 instances, substantially more than SDP-CROWN (930) and Clip-and-Verify (1097).

MethodVerified
CROWN/DeepPoly777
alpha-CROWN927
SDP-CROWN930
GCP-CROWN939
Clip-and-Verify1097
CLAD1146

W2. The constraints and sample are limited

We agree that the image sample and application coverage are limited. However, our work is motivated by LEVIS and Preimage Analysis (Zhang et al., 2024), which demonstrate the practical value of balls and polytopes for characterizing safe input regions. CLAD provides a generic way to retain such convex constraints during verification.


Q2. Can GCP-CROWN incorporate the input halfspace?

We thank the reviewer for the question. Yes, GCP-CROWN can encode an input halfspace as a linear cut.

For a single input halfspace, this formulation works the same way as Clip-and-Verify: the halfspace enters the linear bound through a single Lagrange multiplier, and the bound is then minimized over the box. We ran Clip-and-Verify solves for this multiplier in closed form (exactly) and applied it to every intermediate and output bound, whereas GCP-CROWN optimizes it via gradient steps. We therefore report Clip-and-Verify as the representative cutting-plane baseline, given the same halfspace and run without branch-and-bound.

A nonlinear ℓ2\ell_2-ball constraint cannot be supplied directly as a linear cut, so Clip-and-Verify receives the ball as 32 tangent halfspaces, forming a sound outer approximation.

The table below breaks down the verified instances across the four networks by constraint type (648 instances each):

MethodHalfspaceℓ2\ell_2 ball
alpha-CROWN309309
Clip-and-Verify324464
CLAD327503

Every instance verified by Clip-and-Verify is also verified by CLAD. CLAD handles convex constraint functions directly during concretization, naturally complementing cutting-plane strengthening with support for nonlinear input restrictions.


Q3.1 How were the constraints chosen?

The centered halfspace retains half the box volume in its varying coordinates by symmetry. The L2 ball is centered at the upper corner with radius equal to half the box diagonal. For input xx in a standard Linf box [l,u][l,u] with center c=(l+u)/2c=(l+u)/2, we add either the halfspace x1+x2+⋯+xn≤c1+c2+⋯+cnx_1 + x_2 + \cdots + x_n \le c_1 + c_2 + \cdots + c_n or the L2 constraint ∣x−u∣2≤12∣u−l∣2\\|x-u\\|_2 \le \frac{1}{2}\\|u-l\\|_2.

Q3.2. Were application-generated regions evaluated?

No, our experiments use constructed blur-kernel regions and do not evaluate constraint sets produced by LEVIS or Preimage Analysis. We note that those applications provide the convex region types, which are exactly the same as ones we evaluated in this paper, that CLAD supports natively.

Thanks for the reply and the additional results. I have increased my score to a 3. Please add the additional results to the manuscript.

We thank you for your feedback and comments. We'll revise the paper to include clarifications and new results.

Reviewer_4ofbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes CLAD, an abstract domain for verifying neural networks over input regions with convex constraints. CLAD incorporates the constraints into bound concretization using Lagrangian relaxation and a projected primal-dual solver. The paper derives a sound bound for each iteration, studies when the dual problem is tight, and mechanizes selected results in Lean. The experiments use four convolutional networks with motion-blur perturbations and additional halfspace or ℓ₂-ball constraints. CLAD verifies more output-margin instances than the baselines on the constrained properties.

Critical strengths
  1. The paper addresses a problem that matters for verification. Replacing a constrained input region with an enclosing box can introduce inputs that are not feasible, and CLAD provides a way to use the original constraints when computing bounds.

  2. The formulation can handle convex constraints beyond linear inequalities, provided that subgradients are available. The authors also explain how to obtain a sound bound without exactly solving the inner optimization problem.

Critical weaknesses
  1. The comparison does not establish how much of CLAD’s advantage comes from its solver. The baselines receive an enclosing interval, while CLAD also receives the original constraints. The results therefore show the benefit of retaining constraint information, but leave open how CLAD compares with other methods that use the same information. This also makes it difficult to assess the contribution relative to existing constraint-driven bound-tightening methods.

  2. The experimental evidence is limited. The benchmark covers one family of structured perturbations and uses three correctly classified images per network, perturbation strength, and property combination. Each image produces nine class margins that are counted as separate instances. These margins are neither independent images nor complete classification certificates. A larger sample and image-level results would help establish how often the gains translate into fully verified properties.

Questions for authors
  1. Could the authors compare CLAD with a constraint-aware baseline using the same input constraints and similar computational budgets? For halfspace constraints, a comparison with Clip-and-Verify or an appropriate adaptation would be helpful. For smaller problems, an LP or SOCP solver could provide a reference for both bound quality and computation time.

  2. How many images are certified against all competing classes? Please also clarify how the images were sampled and, if available, report results on a larger sample or across different samples.

  3. What practical assumptions motivate the particular halfspace and ℓ₂ constraints used in the experiments? How much do they restrict the original perturbation set? Results with multiple simultaneous constraints or other constraint configurations would help assess the scope of the method.

  4. Could the authors clarify the tightness and convergence claims in the main text? Strong duality concerns the constrained optimum of a fixed propagated linear bound, whereas the implemented solver uses early stopping and differs from the variant covered by the convergence theorem. How close are the returned bounds to the corresponding constrained optima in practice?

  5. The implementation uses floating-point arithmetic without directed rounding. How do the authors assess numerical errors, particularly when a verification margin is small? It would help to distinguish the real-arithmetic guarantee from the guarantee provided by the implementation.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 4ofb

We thank the reviewer for recognizing that we are addressing an important problem in DNN verification and the constructive suggestions on constraint-aware baselines and image-level results.


W1, W2, Q1 &Q2: CLAD vs constraint-aware baselines

To evaluate CLAD against baselines using the same constraint information, we added SDP-CROWN and Clip-and-Verify as constraint-aware baselines under identical input constraints.

MethodPer-classPer-image
CROWN/DeepPoly77733
alpha-CROWN92754
SDP-CROWN93054
GCP-CROWN93954
Clip-and-Verify109769
CLAD114674
  • CLAD outperforms both baselines across both metrics, certifying 74 per image instances (vs. 69 for Clip-and-Verify and 54 for SDP-CROWN) and 1,146 per class instances (vs. 1,097 and 930).
  • CLAD leads both reported metrics, with each full image/specification certificate requiring all nine margins.
  • CLAD's substantially higher per-class count shows a clear precision advantage over the baselines.
  • Conceptually, CLAD contributes a generic concretization operator for arbitrary convex constraints and their subgradients.

W1 & Q4.3: “CLAD vs exact LP/SOCP“

In our evaluation, using LP solvers for verify the same instances cannot find the solution within 300s when all other baselines completed. In each constraint-aware concretization step, CLAD returned identical bounds to the LP solver for solely concretization and was 5-10x faster.


Q3. What motivates the added constraints?

Q3.1. Why use halfspaces and L2 balls?

The motivation comes from verifiable input regions and preimage analysis (already discussed in the introduction):

  • Levis constructs verifiable regions using balls
  • Preimage Approximation (Zhang et al., 2024) approximates preimages using polytopes defined by halfspaces.

In our evaluation, halfspaces and L2 balls exercise CLAD's central capability: retaining linear and nonlinear convex restrictions during concretization.

Q3.2. How much do they restrict the base region?

The centered halfspace retains half the box volume in its varying coordinates by symmetry. The L2 ball is centered at the upper corner with radius equal to half the box diagonal. Formally, for input xx in a standard Linf box [l,u][l,u] with center c=(l+u)/2c=(l+u)/2, we add either the halfspace x1+x2+⋯+xn≤c1+c2+⋯+cnx_1 + x_2 + \cdots + x_n \le c_1 + c_2 + \cdots + c_n or the L2 constraint ∣x−u∣2≤12∣u−l∣2\\|x-u\\|_2 \le \frac{1}{2}\\|u-l\\|_2.

Q3.3. What about simultaneous constraints?

The formulation of CLAD can conceptually handle multiple convex constraints, with one multiplier per constraint in each affine concretization.


Q4. What do tightness and convergence guarantee?

Q4.1. What does tightness establish?

Assume all additional constraints are convex, under the Slater condition (Thm. C.4), strong duality holds with zero duality gap (min⁡μ≥0d(μ)=ui⋆\min_{\mu \ge 0} \mathrm{d}(\mu) = u_i^\star), so the optimal dual bound matches the exact constrained optimum of the back-substituted linear bound over B∩H\mathcal{B} \cap \mathcal{H}.

This establishes tightness strictly for the concretization of a fixed linear bound, eliminating over-approximation error from input constraints. It does not imply exact neural-network output bounds, which remain an over-approximation due to convex/linear relaxations of nonlinear activations (e.g., ReLUs) accumulated during bound propagation.

Q4.2. What guarantees hold when optimization stops early?

When optimization stops early, the solver returns the dual function d(μ)\mathrm{d}(\mu) at the current, non-optimal μ\mu, where weak duality guarantees d(μ)≥ui⋆\mathrm{d}(\mu) \ge u_i^\star (Thm. C.1). This provides anytime soundness: every iterate produces a valid bound for any μ≥0\mu \ge 0, permitting safe early stopping without requiring solver convergence.


Q5. What numerical guarantees does the implementation provide?

We proved CLAD is guaranteed to yield sound bounds (Thm. 3.1 and 3.2). The proofs are mechanized in Lean 4. Similar to other baselines (CROWN, DeepPoly, GCP-CROWN), CLAD run in standard floating-point arithmetic (Apdx. D).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Follow-up on our rebuttal

Dear reviewers,

We believe we have addressed all questions. Please let us know what you think about our rebuttal. We'd be happy to engage in more discussions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.