acceptodds
Under review as a conference paper at ICLR 2027

Formal Verification of Kolmogorov-Arnold Networks

Abstract

Motivated by the Kolmogorov-Arnold representation theorem, Kolmogorov-Arnold Networks (KANs) are a novel neural network architecture that replace the weight matrices and fixed activation functions of a multi-layer perceptron with a learned univariate spline on every edge and an unweighted sum on every node. They have quickly become popular, being utilized as scientific surrogates, safe controllers and barrier certificates, but attempts to verify them are limited. Mainstream neural network verification tools have no spline operator, and conversion from a KAN with a grid of cells to a ReLU network inflates the network by a factor of . Therefore, this work develops formal verification utilizing set-based reachability for KANs by directly considering its unique architecture. We show that degree-1 KANs without the base branch admit exact verification, and that KANs of degree or with the base branch admit sound verification. We compare head-to-head a method family instantiated on the KAN structure; using interval bound propagation, CROWN-style bounds, mixed-integer linear programs (MILPs), and star-set reachability. We demonstrate formal verification of five classes of properties for trained KANs, namely robustness, output ranges, barrier conditions, monotone ordering and one-step reachability; including certified robustness for an adversarially attacked -input MNIST KAN and all three conditions of a control barrier certificate whose barrier and controller are both KANs. Our literature-based case studies collectively can be considered a small KAN verification benchmark, *e.g.* for VNN-COMP.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Kolmogorov-Arnold Networks, Neural Network Verification, Certified Robustness, Reachability Analysis, Barrier Certificates

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_bfR1OpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates formal verification of Kolmogorov-Arnold Networks (KANs), whose learned spline-based edge functions are not directly supported by mainstream neural network verification tools. The authors adapt several established verification techniques, including IBP, CROWN, α/β-CROWN, MILP, and star-set reachability, to KANs.

The paper establishes exact reachability for degree-1 KANs without base branches and sound over-approximation for higher-degree KANs. Experiments cover 26 trained networks across adversarial robustness, output ranges, monotone ordering, reachability, and control-barrier certification.

Critical strengths
  • Comprehensive verification framework. The paper systematically adapts multiple verification techniques to KANs, with useful theoretical results on knot-cell partitioning, exact reachability, and sound spline relaxations.

  • Diverse applications. The evaluation goes beyond adversarial robustness to include scientific and control applications. In particular, verification of all three barrier conditions for trained KAN-based barrier and controller networks is compelling.

Critical weaknesses
  • Limited methodological novelty: Much of the proposed methodology appears to adapt established neural network verification techniques to KANs. In particular, CROWN-style linear relaxations, optimized slopes, and branch-and-bound have already been extended to general nonlinear operators, as in auto_LiRPA and GenBaB. Similarly, exact verification of degree-1 KANs follows naturally from their piecewise-affine structure. While knot-aware partitioning and spline-tail handling are useful, it is unclear whether they constitute a sufficiently substantial algorithmic advance beyond existing general nonlinear verification frameworks.

  • Missing comparison with general nonlinear verifiers. The paper compares its native KAN-specific α/β-CROWN implementations against released CROWN tools applied to ReLU-converted networks, but not against a general nonlinear verifier equipped with B-spline relaxations. Given that frameworks such as GenBaB already handle general nonlinear operators, this comparison is important for establishing whether the proposed KAN-specific methods provide benefits beyond adding support for a new operator. The current experiments do not clearly establish this distinction.

  • Limited scalability evidence: The high-dimensional experiments primarily use shallow MNIST and Fashion-MNIST networks. While these demonstrate scalability in input dimension, they provide limited evidence of scalability to deeper nonlinear compositions. Given the paper's motivation from scientific and control applications, experiments on deeper, more realistic KANs would be more convincing.

Rebuttal

The rebuttal has addressed most of my concerns and therefore I am increasing my score.

Questions for authors
  • What are the key algorithmic differences between the proposed KAN-specific β-CROWN and existing general nonlinear verification methods such as GenBaB?

  • Why is there no direct comparison against a general nonlinear verifier equipped with certified B-spline relaxations?

  • Can the authors provide additional depth-scaling experiments, preferably on more challenging scientific or control applications?

  • In which regimes does native KAN verification consistently outperform ReLU-conversion-based approaches?

  • How are formal soundness guarantees maintained under floating-point arithmetic and numerical solver tolerances?

8 comments
AuthorsOpenReview ↗

W1 and Q1, novelty and the differences from GenBaB.

Thank you for the detailed review, particularly highlighting the comparison with general nonlinear verifiers and the need for deeper networks. We answer each question with new experiments; added text is blue in the revised PDF.


We agree that the bounding and branching algorithms are those of α,β\alpha,\beta-CROWN and GenBaB and we now mention this in Sec. 5.3, "Relation to branch and bound for general nonlinearities". The contribution is the structure that these algorithms need in order to work on a KAN, together with the proofs that it is sound and, at degree 1, exact and complete. We believe there is also novelty as it can be used as a future VNN-COMP benchmark.

The new experiment E24 measures that structure inside α\alpha,β\beta-CROWN, by giving GenBaB our relaxation as a B-spline operator and changing aspects:

AspectGenBaBThis paperEffect inside GenBaB (E24)
edge relaxationgeneric operators on an exact truncated-power rewritingcertified parallel relaxation of each B-spline edge, quadratic gap (Lemmas 3, 4)354 → 490 of 511 (table below)
case splitsper nonlinearityone split of an input xpx_p fixes all mm edges leaving it (Lemma 2); the case count of exact enumeration does not grow with the output widthper-edge splitting inside GenBaB: +4
branch pointspre-optimized offlinethe knots, known in advance; exact and complete at degree 1 (Theorem 1, Corollary 1)knots −3; branch points optimized online −2
zero tailspolynomial pieces onlythe certified offsets carry the tails; extrapolating is unsound (Proposition 1)soundness
last layerper edgeone combined edge per input of the last layer0
derivative networks–sound discharge of the Lie-derivative barrier condition (Proposition 2)needed for the barrier

Our contribution therefore goes beyond running GenBaB on a KAN: adding our certified B-spline relaxation to GenBaB proves 136 more of the 511 provable queries (354 → 490), whereas changing GenBaB's branching choices moves the count by at most 4. The other rows add guarantees rather than speed: exact and complete verification at degree 1, soundness outside the spline grid, and the barrier condition through the derivative network.

Sec. 5.3 ("Relation to branch and bound for general nonlinearities") states this comparison in the main text, and App. C.15 (Table 15) gives the full results.

AuthorsOpenReview ↗

W2 and Q2, comparison with a general nonlinear verifier.

We have added the comparison (App. C.15, Table 15): our native α\alpha-CROWN and β\beta-CROWN, the KAN implementations of Sec. 5.3 that use our structure directly, against the released α,β\alpha,\beta-CROWN with GenBaB, in double precision, on 538 degree-3 queries of Table 2 under the same 60 s end-to-end budget, once on an exact rewriting of the KAN in operators the tool supports (truncated-power form) and once with a B-spline operator that carries our certified parallel relaxation and leaves the branching to GenBaB (with timeouts in parentheses):

Group (#, ceiling)native α\alpha-CROWNnative β\beta-CROWN, default / anytimeGenBaB, truncated-power formGenBaB + B-spline operator
rob., 2–30 inputs (240, 224)223224 / 224136 (81)224
rob., 784 inputs (48, 37)21 (16)21 (16) / 3722 (15)37
CS, boxes (250, 250)214250 / 250196 (50)229 [227]
all (538, 511)458 (16)495 (16) / 511354 (146)490 [488]

Group: # is the number of queries or boxes, and the ceiling the number without a re-executed counterexample, the most any method can prove. Square Brackets: without the rounding allowance of the operator's offsets.

On the truncated-power form GenBaB proves 354 of 511 (146 budget hits and 11 errors of the tool, counted as not proved); with the B-spline operator it proves 490 (which carries our certified relaxation, the contribution of this paper), matching native β\beta-CROWN on every row except the pykan enclosure (15 of 36 boxes against 36). The anytime configuration computes the CROWN bound first and spends the remaining budget on branch and bound; it proves all 16 depth-2 MNIST queries, where the default root bound exceeds the budget.

AuthorsOpenReview ↗

W3 and Q3, depth and control or scientific KANs.

The native α\alpha-CROWN and β\beta-CROWN members now support any depth (Sec. 5.3, App. C.14), and Sec. 6 adds a "Depth" paragraph with Table 3 (details per member in App. C.14, Table 13) on 18 networks trained by us: MNIST classifiers, a cart-pole controller imitating a saturated LQR controller (actuator bound and one-step closed-loop reach on 162 boxes) and a Lorenz-63 KAN-ODE vector field (one-step reach on 64 boxes) at depth 2, 3 and 4 in both the degree-1 and the degree-3 regime, against the released α,β\alpha,\beta-CROWN on the ReLU conversion, under the same 60 s end-to-end budget and at twice that budget (queries proved):

Degree-3+SiLU regime

Networkdeptharchitectureceilingbest native member, 60 s / 120 sbest converted (released α,β\alpha,\beta-CROWN), 60 s / 120 s
MNIST classifier2[784,32,10]100100 / 10099 / 99
3[784,32,16,10]9592 / 9255 / 55
4[784,32,32,16,10]9489 / 9010 / 10
cart-pole controller2[4,16,1]161161 / 161155 / 155
3[4,8,8,1]157124 / 129140 / 140
4[4,8,8,8,1]16057 / 66127 / 133
Lorenz-63 KAN-ODE2[3,16,3]6464 / 6422 / 22
3[3,8,8,3]6358 / 634 / 4
4[3,8,8,8,3]632 / 20 / 0

Degree-1 no-base regime

Networkdeptharchitectureceilingbest native member, 60 s / 120 sbest converted (released α,β\alpha,\beta-CROWN), 60 s / 120 s
MNIST classifier2[784,32,10]6563 / 6463 / 65
3[784,32,16,10]7738 / 4242 / 60
4[784,32,32,16,10]650 / 026 / 41
cart-pole controller2[4,16,1]161161 / 161154 / 156
3[4,8,8,1]162131 / 137102 / 108
4[4,8,8,8,1]1589 / 90 / 0
Lorenz-63 KAN-ODE2[3,16,3]6161 / 6161 / 61
3[3,8,8,3]5656 / 5653 / 53
4[3,8,8,8,3]4728 / 4740 / 43

Bold: the larger of each pair at each budget.

The released α,β\alpha,\beta-CROWN, the overall winner of VNN-COMP 2024 and 2025, is a mature and highly optimized verifier, so this comparison favors the conversion; even so, at 60 s (Table 3) the best native member proves at least as many queries on 13 of the 18 networks and more on 11. For the 120 s entries (App. C.14, Table 14), every query left undecided at 60 s is run again with twice the budget. Where the conversion leads, the native member gains more on the degree-3 cart-pole networks, which narrows the lead from 16 to 11 queries at depth 3 and from 70 to 67 at depth 4, and on the degree-1 Lorenz-63 network at depth 4, where it overtakes the conversion and reaches the ceiling (47 against 43); on the degree-1 MNIST networks the conversion gains more (35 queries against 5). At 120 s the best native member proves at least as many queries on 13 networks and more on 12.

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

The paper presents a family of formal verification methods for B-spline Kolmogorov–Arnold Networks. It exploits shared input coordinates and spline knot partitions to construct exact star-set reachability for degree-1 networks without base branches, and conservative lifted-star relaxations for higher-degree networks and networks with SiLU base branches. It also implements KAN-specific variants of interval propagation, CROWN-style bounds, branch-and-bound, and MILP verification.

Critical strengths

-- The distinction between exact and relaxed regimes is useful, and Proposition 1 illustrates how incorrect extrapolation can invalidate verification. Theorem 2 provides a clear containment argument for the lifted-star construction.

-- The paper includes multiple verification families, conversion-based comparisons, structural and numerical ablations, and several application classes.

-- The paper's experiments cover 26 trained networks and several property types, including classification robustness, output ranges, ordering between input regions, barrier conditions, and reachability. The authors additionally compare native verification with verification after ReLU conversion and demonstrate verification of a trained cubic KAN barrier and controller.

Critical weaknesses

-- The comparative evaluation does not consistently establish performance under equivalent methods and resource limits. Under a strict end-to-end 60-second budget applied equally to native and converted methods, how do the existing results change, particularly for depth-2 MNIST?

-- Ttheoretical soundness should be distinguished more clearly from implementation-level guarantees. Sampling checks are useful diagnostics but do not certify numerical soundness. The authors should explain the practical acceptance threshold and numerical safeguards, and identify precisely what the Lean development proves versus what remains trusted numerical computation.

-- Why was optimized PWA allocation omitted from the closest baseline? Can you clarify which conclusions concern only the uniform-allocation variant?

-- Keep certified robustness around the predicted label distinct from certified accuracy.

Questions for authors

see above

5 comments
AuthorsOpenReview ↗

W/Q1, strict end-to-end 60 s budget.

Thank you for the careful review, particularly highlighting the need for equal resource limits and for separating theoretical soundness from implementation-level guarantees. We answer each point with new experiments; added text is blue in the revised PDF.


We have updated the results to follow one consistent protocol: 60 s of wall-clock time per query, measured end to end by a supervising process and covering loading, conversion, initialization, the attack and the verification. In the submission the 60 s limit of native β\beta-CROWN started only after its root bound, so 41 of the 50 depth-2 MNIST queries ran longer; under the new protocol these runs count as timeouts. Table 2 is updated, and App. C.11 (Table 10) lists every entry that the 60 s timeout changes, against the same method under its own limits.

The CROWN column of Table 2 groups CROWN, α\alpha-CROWN and β\beta-CROWN and still reports the strongest of the three on each row. On depth-2 MNIST the root bound of α\alpha-CROWN and β\beta-CROWN takes about two minutes per query, so both time out under the budget, but plain CROWN proves all 47 queries within it (median 9.8 s), so the entry of Table 2 is unchanged:

Row (protocol)#ceilingCROWNα\alpha-CROWNβ\beta-CROWNTable 2 column
MNIST, depth 2 (own limits)504747474747
MNIST, depth 2 (60 s budget; budget hits)5047470 (50)0 (47)47
CS2 enclosure, degree 1, width ratio (both protocols)36–1.471.111.00 (9)1.00

In parentheses: runs stopped at the 60 s limit. β\beta-CROWN's attack falsifies the 3 queries that have a counterexample before its root bound, so 47 of its runs reach the limit (α\alpha-CROWN: all 50); on CS2, β\beta-CROWN stops 9 of the 36 boxes under both protocols and still returns a sound enclosure for each.

PWA-MILP on UCI, the other row that the budget changes (Table 2 reports the optimized variant; the uniform one is in Table 5):

RowMember#ceilingown limits60 s budget (budget hits)
UCI ×3, degree 3PWA-MILP, optimized (Table 2)480462462426 (36)
UCI ×3, degree 3PWA-MILP, uniform, K = 4 (Table 5)480462442439 (3)

Every other entry of Tables 2 and 9 is identical under both protocols, so the ranking of the members changes on these two rows only: on depth-2 MNIST α\alpha-CROWN and β\beta-CROWN fall to 0 while the CROWN column of Table 2 stays at 47, and on degree-3 UCI the optimized PWA-MILP falls from the ceiling to 426, below IBP (431).

The converted methods are not part of Table 2; they are compared on paired query subsets in App. C.9, and under the same budget only these entries change (the conversion counts against the budget):

RowConverted method#ceilingown limits60 s budget
degree 3, 2–30 inputsReLU exact star381365307299
MNIST, degree 3released α,β\alpha,\beta-CROWN1612107
Fashion-MNISTbest converted method16960
MNIST, depth 2best converted method1616110

On depth-2 MNIST the conversion alone takes 531–561 s, and on Fashion-MNIST 19–79 s.

AuthorsOpenReview ↗

W/Q2, theoretical soundness against implementation-level guarantees.

Appendix C.13 establishes every Robust verdict, proved box and certified enclosure of the native members behind Tables 2, 3 and 9 with a separate validator, which recomputes each certificate on the exact network in outward-rounded arithmetic, with safe LP bounds from the solver's duals, so the validated verdicts do not depend on solver tolerances. The acceptance rule has no tolerance: a verdict holds only if the rigorous bound is positive (nonnegative for a non-strict property), and enclosures are corrected outward. The sampling and attack checks are diagnostics only, and no verdict is derived from them.

CertificatesResult
networks with up to 30 inputs: all 28,947 certificates behind Tables 2 and 9all valid; 7 enclosure ends widened by at most 1.0×10−71.0\times10^{-7}, verdicts unchanged
784-input rows: every certificate behind Tables 2 and 9all valid
depth networks: all 1,428 proofs of β\beta-CROWN and the star-set modes, including every proof behind Table 3all valid
pooled counterexamples: 528all re-execute as true violations in interval arithmetic
smallest validated margin1.4×10−31.4\times10^{-3} (robustness), 1.3×10−41.3\times10^{-4} (any property)

What the Lean development proves. Every formal statement of the paper, Lemmas 1–6, Theorems 1 and 2, Corollary 1 and Propositions 1–3, together with reach-tube soundness, is machine-checked in Lean 4 with Mathlib, and the written proofs were checked by hand (App. B); Lemma 4 is checked under the equivalent hypothesis that ϕ′\phi' is M2M_2-Lipschitz. The float64 evaluation, the LP solver and the sampling are the trusted computations, and the validation above bounds their error. The main text summarizes this in the paragraph "Numerical soundness" (Sec. 6).

AuthorsOpenReview ↗

W/Q3, optimized PWA allocation.

We had omitted it because the code is not readily available; we now implement it, and Table 2 now uses the optimized piece allocation and MILP encoding of Schwartz et al. (2026). App. C.12 (Table 12) compares the optimized with the uniform variant of the submission at equal piece budgets, with uniform pieces in the ReLU-sum encoding as a control to separate the allocation from the encoding (queries proved under the per-solve limits of Table 5, K = 4 unless stated):

Task (#)ceilinguniformuniform pieces, ReLU-sum encodingoptimizedmean certified error band (smaller is tighter), uniform → optimized
Annulus (660)4514414414490.240 → 0.0529
Two-moons (500)4914914914917.19e-3 → 3.04e-3
Gaussian-4 (120)1151151151151.14e-3 → 5.25e-4
UCI ×3 (480)4624374614626.53e-4 → 1.23e-4
CS1 barrier (129)1291291291296.26e-4 → 3.75e-4
CS2 enclosure (36), width ratio (smaller is tighter)–1.0381.0381.0293.34e-3 → 1.83e-3
CS3 Euler step (21)212121219.18e-5 → 6.87e-5
CS4 range (64)646464641.11e-3 → 6.17e-4
MNIST, 784 inputs (16), K = 2100007.59e-5 → 4.09e-5
MNIST, 784 inputs (16), K = 4108312.05e-5 → 1.05e-5

The optimized pieces shrink the certified error band, which bounds the interpolation error of each edge, by 1.3× (CS3) to 5.3× (UCI). On the annulus the gain (449 against 441) comes from the pieces, since the optimized pieces in our shared-binary encoding also prove 449; on UCI it comes from the encoding (uniform pieces in the ReLU-sum encoding already prove 461), so the node-limit shortfall of the submitted PWA-MILP on MAGIC and Dry Bean was a property of our encoding, not of the method. At 784 inputs the optimized variant proves fewer queries than the uniform one (1 against 8 at K = 4), because every query reaches the limit and its ReLU-sum encoding needs 31,119 binaries against 3,136 shared ones.

The optimized allocation therefore narrows the advantage of the native members but does not remove it: β\beta-CROWN reaches the ceiling on every row, including all 10 provable 784-input queries. Under the 60 s budget of Table 2 (see W1) the optimized PWA-MILP proves 449 of 451 on the annulus (uniform: 441) and 426 of 462 on UCI, where 36 queries reach the budget (uniform: 439), and it reaches the ceiling on the other degree-3 rows.

The conclusions that concern only the uniform variant are now labeled as such. Table 2, Fig. 2(c) and App. C.12 use the optimized variant.

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

This paper develops native verification methods for B-spline Kolmogorov–Arnold Networks. It establishes exact reachability for degree-1 networks without base branches and sound relaxations for higher-degree networks and SiLU branches. The evaluation covers 26 trained networks, including robustness, output bounds, reachability, and verification of a learned barrier and controller.

Critical strengths
  • The framework exploits KAN-specific structure, particularly shared input-coordinate partitions and spline support boundaries.

  • The benchmark covers several useful property classes. Verifying all three barrier conditions directly on the trained cubic barrier and controller is particularly valuable. The comparison with converted networks and the disclosure of failed numerical checks also help clarify the methods’ practical limits.

Critical weaknesses
  • The comparative results need a more consistent protocol. The PWA-MILP baseline replaces optimized piece allocation with uniform pieces, potentially weakening the original method. Timeout handling also differs: Appendix C.8 counts native β-CROWN results despite 41 of 50 depth-2 MNIST queries exceeding the stated 60-second limit, while over-limit converted runs are counted as timeouts. These choices limit the conclusions about relative efficiency and coverage.

  • Evidence for scalability remains limited. Every benchmark network has at most two layers, and the native optimized CROWN implementations support only this depth. Most 784-input examples are single-layer additive models, whose margins separate into univariate problems; IBP with final-layer elision already reaches the verification ceiling there. These results demonstrate high-dimensional input handling, but provide less evidence for verification of deep KAN compositions.

Questions for authors
  1. Does the method ranking remain unchanged under a common end-to-end timeout, including initialization and attack costs?

  2. How does comparison with optimized PWA piece allocation affect the reported advantage over PWA-MILP?

  3. Given the numerical enclosure failures reported in Appendix C.12, can final certificates be independently validated or conservatively corrected for solver tolerances?

5 comments
AuthorsOpenReview ↗

W1 and Q1, common end-to-end timeout.

Thank you for the careful review, particularly highlighting the inconsistency with our presentation of timings and the question of scalability. We answer the three questions with new experiments; added text is blue in the revised PDF.


We have updated the results to follow one consistent protocol: 60 s of wall-clock time per query, measured end to end by a supervising process and covering loading, conversion, initialization, the attack and the verification. You are right about the 41 over-limit depth-2 MNIST queries: the 60 s limit of native β\beta-CROWN started only after its root bound, and under the new protocol these runs count as timeouts. Table 2 is updated, and App. C.11 (Table 10) lists every entry that the 60 s timeout changes, against the same method under its own limits.

The CROWN column of Table 2 groups CROWN, α\alpha-CROWN and β\beta-CROWN and still reports the strongest of the three on each row. On depth-2 MNIST the root bound of α\alpha-CROWN and β\beta-CROWN takes about two minutes per query, so both time out under the budget, but plain CROWN proves all 47 queries within it (median 9.8 s), so the entry of Table 2 is unchanged:

Row (protocol)#ceilingCROWNα\alpha-CROWNβ\beta-CROWNTable 2 column
MNIST, depth 2 (own limits)504747474747
MNIST, depth 2 (60 s budget; budget hits)5047470 (50)0 (47)47
CS2 enclosure, degree 1, width ratio (both protocols)36–1.471.111.00 (9)1.00

In parentheses: runs stopped at the 60 s limit. β\beta-CROWN's attack falsifies the 3 queries that have a counterexample before its root bound, so 47 of its runs reach the limit (α\alpha-CROWN: all 50); on CS2, β\beta-CROWN stops 9 of the 36 boxes under both protocols and still returns a sound enclosure for each.

PWA-MILP on UCI, the other row that the budget changes (Table 2 reports the optimized variant; the uniform one is in Table 5):

RowMember#ceilingown limits60 s budget (budget hits)
UCI ×3, degree 3PWA-MILP, optimized (Table 2)480462462426 (36)
UCI ×3, degree 3PWA-MILP, uniform, K = 4 (Table 5)480462442439 (3)

Every other entry of Tables 2 and 9 is identical under both protocols, so the ranking of the members changes on these two rows only: on depth-2 MNIST α\alpha-CROWN and β\beta-CROWN fall to 0 while the CROWN column of Table 2 stays at 47, and on degree-3 UCI the optimized PWA-MILP falls from the ceiling to 426, below IBP (431).

The converted methods are not part of Table 2; they are compared on paired query subsets in App. C.9, and under the same budget only these entries change (the conversion counts against the budget):

RowConverted method#ceilingown limits60 s budget
degree 3, 2–30 inputsReLU exact star381365307299
MNIST, degree 3released α,β\alpha,\beta-CROWN1612107
Fashion-MNISTbest converted method16960
MNIST, depth 2best converted method1616110

On depth-2 MNIST the conversion alone takes 531–561 s, and on Fashion-MNIST 19–79 s.

AuthorsOpenReview ↗

W1 and Q2, optimized PWA piece allocation.

Table 2 now uses the optimized piece allocation and MILP encoding of Schwartz et al. (2026), which we reimplemented since the code is not readily available. App. C.12 (Table 12) compares the optimized with the uniform variant of the submission at equal piece budgets, with uniform pieces in the ReLU-sum encoding as a control to separate the allocation from the encoding (queries proved under the per-solve limits of Table 5, K = 4 unless stated):

Task (#)ceilinguniformuniform pieces, ReLU-sum encodingoptimizedmean certified error band (smaller is tighter), uniform → optimized
Annulus (660)4514414414490.240 → 0.0529
Two-moons (500)4914914914917.19e-3 → 3.04e-3
Gaussian-4 (120)1151151151151.14e-3 → 5.25e-4
UCI ×3 (480)4624374614626.53e-4 → 1.23e-4
CS1 barrier (129)1291291291296.26e-4 → 3.75e-4
CS2 enclosure (36), width ratio (smaller is tighter)–1.0381.0381.0293.34e-3 → 1.83e-3
CS3 Euler step (21)212121219.18e-5 → 6.87e-5
CS4 range (64)646464641.11e-3 → 6.17e-4
MNIST, 784 inputs (16), K = 2100007.59e-5 → 4.09e-5
MNIST, 784 inputs (16), K = 4108312.05e-5 → 1.05e-5

The optimized pieces shrink the certified error band, which bounds the interpolation error of each edge, by 1.3× (CS3) to 5.3× (UCI). On the annulus the gain (449 against 441) comes from the pieces, since the optimized pieces in our shared-binary encoding also prove 449; on UCI it comes from the encoding (uniform pieces in the ReLU-sum encoding already prove 461), so the node-limit shortfall of the submitted PWA-MILP on MAGIC and Dry Bean was a property of our encoding, not of the method. At 784 inputs the optimized variant proves fewer queries than the uniform one (1 against 8 at K = 4), because every query reaches the limit and its ReLU-sum encoding needs 31,119 binaries against 3,136 shared ones.

The optimized allocation therefore narrows the advantage of the native members but does not remove it: β\beta-CROWN reaches the ceiling on every row, including all 10 provable 784-input queries. Under the 60 s budget of Table 2 (Part 1) the optimized PWA-MILP proves 449 of 451 on the annulus (uniform: 441) and 426 of 462 on UCI, where 36 queries reach the budget (uniform: 439), and it reaches the ceiling on the other degree-3 rows.

Fig. 2(c) now plots the optimized variant (89, 90 and 90 of 120 at K = 2, 4, 8; medians 0.114, 0.246 and 0.582 s). The statements that concern only the uniform variant are labeled as such (App. C.2, C.7 and C.9).

AuthorsOpenReview ↗

Q3, independent validation of the certificates.

Appendix C.13 establishes every Robust verdict, proved box and certified enclosure of the native members behind Tables 2, 3 and 9 with a separate validator, which recomputes each certificate on the exact network in outward-rounded arithmetic, with safe LP bounds from the solver's duals, so the validated verdicts do not depend on solver tolerances. The acceptance rule has no tolerance: a verdict holds only if the rigorous bound is positive (nonnegative for a non-strict property), and enclosures are corrected outward.

CertificatesResult
networks with up to 30 inputs: all 28,947 certificates behind Tables 2 and 9all valid; 7 enclosure ends widened by at most 1.0×10−71.0\times10^{-7}, verdicts unchanged
784-input rows: every certificate behind Tables 2 and 9all valid
depth networks: all 1,428 proofs of β\beta-CROWN and the star-set modes, including every proof behind Table 3all valid
pooled counterexamples: 528all re-execute as true violations in interval arithmetic
smallest validated margin1.4×10−31.4\times10^{-3} (robustness), 1.3×10−41.3\times10^{-4} (any property)

The enclosure failure of the submitted App. C.12 (now App. C.17, item (iv)) is one of the seven widenings, and its verdict still holds rigorously.

The main text summarizes this in the paragraph "Numerical soundness" (Sec. 6).

Comments on the paper

2 comments
AuthorsOpenReview ↗

Paper and Supplement Updated with Blue Text

We have updated the paper with blue text, and the supplement now includes the additional experiments as described below.

We are grateful for the positive assessment of our work in this initial review. We believe our responses below clarify and answer the listed reviewer concerns. We are happy to continue an open dialogue if anything has not been sufficiently answered.

AuthorsOpenReview ↗

Last Day of Discussion

With today being the last day of the discussion, and since we have not received any replies to our rebuttal, we want to thank the reviewers again for the time they have taken while considering our manuscript, particularly in this new AI era of high submission volumes and high reviewer load.

We hope the initial positive assessment has been further increased by our responses to the few points raised for clarification.

Many thanks, The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.